0920--第四次课-大M法

Page1第四节大M法(人工变量法)解决初始基本可行解不存在问题Page2基本思想单纯形法是从一个初始基可行解开始的，解决办法:引入人工变量接下来修改目标函数,从而得到新的线性规划模型.最后通过单纯性法求解新LP模型而得到原LP模型的最优解.但以上条件有时是不满足的,即原LP问题的初始基本可行解不易找出或不存在,此时怎么办？①中心部位具有m阶单位子块②右列元素非负首先利用容许的运算使②满足,即使右列元素非负;然后在中心部位人工添加一些单位列向量,使中心部位具有m阶单位子块,也就是使①满足.即要求标准形对应的单纯性表满足：Page3分析:对应表格引例123123123123min32s.t323624(),,0zxxxxxxxxxxxx例：32-36-12-1-4-3120可见,r(A)=2.但①②不满足.Page432-31061-21014-312032-361-214-31202(-1)r使②满足45xx人工变量人工变量人工变量的系数MMPage532-31061-21014-312MM0人工变量人工变量123123123454545123min32s.t323624()+MM+,,,,0zxxxxxxxxxxxxxxxxxx其中M0为足够大的正常数.Page6一.人工变量的处理—大M法11min,1,2,,(4.1)..0,1,2,,njjjnijjijjzcxaxbimstxjn对于线性规划问题引入人工变量mnnnxxx,,,21构造新的线性规划问题111min,1,2,,(4.2)..0,1,2,,,1,,nnmjjjjjnnijjniijjzcxMxaxxbimstxjnnnm其中M0为足够大的数假设r(A)=m,且对应的初始单纯形表②满足,①不满足.那么：Page7min(4.2)..0,0TTzCxMEyAxybstxy12(,,,),Tnnnmyxxx令(1,1,,1)TE*(,0)Tx则反之,若*x是(4.1)的最优解,是(4.2)的最优解.定理4.1**(,)Txy设是(4.2)的最优解.若的最优解；若*0,y*.1x则是(4)则(4.1)没有可行解.*0,y人工变量全是自由变量Page8二、算法（大M法）--已知初始表不满足①②1.大M法的求解步骤3）将目标函数修改为1,mjjzzMy其中M0为足够大的正常数.从而得到新的LP模型.1）经初等行变换(1)ir通常使右列元素非负;2）在中心部位人工地添加一个m阶单位子块,即引入得到新的约束方程组；引入人工变量12,,0,myyy4）用单纯形求解新的LP模型，试图将变成自由变量，最终将出现5)或6)两种情况：12,,myyyPage96）新LP无界(无最优解)，则原LP问题也无最优解.5）设求得新的LP模型的最优解为(,),Txy则12(,,,)0,myyyy若12(,,,)nxxxx则原LP问题无最优解.12(,,,)0,myyyy若说明：在上面5)中提到的0y的情况属于下面情形：用单纯形法求解新LP得到的新表格满足①②③④，但人工变量并没有完全成为自由变量。此时说明原LP问题是无可行解，因此原LP无最优解.是原LP问题的最优解.Page10解:该LP已是标准形，画出对应表格：2.例题解析123123123123min32s.t323624(),,0wxxxxxxxxxxxx例：32-36-12-1-4-3120可见,r(A)=2.但①②不满足.Page11故用大M法使①②满足32-31061-21014-312MM0人工变量人工变量123123123454545123min32s.t323624()+MM+,,,,0zxxxxxxxxxxxxxxxxxx下面用单纯形法求解这个新LP问题.Page1232-31061-21014-312MM032-31061-21014-3-4M12+2M00-10M满足①②但③不满足满足①②③但④不满足Page1312/3-11/3020-8/32-1/31203+8M/3-1-2M1+4M/306-2M满足①②③但④不满足12/301/61/230-4/31-1/31/2105/30M+5/61/2+M7满足①②③④Page1412/301/61/230-4/31-1/31/2105/30M+5/61/2+M7满足①②③④故新LP问题(II)的最优解为：(3,0,1,0,0)TX故原LP(I)的最优解为：(3,0,1)Tx对应的最优值为：min7.z45xx，注意到人工变量均为0，Page153）若新的LP问题无界（无最优解），那么原LP问题也无最优解.1）若原LP标准形对应表格的中心部位已有(0)llm个不同的单位列向量，则只需添加()ml列向量，使中心部位出现m阶单位矩阵就可以了。个单位即此时只需引入()ml人工变量，减小了计算量。2）在迭代过程中，人工变量一旦离开基变量位置成为自由变量，不会再成为基变量.因此，它的任务就完成了，这一列便可删去。三.有关大M法的一些说明Page164）大M法实质上也是单纯型法(M可看成一个很大的常数)，只不过是在单纯形法的基础上作小的改动得到的.因为有了单纯形算法做基础，因此程序实现比较简单。-----优点.5）缺点：在程序实现时，M究竟应取多大，事先无法预计。若M过大，会导致计算误差大.Page17123412341231231234min23s.t2102520()2315,,,0wxxxxxxxxxxxxxxxxxx例：例2（教材P57，例4.1）Page18解:该LP已是标准形，画出对应表格：易验证,r(A)=3.但特点①不满足，121115123020215010-1-2-310故需要用大M法构造新表格。Page19121100151230102021500110-1-2-31MM0人工变量人工变量123412341231256565631234min23s.t2102315()2520,,,0),(,zxxMxxxxxxxxxxxxxxxxxxxxxx其中M0为足够大的正常数.Page20下面用单纯性法求解该新LP问题121100101230101521500120-1-2-31MM0满足①②但③不满足121100101230101521500120-2-3M-4-3M-4-8M0000满足①②③但④不满足Page21满足①②③但④不满足3/59/5010-1/56-1/57/5001-3/532/51/51001/54(M-2)/2-(7M+6)/5000(8M+4)/5-3M+6121100101230101521500120-2-3M-4-3M-4-8M0000Page221007/6-3/22/35/20101/61/2-1/35/2001-1/21/205/20004M+1M156/7001-9/74/715/7-1/71005/7-3/715/73/7010-1/72/725/7-6/7000(7M+16)/7(7M-4)/790/7④不满足满足①②③④Page23故新LP问题(II)的最优解为：(5/2,5/2,5/2,0,0,0)TX注意到人工变量均为0，(5/2,5/2,5/2,0),Tx最优值为：min15.w1007/6-3/22/35/20101/61/2-1/35/2001-1/21/205/20004M+1M15满足①②③④故原LP问题(I)的最优解为：Page24*(,0)Tx则反之,若*x是(4.1)的最优解,是(4.2)的最优解.定理4.1**(,)Txy设是(4.2)的最优解.若的最优解；若*0,y*.1x则是(4)则(4.1)没有可行解.*0,y四.定理4.1及详细证明min(4.2)..0,0TTzCxMEyAxybstxymin(4.1)..0TzCxAxbstxPage25证明：TzCx是(4.2)的可行解，且对应的函数值为则(,0)Tx则有TzCx综上可知，x是原LP（4.1）的最优解。设x是原LP（4.1）的任一可行解，(,)(0)Txyy由于是(4.2)的最优解（最小点）,zTCx因(,)(0)Txyy是(4.2)的最优解，也是可行解,是（4.1）的可行解。x故下面证对应的目标函数值还是最小的。x若的最优解；*0,y*.1x则是(4)(i)**(,)Txy设是(4.2)的最优解.Page26反证法：是(4.2)的可行解，则(,0)Tx(,)(0)Txyy而(4.2)的最优解对应的目标函数值为1+mTjjzCxMy可见当M足够大时，显然这与(,)Txy是(4.2)的最优解（最小点）矛盾。即(4.1)无可行解得证。若则（4.1）无可行解。*0,y(ii),x假设这种情况下(4.1)有可行解TzCx且对应的函数值为,zz必有：因此假设有误，Page27分情况讨论：(1)若0,y由于M0可以充分大，综上知，(,0)Tx是(4.2)的最优解，(iii)TTTCxCxMEy所以必有*(,0)Tx则若*x是(4.1)的最优解,是(4.2)的最优解.(,)Txy设是（4.2）的任一可行解，下面证对应的函数值比它对应的函数值小。(,0)Tx则x是（4.1）的一个可行解，于是TzCxTCx可见(,0)Tx对应的函数值比(,)Txy对应的小.(2)若0,y此时(,0)Tx对应的函数值比(,)Txy对应的仍小.最优值为.TzCx*(,0)Tx是(4.2)的一个可行解显然；证明：Page28