2013运筹学64学时总复习要点

1、运筹学总复习2014.1.3复习内容与要求:1建模方面：目标规划、动态规划、整数规划2计算方面：线性规划、对偶规划、运输问题、指派问题、割平面算法、最大流、网络计划、 对策论、决策论。max z = 2x1 5x2x1< 4【例题1】用单纯形法求解线性规划问题的解。2x2 <12 3x1 2x2 乞 18X1, X2 一 0解：添加三个松弛变量，把上述规划化成标准型maxz=2xi 5x2Xi+xs =4X2 +X4 =63xi +2x2 +X5 =18Xi,X2,X3,X4,X5 KO基变量bX1X2X3X4X5X3410100X4601010X51832001025000基变量

2、bX1X2X3X4X5X3410100X2601010X56300-21-30200-50基变量bX1X2X3X4X5X320012/3-1/3X2601010Xi2100-2/31/3-3400-5-11/3-2/3最优解是（2， 6）最优值是34。【例题2】某公司制造三种产品 A、B、C,需要两种资源（劳动力和原材料），现要确定总利润max z = 3% + x2+5x36%+3x2+5x3 兰 45（劳动力）最大的生产计划，列出下述线性规划“*3xi+ 4X2+5怡兰30（原材料）Xi, X2, X3XO求：（1）线性规划问题的最优解；（2）求对偶问题的数学模型及其最优解；（3）最优解不

3、变的情况下，求产品A的利润允许变化范围；（4）假定能以10元的价格购进15单位的材料，这样做 是否有利，为什么？ （ 5）当可利用的资源增加到 60单位时，求最优解。（6）当产品B的原材 料消耗减少为2个单位时，是否影响当前的最优解，为什么？ （7）增加约束条件2xi+x2+3x320,对原最优解有何影响，对对偶解有何影响？解答：（1 ）线性规划问题的最优解 首先将问题标准化：max z = 3x1+ x2+ 5x33x2+ 5x3 x4-453x-i+ 4x2+5x3 x5 =30X1,X2, X3, X4, X5 - 0cj315009iCbXBbX1X2X3X4X50X456351090

4、43034【5】016X5315000X153-101-15463/54/5101/5X30-300-1最优解为 X*=(x 1,X2,X3,X4,X5)T=(0,0,6,15,0)T，最优目标值 z*=30（2）求对偶问题的数学模型及其最优解;min w 二 45y130 y26 yi + 3 y2 Z 3* 3力 +4y?兰 15y1 5y2 - 5y -0,y2 -0y1*=0,y 2*=1（3）最优解不变的情况下，求产品A的利润允许变化范围;最优解不变的情况下，：ci0,c <3(4) 假定能以10元的价格购进15单位的材料，这样做是否有利，为什么？有利单位材料的影子价格是1元，

5、10元钱购进15单位的材料的单位价格为2/3元，低于影子价格。同时，在保持最优基不变的情况下- 30 _ b2 : 15购进15吨的原材料，最优基不变。该材料的影子价格仍为1元。(5) 当可利用的资源增加到60单位时，求最优解。b' -B Jb+潤七5cj31500CbXbX1X2X3X4X5B0X-153-101【-1】54123/54/5101/5X30-300-10X15-310-115596/53/511/50X3-3-20-10最优解为 X*=(x 1,X2,X3,X4,X5)T=(0,0,9,0,15)T，最优目标值 z*=45(6) 当产品B的原材料消耗减少为 2个单位时

6、，是否影响当前的最优解，为什么?X2在最有表是非基变量，该产品的原材料消耗只影响X2的检验数。P2 = B 和2二 2 = c2 C B B P2所以最优解不变(7) 增加约束条件2X1+X2+3X3< 20,对原最优解有何影响，对对偶解有何影响?增加的约束条件，相当于增加了一个约束方程2x1 x2 3x3 X6 = 20cj241000CbXbbX1X2X3X4X5X60X4153-101-105X363/54/5101/500X6202130010-300-100X4r 153-101-105X363/54/5101/500X624/5-7/500-3/510-300-10对原问题的

