最新单纯形法-人工变量法课件.ppt

1、人工变量的引入及其解法人工变量的引入及其解法 当约束条件为当约束条件为“ ”型，引入剩余变量和人工变量型，引入剩余变量和人工变量 由于所添加的剩余变量的技术系数为由于所添加的剩余变量的技术系数为 1，不能作为初，不能作为初始可行基变量，为此引入一个人为的变量（注意，此始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为时约束条件已为“=”型），以便取得初始基变量，故型），以便取得初始基变量，故称为人工变量称为人工变量 由于人工变量在原问题的解中是不能存在的，应尽快由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值被迭代出去，因此人工变量在目标函

2、数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定法而定 两种方法两种方法 大大M法法 二阶段法二阶段法 标准型：标准型： max z =3 3x1- -x2- -x3 s.t. 01 23 2 411 2 513153214321x,xxxxxxxxxxx其中第其中第2、3个约束方程中无明显基变量，分别加上人工变量个约束方程中无明显基变量，分别加上人工变量x6, x7,约束方程为约束方程为“=”或或“=”的情形的情形（加人工变量） 01 23 2411 2 71731653214321x,xxxxxxxxxxxxx 这时，初始基和

3、初始基可行解很明显。这时，初始基和初始基可行解很明显。X(0)=(0，0，0，11，0，3，1)T不满足原来的约束条件。如何使得可从不满足原来的约束条件。如何使得可从X(0)开始，经迭代逐步得到开始，经迭代逐步得到x6=0，x7=0 的基可行解，的基可行解，从而求得问题的最优解，有两种方法：从而求得问题的最优解，有两种方法： 01 23 2411 2 71731653214321x,xxxxxxxxxxxxx 反之，若加了人工变量的问题解后最优解中仍含人工变量反之，若加了人工变量的问题解后最优解中仍含人工变量为基变量，便说明原问题无可行解。例的单纯形表格为：为基变量，便说明原问题无可行解。例的

4、单纯形表格为： 只要原问题有可行解，随着目标函数向最大化方向的改善只要原问题有可行解，随着目标函数向最大化方向的改善，人工变量一定会逐步换出基，从而得到原问题的基可行解，人工变量一定会逐步换出基，从而得到原问题的基可行解，进而得到基最优解。进而得到基最优解。大大M法法在目标函数中加上惩罚项。在目标函数中加上惩罚项。max =3 3x1- -x2- -x3- -Mx6- -Mx7其中其中M为充分大的正数。为充分大的正数。3- -6M M- -13M- -1 0- -M 0 0 0 x4 10 3 -2 0 1 0 0 -1 -M x6 1 0 1 0 0 -1 1 -2 1 -1 x3 1 -2

5、 0 1 0 0 0 1 1 1 -1+M 0 0- -M 0 -3M+1 0 x4 12 3 0 0 1 -2 -1 x2 1 0 1 0 0 -1 4 -1 x3 1 -2 0 1 0 0 1 0 0 0 -13 x1 4 1 0 0 1/3 -2/3 -1 x2 1 0 1 0 0 -1 -1 x3 9 0 0 1 2/3 -4/3 -2 0 0 0 -1/3 -1/3X X* * = (4= (4，1 1，9 9，0 0，0)0)T T, z, z* * = 2= 2113/2 1 只要原问题有可行解， 该最小化问题的最优目标函数值就只要原问题有可行解， 该最小化问题的最优目标函数值就

6、是是 0，解得的最优解，解得的最优解 x6=0，x7=0，对应原问题一个基可行解。，对应原问题一个基可行解。反之若该问题的最优解目标函数值大于零， 则说明原问题无可反之若该问题的最优解目标函数值大于零， 则说明原问题无可行解。行解。 两阶段法两阶段法第一阶段第一阶段：以：以人工变量之和人工变量之和最小化为目标函数。最小化为目标函数。 min min = = x6+x7 第二阶段第二阶段：以第一阶段的最优解：以第一阶段的最优解(不含人工变量不含人工变量)为初始解，为初始解，以原目标函数为目标函数。以原目标函数为目标函数。例例8 试用两阶段法求解线性规划问题试用两阶段法求解线性规划问题 min z

7、 =- -3 3x1+x2+x3 s.t. 01 23241123211321321x,x,xx xxxxxxx3 解：先在上述线性规划问题的约束方程中加入人工变量，解：先在上述线性规划问题的约束方程中加入人工变量，给出第一阶段的数学模型为：给出第一阶段的数学模型为： min min = = x6+x7 x1- -2 2x2+x3+x4 =11 - -4 4 x1+ x2+2x3 - -x5 + x6 =3 - -2 2x1 + x3 + x7 =1 x1， x7 0 第第一一阶阶段段的的单单纯纯形形表表如如下下： cj 0 0 0 0 0 0 0 1 1 CB XB b x1 x2 x3 x

8、4 x5 x6 x7 0 1 1 x4 x6 x7 11 3 1 1 - -4 - -2 2 - -2 2 1 0 1 2 1 1 0 0 0 0 - -1 1 0 0 1 0 0 0 1 11 3/2 1 6 - -1 - -3 3 0 1 1 0 0 0 0 1 0 x4 x6 x3 1 10 0 1 1 1 1 3 3 0 0 - -2 2 - -2 2 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 - -1 1 0 0 0 0 1 1 0 0 - -1 1 - -2 2 1 1 1 1 0 0 - -1 1 0 0 0 0 1 1 0 0 3 3 0 0 0 0 0

