单纯形法步骤详解（附例题）-Toy模板网

这篇具有很好参考价值的文章主要介绍了单纯形法步骤详解（附例题）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

用单纯形法求解下列问题：
$Max 6x_1 + 14x_2 + 13x_3$
$s.t.\left\{ \begin{aligned} x_1+4x_2+2x_3&\le48\\ x_1+2x_2+4x_3&\le60\\ x_1,x_2,x_3&\ge0 \end{aligned} \right.$

将模型转化为标准形式

首先进行标准化,线性规划的标准形式：
$（LP）\left\{ \begin{aligned} &MaxC^TX\\ &s.t.Ax=b\\ &x\ge0 \end{aligned} \right.$
即约束条件都是等式，等式约束的右端项为非负的常数，每个变量都要求取非负数值（无约束也不行）

方法

若目标函数为最小值，将目标函数取一个负数转换为求最大值即可
若约束为不等式。约束方程为“≤”不等式,则可在“≤”不等式的左端加入非负松弛变量，把原不等式变为等式；约束方程为“≥”不等式，则可在“≥”不等式的左端减去非负剩余变量（也可称松弛变量)，把原不等式变为等式约束条件。
若表达式 $x_i$ 没有约束。用 $x_i-x_j$ 代替 $x_i$ 即可。

例题

$Min -x_1 + 2x_2 - 3x_3$
$s.t.\left\{ \begin{aligned} x_1+x_2+x_3&\le7\\ x_1-x_2+x_3&\ge2\\ 3x_1-x_2-2x_3&=-5\\ x_1,x_2\ge0,x_3&无约束 \end{aligned} \right.$
将该LP问题转化为标准型：
$Max x_1 - 2x_2 + 3(x_3-x_4)+0x_5+0x_6$
$s.t.\left\{ \begin{aligned} x_1+x_2+x_3-x_4+x_5&=7\\ x_1-x_2+x_3-x_4-x_6&=2\\ -3x_1+x_2+2(x_3-x_4)&=5\\ x_1,x_2,x_3,x_4,x_5,x_6&\ge0 \end{aligned} \right.$

$\textbf{接原问题,}$ 将原LP问题化为标准型可得：
$Max 6x_1 + 14x_2 + 13x_3+0x_4+0x_5$
$s.t.\left\{ \begin{aligned} x_1+4x_2+2x_3+x_4&=48\\ x_1+2x_2+4x_3+x_5&=60\\ x_1,x_2,x_3,x_4,x_5&\ge0 \end{aligned} \right.$

初始化单纯形表

取初始基本可行解 $x_1 = x_2 = x_3 = 0， x_4 = 48， x_5 = 60$ ；它的基 [p4, p5]= $\begin{vmatrix} 1 & 0\\ 0 & 1 \end{vmatrix}$ 为单位矩阵。
由标准形式可知
$C=[6,14,13,0,0]^T$ , $C_B=[0,0]^T$ ,
A= $\begin{vmatrix} 1 & 4 & 2 & 1 & 0\\ 1 & 2 & 4 & 0 & 1 \end{vmatrix}$ = $P_1,P_2,P_3,P_4,P_5]$ ,
$b=[48,60]^T$
此时， $-z=-0\times48-0\times60=0$
则初始的单纯形表为：

			$c_1$	$c_2$	$c_3$	$c_4$	$c_5$
$C_B$	$X_B$	b	6	14	13	0	0	$\theta$
0	$x_4$	48	1	4	2	1	0	12
0	$x_5$	60	1	2	4	0	1	30
		-z:0	6	14	13	0	0

检验数

其中，最后一行为检验数：
$\sigma_i=c_i-\displaystyle \sum{m \atop k=1}c_ka_{ki}$
即 $\sigma_1=6-0\times1-0\times1=6$ ,
$\sigma_2=14-0\times4-0\times2=14$ ,
$\sigma_3=13-0\times2-0\times4=13$ ,
$\sigma_4=0-0\times1-0\times0=0$
$\sigma_5=0-0\times0-0\times1=0$
易知第一次单纯性表的检验数分别为对应系数 $c_i$ 。

进基变量

取非负检验数中的最大值为进基变量（对于检验数这一行值，当检验数均为非正后，达到最优（一定是对Max问题），如果此时非基变量检验数有0值，则有无限多最优解；如果计算过程中出现检验数大于0的列对应的系数列向量中所有分量都有 $a_{ik}\le0$ ，则无有限最优解），在此题中，14为正数中的最大值，则 $x_2$ 为进基变量。

离基变量

计算最后一列的 $\theta$ 值，设进基变量的下角标为k,即 $x_k$ 为进基变量， $\theta$ = $b_i/a_{ik}$ ,如果 $a_{ik}=0$ ,该 $\theta_i$ 设为无穷大，选择最小的作为离基变量。
即 $\theta_1=b_1/a_{12}=48/4=12$ ， $\theta_2=b_2/a_{22}=60/2=30$ ；
该题中的最小值为12，所以离基变量为 $x_4$ 。

初等行变换

继续计算单纯性表，将进基变量通过初等行变换为单位向量，即从 $\begin{vmatrix} 4\\ 2 \end{vmatrix}$ 变为 $\begin{vmatrix} 1\\ 0 \end{vmatrix}$
为此，我们将第一行乘以1/4，在将第二行减去2倍的第一行，注意，加粗部分均需参与初等行变换。 $C_B$ 系数部分按照相应的进基变量、离基变量进行修改。

			$c_1$	$c_2$	$c_3$	$c_4$	$c_5$
$C_B$	$X_B$	b	6	14	13	0	0	$\theta$
0	$x_2$	48	1	4	2	1	0	12
0	$x_5$	60	1	2	4	0	1	30
		-z:0	6	14	13	0	0
			$c_1$	$c_2$	$c_3$	$c_4$	$c_5$
$C_B$	$X_B$	b	6	14	13	0	0	$\theta$
14	$x_2$	12	1/4	1	1/2	1/4	0	24
0	$x_5$	36	1/2	0	3	-1/2	1	12
		-z:-168	5/2	0	6	-7/2	0

对斜体部分进行计算得到 $-z=-14\times12-0\times36=-168$
计算检验数：
$\sigma_1=6-14\times1/4-0\times1/2=6-14/4=5/2$ ,
$\sigma_2=14-14\times1-0\times0=0$ ,
$\sigma_3=13-14\times1/2-0\times3=6$ ,
$\sigma_4=0-14\times1/4-0\times（-1/2）=-7/2$
$\sigma_5=0-14\times0-0\times1=0$
基变量对应的检验数一定为0。
6最大， $x_3$ 进基；
计算 $\theta_i$ ：
$\theta_1=b_1/a_{12}=12/（1/2）=24$ ， $\theta_2=b_2/a_{22}=36/3=12$ ；
12最小， $x_5$ 离基。
同理继续进行变换、计算：

			$c_1$	$c_2$	$c_3$	$c_4$	$c_5$
$C_B$	$X_B$	b	6	14	13	0	0	$\theta$
0	$x_4$	48	1	4	2	1	0	12
0	$x_5$	60	1	2	4	0	1	30
		-z:0	6	14	13	0	0
			$c_1$	$c_2$	$c_3$	$c_4$	$c_5$
$C_B$	$X_B$	b	6	14	13	0	0	$\theta$
14	$x_2$	12	1/4	1	1/2	1/4	0	24
0	$x_5$	36	1/2	0	3	-1/2	1	12
		-z:-168	5/2	0	6	-7/2	0
			$c_1$	$c_2$	$c_3$	$c_4$	$c_5$
$C_B$	$X_B$	b	6	14	13	0	0	$\theta$
14	$x_2$	6	1/6	1	0	1/3	-1/6	36
13	$x_3$	12	1/6	0	1	-1/6	1/3	72
		-z:–240	3/2	0	0	-5/2	-2
			$c_1$	$c_2$	$c_3$	$c_4$	$c_5$
$C_B$	$X_B$	b	6	14	13	0	0	$\theta$
6	$x_1$	36	1	6	0	2	-1
13	$x_3$	6	0	-1	1	-1/2	1/2
		-z:–294	0	-9	0	-11/2	-1/2

此时，检验数全为非正数，当前解即为最优解， $x^*=[36,0,6,0,0]^T$ ,最优解为 $z = 294$ 。
值得注意的是、变量非负约束是单纯形表中所隐含的,任何时候b列的值都应是非负的，如果出现负值，则表示当前基本解不是可行解，求解也就无法进行。文章来源地址https://www.toymoban.com/news/detail-735351.html