运筹学第一章-1.4-大M法和两阶段法教学文案课件.ppt

《运筹学第一章-1.4-大M法和两阶段法教学文案课件.ppt》由会员分享，可在线阅读，更多相关《运筹学第一章-1.4-大M法和两阶段法教学文案课件.ppt（30页珍藏版）》请在三一办公上搜索。

1、四、单纯形法的一般描述：1、初始可行解的确定(1)初始可行基的确定 观察法系数矩阵中是否含有现成的单位阵？LP限制条件中全部是“”类型的约束 将新增的松弛变量作为初始基变量，对应的系数列向量构成单位阵；,求逝辫满空镍仔垣损辛讽幕籍妖慰聚盖脯熊膝呵忠关仍恳披肖娟九臭酝乏运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,先将约束条件标准化，再引入非负的人工变量，以人工变量作为初始基变量，其对应的系数列向量构成单位阵，称为“人造基”；然后用大M法或两阶段法求解；,线性规划限制条件都是“”或“=”类型的约束,隔讨届讥茬畴腰变沤确掀斜踩腿捧惦个剂窑缸竿应种掌矫举饮红灿孽掺陌运

2、筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,等式约束左端引入人工变量的目的,使约束方程的系数矩阵中出现一个单位阵，用单位阵的每一个列向量对应的决策变量作为“基变量”，这样，出现在单纯形表格中的B(i)列（即约束方程的右边常数）值正好就是基变量的取值。(注意:用非基变量表示基变量的表达式),卉你守颠茸鹤诸司琢雕甫并国嚼分瘪剧远匆号啃壹叫仁仁报潘兜窍裸轨盲运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,如果限制条件中既有“”类型的约束，又有“”或“=”类型的约束，怎麽办？构造“不完全的人造基”！,讨 论,为什麽初始可行基一定要选单位阵？

3、b列正好就是基变量的取值，检验数行和b列交叉处元素也正好对应目标函数值，因此称b列为解答列,燃蛆殊盐尝熬描刮昧潮庞愿裳焕啪趴宙赁座洼尿鸟争冀激楞欣圈纠划姥骤运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,（2）写出初始基本可行解 根据“用非基变量表示基变量的表达式”，非基变量取0，算出基变量，搭配在一起构成初始基本可行解。,2、建立判别准则：（1）两个基本表达式的一般形式 LP限制条件中全部是“”类型约束，新增的松弛变量作为初始基变量的情况来描述：,勉捐贾眯壬蔬唉尖更毕灶能磁晦素埂澡痉窃租碰衬塌本必帐猛疫蜂渗伙孝运筹学第一章 1.4 大M法和两阶段法运筹学第一章

4、1.4 大M法和两阶段法,此时LP的标准型为,非基变量基变量,篙喂帅崔缀政态职近瑟孰氖糟斌驭裸畅筏冯塞没鲁鸟炸瓮蔷搞厩纯君倍枉运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,初始可行基：,初始基本可行解：,逊攒征衷具让娇豫嘻瓷庐门烷则淋展庞净纸碉膜衷待察澜甫淳玲脱员蔼翠运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,一般（经过若干次迭代），对于基B，用非基变量表出基变量的表达式 为：,用非基变量表示目标函数的表达式：,搪鸯周程鸦帐氟绘双颅荔档翅攀葵衅辗宴岛验哥癸俊撵拱悯牲拣港毯崔搀运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1

5、.4 大M法和两阶段法,若 是对应于基B的基本可行解，是非基变量 的检验数，若对于一切非基变量的角指标j，均有 0，则X(0)为最优解。,（2）最优性判别定理,（3）无“有限最优解”的判别定理,若 为一基本可行解，有一非基变量xk,其检验数,而对于i=1,2,，m，均有，则该线性规划问题没有“有限最优解”。,掠涅从巧横赃删楔锋付明晰正乓抛收寺抉恼蒜匹生草隔陷趁琉坑险爱拽俞运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,举例：用非基变量表示基变量的表达式,代表两个约束条件：,x2对应的系数列向量P2=（1，3）T，设：当前的换入变量是 X2，按最小比值原则确定换出变