9、0 x4 x2 x3 1 12 2 1 1 1 1 3 3 0 0 - -2 2 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 - -2 2 - -1 1 0 0 2 2 1 1 0 0 - -5 5 - -2 2 0 0 4 4 0 0 0 0 0 1 1 1 第一阶段求得的结果是一阶段求得的结果是 = = 0, 0,最优解是（最优解是（0 0, ,1 1, ,1 1, ,1212, ,0 0, ,0 0, ,0 0）T T 因人工变量因人工变量 x6= x7=0，所以，所以(0,1,1,12,0)T是原线性规划问题的基可行解。是原线性规划问题的基可行解。 第二阶段

10、运算: 约束方程为约束方程为“=”或或“=”的情形的情形（加人工变量） 人工变量法（确定初始可行基）：0, 0,1111222121111111mnnnmmnnmnmnnnnnnxxxxbxxaxabxxaxabxxaxa原约束方程：AX=b加入人工变量：xn+1，xn+m人工变量是虚拟变量，加入原方程中是作为临时基变量，人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原

11、问题无可行解。还有某个非零的人工变量，原问题无可行解。Max Z=2x1+ x 2+ x 3 s.t. 4x1+2x2+ 2x 34 2x1+4x2 20 4x1+8x2+ 2x 316 x1，x2，x 30 用两阶段法求下面线性规划问题的解用两阶段法求下面线性规划问题的解线性规划问题解的讨论线性规划问题解的讨论一、无可行解一、无可行解 max z=2x1+4x2 x1 +x2 10 2x1 +x2 40 x1 ,x2 0 x1x2CBXBbX3 0-1 0 0 0 0 -1 x1 x2 x3 x4 x540 2 1 0 -1 110 1 1 1 0 0cj1040/2x1 x5 0-1 20

12、 0 -1 -2 -1 110 1 1 1 0 0 cj-zj0 -1 -2 -1 0cj-zj2 1 0 -1 0 Z0=-40Z1=-20两阶段法两阶段法例例: max z=3x1+4x2 x1 +x2 40 2x1+x2 60 x1-x2 =0 x1 ,x2 0 x1x2 0 x3 40 1 1 1 0 0 0 x4 60 2 1 0 1 -1 -M x5 0 1 -1 0 0 1 0 x3 40 0 2 1 0 0 x4 60 0 3 0 1 3 x1 0 1 -1 0 0 3+M 4-M 0 0 0 zj- cj 0 0 0 -7/3 zj- cj 0 x3 0 0 0 1 -1/3

13、 4 x2 20 0 1 0 1/3 3 x1 20 1 0 0 1/3 cj 3 4 0 0 -M CB XB b x5 x1 x2 x3 x4 0 7 0 0 zj- cj 0 0 -3.5 0 zj- cj 4 x2 20 0 1 1/2 0 0 x4 0 0 0 -3/2 1 3 x1 20 1 0 1/2 0 三、三、 有无穷多最优解的情况有无穷多最优解的情况 最优解中有最优解中有非基变量的检验数等于零非基变量的检验数等于零的的情况。以这种非基变量作为换入变量，迭代可情况。以这种非基变量作为换入变量，迭代可求得另一基最优解。求得另一基最优解。 任一最优解可表示为所有基最优解的凸任一最

14、优解可表示为所有基最优解的凸组合组合。 例例 max z=3x1+5x2 3x1 +5x2 15 2x1 + x2 5 2x1+2x2 11 x1 ,x2 0。CBXBbx3 000 3 5 0 0 0 x1 x2 x3 x4 x5 5 2 1 0 1 015 3 5 1 0 035 11/2x2 x4x5 5003 3/5 1 1/5 0 02 7/5 0 -1/5 1 0 5 4/5 0 -2/5 0 1 cj-zj 0 0 -1 0 0cj-zj3 5 0 0 0 Z0=011 2 2 0 0 1Z1=15x1x2四、无（有）界解四、无（有）界解 max z=x1+x2 -2x1+x2

15、4 x1- x2 2 -3x1+x2 3 x1 ,x2 0练习：写出单纯形表练习：写出单纯形表,分析检验数分析检验数 与系数关系并画图验证。与系数关系并画图验证。 线性规划解除有线性规划解除有唯一最优解唯一最优解的情况外，还的情况外，还有如下几种情况有如下几种情况人工人工变量变量不能不能从基从基底中底中换出换出基可行基可行解中非解中非零元素零元素个数小个数小于基变于基变量数量数检验数检验数中零的中零的个数多个数多于基变于基变量的个量的个数数检验数大检验数大于零，但于零，但对应列元对应列元素小于等素小于等于零，无于零，无换出变量换出变量单单纯纯形形法法小小结结 根根据据实实际际问问题题给给出出数

16、数学学模模型型,列列出出初初始始单单纯纯形形表表,进进行行标标准准化化,见见表表 变变量量 x xj j0 0 x xj j0 0 x xj j无无约约束束 不不需需要要处处理理 令令xj=-xj; xj0 令令xj=xj-xj; ;xj, ,xj0 约约束束条条件件 b0 b 0 计 算计 算i i=bi/aik令令l=min=mini i 第第l l个基变量个基变量为换出变为换出变量，量，alk为主元素为主元素 迭代运算迭代运算.用非基变量用非基变量xk替换换出变量替换换出变量 .对主元素行对主元素行(第第l行行) 令令 bl/alkbl;alj/alkajl对主元素列对主元素列(第第k列列)令令1aalklk;0;0其它元其它元素表中其它行列元素素表中其它行列元素令令 aij-ali/alkaikaaijij b bi i-b-bl l/a/alklka aikikbbi i j- alj/alk k j否对目标函数求极大值标准型线性规划对目标函数求极大值标准型线性规划问题，单纯形法计算步骤的框图：问题，单纯形法计算步骤的框图：