《工学单纯形》ppt课件

《《工学单纯形》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、从图形解到代数解的转换1ABCDEF最优点(1,2,0,0)方程组有m=2个方程和n=4个变量。因此最大数目的角点为解空间到底令哪些点为零才能对应一个特定的角点？(0，0，4，5)(0，2.5，1.5，0)(x1，x2，s1，s2)(2，0，0，3)2非基（零）变量基变量基本解相应的角点可行否？目标值Z（x1,x2）（s1,s2）(4,5)A是0（x1,s1）（x2,s2）(4,-3)F否-（x1,s2）（x2,s1）(2.5,1.5)B是7.5（x2,s1）（x1,s2）(2,3)D是4（x2,

2、s2）（x1,s1）(5,-6)E否-（s1,s2）（x1,x2）(1,2)C是8（最优点）可以看到，当问题的大小增加后（即m与n变大），枚举所有角点的过程包含巨量的计算，如m=10和n=20，必须求解184756个10×10阶的方程。而在很多实际的问题中，很多是有成百上千的变量和约束的问题。3单纯形方法单纯形方法的迭代本质ABCDEF最优点（x1=1，x2=2）正常情况下，单纯形从原点（A点）开始，此时Z=0，能否在当前零值的基础上，通过增加非基变量x1和x2来增加Z值？图形显示，增加x1和x2

3、将增加Z。单纯形方法每次要求增加一个变量，且选择使得Z有最大改善率的那个变量。因此选择增加x2具有最大改善率，因此增加x2直到角点B，在点B，再增加X1的值，达到改进的角点C，他是最优点。因此单纯形方法的路径是沿着A→B→C。沿着路径的每个角点与一步迭代是对应的，单纯形方法是沿着解空间的边缘移动，不能抄近路，直接A→C4ABCDEF最优点(1,2,0,0)(0，2.5，1.5，0)(2，0，0，3)x1x2s1s2A0045B02.51.50C1200D2003(0，0，4，5)单纯形方法的本质就

4、是换基！5相应的角点基变量非基（零）变量A（s1,s2）（x1,x2）B（x2,s1）（x1,s2）C（x1,x2）（s1,s2）可以看到，在基变量和非基变量中的变化模式随着解沿着路径A→B→C的移动而改变。A→B，在A处的非基变量x2变成B处的基变量，并且在A处的基变量s2变成在A处的非基变量，称X2为进基变量，s2为离基变量，类似地，在点B，x1进基，s1离基，因此到了C点6ReddyMikks公司使用M1和M2两种原料生产内、外墙涂料，其基本数据如下：每吨产品使用原料吨数日最大可用量（吨）外

5、墙涂料内墙涂料原料M16424原料M1126每吨利润（千美元）54市场调查表明，内墙涂料日需求量不超过外墙涂料的日需求加上1吨，内墙涂料的最大日需求量是2吨定义x1=外墙涂料的日生产吨数，x2=内墙涂料的日生产吨数7完整的ReddyMikks模型是MaxZ=5x1+4x2St6x1+4x2≤24（原料M1）x1+2x2≤6（原料M1）-x1+x2≤1（市场限制）x2≤2（需求限制）x1,x2≥08单纯形算法的计算细节基Zx1x2s1s2s3s4解Z1-5-400000Z行s1064100024s1

6、行s201201006s2行s30-1100101s3行s400100012s4行初始解是最优解吗？目标函数表明可以增加x1或x2来改进这个解，选择具有最正的系数的变量x1为进基变量，这个等价于将目标函数中最负系数的变量作为进基变量。——最优性条件，该条件确定进基变量单纯形迭代开始于原点（x2,x2）=(0,0)，因此,在初始点处的非基（零）变量：（x1,x2）在初始点处的基变量：（s1,s2,s3,s4）即Z=0，s1=24,s2=6,s3=1,s4=29基进基x1解比值（或截距）s1624X1

7、=24/6=4←最小值s216X1=6/1=6s3-11X1=1/-1=-1（不考虑）s402X1=2/0=∞（不考虑）结论：x1进基，s1离基从单纯形表中确定离基变量的方法是，计算方程的右端项（解列）与相应的在进基变量x1下方的约束系数的非负比——可行性规则最小非负比自动识别当前基变量s1作为离基变量，并指定进基变量x1的新值为410abcd-1461234561235s1=0s2=0s3=0s4=01/-1=-124/6=46/1=6ABC在点B处的非基（零）变量：（s1,x2）在点B处的基变

8、量：（x1,s2,s3,s4）11进基变量和离基变量如何“交换”？进基↓基Zx1x2s1s2s3s4解Z1-5-400000离基←s1064100024枢轴行s201201006s30-1100101s400100012枢轴行一些概念12基于高斯-乔丹行操作来计算新的基本解1.枢轴行a.在基列中，以进基变量替换离基变量b.新的枢轴行=当前枢轴行÷枢轴元素2.其他所有行，包括Z行新的行=当前行-当前枢轴列的系数×新的枢轴列将该方法应用到上表在基列中，以x1替换s1新的x1行=当前s1