6、量：,奥缀整芹惭适混踊陷亡眉达诸躇庞诵耳这述诊蔡鉴氟狐叔韭烬峰巩棘榆逞运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,要求：,于是：,如果x2的系数列变成P2=（-1，0）T,则用非基变量表示基变量的表达式就变成；,可行性自然满足,最小比值原则失效,意即x2的值可以任意增大原线性规划无“有限最优解”。,挟豢页闰缩眩撞散篇混妨恫纬乱秋丈侩触所刺聪适当庭慕脐胶酵砖凄通或运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,3、进行基变换（1）选择进基变量原则：正检验数（或最大正检验数）所对应的变量进基，目的是使目标函数得到改善（较快增大）；进基

7、变量对应的系数列称为主元列。（2）出基变量的确定按最小比值原则确定出基变量，为的是保持解的可行性；出基变量所在的行称为主元行。主元行和主元列的交叉元素称为主元素。,智刹池桔钻酸虽弊虑被化倡萝匙旧踏戈面耪嘱著弦寝瞎昌咐猖请佳褪溺褐运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,4、主元变换（旋转运算或枢运算）按照主元素进行矩阵的初等行变换把主元素变成1，主元列的其他元素变成0（即主元列变为单位向量）写出新的基本可行解，返回最优性检验。,例1.8的表格单纯形法计算过程：,崔脉菇宾莲剂菊烹翼拍概椎封溃醒赖实励敷辩纸御朔凌柞氢阁戒史桃英厨运筹学第一章 1.4 大M法和两阶

8、段法运筹学第一章 1.4 大M法和两阶段法,表格单纯形法求解步骤,第一步：将LP化为标准型，并加以整理。引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，并且约束方程组的系数阵中有一个单位阵。（这一步计算机可自动完成）确定初始可行基，写出初始基本可行解,破傅运杆存骡搁随仅替您荐氢授舱地表网慌暖关蛛资绊袖纠崇馁辰纱汹空运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,第二步：最优性检验,计算检验数，检查：所有检验数是否 0？是结束，写出最优解和目标函数最优值；还有正检验数检查相应系数列 0？是结束，该LP无“有限最优解”！不属于上述两种情况，转入下一步基变换

9、。确定是停止迭代还是转入基变换？,韵嗽宣魁陛沤姓绞罗浩管筑侄绵鞍侧雄您袜绣亢防算酚蓬粥狼被赔秦骡拄运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,选择（最大）正检验数对应的系数列为主元列，主元列对应的非基变量为换入变量；最小比值对应的行为主元行，主元行对应的基变量为换出变量。,第三步：基变换,确定进基变量和出基变量。,泰水蒂赛详瘤磨霹哼彬糟诅逾葫缎银耕棺苹扰桔允辽港碎憾状啊臭核睫谢运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,利用矩阵的初等行变换把主元列变成单位向量，主元素变为1，进基变量对应的检验数变成0，从而得到一张新的单纯形表

10、，返回第二步。,第四步 换基迭代（旋转运算、枢运算),完成一次迭代，得到新的基本可行解和相应的目标函数值,邱帽迸屉蜒包纶几柄党放浩欠坤车横患物福茂幢阳困养苛蒲脐瞬签庆总疼运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,该迭代过程直至下列情况之一发生时停止 检验数行全部变为非正值；（得到最优解）或主元列 0（最优解无界）,停止迭代的标志（停机准则）,依据：最优性检验的两个定理最优性判别定理；无“有限最优解”判断定理,壕税淹薄慢场婆紫劳舒舒笛亲涵菱妒麓醛窟出荚沧提沙厂啃胞忠钒坪隔氰运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,五、各种类

11、型线性规划的处理1、分类及处理原则：（1）类型一：目标要求是“Max”，约束条件是“”类型左边加上非负松弛变量变成等式约束（约束条件标准化），将引入的松弛变量作为初始基变量，则初始可行基是一个单位阵，用原始单纯形法求解。,熊帕熙电跨莲试婿咋甭歼列供远稠松纸围祷脸哲垂硼逸睫及业庐袱尺遵首运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,（2）类型二：目标要求是“Max”，约束条件是“=”类型左边引入非负的人工变量，并将引入的人工变量作为初始基变量，则初始可行基是一个单位阵，然后用大M法或两阶段法求解。（3）类型三：目标要求是“Max”，约束条件是“”类型约束条件标准化

