Лінійна оптимізація

Лінійне програмування – розділ математичного програмування, присвячений знаходженню екстремуму лінійних функцій кількох змінних при додаткових лінійних обмеженнях, що накладаються на змінні.

Методи вирішення задач поділяються на універсальні (наприклад, симплексний метод) та спеціальні. За допомогою універсальних методів вирішуються будь-які задачі лінійного програмування.

Особливістю задач лінійного програмування є досягнення екстремуму цільової функції на межі області допустимих значень.

Приклад №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)}.

Формулювання математичної моделі задачі:

• змінні для вирішення задачі: добові об’єми виробництва матеріалів А і В (В3:В4);

• визначення цільової функції (критерію оптимізації): серед усіх припустимих значень змінних знайти такі добові об’єми виробництва матеріалів, що максимізують сумарний прибуток від виробництва (D5);

• обмеження на змінні: об’єми виробництва матеріалів не можуть бути від’ємними (В3:В4≥0) та витрати сировини обох типів матеріалів не можуть перевищувати максимально можливих запасів сировини (В11:С11≤В12:С12);

• обмеження на величину попиту на матеріали: об’єми виробництва матеріалів не можуть перевищувати попит на будматеріали (В3:В4≤Е3:Е4).

Для вирішення даної задачі будемо використовувати програму Excel, інструмент Поиск решения. Обираємо опцію Сервис, Поиск решения. У вікні Поиск решения, що з'явилося (Рис. 4), встановлюємо максимальне значення у цільовій клітині D5, вказуємо для зміни клітини В3:В4 та додаємо обмеження.

Рис. 4.

Натискаємо кнопку Параметры. У вікні, що з’явилося (рис. 5), встановлюємо параметри пошуку рішення (метод оцінки, метод чисельного диференціювання та алгоритм оптимізації). Натискаємо кнопку ОК та переходимо назад у вікно Поиск решения, натискаємо кнопку Выполнить. Програма виконує обчислення.

Після закінчення процесу пошуку на екрані з’являється вікно Результаты поиска решения. Потрібно обрати, які дані залишити, та тип звіту, а також чи зберігати сценарій отриманого рішення. Встановивши опції, натискаємо ОК та отримаємо звіт вказаного типу (рис. 6-8).

Рис. 5.

Опис звітів про рішення задачі

Звіт по результатах (рис. 6) – таблиця Целевая ячейка виводить відомості про цільову функцію; таблиця Изменяемые ячейки показує значення змінних, отримані в результаті вирішення задачі; таблиця Ограничения відображає результати оптимального вирішення для обмежень і для граничних умов. В полі Формула наведені залежності, що були введені у вікно Поиск решения, в поле Разница – величини використаного матеріалу. Якщо матеріал використаний повністю, то в полі Статус виводиться связанное, за неповного використання матеріалу в цьому полі виводиться не связан. Для граничних умов замість величини невикористаного продукту показана різниця між значенням змінної і заданої для неї граничною умовою.

Рис. 6.

Звіт по стійкості (рис. 7) – у таблиці Изменяемые ячейки наводиться результат вирішення задачі. У таблиці Ограничения показуються значення обмежень, для яких зберігається оптимальний набір змінних, що входять у оптимальне рішення.

Рис. 7.

Звіт по лімітах (рис. 8) – у звіті показано, у яких лімітах може змінюватися кількість матеріалів в оптимальному рішенні; наводяться значення змінних у оптимальному рішенні, а також нижні і верхні границі зміни значень змінних; вказані значення цільової функції за умови випуску даного типу продукції на верхній та нижній границях.

Рис. 8.

Приклад №2. Визначення складу добрив.

Для випуску добрив типів 1 і 2 використовуються хімічні речовини А, В, С і D, вимоги до змісту яких у добривах наведені в табл. 5. Для першого типу добрив: не більше 70% речовини А і не більше 40% речовини В; для другого типу добрив: від 30% до 50% речовини В, не менше 25% С і не більше 65% D.

Характеристики і запаси мінералів, що використовуються для виробництва хімічних речовин А, В, С і D, наведені в табл. 6.

Таблиця 5

Таблиця 6

Ціна 1 т добрива типу 1 дорівнює 320 у.о., ціна 1 т добрива типу 2 – 350 у.о. Необхідно максимізувати прибуток від продажу добрив типів 1 і 2.

Для вирішення даної задачі будемо використовувати програму MS Excel, процедуру Поиск решения. Запишемо умови задачі у робочій книзі (рис. 9).

Рис. 9.

Для математичного запису обмежень на зміст хімічних речовин у добривах використовуються допоміжні клітини: 70% речовини А у добриві типу 1 записано у клітині С7 (=C4*B12), обмеження на зміст речовини В - Е7 (=B12*E4), Е8 (=B13*E5), Е9 (=B13*E6), на зміст речовини С - G8 (=G5*B13), на зміст D - І8 (=I5*B13).

Кількість добрива визначається як сумарний склад добрива у хімічних речовинах, наприклад для добрива типу 1 – у клітині В12 (=СУММ(C12:F12)).

Загальна ціна всього об’єму добрив типів 1 і 2 у клітинах Н12 і Н13 визначається за допомогою формули масиву {=B12:B13*G12:G13}. Загальна кількість речовини А у обох типах добрив у клітині С14 знаходиться за формулою: =СУММ(C12:C13), аналогічно для інших речовин. Загальна кількість речовини А у трьох типах мінералів у клітині С21 знаходиться за формулою масиву {=СУММ($B$18:$B$20*C18:C20)}, для інших речовин – формула копіюється. Загальні витрати у масиві клітин I18:I20 визначаються за формулою масиву {=B18:B20*H18:H20}.

Сумарний прибуток у клітині Н14 визначається як різниця сумарної загальної ціни і сумарних витрат: =СУММ(H12:H13)-I21.

Формулювання математичної моделі задачі:

• змінні для вирішення задачі: кількість хімічних речовин А, В, С і D у добривах типів 1 і 2 (С12:F13) та кількість мінералів I, II і III (В18:В20);

• визначення цільової функції (критерію оптимізації): серед усіх припустимих значень змінних знайти таку кількість хімічних речовин і мінералів, що максимізують сумарний прибуток від виробництва (Н14);

• обмеження на змінні: об’єми виробництва хімічних речовин та мінералів не можуть бути від’ємними (С12:F13≥0, В18:В20≥0), а також кількість мінералів не може перевищувати максимально можливих запасів (В18:В20≤G18:G20) та кількість хімічних речовин А, В, С і D у добривах не може бути більше, ніж кількість речовин у мінералах (С14:F14≤C21:F21);

• обмеження на відсотковий зміст хімічних речовин у добривах згідно з умовами задачі - обмеження на зміст речовини А: у першому типі добрив С12≤С7, на зміст речовини В: у першому типі добрив D12≤E7, у другому типі добрив D13≤E9 і D13≥E8, на зміст речовини С: у другому типі добрив E13≥G8, на зміст речовини D:, у другому типі добрив F13≤I8.

Для вирішення даної задачі будемо використовувати програму Excel, інструмент Поиск решения. Обираємо опцію Сервис, Поиск решения. У вікні Поиск решения встановлюємо максимальне значення у цільовій клітині Н14, вказуємо для зміни клітини С12:F13 та В18:В20 і додаємо обмеження.

У вікні Параметры встановлюємо параметри пошуку рішення (метод оцінки, метод чисельного диференціювання та алгоритм оптимізації). У вікні Результаты поиска решения задаємо виведення всіх типів звітів.

Результати вирішення задачі показані на рис. 10.

Рис. 10.