最新复习课运筹学ppt课件.ppt

《最新复习课运筹学ppt课件.ppt》由会员分享，可在线阅读，更多相关《最新复习课运筹学ppt课件.ppt（59页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、模型、概念模型、概念图解法图解法标准化标准化单纯形法单纯形法对偶理论对偶理论第五章第五章Min zMax -z 不等式约束不等式约束通过添加松弛通过添加松弛变量变量()或剩或剩余变量余变量()化化为等式约束。为等式约束。处理非正和自由的变量处理非正和自由的变量0 x,x2xx22x2x. t . sx3x2zmax21212121标准化；列初始单纯形表；迭代。标准化；列初始单纯形表；迭代。0,2222. .32max21212121xxxxxxt sxxz0 x ,x ,x ,x2xxx22xx2x. t . sx0 x0 x3x2zmax43214213214321引入松弛变量引入松弛变量x

2、3 ,成成x1+2x2+x3=2引入松弛变量引入松弛变量x4 ,成成2x1+x2+x4=2极小化极大。极小化极大。两个松弛变量两个松弛变量x1x2x3x4比值zjj=cj-zj迭代次数基变量CBb初始单纯形表初始单纯形表基变量是哪两个？基变量是哪两个？x x3 3x x4 42 23 30 00 00 00 0C CB B=? =? x1x2x3x4x3x4迭代次数基变量CBb比值zjj=cj-zj0初始单纯形表初始单纯形表头两行头两行? Z? Zj j=? =? 末行？末行？2 3 0 02 3 0 01 2 1 0 21 2 1 0 22 1 0 1 22 1 0 1 20 00 0 x1

3、x2x3x42300 x3012102x4021012000023 3000比值zj0j=cj-zj迭代次数基变量CBb单纯形表单纯形表最优最优? ? 谁进基谁进基? ? 比值比值? ? 谁出基？谁出基？1 12 2x1x2x3x42300 x30121021x40210122000023 3000比值zj0j=cj-zj迭代次数基变量CBb迭代迭代X X2 2进基，进基，x x3 3出基，红格要变成几出基，红格要变成几? ?x1x2x3x42300 x230.510.501x40210120比值zjj=cj-zj迭代次数基变量CBbx1x2x3x42300 x230.510.5012x401

4、.51.50-0.5112/31.531.500.50.50-1.50迭代次数基变量CBb比值zj3j=cj-zj1第一次迭代第一次迭代是最优解是最优解? ?谁进基谁进基? ?谁出基谁出基? ?第二次迭代第二次迭代是最优解是最优解? ?最优解是最优解是?max?max?x1x2x3x42300 x23 30 01 12/3-1/32/3x12 21 10 0-1/32/32/32 23 34/31/30 00 0-4/3-1/3比值迭代次数基变量CBb j=cj-zj2zj10/3标准化；列初始单纯形表；迭代。标准化；列初始单纯形表；迭代。0,643422. .42max32132321132

5、1xxxxxxxxxt sxxxz0,643422. .00042max654321632532141654321xxxxxxxxxxxxxxxt sxxxxxxz引入松弛变量引入松弛变量x4 ,成成x1+x4=2引入松弛变量引入松弛变量x5 ,成成x1+x2+2x3+x5=4三个松弛变量三个松弛变量引入松弛变量引入松弛变量x6 ,成成3x2+4x3+x6=6x1x2x3x4x5x6比值0zjj=cj-zj迭代次数CB基变量b初始单纯形表初始单纯形表基变量是哪三个？基变量是哪三个？x xx x5 51 12 20 00 0 x x6 64 40 00 00 00 0C CB B=?=?1 1

6、0 0 0 0 1 1 0 0 0 0 2 21 1 1 2 1 2 0 0 1 0 1 0 4 40 0 3 4 3 4 0 0 0 1 0 1 6 60 0 0 0 0 0 0 0 0 00 00 01 1 2 4 2 4 0 0 0 00 0例例1.1.一目标函数是一目标函数是Max Z的的LPLP问题，用单纯形法问题，用单纯形法解的过程中，得到如下数据有缺的单纯形表。解的过程中，得到如下数据有缺的单纯形表。其中其中 为常数，求表中为常数，求表中( (* *处处) )所有缺失的数。所有缺失的数。x1x2 x3x4x5x6465000 x4*1*-210*14x2*1u*0.5*25x6*

