单纯形法-人工变量法

《单纯形法-人工变量法》由会员分享，可在线阅读，更多相关《单纯形法-人工变量法（20页珍藏版）》请在装配图网上搜索。

1、单击以编辑母版标题样式,,单击以编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,*,人工变量的引入及其解法,,当约束条件为“,,”型，引入剩余变量和人工变量,由于所添加的剩余变量的技术系数为,1，不能作为初始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变量,,由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定,,两种方法,,大M法,,二阶段法,,其中第2、3个约束方程中无明显基变量，分别加上人工变量,x,6,, x,7,,,约束

2、方程为“>=”或“=”的情形,（,加,人工变量,）,,这时，初始基和初始基可行解很明显。,X,(0),=(0，0，0，11，0，3，1),T,不满足原来的约束条件。如何使得可从,X,(0),开始，经迭代逐步得到,x,6,=0，,x,7,=0 的基可行解，从而求得问题的最优解，有两种方法：,,反之，若加了人工变量的问题解后最优解中仍含人工变量为基变量，便说明原问题无可行解。例的单纯形表格为：,,只要原问题有可行解，随着目标函数向最大化方向的改善，人工变量一定会逐步换出基，从而得到原问题的基可行解，进而得到基最优解。,大M法,在目标函数中加上惩罚项。,,max =,3,x,1,-,x,2,-,x,

3、3,-,M,x,6,-,M,x,7,,其中M为充分大的正数。,,3,-,6M M,-,1 3M,-,1 0,,-,M 0 0,,,0,x,4,,10 3 -2 0 1 0 0 -1,,-M,x,6,1 0,[,1,],0 0 -1 1 -2 1,,-1,x,3,1 -2 0

4、 1 0 0 0 1,,1,-1+M 0 0,,-,M 0 -3M+1,,,0,x,4,,12,[,3,],0 0 1 -2,,-1,x,2,1 0 1 0 0 -1 4,,-1,x,3,1 -2 0

5、 1 0 0,,1,0 0 0,,-1,,,3,x,1,,4 1 0 0 1/3 -2/3,,-1,x,2,1 0 1 0 0 -1,,-1,x,3,9 0 0 1 2/3 -4/3,,-2,0 0

6、0,,-1/3 -1/3,,,X,*,= (4，1，9，0，0),T,, z,*,= 2,,11,,3/2,,1,〔 〕,,两阶段法,第一阶段,：以,人工变量之和,最小化为目标函数。,min,,=,x,6,+,x,7,,第二阶段,：以第一阶段的最优解(不含人工变量)为初始解，以原目标函数为目标函数。,,,,,约束方程为“>=”或“=”的情形,（,加,人工变量,）,人工变量法（确定初始可行基）：,原约束方程：AX=b,加入人工变量：x,n+1,，,，x,n+m,人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验

7、数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。,,Max Z=2x,1,+ x,2,+ x,3,,s.t. 4x,1,+2x,2,+ 2x,3,≥4,,2x,1,+4x,2,≤20,,4x,1,+8x,2,+ 2x,3,≤16,,x,1,，x,2,，x,3,≥0,用两阶段法求下面线性规划问题的解,,线性规划问题解的讨论,一、无可行解,,,max z=2x,1,+4x,2,,x,1,+x,2,10,,,2x,1,+x,2,,,40,x,1,,x,2,0,,人工变量不能从基底换出，此时原线性规划问题无可行解。,x,1,x,2,,C,B,X,B,b,X3,,,x5,,0

8、,,-1,,0 0 0 0 -1,,x,1,x,2,x,3,x,4,x,5,40 2 1 0 -1 1,10 [1] 1 1 0 0,c,j,,10,,40/2,x1,,,x5,,0,,-1,,20 0 -1 -2 -1 1,10 1 1 1 0 0,,c,j,-z,j,0 -1 -2 -1 0,,,c,j,

