管理运筹学课件02单纯形法

《管理运筹学课件02单纯形法》由会员分享，可在线阅读，更多相关《管理运筹学课件02单纯形法（34页珍藏版）》请在金锄头文库上搜索。

1、 第二章第二章 单纯形法单纯形法Simplex MethodSM疼今帧逮褪仆样傅品素璃冠苗蔫洁尸顿狡描插熄彝嚣椿亮荔秦妮挎敬妹师管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法2.1 单纯形法的基本思想单纯形法的基本思想2.2 单纯形法的计算过程单纯形法的计算过程2.3 人工变量法人工变量法2.4 单纯形法补遗单纯形法补遗第第2章章 单纯形法单纯形法鲜挤褥晚尔新疯言啥浸弘胖翅卒框股另死审售荣疼席螺皂乒鞭淆枣而悬澜管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法2第2章 单纯形法2.1 单纯形法的基本思想单纯形法的基本思想 单纯形法有三种形式：单纯形法有三种形式： 方程组形式方程

2、组形式 表格形式表格形式 矩阵形式矩阵形式2.1.1 方程组形式的单纯形法方程组形式的单纯形法思路思路思路思路：由一个基本可行解转化为另一个基本可行解。由一个基本可行解转化为另一个基本可行解。s.t. x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 = 36 x1 ， x2 ，x3，x4，x5 0 max z = 3x1+5x2z - -3x1 - -5x2 = 0例例1 范例范例等价改写为等价改写为s.t. z -3x1 -5x2 = 0 x1 +x3 = 8 2x2 +x4 = 12 3x1+4x2 +x5 = 36 x1 ， x2 ，x3，x4，x5 0 ma

3、x z目标方程目标方程兔漳蚕澡沏窟出哮孤易畸块般刘替休菲尤恭乔造炭画轧侄怂答伴织韭并鳖管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法3第2章 单纯形法2.1 单纯形法的基本思想单纯形法的基本思想1 0 00 1 00 0 1典式典式典式典式 条条条条 典典典典 当前基：当前基：m阶阶排列阵排列阵 目标方程目标方程中：一切基变量中：一切基变量 的系数的系数 j = 0Z - -3x1 - -5x2 = 0 0 x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 = 36 ()0最优性检验：最优性检验：一切一切一切一切 j 0 ？初始基本可行解初始基本可行解 X0

4、 = (0, 0, 8, 12, 36)T z0 =0 0 排列阵排列阵： 每行每列有且仅有一个元素每行每列有且仅有一个元素为为1 1 1 1，其余元素全为，其余元素全为0 0 0 0 的方阵。的方阵。 1 = - -3 0 2 = - -5 0当前解当前解 X0 非优；非优；+0x3+0x4+0x5须由须由X0 转化为另一个基本可行解转化为另一个基本可行解 X1。满足满足条典条典条典条典的的方程组方程组称为称为典式典式典式典式(方程组方程组方程组方程组)。思路思路思路思路：让：让X0 中的一个中的一个非基变量非基变量进基进基，去替换原来的一个，去替换原来的一个基变量基变量基变量基变量（离基离

5、基）。）。渔冕奥税鲜氏骇敏惺障泵睦楷璃痰爵误猎傻字庞枢堆啮释期吃涎腐减咱抡管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法4第2章 单纯形法2.1 单纯形法的基本思想单纯形法的基本思想x1仍为非基变量，其值为仍为非基变量，其值为0。x3 = 8x4 = 12 - -2x2x5 = 36 - -4x2 x2 12/2 x2 36/4w 离基离基离基离基（最小比值规则最小比值规则最小比值规则最小比值规则） ： x2 min ，12/2，36/4 = 6 x2 = min ，12/2，36/4 = 6 6 x4x4为为离基变量离基变量w 进基进基（最小检验数规则最小检验数规则最小检验数规则最

6、小检验数规则）：）： 在在负检验数负检验数负检验数负检验数中选择中选择最小的最小的最小的最小的进基进基。 min j j0 = k xk 进基进基 min - -3，- -5 = - -5= 2 x2 进基进基 0 0 0 0 0 0= = = 1212 X1 = ( 120, 6, 8, 0,)Tz -3x1 -5x2 = 0 0 x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 = 36 ()0由由 有有酬团腮关吕中甜厄扔蓝舒械厨轿渊琐倡桥犀诲果电腔忻笆幻傅恿淄烩辱伺管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法5第2章 单纯形法2.1 单纯形法的基本思

