Методика розв’язання оптимізаційних задач лінійного програмування (у середовищі EXCEL)

 

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

Лінійні оптимізаційні задачі можуть бути реалізовані в середовищі EXCEL.

ПОИСК РЕШЕНИЯ - це надбудова EXCEL, що дає можливість розв'язувати лінійні задачі. Якщо в меню Сервис відсутня команда ПОИСК РЕШЕНИЯ, її потрібно активізувати: Сервис - Надстройки - Поиск решения.

Для реалізації алгоритму задачі необхідно:

• сформувати форму для вводу умов задачі;

• вказати адреси клітин, в які буде надсилатися результат розв'язку задачі (изменяемые ячейки);

• ввести залежність для цільової функції;

• вказати призначення цільової функції (установить целевую ячейку);

• ввести обмеження;

• ввести параметри для розв'язку ЗЛП.

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

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

Позначимо через X₁, Х₂, Х₃, Х₄, Х₅ масу окремих кормів, а через X₆ -загальну поживність раціону.

Економіко-математична модель задачі матиме такий вигляд.

Цільова функція - це математичний вираз мети, тобто того, що в даному випадку необхідно мінімізувати:

F(x) = 0,5 Х₁ + 0,6 Х₂ + 0,25 X₃ + 0,04 Х₄ + 0,08 X₅

Обмеження за умовою задачі:

1,15 X₁ +1,18 Х₂ +0,44 Х₃ + 0,2 Х₄ + 0,2 Х₅ >= 13,4

1,15 X₁ +1,18 Х₂ +0,44 Х₃ + 0,2 Х₄ + 0,2 Х₅ <= 13,8

85 X₁ +189 Х₂ +144 Х₃ + 5 Х₄ +14 Х₅ >= 1340

85 X₁ +189 Х₂ +144 Х₃ + 5Х₄ + 14 X, <= 1380

2Х₁ +2Х₂ +17Х₃ + 2,8Х₄ + 1,4Х₅>=97

3,9 Х₁ +4,3 Х₂ +2,2 Х₃ + 0,8Х₄ + 0,4 Х₅ >= 69

0,3 Х₁ +0,2 Х₂ +49 Х₃ + 4Х₄ + 20Х₅>=610

1,15 X₁ +1,18 Х₂ + 0,44 X₃ + 0,2 Х₄ + 0,2 Х₅ ­- Х₆ = 0

0,44 Х₃ + 0,2Х₄- 0,26 X₆ = 0

1,15 X, +1,18 X₂ - 0,29 X₆>=0

X₅>=15

X₂<=2

Х₁, Х₂, Х₃, Х₄, Х₅ >= 0

1. Для наведеної задачі підготувати форму для вводу умов (рис. 1.1)

2. У нашій задачі оптимальні значення вектора X = (X₁, Х₂, Х₃, Х₄, X ₅) після розв’язку задачі будуть розміщені в клітинках B3:F3, оптимальне значення цільової функції - в клітинці Н5.

3. Введемо дані задачі у підготовлену форму, отримаємо результат, зображений нарис. 1.2.

Рис. 1.1. Форма для вводу даних

 

Рис. 1.2. Дані введено у форму

4. Введемо залежність для цільової функції:

- робимо активною клітину Н5;

- курсор на Мастер функций;

- на екрані з'являється діалогове вікно Мастер функции;

- з вікна Категория курсором вибираємо категорію Математические;

- у вікні Функции обираємо СУММПРОИЗВ;

- у масив 1 вводимо B3:F3;

- у масив 2 вводимо B4:F4;

- установку цільової функції завершено. На екрані Н5 цільова функція введена, як показано на рис. 1.3.

5. Введемо залежності для лівих частин обмежень: або аналогічно по­передньому кроку вводимо функції для лівих частин, або з клітини H5 копіюємо формулу в Н7, Н8,... Н18. На цьому завершено введення залежностей.

Після вибору команд Сервис => Поиск решения з'явиться діалогове вікно Поиск решения.

У діалоговому вікні Поиск решения є три основних параметри:

- Установить целевую функцию.

- Изменяя ячейки.

- Ограничения.

Насамперед необхідно заповнити поле Установить целевую функцию.

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

Другий важливий параметр засобу Поиск решения - Изменяя ячейки.

Изменяемые ячейки - це клітини, значення в яких будуть змінюватися для того щоб, оптимізувати результат у цільовій клітині.

Для розв'язку задачі можна вказати до 200 таких клітин, але до них є дві основні умови: вони мають містити формули і зміна їх значень повинна впливати на зміну значення цільової функції, тому цільова клітина залежна від Изменяемых ячеек.

Третій параметр, що необхідно встановити - Ограничения.

6. Призначення цільової функції:

■ Навести курсор в поле Установить целевую функцию.

■ Ввести адресу клітини Н5.

■ Ввести напрямок цільової функції (максимального значення).

Ввести адреси змінних:

■ Навести курсор в поле Изменяя ячейки.

■ Ввести адреси B3:F3.

7. Вводимо обмеження:

■ Курсор в поле Добавить, з'являється діалогове вікно Добавление ограничений (рис. 1.4.)

Рис. 1.4. Формування обмежень

■ У полі Ссылка на ячейку ввести адресу Н7.

■ Ввести знак обмеження та обсяг обмеження.

■ Добавить. Аналогічно ввести решту обмежень.

■ Після останнього обмеження ввести ОК.

На екрані з'являється діалогове вікно Поиск решения з введеними умовами (рис. 1.5)

Рис. 1.5. Сформовані та введені всі умови для розв’язку задачі

8. Визначення параметрів для розв'язку ЗЛП (рис. 1.6).

§ Відкрити вікно Параметры поиска решения.

§ Відмітити позначку Линейная модель, що забезпечує використання симплекс-методу, та позначити прапорцем Неотрицательные значення.

§ ОК. На екрані з'явиться вікно Поиска решения.

§ Выполнить. На екрані з'явиться діалогове вікно Результаты поиска решения - рис. 1.7.

Отримати оптимальний результат не вдалось у зв'язку з тим, що в раціоні має місце нестача фосфору. За умови введення фосфорної добавки або зниження норми годівлі по фосфору з 69 г до 42 г можна отримати оптимальне рішення (рис. 1.8).

Отриманий оптимальний розв’язок означає, що мінімальна вартість добового раціону 5,5 грн. забезпечить отримання добового надою молока від корови 18 кг. При цьому раціон включатиме 1,44 кг дерті ячмінної, 2 кг дерті горохової, 2,38 кг сіна, 12,71 кг соломи та 31 кг силосу. Високий вміст соломи можна пояснити відсутністю обмеження щодо її введення в раціон. Раціон за поживністю відповідає нормі годівлі тварин (за винятком вмісту фосфору).