原问题化对偶问题

例子:

$$ \max z=5 x_{1}+3 x_{2}+6 x_{3} \\ \left\{\begin{array}{l} x_{1}+2 x_{2}+x_{3} \leq 18 \\ 2 x_{1}+x_{2}+3 x_{3}=16 \\ x_{1}+x_{2}+x_{3}=10 \\ x_{1}, x_{2} \geq 0, x_{3} \text {无约束} \end{array}\right. $$

原问题求 max,那么我们先写出 min z'

目标函数

原问题有三个约束条件,那么对偶问题变量就有三个,记为 $\begin {bmatrix} y1\\y2\\y3\end {bmatrix}$,点乘以三个常数。则目标函数为:

$$ \min z = 18y_1+16y_2+10y_3 $$

约束条件

用 $x_1$ 的系数向量点乘以 $\begin {bmatrix} y1\\y2\\y3\end {bmatrix}$,得到约束条件 $y_1 + 2y_2 + y_3$,结合原函数 $\max z$ 中 $x_1$ 的系数。列出:

$$ y_1 + 2y_2 + y_3\ ? \ 5 $$

同理列出:

$$ \begin{array}{ll} y_{1}+2 y_{2}+y_{3} & 5 \\ 2 y_{1}+y_{2}+y_{3} & 3 \\ y_{1}+3 y_{2}+y_{3 } & 6 \end{array} $$

符号

$\max$ 化 $\min$,约束让变量反号,变量让约束同号。

$\min$ 化 $\max$,约束让变量同号,变量让约束反号。

比如:

  1. 第一个约束 $x_{1}+2 x_{2}+x_{3} {\color {red}\leq} 18$,是 $\leq$ 符号,则 $y_1 \geq 0$

  2. 第二个约束 $2 x_{1}+x_{2}+3 x_{3}=16$,是 $=$ 符号,则 $y_2$ 无约束,同理 $y_3$ 无约束。

而原来问题的变量约束是:

$$ x_{1}{\color {red}\geq} 0, x_{2} {\color {red}\geq} 0, x_{3} {\color {red}\text {无}} \text {约束} $$

则约束符号为:

$$ \begin{array}{ll} y_{1}+2 y_{2}+y_{3} {\color{red}\geq} 5 \\ 2 y_{1}+y_{2}+y_{3} {\color{red}\geq} 3 \\ y_{1}+3 y_{2}+y_{3 }{\color{red}=} 6 \end{array} $$

题型:已知单纯性表,写最优解和影子价格

【例子】下题为某问题的最终单纯形表,直接求其对偶问题的最优解,并求各资源的影子价格。

typora\20201219165836_42e2518c033e489b1ad9169543cdd8b2.png

【分析】

如图标上 $y_1, y_2, y_3$:

typora\20201219165843_50b41085999f4c5897ee9093cf7d2f6c.png

然后升序靠右写到下面:

typora\20201219165850_5ba2c2c553d0ddd0e73fdda1e891a1b8.png

再循环补齐变量:

typora\20201219165858_af2235fca66cd4ecb4fd76cf01880655.png

则最优解为 $\sigma_j$ 行乘以 $-1$,i.e.

$$ \begin{bmatrix} y_1\\y_2\\y_3\\y_4\\y_5 \end{bmatrix}= \begin{bmatrix} 0\\1/4\\1/2\\0\\0 \end{bmatrix} $$

本题 $b_1, b_2, b_3$ 的影子价格对应 $y_1, y_2, y_3$ 的取值,也即 $(0, 1/4, 1/2)$。

影子价格:已经达到最优解的情况下,增加单位数量的 $t$,使目标函数增加 $v$,则 $v$ 是 $t$ 的影子价格。

**未充分利用资源的影子价格为 0 **:比如你有 A 和 B 能生产出 C,A 已经用完了,则无论再给你多少的 B,也没有办法生产出新的 C,此时 B 的影子价格是 0。

对偶理论

  1. 原问题(极大化问题)为无界解,则对偶问题(极小化问题)无可行解;
  2. 对偶问题(极大化问题)为无界解,则原问题(极小化问题)无可行解;
  3. 原问题有可行解,对偶问题无可行解,则原问题为无界解;
  4. 原问题无可行解,则其对偶问题具有无界解或无可行解;
  5. 原问题目标函数值 = 对偶问题目标函数值原问题和对偶问题均取得最优解。
  6. 互为对偶问题,则一个有最优解意味着另一个也有最优解

已知最优解求原问题最优解

【例子】

$$ \begin{array}{l} \min \omega=2 x_{1}+3 x_{2}+5 x_{3}+2 x_{4}+3 x_{5} \\ \left\{\begin{array}{l} x_{1}+x_{2}+2 x_{3}+x_{4}+3 x_{5} \geq 4 \\ 2 x_{1}-x_{2}+3 x_{3}+x_{4}+x_{5} \geq 3 \\ x_{j} \geq 0, j=1,2, \cdots 5 \end{array}\right. \end{array} $$

最优解为:$y_{1}^{*}=\dfrac {4}{5}, y_{2}^{*}=\dfrac {3}{5}, z^{*}=5$,找出原问题的最优解。

【分析】

首先化为对偶问题。

两个方程,所以对偶变量两个 $y_1,y_2$。

根据系数列出:

$$ \begin{align} y_1 + 2y_2?2\\ y_1-y_2?3\\ 2y_1+3y_2?5\\ y_1+y_2?2\\ 3y_1+y_2?3 \end{align} $$

根据约束写出条件:

$y_1 \geq0,y_2 \geq 0$

得到对偶问题:$\max z= 4y_1 + 3y_2$

$$ \left\{ \begin{align} y_1 + 2y_2\leq2\\ y_1-y_2\leq3\\ 2y_1+3y_2\leq5\\ y_1+y_2\leq2\\ 3y_1+y_2\leq3\\ y_1 \geq0,y_2 \geq 0 \end{align} \right. $$

然后化标准型

$$ \max z=4 y_{1}+3 y_{2} \\\left\{ \begin{array}{l} y_{1}+2 y_{2}+y_{s_{1}}=2 \\ y_{1}-y_{2}+y_{s_{2}}=3 \\ 2 y_{1}+3 y_{2}+y_{s_{3}}=5 \\ y_{1}+y_{2}+y_{s_{4}}=2 \\ 3 y_{1}+y_{2}+y_{s_{5}}=3 \\ y_{1}, y_{2}, y_{s_{i}} \geq 0 \quad i=1 \cdots 5 \end{array} \right. $$

带入 $y_{1}^{*}=\dfrac {4}{5}, y_{2}^{*}=\dfrac {3}{5}$ 可以得到松弛变量的取值范围。

$$ \left\{\begin{array}{l} y_{s_{1}}=0 \\ y_{s_{2}}>0 \\ y_{s_{3}}>0 \\ y_{s_{4}}>0 \\ y_{s_{5}}=0 \end{array}\right. $$

根据互补松弛性,可知:

互补松弛性:

原问题变量,与对偶问题对应变量相乘等于零。

对偶问题变量,与原问题对应变量相乘等于零。

$$ \begin{array}{l} y_{s_{2}} \cdot x_{2}^{*}=0, \quad y_{s_{3}} \cdot x_{3}^{*}=0, \quad y_{s_{4}} \cdot x_{4}^{*}=0 \\ \text {又} y_{s_{2}}, y_{s_{3}}, y_{s_{4}} \text {均}>0, \text {故} x_{2}^{*}=x_{3}^{*}=x_{4}^{*}=0 \end{array} $$

将原问题化为标准型等式: $\left\{\begin {array}{l} x_{1}+x_{2}+2 x_{3}+x_{4}+3 x_{5}-x_{s_{1}}=4 \\ 2 x_{1}-x_{2}+3 x_{3}+x_{4}+x_{5}-x_{s_{2}}=3\end {array}\right.$, 由互补松弛性得: $y_{1}^{\circ} \cdot x_{s_{1}}=0, y_{2}^{\circ} \cdot x_{s_{2}}=0$ 又 $y_{1}^{*}=\frac {4}{5}, y_{2}^{*}=\frac {3}{5},$ 故 $x_{s_{1}}=x_{s_{2}}=0$, 带入解出 $x_1^*, x_5^*$,最优解为 $X^* = (1,0,0,0,1), \omega^* = 5$