7、想单纯形法的基本思想主方程主方程主方程主方程 0主列主列进基进基主元主元 z - - 3x1 - - 5 x2 = 0x1 +x3 = 8 2 x2 +x4 = 12 3x1 + 4 x2 +x5 = 36 ()- -69比值比值比值比值min离基离基离基离基以以主列主列中中正值元素正值元素正值元素正值元素为为分母分母分母分母，同行，同行右端常数右端常数右端常数右端常数为为分子分子分子分子，求，求比值比值比值比值；按按最小最小最小最小比值比值比值比值规则规则规则规则确定确定主方程主方程主方程主方程和和主元素主元素主元素主元素，以及，以及离基变量离基变量离基变量离基变量。搔霖洪参亨走圈身代锰峡笋

8、阜兰炎赐荤逞叶炊卷丛钩枉椅沁捍瓤恐竣娟舌管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法6第2章 单纯形法X X0 0 = ( 0, 0, 8, 12, 36 )= ( 0, 0, 8, 12, 36 )T T z z0 0 = 0= 0 () x1 +x3 = 8 3x1 - -2x4 +x5 = 12 得得X X1 1 = =z z0 0 = 30= 30称为单纯形法的一次称为单纯形法的一次迭代迭代。z- - 3x1 - -5x2 = 0 x1 +x3 = 8 2x2 +x4 = 12 3x1 +4x2 +x5 = 36 ()20 x2 + x4 = 6 12 z -3x1 + x

9、4 = 30052( ( 12120, 0,6, 6,8, 8,0, 0,) )T T换基运算换基运算换基运算换基运算方程组方程组方程组方程组的的初等变换初等变换初等变换初等变换目的目的目的目的是把是把主列主列主列主列变为变为单位向量单位向量单位向量单位向量：主元：主元：主元：主元变变为为1，其余变为，其余变为0。用用换基运算换基运算换基运算换基运算将将X0 转化为转化为另一个基本另一个基本可行解可行解 X X1 1。0 00 01 10 02.1 单纯形法的基本思想单纯形法的基本思想蒲鲤脂拄迅滁腑散孟亮笆辅堕祷雪邑渡走硝宙尼孝篡锤彰尿郊虱祭瞬纵辩管理运筹学课件02-单纯形法管理运筹学课件02

10、-单纯形法7第2章 单纯形法2.1 单纯形法的基本思想单纯形法的基本思想() x1 - - x4 + x5 = 4 2 31 3x2 + x4 = 6 12() x1 +x3 = 8 3 x1 - -2x4 + x5 = 12 x2 + x4 = 6 12 z- -3x1 + x4 = 30052 x3 + x4 - - x5 = 4 2 31 3 z + x4 +x5 = 42012得得X X* * = = ( ( ( ( 4,4, 6,6, 4,4, 0,0, 0 0 ) ) ) )T T z*z* = = 42428 8- -4 4min比值比值比值比值10肯嘘而纲赔丫炔忠属疚掐跪勿刻搁

11、宛扫邵锌场跌睫侣沫景莫街放葫本盆块管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法8第2章 单纯形法2.1 单纯形法的基本思想单纯形法的基本思想2.1.2 单纯形法的几何意义单纯形法的几何意义D(0,6)O(0,0)C(4,6)B(8,3)A(8,0)x1x2z = 0脊线脊线( 4, 6, 4, 0, 0 )( 4, 6, 4, 0, 0 )T T( 0, 0, 8, 12, 36 )( 0, 0, 8, 12, 36 )T T( 0, 6, 8, 0, 12 )( 0, 6, 8, 0, 12 )T Tz z 法向法向法向法向或或或或棱线棱线棱线棱线铸视帕汤辛捷守榔几长馆抹痈倔婚履

