Використання електронних таблиць для розв’язку оптимізаційних задач

Використання електронних таблиць для розв’язку оптимізаційних задач

План:

1. Оптимізаційна задача

2. Приклади розв’язання оптимізаційних задач

3. Варіанти завдань для самостійного розв’язку

1. Оптимізаційна задача

Оптимізаційною називають задачу знаходження мінімуму (максимуму) функції за наявності певних обмежень на значення незалежних змінних. Задачі умовної оптимізації вивчає розділ прикладної математики під назвою “оптимальне (математичне) програмування”. Цей напрямок зародився в 30-х роках минулого століття під час аналізу передусім економічних задач ефективного планування випуску продукції, управління, розміщення виробництва і т. ін. Сам термін “оптимальне програмування” не є вдалим; він сформувався як калька з англійської “optimal programming” (що в даному випадку правильно перекласти як “оптимальне планування”) і, звичайно, не має ніякого відношення до “програмування” як розробки алгоритмів для комп’ютерних програм. Суть принципу оптимального планування полягає у прагненні знайти таке планово-управлінське рішення X=(x1, x2, …, xn), де xj, (j=) – його компоненти, яке найкращим чином ураховувало б внутрішні можливості та зовнішні умови виробничої діяльності суб’єкта господарювання.

Математично задачу умовної оптимізації традиційно записують у такому вигляді: знайти мінімум (максимум) функції

F(X) = F(x1, x2, …, xn).

За наявності обмежень

i(x1, x2, …, xn){,,}0, i=.

Тут F(X) – математичний запис критерію оптимальності (цільова функція). Запис {,,} означає в певному обмеженні можливість вибору одного із знаків ,  або .

Існує декілька критеріїв класифікації оптимізаційних задач. У випадку, коли цільова функція F(X) та всі функції i(x1, x2, …, xn), i= в обмеженнях є лінійними відносно своїх аргументів, оптимізаційна задача називається задачею лінійного програмування, в інших випадках – нелінійного програмування. За характером зміни управляючих змінних x1, x2, …, xn виділяють неперервні та дискретні задачі. Якщо значення змінної вибираються з множини цілих чисел, то такий різновид дискретної задачі називається задачею цілочисельного програмування.

За весь період розвитку математичного програмування розроблено багато чисельних методів розв’язку оптимізаційних задач. Найбільш поширеним методом розв’язку задач лінійного програмування є симплекс-метод [1]. Для окремих класів задач лінійного програмування (транспортних, задач на призначення тощо) розроблені окремі спеціалізовані методи (метод потенціалів для транспортної задачі тощо) [4]. Багато з чисельних методів розв’язку оптимізаційних задач реалізовано як у сучасних програмах-генераторах підтримки прийняття рішень, так і в “надбудовах” до пакетів офісних програм, зокрема електронних таблиць.

2. Приклади розв’язання оптимізаційних задач

Задача 1. Митниця замовляє будівництво митних складів. Для будівництва є 4 типових проекти складів, у кожному з який передбачено 4 типи приміщень. Кількість приміщень i-го типу в одному складі j-го типу, потреба в приміщеннях i-го типу і вартість проекту кожного типу наведені в таблиці. Побудувати модель і на її основі сформулювати екстремальну задачу знаходження плану будівництва митних складів (X=(x1, x2,..., xn), де xj – число складів j-го типу, n=4), що задовольняє потребу в приміщеннях, для якого витрати на будівництво будуть мінімальні.

Розв’язок. Позначимо через aij кількість приміщень i-го типу в проекті j-го типу (i=, j=, m=4), cj – вартість проекту j-го типу, bi – потреба в приміщеннях i-го типу. Тоді вартість будівництва складів буде виражатись лінійною функцією

F(X) = c1x1+c2x2+…+cnxn=.              (1)

Кількість приміщень i-го типу для встановленого плану будівництва складатиме

i(X) = ai1x1+ai2x2+…+ainxn=.              (2)

Тоді екстремальну задачу можна сформулювати так:

F(X)min;              i(X)bi, xj0, xj – ціле (i=, j=).              (3)

Це цілочисельна задача лінійного програмування. Для її розв’язання застосуємо надбудову “Пошук рішення” до пакета Microsoft Excel. Розташування вхідних даних та формул для обчислень на листі електронної таблиці можна організувати, як показано на рисунку 1. Вектор невідомих X (оптимальний план будівництва) розташуємо в діапазоні чарунок B8:E8, матрицю A=(aij) – в діапазоні B3:E6, вектор потреби в приміщеннях B=(bi) – в діапазоні G3:G6, вектор вартості проекту кожного типу C=(cj) – в діапазоні B7:E7. Формулу для обчислень сумарної вартості будівництва F(X) розташуємо в чарунці F7 (цільова чарунка), а формули для обчислень функцій i – в діапазоні F3:F6. Оскільки ці формули однотипні, доцільно, використовуючи властивості абсолютної та відносної адресації чарунок, ввести відповідну формулу в цільову чарунку та скопіювати її в діапазон чарунок F3:F6. Для розрахунку за формулою (2) використаємо стандартну функцію Excel СУММПРОИЗВ, набравши в чарунці F7 формулу =СУММПРОИЗВ($B$8:$E$8;B7:E7).

