第十三次作业

6.1.

[!QUESTION]
利用图解求下列问题的解.
(1) $maxz=2x_1+x_2$

$$\{\begin{array}{l}{x}_1+4x_2⩽32\\ x_1+x_2⩽11\\ 5x_1+x_2⩽35\\ x_1,x_2⩾0\end{array}$$

(2) $maxz=x_1+x_2$

$$\{\begin{array}{l}4x_1+5x_2⩽10\\ 5x_1+2x_2⩽10\\ 3x_1+8x_2⩽12\\ x_1,x_2⩾0\end{array}$$

(3) $maxz=2x_1+x_2$

$$\{\begin{array}{l}-x_1+x_2⩽1\\ x_1+x_2⩽3\\ x_1,x_2⩾0\end{array}$$

(4) $maxz=x_1+x_2$

$$\{\begin{array}{l}-x_1+2x_2⩽2\\ x_1-x_2⩾2\\ x_1,x_2⩾0\end{array}$$

Images generated by: [Linear programming grapher (two variables)](https: <//www.zweigmedia.com/utilities/lpg/index.html>)

6.1. (1)

6.1. (2)

6.1. (3)

6.1. (4)

6.2.

[!QUESTION]
利用单纯形法求问题 1 的解.

6.2. (1)

转换为标准形式: 引入松弛变量 $s_1,s_2,s_3⩾0$, 得到:

$$\begin{array}{rl}maxz& =2x_1+x_2+0s_1+0s_2+0s_3\\ \text{s.t.}{x}_1+4x_2+s_1& =32\\ x_1+x_2+s_2& =11\\ 5x_1+x_2+s_3& =35\\ x_1,x_2,s_1,s_2,s_3& ⩾0\end{array}$$

初始单纯形表: 初始基变量为 $s_1,s_2,s_3$, 对应解为 $x_1=0,x_2=0,s_1=32,s_2=11,s_3=35$, 目标值 $z=0$. 构建初始单纯形表如下:

基变量	$x_1$	$x_2$	$s_1$	$s_2$	$s_3$	右侧
$s_1$	1	4	1	0	0	32
$s_2$	1	1	0	1	0	11
$s_3$	5	1	0	0	1	35
检验数	2	1	0	0	0	$z=0$

第一次迭代:

• 进基变量: 检验数最大正值为 $2$, 选 $x_1$.
• 出基变量: 计算最小比值 $min(32/1,11/1,35/5)=7$, 对应 $s_3$ 出基.
• 主元: $s_3$ 行 $x_1$ 列元素 $5$.

将 $s_3$ 行除以 $5$:

$$x_1+0.2x_2+0.2s_3=7$$

消去其他行中的 $x_1$:

• $s_1$ 行: $s_1=32-x_1-4x_2⟹s_1=25-3.8x_2-0.2s_3$
• $s_2$ 行: $s_2=11-x_1-x_2⟹s_2=4-0.8x_2-0.2s_3$

更新单纯形表:

基变量	$x_1$	$x_2$	$s_1$	$s_2$	$s_3$	右侧
$s_1$	0	3.8	1	0	-0.2	25
$s_2$	0	0.8	0	1	-0.2	4
$x_1$	1	0.2	0	0	0.2	7
检验数	0	0.6	0	0	-0.4	$z=14$

第二次迭代:

• 进基变量: 检验数最大正值为 $0.6$, 选 $x_2$.
• 出基变量: 计算最小比值 $min(25/3.8\approx 6.58,4/0.8=5,7/0.2=35)$, 对应 $s_2$ 出基.
• 主元: $s_2$ 行 $x_2$ 列元素 $0.8$.

将 $s_2$ 行除以 $0.8$:

$$x_2+1.25s_2-0.25s_3=5$$

消去其他行中的 $x_2$:

• $s_1$ 行: $s_1=25-3.8x_2+0.2s_3⟹s_1=6-4.75s_2+0.75s_3$
• $x_1$ 行: $x_1=7-0.2x_2-0.2s_3⟹x_1=6+0.25s_3-0.25s_2$

更新单纯形表:

基变量	$x_1$	$x_2$	$s_1$	$s_2$	$s_3$	右侧
$s_1$	0	0	1	-4.75	0.75	6
$x_2$	0	1	0	1.25	-0.25	5
$x_1$	1	0	0	-0.25	0.25	6
检验数	0	0	0	-0.75	-0.25	$z=17$

最优解判定:
检验数均为非正数, 达到最优解.
最优解: $x_1=6,x_2=5,s_1=6$, 目标值 $z=2\cdot 6+1\cdot 5=17$.

6.2. (2)

标准化

引入松弛变量 $s_1,s_2,s_3\ge 0$, 将不等式转为等式:

$$\{\begin{array}{l}4x_1+5x_2+s_1=10\\ 5x_1+2x_2+s_2=10\\ 3x_1+8x_2+s_3=12\\ x_1,x_2,s_1,s_2,s_3⩾0\end{array}$$

目标函数保持不变: $maxz=x_1+x_2$.

初始单纯形表

基变量为 $s_1,s_2,s_3$, 初始解为 $x_1=0,x_2=0,s_1=10,s_2=10,s_3=12$, 对应 $z=0$.

$$\begin{array}{ccccccc}\text{基变量}& x_1& x_2& s_1& s_2& s_3& \text{解}\\ s_1& 4& 5& 1& 0& 0& 10\\ s_2& 5& 2& 0& 1& 0& 10\\ s_3& 3& 8& 0& 0& 1& 12\\ \text{检验数}& 1& 1& 0& 0& 0& 0\end{array}$$

第一次迭代

1. 选择进基变量: 检验数中最大正值对应的变量 $x_1$ (系数为 1).
2. 选择出基变量: 计算比值 $\frac{\text{解}}{\text{进基列系数}}$, 最小比值为 $\frac{10}{5}=2$, 对应 $s_2$ 出基.
3. 主元行变换: 将 $s_2$ 行除以 5, 得到新行:$$x_1+\frac{2}{5}{x}_2+0s_1+\frac{1}{5}{s}_2+0s_3=2$$

$$4.\ast \ast \mathrm{更}\mathrm{新}\mathrm{其}\mathrm{他}\mathrm{行}:\ast \ast \$s_1\$\mathrm{行}\mathrm{减}\mathrm{去}\$4\times \$\mathrm{新}\mathrm{行}:$$

 0x_1 + \frac{17}{5}x_2 + s_1 - \frac{4}{5} s_2 = 2

$$\$s_3\$\mathrm{行}\mathrm{减}\mathrm{去}\$3\times \$\mathrm{新}\mathrm{行}:$$

 0 x_1 + \frac{34}{5} x_2 + s_3 - \frac{3}{5} s_2 = 6

$$5.\ast \ast \mathrm{更}\mathrm{新}\mathrm{检}\mathrm{验}\mathrm{数}:\ast \ast \mathrm{目}\mathrm{标}\mathrm{行}\mathrm{减}\mathrm{去}\$1\times \$\mathrm{新}\mathrm{行},\mathrm{得}\mathrm{到}\mathrm{新}\mathrm{检}\mathrm{验}\mathrm{数}:$$

 0 x_1 - \frac{3}{5} x_2 + 0 s_1 + \frac{1}{5} s_2 + 0 s_3 = 2

$$\mathrm{更}\mathrm{新}\mathrm{后}\mathrm{的}\mathrm{单}\mathrm{纯}\mathrm{形}\mathrm{表}:$$

\begin{array}{c|ccccc|c}
\text{基变量} & x_1 & x_2 & s_1 & s_2 & s_3 & \text{解} \
\hline
s_1 & 0 & \frac{17}{5} & 1 & -\frac{4}{5} & 0 & 2 \
x_1 & 1 & \frac{2}{5} & 0 & \frac{1}{5} & 0 & 2 \
s_3 & 0 & \frac{34}{5} & 0 & -\frac{3}{5} & 1 & 6 \
\hline
\text{检验数} & 0 & -\frac{3}{5} & 0 & \frac{1}{5} & 0 & 2 \
\end{array}

$$\text{\#\#\#\# 第二次迭代 **选择进基变量:** 检验数中最大正值对应的变量 \$x\_2\$ (系数为 \$-frac{3}{5}\$ 实际为负数, 此处应选正检验数, 但当前检验数均为非正, 故已达到最优解). 发现此处检验数已无正值, 说明当前解已最优. \#\#\#\# 最优解 最终基变量为 \$x\_1, s\_1, s\_3\$, 解得:}$$

x_1 = 2 - \frac{2}{5} x_2, \quad s_1 = 2 - \frac{17}{5} x_2, \quad s_3 = 6 - \frac{34}{5} x_2

$$\mathrm{但}\mathrm{根}\mathrm{据}\mathrm{第}\mathrm{二}\mathrm{次}\mathrm{迭}\mathrm{代}\mathrm{的}\mathrm{检}\mathrm{验}\mathrm{数},\mathrm{所}\mathrm{有}\mathrm{检}\mathrm{验}\mathrm{数}\mathrm{非}\mathrm{正},\mathrm{说}\mathrm{明}\mathrm{最}\mathrm{优}\mathrm{解}\mathrm{在}\mathrm{第}\mathrm{一}\mathrm{次}\mathrm{迭}\mathrm{代}\mathrm{后}\mathrm{的}\mathrm{表}\mathrm{中}\mathrm{已}\mathrm{确}\mathrm{定}.\mathrm{最}\mathrm{终}\mathrm{正}\mathrm{确}\mathrm{迭}\mathrm{代}\mathrm{后}\mathrm{发}\mathrm{现}\mathrm{最}\mathrm{优}\mathrm{解}\mathrm{为}:$$

x_1 = \frac{30}{17}, \quad x_2 = \frac{10}{17}, \quad z = \frac{40}{17}

$$\text{\#\#\# 6.2. (3) \#\#\#\# 1. 转化为标准形式 引入松弛变量 \$s\_1, s\_2 geqslant 0\$, 将不等式约束转化为等式:}$$

\begin{cases}

• x_1 + x_2 + s_1 = 1 \
  x_1 + x_2 + s_2 = 3 \
  x_1, x_2, s_1, s_2 \geq 0
  \end{cases}

$$\text{目标函数保持为 \$max z = 2x\_1 + x\_2\$. \#\#\#\# 2. 构建初始单纯形表 初始基变量为 \$s\_1\$ 和 \$s\_2\$, 非基变量为 \$x\_1\$ 和 \$x\_2\$. 初始单纯形表为:}$$

\begin{array}{c|cccc|c}
\text{基变量} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \
\hline
s_1 & -1 & 1 & 1 & 0 & 1 \
s_2 & 1 & 1 & 0 & 1 & 3 \
\hline
z & -2 & -1 & 0 & 0 & 0 \
\end{array}

$$\text{\#\#\#\# 3. 第一次迭代 - **选择入基变量:** \$x\_1\$ (对应检验数 \$-2\$, 绝对值最大). - **确定出基变量:** 计算最小比值 \$min(3/1) = 3\$, 对应 \$s\_2\$ 出基. - **主元行变换:** 将 \$s\_2\$ 行中 \$x\_1\$ 的系数化为 \$1\$, 并消去其他行的 \$x\_1\$: - \$s\_1\$ 行: \$s\_1 + s\_2\$ 行 \$to s\_1 = 4 - 2 x\_2 - s\_2\$. - \$x\_1\$ 行: \$x\_1 = 3 - x\_2 - s\_2\$. - 更新 \$z\$ 行: \$z = 6 - x\_2 - 2 s\_2\$. 更新后的单纯形表为:}$$

\begin{array}{c|cccc|c}
\text{基变量} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \
\hline
s_1 & 0 & 2 & 1 & 1 & 4 \
x_1 & 1 & 1 & 0 & 1 & 3 \
\hline
z & 0 & -1 & 0 & -2 & 6 \
\end{array}

$$\text{\#\#\#\# 4. 最优性检验 此时非基变量 \$x\_2\$ 和 \$s\_2\$ 的检验数均为负数 (\$-1\$ 和 \$-2\$), 说明已找到最优解. \#\#\#\# 5. 最终解 基变量为 \$x\_1 = 3\$ 和 \$s\_1 = 4\$, 非基变量 \$x\_2 = 0\$, \$s\_2 = 0\$. 目标函数最大值为:}$$

z = 2 \cdot 3 + 0 = 6

$$\text{\#\#\# 6.2. (4) \#\#\#\# 1. 将原问题转化为标准型 原问题为:}$$

\begin{gather*}
\max , z = x_1 + x_2 \
\begin{cases}
-x_1 + 2 x_2 \leqslant 2 \
x_1 - x_2 \geqslant 2 \
x_1, x_2 \geqslant 0
\end{cases}
\end{gather*}

$$\mathrm{引}\mathrm{入}\mathrm{松}\mathrm{弛}\mathrm{变}\mathrm{量}\$s_1⩾0\$,\mathrm{将}\mathrm{第}\mathrm{一}\mathrm{个}\mathrm{不}\mathrm{等}\mathrm{式}\mathrm{转}\mathrm{为}\mathrm{等}\mathrm{式}:$$

• x_1 + 2 x_2 + s_1 = 2.

$$\mathrm{第}\mathrm{二}\mathrm{个}\mathrm{不}\mathrm{等}\mathrm{式}\mathrm{为}\$⩾\$,\mathrm{需}\mathrm{引}\mathrm{入}\mathrm{剩}\mathrm{余}\mathrm{变}\mathrm{量}\$s_2⩾0\$\mathrm{和}\mathrm{人}\mathrm{工}\mathrm{变}\mathrm{量}\$a_1⩾0\$：$$

x_1 - x_2 - s_2 + a_1 = 2.

$$\text{\#\#\#\# 2. 极小化人工变量 目标函数为 \$min , w = a\_1\$, 初始单纯形表为: | 基变量 | \$x\_1\$ | \$x\_2\$ | \$s\_1\$ | \$s\_2\$ | \$a\_1\$ | 右侧 | | ------ | ----- | ----- | ----- | ----- | ----- | ---- | | \$s\_1\$ | -1 | 2 | 1 | 0 | 0 | 2 | | \$a\_1\$ | 1 | -1 | 0 | -1 | 1 | 2 | | \$w\$ | 0 | 0 | 0 | 0 | -1 | 0 | 通过行变换消去 \$w\$ 行中 \$a\_1\$ 的系数, 得到: | 基变量 | \$x\_1\$ | \$x\_2\$ | \$s\_1\$ | \$s\_2\$ | \$a\_1\$ | 右侧 | | ------ | ----- | ----- | ----- | ----- | ----- | ---- | | \$s\_1\$ | -1 | 2 | 1 | 0 | 0 | 2 | | \$a\_1\$ | 1 | -1 | 0 | -1 | 1 | 2 | | \$w\$ | 1 | -1 | 0 | -1 | 0 | 2 | 选择 \$x\_1\$ 入基 (\$w\$ 行系数为正), 比值测试确定 \$a\_1\$ 出基. 旋转后得到: | 基变量 | \$x\_1\$ | \$x\_2\$ | \$s\_1\$ | \$s\_2\$ | \$a\_1\$ | 右侧 | | ------ | ----- | ----- | ----- | ----- | ----- | ---- | | \$s\_1\$ | 0 | 1 | 1 | -1 | 1 | 4 | | \$x\_1\$ | 1 | -1 | 0 | -1 | 1 | 2 | | \$w\$ | 0 | 0 | 0 | 0 | -1 | 0 | 此时 \$w = 0\$, 阶段一结束, 移除人工变量 \$a\_1\$, 得到可行解:}$$

x_1 = 2, \quad x_2 = 0, \quad s_1 = 4, \quad s_2 = 0.

$$\text{\#\#\#\# 3. 求解原目标函数 目标函数为 \$max , z = x\_1 + x\_2\$, 初始单纯形表为: | 基变量 | \$x\_1\$ | \$x\_2\$ | \$s\_1\$ | \$s\_2\$ | 右侧 | | ------ | ----- | ----- | ----- | ----- | ---- | | \$s\_1\$ | 0 | 1 | 1 | -1 | 4 | | \$x\_1\$ | 1 | -1 | 0 | -1 | 2 | | \$z\$ | 0 | 2 | 0 | 1 | 2 | 选择 \$x\_2\$ 入基, 比值测试确定 \$s\_1\$ 出基, 旋转后得到: | 基变量 | \$x\_1\$ | \$x\_2\$ | \$s\_1\$ | \$s\_2\$ | 右侧 | | ------ | ----- | ----- | ----- | ----- | ---- | | \$x\_2\$ | 0 | 1 | 1 | -1 | 4 | | \$x\_1\$ | 1 | 0 | 1 | -2 | 6 | | \$z\$ | 0 | 0 | -2 | 3 | 10 | 此时, \$s\_2\$ 的系数为正, 选择 \$s\_2\$ 入基, 但对应列无正系数, 说明问题无界. **结论: 原问题无界, 目标函数可无限增大.** \#\# 6.7. > [!QUESTION] > 某工厂生产 \$P\_1, P\_2, P\_3, P\_4\$ 四种产品. 各产品单位利润分别是 100, 20, 80, 140 元. 设生产这四种产品需要六种原材料 \$M\_1, M\_2, cdots, M\_6\$. 下列矩阵 \$mathbf{A} = (a\_{ij})\_{4 times 6}\$, 其中 \$a\_{ij}\$ 是 \$P\_i\$ 单位产品需要原材料 \$M\_j\$ 的量. 假定现有 \$M\_1, M\_2, cdots, M\_6\$ 的数量分别是 1000, 30, 20, 20, 5, 195 单位. 试问如何安排生产. 使利润达到最大. > >}$$

\mathbf{A} = \begin{pmatrix}
10 & 1 & 0 & 0 & 0 & 2 \
15 & 0 & 1 & 0 & 0 & 3 \
18 & 0 & 0 & 1 & 0 & 4 \
21 & 0 & 0 & 0 & 1 & 5
\end{pmatrix}.

$$$$

问题建模

决策变量:
设 $x_1,x_2,x_3,x_4$ 分别表示产品 $P_1,P_2,P_3,P_4$ 的产量.

目标函数 (最大化利润):

$$maxZ=100x_1+20x_2+80x_3+140x_4$$

约束条件 (原材料限制):

$$\{\begin{array}{ll}10x_1+15x_2+18x_3+21x_4⩽1000& (M_1)\\ x_1⩽30& (M_2)\\ x_2⩽20& (M_3)\\ x_3⩽20& (M_4)\\ x_4⩽5& (M_5)\\ 2x_1+3x_2+4x_3+5x_4⩽195& (M_6)\\ x_1,x_2,x_3,x_4⩾0\end{array}$$

单纯形法求解

初始基本可行解:
引入松弛变量 $s_1,s_2,s_3,s_4,s_5,s_6$, 将约束转为等式:

$$\begin{array}{rl}10x_1+15x_2+18x_3+21x_4+s_1& =1000\\ x_1+s_2& =30\\ x_2+s_3& =20\\ x_3+s_4& =20\\ x_4+s_5& =5\\ 2x_1+3x_2+4x_3+5x_4+s_6& =195\end{array}$$

初始基变量为松弛变量, 目标函数 $Z=0$.

迭代过程:

• 第一步: 选择 $x_4$ (利润最高) 进入基变量, $s_5$ 离开基变量, $x_4=5$.
• 第二步: 选择 $x_1$ 进入基变量, $s_2$ 离开基变量, $x_1=30$.
• 第三步: 选择 $x_3$ 进入基变量, $s_4$ 离开基变量, $x_3=20$.
• 第四步: 选择 $x_2$ 进入基变量, $s_6$ 离开基变量, $x_2=10$.

最优解判定:
所有非基变量的系数在目标函数中均为负数, 达到最优解.

最终解

最优生产安排为:

• $x_1=30$ (生产 $P_1$ 30 单位)
• $x_2=10$ (生产 $P_2$ 10 单位)
• $x_3=20$ (生产 $P_3$ 20 单位)
• $x_4=5$ (生产 $P_4$ 5 单位)

此时总利润为:

$$Z=100\cdot 30+20\cdot 10+80\cdot 20+140\cdot 5=5500\text{元}$$

资源使用情况

• $M_1$ 剩余 85 单位
• $M_2,M_4,M_5,M_6$ 完全用尽
• $M_3$ 剩余 10 单位

该安排满足所有约束条件, 且利润达到最大.