Page 222 - 4685

Q
i
maxEAI : = ; 0 ¤ ;

[
K
K
!
Q
h ; 1 ¤ ≥ S H = 1, … , E;
=
=
K
K!
g ¤ ≥ 0A = 1, … E.

Подвійну задачу по відношенню до прямої складають згідно наступних
правил:
1) якщо цільова функція прямої задачі задається на max, тоді цільова
функція подвійної задачі – на min, і навпаки;
1 1 … 1
!! ![ !>
1 1 … 1
2) матриця n = ¥ [! ![ [> ¦, складена з коефіцієнтів в системі
… … … …
1 Q! 1 Q[ … 1 Q>
a a ... a 
 11 21 m1 
a a ... a 
обмежень прямої задачі, і аналогічна матриця A T =  12 22 m2  у подвійній
 ... ... ... ... 
 
 a n 1 a 2 m ... a mn 
задачі виходять одна з одної транспонуванням;
3) кількість змінних в подвійній задачі (m) дорівнює кількості
співвідношень (обмежень) в прямій задачі, а число обмежень в подвійній задачі
(n) – кількості змінних в прямій задачі;
4) коефіцієнти при невідомих в цільовій функції прямої задачі – це вільні
члени (b ), а праві частини в обмеженнях подвійної задачі (c ) – це коефіцієнти
j
i
при невідомих в цільовій функції прямої задачі;
5) якщо змінна x прямої задачі може набувати лише позитивних значень (х
j
j
≥0), то j-та умова подвійної задачі – умова нерівності вигляду "≥"; якщо i-е
співвідношення в прямій задачі – нерівність, то i-та змінна подвійної задачі z ≥
i
0.
Якщо пряма задача має рішення, то і подвійна задача теж має рішення,
причому max (min) L = min (max) L . Тому досить для відшукання оптимуму
2
1
вирішити одну яку-небудь із задач подвійної пари; зазвичай вирішують ту, яка
простіша.
Оптимальний план подвійної задачі дозволяє оцінити міру дефіцитності
ресурсів, що споживаються при виконанні оптимального плану вихідної задачі.
Приклад. Для виробництва виробів А, В, С використовуються три різні
види ресурсів. Кожен з них може бути використаний в кількості, відповідно не
більшій 180, 210, 244 од. Відомі витрати кожного з видів ресурсів на одиницю
продукції і ціна одиниці продукції кожного виду:

218