Приклад виконання завдання

Розглянемо приклад виконання завдання за вихідних даних, наведених у таблиці 1.4.

Таблиця 1.4 – Вихідні дані задачі

Вид заготовки	Кількість заготовок, отриманих за варіантами розкрою, шт.				Потреба у заготовках, шт.
	1	2	3	4
І	5	–	4	2	80
ІІ	–	7	1	4	60
Відходи паперу, см2	25	15	25	12

Розв’язок.

Складемо математичну модель задачі. Нехай х_і ( ) кількість рулонів, що розкроюються за і-м варіантом. Тоді, за умовою задачі, необхідно мінімізувати відходи від розкрою паперу

при обмеженнях на заданий план виходу заготовок кожного виду

;

.

– на невід’ємність змінних задачі

; ; ; .

Запишемо для цієї прямої задачі двоїсту.

Максимізувати

,

при обмеженнях

;

;

;

;

; .

Двоїста задача має дві незалежні змінні, тому може бути вирішена графічним методом. Рішення двоїстої задачі графічним методом наведено на рис. 1.1.

Оптимальне рішення двоїстої задачі досягається у точці перетину прямих

Рисунок 1.1 – Рішення двоїстої задачі графічним методом

Вирішивши цю систему рівнянь отримаємо оптимальний план двоїстої задачі: ; ; F_max = 430.

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

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

;

;

;

;

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

Покладаючи та у системі обмежень прямої задачі та замінивши знаки нерівностей на знаки рівностей отримаємо систему рівнянь

;

.

Звідки знаходимо оптимальне рішення прямої задачі: ; ; .

Таким чином, необхідно розкроїти 10 рулонів паперу за першим варіантом та 15 рулонів паперу за третім варіантом. При цьому мінімальна кількість відходів складе 430 см².

Контрольні запитання

1. У чому полягає сутність двоїстості у лінійному програмуванні ?

2. Які двоїсті задачі називають симетричними, а які – несиметричними ? У чому полягає їх відмінність ?

3. Як визначається кількість змінних та обмежень двоїстої задачі у відповідності до прямої задачі ?

4 Сформулюйте теореми двоїстості.

5 Сформулюйте правила побудови двоїстих задач лінійного програмування.

6 Запишіть всі види прямих та двоїстих задач.