Рис. 1. Розташування даних та формул на листі електронних таблиць

Виконавши необхідні дії щодо введення даних та формул, приступаємо до розв’язку оптимізаційної задачі. Для цього викликаємо діалог “Поиск решения” (Пункт меню Сервис->Поиск решения) та вводимо необхідні дані для розв’язку (див. рис. 2).

Рис. 2. Вікно діалогу “Поиск решения”

Для введення обмежень за формулами (2) необхідно використовувати діалог “Добавление/Изменение ограничения” (рисунок 3). Зверніть увагу, що для одночасного введення декількох обмежень можна використовувати діапазони чарунок. Так, з 12 обмежень (3) ми ввели для них лише 3 формули (рис. 2).

Рис. 3. Вікно діалогу “Добавление/Изменение ограничения”

Після введення необхідних даних для пошуку рішення можна встановити певні параметри самого процесу чисельного розрахунку оптимального розв’язку. Це здійснюється за допомогою діалогу “Параметры поиска решения”, який викликається за допомогою кнопки “Параметры” вікна діалогу “Поиск решения” (рис. 4). Зокрема, для нелінійних оптимізаційних задач можна встановити тип методу лінеаризації задачі (зведення початкової нелінійної задачі до послідовності лінійних задач), критерій збіжності задачі, максимальну кількість ітерацій тощо. У даному випадку ми знаємо, що наша задача є задачею лінійного цілочисельного програмування, тому варто встановити прапорець “Линейная модель” для вибору саме лінійних алгоритмів розв’язку (симплекс-методів), що робить більш ефективним процес знаходження оптимального рішення.

Рис. 4. Вікно діалогу “Параметры поиска решения”

Після введення всіх необхідних даних та параметрів у вікні “Поиск решения” запускаємо процес чисельного розв’язку. Після його закінчення буде запропоновано зберегти отримані результати, а також отримати звіти про хід чисельного розв’язку (рис. 5).

Рис. 5. Вікно діалогу “Результаты поиска решения”

Звіти зберігаються на окремих листах робочої книги. В оптимізаторі Excel існують три типи звітів:

1)     звіт про результати;

2)     звіт про стійкість;

3)     звіт про границі.

Звіт про результати показує значення чарунок розв’язку до та після роботи оптимізатора, відображає вільні (незадіяні) ресурси, деталізує обмеження для кожної чарунки окремо (навіть, як у даному випадку, обмеження вводились “пакетом”). Для цієї задачі ми отримаємо звіт, що наведений в таблиці нижче.

Звіт про стійкість формується лише для неперервних задач та включає в себе дві частини (таблиці). В таблиці 1 наводяться:

а) результат розв’язку задачі;

б) редукована вартість, тобто додаткові двоїсті змінні, що характеризують зміну цільової функції під час вимушеного включення даної одиниці продукції в оптимальне рішення;

в) коефіцієнти цільової функції;

г) граничні значення приросту коефіцієнтів цільової функції, при яких зберігається набір змінних, що входять в оптимальне рішення.

У таблиці 2 наводяться значення для обмежень:

а) величина використаних ресурсів;

б) двоїсті оцінки (тіньова ціна), які показують, як зміниться цільова функція при зміні ресурсів на одиницю;

в) значення прирощень ресурсів, при яких зберігається оптимальний набір змінних, що утворюють рішення.

Звіт про границі показує, в яких межах може змінюватись випуск продукції, що входить до оптимального рішення, при збереженні структури рішення. У цьому звіті наводяться:

а) значення змінних чарунок в оптимальному рішенні;

б) нижні границі зміни їх значень;

в) значення цільової функції (графа “Целевой результат”), якщо даний тип продукції виробляється на нижній межі;

г) верхні границі зміни чарунок рішення;

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

У результаті чисельного розв’язку розглянутої задачі буде отриманий оптимальний план (0,0,3,8) загальною вартістю 138 млн. грн. Аналізуючи цей план, можна сказати, що він є напруженим за першим типом приміщень, і можна порадити розробникам (при збереженні аналогічної потреби на всі типи приміщень) розробляти проекти з порівняно більшою кількістю приміщень цього типу.

Задача 2. У місті є 4 домобудівні компанії (ДБК) А1, А2, А3, А4, виробничі потужності яких ai (і=, m=4) відомі. Вироби ДБК поставляються 4 споруджуваним житловим масивам міста B1, B2, B3, B4, потреби у виробах ДБК bj (j=, n=4) яких також відомі. Ці відомості, а також витрати cij пов’язані з доставкою одного комплекту виробів з i-го ДБК до j-го житлового масиву, задані таблицею. Побудувати модель і на її основі сформулювати екстремальну задачу знаходження такого плану доставки, щоб сумарні витрати на доставку виробів ДБК були мінімальними і були задоволені потреби всіх житлових масивів.