8 Дуални задачи
Да разгледаме следната задача:
\begin{align*} \max z = 5x_1 + 7x_2\\ x_1 + 2x_2 \leq 10 \\ 2x_1 + x_2 \leq 8 \\ x_1 , x_2 \geq 0 \end{align*} \tag{8.1}
Оптимумът в тази задача се постига при x_1 = 2, x_2 = 4 със стойност на целевата функция z^* = 38. Искаме да използваме неравенствата в 8.1, за да докажем, че това е възможно най-голямата стойност на целевата функция.
| Последна таблица | ||||||
|---|---|---|---|---|---|---|
| C_j | 2 | 1 | 0 | 0 | ||
| Базисни пр. | C_B | X_B | x_1 | x_2 | s_1 | s_2 |
| x_2 | 7 | 4 | 0 | 1 | 2/3 | -1/3 |
| x_1 | 5 | 2 | 1 | 0 | -1/3 | 2/3 |
| Z | Z_j | 5 | 7 | 3 | 1 | |
| \Delta_j | 0 | 0 | 3 | 1 |
Въпрос: възможно ли е да намерим най-малката горна граница на целевата функция без да налучкваме коефициентите, с които да комбинираме уравненията?
Упражнение 8.1 (Дуална задача) Намерете дуалната задача за следната първична задача:
\begin{align*} & \max 5 x_1 + 12 x_2 + 4 x_33 \\ & x_1 + 2x_2 + x_3 \leq 10 \\ & 2x_1 - x_2 + 3x_3 \leq 8 \\ & x_1, x_2, x_3 \geq 0 \end{align*}
Каноничен вид на задачата:
\max 5 x_1 + 12 x_2 + 4 x_33 + 0 s_1 + 0 s_2\\
\begin{align*} x_1 + 2x_2 + x_3 + s_1& = 10 \quad \text{дуална променлива } y_1 \\ 2x_1 - x_2 + 3x_3 + s_2 & = 8 \quad \text{дуална променлива } y_2\\ x_1, x_2, x_3, s_1, s_2 & \geq 0 \end{align*}
Дуалната задача ще има 2 целеви променливи y_1 и y_2, по една за всяко ограничение.
Ограничения на дуалната задача
\begin{align*} & y_1 + 2 y_2 \geq 5 \\ & 2y_1 - y_2 \geq 12 \\ & y_1 + 3 y_2 \geq 4 \\ & y_1 + 0 y_2 \geq 0 \\ & 0y_1 + y_2 \geq 0 \end{align*}
Целева функция на дуалната задача:
\min 10 y_1 + 8 y_2
Същото представяне можем да получим чрез транспониране на матрицата от коефициентите на каноничната задача.
Ограничения на каноничната задача:
\underbrace{\begin{pmatrix} 1 & 2 & 1 & 1 & 0 \\ 2 & -1 & 3 & 0 & 1 \end{pmatrix}}_{A} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ s_1 \\ s_2 \end{pmatrix} = \begin{pmatrix} 10 \\ 8 \end{pmatrix}
А^T = \begin{pmatrix} 1 & 2 \\ 2 & -1 \\ 1 & 3 \\ 1 & 0 \\ 0 & 1 \\ \end{pmatrix}
\begin{pmatrix} 1 & 2 \\ 2 & -1 \\ 1 & 3 \\ 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} \geq \begin{pmatrix} 5 \\ 12 \\ 4 \\ 0 \\ 0 \end{pmatrix}
Упражнение 8.2 (Дуална задача) Намерете дуалната задача за следната първична задача:
\begin{align*} & \max z = 5x_1 + 12x_2 + 4x_3\\ & x_1 + 2x_2 + x_3 \leq 10 \\ & 2x_1 - x_2 + 3x_3 = 8 \\ & x_1 , x_2 , x_3 \geq 0 \end{align*}
Каноничен вид:
\begin{align*} & \max z = 5x_1 + 12x_2 + 4x_3 + 0s_1 \\ & x_1 + 2x_2 + x_3 + s_1 = 10 \\ & 2x_1 - x_2 + 3x_3 = 8 \\ & x_1 , x_2 , x_3 \geq 0 \end{align*}
Ограничения на дуалната задача
\begin{align*} & y_1 + 2y_2 \geq 5 \\ & 2 y_1 - y_2 \geq 12 \\ & y_1 + 3y_2 \geq 4 \\ & y_1 + 0 y_2 \geq 0 \\ & y_2 \text{ неограничена} \end{align*}
Целева функция на дуалната задача
\min 10 y_1 + 8 y_2
Упражнение 8.3 (Дуална задача) Намерете дуалната задача за следната първична задача:
\begin{align*} & \max z = 15x_1 + 12x_2\\ & x_1 + 2x_2 \leq 3 \\ & 2x_1 - 4x_2 \geq 5 \\ & x_1, x_2 \geq 0 \end{align*}
Каноничен вид на задачата \begin{align*} & \max z = 15x_1 + 12x_2 + 0s_1 + 0s_2\\ & x_1 + 2x_2 - s_1 = 3 \\ & 2x_1 - 4x_2 + s_2 = 5 \\ & x_1, x_2, s_1, s_2 \geq 0 \end{align*}
Ограничения на дуалната задача
\begin{align*} & y_1 + 2y_2 \geq 15 \\ & 2 y_1 + 4 y_2 \geq 12 \\ & -y_1 + 0y_2 \geq 0 \implies y_1 \leq 0 \\ & 0y_1 + y_2 \geq 0 \implies y_2 \geq 0 \end{align*}
Целева функция на дуалната задача:
\min 3 y_1 + 5 y_2
Упражнение 8.4 (Дуална задача) Намерете дуалната задача за следната първична задача:
\begin{align*} & \max z = 5x_1 + 6x_2\\ & x_1 + 2x_2 = 5 \\ & -x_1 + 5x_2 \geq 3 \\ & 4x_1 + 7x_2 \leq 8 \\ & x_1 \text{ неограничена}, x_2 \geq 0 \end{align*}
\begin{align*} & \max z = 5x_1^{+} - 5 x_1^{-} + 6x_2 + 0s_1 + 0s_2\\ & x_1^{+} - x_1^{-} + 2x_2 = 5 \\ & -x_1^{+} + x_1^{-} + 5x_2 - s_1 = 3 \\ & 4x_1^{+} - 4 x_1^{-} + 7x_2 + s_2 = 8 \\ & x_1^{+}, x_{1}^{-}, x_2, s_1, s_2 \geq 0 \end{align*}
Ограничения на дуалната задача:
\begin{align*} & y_1 - y_2 + 4y_3 \geq 5\\ & -y_1 + y_2 - 4y_3 \geq -5 \\ & 2y_1 + 5 y_2 + 7 y_3 \geq 6 \\ & 0 y_1 + 0y_2 + 0 y_3 \geq 0 \\ & -y_1 + 0y_2 + 0 y_3 \geq 0 \implies y_1 \leq 0 \\ & 0y_1 - y_2 + 0 y_3 \geq 0 \implies y_2 \geq 0 \end{align*}
\begin{align*} & y_1 - y_2 + 4y_3 = 5\\ & 2y_1 + 5 y_2 + 7 y_3 \geq 6 \\ & 0 y_1 + 0y_2 + 0 y_3 \geq 0 \\ & y_1 \leq 0 \\ & y_2 \geq 0 \end{align*}
Упражнение 8.5 (Дуална задача) Дадена е следната първична задача:
\begin{align*} & \max 5x_1 + 4x_2\\ & 6x_1 + 4x_2 \leq 24 \quad \text{ресурс 1}\\ & x_1 + 2x_2 \leq 6 \quad \text{ресурс 2} \\ & -x_1 + x_2 \leq 1 \quad \text{ресурс 3} \\ & x_2 \leq 2 \quad \text{ресурс 4} \end{align*}
Оптимумът се постига при x_1 = 3, x_2 = 1.5 и стойност на целевата функция z = 21. Проверете дали y_1 = 0.75, y_2 = 0.5, y_3 = y_4 = 0 е оптимум на дуалната задача.
Целевата функция на дуалната задача е
g = 24 y_1 + 6 y_2 + y_3 + 2 y_4
Стойността й за y_1 = 0.75, y_2 = 0.5, y_3 = y_4 = 0 е:
g = 24 \cdot 0.75 + 6 \cdot 0.5 + 0 + 2 \cdot 0 = 21
Това е и оптимум на дуалната задача, тъй като стойностите на първичната и на целевата функция съвпадат.
Упражнение 8.6 (Дуална задача) Предприятие произвежда три вида детски играчки: влакчета (x_1 на брой), камиончета (x_2 на брой) и коли (x_3 на брой). Целевата функция при оптимизацията е прогнозираната печалба (в лв.) от продажбата на тези играчки.
\begin{align*} & \max z = 3x_1 + 2x_2 + 5x_3 \\ & x_1 + 2x_2 + x_3 \leq 430 \quad \text{Персонал} \\ & 3x_1 + 2x_3 \leq 460 \quad \text{Пластмаса} \\ & x_1 + 4x_2 \leq 420 \quad \text{Метал} \\ & x_1, x_2, x_3 \geq 0 \end{align*}
Оптималния производствен план се постига при x_1 = 0, x_2 = 100, x_3 = 230, z = 1350. Оптималното решение на дуалната задача е y_1 = 1, y_2 = 2, y_3 = 0.
- Кои са дефицитните ресурси в оптималното решение?
- В оптималното решение предприятието не произвежда влакчета. С колко лева би намаляла печалбата на предприятието, ако то реши да произведе една единица от този продукт?
- Управителният съвет на предприятието обмисля да продаде десет единици от третия ресурс (метал) за 2 лв./единица. Изгоден ли е този ход за предприятието?
- Управителният съвет обмисля производството на нов продукт с прогнозна печалба на единица от 3 лв. За производството му са нужни една единица персонал и две единици метал. Преценете дали този ход ще е изгоден за предприятието.
8.1 Връзка между решенията на първичната и дуалната задача
| Първична задача | Дуална задача |
|---|---|
| Множество решения | Изродено решение |
| Едно неизродено решение | Едно неизродено решение |
| Множество неизродени решения | Едно изродено решение |
| Едно изродено решение | Множество решения |