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

Для розв’язаннязадач лінійного програмування в Excel є спеціальна процедура, яка запускається командою "Поиск решения...". з меню "Сервіс".

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

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

Вид діалогового вікна "Добавление ограничения" показаний на рис. 22.

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

Поле "Ограничение" служить для завдання умови, яке накладається на значення комірки або діапазону, вказаного в полі "Ссылка на ячейку". Для завдання умови необхідно вибрати умовний оператор (<=або "цілий") і ввести обмеження: число, формулу, посилання на комірку або діапазон комірок в полі праворуч від списку умовних операторів, що розкривається.

Кнопка "Добавить" дозволяє накласти нове обмеження на пошук розв’язку, не повертаючись у вікно діалогу "Поиск решения…".

Робота у вікні діалогу "Изменить ограничение" аналогічна роботі у вікні "Добавление ограничения".

 

Задача №2. Виробнича фірма випускає три види виробів (А, В, С). Для випуску кожного з них вимагається певний час обробки на чотирьох верстатах I, II, III, IV (табл. 5.1).

 

 

Таблиця 5.1

Вид виробу	Час обробки, год.	Прибуток, грош. од.
І	ІІ	ІІІ	ІV
А
В
С

 

Час роботи на верстатах складає 84, 42, 21 і 42 години відповідно.

Визначити, які вироби і в яких кількостях варто робити для максимізації прибутки, якщо на вироби виду В є попередня домовленість у кількості 2 од.

Розв’язання. Нехай х₁ – кількість виробів виду, що випускаються А, х₂ – кількість виробів виду В, х₃ – кількість виробів виду С. Тоді математична модель цього завдання виглядатиме так:

максимізувати отримуваний прибуток

при виконанні обмежень машинного часу роботи верстатів

При цьому: х ₂ ³ 2.

 

I. Введення умов задачі складається з таких основних кроків:

 

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

Рис. 1.1 Форма для введення умов задачі

 

2. Введення вихідних даних (рис. 1.2).

Рис. 1.2 Вихідні дані.

 

3. Введення залежностей з математичної моделі.

Ввести вихідні дані у форму: розрахунок цільової функції і лівих частин обмежень (комірки D6, D10, D11, D12).

Викликати Майстра функцій. В полі Категорія вибрати Математичні та із списку функцій вибрати СУММПРОИЗВ. Як аргументи використовуються комірки значень змінних (В3, С3, D3 – Массив1) і коефіцієнти або цільової функції, або обмежень (Массив2). Після цього форма набуде вигляду (рис. 1.3).

Рис. 1.3 Введення формул за допомогою майстра функцій

 

II. Робота в діалоговому вікні Поиск решения.

 

Вибрати в меню С е рвіс команду Поиск решения.

Призначити цільову функцію (рис. 1.4):

в полі Установить целевую ячейку – ввести адресу: D6.

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

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

в полі Изменяя ячейки – ввести адреси: В3:D3.

Рис. 1.4 Діалогове вікно Поиск решения

 

Обмеження вводяться після натиснення кнопки Добавить. Після цього на екрані з'являється нове вікно Добавление ограничения (рис. 1.5).

 

Рис. 1.5 Введення обмежень.

 

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

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

Перед одержанням розв’язку задачі бажано виставити параметри (рис. 1.6).

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

Максимальное время

Служить для призначення часу в секундах, що виділяється на пошук розв’язання задачі. В полі можна ввести час, що не перевищує 32767 з (більше 9 годин!). Значення 100, що використовується за умовчанням, підходить для розв’язання більшості задач.

Предельное число итераций

Служить для призначення числа ітерацій. Значення 100, що використовується за умовчанням, підходить для розв’язання більшості задач.

Рис. 1.6 Діалогове вікно «Параметры поиска решения»

Після цих пояснень продовжимо розв’язання задачі.

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

На екрані з’явиться нове діалогове вікно Результаты поиска решения (рис. 1.7).

Зауваження. У випадку, якщо все було правильно зроблене без помилок та умови задачі були сумісні, то у вікні буде написано: Решение найдено. Все ограничения условия оптимальности выполнены. У всіх інших випадках на екрані з’явиться: Поиск не может найти подходящего решения. Якщо цільова функція не обмежена, то на екрані з'явиться Значения целевой ячейки не сходятся.

 

Рис. 1.7 Діалогове вікно «Результаты поиска решения»