7、6*-1*-2112*0-2*0比值1zjj=cj-zj*迭代次数基变量CBbx1x2 x3x4x5x6465000 x4*1*-210*14x2*1u*0.5*25x6*6*-1*-2112*0-2*0比值1zjj=cj-zj*迭代次数基变量CBbx1 x2x3x4x5x6465000 x4010-210014x2611u00.5025x6060-10-2112666u030-20 5-6u 0-30迭代次数基变量CBb1zj150j=cj-zj比值vLP问题对偶规划的提出问题对偶规划的提出v求求LP问题的对偶规划问题的对偶规划vLP问题对偶单纯形法问题对偶单纯形法例例( (对偶理论对偶理论

8、):原问题原问题几个变量？几个变量？这是要求这是要求X1 , X2 使销售收入最使销售收入最_的的LP问题问题LPLP的对偶理论的对偶理论 产品产品设备设备产品产品1 产品产品2加工能力加工能力(小时小时/天天)A2 22 21212B1 12 28 8C4 40 01616D0 04 41212销售收入销售收入23设设X1 , X2 为产品为产品1,产品产品2的产量的产量大大约束条件有几个？约束条件有几个？等式还是不等式约束？等式还是不等式约束？0,124164821222322121212121XXXXXXXXXXzMaxMin f= y1 y2 y3 y4 其对偶有几个变量？其对偶有几个

9、变量？约束条件有几个？约束条件有几个？求极大？极小？求极大？极小？42极小极小12+16+12y1 y2 y3 y4 y1 y2 y3 y4 y1 y2 y3 y4 2+4+02+2+0 +4230，+8Min z = 2x1+x2-x3 x1+x2-x3 = 1x1-x2+x3 2 x2+x3 3x1 0,x2 0, x3自由自由例例1、写出下面问题的对偶规划、写出下面问题的对偶规划Max w= y1 y2 y3 +2+3y1 y2 y3 y1 y2 y3 y1 y2 y3 y1 y2 y3 +0+- 自由自由,0,0 对一般的对一般的LP问题中：问题中： 原问题第原问题第k个约束为个约束为

10、等式等式或或，对偶，对偶问题第问题第k个变量是个变量是自由自由或非正或非正变量。变量。 原问题第原问题第k个变量是个变量是自由自由或非正或非正变量，变量，则对偶问题第则对偶问题第k个约束为个约束为等式等式或或约束。约束。对偶问题对偶问题 原问题原问题 对偶问题对偶问题目标函数类型目标函数类型 Max Min目标函数与右边目标函数与右边 目标函数系数目标函数系数 右边常数项右边常数项常数项的对应关系常数项的对应关系 右边常数项右边常数项 目标函数系数目标函数系数变量数与约束数变量数与约束数 变量数变量数n 约束数约束数 n的对应关系的对应关系 约束数约束数m 变量数变量数m原问题变量类型与原问题

11、变量类型与 变量变量 0约束约束对偶问题约束类型对偶问题约束类型 变量变量 0 约束约束的对应关系的对应关系 自由变量自由变量 约束约束原问题约束类型与原问题约束类型与 约束约束 变量变量 0 对偶问题变量类型对偶问题变量类型 约束约束 变量变量 0 的对应关系的对应关系 约束约束 自由变量自由变量对偶关系对应表对偶关系对应表原线性规划原线性规划Min z = 4X1 +2X2 -3X3 -X1+2X2 62X1 +3X3 9 X1 +5X2 -2X3 = = 4X2 , X3 0Max f- y1+2y2 + y3 对偶规划对偶规划例例2、写出下面问题的对偶规划、写出下面问题的对偶规划= 6

12、y1 +9y2 +4y3 2y1 +5y33y2 -2y3y1 0 , y3自由自由y2 0,4 2 -3 = Min z = 3X1 +2X2 +X3+4X4 2X1+4X2+5X3+ X4 03X1 - X2+7X3-2X4 25X1+2X2+ X3+6X4 10X1 ,X2 ,X3 , X4 0例例3、用对偶单纯形法解规划问题、用对偶单纯形法解规划问题产地数产地数m=2,m=2,销地数销地数n=3,n=3,产销平衡，产销平衡，决策变量个决策变量个数数m m* *n,n,等式等式约束数约束数m+nm+n，不等式约束不等式约束数数0,0,目标函目标函数是总运价数是总运价, ,要求最小。要求最

13、小。 销地销地 运价运价产地产地B1B2B3产量产量A16 64 46 6200200A26 65 55 5300300销量销量150150150150200200500500 销地销地 运量运量产地产地B1B2B3产量产量A1x11x12x13200200A2x21x22x23300300销量销量150150150150200200500500 销地销地 运价运价产地产地B1B2B3B4产量产量A13 311113 310107 7A21 19 92 28 84 4A37 74 410105 59 9销量销量3 36 65 56 62020 销地销地 运价运价产地产地B1B2B3B4产量产量

14、A13 311113 310107 7A21 19 92 28 84 4A37 74 410105 59 9销量销量3 36 65 56 62020从闭回路看。从闭回路看。？4+5-1=8 4+5-1=8 。？121 销地销地 运价运价产地产地B1B2B3B4产量产量A13 311113 310107 7A21 19 92 28 84 4A37 74 410105 59 9销量销量3 36 65 56 62020-11012 销地销地 运价运价产地产地B1B2B3B4产量产量A13 311113 310107 7A21 19 92 28 84 4A37 74 410105 59 9销量销量3

15、36 65 56 62020121-11012 销地销地 运价运价产地产地B1B2B3B4uiA13 311113 31010A21 19 92 28 8A37 74 410105 5vj3132560310-23-590221912例例2.2.求下列运输问题的解。求下列运输问题的解。检查产销是否平衡？检查产销是否平衡？ 销地销地 运价运价产地产地B1B2B3B4产量产量4 41 14 46 68 81 12 25 50 08 83 37 75 51 14 4销量销量6 65 56 63 3产销平衡？产销平衡？用最小元素法求下列运输问题的初始基可行解。用最小元素法求下列运输问题的初始基可行解。

16、用位势法检查此解是否最优？用位势法检查此解是否最优？ 销地销地 运价运价产地产地产产量量4 41 14 46 61 12 25 50 03 37 75 51 1销量销量20208 88 8B1B2B3B44 46 65 56 63 330550350110333 销地销地 运价运价产地产地位位势势4 41 14 46 6531 12 25 50 0533 37 75 51 113位势位势B3B4B1B2求出位势检查此解是否最优？求出位势检查此解是否最优？求检验数此解优否？求检验数此解优否？0214-11152225-1否！闭回路？否！闭回路？ 如何调？如何调？ 销地销地 运价运价产地产地位位势

17、势4 41 14 46 6531 12 25 50 0533 37 75 51 113位势位势B3B4B1B2用闭回路调整用闭回路调整, ,调整量？调整量？Min1,3=11求位势！求位势！0141001求检验数！求检验数！361115有负的吗？有负的吗？最优？最优？是！是！总运费？总运费？一个求最大的一个求最大的LP问题的单纯形表如下：问题的单纯形表如下：课堂练习一.求其中空缺的数求其中空缺的数(*)分别是什么？求出此分别是什么？求出此LP问题的解。问题的解。x1x2x3 x4 x5x6124000 x4*10*002*1 -0.5 *1 -0.5 1x3*0*0 0.25 1.5*-1*1

18、zjj=cj-zj*迭代次数基变量CB比值b为什么？为什么？课堂练习二. 销地销地 运价运价产地产地B1B2B3B4B5产产量量A15 520202525A2181812123030A315155 520204040A420202020销量销量20203838171720202020求解如下运输问题：求解如下运输问题：课堂练习三. 销地销地 运价运价产地产地B1B2B3B4产量产量A12 29 910107 79 9A21 13 34 42 25 5A38 84 42 25 57 7销量销量3 38 84 46 6求下图中从求下图中从A A到到E E的最短路的最短路 :AB1C3B2C1C22

19、25611312316ED3D1D2134514用标号法求得下图中从用标号法求得下图中从A到到E的最短路的最短路AB1C3B2C1C2225611312316ED3D1D21345140233464576为为A B2 C2 D1E,其长为其长为7。 vsv2v3v1v4vt151041010102012453用标号法求得下图中从用标号法求得下图中从vs到到vt的最短路的最短路 01510121014121622141622最短路最短路为为vs v3 vt,其长为其长为22。 练习练习: :求下图中从求下图中从v v1 1到到v v7 7的最短路的最短路 用标号法求得下图中从用标号法求得下图中从v1到到v7的最短路的最短路0898151691011101114141313终点终点v2v3v4v5v6v7最短路长最短路长9 98 81111101014141313得：得：59 结束语结束语