Page 29 - 6449

Зокрема, двоїсту задачу вигідніше розв’язувати, ніж вихідну пряму,
якщо в прямій задачі при малій кількості змінних ( М > 1) наявна велика
кількість обмежень.
Основні правила постановки двоїстої задачі до прямої або до
вихідної ЗЛП формуються таким чином:
Якщо пряма задача є задачею знаходження максимуму цільової
функції, то двоїста – задача знаходження мінімуму.
Цільова функція двоїстої задачі як вектор прибутку містить вектор
обмежень прямої.
Вектор обмежень двоїстої задачі є вектором прибутку прямої.
Кількість обмежень двоїстої задачі дорівнює кількості невідомих у
прямій задачі.
Кількість невідомих двоїстої задачі дорівнює кількості обмежень у
прямій задачі.

Всі знаки обмежень у двоїстій задачі є протилежними до знаків
обмежень у прямій задачі.
На ті невідомі двоїстої задачі, які відповідають обмеженням типу
нерівності, у двоїстій задачі накладається умова невід’ємності, на інші
невідомі така умова не накладається.
При невідомих прямої задачі, на які накладена умова невід’ємності
в двоїстій задачі відповідають обмеженням виду нерівності, іншим
невідомим відповідають обмеження вигляду рівнянь.
Матриця двоїстої задачі є транспонованою матрицею прямої.
Пара задач- пряма ЗЛП та двоїста до неї ЗЛП - є взаємно
двоїстими.
З економічної точки зору можна пояснити такі особливості прямої
та двоїстої задачі – якщо пряма задача є задачою максимізації прибутку, то
двоїста задача є задачею мінімізації затрат на виробництво [10,13,17].
З теорії лінійного програмування відомим є такий факт: якщо пряма
та двоїста задача мають два розв’язки, при яких значення цільових
функцій співпадають, то вказані розв’язки є оптимальними розв’язками
відповідних задач. Запишемо постановку прямої та двоїстої задачі в
загальному вигляді:
1. Пряма задача :
Z  X C  X C  X C  ......... X C  max
1 1 2 2 3 3 n n
 a 11  x 1  a 12  x 2 .....  a 1 n  x n  b 1
 a  x  a  x .....  a  x  b
 21 1 22 2 2 n n 2
 .......... .......... .......... .......... .......... .....

 a S1  x 1  a S 2  x 2 .....  a sn  x n  b S (1.31)
 a  x  a  x .....  a  x  b
 S  1,1 1 S  2,1 2 s  n,1 n S 1
 .......... .......... .......... .......... .......... .......... ....

 a m1  x 1  a m2  x 2 .....  a mn  x n  b m
n
x 1 ,x 2 ,.......,x k  , 0 k 

29