运筹学复习资料.ppt

《运筹学复习资料.ppt》由会员分享，可在线阅读，更多相关《运筹学复习资料.ppt（49页珍藏版）》请在优知文库上搜索。

1、 某市准备在下一年度预算中购置一批救护车，已知每辆救护车购某市准备在下一年度预算中购置一批救护车，已知每辆救护车购置价为置价为2020万元。救护车用于所属的两个郊区县万元。救护车用于所属的两个郊区县, ,各分配各分配x xA A和和x xB B台，台， A A县县救护站从接到求救电话到救护车出动的响应时间为救护站从接到求救电话到救护车出动的响应时间为(40(40- x xA A)min)min， B B县县相应的响应时间为相应的响应时间为(50- 4 x(50- 4 xB B )min)min，该市确定如下优先级目标。，该市确定如下优先级目标。P P1 1：救护车购置费用不超过：救护车购置费用

2、不超过400400万元。万元。要求建立目标规划模型。要求建立目标规划模型。P P2 2： A A县的响应时间不超过县的响应时间不超过5min5min。P P3 3： B B县的响应时间不超过县的响应时间不超过5min5min。Ax112233112233min z20204004035s.t.5045,0;,0,(1,2,3)ABABABiiPdP dPdxxddxddxddxxddi 解解 设设 为分配给为分配给A A县的救护车数量，县的救护车数量， 其目标规划模型其目标规划模型为：为：Bx为分配给为分配给B B县的救护车数量。县的救护车数量。目标规划 某工厂计划生产某工厂计划生产A A、B

3、 B两种产品，每吨产品的耗电量指两种产品，每吨产品的耗电量指标、原材料消耗、单位产品利润及资源限量如表所示。标、原材料消耗、单位产品利润及资源限量如表所示。 厂长首先考虑要充分利用供电部门分配的电量限额厂长首先考虑要充分利用供电部门分配的电量限额6666， 然后考虑利润不低于然后考虑利润不低于100100元；元； 据市场调查结果，希望据市场调查结果，希望B产品的产量不低于产品的产量不低于A产品的产量，产品的产量， 问应如何制定产品问应如何制定产品A A、B B的产量。建立该目标规划的数学模型。的产量。建立该目标规划的数学模型。 产品产品资源资源AB资源限量资源限量 电力电力101266原材料原

4、材料218单位产品利润单位产品利润 1020目标规划解：解：设设x1、x2分别分别表示表示A A、B B两种产品的产量，则目两种产品的产量，则目 标规划模型如下：标规划模型如下： minZ=P1 (d1- + d1+ ) + P2d2- + P3d3- 2x1+x2 8 10 x1+12x2 +d1- - d1+ =66 10 x1+20 x2 +d2- - d2+ =100 -x1+x2 +d3- - d3+ =0 x1,x2 ,d1- ,d1+ ,d2- , d2+ ,d3- , d3+ 0 6个人完成个人完成4项工作，由于个人和技术专长不同，他们项工作，由于个人和技术专长不同，他们完成完

5、成4项工作任务所获得收益如下表：项工作任务所获得收益如下表： 13545267683898841010911512111012613121113且规定每人只能做一项工作，一项工作任务只需一人操且规定每人只能做一项工作，一项工作任务只需一人操作，试求使作，试求使 总收益最大的分派方案。总收益最大的分派方案。 解解 此问题是一个非标准的指派问题，虚设两项任务此问题是一个非标准的指派问题，虚设两项任务，并设任务的收益为并设任务的收益为0， 化为标准的指派问题。化为标准的指派问题。 标准的指派问题的收益矩阵为：标准的指派问题的收益矩阵为：35450067680089810001010911001211