12、胖涛她牵虏积褂踢跑缀事木沦杉钻保管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法9第2章 单纯形法2.2.1 单纯形表单纯形表范例范例: 基于基于典式典式典式典式标准形标准形标准形标准形cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0比比 值值 1 0 1 0 0x3x4 x5 81236 0 2 0 1 000 0 3 4 0 0 1 0 00 0 0 00 0- - - -3 3- - - -5 5检验行检验行C CB Bb b352.2 单纯形法的计算过程单纯形法的计算过程s.t. x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 =

13、36 x1 ， x2 ，x3，x4，x5 0 max z = 3x1+5x2z z0 0 = C CB Bb b T检验行检验行计算公式计算公式计算公式计算公式 j j = C CB Ba aj j - - - - cj ,Tj=1,2,n硝廖旅诚揉烙联彪珊谗扭贼刚摹碧咸淳油岂瓦粮枫背闽慷诗暗午仔乎药怜管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法10第2章 单纯形法2.2 单纯形法的计算过程单纯形法的计算过程初始单纯形表初始单纯形表的一般形式的一般形式欲椽喻塘师痞接衣赔竭媳瘫逼皑郊避岛澈鳞羡暂融咸著突位媚广壶蚕攒懊管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法11第2章

14、单纯形法2.2 单纯形法的计算过程单纯形法的计算过程 2.2.2 单纯形法的计算步骤单纯形法的计算步骤1 1 把把LP问题化为问题化为标准形标准形标准形标准形。2 2 在系数阵中找出或构造一个在系数阵中找出或构造一个mm阶阶阶阶排列阵排列阵排列阵排列阵作为初始作为初始 可行基，建立可行基，建立初始单纯形表初始单纯形表初始单纯形表初始单纯形表。3 3 最优性检验最优性检验最优性检验最优性检验: 若所有检验数若所有检验数j 0，就得到一个，就得到一个 最优基本解，停止计算；否则转最优基本解，停止计算；否则转4 。4 4 解无界判断解无界判断解无界判断解无界判断: 在所有在所有j 0中中, 只要有一

15、个只要有一个r 0 所对应的系数列向量所对应的系数列向量 ar 0，即一切，即一切 air 0 ， i=1, 2, , m 则该则该LP问题问题解无界解无界解无界解无界，停止计算；否则转，停止计算；否则转5 。预预预预备备备备步步步步骤骤骤骤迭迭迭迭代代代代步步步步骤骤骤骤傍鸳磷睁凿苇譬孔璃溅砰甸逼跋萍毯晒锐契冒今捐泉栋莆诧基逊檄饱粕拒管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法12第2章 单纯形法2.2 单纯形法的计算过程单纯形法的计算过程 5 5 确定主元确定主元确定主元确定主元 先按先按最小检验数规则最小检验数规则最小检验数规则最小检验数规则 min jj 0 =aikbia

16、l kbl迭迭迭迭代代代代步步步步骤骤骤骤拔眉靡坝票锑琅而柜炸跪走烂踩宜泅缅苇锐耍乱韩拱哑转袖煤喇藐蝇沦尸管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法13第2章 单纯形法2.2 单纯形法的计算过程单纯形法的计算过程2 2. .2 2. .3 3 单纯形法计算之例单纯形法计算之例范例范例 第第第第0 0 0 0次迭代次迭代次迭代次迭代cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0比比 值值 1 0 1 0 0x3x4 x5 812 36 0 2 0 1 000 0 3 4 0 0 1 0 - -3 - -5 0 0 0- -6 9min2庆丰散寂恩赦闰霉培凌鼠蓝稼

17、深终起耶纳篆嘻锨胖摄袍价顷饿裸菌劲肯磊管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法14第2章 单纯形法2.2 单纯形法的计算过程单纯形法的计算过程第一次迭代第一次迭代第一次迭代第一次迭代cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0比比 值值 1 0 1 0 0x3x4 x5 81236 0 2 0 1 000 0 3 4 0 0 1 0 - -3 - -5 0 0 0- -6 9min2x3x2 x5 05 01/2 8 1 0 1 0 0- -25/2 4min 1600012300130- -30008 - -娟烟渐黄晕址今勤尝牧祖所隧玻乡羌左蛤咬还讲俞盏

