Різні форми запису задач лінійного програмування. Перехід від однієї форми запису до іншої

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

Стандартна задача – це задача дослідження цільової функції на максимум з обмеженнями – нерівностями типу,, ” і невід’ємними змінними. Вона має вигляд:

;

, ,

Задачу можна подати за допомогою:

а) матричного запису: ; ¢

; ¢

; ¢

 

де ;

; ; ;

 

б) векторного запису: ; ²

; ²

; ²

; ; ; ;...; .

Канонічна задача – це задача максимізації цільової функції при обмеженнях-рівностях, причому всі змінні невід’ємні. У канонічній задачі кількість невідомих завжди більша за кількість рівнянь .

Загальний вигляд канонічної задачі:

;

;

.

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

;

;

; ; …; ;

; ; …; .

Загальною задачею лінійного програмування є задача, у якій в систему обмежень входять як рівності, так і нерівності, вимога невід’ємності не накладається на усі змінні. Стандартна і канонічна задачі входять в клас загальних задач.

Загальна задача має вигляд:

;

, ;

, ;

, ;

, ,

-довільні, .

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

;

.

Основним залишається перетворення системи обмежень.

Нерівності (9) множенням лівих і правих частин на (-1) можна перетворити в нерівності (8) і навпаки. Якщо в задачі деяка змінна довільного знаку, то її подають у вигляді різниці двох невід’ємних змінних: , де і . У випадку, коли деяка змінна , то її замінюють на , де .

Існують такі способи перетворень.

1. Перехід від стандартної до канонічної форми здійснюється шляхом введення додаткових невід’ємних змінних так, щоб система нерівностей перетворилася в систему рівнянь:

, .

При цьому нова система обмежень буде мати рівнянь і змінних.

Якщо є розв’язком канонічної задачі, то є розв’язком стандартної задачі.

2. Перехід від канонічної до стандартної форми можна здійснити двома способами. Першим – кожну рівність замінити однією з систем нерівностей:

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

(13)

оскільки , , , то покладемо , тоді одержимо:

Підставимо систему в цільову функцію, одержимо

.

Таким чином, одержали задачу в стандартному вигляді.

Приклад 3.1

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

;

;

Відомо, що , ;

змінні: , і :

;

.

Крім того, введемо дві додаткові змінні і , щоб нерівності перетворити в рівності.

Задача набуде вигляду:

;

, , ,

, , .

Приклад 3.2

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

;

, .

Зменшимо кількість невідомих. Для цього виділимо базис методом Жордана-Гаусса:

 

1 2 1 1 5

2 3 1 3 9

1 2 1 1 5

0 –1 –1 1 –1

1 2 1 1 5

0 1 1 –1 1

1 0 –1 3 3

0 1 1 –1 1

.

Відповідь: ;

; .