7、最优解无影响，对对偶问题的最优解也无影响。【例题3】已知如下线性规划问题：maxz =2洛 x2 5x3 6x4 2洛亠冷亠沧_82洛 2x2 冷 2x4 _12N，X2，X3，X4 一0已知其对偶问题的最优解为Y* =(4,1)。试用对偶理论求出原问题的最优解。解：对偶问题是： minw=8yi，12y242yi 2y2 _22y2 -1yi y2 -5y1 ' 2y2 -6 mm 一0 设原问题最优解为 X =(X1 , X2 , X3, X4)T , 将Y*带入对偶问题约束条件中，得(2)为严格不等式；由互补松弛条件知，x；=X；=0。因为y1=4丰0，及y2=1丰0,所以原问题

8、的两个约束条件应取等号，故有X3X4=8II *X =(0,0,4,4)，最优值 z=44。X3+2x4=12解方程组得:x3=x4= 4,所以原问题的最优解为【例题4】用对偶单纯形法求下面问题min f (x) =4x1 6x2|x1 2x2 -80s.t. 3x1 x2 -75X1, X2 0解:CjTCbXbb4600min( zj - Cj)/ai*jX1X2X3X4ai*j <00X3-80-1(-2)104,3*0X4J75-101OBJ=0ZjT0000Z - Cj-4-600CjT4600CbXbbXiX2X3X46X2401/21J/200X4-35（2）0J/212/

9、5*,6OBJ=240ZjT36-30Z - Cj-10-30CjT4600CbXbbX1X2X3X46X23301-3/51/54Xi14101/5-2/5OBJ=254ZjT46J4/5-2/5Z - Cj00J4/5-2/5答：最优解为Xi =14 , X2=33，目标函数值为 254。【例题5】给定下列运输问题的单位运价表及各个产销地的产量和销量,B1B2B3B4产量A1291079A213425A384257销量3846求运费最小的运输方案。解：(1 )利用伏格尔法求初始基B1B2B3B4产量A13519A255A3347销量3846(2)写出位势表并计算各变量的检验数。B1B2B3

10、B4UiA100300A24-120-5A311003-5Vj2977（3）当前检验数有负数，闭回路法调整。B1B2B3B4产量A1369A2505A3347销量3846并计算上表所描述的调运方案的检验数B1B2B3B4UiA1140A243-5A3102-4Vj2867可见，检验数全为正，故最优解为3X 2 + 6 X 7 + 5X 3 + 3 X 4 + 4X 2 = 83。【例题6】某市准备在下一年度预算购置一批救护车，已知每辆救护车购置价格为20万元。救护车用于所属的两个县，各分配Xa和Xb台，A县救护站从接到求救电话到救护车出动的响应时间为（40-3xa） min , B县相应的响应

11、时间为（50-4xB） min，该市确定如下优先级目标。Pi：救护车的购置费用不超过 400万元；P2： A县的响应时间不超过 5min ;P3: B县的响应时间不超过 5min。要求：（1 ）建立目标规划模型（不用求解）。（2）若对优先级目标作出调整，P2变Pi, P3变P2, Pi变P3,重新建立目标规划模型（不用求解） 。解：设Xa为分配给A县的救护车数，Xb为分配给B县的救护车数量。min z = Rd广+ F2d2+ Rdf20xa +20xb +di di*=400(1) 目标规划模型为：40 _3xa十d2_ d2+ = 5st#+50-4xb +d3-dj = 5Xa,Xb 0

12、,d,di _0(i =1,2,3)(2) 与(1)比较，只是目标函数改变了，而约束条件没有变化。故(2)的目标规划模型为:min z = Rd2*+ F2d3+ F3dJ20xa +20xb "-4=40040-3xa +d厂-d2+= 5s.t#_+50-4xb +d-d3 =5Xa,Xb 0,d,di 0( 1,2,3)【例题7】某厂拟建两种不同类型的冶炼炉。甲种炉每台投资为2个单位，乙种炉每台许投资为1个单位，总投资不能超过 10个单位；又该厂被许可用电量为 2个单位，乙种炉被许可用电 量为2个单位，但甲种炉利用余热发电，不仅可以满足本身需要，而且可供出电量1个单位。已知甲种

