单纯形法-人工变量法.ppt

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

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

2、解很明显。X(0)=(0，0，0，11，0，3，1)T不满足原来的约束条件。如何使得可从X(0)开始，经迭代逐步得到x6=0，x7=0的基可行解，从而求得问题的最优解，有两种方法：反之，若加了人工变量的问题解后最优解中仍含人工变量为基变量，便说明原问题无可行解。例的单纯形表格为：只要原问题有可行解，随着目标函数向最大化方向的改善，人工变量一定会逐步换出基，从而得到原问题的基可行解，进而得到基最优解。大M法在目标函数中加上惩罚项。max=3x1-x2-x3-Mx6-Mx7其中M为充分大的正数。3-6MM-13M-10-

3、M000x4103-20100-1-Mx610[1]00-11-21-1x31-20100011-1+M00-M0-3M+10x412[3]001-2-1x210100-14-1x31-201001000-13x141001/3-2/3-1x210100-1-1x390012/3-4/3-2000-1/3-1/3X*=(4，1，9，0，0)T,z*=2113/21〔〕两阶段法第一阶段：以人工变量之和最小化为目标函数。min=x6+x7第二阶段：以第一阶段的最优解(不含人工变量)为初始解，以原目标函数为目标函数。约束

4、方程为“>=”或“=”的情形（加人工变量）人工变量法（确定初始可行基）：原约束方程：AX=b加入人工变量：xn+1，，xn+m人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。MaxZ=2x1+x2+x3s.t.4x1+2x2+2x3≥42x1+4x2≤204x1+8x2+2x3≤16x1，x2，x3≥0用两阶段法求下面线性规划问题的解线性规划问题解的讨论一、无可行解maxz=

5、2x1+4x2x1+x2102x1+x240x1,x20人工变量不能从基底换出，此时原线性规划问题无可行解。x1x2CBXBbX3x50-10000-1x1x2x3x4x540210-1110[1]1100cj1040/2x1x50-1200-1-2-111011100cj-zj0-1-2-10cj-zj210-10Z0=-40Z1=-20两阶段法例:maxz=3x1+4x2x1+x2402x1+x260x1-x2=0x1,x20此题初始解是退化的。最优解也是退化解。退化解迭代中，当换入变量取零值时目

6、标函数值没有改进，x1x20x340111000x4602101-1-Mx50[1]-10010x3400[2]100x46003013x101-1003+M4-M000zj-cj000-7/3zj-cj0x30001-1/34x2200101/33x1201001/3cj→3400-MCBXBbx5θx1x2x3x40700zj-cj00-3.50zj-cj4x220011/200x4000-3/213x120101/20例maxz=3x1+5x23x1+5x2152x1+x252x1+2x211x1,x2

7、0如果将x1换入基底，得另一解，由可行域凸性易知，有两个最优解必有无穷多组最优解当非基底变量的检验数中有取零值，或检验数中零的个数大于基变量个数时，有无穷多解。CBXBbx3x4x500035000x1x2x3x4x5521010153[5]1003511/2x2x4x550033/511/50027/50-1/51054/50-2/501cj-zj00-100cj-zj35000Z0=01122001Z1=15x1x2四、无（有）界解maxz=x1+x2-2x1+x24x1-x22-3x1+x23x1,x2

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