单纯型法精品课件

1、单纯型法第1页，共35页，2022年，5月20日，3点17分，星期二非基变量 基变量=1、线性规划的矩阵表示第2页，共35页，2022年，5月20日，3点17分，星期二=BNIIB-1b非基变量基变量=CBB-1B-CB=0第3页，共35页，2022年，5月20日，3点17分，星期二=Z+( CBB-1N-CN) XN= CBB-1b XB+B-1N XN=B-1b Z+（CBB-1A-C）X= CBB-1b B-1AX= B-1b X右端ZCBB-1A-CCBB-1bXBB-1AB-1b第4页，共35页，2022年，5月20日，3点17分，星期二基变量在目标函数中的系数等于0，基变量在约束条

2、件中的系数是一个单位矩阵约束条件的右端B非负2、单纯形表的结构和性质第5页，共35页，2022年，5月20日，3点17分，星期二注意：Z行中有m 个0，它们与基变量相对应。一般情况下，这m个0分散在Z行的各列中，并与基变量相对应。其余m行中有一个m阶单位矩阵I，其各列与基变量相对应。一般情况下，组成I的各列分散在表的各列中，它们与基变量相对应。单纯形表的结构第6页，共35页，2022年，5月20日，3点17分，星期二我们将用单纯形表解决以下三个问题：如何找出第一个（初始的）基可行解？如何判断这个初始基可行解是不是最优解？如果不是，怎样将它调整成一个“更好的”基可行解，以致最终求出最优解？3、单

3、纯形表的运算第7页，共35页，2022年，5月20日，3点17分，星期二当线性规划问题的约束条件全为“小于等于约束”，并且右边常数全部“大于等于0”，化标准问题时在每个约束中添加的松弛变量恰构成一个单位矩阵，这单位矩阵可作为初始可行基。添加的松弛变量即为基变量，其他变量为非基变量。对于不能直接获得初始可行基的问题，可以用引入人工变量的方法构造一初始可行基。这将在“人工变量法”中作介绍。（1）初始基可行解的确定第8页，共35页，2022年，5月20日，3点17分，星期二用检验数j=Zj Cj 进行判断，若所有检验数j0，则X是最优解。若存在某个检验数j 0,它所对应的列向量全部分量为非正，则所给

4、问题的目标函数值无下界，因而无最优解。若存在j 0,且它（们）所对应的列向量中都有正分量，则这时可进行基变换。 （2）基可行解的判别和改进第9页，共35页，2022年，5月20日，3点17分，星期二若存在j 0,且它（们）所对应的列向量中都有正分量，则这时可进行基变换。取max=1.。j 所对应的非基变量为进基变量。将“右端”列中各数分别和“进基变量列”的各数作比式（只对进基变量列中的正数作比式），并以记这些比式中最小一个。获得行所对应的基变量即为离基变量。进基变量列和离基变量行相交处的元素成为“主元”，在其上加以圆圈。进行单纯形变换，即令主元为1，主元所在列的其他元素为0。即得一新的单纯形表

5、，继续进行判断。（3）基可行解的基变换第10页，共35页，2022年，5月20日，3点17分，星期二=目标函数约束条件基矩阵右边常数 进基变量、离基变量、基变换=基变量第11页，共35页，2022年，5月20日，3点17分，星期二=进基变量离基变量目标函数约束条件右边常数=第12页，共35页，2022年，5月20日，3点17分，星期二=目标函数约束条件新的基矩阵右边常数=第13页，共35页，2022年，5月20日，3点17分，星期二=进基变量离基变量目标函数约束条件基矩阵=第14页，共35页，2022年，5月20日，3点17分，星期二=目标函数约束条件新的基矩阵右边常数=第15页，共35页，2

6、022年，5月20日，3点17分，星期二 单纯形表法的运算步骤单纯形表的运算Step 0 获得一个初始的单纯形表，确定基变量和非基变量Step 1 检查基变量在目标函数中的系数是否等于0，在约束条件中的系数是否是一个单位矩阵Step 2 如果表中非基变量在目标函数中的系数全为负数，则已得到最优解。停止。否则选择系数为正数且绝对值最大的变量进基。Step 3 如果进基变量在约束条件中的系数全为负数或0，可行域开放，目标函数无界。停止。否则选取右边常数和正的系数的最小比值，对应的基变量离基。Step 4 确定进基变量的列和离基变量的行交叉的元素为“主元”，对单纯形表进行行变换，使主元变为1，主元所

7、在列的其他元素变为0。将离基的基变量的位置用进基的非基变量代替。转Step 1。第16页，共35页，2022年，5月20日，3点17分，星期二 设X1表示I型饼干日产量，X2表示II型饼干日产量（单位为吨），z表示I型和II型饼干所创造的日总利润目标： max z = 5X1 +4X2约束条件： 3X1 +5X2 15 （搅拌机的限制） 2X1 + X2 5 （成形机的限制） 2X1 +2X2 11 （烘箱的限制） X1 0 ， X2 0 例题：饼干生产问题第17页，共35页，2022年，5月20日，3点17分，星期二 转化为标准模型 设z= - z, 引入松弛变量X3 , X4 , X5 0

