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

Розв’язок. Позначимо через xij кількість комплектів ДБК, що постачаються з i-го пункту виробництва на j-й житловий масив. Тоді загальна вартість перевезень визначатиметься лінійною функцією

F(X) =F(xij) = .                                                                      (4)

Загальна кількість комплектів виробів, що постачаються на j-й житловий масив, визначається формулою

j(X) = .                                                                                    (5)

а реальне навантаження на i-ту ДБК – формулою

i(X) = .                                                                                    (6)

Виходячи з цього, оптимізаційну задачу можна сформулювати так:

F(X)min;              i(X)ai, j(X)bj, xij0, xij – ціле (i=, j=).              (7)

Задача (7) є цілочисельною лінійною транспортною задачею. Для її розв’язку в системі Excel розташуємо вхідні дані та формули для обчислень так, як показано на рисунку 6.

Рис. 6. Розташування вхідних даних та формул на листі електронної таблиці для розв’язання транспортної оптимізаційної задачі

Матрицю невідомого плану перевезень розмістимо в діапазоні чарунок B14:E17, матрицю вартості перевезень – в діапазоні B4:E7, вектор потреб – в діапазоні B9:E9, вектор виробничих потужностей – в діапазоні F4:F7. Як і в попередній задачі, будемо використовувати для обчислень значень цільової функції F та функцій (5), (6), що входять до складу лівих частин рівнянь системи обмежень, убудовані в Excel функції СУММПРОИЗВ та СУММ. Для визначення цільової функції в чарунку F13 введемо формулу =СУММПРОИЗВ(B14:E17; B4:E7). Для обчислення 1 в чарунку F4 введемо формулу =СУММ(B14:E14) і скопіюємо її значення в діапазон F5:F7. Аналогічно для обчислень 1 в чарунку B9 введемо формулу =СУММ(B14:B17) та скопіюємо її в діапазон C9:E9. Після введення формул та вхідних даних приступаємо до чисельного розв’язку задачі за допомогою надбудови “Поиск решения”. Вікно діалогу “Поиск решения” для даної задачі показано на рисунку 7.

Рис. 7. Вікно діалогу “Поиск решения” для розв’язку транспортної задачі

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

X = ,

якому відповідає значення цільової функції F(X)=2190.

Зауваження. Повторивши процес розрахунків, отримаємо інший оптимальний вектор

X =

зі значенням цільової функції на ньому F(X)=2190. З теорії лінійного програмування ми знаємо, що існують три можливі варіанти розв’язку екстремальної задачі: 1) існує єдиний оптимальний план; 2) жодного оптимального плану не існує; 3) існує безліч оптимальних планів, але з однаковим значенням цільової функції на них. У даному прикладі ми маємо справу саме з третім випадком.

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

Таблиця відповідності номерів варіантів порядковим номерам курсантів за журналом групи

Варіант 1

Задача 1

Виробничі об’єднання “Альфа”, “Сигма” і “Омега” випускають взаємозамінне нестандартне устаткування для чотирьох споруджуваних об’єктів. Перевезення устаткування від складів готової продукції до будівельних майданчиків виконуються транспортним агентством на спеціальних машинах (по одному комплекту на кожній) із середньою швидкістю 50 км/год. і тільки вночі. На час транспортування устаткування перекривається рух міського транспорту по всьому маршруту проходження вантажу. На всіх можливих маршрутах інтенсивність руху приблизно однакова. Однак рух міського транспорту може бути зупинено не більше ніж на три години. За кожні десять хвилин затримки агентство сплачує штраф у розмірі 200 грн.

Довжина (у кілометрах) можливих маршрутів від складів готової продукції до будівельних майданчиків (для об’єднань “Альфа”, “Сигма” і “Омега” – відповідно) наведені в табл. 1 – 3.

Наявність устаткування на першому, другому, третьому складах – 5, 4, 6 одиниць, кількість його, необхідна для установки на першому, другому, третьому і четвертому об’єктах, складає відповідно 4, 2, 3 і 4 одиниці.

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

              Таблиця1              Таблиця 2

              Таблиця 3

Задача 2

Цех меблевого комбінату випускає трельяжі, трюмо і тумбочки під телевізори. Норма витрати матеріалу в розрахунку на один виріб, планова собівартість, оптова ціна підприємства, плановий (місячний) асортимент і трудомісткість одиниці продукції наведені в табл. 4. Запас деревостружкових плит, дощок ялинових і березових 90, 30 і 14 м3 відповідно. Плановий фонд робочого часу 16800 людино-годин.