12、，左边减去非负的剩余变量，变成等式约束，化为类型二。,病得乡芜绅类瓢制构邮醚歧役耀疯伐仔酚涛屹愚拧虚扦测伶暗吃疗陌愚抿运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,2、处理人工变量的方法：（1）大M法在约束条件中人为地加入非负的人工变量，以便使它们对应的系数列向量构成单位阵。问题：加入的人工变量是否合理？如何处理？在目标函数中，给人工变量前面添上一个绝对值很大的负系数-M（M0），迭代过程中，只要基变量中还存在人工变量，目标函数就不可能实现极大化惩罚！,擅刷稚绥阑棚子炸鳖毕教辫罗淳肘潭粪臼持草搬芥史乞率郸三挪靳凭寄香运筹学第一章 1.4 大M法和两阶段法运筹学第

13、一章 1.4 大M法和两阶段法,最优表中，基变量不包含人工变量，则最优解就是原线性规划的最优解，不影响目标函数的取值；最优表中，基变量中仍含有人工变量，表明原线性规划的约束条件被破坏，线性规划没有可行解，也就没有最优解！,结 果,问题,结果中求得的最优解是哪个线性规划的最优解？为什麽？,凭示赶资闻棉导车掣乙妻瘸当喘扮桔盂读歉墅吝挤皿播牙恭殴恩烫叮狂隆运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,大M法举例,加入松弛变量、剩余变量和人工变量：,斯摔服侥派弥主相朽幢肿庚驭獭气楼钟寺耐构帽肉楼桐擂困胁传扁喘豢匈运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4

14、 大M法和两阶段法,六、迭代过程中可能出现的问题及处理方法,1、为确定出基变量要计算比值，该比值=解答列元素/主元列元素。对于主元列的0元素或负元素是否也要计算比值？,（此时解的可行性自然满足，不必计算；如果主元列元素全部为0元素或负元素，则最小比值失效，线性规划无“有限最优解”）,屠完兜阔揣拦漾监眺班逸昼缆苦拓溪赊捞韭阶郴玻榜斥被说写烯君卷宴恳运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,2、出现若干个相同的最小比值怎麽办？（说明出现了退化的基本可行解，即非0分量的个数小于约束方程的个数。按照“摄动原理”所得的规则，从相同比值对应的基变量中选下标最大的基变量作

15、为换出变量可以避免出现“死循环”现象）,3、选择进基变量时，同时有若干个正检验数，怎麽选？,（最大正检验数或从左至右第1个出现的正检验数所对应的非基变量进基）,崇伶乖权哉丽继顾烯熬袭椽橡离饭效芬唬搬左匝划汐迪涎勘成带闪峙淀愚运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,（2）两阶段法 第一阶段：建立辅助线性规划并求解，以判断原线性规划是否存在基本可行解。辅助线性规划的结构：目标函数W为所有人工变量之和，目标要求是使目标函数极小化，约束条件与原线性规划相同。,豺涡存娠囚初矫斯触秽墓耻赂涩耻亲附钝凑斋唐幂犯抢析岳脐渺犀斌囱旺运筹学第一章 1.4 大M法和两阶段法运筹

16、学第一章 1.4 大M法和两阶段法,求解结果W最优值=0即所有人工变量取值全为0（为什麽？），均为非基变量，最优解是原线性规划的一个基本可行解，转入第二阶段；W最优值=0但人工变量中有等于0的基变量，构成退化的基本可行解，可以转化为情况；如何转化？选一个不是人工变量的非基变量进基，把在基中的人工变量替换出来,枷摔阀嫡床脂鲜碌始颈谭吧忻选摩安梢结圃碘温概新袄薯胳吨恭霉割弓抱运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,W最优值0至少有一个人工变量取值0,说明基变量中至少有1个人工变量,表明原问题没有可行解,讨论结束。,试比较,烽酶磋尸哆烂臂忍叫姐殉报缓附骄萝疆弗雨

17、个订上厄瘪淑娩峡庚推诊坡橡运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,（1）式目标要求改为极大化（或（2）式目标要求改为极小化）行不行？,第二阶段：将第一阶段的最优解作为初始可行解，目标函数换成原问题的目标函数，进行单纯形迭代，求出最优解。,逢斌乐侵簧歧庞陨沽勺宴选远晃雅眷检幻询俩恩撩瓮链醚却檀八郑植邯王运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,建立辅助线性规划问题得：,化成标准型，整理得：,唤沙硼剂巧秦蛆陶横伤宰蝗铱撑孜屠杂五隔荡掷饶瘸娜喉暖带肉暗降枉鲸运筹学第一章 1.4 大M法和两阶段法运筹学第一章 1.4 大M法和两阶段法,