第二章 单纯型法

第二章单纯形法

线性规划问题的矩阵表示 单纯形表的结构和性质单纯形表的运算初始基可行解的确定基可行解的判别和改进

非基变量基变量==1、线性规划的矩阵表示===BNIIB-1b非基变量σ基变量σ=CBB-1B-CB=0=Z+(CBB-1N-CN)XN=CBB-1b

XB+B-1NXN=B-1b

Z+（CBB-1A-C）X=CBB-1b

B-1AX=B-1b

X右端ZCBB-1A-CCBB-1bXBB-1AB-1b基变量在目标函数中的系数等于0，基变量在约束条件中的系数是一个单位矩阵约束条件的右端B非负2、单纯形表的结构和性质注意：Z行中有m个0，它们与基变量相对应。一般情况下，这m个0分散在Z行的各列中，并与基变量相对应。其余m行中有一个m阶单位矩阵I，其各列与基变量相对应。一般情况下，组成I的各列分散在表的各列中，它们与基变量相对应。单纯形表的结构我们将用单纯形表解决以下三个问题：如何找出第一个（初始的）基可行解？如何判断这个初始基可行解是不是最优解？如果不是，怎样将它调整成一个“更好的”基可行解，以致最终求出最优解？3、单纯形表的运算当线性规划问题的约束条件全为“小于等于约束”，并且右边常数全部“大于等于0”，化标准问题时在每个约束中添加的松弛变量恰构成一个单位矩阵，这单位矩阵可作为初始可行基。添加的松弛变量即为基变量，其他变量为非基变量。对于不能直接获得初始可行基的问题，可以用引入人工变量的方法构造一初始可行基。这将在“人工变量法”中作介绍。（1）初始基可行解的确定用检验数σj=Zj

–Cj

进行判断，若所有检验数σj≤0，则X是最优解。若存在某个检验数σj>0,它所对应的列向量全部分量为非正，则所给问题的目标函数值无下界，因而无最优解。若存在σj>0,且它（们）所对应的列向量中都有正分量，则这时可进行基变换。（2）基可行解的判别和改进若存在σj>0,且它（们）所对应的列向量中都有正分量，则这时可进行基变换。取max={σ1.。。。σj}所对应的非基变量为进基变量。将“右端”列中各数分别和“进基变量列”的各数作比式（只对进基变量列中的正数作比式），并以θ记这些比式中最小一个。获得θ行所对应的基变量即为离基变量。进基变量列和离基变量行相交处的元素成为“主元”，在其上加以圆圈。进行单纯形变换，即令主元为1，主元所在列的其他元素为0。即得一新的单纯形表，继续进行判断。（3）基可行解的基变换=目标函数约束条件基矩阵右边常数

进基变量、离基变量、基变换=基变量=进基变量离基变量目标函数约束条件右边常数==目标函数约束条件新的基矩阵右边常数==进基变量离基变量目标函数约束条件基矩阵==目标函数约束条件新的基矩阵右边常数=

单纯形表法的运算步骤单纯形表的运算Step0获得一个初始的单纯形表，确定基变量和非基变量Step1检查基变量在目标函数中的系数是否等于0，在约束条件中的系数是否是一个单位矩阵Step2如果表中非基变量在目标函数中的系数全为负数，则已得到最优解。停止。否则选择系数为正数且绝对值最大的变量进基。Step3如果进基变量在约束条件中的系数全为负数或0，可行域开放，目标函数无界。停止。否则选取右边常数和正的系数的最小比值，对应的基变量离基。Step4确定进基变量的列和离基变量的行交叉的元素为“主元”，对单纯形表进行行变换，使主元变为1，主元所在列的其他元素变为0。将离基的基变量的位置用进基的非基变量代替。转Step1。设X1表示I型饼干日产量，X2表示II型饼干日产量（单位为吨），z表示I型和II型饼干所创造的日总利润目标：

maxz=5X1+4X2约束条件：

3X1+5X2≤15

（搅拌机的限制）

2X1+X2≤5

（成形机的限制）

2X1+2X2≤11

（烘箱的限制）

X1≥0，X2≥0

例题：饼干生产问题转化为标准模型设z’=-z,引入松弛变量X3,X4,X5≥0

目标：

minz’=-5X1-4X2约束条件：

3X1+5X2+

X3=15

（搅拌机的限制）

2X1+X2+

X4=5

（成形机的限制）

2X1+2X2+

X5=11

（烘箱的限制）

X1,X2,X3,X4,X5≥0