18、垦跨彰爪勺初弦追券管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法15第2章 单纯形法2.2 单纯形法的计算过程单纯形法的计算过程cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0比比 值值 1 0 1 0 0x3x2 x5 8612 0 1 0 1/2 005 0 3 0 0 - -2 1 30 - -3 0 0 5/2 0x3x2 x1 05 36 0 1 0 1/2 04 0 0 1 2/3 - -1/3 4 1 0 0 - -2/3 1/342 0 0 0 1/2 18- - 4min3X*= (4, 6, 4, 0, 0)T, z* = 42第第第第二二二二次

19、次次次迭迭迭迭代代代代俞骨摄巍凸诅誉八劣桑械鉴卉嘻荤邯棋瞎作亦佐慑诧霜涌乘荣结揪储针厅管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法16第2章 单纯形法2.2 单纯形法的计算过程单纯形法的计算过程s.t.max z = 3x1+2x2 -2x1 +x2 2 x1 -3x2 3 x1 ， x2 0 s.t.max z = 3x1+2x2 -2x1 +x2 +x3 = 2 x1 -3x2 +x4 = 3 x1，x2 ，x3， x4 0 cj 基基 解解 x1 x2 x3 x4 3 2 0 0 - -2 1 1 0x3x4 23 1 - -3 0 100 0 - -3 - -2 0 01

20、3 1 1 - -3 0 1x3x1 03 8 0 0 - -5 1 2 9 0 0 - -11 0 3解无界解无界例例2 2 求解下述求解下述LP问题问题遵拱告猛庶彬亲宜粥产薯名揩舆荫痛皋桶刃赢眼宪莆措罗补涕疾拦溪翼软管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法17第2章 单纯形法2.3 人工变量法人工变量法 考虑考虑标准型标准型 (M)： 分别给每个约束方程分别给每个约束方程硬性加入硬性加入硬性加入硬性加入一个非负变量一个非负变量 a11x1 +a12x2+a1nxn + +xn+1n+1 = b1 (0) a12x1 +a22x2+a2nxn + +xn+2n+2 = b2

21、(0) am1x1+am2x2+amnxn + +xn+mn+m = bm(0)n个个 xn+1, xn+2, , xn+m 称为称为人工变量人工变量。 初始基本可行解：初始基本可行解：( ( 人造基本解人造基本解人造基本解人造基本解 ) ) X X0 0 = ( 0, 0, , 0, b1, b2, , bm )T( (2 2. .1 1) )诡树砚沂哮搐膀栗蔼赋衔檬皆瘟碗唬胞跨巡砧汹藐始对音宠热扮酱羌昭听管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法18第2章 单纯形法 基本思想：基本思想：基本思想：基本思想： 人造解人造解 X0 不是原不是原LPLP问题的基本可行解。问题的基本

22、可行解。 但若能通过单纯形法的迭代步骤，将虚拟但若能通过单纯形法的迭代步骤，将虚拟 的人工变量都替换出去，都变为非基变量（即的人工变量都替换出去，都变为非基变量（即 人工变量人工变量xn+1 = xn+2 = = xn+m = 0），则），则X0的的 前前n个分量就构成原个分量就构成原LPLP问题的一个基本可行解。问题的一个基本可行解。 反之，若经过迭代，不能把人工变量都变反之，若经过迭代，不能把人工变量都变 为非基变量，则表明原为非基变量，则表明原LPLP问题问题无可行解无可行解。2.3 人工变量法人工变量法扫唉罗岔端坎般膝康灭逃霖蛰磊容屑酉地邯炒谢钱憋污劣糟斌华缮搭顾秆管理运筹学课件02-

23、单纯形法管理运筹学课件02-单纯形法19第2章 单纯形法2.3 人工变量法人工变量法2.3.1 大大M法法 在原问题的目标函数中添上全部人工变量，并令其系数在原问题的目标函数中添上全部人工变量，并令其系数 都为都为- -M，而而M是一个是一个充分大的正数充分大的正数。即。即 max z = c1x1 + c2x2 + c3x3 + + cnxn M( xn+1 + xn+2 + xn+m ) 由于问题目标要求最大化，因此迭代必然趋向于把具有充分小系由于问题目标要求最大化，因此迭代必然趋向于把具有充分小系数的人工变量从基变量中替换出去。数的人工变量从基变量中替换出去。 若迭代最终得到若迭代最终得