13、炉每台收益为 6个单位，乙种炉每台收益为 4个单位。试问：应建甲、乙两种炉各多 少台，使之收益最大？该问题也可如下表表示。（要求用割平面法求解该整数规划问题）甲种炉（X1）乙种炉（X2）限量每台投资/单位2110用电量/单位-122收益/单位64解：设X1,X2为甲乙种炉应建台数，则max z 6x1 4x22x1 x2 乞 10s.t.« 论 + 2x2 兰2x1, x2 K 0,且为整数用单纯形法求最优解，见下表。基变量bX1X2X3X4X31021105X42-1201-z06400X1511/21/2010X4705/21/2114/5-z-3001-30X118/5102/

14、5-1/5X2"-Z-32.8014/51/52/50-16/5-2/5最优解为 x° =(睾,善,O,O)T,Zo =32.81214X?X3X4确定割平面方程：555卄412取 x22- (- x3x4)乞 0555从而，构造割平面，并且标准化，加入最优表中，用对偶单纯形法求最优解，见下表。基变量bX1X2X3X4X5X118/5102/5-1/50X214/5011/52/50X5-4/500-1/5-2/51-z-32.800-16/5-2/50基变量bX1X2X3X4X5X14101/20-1/2X2201001X42001/21-5/2-z-3200-30-1=

15、 （4,2,0,2,0 T, z*=32。此解为整数解，故计算停止。划线过程（发现有4条直线）找到最优解【例题8】某部门有4个工人，现指派他们分别完成 4项工作。每人做各项工作所消耗的时间（h）如下表所示，问如何分派工作，使总的消耗时间最少？消耗工作 工ABCD甲3353乙3252丙1516丁46410解：变换效率矩阵如下:3353逐(0)0*20*逐(0)0*20*3252行1030列1(0)30*1516二标0*4(0)5n标0*4(0)546410记0*20*6记0*20*6每行每列都有两个以上的0未找到最优解答：容易看出，共有四个最优解：甲B，乙D，丙A，丁 C；甲D,乙B,丙）A，丁

16、 ）C;甲B,乙）D，丙）C,T ）A ;甲D，乙B,丙 C, 丁 A ； OBJ=10。【例题9】分配甲、乙、丙、丁四人去完成5项任务。每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一人可兼完成两项任务，其余三人每人完成一项，试确定总 花费时间最少的指派方案。甲 一04一5 乙19 18501912戊.4变换得A甲_0乙1770 甲* 18 1117718707A14甲$16*6 一54ABCDE甲2529314237乙3938262033丙3427284032丁2442362345解：假设增加一个人戊完成各项工作的时间取A、B、C、D、E最小值。得效率矩阵为:ABCDE甲

17、-25293142371乙3938262033丙3427284032丁2442362345戊2427262032 一各行减最小值，各列减最小值：得A B甲001183乙1813003丙1100180丁0147012戊2002最有指派方案A B C D E10 0 00 0 100 0 0 10 0 0 00 10 0甲一一B，乙C,D，丙一一E, 丁最低费用=29+ 26+ 20+ 32+ 24= 131【例题10】某公司打算将3千万元资金用于改造扩建所属的3个工厂，每个工厂的利润增长额与所分配的投资有关。各工厂在获得不同的投资额时所能增加的利润如下表所示，问应如何分配资金，使公司总的利润为最

18、大。利润"''工厂''JX投资01千万2千万3千万102.541020358.530269解：K为阶段变量，k=1,2,3S k：第k阶段所剩的资金数X k：第k阶段分配给第k个工厂的资金数 gk（ Xk）:将Xk分配给第k个工厂的效益 状态转移方程：Sk+i= Sk-Xk递推关系：k 二 n-1,1fk(Sk) =0maxgk(Xk) + fk41(Sk -Xk) fn(Sn) =maxgn(xn)_Xn 已第三阶段，k=3X3=s3f3(s3"maxg3(x3)g3（X3）f3（S3）*301230000122126623993第二阶段：