写出初始单纯形表15/35/2x4离基x1进基x1x2X3X4X5右端Z540000x33510015x4210105X5220011111/2x1x2X3X4X5右端Z540000x33510015x4210105X52200111x101/205/21/210-5/20-25/23/201-3/2015/27/200-1161015/756x2进基x3离基得到最优解，最优解为：（x1，x2，x3，x4，x5）=（10/7，15/7，0，0，0，27/7）minz’=-110/7，maxz=110/7x1x2X3X4X5RHSZ′03/20-5/20-25/2x307/21-3/2015/2X111/201/205/2X5010-116x22/7-3/7015/710-3/7-13/70-110/700-1/75/7010/701-2/7-4/7127/700产品A产品B产品C利润（万元/吨）

941耗用原料（吨/吨）

425排放污染（m3/吨）

213销售价格（万元/吨）

301020总产量（吨）

111某工厂生产A、B、C三种产品，目标是这三种产品的总利润最大化。和利润有关的因素有原材料的消耗、排放的污染，产品的销售总额和三种产品的产量。有关数据如下表所示。设生产的产品全部销售，要求安排使总利润最大的生产计划，使得耗用原料不超过38吨，排放污染不超过25立方米，销售总额不低于100万元，三种产品的总产量不低于12吨。这是一个利润目标最大化的单目标线性规划问题。两阶段法举例人工变量法如果约束条件全为“≤”，且右边常数全为非负，则引进的松弛变量就可以作为初始的基变量，得到一个初始的基础可行解。如果约束条件有“=”

，右边常数全为非负，则需要加上非负人工变量，建立辅助问题。如果约束条件有“≥”，右边常数全为非负，则需要减去非负人工变量，建立辅助问题。4、人工变量法人工变量法举例思路——人为构造一个单位矩阵人工变量人工变量大M法的步骤引进松弛变量，使约束条件全为等式。引进人工变量，令人工变量在目标函数中的系数为大M（任意大的正数）用单纯形法求解，得到原问题的最优解。若基变量中有非零的人工变量，则该LP无可行解。(1)大M法的步骤求解以下LP问题(大M法)化为标准型后加入人工变量，得到辅助问题Minz=x1+3x2s.t.2x1+x2=43x1+4x2-x3=6x1+3x2+x4=3x1,x2,x3,x4

≥0+mr1+mr2,r1,r2+r2+r1

X1X2X3r1r2X4rhs比Z-1-30-m-m00

r12101004

r234-10106

X41300013

X1X2X3r1r2X4rhs比Z5m-15m-3-m00010m

r1[2]1010044/2r234-101066/3X413000133/1

X1X2X3r1r2X4rhs比Z00-1-1-m1-m02

X1101/52-1/502X201-2/5-3/52/500X40011-111X1X2X3r1r2X4rhs比Z05/2m-5/2-m1/2-5/2m002

X111/201/20024r20[5/2]-1-3/21000X4000-1/20112/5最优解x1=2,x2=0,x4=1,r1=r2=x3=0,minz=2练习：用大m法求解下列线性规划问题引进松弛变量，使约束条件全为等式。引进人工变量，建立辅助问题。辅助问题的目标函数为各人工变量之和（仅含人工变量）。用人工变量作为辅助问题的初始基变量，用单纯形法求解辅助问题，得到辅助问题的最优解和最优解的目标函数值。如果辅助问题最优解的目标函数值大于0，原问题可行域为空集，无可行解。如果辅助问题最优解的目标函数值等于0，辅助问题的最优解是原问题的初始基础可行解。将第一阶段得到的最终表除去人工变量，将目标函数行的系数换原问题的目标函数系数，作为第二阶段计算的初始表，用单纯形法求解，得到原问题的最优解。(2)两阶段法的步骤求解以下LP问题(两阶段法)minZ=X1+3X2s.t.2x1+x2=43x1+4x2-x3=6x1+3x2+x4=3x1,x2,x3,x4≥0

化成标准型第一阶段：作辅助问题minf=r1+r2s.t.2x1+x2+r1=43x1+4x2-x3+r2=6x1+3x2+x4=3x1,x2,x3,x4,r1,r2≥0

X1X2X3r1r2x4右端比f000-1-100

r12101004

r234-10106

x41300013

X1X2X3r1r2x4右端比f55-100010

r121010044/2r234-101066/3x413000133/1

X1X2X3r1r2x4右端比f05/2-1-5/2000

X111/201/20024r205/2-1-3/21000x405/20-1/20112/5

X1X2X3r1r2x4右端比f000-1-100