Для того, щоб розв’язати задачу ЛП в табличному редакторі Microsoft Excel, необхідно виконати такі дії.

1. Ввести умову задачі:

а) створити екранну форму для введення умови задачі:

– змінних;

– цільової функції (ЦФ);

– обмежень;

– граничних умов;

б) ввести початкові дані в екранну форму:

– коефіцієнти ЦФ;

– коефіцієнти при змінних в обмеженнях;

– праві частини обмежень;

в) ввести залежність з математичної моделі в екранну форму:

– формулу для розрахунку ЦФ;

– формули для розрахунку значень лівих частин обмежень;

г) задати ЦФ (у вікні “Поиск решения”):

– цільова комірка;

– напрям оптимізації ЦФ;

д) ввести обмеження і граничні умови (у вікні “Поиск решения”):

– комірки з значеннями змінних;

– граничні умови для допустимих значень змінних;

– співвідношення між правими і лівими частинами обмежень.

2. Розв’язати задачу:

а) встановити параметри розв’язання задачі (у вікні “Поиск решения”);

б) запустити задачу на розв’язання (у вікні “Поиск решения”);

в) вибрати формат висновку розв’язання (у вікні “Результаты поиска решения”).

1.3 Інструкція до виконання лабораторної роботи за допомогою Microsoft Excel

1.3.1 Одноіндексні задачі ЛП

Розглянемо приклад знаходження розв’язку для такої одноіндексної задачі ЛП:

Введення початкових даних. Створення екранної форми і введення в неї умови задачі.

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