19、S3=s2-x2,0<s2<3,0<x22f2（S2）礼鬟醫区）f3（S2 -X2）f2（S2）=0mjax2g2（X2）+ f3（S2 X2）f2（S2）*2012300+00010+23+02120+63+25+06030+93+65+28.5+090,1第三阶段S1=3S2=s1-x1,001 3f1（S1）-xjf1（S1）*1Lx012330+92.5+64+310+0103最优分配方案为，x1*=3,x2*=0,x3*=0最佳获益值：10千万。【例题11】现有一批重要物资空运到距离灾区发生地最近的某机场后，要通过公路运输将物资运往10个重灾地点，下图为各重灾地点的

20、交通网络示意图，其中1代表机场，2-11代表10个重灾区，12和13代表道路节点。请你求出从机场到各重灾区的最短路径。I UliC>Ww7/Q:解：本题直接使用 Dijkstra标号算法即可求出从机场1到各灾区的最短路。第一步：对灾区1进行标号，为(0,-),接着对其余各点进行临时标号，分别为灾区3：(-，150);灾区10：(-，100)；灾区9:( -，190)；道路节点12 :( -，100)；道路节点 13: (-, 80);灾区 2： (-,s) ; 0 灾区 4: (-,s);灾区 5： (-,s);灾区 6： (-, );灾区 7: (-，);灾区 8： (-,g);灾区

21、11 : (-，);第二步：选择临时标号最小的，转为永久性标号，并将各结点标号重新标号灾区 1: (0,-);道路节点 13: (80,-);灾区 3: (-, 150);灾区 10: (-, 100);灾区 9:(-, 190);道路节点 12: (-, 100);灾区 2: (-,s) ; 0 灾区 4: (-,s);灾区 5: (-，);灾区 6:(-，);灾区 7: (-,g);灾区 8: (-,8);灾区 11: (-,g);第三步：选择临时标号最小的，转为永久性标号，并将各结点标号重新标号灾区1: (0,-);道路节点13: ( 80,-);道路节点12: (100,-);灾区10

22、: (100,-);灾区3: (-,150);灾区 9: (-, 145);灾区 2: (-, 140);灾区 6: (-, 125);灾区 4: (-,8)；灾区 5: (-,8);灾区 7: (-,8);灾区 8: (-,8);灾区 11 ： (-,8);第四步：选择临时标号最小的，转为永久性标号，并将各结点标号重新标号灾区1: (0,-);道路节点13: ( 80,-);道路节点12: (100,-);灾区10: (100,-);灾区6: (125,-);灾区 3: (-, 150);灾区 9: (-, 145);灾区 2: (-, 140);灾区 4: (-,8)；灾区 5: (-,8

23、);灾区 7: (-,8);灾区 8: (-, 165);灾区 11: (-, 307);第五步：选择临时标号最小的，转为永久性标号，并将各结点标号重新标号灾区1: (0,-);道路节点13: ( 80,-);道路节点12: (100,-);灾区10: (100,-);灾区6: (125,-);灾区 2: (140,-);灾区 3: (-, 150);灾区 9: (-, 145);灾区 4: (-, 225);灾区5: (-, 8);灾区 7: (-, 215);灾区 8: (-, 165);灾区 11: (-, 307);第六步：选择临时标号最小的，转为永久性标号，并将各结点标号重新标号灾区

