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

1-30. Знайти цілочисельне рішення задач. Дати геометричну інтерпретацію.

 

1.		2.
3.		4.
5.		6.
7.		8.
9.		10.
11.		12.
13.		14.
15.		16.
17.		18.
19.		20.
21.		22.
23.		24.
25.		26.
27.		28.
29.		30.

 

 

ВИКОРИСТАННЯ КОМП'ЮТЕРНИХ ТЕХНОЛОГІЙ ДЛЯ РІШЕННЯ ЗАДАЧ МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ

4.1 Пакет "The management scientist"

 

Пакет прикладних програм призначений для рішення задач з використанням методів математичного програмування і деяких задач, що містять статистичні залежності. Для початку роботи в пакеті потрібно запустити на виконання файл ms.exe. У діалоговому вікні, що з'явилося, пропонується вибрати диск, на якому буде відбуватися робота, на нього будуть записуватися збережені задачі і результати рішень. Припустимо, нами обраний диск С:, тоді як місце роботи вказують: С:.

Головне меню програми має вигляд, представлений на мал. 1.

1. Лінійне програмування 2. Транспортна задача 3. Призначення 4. Цілочислельне лінійне програмування 5. Найкоротший маршрут 6. Мінімальна мережа	7. PERT/CPM 8. Інвентар 9. Черги 10. Аналіз рішень 11. Прогноз 12. Марковські процеси
13. Вихід у doc

Малюнок 1 – Головне меню пакета

 

Вибравши необхідний пункт, вводять його номер, наприклад, 2 (це дозволить перейти до рішення транспортної задачі) і натискають клавішу ENTER. Для припинення роботи з пакетом треба ввести число 13 або натиснути разом клавіші CTRL і BREAK. Незалежно від обраного пункту з'являється стандартне “Меню вибору проблеми” (див. малюнок 2).

1. Створити нову проблему 2. Викликати збережену раніше проблему 3. Продовжити роботу з поточною проблемою 4. Вилучити раніше збережену проблему 5. Повернення в меню верхнього рівня

Малюнок 2 – Меню вибору проблеми

 

 

При записі математичної моделі діють наступні правила:

§ імена змінних повинні складатися не більш, ніж з 14 символів, індекси не використовуються, наприклад, XI, АВ12, З33;

§ дійсні числа вводяться з використанням точки, що відокремлює дробову і цілу частини 0.7; 3.61;

§ при програмуванні цільової функції першим указується її тип, а потім вводяться коефіцієнти при невідомих:

max 10Х1+3Х2

чи min 7.4 XI + 6.8 X2;

§ запис виду.53 рівносильна 0.53.

Якщо вводиться математична модель нової задачі чи викликається раніше створена, то наступний крок – це робота в меню, представленому на малюнку 3.

 

Меню роботи з проблемою 1. Вирішити проблему 2. Зберегти проблему 3. Перегляд / Редагування 4. Повернутися в меню вибору проблеми

 

Малюнок 3 – Меню рішення задачі

Для одержання рішення задачі вибирають опцію 1 (мал. 3), для збереження – 2. При збереженні модуля варто дотримуватись наступних правил: ім’я файлу не повинне перевищувати вісьмох знаків, причому забороняється використовувати пробіл, кому, “, /, [, ],:, <, >, +, =,;. Після того, як задача буде вирішена, з'являється меню, представлене на малюнку 4.

Меню рішення проблеми 1. Вивести ще раз 2. Вивести рішення на принтер 3. Продовжити поточну проблему 4. Повернутися в попереднє меню

Малюнок 4 – Меню рішення проблеми

Якщо необхідно скорегувати модель, у “Меню рішення задачі” (мал. 3) вибирається відповідний пункт, що передає управління “Меню редагування” (мал. 5).

 

Меню редагування 1. Переглянути проблему 2. Перегляд і редагування цільової функції 3. Перегляд / Редагування обмежень 4. Додання обмежень 5. Вилучення обмеження 6. Повернення в меню роботи з проблемою

Малюнок 5 – Меню редагування задачі

Розглянемо приклад: Знайти максимум функції при обмеженнях:

У головному меню (мал. 1) виберемо опцію “Лінійне програмування”, потім, після переходу в меню вибору проблеми (мал. 2) задамо варіант “Створити нову проблему”. Впровадження моделі здійснюєтьсяпоетапно.

 

Крок I.

Введіть цільову функцію, використовуючи імена змінних з 14 символів або менше;
Цільова функція:

Крок II.

Будь ласка, введіть обмеження:

< для менш чи дорівнює
= для дорівнює
> для більш чи дорівнює

 

Після появи слів “обмеження” ввестиумови, що накладаються, і натиснути ENTER. Коли всі умови будуть уведені,надрукувати END.

обмеження 1:

обмеження 2:

обмеження 3:

обмеження 4:

обмеження 5:

обмеження 6:end

Після завершення введення математичної постановки екстремальної задачі пакет автоматично переходить у меню роботи з проблемою (мал. 3). Перед подальшим використанням модель бажано зберегти, вибравши відповідну опцію меню. Дамо їй ім'я LP1. Рішення задачі буде роздруковане у вигляді

Цільова функція Значення = 32.8

 

Змінні --------------------------	Значення –––––––––––––––––	Змінені ціни ––––––––––––––––––––
XI	1.6	0.0
Х2	5.6	0.0

 

Обмеження ---------------------	Недолік/Надлишок -------------------------------	Відчутність ------------------------–-
	9.2	0.0
	0.0	0.7
	0.0	0.5
	4.0	0.0
	38.2	0.0

 

Величини, зазначені в стовпчику “Недолік/Надлишок”, означають резерв ресурсу, що присутній у відповідному обмеженні. Стовпчик “Відчутність” показує, на скільки покращиться оптимальне значення при збільшенні на одиницю значення правої сторони нерівності. Так, для другого обмеження підвищення ресурсу на одиницю приведе до збільшення значення цільової функції на 0.7. Аналогічно для інших обмежень.

 

Наступна таблиця характеризує:

§ нижні і верхні границі коефіцієнтів, у межах яких може мінятися один з коефіцієнтів, і при цьому рішення будуть забезпечувати ті ж значення змінних;

§ діапазони правої частини нерівностей, для якої відчутність залишається постійною.