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

МЕТА РОБОТИ

Придбання навичок рішення завдань лінійного програмування (ЛП) у табличному редакторі Microsoft Excel.

ПОРЯДОК ВИКОНАННЯ РОБОТИ

Для моделі ЛП, що відповідає номеру Вашого варіанта, знайдіть оптимальне рішення в табличному редакторі Microsoft Excel і продемонструйте його викладачеві.

1.3. ІНСТРУКЦІЯ З ВИКОРИСТАННЯ Microsoft Excel ДЛЯ РІШЕННЯ ЗАВДАНЬ ЛП [5]

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

1. Увести умову завдання:

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

· змінних,

· цільової функції (ЦФ),

· обмежень,

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

b) увести вихідні дані в екранну форму:

· коефіцієнти ЦФ,

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

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

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

· формулу для розрахунку ЦФ,

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

d) задати ЦФ (у вікні "Пошук рішення"):

· цільовий осередок,

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

e) увести обмеження й граничні умови (у вікні "Пошук рішення"):

· осередку зі значеннями змінних,

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

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

2. Вирішити завдання:

a) установити параметри рішення завдання (у вікні "Пошук рішення" );

b) запустити завдання на рішення (у вікні "Пошук рішення" );

c) вибрати формат виводу рішення (у вікні "Результати пошуку рішення").

1.3.1. Одноіндексні завдання ЛП

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

(1.1)

1.3.1.1. Уведення вихідних даних

Створення екранної форми й уведення в неї умови завдання

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

Рис.1.1. Екранна форма завдання (1.1) (курсор в осередку F6)

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

Уведення залежностей з математичної моделі в екранну форму

Залежність для ЦФ

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

(1.2)

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

(1.3)

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

=СУММПРОИЗВ(B$3:E$3;B6:E6),

(1.4)

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

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

Рис.1.2. Екранна форма завдання (1.1) після уведення всіх необхідних формул

(курсор в осередку F6)

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

· курсор у поле F6;

· нажавши кнопку " ", викличте вікно "Майстер функцій – крок 1 з 2";

· виберіть у вікні "Категорія" категорію "Математичні";

· у вікні "Функція" виберітьфункцію СУММПРОИЗВ;

· у вікні, що з'явилося, "СУММПРОИЗВ " у рядок "Масив 1 " уведіть вираження B$3:E$ 3, а в рядок "Масив 2 " - вираження B6:E 6 (мал.1.3);

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

Рис.1.3. Уведення формули для розрахунку ЦФ у вікно "Майстер функцій"

Залежності для лівих частин обмежень

Ліві частини обмежень завдання (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)

Ліва частина обмеження	Формула Excel
або	=СУММПРОИЗВ(B$3:E$3;B10:E10)
або	=СУММПРОИЗВ(B$3:E$3;B11:E11)
або	=СУММПРОИЗВ(B$3:E$3;B12:E12)

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

· помістити курсор у поле цільового осередку F6 і скопіювати в буфер уміст осередку F6 (клавішами "Ctrl-Insert");

· поміщати курсор по черзі в поля лівої частини кожного з обмежень, тобто в F10, F11 й F12, і вставляти в ці поля вміст буфера (клавішами "Shift-Insert") (при цьому номер осередків у другому масиві формули буде мінятися на номер того рядка, у яку була зроблена вставка з буфера);

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

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

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

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

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

для лівої частини обмеження 3

Завдання ЦФ

Подальші дії виробляються у вікні "Пошук рішення", що викликається з меню "Сервіс" (мал. 1.6):

· поставте курсор у поле "Установити цільовий осередок";

· уведіть адресу цільового осередку $F$6 або зробіть одне натискання лівої клавіші миші на цільовий осередок в екранній формі ¾ це буде рівносильно уведенню адреси із клавіатури;

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

Рис.1.6. Вікно "Пошук рішення" завдання (1.1)

Уведення обмежень і граничних умов

Завдання осередків змінних

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

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

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

· Натисніть кнопку "Додати", після чого з'явиться вікно "Додавання обмеження" (мал. 1.7).

· У поле "Посилання на осередок" уведіть адреси осередків змінних $B$3:$E$3. Це можна зробити як із клавіатури, так і шляхом виділення мишею всіх осередків змінних безпосередньо в екранній формі.

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

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

Рис.1.7. Додавання умови незаперечності змінні завдання (1.1)

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

· Натисніть кнопку "Додати" у вікні "Додавання обмеження".

· У поле "Посилання на осередок" уведіть адресу осередку лівої частини конкретного обмеження, наприклад $F$10. Це можна зробити як із клавіатури, так і шляхом виділення мишею потрібного осередку безпосередньо в екранній формі.

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

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

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

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

Вікно "Пошук рішення" після уведення всіх необхідних дані завдання (1.1) представлене на мал. 1.6.

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

1.3.1.2. Рішення завдання

Установка параметрів рішення завдання

