Додаток Б. Розв’язування задач лінійного програмування

Розв’язування задач лінійного програмування

Послідовність операцій розв’язку задач лінійного програмування розглянемо на такому прикладі:

при обмеженнях:

1 Розміщення коментарів і вихідної інформації в клітинках робочого поля.

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

Один із варіантів введення вихідної інформації для розв’язку задач наведений на рис. Б1.

Рисунок Б1 - Вихідна інформація задачі прикладу 2

на робочому полі

У всіх клітинках стовпців А, С, E, G знаходиться пояснювальний текст, який не впливає на рішення задачі. Цей текст служить тільки для наочності вихідної інформації.

У клітинках В2…В13, D10…D12, F10...F12 розміщена цифрова інформація, яка відповідає тексту зліва.

У клітинках Н2…Н4 розміщені нулі - початкові нульові значення шуканих змінних х1, х2 і х3. У клітинці Н7 розміщений вираз цільовій функції =В2*Н2+В3*Н3+В4*Н4, початкове значення якої рівне нулю при початкових нульових значеннях шуканих змінних.

У клітинках В16…В19 розміщені ліві частини обмежень-нерівностей:

= В10*Н2+D10*H3+F10*H4,

= В11*Н2+D11*H3+F11*H4,

= В12*Н2+D12*H3+F12*H4,

=Н2+Н3+Н4,

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

При роботі в Excel не потрібно переходити від обмежень нерівностей до рівності. Цю операцію виконає комп'ютер.

2 Команда «Сервіс» і введення вихідної інформації в діалогове вікно «Пошук рішення».

Розкривається МЛ команда «Сервіс» в головному меню; із змісту команди «Сервіс» розкривається МЛ команда «Пошук рішення»; на екрані з'являється діалогове вікно «Пошук рішення» (рис. Д3);

Рисунок Б2 - Діалогове вікно «Пошук рішення»

У цьому діалоговому вікні вказується адреса клітинки з виразом цільовій функції. У даному прикладі це адреса Н7. У переліку «Рівної:» відмічається МЛ кнопка «максимальному значенню», оскільки потрібно знайти максимум цільової функції.

У вікно «Змінюючи клітинки» вводяться адреси клітинок з шуканими змінними х1, х2 і х3. У даному випадку це масив адрес Н2, Н3 і Н4. Масив адрес клітинок вводиться через знак «крапка з комою». З метою скорочення, масив адрес клітинок, що йдуть по порядку, вводиться адресами початкової і кінцевої клітинок через знак «двокрапка» Н2:Н4 (рис. Д3).

При введенні даних в діалогові вікна у адрес клітинок автоматично з'являється знак $. Наприклад, на рис. Д3 адреса цільової клітинки виглядатиме як $H$7. Хай цей факт не бентежить користувача, і він продовжує введення вихідних даних.

Введення обмежень здійснюється у вікні «Обмеження» через активування МЛ клавіші «Додати», внаслідок чого розкривається діалогове вікно «Додавання обмеження» (рис. Д4).

Рисунок Б3 - Діалогове вікно «Додавання обмеження»

У вікно «Посилання на клітинку» вводиться адреса клітинки, що містить ліву частину обмеження. У середньому вікні після активування МЛ клавіші «▼» вводиться вид обмеження (<=, >= =). У вікні «Обмеження» вводиться адреса клітинки з правою частиною обмеження. Рис. Д4 ілюструє введення обмеження з енергетичних ресурсів В16<=В6. Після введення чергового обмеження активується МЛ клавіша «Додати» і вводиться наступне обмеження. Після введення всіх обмежень активується МЛ клавіша «ОК», внаслідок чого автоматично здійснюється перехід до діалогового вікна «Пошук рішення» (рис. Б3). У вікні «Обмеження» на рис. Б3 показані всі обмеження вирішуваної задачі.

Граничні умови невід’ємності шуканих змінних враховуються у вигляді обмеження Н2:Н4 >= 0.

Введені обмеження можна змінювати і видаляти. Для цього МЛ виділяється обмеження і за допомогою активування МЛ клавіш «Змінити» або «Видалити» виконується відповідна дія.

3 Введення інформації в діалогове вікно «Параметри пошуку рішення»

Після введення вихідних даних в діалоговому вікні «Пошук рішення» активується МЛ клавіша «Параметри» цього діалогового вікна, внаслідок чого розкривається діалогове вікно «Параметри пошуку рішення» (рис. Б4).

Рисунок Б4 - Діалогове вікно «Параметри пошуку рішення»

У цьому діалоговому вікні встановлюється МЛ галочку «v» у лінійній моделі, що забезпечує рішення задачі методом лінійного програмування (симплекс-методом). Всі останні вікна і команди можна використовувати за замовчуванням, оскільки вони підходять для розв’язку більшості оптимізаційних задач.

Активізується МЛ клавіша «ОК»; на екрані з'являється вже знайоме діалогове вікно «Пошук рішення».

4 Отримання рішення

У діалоговому вікні «Пошук рішення» активується МЛ клавіша «Виконати». Комп'ютер проводить обчислення. На робочому полі з'являються результати обчислень (рис. Д.6):

- значення шуканих змінних х1, х2 і х3 в клітинках Н2, Н3 і Н4;

- максимальне значення цільової функції в клітинці Н7;

- ліві частини обмежень в клітинках В16, В17, В18 і В19.

Рисунок Б5 - Результат розв’язку задачі на робочому полі

Рисунок Б6 - Діалогове вікно «Результати пошуку рішення»

Тут же на робочому полі з'являється діалогове вікно «Результати пошуку рішення». Після активування МЛ клавіші «ОК» цього вікна на екрані залишається робоче поле з результатами рішення.