Різні форми запису задач лінійного програмування. Перехід від однієї форми запису до іншої
За формою запису серед задач лінійного програмування виділяють: стандартні (або симетричні), канонічні, загальні.
Стандартна задача – це задача дослідження цільової функції на максимум з обмеженнями – нерівностями типу ,, 
” і невід’ємними змінними. Вона має вигляд:
; 
, 
, 
Задачу можна подати за допомогою:
а) матричного запису: 
; ¢
; ¢
; ¢
де 
;
; 
; 
;
б) векторного запису: 
; ²
; ²
; ²
; ; 
; 
; ... ; 
.
Канонічназадача – це задача максимізації цільової функції при обмеженнях-рівностях, причому всі змінні невід’ємні. У канонічній задачі кількість невідомих завжди більша за кількість рівнянь 
.
Загальний вигляд канонічної задачі:
; 
; 
. 
Частинним випадком канонічної задачі є задача в базисній формі, тобто задача - , у якої 
і матриця системи обмежень 
містить одиничну матрицю розмірністю 
. Задача має вигляд:
;
;
; 
; … ; 
;
; 
; … ; 
.
Загальноюзадачею лінійного програмування є задача, у якій в систему обмежень входять як рівності, так і нерівності, вимога невід’ємності не накладається на усі змінні. Стандартна і канонічна задачі входять в клас загальних задач.
Загальна задача має вигляд:
; 
, 
; 
, 
; 
, 
; 
, 
, 
-довільні, 
. 
На практиці більшість економічних задач зводяться до побудови стандартних і загальних задач. Однак, основні методи розв’язування розроблені для канонічних задач. Тому виникає потреба перетворювати задачі лінійного програмування з однієї форми в іншу. Задачу мінімізації можна формально замінити на задачу максимізації і навпаки за допомогою рівностей:
;
.
Основним залишається перетворення системи обмежень.
Нерівності (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
.
Відповідь: 
;
; .