Завдання запускається на рішення у вікні "Пошук рішення". Але попередньо для встановлення конкретних параметрів рішення завдань оптимізації певного класу необхідно нажати кнопку "Параметри" і заповнити деякі поля вікна "Параметри пошуку рішення" (мал. 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 знайти оптимальне рішення, що у дійсності існує (див. нижче подразд.1.3.5).

Якщо при заповненні полів вікна "Пошук рішення" були допущені помилки, що не дозволяють Excel застосувати симплекс-метод для рішення завдання або довести її рішення до кінця, то після запуску завдання на рішення на екран буде видане відповідне повідомлення із вказівкою причини, по якій рішення не знайдене. Іноді занадто мале значення параметра "Відносна погрішність" не дозволяє знайти оптимальне рішення. Для виправлення цієї ситуації збільшуйте погрішність поразрядно, наприклад від 0,000001 до 0,00001 і т.д.

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

Рис.1.12. Екранна форма завдання (1.1) після одержання рішення

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

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

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

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

- в поле "Посилання на осередок" уведіть адреси осередків змінні завдання, тобто $B$3:$E$3;

- у поле уведення знака обмеження встановите "ціле" ;

- підтвердите уведення обмеження натисканням кнопки " OK" .

Рис.1.13. Рішення завдання (1.1) за умови целочисленности її змінних

Рис.1.14. Уведення умови целочисленности змінні завдання (1.1)

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

Двухиндексные завдання ЛП

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

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

Таблиця 1.2

Вихідні дані транспортного завдання

Тарифи, руб. /шт.	1-й магазин	2-й магазин	3-й магазин	Запаси, шт.
1-й склад
2-й склад
3-й склад
4-й склад
Потреби, шт.

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

(1.5)

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

Рис.1.15. Екранна форма двухиндексной завдання (1.5)

(курсор у цільовому осередку F15)

Таблиця 1.3

Формули екранної форми завдання (1.5)

Об'єкт математичної моделі	Вираження в Excel
Змінні завдання	C3:E6
Формула в цільовому осередку F15	=СУММПРОИЗВ(C3:E6;C12:E15)
Обмеження по рядках в осередках F3, F4, F5, F6	=СУМ(C3:E3) =СУМ(C4:E4) =СУМ(C5:E5) =СУМ(C6:E6)
Обмеження по стовпцях в осередках З7, D7, E7	=СУМ(C3:C6) =СУМ(D3:D6) =СУМ(E3:E6)
Сумарні запаси й потреби в осередках H8, G9	=СУМ(H3:H6) =СУМ(C9:E9)

Рис.1.16. Обмеження й граничні умови завдання (1.5)

Рис.1.17. Екранна форма після одержання рішення завдання (1.5)

(курсор у цільовому осередку F15)

1.3.4. Завдання з булевыми змінними

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

Рис.1.18. Рішення двухиндексной завдання з булевыми змінними

Крім завдання вимоги целочисленности (див. подразд.1.3.2) при уведенні умови завдань із булевыми змінними необхідно:

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

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

Рис.1.19. Додавання умови одиничної верхньої границі значень змінних двухиндексной завдання з булевыми змінними

Вид вікна "Пошук рішення" для завдання з булевыми змінними, представленої на мал. 1.18, наведений на мал. 1.20.

Рис.1.20. Вікно "Пошук рішення" для завдання з булевыми змінними, представленої на мал. 1.18

1.3.5. Можливі помилки при уведенні умов завдань ЛП

Якщо при рішенні завдання ЛП видається повідомлення про неможливість знаходження рішення, то можливо, що причина полягає в помилках уведення умови завдання в Excel. Тому, перш ніж робити вивід про принципову неможливість знаходження оптимального рішення завдання, відповідайте на питання з табл.1.4.

Таблиця 1.4 Список питань, що дозволяють виявити помилки уведення умови завдання в Excel

Місце розташування в Excel

Екранна форма

Вікно "Пошук рішення"

Вікно "Пошук рішення" Поле "Змінюючи осередку"

Екранна форма, Вікно "Пошук рішення" Поле "Обмеження"

Вікно "Пошук рішення" Поле "Обмеження"

Вікно "Параметри пошуку рішення"

Питання

Чи правильно Ви ввели чисельні значення й знаки (+, —) коефіцієнтів цільової функції й обмежень, правих частин обмежень?

Счи балансована двухиндексная завдання?

Чи правильні формули в цільовому осередку й в осередках лівих частин обмежень? Для наочності перевірки поставте курсор на осередок з формулою й зробіть подвійного щиглика лівою клавішею миші. Рамкою в екранній формі будуть виділені осередки, що беруть участь у даній формулі (див. мал. 1.4, 1.5).

Чи правильно зазначена адреса цільового осередку?

Правильно чи зазначений напрямок оптимізації ЦФ?

Чи правильно зазначені адреси осередків змінних?

Правильно чи уведені знаки обмежень (<=, >=, =)?

Чи правильно зазначені адреси осередків лівих і правих частин обмежень?

Не чи забули Ви задати вимогу незаперечності змінних?

Чи не забули Ви задати вимоги за одиничним значенням верхньої границі змінних (для завдань із булевыми змінними)

Не чи забули Ви задати умову целочисленности змінних (відповідно до умови завдання)?

Перевірте правильність установки параметрів (див. подразд.1.3. 1.2)

№

1.4. ЗРАЗКОВІ ПИТАННЯ НА ЗАХИСТІ РОБОТИ

1. Які основні етапи рішення завдань ЛП в MS Excel?

2. Який вид і способи завдання формул для цільового осередку й осередків лівих частин обмежень?

3. У чому зміст використання символу $ у формулах MS Excel?

4. У чому розходження використання у формулах MS Excel символів; і:?

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

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

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

8. Як наочно відобразити в екранній формі осередку, використовувані в конкретній формулі, з метою перевірки її правильності?

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

10. Яким образом можна змінювати, додавати, видаляти обмеження у вікні "Пошук рішення"?

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

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

13. Які особливості рішення в MS Excel целочисленных завдань ЛП?

14. Які особливості рішення в MS Excel двухиндексных завдань ЛП?

15. Які особливості рішення в MS Excel завдань ЛП із булевыми змінними?

1.5. ВАРІАНТИ

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

Таблиця 1.5

Варіанти завдань до лабораторної роботи №1

№ варіанта	Математична модель

№ варіанта	Математична модель

№ варіанта	Математична модель