9、-z,j,2 1 0 -1 0,Z,0,=-40,Z,1,=-20,两阶段法,,,,例,:,max z=3x,1,+4x,2,x,1,+x,2,40,,,2x,1,+x,2,60,,,x,1,-x,2,=0,x,1,,x,2,0,,此题初始解是退化的。最优解也是退化解。,,退化解迭代中，当换入变量取零值时目标函数值没有改进，,x,1,x,2,0,x,3,40 1 1 1 0 0,0,x,4,60 2 1 0 1 -1,-

10、M,x,5,0 [1] -1 0 0 1,0,x,3,40 0 [2] 1 0,0,x,4,60 0 3 0 1,3,x,1,0 1 -1 0 0,3+M 4-M 0 0 0,z,j,-,c,j,,0 0 0 -7/3,,z,j,-,c,j,,0,x,3,0 0 0 1 -1/3,,,4,x,2,20 0 1 0 1/3,3,x,1,20

11、1 0 0 1/3,,c,j,→,3 4 0 0 -M,,C,B,,X,B,b,x,5,,θ,x,1,x,2,x,3,,,x,4,,,0 7 0 0,z,j,-,c,j,0 0 -3.5 0,z,j,-,c,j,4,x,2,20 0 1 1/2 0,0,x,4,0 0 0 -3/2 1,3,x,1,20 1 0 1/2 0,,,,例 max z=3x,1,+5x,2,3x,1,+5x,2

12、,15,,,2x,1,+ x,2,5,,2,x,1,+2x,2,11,,x,1,,x,2,0,,如果将x,1,换入基底，得另一解，由可行域凸性易知，有两个最优解必有无穷多组最优解,,当非基底变量的检验数中有取零值，或检验数中零的个数大于基变量个数时，有无穷多解,。,,,C,B,X,B,b,x3,,,x4,,x5,,0,,0,,0,3 5 0 0 0,,x,1,x,2,x,3,x,4,x,5,5 2 1 0 1 0,15 3 [5 ] 1

13、0 0,,3,,5,,11/2,x2,,,x4,,x5,,5,,0,,0,3 3/5 1 1/5 0 0,,2 7/5 0 -1/5 1 0,,5 4/5 0 -2/5 0 1,,c,j,-z,j,0 0 -1 0 0,,c,j,-z,j,3 5 0 0 0,Z,0,=0,11 2 2 0 0 1,Z,1,=15,

14、x,1,x,2,,四、无（有）界解,,max z=x,1,+x,2,-2x,1,+x,2,4,,,x,1,- x,2,2,,-3,x,1,+x,2,3,,x,1,,x,2,0,,若检验数有大于0，而对应系数列中元素全部小于或等于零（无换出变量）则原问题有无界解。,练习：写出单纯形表,分析检验数,,与系数关系并画图验证。,,,线性规划解除有,唯一最优解,的情况外，还有如下几种情况,,无可行解,,退化,,无穷多解,,无界解,人工变量不能从基底中换出,基可行解中非零元素个数小于基变量数,检验数中零的个数多于基变量的个数,检验数大于零，但对应列元素小于等于零，无换出变量,,,唯一最优解,,否

15、,,否,否,,是,是,是,添加松弛变量,、,人工变量 列出初始单纯形表,,计算非基变量,,各列的检验数,б,j,所有,б,j,,0,基变量中,,有非零的,,人工变量,某非基变量检验数为零,无可行解,无穷多最优解,对任一,б,j,≥,0,,有a,ik,≤,0,无界解,令,б,k,=max{,б,j,},x,k,为换入变量,,对所有a,ik,>,0计算,θ,i,=b,i,/a,ik,,令,θ,l,=min{θ,i,},,第l个基变量,为换出变量，,a,l,k,为主元素,,,迭代运算,,.,用非基变量x,k,替换换出变量,,,,.,对主元素行(第l行),,令 b,l,/a,lk,→,b,l,;a,lj,/a,lk,→,a,jl,,对主元素列(第k列)令1,→a,lk,;0→,其它元素表中其它行列元素,,令 a,ij,-a,li,/a,lk,·,a,ik,→a,ij,,,b,i,-b,l,/a,lk,·a,ik,→b,i,,,б,j,- a,lj,/a,lk,· б,k,→ б,j,否,对目标函数求极大值标准型线性规划问题，单纯形法计算步骤的框图：,,