Розв’язок ЗЛП з допомогою MS Excel

Алгоритм такого розв’язку:

1. Виконати команду СервисÞНадстройки…. У вікні, що відкривається установити прапорець в режимі «Поиск решения».

2. Створити форму ЗЛМ (рисунок 34-а).

3. Використати команду: СервисÞПоиск решения (рисунок 34-б).

4. Вказати адресу цільової функції.

5. Перемикач установити на MAX.

6. Ввести адреси х1 та х2.

7. Ввести обмеження №1 по інструкції:

a. Команда «Добавить»;

b. Вказати адресу обмеження №1;

c. Установити знак «<=»;

d. Надрукувати ;

e. ОК.

8. Аналогічно ввести обмеження №2 та №3.

9. «Добавить» Þ ввести діапазон х1 та х2 Þ установити «>=»ÞОК.

10. Ввести умову цілочисленості змінних: ДобавитьÞввести діапазон х1, х2ÞЦЕЛÞОК.

11. Кнопка «Параметры», установити режим «Линейная модель».

12. Кнопка «Выполнить». Повідомлення: «Решение найдено».

13. «Сохранить найденое решение» ОК.

На рисунку 34-в представлені результати розрахунку.

а)

б)

в)

Рисунок 34. Розв’язок ЗЛП

Варіанти завдань

Вирішити задачу лінійного програмування симплекс-методом.

На заводі залізобетонних виробів маємо запаси сировини: цементу , щебеню , арматури . Одержати оптимальний план роботи заводу по випуску плит перекриття вартістю S за одиницю та стінових панелей вартістю Z. На виготовлення однієї плити витрата цементу , щебеню і арматури , на випуск панелі – відповідно , , .

Таблиця 18

№	Плита	Панель	Запаси	Вартість
										S	Z

Транспортна задача

Постановка задачі

Деякий однорідний продукт, скупчений у постачальників в кількості одиниць, потрібно доставити споживачам в кількості одиниць. Відома вартість перевозки одиниці вантажа від і-го постачальника до j-го споживача.

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

Поставлену задачу можна представити такою таблицею:

Представимо модель такої задачі.

Цільова функція:

[10.5]

Система обмежень випливає із умови:

a) всі вантажі повинні бути вивезені: [10.6]

b) всі потреби повинні бути забезпечені: ; [10.7]

c) перевозки повинні бути реальними .

Модель транспортної задачі, у якої називається закритою. Саме таку задачу ми і розглянемо.

Розглянемо систему обмежень [10.6] та [10.7]. Вона має рівнянь та невідомих. Якщо почленно скласти [10.6] та [10.7], то одержимо два однакових рівняння. Це вказує на те, що система обмежень лінійно залежна. Щоб з неї одержати лінійно незалежну систему, потрібно відкинути одне рівняння. Тому невироджений опорний план транспортної задачі має додатніх перевозок. Тобто в матриці плану повинно бути клітинок, що зайняті перевозками.

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

Розглянемо ряд простих методів побудови первісного опорного плану.