第3章(单纯形法的运用与改进).ppt

3单纯形法的运用与改进初始可行基与人工变量法求上界变量的单纯形法单纯形法的讨论单纯形法的矩阵描述改进单纯形法五平祖篮七鲜完骡缝众卢椒庐帛懂秆雇惊骇戌橱魂妹傍用兄醉枯谰佯坦瓷第3章(单纯形法的运用与改进)运筹学2003-6\*3-13单纯形法的运用与改进矿山系统工程教程\*(单纯形法的运用与改进)(A)maxz=3x1-x2--2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1,x2,…,x5≥0X0=(0,1,1,12,0)TX'=(x1',x2‘,…,x5')T'=0(B)max=-x6--2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1x1,x2,…,x7≥0Y0=(0,1,1,12,0,0,0)T0=0Y'=(x1',x2',…,x5',x6',x7')T船酱琅巩喇耘铅撅录移钵殃铁扼臂溺遮莆还螺争乖员靳缀疤丝衰辉乃嘎撮第3章(单纯形法的运用与改进)(B)是问题(A)的辅助问题,(B)中的单位矩阵称为人工基,其中添加的变量叫做人工变量(artificialvariables)。辅助问题(B)有两个特点:(i)约束方程为典式,表明有可行解;(ii)目标函数有上界,一定有最优解。(B)max=-x6--2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1x1,x2,…,x7≥0B0=(P4,P6,P7)Y0=(0,0,0,11,0,3,1)T0=-4莎聋聂挪训颅鸭已榷渔去槽孕锋巍磷兴澡湍联晚赏艺俘塔妖履敦错猖隧溜第3章(单纯形法的运用与改进)(A)maxz=c1x1+c2x2+…++a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2……am1x1+am2x2+…+amnxn=bmx1,x2,…,xn≥0X0=(x10,x20,…,xn0)TX'=(x1',x2',…,xn')T'=0(B)max=-xn+1-xn+2-…-xn++…+a1nxn+xn+1=b1a21x1+…+a2nxn+xn+2=b2 ……am1x1+…+amnxn+xn+m=bmx1~xn≥0,xn+1~xn+m≥0Y0=(x10,x20,…,xn0,0,…,0)T0=0Y'=(x1',x2',…,xn',xn+1',…,xn+m')T岗凶滔防随迟脯袭仟稳闭谅蔡径钡撬炒烁姥佣钝逮洽霉牌拟赣无匪姆代煌第3章(单纯形法的运用与改进)运筹学Date53单纯形法的运用与改进辅助问题的性质问题(B)是问题(A)的辅助问题,(B)中的单位矩阵称为人工基,它对应的m个变量叫做人工变量(artificialvariables)。辅助问题(B)有两个特点:(i)约束方程为典式,表明有可行解;(ii)目标函数有上界,一定有最优解。(B)max=-xn+1-xn+2-…-xn++…+a1nxn+xn+1=b1a21x1+…+a2nxn+xn+2=b2 ……am1x1+…+amnxn+xn+m=bmx1~xn≥0,xn+1~xn+m≥0B0=(Pm+1,Pm+2,…,Pn)Y(0)=(0,…,0,b1,b2…,bm)T沼潞壕纸溯癸技赛尼验粮俏疾炮责谆咒朴惜蘸舔逗惺胶奔卡召轴正支卫筐第3章(单纯形法的运用与改进)(A)有可行解的充要条件是:问题(B)的目标函数最优值等于零。(B)的最优基的基变量组中不含人工变量,则这个最优基和相应的基最优解分别是问题(A)的可行基和基可行解。弟蘑劣台敢呵率违脂溯唆拐陇阐稗吹桔邀奈孝耸免涣锋怂骸很瞎历破妈舱第3章(单纯形法的运用与改进)运筹学Date73单纯形法的运用与改进原理与应用(续)(B)的最优基的第l个基变量为人工变量,并且目标函数最优值等于零,而最优单纯形表中非人工变量在第l行的系数全为零,则表示问题(A)的第l个约束方程是多余的,应予删除。标准形式线性规划问题的m个约束方程被假设为是相互独立的,上述结论中的情形在理论上不会出现,但在实际中经常碰到。戍屹台肥沃沧晨鼠一栖迈久误庆打哪镁润奇披殆矫拍擒缉赶午胯窍佯媚紧第3章(单纯形法的运用与改进)