3.3. Двоїста задача та практичне використання двоїстих оцінок в аналізі економічних проблем


Повернутися на початок книги
1 2 3 4 5 6 7 8 9 10 11 12 13 14 
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 
60 61 62 63 64 65 66 67 

Загрузка...

Двоїсту  задачу  можна побудувати  за таким  алгоритмом (рис. 3.1) [13].

 

Пряма задача:

 

Двоїста задача:

 

 

 

максимізація

 

**

 

мінімізація

 

 

 

константи в правіи частині обмежень

 

->►-<-

 

коефіцієнти цільової функції

 

 

 

коефіцієнт цільової функції

 

+"*г

 

константи

в правій частині обмежень

 

 

 

у'-й стовпчик з коефіцієнтів при невідомих в обмеженнях

 

^-<-

 

у'-й рядок з коефіцієнтів при невідомих обмеженнях

 

 

 

г'-й рядок з коефіцієнтів при невідомих в обмеженнях

 

+"<-

 

г'-й стовпчик з коефіцієнтів при невідомих в обмеженнях

 

 

 

у'-а невід'ємна змінна

 

^-<-

 

у'-а нерівність виду >

 

 

 

у-а змінна не має обмеження на знак

 

->*•<-

 

у'-е співвідношення є рівність

 

 

 

і-& нерівність виду <

 

+"*г

 

г-азмінна > 0

 

 

 

і-в співвідношення виду рівності

 

->►-<-

 

г-а змінна

не має обмеження на знак

 

Рис. 3.1.

Позначимо двоїсті змінні у. ,j = \,m і, використовуючи наве-

дений алгоритм, побудуємо двоїсту задачу до задачі (3.17)— (3.19) (задача (3.17)—(3.19) має назву пряма задача).

(3.20) (3.21) (3.22)

т                     

^аііУі -СІ > 1=\п ;

і=\

;

у >0, j = \,т

и(у) = T<b-y- —> min

у=і

Задача (3.20)—(3.22) є двоїстою до задачі (3.17)—(3.19). Між прямою і двоїстою задачами існує дуже важливий зв'я-зок, який формулюється теоремами двоїстості.

/ теорема. Якщо пряма і двоїста задачі мають допустимі

розв'язки, то існує х*(і = \,п) -- оптимальний розв'язок прямої задачі, у*Л} = \,т) —оптимальний розв'язок двоїстої задачі і

 

II теорема. Нехай х*(і = \,п) - розв'язок прямої задачі, y*(j = l,m) - розв'язок відповідної двоїстої задачі. Ці два розв'язки є оптимальними тоді і лише тоді, коли

 

У (X аііхі ~ Ь,) = 0,     j = 1, т

і=\

т                     

Хі СЕ^аііУ    ~ Сі ) = 0,         І = \,П

 

(3.23)

 

Отже, якщо пряма задача має обмеження виду строгої нерів-ності, то відповідна змінна двоїстої задачі має нульове значення (дорівнює нулю).

Оптимальні значення змінних двоїстої задачі визначаються по останній симплекс-таблиці при розв'язанні задачі максимізації і співпадають з коефіцієнтами при вільних змінних в А-рядку.

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

Якщо оптимальне значення деякої змінної двоїстої задачі до-датне, то цей ресурс є дефіцитним для прямої задачі і збільшення його величини надасть можливість знайти другий оптимальний розв'язок й покращити значення функції цілі.

Для задачі про оптимальне використання сировини, яку роз-глянуто у прикладі, оптимальними оцінками сировини є такі:

у* = /г   у*2 = /С  (грошових одиниць), тобто обидва види сиро-

вини використовуватимуться у виробничому процесі повністю, тому є дефіцитними.

У разі збільшення на одиницю виробничого споживання сиро-вини першого типу очікуваний прибуток підприємства (з відпо-

відною корекцією виробничої програми) зросте на 165 грошових

одиниць; збільшення на одиницю виробничого споживання сиро-

вини другого типу дозволить збільшити прибуток на 175 грошо-

вих одиниць.

3 останніх п співвідношень (3.23) походить, у свою чергу, що у випадку, коли розмір сукупних витрат ресурсів на одиницю продукції,   обчислений   за   оптимальними   оцінками   ресурсів

у*, j = 1,т , перевищуватиме прибуток Cj від реалізації одиниці /'-

оі продукци, тоді оптимальнии обсяг виробництва х. дорівнює нулю.