8、 目标： min z = -5X1 -4X2约束条件： 3X1 +5X2 + X3 = 15 （搅拌机的限制） 2X1 + X2 + X4 = 5 （成形机的限制） 2X1 +2X2 + X5 = 11 （烘箱的限制） X1, X2, X3 , X4 , X5 0 第18页，共35页，2022年，5月20日，3点17分，星期二写出初始单纯形表15/35/2x4离基x1进基x1x2X3X4X5右端Z540000 x33510015x4210105X5220011111/2x1x2X3X4X5右端Z540000 x33510015x4210105X52200111x101/205/21/210-5

9、/20-25/23/201-3/2015/27/200-1161015/75 6x2进基x3离基第19页，共35页，2022年，5月20日，3点17分，星期二得到最优解，最优解为：（x1，x2，x3，x4，x5）=（10/7，15/7，0，0，0，27/7）min z=-110/7，max z=110/7x1x2X3X4X5RHSZ03/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第20页，共35页，2022年，

10、5月20日，3点17分，星期二产品A产品B产品C利润（万元/吨） 941耗用原料（吨/吨） 425排放污染（m3/吨） 213销售价格（万元/吨） 301020总产量（吨） 111某工厂生产A、B、C三种产品，目标是这三种产品的总利润最大化。和利润有关的因素有原材料的消耗、排放的污染，产品的销售总额和三种产品的产量。有关数据如下表所示。设生产的产品全部销售，要求安排使总利润最大的生产计划，使得耗用原料不超过38吨，排放污染不超过25立方米，销售总额不低于100万元，三种产品的总产量不低于12吨。这是一个利润目标最大化的单目标线性规划问题。两阶段法举例第21页，共35页，2022年，5月20日，

11、3点17分，星期二人工变量法如果约束条件全为“”，且右边常数全为非负，则引进的松弛变量就可以作为初始的基变量，得到一个初始的基础可行解。如果约束条件有“=” ，右边常数全为非负，则需要加上非负人工变量，建立辅助问题。如果约束条件有“”，右边常数全为非负，则需要减去非负人工变量，建立辅助问题。4、人工变量法第22页，共35页，2022年，5月20日，3点17分，星期二人工变量法举例思路人为构造一个单位矩阵人工变量人工变量第23页，共35页，2022年，5月20日，3点17分，星期二大M法的步骤引进松弛变量，使约束条件全为等式。引进人工变量，令人工变量在目标函数中的系数为大M （任意大的正数）用单

12、纯形法求解，得到原问题的最优解。若基变量中有非零的人工变量，则该LP无可行解。(1)大M法的步骤第24页，共35页，2022年，5月20日，3点17分，星期二求解以下LP问题(大M法)第25页，共35页，2022年，5月20日，3点17分，星期二化为标准型后加入人工变量，得到辅助问题Minz=x1+3x2s.t. 2x1+x2 =4 3x1+4x2-x3 =6 x1+3x2+x4 =3 x1,x2,x3,x4 0+mr1+mr2,r1,r2+r2+r1第26页，共35页，2022年，5月20日，3点17分，星期二X1X2X3r1r2X4rhs比Z-1-30-m-m00r12101004r234

13、-10106X41300013X1 X2X3r1r2X4rhs比Z5m-15m-3-m00010mr121010044/2r234-101066/3X413000133/1第27页，共35页，2022年，5月20日，3点17分，星期二X1X2X3r1r2X4rhs比Z00-1-1-m1-m02X1101/5 2-1/502X201-2/5-3/52/500X40011-111X1X2X3r1r2X4rhs比Z05/2m-5/2-m1/2-5/2m002X111/201/20024r205/2-1-3/21000X4000-1/20112/5最优解x1=2, x2=0, x4=1,r1=r2=x

14、3=0, minz=2第28页，共35页，2022年，5月20日，3点17分，星期二练习：用大m法求解下列线性规划问题第29页，共35页，2022年，5月20日，3点17分，星期二引进松弛变量，使约束条件全为等式。引进人工变量，建立辅助问题。辅助问题的目标函数为各人工变量之和（仅含人工变量）。用人工变量作为辅助问题的初始基变量，用单纯形法求解辅助问题，得到辅助问题的最优解和最优解的目标函数值。如果辅助问题最优解的目标函数值大于0，原问题可行域为空集，无可行解。如果辅助问题最优解的目标函数值等于0，辅助问题的最优解是原问题的初始基础可行解。将第一阶段得到的最终表除去人工变量，将目标函数行的系数换

15、原问题的目标函数系数，作为第二阶段计算的初始表，用单纯形法求解，得到原问题的最优解。(2)两阶段法的步骤第30页，共35页，2022年，5月20日，3点17分，星期二求解以下LP问题(两阶段法)第31页，共35页，2022年，5月20日，3点17分，星期二minZ=X1+3X2s.t. 2x1+ x2 =4 3x1+4x2-x3 =6 x1+3x2+ x4 =3 x1,x2,x3,x40化成标准型第一阶段：作辅助问题minf=r1+r2s.t. 2x1+x2+r1 =4 3x1+4x2-x3+r2 =6 x1+3x2+ x4 =3 x1,x2,x3,x4,r1,r20第32页，共35页，2022年，5月20日，3点17分，星期二X1X2X3r1r2x4右端比f000-1-100r12101004r234-10106x41300013X1X2X3r1r2x4右端比f55-100010r121010044/2r234-101066/3x413000133/1第33页，共35页，2022年，5月20日，3点17分，星期二X1X2X3r1r2x4右端比f05/2-1-5/2000X111/201/20024r205/2-1-3/21000 x405/20-1/20112/5X1X2X3