Табличний процесор Excel — рішення пошукових завдань лінійного програмування

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

Всі завдання цього типу вирішуються за допомогою інструмента Excel Пошук рішення. Цей режим викликається за допомогою пунктів меню СервисПоиск решения, при цьому на екрані виникає вікно наступного виду:

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

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

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

Команда Выполнить служить для запуску пошуку рішення поставленого завдання. Команда Закрыть служить для виходу з вікна діалогу без запуску пошуку рішення поставленого завдання. При цьому зберігаються установи, зроблені у вікнах діалогу, що з’являлися після натискань на кнопки Параметры, Добавить, Заменить або Удалить.

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

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

Рис. 1.6- Вид вікна в режимі Поиск решения.

Рис. 1.7— Діалогове вікно Добавление ограничений.

Настроювання параметрів алгоритму й програми проводиться в діалоговому вікні Параметры поиска решения (рис. 1.8). У вікні установлюються обмеження на час рішення завдань, вибираються алгоритми, задається точність рішення, надається можливість для збереження варіантів моделі і їхнього наступного завантаження. Значення й стани елементів управління, використовувані за замовчуванням, підходять для рішення більшості завдань.

Поле Максимальное время служить для обмеження часу, що відпускається на пошук рішення завдання. У поле можна ввести час (у секундах) не перевищуючий 32 767; значення 100, використовуване за замовчуванням, підходить для рішення більшості лабораторних робіт.

Поле Предельное число итераций служить для управління часом рішення завдання, шляхом обмеження числа проміжних обчислень. У поле можна ввести час (у секундах) не перевищуючий 32 767. При досягненні відведеного тимчасового інтервалу або при виконанні відведеного числа ітерацій на екрані з’являється діалогове вікно Текущее состояние поиска решения.

Поле Относительная погрешность служить для завдання точності (припустимої погрішності), з якої визначається відповідність комірки цільовому значенню або наближення до зазначених границь. Поле повинно містити число з інтервалу від 0 (нуля) до 1, наприклад, 0,0001. Висока точність збільшить час, потрібний для того, щоб зійшовся процес оптимізації. Чим менше введене число, тим вища точність результатів Поле Допустимое отклонение служить для завдання допуску на відхилення від оптимального рішення. При вказівці більшого допуску пошук рішення закінчується швидше.

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

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

Прапорець Линейная модель служить для прискорення пошуку рішення лінійного завдання оптимізації або лінійної апроксимації нелінійного завдання.

Прапорець Неотрицательные значения дозволяє установити нульову нижню межу для тих комырок, для яких вона не була зазначена в поле Оганичения діалогового вікна Добавление ограничения.

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

Прапорець Показывать результаты итераций служить для припинення пошуку рішення для перегляду результатів окремих ітерацій.

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

Кнопки Разности (похідні) служать для вказівки методу чисельного диференціювання (прямі або центральні похідні), що використовується для обчислення часток похідних цільових і обмежуючих функцій. Прямые використовується для гладких безперервних функцій. Центральные використовується для функцій, що мають розривну похідну. Незважаючи на те, що даний спосіб вимагає більше обчислень, він може допомогти при одержанні підсумкового повідомлення про те, що процедура пошуку рішення не може поліпшити поточний набір вживаючих осередків.

Кнопки Метод поиска служать для вибору алгоритму оптимізації (метод Ньютона або сполучених градієнтів) — при необхідності. Кнопка Ньютона служить для реалізації квазіньютонівского методу, у якому запитується більше пам’яті, але виконується менше ітерацій, чим у методі сполучених градієнтів. Тут обчислюються частки похідні другого порядку. Кнопка Сопряженных градиентов служить для реалізації методу сполучених градієнтів, у якому запитується менше пам’яті, але виконується більше ітерацій, чим у методі Ньютона. Даний метод варто використовувати, якщо завдання досить велике й необхідно заощаджувати пам’ять, а також якщо ітерації дають занадто малу відмінність у послідовних наближеннях. Для рішення лінійних завдань використовуються алгоритми симплексного методу.

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

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

Побудуємо математичну модель завдання знаходження оптимального плану. Позначимо x_i, i=1,2,3, відповідно обсяги випуску столів, стільців і диванів. Тоді завдання максимізації прибутку буде виглядати в такий спосіб: знайти.

20x₁+18x₂+22x₃ max.

за умови дотримання наступних обмежень:

• 9x₁+5x₂+6x₃ 600
• 4x₁+5x₂+6x₃ 400
• 3x₁+4x₂+5x₃ 800

x₁0, x₂0, x₃0.

Рішення поставленого завдання проведемо в табличному процесорі Excel за допомогою режиму «Поиск решения». Вихідні дані завдання оптимізації прибутку:

Рис. 1.9 — Результат пошуку оптимального рішення.

Рис. 1.10 — Формули, які введені для пошуку рішення.