ьного асортименту продукції, визначенні плану товарообігу, а також в задачах розвитку і розміщення продуктивних сил, баз і складів систем звернення матеріальних ресурсів і т.д. Особливо широке застосування методи і моделі лінійного програмування отримали у вирішенні завдань економії ресурсів, виробничо-транспортних та інших завдань.
Економіко-математична модель будь-якої задачі лінійного програмування включає цільову функцію, оптимальне значення якої потрібно відшукати; обмеження у вигляді системи лінійних рівнянь або нерівностей; вимога невід'ємності змінних.
У загальному вигляді модель записується таким чином:
- Цільова функція. (1)
при обмеженнях:
(2.1, 2.2, 2.3)
При цьому a ij , b i , c j - задані постійні величини.
Завдання полягає в знаходженні оптимального значення функції 1 при дотриманні обмежень 2.1, 2.2 і 2.3.
Вектор, що задовольняє обмеженням, називається допустимим рішенням (планом) задачі лінійного програмування. План, при якому функція 1 досягає свого максимального / мінімального значення, називається оптимальним.
Симплексний метод.
Симплексний метод універсальний. З його допомогою можна вирішити будь-яке завдання лінійного програмування.
В основу симплексного методу покладена ідея послідовного поліпшення одержуваного рішення.
Геометричний сенс симплексного методу полягає в послідовному переході від однієї вершини багатогранника обмежень до сусідньої, в якій цільова функція приймає найкраще (або, по крайней мере, не найгірше) значення до тих пір, поки не буде знайдено оптимальне рішення - вершина, де досягається оптимальне значення функції мети.
Таким чином, маючи систему обмежень, приведену до канонічної формі, знаходять будь базисне рішення цієї системи, піклуючись тільки про те, щоб знайти його якомога простіше. Якщо перше ж знайдене базисне рішення виявилося допустимим, то перевіряють його на оптимальність. Якщо воно не оптимально, то здійснюється перехід до іншого, обов'язково допустимому базисного рішенням. Симплексний метод гарантує, що при цьому новому рішенні цільова функція, якщо і не досягне оптимуму, то наблизиться до нього. З новим допустимим базисним рішенням чинять ж до тих пір, поки не знайдеться рішення, яке є оптимальним.
Процес застосування симплексного методу передбачає реалізацію трьох його основних елементів:
) спосіб визначення якогось початкового допустимого базисного рішення задачі;
) правило переходу до більш оптимального рішення;
) перевірка оптимальності знайденого рішення.
Симплексний метод включає в себе ряд етапів і може бути сформульований у вигляді чіткого алгоритму (чіткого припису про виконання послідовних операцій). Це дозволяє успішно програмувати і реалізовувати його на ЕОМ. Завдання з невеликим числом змінних і обмежень можуть бути вирішені симплексним методом навіть вручну.
3. Отримання прибутку підприємств методом лінійного програмування
3.1 Підприємство з виробництва м'яких іграшок «Малишок»
Таблиця 11. Дані по закупкам підприємства «Малишок» на ресурси для виробництва продукції на кожному кроці.
Розмір інве...