24、1: (0,-);道路节点13: ( 80,-);道路节点12: (100,-);灾区10: (100,-);灾区6: (125,-);灾区 2: (140,-);灾区 9: (145,-);灾区 3: (-, 150);灾区 4: (-, 225);灾区 5: (-, 8);灾区 7: (-, 215);灾区 8: (-, 165);灾区 11: (-, 245);第七步：选择临时标号最小的，转为永久性标号，并将各结点标号重新标号灾区1: (0,-);道路节点13: ( 80,-);道路节点12: (100,-);灾区10: (100,-);灾区6: (125,-);灾区 2: (140,-

25、);灾区 9: (145,-);灾区 3: (150,-);灾区 4: (-, 183);灾区5: (-, 196);灾区 7: (-, 215);灾区 8: (-, 165);灾区 11: (-, 245);第八步：选择临时标号最小的，转为永久性标号，并将各结点标号重新标号灾区1：（0，-）；道路节点13：（ 80,-）；道路节点12：（ 100，-）；灾区10：（ 100，-）；灾区6： （125，-）；灾区 2：（ 140，-）；灾区 9：（ 145，-）；灾区 3:（ 150，-）；灾区 & （ 165，-）;灾区4: （-，183）；灾区 5: （-，196）；灾区 7: （

26、-，210）；灾区 11 : （-，245）； 第九步：选择临时标号最小的，转为永久性标号，并将各结点标号重新标号灾区1: （0，-）；道路节点13:（ 80，-）；道路节点12: （100，-）；灾区10:（100，-）；灾区6:（125，-）；灾区 2: （140，-）；灾区 9: （145，-）；灾区 3: （150，-）；灾区 & （ 165，-）；灾区4: (183，-)；灾区 5:(196,-)；灾区 7:11： （245，-）；算法结束。（210，-）；灾区【例题12】求下面网络s到t的最大流和最小截，从给定的可行流开始标号法。（要求每得到一个可行流后，即每次增广之后，重

27、新画一个图，标上增广后的可行流，再进行标号法）解:答：最大流为15,最小割截为V = (s,v3),V = (v1,v2 ,v4 ,v5,t)【例题13】绘制工程图，计算各工作的最早开始时间和最早完工时间，并给出关键路线。工序内容工时（天）紧前工序A初步研究1/B研究选点2AC准备调研方案4AD联系调研点2BE培训工作人员3B、CF实地调研5D、EG写调研报告并汇总4F解：（1）工程图如下:（2）各工序时间如下图，工程ESEFA01B13C15D35E58F813G1317（3）关键路线是 A-C-E-F-G【例题14】甲乙乒乓球队进行团体对抗赛，每对由三名球员组成， 双方都可排成三种不同的阵

28、容，每一种阵容可以看成一种策略，双方各选一种策略参赛。比赛共赛三局，规定每局胜者得1分,输者得-1分，可知三赛三胜得3分，三赛二胜得1分，三赛一胜得-1分，三赛三负得-3分。甲队的策略集为S1= a, a, a，乙队的策略集为 Sj= ft ,役，伦，根据以往比赛得分资料，可 得甲队的赢得矩阵为 A，如下：r 111A=1 1-1-33-13试问这次比赛各队应采用哪种阵容上场最为稳妥。解：甲队的a, a, a三种策略可能带来的最少赢得，即矩阵A中每行的最小元素分别为：1,-3, -1 ,在这些最少赢得中最好的结果是1，即甲队应采取策略 a，无论对手采用什么策略，甲队至少得1分。而对乙队来说，策

29、略竹,债,伍可能带来的最少赢得，即矩阵A中每列的最大因素 （因为两人零和策甲队得分越多，就使得乙队得分越少），分别为：3 , 1 , 3,其中乙队最好的结果为甲队得1分，这时乙队采取 役策略，不管甲队采用什么策略甲队的得分不会超过1分（即乙队的失分不会超过 1 ）。这样可知甲队应采用 a策略，乙队应采取 3 2策 略。把这种最优策略 a和32分别称为局中人甲队、乙队的最优纯策略。这种最优纯策略只有当 赢得矩阵A= （aj）中等式max min a j = min max a ji j j i成立时，局中人才有最优纯策略，并把（a , 32）称为对策G在纯策略下的解，又称（a , 32）为对策G的鞍点。【例题15】矩阵