24、到最优解最优解最优解最优解X*X* ，而且，而且基变量基变量基变量基变量中中不含有人工变量不含有人工变量不含有人工变量不含有人工变量，则，则X*X*的的前前n个分量就构成原问题的一个个分量就构成原问题的一个最优基本解最优基本解最优基本解最优基本解；否则，原问题；否则，原问题无可行解无可行解无可行解无可行解。 若迭代结果是若迭代结果是解无界解无界解无界解无界，而且，而且基变量基变量基变量基变量中中不含有人工变量不含有人工变量不含有人工变量不含有人工变量， 则原问题也则原问题也解无界解无界解无界解无界；否则，原问题；否则，原问题无可行解无可行解无可行解无可行解。瑟恍瞥霞岛比栈偏屿阀瞳骸弗疹追致波镍

25、欧卜挖畦荫睹誉帐寒窝鸦恍胡剪管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法20第2章 单纯形法2.3 人工变量法人工变量法 例例3 3 用大用大M法求解下述法求解下述LPLP问题问题 max z = 3x1 x2 2x3 3x1+ 2x2 3x3 = 6 x1 2x2 + x3 = 4 x1， x2， x3 0 max z = 3x1 x2 2x3 3x1+ 2x2 3x3 +x4 = 6 Mx4x1 2x2 + x3 + x5 = 4Mx5x1， x2， x3 ， x4， x5 0s.t.解解s.t.监抉污妻旺辑畔堵幼筑揭橱件彻赵诅坚卤慕歉粱丝熊卓殆揉熬崎鞘脐啪滩管理运筹学课件02

26、-单纯形法管理运筹学课件02-单纯形法21第2章 单纯形法2.3 人工变量法人工变量法cj 基基 解解 x1 x2 x3 x4 x5 0 0 0 - M - M比比 值值 3 2 - -3 1 0x4x5 64 1 - -2 1 0 1- - M- - M - -10M - -4M- -3 1 2M +2 0 0243 2 1 2/3 - -1 1/3 0x1x5 0- - M 2 0 - -8/3 2 - -1/3 16- -2M 0 8M/3+3 - -2M- -1 4M/3+1 02 3- -2 x1x3 1 0 - - 4/3 1 -1/6 1/2 3 1 - -2/3 0 1/6 1

27、/2 7 0 5/3 0 M+5/6 M+1/2min X* = ( 3, 0, 1 )T, z* = 7 钟疡饼沿走匹谚赤拌怠站晓瘁铅晚态茄炯蝎辑常私脱诊襟伍封恨惋土离寻管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法22第2章 单纯形法2.3 人工变量法人工变量法2.3.2 两阶段法两阶段法 阶段阶段 求解求解人造极大问题人造极大问题 max w = - -xn+1 - -xn+2 - - - -xn+m s.t. ( 2.1 )( 2.1 ) 因为人工变量因为人工变量 xn+1, xn+2, , xn+m 0 所以所以 max w 0(1) 若若w* 0，则原问题，则原问题无可行

28、解无可行解，停止计算；，停止计算；(2) 若若若若ww* = 0* = 0，且人工变量都不是基变量，则转入，且人工变量都不是基变量，则转入阶段阶段： 求解原问题求解原问题；兹戮漓阴漫增任冠顽舔产阵恒琵窥徒兑冀臂劣膀疾侠惫黔冗昌搐呢测后男管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法23第2章 单纯形法2.3 人工变量法人工变量法(3) 若若若若ww* * = = 0 0，但，但“基列基列基列基列”存在人工变量，例如该列第存在人工变量，例如该列第l l 行的基变行的基变量量 xBl l是人工变量，同时该行的前是人工变量，同时该行的前n个系数个系数al l j全都是全都是0，这说明，这说

29、明 原问题的该约束方程式多余的，那么删去第原问题的该约束方程式多余的，那么删去第l l 行及行及xBl l列，类列，类 似情况全都这样删去相应行、列；转入似情况全都这样删去相应行、列；转入阶段阶段；(4) 若若若若ww* * = = 0 0，且存在人工变量，且存在人工变量xBl l是基变量，但该行的前是基变量，但该行的前n个系数个系数 中存在中存在al l k0 ，则以，则以al l k为主元进行一次换基运算，可使原变为主元进行一次换基运算，可使原变 量量xk取代人工变量取代人工变量xBl l作为基变量，类似可将这类人工变量全作为基变量，类似可将这类人工变量全 部都由基变量变为非基变量；转入部

