Site Overlay

运筹学笔记 / 对偶问题

原问题化对偶问题

例子:
$$
\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 + y3\ ? \ 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$

发表评论

电子邮件地址不会被公开。 必填项已用*标注