Перегляд вихідного коду сторінки Економічна інтерпретація прямої та двоїстої задач ЛП. Правила побудови двоїстих задач

== '''Економічна інтерпретація прямої та двоїстої задач ЛП''' ==


Кожна задача лінійного програмування пов’язана з іншою, так званою двоїстою задачею. 

Пряма задача:	<math>max F = c_1x_1 + c_2x_2 + … + c_nx_n</math>           '''(1)'''

<math>\left\{ {\begin{array}{l}
 a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n} \le b_1 \\ 
 a_{21}x_{1}+a_{22}x_{2}+...+a_{2n}x_{n} \le b_2 \\ 
................................ \\ 
 a_{m1}x_{1}+a_{m2}x_{2}+...+a_{mn}x_{n} \le b_m \\ 
\end{array}} \right.</math>                    '''(2)'''


<math>x_j \ge 0 , j= \overline{1,n}</math>                  '''(3)'''

Необхідно визначити, яку кількість продукції  кожного j-го виду <math>x_j ( j= \overline{1,n} )</math> необхідно виготовляти в процесі виробництва, щоб максимізувати загальну виручку від реалізації продукції під-приємства. Причому відомі: наявні обсяги ресурсів — <math>b_i ( i= \overline{1,m} )</math> ; норми витрат і-го виду ресурсу на виробництво одиниці j-го виду продукції — <math>a_{ij} ( i= \overline{1,m}, j= \overline{1,n} )</math>, а також <math>c_j ( j= \overline{1,n} )</math> — ціни реалізації одиниці j-ої продукції.


Нехай доцільно продавати деяку частину чи всі наявні ресурси. 

Позначимо <math>y_i</math> — ціна одиниці і-го ресурсу.

Необхідно визначити такі ціни ресурсів щоб загальна ціна на них була мінімально.  Продавати ресурси доцільно лише за умо-ви, що виручка, отримана від продажу ресурсів, перевищує суму, яку можна було б отримати від реалізації продукції, виготовленої з тих самих обсягів ресурсів, тобто: 
<math>min Z = b_1y_1 + b_2y_2 + … + b_ny_n</math>              '''(4)'''

за умов:

<math>\left\{ {\begin{array}{l}
 a_{11}y_{1}+a_{12}y_{2}+...+a_{1n}y_{n} \ge c_1 \\ 
 a_{21}y_{1}+a_{22}y_{2}+...+a_{2n}y_{n} \ge c_2 \\ 
................................ \\ 
 a_{m1}y_{1}+a_{m2}y_{2}+...+a_{mn}y_{n} \ge c_m \\ 
\end{array}} \right.</math>                           '''(5)'''

<math>y_i \ge 0 , i= \overline{1,m}</math>                  '''(6)'''
 
Необхідно визначити, які мінімальні ціни можна встановити для одиниці кожного і-го виду ресурсу <math>y_i, i= \overline{1,m}</math> щоб продаж ресурсів був доцільнішим, ніж виробництво продукції. 
Зауважимо, що справжній зміст величин <math>y_i, i= \overline{1,m}</math> — умовні ціни, що виражають рівень «цінності» відповідного ресурсу для даного виробництва. Англійський термін «shadow prices» у літе-ратурі перекладають як «оцінка» або «тіньова, неявна ціна». Ака-демік Л. В. Канторович назвав їх об’єктивно обумовленими оці-н¬ками відповідного ресурсу.
Початкова постановка задачі та математична модель може мати вигляд як (1)—(3), так і (4)—(6). Отже, як правило, кажуть про пару спряжених задач лінійного програмування.



== '''Правила побудови двоїстих задач''' ==


Вважають, що задача лінійного програмування подана у стан-дартному вигляді, якщо в задачі максимізації всі обмежень при-ведені до виду « <math>\le</math> », а для задачі мінімізації — до виду « <math>\ge</math> ».
Якщо пряма задача лінійного програмування подана в стандарт¬ному вигляді, то двоїста задача утворюється прави-лами:
1. Кожному обмеженню прямої задачі відповідає змінна двоїс-тої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі.
2. Кожній змінній прямої задачі відповідає обмеження двоїстої задачі, причому кількість обмежень двоїстої задачі дорівнює кількості невідомих прямої задачі.
3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі — на визначення найменшого значення (min), і навпаки.
4. Коефіцієнтами при змінних у цільовій функції двоїстої за-дачі є вільні члени системи обмежень прямої задачі.
5. Правими частинами системи обмежень двоїстої задачі є ко-ефіцієнти при змінних у цільовій функції прямої задачі.
6. Матриця коефіцієнтів при змінних у системі обмежень прямої задачі, і матриця коефіцієнтів у системі обмежень двої-стої задачі утворюються одна з одної транспонуванням

[[Файл:F_1_rm36.PNG]]

Схема побудови двоїстої задачі до прямої


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

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

{|border=1
| '''Пряма задача'''
| '''Двоїста задача'''
|-
|'''Cиметричні задачі'''
|-
| <math>max F = CX</math>
| <math>min Z = BY</math>
|-
| <math>AX \le B</math>
| <math>A^TY \ge C</math>
|-
| <math>X \ge 0</math>
| <math>Y \ge 0</math>
|-
| <math>max F = CX</math>
| <math>nax Z = BY</math>
|-
| <math>AX \ge B </math>
| <math>A^TY \le C</math>
|-
| <math>X \ge 0</math>
| <math>Y \ge 0</math>
|-
| '''Несиметричні задачі'''
|-
| <math>max F = CF</math>
| <math>min Z = BY</math>
|-
| <math>AX = B</math>
| <math>A^TY \ge C</math>
|-
| <math>X \le 0</math>
| <math>Y \in [-\propto ; \propto ]</math>
|-
| <math>min F = CX</math>
| <math>max Z = BY</math>
|-
| <math>AX = B</math>
| <math>A^TY \le C</math>
|-
| <math>X \ge</math>
| <math>Y \in [-\propto ; \propto ]</math>
|}