30、都由基变量变为非基变量；转入阶段阶段。 黑桐儿偏急巡设橱驶糠涧钩阑兴棋划届员鳃齿葡锦调挎卯饼没冻吭属惮咆管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法24第2章 单纯形法 阶段阶段 求解求解原问题原问题原问题原问题 建立建立原问题原问题原问题原问题的的初始单纯形表初始单纯形表。只需把。只需把阶段阶段的的最末单纯形表最末单纯形表最末单纯形表最末单纯形表修改如下：修改如下： (1) 删去人工变量删去人工变量 xn+1，xn+2 ， ， xn+m诸列；诸列； (2) 把把cj行与行与cj列的数字换成原问题目标函数的相应系数列的数字换成原问题目标函数的相应系数; (3) 重新计算重新计算z0

31、和和j ，用以取代原检验行中相应数字。，用以取代原检验行中相应数字。 然后用单纯形法进行迭代，直到运算结束。然后用单纯形法进行迭代，直到运算结束。 2.3 人工变量法人工变量法s.t.3x1 +2x2 3x3 +x4 = 6x1 2x2 + x3 + x5 = 4x1， x2 ， x3， x4， x5 0例例4 4max w = x4 x5鱼佯养间疯损汤蚕应秩思失射夕淮乃甄吧吃又呀袖瓤盲帽拽冬淤遍腑倒笼管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法25第2章 单纯形法2.3 人工变量法人工变量法cj 基基 解解 x1 x2 x3 x4 x5 0 0 0 - - 1 - -1比比 值值

32、 3 2 - -3 1 0x4x5 64 1 - -2 1 0 1- -1- -1 - -10 - - 4 0 2 0 0243 2 1 2/3 - -1 1/3 0x1x5 0- -1 2 0 - -8/3 2 - -1/3 1 - -2 0 8/3 - -2 4/3 02min 3- -2 x1x3 0 0 - - 4/3 1 - -1/6 1/2 0 1 - -2/3 0 1/6 1/2 0 0 0 0 1 1憾渣桔懒杜桥鸣陆圭偏干活移烤介林翌履佬舔屋蚤畔椽祸幽死晤炸殆躬芭管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法26第2章 单纯形法2.3 人工变量法人工变量法 阶段阶段：

33、求解原问题：求解原问题 1 0 - - 4/3 1 3 1 - -2/3 0x1x3 X* = ( 3, 0, 1 )T, z* = 7 3 - -1 - -2 3- -2 7 7 0 0 5/3 5/3 0 0 x1 x2 x3cj基基解解证胚漏渝扁菊难幻换叭应矣厕晾篱蛇裳邢痔纱隘浸壮蝗湘竖池孽二软试交管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法27第2章 单纯形法2.4 单纯形法补遗单纯形法补遗2.4.1 进基变量进基变量进基变量进基变量的相持及其突破的相持及其突破 进基变量按最小检验数规则选定，如果出进基变量按最小检验数规则选定，如果出现两个或更多个现两个或更多个j0同时达到

34、最小而相持时同时达到最小而相持时,则应：则应：从相持的检验数从相持的检验数k 所对应的变量所对应的变量 xk中中, ,任选一个任选一个作为进基量作为进基量。册铡遂宽身冷万起劲七脆扦镑箭杨盘薛占唤听金己冯都凌螺综杜呆族萌诸管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法28第2章 单纯形法2.4 单纯形法补遗单纯形法补遗2.4.2 离基变量离基变量离基变量离基变量的相持及其突破的相持及其突破退化退化退化退化与与循环循环循环循环 cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0比比 值值 1 0 1 0 0x3x4 x5 812 24 0 2 0 1 000 0 3 4

