Розв’язок ЗЛП з допомогою 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° і рухаються до іншої заповненої клітинки і т.д., намагаючись повернутися в початкову клітинку. Якщо таке повернення можливе, одержуємо цикл і план не являється опорним; його можна зоптимізувати.
Розглянемо ряд простих методів побудови первісного опорного плану.