6、1012001312111300ijc6611max目标函数： ijijijzc x 将其化为极小值问题。将其化为极小值问题。1089813137675131354531313334213131231131301201313ijc 最优解矩阵为：最优解矩阵为：000001000010000100001000010000100000ijc 最优分派方案为：第最优分派方案为：第3个人做第个人做第项工作，项工作，第第4个人个人做第做第项工作，第项工作，第5个人做第个人做第项工作，第项工作，第6个人做第个人做第项工作，项工作，所得最大总收益为：所得最大总收益为：max613(1313342)43 z用

7、用Ford-Fulkerson标号法求下图中从标号法求下图中从s到到t的最大流及其流量，的最大流及其流量， 并求网络的最小割。弧旁数字为（并求网络的最小割。弧旁数字为（cij，fij）。）。解用解用Ford-Fulkerson标号法求出网络的增广链，如下图中虚线所示。（标号法求出网络的增广链，如下图中虚线所示。（5分）分）因此，网络中的可行流不是最大流，将其调整后得一新的可行流，如下图所因此，网络中的可行流不是最大流，将其调整后得一新的可行流，如下图所示（示（2分）分）再用标号法在上图中找增广链，标号法中断，表明已找不出增广链，故上图再用标号法在上图中找增广链，标号法中断，表明已找不出增广链，

8、故上图中的可行流即为最大流，其流量为中的可行流即为最大流，其流量为5+3+5=13。最小割为：。最小割为：(,)=( ,),( ,),(A,B)V Vs Ds C3分分第第11章章 网络计划网络计划例例(7.1b)(7.1b)：根据下表给定的条件，绘制：根据下表给定的条件，绘制PERTPERT网络图。网络图。ABCDEFGHIJKLM139876542101 1 (10(10分分) ) 、写出如下线性规划问题的对偶问题，并利、写出如下线性规划问题的对偶问题，并利用弱对偶性说明用弱对偶性说明z z的最大值不大于的最大值不大于1 1。 123123123123123221s.t.2200max,z

9、xxxxxxxxxxxxxxx无限制解解 原问题的对偶问题为：原问题的对偶问题为： 12312312312313222212s.t.100m in,wyyyyyyyyyyyyyyy无 约 束由于（由于（0，1，0）是上述对偶问题的可行解，对原问题的任一可行解）是上述对偶问题的可行解，对原问题的任一可行解CXYbX都有。2 0 1 0112, ,Y b而所以所以z的最大值不大于的最大值不大于1。(10(10分分) )设有某个求极大值线性规划问题，它的某一次迭代结果如下表，试再设有某个求极大值线性规划问题，它的某一次迭代结果如下表，试再进行一次迭代，判断迭代进行一次迭代，判断迭代的结果是否已求得最

10、优解，写出解的全部内容。的结果是否已求得最优解，写出解的全部内容。Cj 2 5 0 0 0 基基 b x1 x2 x3 x4 x5 0 5 0 x3 x2 x5 4 6 6 1 0 3 0 1 0 1 0 0 0 1/2 -1 0 0 1Cj- Z 2 0 0 -5/2 0解：解：再进行一次迭代结果如下：再进行一次迭代结果如下：Cj25000基基bx1x2x3x4x5050 x3x2x546610301010001/2-1001Cj- Zj200-5/20052x3x2x126200101010-31/31/2-1/3-1/301/3Cj- Zj000-11/6-2/32 6 2 0 0TX最

11、 优 解，2(102(10分分) )、对于线性规划问题：、对于线性规划问题： 12313123123123647 32324s.t.2250min,fxxxxxxxxxxxx xx（1）写出此问题的对偶问题；）写出此问题的对偶问题；（2）求出此问题和它的对偶问题的最优解）求出此问题和它的对偶问题的最优解和最优值。和最优值。(1)(1)对偶问题为：对偶问题为： 1231232312312324536 (1)224 (2)s.t.327 (3)0max,zyyyyyyyyyyyyyy(2)(2)引入松弛变量引入松弛变量y y4 4,y,y5 5,y,y6 6, ,将对偶问题规范化为：将对偶问题规范