35、0 0 1 0 - -3 - -5 0 0 0- - - -6 6min4 6 3/4 1 0 0 1/4x3x4 x2 00 5 0 - -3/2 0 0 1 - -1/2 8 1 0 1 0 1 30 3/4 0 0 0 5/4X*= (0, 6, 8, 0, 0)T, z* = 30 葫余展痞恢焦揪掖危农决掳佑放贱镊游案韵颈盖救仅办彪八郁侣落锨潮瘟管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法29第2章 单纯形法 突破离基变量的相持突破离基变量的相持突破离基变量的相持突破离基变量的相持是一重要问题，关键在于是一重要问题，关键在于突破离基变量的相持必然导致一个突破离基变量的相持必

36、然导致一个退化退化退化退化的基本可行的基本可行解，这就有可能造成单纯形法的迭代步骤陷入一个解，这就有可能造成单纯形法的迭代步骤陷入一个周而复始的周而复始的循环循环循环循环过程。过程。 避免避免循环循环循环循环的方法的方法有：有： 摄动法摄动法； 辞典序法辞典序法； 布兰德法布兰德法根据摄动法摄动法，避免避免循环循环循环循环的的准则准则是：是：2.4 单纯形法补遗单纯形法补遗从相持的离基变量中，选择从相持的离基变量中，选择下标最大者下标最大者下标最大者下标最大者离基。离基。睬眶假脊嗣愈匹妖哪狙榨炳拜喜贴常省谨沫蒙描涎孜腥禹逾蟹溃酒肄熏奇管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法30

37、第2章 单纯形法 定理定理定理定理1 1 1 1 多重最优解判别准则多重最优解判别准则多重最优解判别准则多重最优解判别准则 在最优最优单纯形表单纯形表中： 若有一个或更多个非基变量非基变量xj的检验数 j = 0，则该问题有无穷多个最优解；2.4 单纯形法补遗单纯形法补遗 2.4.3 多重最优解多重最优解每次都选一个这样的xj 进基，就能得到其它最优基本解；若问题有r 个最优极点解Xi*，则该LP问题有无穷多个最优解，且其中任一最优解X*都能表示成这r 个最优极点解的凸组合：若该xj在该表中的系数列向量 aj 0，则按单纯形法另作几次迭代，0 i 1 ， i =1, 2, , r, 且且ui

38、=1其中：X* = 1X1*+2X2* + +r Xr* 厚辉索屡喻氨阂孜崖货逼溉强努猴让袱巩腹帖狙絮阜物懒刑羞蓑审帜纠搐管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法31第2章 单纯形法2.4 单纯形法补遗单纯形法补遗 cj 基基 解解 x1 x2 x3 x4 x5 3 4 0 0 0比比 值值 1 0 1 0 0x3x4 x5 812 36 0 2 0 1 000 0 3 4 0 0 1 0 - -3 - - 4 0 0 0- -6 9min2 6 0 1 0 1/2 0x3x2 x5 04 0 8 1 0 1 0 0 12 3 0 0 - -2 1 24 - -3 0 0 2

39、08- - 4 min3嫁侄火甲煽庞蔷嘎沏眺爱庞矫睦剂洽块钦阂耪狈严疮豢速修瘸鞍瓷喻禁杭管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法32第2章 单纯形法2.4 单纯形法补遗单纯形法补遗 cj 基基 解解 x1 x2 x3 x4 x5 3 4 0 0 0比比 值值 4 0 0 1 2/3 - -1/3 x3x2 x1 6 0 1 0 1/2 004 3 4 1 0 0 - -2/3 1/3 36 0 0 0 0 0 16 12 - -min2/3 3 0 1 - -3/4 0 1/4x4x2 x1 04 3 6 0 0 3/2 1 - -1/2 8 1 0 1 0 0 36 0 0 0 0 0 1X1* = (4, 6)TX X2 2* * = (8, 3)T鸵奠洼偿栋雨讥啦潮抒霹看稳琉绍辅忠呜跋扦蔫盟挤姚扳驯颊坞跌本范酪管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法33第2章 单纯形法2.4 单纯形法补遗单纯形法补遗 X1* = (4, 6)T, X2* = (8, 3)T 0, , 1 X* = ( 8 - -4 , , 3+3 )T , 0, , 1 8 - -4 3+34683X* = + (1- -) =蛛嘘伙蹲栖逢龙友婆漾悉掀吸陋粱鸭钧醚困伟鸥青君讲币戊刻网扒熬咖导管理运筹学课件02-单纯形法管理运筹学课件02-单纯形法34第2章 单纯形法