В екранній формі на рис.1.1 кожній змінній і кожному коефіцієнту задачі поставлена відповідно конкретна комірка в Excel. Ім'я комірки складається з букви, що позначає стовпець, і цифри, що позначає рядок, на перетині яких знаходиться об'єкт задачі ЛП. Так, наприклад, змінним задачі (1.1) відповідають комірки B3 ((х₁), C3 ((х₂), D3 ((х₃), E3 ((х₄), коефіцієнтам ЦФ відповідають комірки B6 ((с₁ = 130,5), C6 ((с₁ = 20), D6 ((с₁ = 56), E6 ((с₄ = 87,8), правим частинам обмежень відповідають комірки H10 ((b₁ = 756), H11 ((b₂ = 450), H12 ((b₃ = 89) і т.д.

Рисунок 1.1 – Екранна форма задачі

В комірку F6, в якій буде відображатися значення ЦФ, необхідно ввести формулу, за якою це значення буде розраховано. Згідно з (1.1) значення ЦФ визначається виразом

Використовуючи позначення відповідних комірок в Excel (див. рис.1.1), формулу для розрахунку ЦФ (1.2) можна записати як суму значень кожної з комірок, відведених для значень змінних задачі (B3, C3, D3, E3), на відповідну комірку, відведену для коефіцієнтів ЦФ (B6, C6, D6, E6), тобто

Щоб задати формулу (1.3) необхідно в комірку F6 ввести такий вираз і натискувати клавішу “Enter”

де символ “$” перед номером рядка 3 означає, що при копіюванні цієї формули в інші місця листа Excel номер рядка 3 не зміниться;

символ : означає, що у формулі будуть використані всі комірки, розташовані між комірками, вказаними зліва і справа від двокрапки (наприклад, запис B6:E6 указує на комірки B6, C6, D6 і E6). Після цього в цільовій комірці з'явиться 0 (нульове значення) (рис.1.2).

Рисунок 1.2 – Екранна форма задачі

Рисунок 1.3 – Введення формули для розрахунку ЦФ у вікно “Мастер функций”

Примітка. Існує інший спосіб задання функцій в Excel за допомогою режиму “Вставка функций”, який можна викликати з меню “Вставка” або при натисненні кнопки “ ” на стандартній панелі інструментів. Так, наприклад, формулу (1.4) можна задати таким чином.

1. Курсор в полі F6.

2. Натисніть кнопку “ ”, викличте вікно “Мастер функций – шаг 1 с 2”.

3. Виберіть у вікні “Категория” категорію “Математические”.

4. У вікні “Функция” виберіть функцію СУММПРОИЗВ.

5. У вікні “СУММПРОИЗВ”, що з'явилося, в рядок “Массив 1” введіть вираз B$3:E$3, а в рядок “Массив 2” – вираз B6:E6 (рис.1.3).

6. Після введення комірок в рядки “Массив 1” і “Массив 2” у вікні “СУММПРОИЗВ” з'являться числові значення введених масивів (см.  рис.1.3), а в екранній формі в комірці F6 з'явиться поточне значення, обчислене за введеною формулою, тобто 0 (оскільки у момент введення формули значення змінних задачі нульові).

Залежність для лівих частин обмежень. Ліві частини обмежень задачі (1.1) є сумою кожної з комірок, відведених для значень змінних задачі (B3, C3, D3, E3), на відповідну комірку, відведену для коефіцієнтів конкретного обмеження (B10, C10, D10, E10 – 1-е обмеження; B11, C11, D11, E11 – 2-е обмеження і B12, C12, D12, E12 – 3-е обмеження). Формули, відповідні лівим частинам обмежень, показані в табл.1.1.

Таблиця 1.1 – Формули, що описують обмеження моделі (1.1)

 або

 або

 або

Як видно з табл.1.1, формули, задаючи ліві частини обмежень задачі (1.1), відрізняються одна від одної і від формули (1.4) в цільовій комірці F6 тільки номером рядка в другому масиві. Цей номер визначається тим рядком, в якому обмеження записано в екранній формі. Тому для задання залежності для лівих частин обмежень достатньо скопіювати формулу з цільової комірки в комірки лівих частин обмежень. Для цього необхідно.

1. Помістити курсор в полі цільової комірки F6 і скопіювати в буфер вміст комірки F6 (клавішами “Ctrl-С”).

2. Поміщати курсор по черзі в поля лівої частини кожного з обмежень, тобто в F10, F11 і F12, і вставляти в ці поля вміст буфера (клавішами “Shift-Іnsert”) (при цьому номер комірок в другому масиві формули буде змінюватись на номер того рядка, в який була вироблена вставка з буфера).

3. На екрані в полях F10, F11 і F12 з'явиться 0 (нульове значення) (див. рис.1.2).

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

Рисунок 1.4 – Перевірка правильності введення формули в цільову комірку

Задання ЦФ. Подальші дії виконуються у вікні “Поиск решения”, яке викликається з меню “Сервис” (рис.1.6).

1. Поставте курсор в полі “Установить целевую ячейку”.

2. Введіть адресу цільової комірки $F$6 або зробіть одне натиснення лівої клавіші миші на цільову комірку в екранній формі – це буде рівносильно введенню адреси з клавіатури.

3. Введіть напрям оптимізації ЦФ, клацнувши один раз лівою клавішею миші по селекторній кнопці “максимальное значение”.

Рисунок 1.5 – Перевірка правильності введення формули в комірку F12

Рисунок 1.6. – Вікно “Поиск решения”

Введення обмежень, граничних умов та задання комірок змінних. У вікно “Поиск решения” в полі “Изменяя ячейки” впишіть адреси $B$3:$E$3. Необхідні адреси можна вносити в полі “Изменяя ячейки” і автоматично шляхом виділення мишею відповідних комірок змінних безпосередньо в екранній формі.

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

1. Натискуйте кнопку “Добавить”, після чого з'явиться вікно “Добавление ограничения” (рис.1.7).

2. В полі “Ссылка на ячейку” введіть адреси комірок змінних $B$3:$E$3. Це можна зробити як з клавіатури, так і шляхом виділення мишею всіх комірок змінних безпосередньо в екранній формі.

3. В полі знака відкрийте список пропонованих знаків і виберіть .

4. В полі “Ограничения” введіть адреси комірок нижньої межі значень змінних, тобто $B$4:$E$4. Їх також можна ввести шляхом виділення мишею безпосередньо в екранній формі.

Рисунок 1.7 – Додавання умови позитивності змінних

Задання знаків обмежень   ,   , =.

5. Натисніть кнопку “Добавить” у вікні “Добавление ограничения”.

6. В полі “Ссылка на ячейку” введіть адресу комірки лівої частини конкретного обмеження, наприклад $F$10. Це можна зробити як з клавіатури, так і шляхом виділення мишею потрібної комірки безпосередньо в екранній формі.

7. Відповідно до умови задачі (1.1) вибрати в полі знака необхідний знак, наприклад =.

8. В полі “Ограничения” введіть адреси комірки правої частини даного обмеження, наприклад $H$10.

9. Аналогічно введіть обмеження: $F$11>=$H$11 $F$12<=$H$12.

10. Підтвердіть введення всіх перерахованих вище умов натисненням кнопки “OK”.

Вікно “Поиск решения” після введення всіх необхідних даних задачі (1.1) подано на рис.1.6.

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

Розв’язування задачі. Встановлення параметрів розв’язування задачі.

Задача запускається на розв’язування у вікні “Поиск решения”. Але заздалегідь для встановлення конкретних параметрів розв’язування задач оптимізації певного класу необхідно натискувати кнопку “Параметры” і заповнити деякі поля вікна “Параметры поиска решения” (рис.1.8).

Рисунок 1.8 – Параметри пошуку розв’язування, відповідні для більшості задач ЛП

Параметр “Максимальное время” служить для призначення часу (в секундах), що виділяється на розв’язування задачі. В полі можна ввести час, що не перевищує 32 767 секунд (більше 9 годин).

Параметр “Предельное число итераций” служить для управління часом розв’язування задачі шляхом обмеження числа проміжних обчислень. В полі можна ввести кількість ітерацій, що не перевищує        32 767.

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

Параметр “Допустимое отклонение” служить для задання допуску на відхилення від оптимального розв’язування в цілочислових задачах. При вказанні більшого допуску “Поиск решения” закінчується швидше.

Параметр “Сходимость” застосовується тільки при розв’язуванні нелінійних задач.

Встановлення прапорця “Линейная модель” забезпечує прискорення пошуку розв’язування лінійної задачі за рахунок застосування симплекс-методу.

Підтвердіть встановлені параметри натисненням кнопки “OK”.

Запуск задачі на розв’язування робиться з вікна “Поиск решения” шляхом натиснення кнопки “Выполнить”.

Після запуску на розв’язування задачі ЛП на екрані з'являється вікно

“Результаты поиска решення” з одним з повідомлень, поданих на рис.1.9, 1.10 і 1.11.

Рисунок 1.9 – Повідомлення про успішне розв’язування задачі

Рисунок 1.10 – Повідомлення при несумісній системі обмежень задачі

Рисунок 1.11 – Повідомлення при необмеженості ЦФ в необхідному напрямі

Іноді повідомлення, показані на рис.1.10 і 1.11, свідчать не про характер оптимального розв’язування задачі, а про те, що при введенні умов задачі в Excel були допущені помилки, що не дозволяють Excel знайти оптимальний розв’язок, який насправді існує.

Якщо при заповненні полів вікна “Поиск решения” були допущені помилки, що не дозволяють Excel застосувати симплекс-метод для розв’язування задачі або довести її розв’язування до кінця, то після запуску задачі на розв’язування на екран буде видано відповідне повідомлення з вказанням причини, за якою розв’язування не знайдено.

Іноді дуже мале значення параметра “Относительная погрешность” не дозволяє знайти оптимальний розв’язок. Для виправлення цієї ситуації збільшуйте похибку порозрядно, наприклад, від 0,000001 до 0,00001 і т.д.

У вікні “Результаты поиска решения” подані назви трьох типів звітів: “Результаты”, “Устойчивость”, “Пределы”. Вони необхідні при аналізі отриманого розв’язку на чутливість (див. нижче підрозділ 3.3). Для отримання ж відповіді (значень змінних, ЦФ і лівих частин обмежень) прямо в екранній формі просто натискуйте кнопку “OK”. Після цього в екранній формі з'являється оптимальний розв’язок задачі (рис.1.12).

Рисунок 1.12 – Екранна форма задачі після отримання розв’язку

1.3.2 Цілочислове програмування

Припустимо, що до умови задачі (1.1) додалася вимога цілочислових значень всіх змінних. В цьому випадку описаний вище процес введення умови задачі необхідно доповнити такими кроками.

1. В екранній формі вкажіть, на які змінні накладається вимога цілочислової (цей крок робиться для наочності сприйняття умови задачі) (рис.1.13).

2. У вікні “Поиск решения” (меню “Сервис”®“Поиск решения”), натискуйте кнопку “Добавить” і у вікні “Добавление ограничения”, що з'явилося, введіть обмеження таким чином (рис.1.14):

3. В полі “Ссылка на ячейку” введіть адреси комірок змінних задачі, тобто $B$3:$E$3;

4. В полі введення знака обмеження встановіть “Целое”;

5. Підтвердіть введення обмеження натисненням кнопки “OK”.

Рисунок 1.13 – Розв’язування задачі за умови цілочислових змінних

Рисунок 1.14 – Введення умови цілочислових змінних задачі

На рис.1.13 подано розв’язування задачі (1.1), до обмежень якої додано умову цілочислових значень її змінних.

1.3.3 Двохіндексні задачі ЛП

Двохіндексні задачі ЛП вводяться і розв'язуються в Excel аналогічно одноіндексним задачам. Специфіка введення умови двохіндексної задачі ЛП полягає лише в зручності матричного задання змінних задачі і коефіцієнтів ЦФ.

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

Таблиця 1.2 – Початкові дані транспортної задачі

Цільова функція і обмеження даної задачі мають вигляд

Екранні форми, задання змінних, цільової функції, обмежень і граничних умов двохіндексної задачі (1.5) і її розв’язування подані на рис.1.15, 1.16, 1.17 і в табл.1.3.

Таблиця 1.3 – Формули екранної форми задачі

Продовження таблиці 1.3

Рисунок 1.15 – Екранна форма двохіндексної задачі

Рисунок 1.16 – Обмеження і граничні умови задачі

Рисунок 1.17 – Екранна форма після отримання розв’язку задачі

1.3.4 Задачі з булевими змінними

Окремим випадком задач з цілочисловими змінними є задачі, в результаті розв’язування яких шукані змінні  можуть приймати тільки одне з двох значень: 0 або 1. Такі змінні названі на честь англійського математика Джорджа Буля, що запропонував їх називати булевими. На рис.1.18 подана екранна форма з розв’язуванням деякої двохіндексної задачі з булевими змінними.

Рисунок 1.18 – Розв’язування двохіндексної задачі з булевими змінними

Крім задання вимоги цілочислової при введенні умови задач з булевими змінними необхідно.

1. Для наочності сприйняття ввести в екранну форму слово “булевые” як характеристики змінних (див. рис.1.18).

2. У вікні “Поиск решения” додати граничні умови, що мають обмеження значень змінних за їх одиничною верхньою межею (рис.1.19).

Рисунок 1.19 – Додання умови одиничної верхньої межі значень змінних двохіндексної задачі з булевими змінними

Вигляд вікна “Поиск решения” для задачі з булевими змінними, поданої на рис.1.18, наведений на рис.1.20.

Рисунок 1.20 – Вікно “Поиск решения” для задачі з булевими змінними

1.4 Варіанти

Використовуючи MS Excel, знайти розв’язок для моделі ЛП, відповідної заданому варіанту (табл.1.4).

Таблиця 1.4 – Варіанти задач до лабораторної роботи №1

Продовження таблиці 1.4

Продовження таблиці 1.4

1.5 Запитання на захисті роботи

1.     Які основні етапи розв’язування задач лінійного програмування в MS Excel?

2.     В чому сенс використовування символу $ у формулах MS Excel?

3.     Чому при введенні формул в комірки ЦФ і лівих частин обмежень в них відображаються нульові значення?

4.     Яким чином в MS Excel задається напрям оптимізації ЦФ?

5.     Які комірки екранної форми виконують ілюстративну функцію, а які необхідні для розв’язування задачі?

6.     Поясніть загальний порядок роботи з вікном “Поиск решения”.

7.     Яким чином можна змінювати, додавати, видаляти обмеження у вікні “Поиск решения”?

8.     Які повідомлення видаються в MS Excel у випадках: успішного розв’язування задачі ЛП; неспільності системи обмежень задачі; необмеженості ЦФ?

9.     Поясніть сенс параметрів, що задаються у вікні “Параметри поиска решения”.

10.            Які особливості розв’язування в MS Excel цілочислових задач лінійного програмування?

11.            Які особливості розв’язування в MS Excel двохіндексних задач лінійного програмування?

12.            Які особливості розв’язування в MS Excel задач лінійного програмування з булевими змінними?

13.            Яке практичне значення задач лінійного програмування?

14.            Запишіть формулу ЦФ.

15.            Яким чином задається ЦФ?

16.            В чому суть симплекс-методу для розв’язування задач лінійного програмування?

17.            Яке практичне значення двохіндексних задач лінійного програмування?

18.            Що таке булеві змінні?

19.            Навіщо додавати обмеження при розв’язанні задач лінійного програмування?

20.            Що таке відносна та абсолютна похибки?

21.            Навіщо треба ставити параметр “Допустимое отклонение”?

22.            Що таке граничні умови задачі?

23.            Розв’язки яких задач можуть приймати тільки одне з двох значень: 0 або 1?

24.            В чому полягає специфіка розв’язку двохіндексної задачі лінійного програмування?