2015-04-08
675
Лінійне програмування – розділ математичного програмування, присвячений знаходженню екстремуму лінійних функцій кількох змінних при додаткових лінійних обмеженнях, що накладаються на змінні.
Методи вирішення задач поділяються на універсальні (наприклад, симплексний метод) та спеціальні. За допомогою універсальних методів вирішуються будь-які задачі лінійного програмування.
Особливістю задач лінійного програмування є досягнення екстремуму цільової функції на межі області допустимих значень.
Приклад №1. Планування виробництва будівельних матеріалів.
Фірма випускає два типи будівельних матеріалів А і В. Продукція обох типів надходить у продаж. Для виробництва матеріалів використовуються два типи сировини І і ІІ. Максимально можливі добові запаси сировини становлять 7 і 9 тон відповідно. Витрати продуктів І і ІІ на 1 тонну відповідних матеріалів наведені в табл. 4.
Таблиця 4
Вивчення ринку збуту показало, що добовий попит на матеріал В ніколи не перевищував попиту на матеріал А більше, ніж на 1 т. Попит на матеріал А не перевищує 3 т на добу. Оптові ціни однієї тони матеріалів: 4000 у.о. для В і 3000 у.о. для А. Яку кількість матеріалу кожного типу повинна виробляти фабрика, щоб прибуток від реалізації був максимальним?
|
|
|
Для вирішення даної задачі будемо використовувати програму MS Excel, процедуру Поиск решения. Запишемо умови задачі у робочій книзі ( рис. 3).
Рис. 3.
Загальний прибуток у клітинках D3:D4 визначається так: ={B3:B4*C3:C4}. Сумарний прибуток у клітині D5: =СУММ(D3:D4). Всього по типах сировини у клітинках В11 і С11 знаходиться, відповідно, за формулами: {=СУММ($B$3:$B$4*B9:B10)} і {=СУММ($B$3:$B$4*C9:C10)}.
Формулювання математичної моделі задачі:
v змінні для вирішення задачі: добові об’єми виробництва матеріалів А і В (В3:В4);
v визначення цільової функції (критерію оптимізації): серед усіх припустимих значень змінних знайти такі добові об’єми виробництва матеріалів, що максимізують сумарний прибуток від виробництва (D5);
v обмеження на змінні: об’єми виробництва матеріалів не можуть бути від’ємними (В3:В4≥0) та витрати сировини обох типів матеріалів не можуть перевищувати максимально можливих запасів сировини (В11:С11≤В12:С12);
v обмеження на величину попиту на матеріали: об’єми виробництва матеріалів не можуть перевищувати попит на будматеріали (В3:В4≤Е3:Е4).
Для вирішення даної задачі будемо використовувати програму Excel, інструмент Поиск решения. Обираємо опцію Сервис, Поиск решения. У вікні Поиск решения, що з'явилося (Рис. 4), встановлюємо максимальне значення у цільовій клітині D5, вказуємо для зміни клітини В3:В4 та додаємо обмеження.
|
|
|
Рис. 4.
Натискаємо кнопку Параметры. У вікні, що з’явилося (рис. 5), встановлюємо параметри пошуку рішення (метод оцінки, метод чисельного диференціювання та алгоритм оптимізації). Натискаємо кнопку ОК та переходимо назад у вікно Поиск решения, натискаємо кнопку Выполнить. Програма виконує обчислення.
Після закінчення процесу пошуку на екрані з’являється вікно Результаты поиска решения. Потрібно обрати, які дані залишити, та тип звіту, а також чи зберігати сценарій отриманого рішення. Встановивши опції, натискаємо ОК та отримаємо звіт вказаного типу (рис. 6-8).
Рис. 5.