12、化为： 123123423512364562453622 4s.t.32 7016max, (,)izyyyyyyyyyyyyyyyiyyy为基变量用单纯形表迭代求最优解为：用单纯形表迭代求最优解为：最优解最优解Y Y* *=(1,0,2,7,0,0)=(1,0,2,7,0,0)T T，z z* * = max z=12 = max z=12。1313123123233 102032 225 (1)16011326 2252311 2 01263,TyyxxxxxxxxxxxXz 又为，取不等号，即。，。（12分）给出下列分）给出下列线性规划的最优单纯形表，其中线性规划的最优单纯形表，其中s

13、s1 1、s s2 2分别为第分别为第1 1、第、第2 2约束方程中的松弛变量。约束方程中的松弛变量。1231231233max6212 4324s.t. 26330 ,zxxxxxxxxxx xx120c cj j6 2 12 0 0 6 2 12 0 0 c cB B 基基 bx x1 1 x x2 2 x x3 3 s s1 1 s s2 2 12 x12 x3 3 8 8 4/3 1/3 1 1/3 0 4/3 1/3 1 1/3 0 0 s 0 s2 2 6 6 -2 5 0 -1 1 -2 5 0 -1 1 c cj j-z-zj j-10 -2 0 -4 0 -10 -2 0 -

14、4 0 (1)求出最优基不变的求出最优基不变的b2的变化范围；的变化范围；(2)求出最优解不变的求出最优解不变的c3的变化范围。的变化范围。解解 （1）设）设 b2 b2+ b2，则最终表中的，则最终表中的b变为：变为：128= 6bBbb其中，其中，8 80，要使原最优基不变，还应满足：，要使原最优基不变，还应满足：6+ b20，即得到，即得到 b2-6， b b2 224。（2）设）设c3 c c3 3+ + c c3 3, ,则最终表中则最终表中x3的检验数变为：的检验数变为：33333(12)( 4,0)=12 ( 12) 3cccc 于是原最终表变为下表：于是原最终表变为下表：c c

15、j j6 2 12 0 0 6 2 12 0 0 c cB B 基基 bx x1 1 x x2 2 x x3 3 s s1 1 s s2 2 12 x12 x3 3 8 84/3 1/3 1 1/3 0 4/3 1/3 1 1/3 0 0 s 0 s2 2 6 6-2 5 0 -1 1 -2 5 0 -1 1 c cj j-z-zj j-10-4-10-4c c3 3/3 -2-/3 -2-c c3 3/3 0 -4-/3 0 -4-c c3 3/3 0 /3 0 要使原最优解不变，应满足：要使原最优解不变，应满足：3334100320 3403ccc 解得解得c c3 3-6，故，故 c36

16、。习题习题2.6 2.6 用对偶单纯形法求解下述线性规划问题：用对偶单纯形法求解下述线性规划问题： 0 x,x,x5x2x23x3x. t . sx18x12x4zmin321323132112313423512345max4121833s.t.225,0zxxxxxxxxxx x x x x 解解 先将问题改写为先将问题改写为 列出单纯形表，并用对偶单纯形法求解，计算步骤见表列出单纯形表，并用对偶单纯形法求解，计算步骤见表2-82-8最优解最优解X=(0X=(0，3/23/2，1)1)T T，min z=36min z=36下述线性规划问题下述线性规划问题习题习题 9 . 2 0 x,x2x1xx8xx26x2x. t . sx2x3zmax21221212121已知用单纯形法求得最优解的单纯形表如表已知用单纯形法求得最优解的单纯形表如表2-242-24所示。试分所示。试分析在下列各种条件单独变化的情况下进行分析。析在下列各种条件单独变化的情况下进行分析。(c) (c) 增加一个变量增加一个变量x x7 7, ,其在目标函数中系数其在目标函数中系数c c7 7=4,P=4,P7 7=