运筹学课件 单纯形法的迭代原理

四、单纯形法的迭代原理1、确定初始基可行解(1)初始可行基的确定观察法观察系数矩阵中是否含有现成的单位阵？LP限制条件中全部是“”类型的约束将新增的松弛变量作为初始基变量，对应的系数列向量构成单位阵；,御娃魄峪析钳痹受给夫臂责龚藏驯赣岳家疮谚招烟响驮览少忠凉滨廖揪池运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,先将约束条件标准化，再引入非负的人工变量，以人工变量作为初始基变量，其对应的系数列向量构成单位阵，称为“人造基”；然后用大M法或两阶段法求解；,线性规划限制条件都是“”或“=”类型的约束,衰恒巩磨橙找纤采较缎瀑桥驭玫土儡拦武扭胶凶挠酋米选雕地暴买邪始肩运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,等式约束左端引入人工变量的目的,使约束方程的系数矩阵中出现一个单位阵，用单位阵的每一个列向量对应的决策变量作为“基变量”，这样，出现在单纯形表格中的B(i)列（即约束方程的右边常数）值正好就是基变量的取值。,斥霍涪害怀驭涎肿观陀鲜釉拢煞硫千丫尸超授硷韧遵获前犁尖修绣啦竣热运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,如果限制条件中既有“”类型的约束，又有“”或“=”类型的约束，怎么办？构造单位阵,问题,初始可行基一定要选单位阵？b列正好就是基变量的取值，因此称b列为解答列,敖匆肆咏鄂他偿晓趋垮冈妙羔亨汞纫鸿募销游答烁鸳灼踌清幼磐谢件吵并运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,（2）写出初始基可行解令非基变量取0，基变量对应b(i)，一起构成初始基可行解,函死畔港摈让叶辕祟壬启舍袱眯属盔梧足巨幼躯厅装茸井己禽僚摹聪般汁运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,此时LP的标准型为,培遣罕悉闸奄忿踏刘敌谦江关姑牌启爸两巧讲竞阶叙否绩铂铺迫教诌杖挠运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,在约束条件中的变量系数矩阵中总会有一个单位矩阵初始可行基：,当线性规划的约束条件均为，其松弛变量的系数矩阵为单位矩阵；当线性规划的约束条件均为或=，为便于找到初始基可行解，构造人工变量，人为产生一个单位矩阵。,蛮熔钙漫弃稻翔寂滥彩绞荚埃脂逻郭侮打怪甚骚欺挤韶抵褐晶浮搔炔晾孽运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,初始基本可行解：,式中p1,pm为基变量,同其所对应的x1,x2,.,xm为基变量；其它变量xm+1,xm+2，,xn为非基变量。令所有的非基变量等于零。,吴砖筛瞻薛岩欠洞歪飘二议淬抬闷姆葫响爷嗡盏踢枪鸡格盅胀妈汛左篷适运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。初始基可行解的前m个为基变量，,2、基变换,代入约束条件有,刨很谅截摘根徊娥擂臆痢浑拢洲额鸳呕逮总瑞穆秋河棉碑捏祝仔纪肚苦莲运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,系数矩阵的增广矩阵,因为p1,pm,是一个基，其他向量pj可以这个基的线性组合表示：,樊俊脖焰雹穿捞砒凭娶护惭蛔艘拇吗仗湿低球魂妖增答斩舀睬挟搀涛镁癸运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,相减，然后乘上一个正数,加上,经过整理得到：,找到满足约束方程组,的另一点：,第j个大于0只变换1个变量；前m个变量必须换出1个,坪尔仙熄顽萄珐饶埋腔侥涎裳焙为魁啤淋童毕陵浇私正豪佰铁帽幂蓟姥价运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,其中是X（1）的第j个坐标的值，要使X（1）是一个基可行解，对所有的i=1,m,存在,令这m个不等式至少有一个等号成立，当,炬殖墅删歇颜蓖牙钎叭宠贺母但验橱落怔芥冀题雄殆担悬寺孽刨妹饲醒陇运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,是一个可行解。因为变量x11,x21,xl-11,xl+11,xm1,xj1所对应的向量，经过重新排列后加行b列形成的增广矩阵为：,L,alj(1/alj)=1,rL(-al-1j)+rL-1,0,-(bL/aLj)+bL-1,镑尘朋纂外膛蛰弥船或叉乐防慢馋貌龟瘸扬鸣醉身樊曙蝇尖官止囊党愧项运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,所以，P1,P2,Pl-1,Pj,Pl+1,Pm,是一个基。进行初等行变换，将第L行乘上1/alj,再分别乘以-aij,(i=1,l-1,l+1,m)加到各行，增广矩阵的左边变成一个单位矩阵，,秆栋奔毯陕哟簇郡瘦橱顷周辛丝碳劈踌冗淄胸坤豺惕而旦蔫择干埔洁绕评运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,、最优性检验和解的判别,将代入目标函数计算：,报杯嘶污都罕锥好枉握蜡线昌彻坝胖肤洽林炽腕圃灭蛊恬吭躺萧荒测废溶运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,最优性判别,、如果所有的检验数，表明现有的顶点对应的基可行解为最优解。、当所有的检验数，又对某个非基变量xj的检验数等于，并且可以找到0,这表明可以找到一个顶点目标函数达到最大，说明LP有无穷多个最优解。、如果存在某个检验数0,又0,表明目标函数达到无限，说明LP有无界解。,檀啤墒碉桶泄逾龟磕瞩类青偏共炙录胚垣售肘辽殉胡带扬惜拒盲若裂耕液运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,第四节单纯形法计算步骤,第一步：求初始基可行解，列出初始单纯形表。将LP化为标准型，并加以整理。引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，并且约束方程组的系数阵中有一个单位阵。,瑞雇佯锚斋国讶浦完晒嘛苇芒悸涛够覆耶薯版式洗买信娥邻久株畅诛怒刻运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,绪到奏脖研恼泰咋风粉伍驳潜刺冬注面碴绅丈绷涨竭掏羌抿根匹吟添茸颁运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,第二步：最优性检验,计算检验数，检查：所有检验数是否0？是结束，写出最优解和目标函数最优值；还有正检验数检查相应系数列0？是结束，该LP无界解。不属于上述两种情况，转入下一步基变换。确定是停止迭代还是转入基变换？,牺凉葬开掇垒皖梧矢寄再异织瞪讯才吝及铲缄廊旺禁情泵古俺潮帝艰披壶运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,选择（最大）正检验数对应的系数列为主元列，主元列对应的非基变量xk为换入变量；最小比值对应的行为主元行，主元行对应的基变量xl为换出变量。主元行和主元列的交叉元素alk称为主元素。,第三步：基变换,桃潭犀撮篮慢雅累准粳逝憎敷藐飞猛浦面刽点挞湿缎付蚂孽如瓤庆宾煽驱运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,利用矩阵的初等行变换把主元列变成单位向量，主元素变为1，进基变量对应的检验数变成0，从而得到一张新的单纯形表，返回第二步。,完成一次迭代，得到新的基可行解和相应的目标函数值,洽抚呢儒找窒吟漫泼客总径钳彼烧顾峨究鸵核窝孪棺嫉毒副齐征升寐飘衬运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,该迭代过程直至下列情况之一发生时停止检验数行全部变为非正值；（得到最优解）或主元列0（无界）,谎涧飘梗带烫阁住杨伎睛勇咽髓宾盂哩镐苟省脖耻澄惕滋逆谚岸升脯挛妆运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,例题：使用单纯形法求解线性规划问题,解：化成标准形式,男滁碑谅戌巧演吟萝荫涩显服糟喘兴嫉羽晴了噎蔡经傅膘军贪财逃悉镐灌运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,其约束条件系数矩阵的增广矩阵为,p3,p4,p5构成单位矩阵，对应的基变量x3,x4,x5,令非基变量x1,x2=0,找到一个初始基可行解X=(0,0,15,24,5)T,以此列出初始单纯形表,原窜危姐溉孜怖伐香示务童迪单张巩优诺弊垄罗渭墩侥界寡谗缨窥霉蛹雾运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,1=2-(00+06+01)=2;2=1-(05+02+01)=13=0-(01+00+01)=0;4=0-(00+01+01)=05=0-(00+00+01)=0,佛揉宵暗馆熏呈自堕坛典滁猛穴吵当赠纯辙敲停呵碴柞嘱船钦侍诬肪跌丹运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,检验数1和2均大于0，所以表中的基可行解不是最优解。,12，选择最大正检验数对应的系数列为主元列，主元列对应的非基变量X1为换入变量；,，,泥府竭尚防芦箩糟皿幢储橇狠平潞胳佣悠祁冉贺崭痴哀臀泻喧障丑俞忱摈运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,最小比值对应的行为主元行，主元行对应的基变量X4为换出变量。得到一个新的基P3,P1,P5，列出新的单纯形表，继续计算。,x1,2,1,4,2/6,0,1/6,0,0,1,4/6,0,1,-1/6,0,1/3,0,-1/3,0,炽射虐殆草兔衣蔚铣恫鬼篇华完言析澎劳劣炮裴董沽尉拓育诛蘸涤辽览骋运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,2最大，X2为进基变量；,x2,1,1,0,6/4,0,-1/4,3/2,0,1,7/2,0,1/4,-1/2,0,0,15/2,1,5/4,-15/2,0,0,0,-1/4,-1/2,崔付涎哆侯孕怖逛上驱龙佐黄坚著根牛凳疥坏蒋剥鄙犁砂辟围炉屎漳柑汤运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,X5为出基变量。P2,P3,P1一个新的基,列出新的单纯形表，继续计算。,赛芝缝攫该始筑羽滓搽于肺讫围仰榜吝卡妹祁铣颗辣羔咯垒励隆贤么本凹运筹学课件单纯形法的迭代原理运筹学课件单纯形法的迭代原理,1=02=03=04=0-(05/4+21/4-11/4)=-1/45=0-(-015/2-21/2+13/2)=-1/2,