运筹学例题解析

1、标记，不等式约束条件及变量约束要标出成立的方向，目标求数只程画下其中一条等值线，顶点用大写英文字母标记。1.各个约束条件的边界及其方向如图'；A(5,043C5x2汨(1,32X1+X2<5B(1,3)和 0(0,0)。X2> 3 x 11中直线和箭头所示，其中阴影部分为可行域，由直线相交可得其顶点A(5,0)、2.画出目标函数的一条等值线CD2x1+X2=0,它沿法线向上平移，目标函数值-2 -1 -1X1(一)线性规划建模与求解B.样题：活力公司准备在 5小时内生产甲、乙两种产品。甲、乙两种产品每生产1单位分别消耗2小时、1小时。又根据市场需求信息，乙产品的产量应该至少

2、是甲产品产量 的3倍。已知甲、乙两种产品每销售1单位的利润分别为 3百元和1百元。请问：在5小时内，甲、乙两种产品各生产多少单位，才能够使得总销售利润最大要求：1、建立该问题的线性规划模型。2、用图解法求出最优解和最大销售利润值，并写出解的判断依据。如果不存在最优解，也请说明理由。解: 1、(1)设定决策变量：设甲、乙两种产品分别生产X1、X2单位(2)目标函数： max z=2x 1+X22x1 X25约束条件如下：s.t X2 3XX1,X201所示，其中可行域用阴影部分2、该问题中约束条件、目标函数、可行域和顶点见图结论：本题解的情形是：无穷多最优解 ，理由:目标函数等值线 z=2 X1

3、+X2与约束条件2 x 1+X2w 5的边界平行 。甲、乙两种产品的最优产量分别为(5,0)或(1,3)单位;最大销售利润值等于 5百元。（二）图论问题的建模与求解样题A.正考样题（最短路问题的建模与求解，清华运筹学教材编写组第三版 267-268页例13）某企业使用一台设备， 每年年初，企业都要做出决定，如果继续使用旧的， 要付维修费； 若购买一台新设备，要付购买费。但是变卖旧设备可以获得残值收入，连续使用1年、2年、3年、4年以上卖掉的设备残值分别为8万元、6万元、3万元和0万元。试制定一个 5年的更新计划，使总支出最少。已知设备在各年的购买费与维修费如表2所示。要求：（1）建立某种图论模

4、型；（2 ）求出最少总支出金额。表2枪畚吋购匹絲乌草條霽（单注：万那1年工2旷需J年牌畑II"Ti1212B机81督非0电11 7 22 7344 Sit惰烧an10解: （ 1）建立图论一一最短路问题模型。 设点V表示第i年年初，虚设一个点 V6,表示第五年年底； 弧（Vi, Vj）表示第i年初购进一台设备一直使用到第j年初（即第i-1年年底）再卖掉并获得残值收入； 弧（Vi, V）上的权数表示第i年初购进一台设备，一直使用到第j年初所需支付的购买、维修及抵扣残值收入以后的全部费用（单位：万元）。例如：弧（V1, V 4）上的费用权数（2）用Dijkstra法求解从V1到V的最短路

5、。给起点V1标号（0,v 1）;=V1； J=v2,v 3,v 4,v 5,v 6弧集合v 1,v 2、v 1 ,v 3、v 1 ,v 4 、v 1,v 5、v 1,v 6S12=l 1+b12=0+8=8;s 13=1 1+b13=0+16=16;s 14=1 1+b14=0+27=27;S15=l 1+b15=0+41=41;s 16=l 1+b16=0+59=59mins 12,s 13,s 14,s 15,s 16=min8,16,27,41,59=8= s12=l 2给 V2标号（8,vi）=v 1,v 2 J= v3,v 4,v 5,v 6弧集合v 1,V3、v 1,V 4、v 1

6、,V5、v1,V6、 v2,v 3、v 2,v4、v 2,v 5、V2,V6s23=l 2+b23=8+8=16;s 24=l 2+b24=8+16=24;s 25=l 2+b25=8+27=35;s 26=l2+b26=8+41=49/ minsi4,s i5,s i6,s 23,s 24,s 25,s 26=min16,27,41,59,16,24,35,49=16=S13或 S23=l 3 ,任选一个si3,选择给V3标号（16, v i）。=v 1,v 2,v3J=v4,v5,v 6弧集合 v 1,v 4 、 v 1,v5、 v 1,v 6、 v 2,v4、 v 2,v 5、 v 2,

7、v6、v3,v4、 v3,v5 、 v3,v6 s34=l 3+b34=16+9=25; s 35=l 3+b35=16+27=35;s 26=l 2+b26=8+41=49mins i4,s i5,s i6,s 24,s 25,s 26,s 34,s 35,s 36=min27,41,59,24,35,49,25,35,49=24=s24=14给 V4标号（24,v 2）=v1,v2,v3,v4J=v5,v6弧集合 v1,v5、 v 1,v6、v2,v5、 v2,v6、v 3,v5 、 v3,v6、 v4,v5 、 v4,v6 s45=l 4+b45=24+9=33; s 46=l 4+b4

8、6=24+17=41/ mins ©s 16,s 25,s 26,s 35,s 36,s 45,s 46=min41,59,35,49,35,49,33,41=33=s45=l 5.给 V5标号（ 33,v 4）=v1,v2,v3,v4,v5J=v 6 弧集合 v 1,v6、 v2,v6、v3,v6、v4,v6、 v5,v6 s56=l 5+b56=33+10=43 / mins 16,s 26,s 36,s 46,s 56=min59,49,49,41,43=41=s46=1 6给 V6标号（ 41,v 4）= J=计算终止。由终点V6标号反向追踪，可得到V1到V6的最短路：V12

9、V 4V 6,长度为丨6=41,即5年内该设备的最小总支出金额为 41 万元。B.考题复习知识点：1. 最短路问题求解的基本思想请查阅课本或其他参考书籍，自行简答总结。2. 掌握用上述“ Dijkstra 标号法”求解的步骤和处理方法，考试时书写格式请参照本样题。3. 掌握最短路确定的反向追踪方法和最短距离。考试题比此题计算量小。4. 掌握图论问题建模的程序，会说明图论模型各组分（弧或边、节点、权数）的实际涵义。(三)动态规划 “复合系统工作可靠性问题”建模和求解)A.正考样题及其解答：某厂设计一种电子设备，由三种元件 D、D2、D3组成。已知这三种元件的单位价格、单位重量和可靠性如表4,要求

10、在设计中所使用元件的费用不超过105元，重量不超过 21克。问应如何设计使设备的可靠性达到最大。解：(1)建立动态规划模型 按元件的种类数划分阶段，k= 1,2,3。每阶段阶段第k种元件并联几个。 状态变量xk表示第k阶段初尚未使用的费用；状态变量yk表示第k阶段初剩余的可增加重量。显然 X1=105,y 1=21,x k>O,y k>0。决策变量Uk表示第k阶段元件D并联的个数。允许决策集合:Dk(xk，y k) = ukX k -Cky k -w k1 < Uk < min(j=k+1,j=k+1,k = 1,2ckwkXy1 < U3 <min( 丄,

11、 亠C3W3Ck表示第k种元件的单位费用；w表示第k种元件的单位重量； 状态转移方程： Xk+1 = x k-c k u k ; y k+1= yk-Wk u k。HckU)=1-(1-Pk)* 阶段指标函数dk(Uk)表示元件B正常工作的概率；最优指标函数fk(Xk ,y k)表示从元件 D到元件D正常运行的最大概率。 逆序解法的基本方程如下：fk(xk,yk)max、dk(Uk) fk1(xk1,yk1)k=3,2,1Uk Dk(x< ,yk)彳4(“4)1(2 )用逆序解法求解第3阶段，k=3f3(X33)=maxX3 y31 旬3min ',205d3(U3)1- (1-

12、0.5)U3第2阶段，k=2f2(X2,y2)max。yKu? vmin(:仆,七5) 1-(1-0.8)U2 f3(X2 沁必 W2U2) 第1阶段，k=1u,屮f1(X1,yJXmax5 y 54 1-(1- 0.9)U1 f2(X1 30u1,y 3uJX120 15 y1541<U1 市in( J- , 1)303 由于xi=105,y 1=21,故问题为求出f 1(105,21)即可。而f i(105,21)max1- (1- 0.9) U1 f2 (10530 u1, 21 3u1),105201521542'1，1 f1 <U1 <min(,)303ma

13、x 0.9 f2 (75,18),0.99 f2 (45,15)1 <u 1 <2f 2(75,18)max752018 0.8) U2f3(7515 u 2,184 u2)f 2(45,15)max452015 51 © 2 <min(,.21541)-(1-0.8)U2 f3(45 15u2,154U2)=max 0.8 f3 (30,11)U 210.8 f3(30,11)f3(60,14)max 11 <U3 <min(60 ,：)205(1-10.5)U3max (0.5, 0.75)1 <U3 <2 '0.75f3(45

14、,10)max14510 111 <U3 <min(,_)3盯丁-(1-0.5)U 3max( 0.5, 0.1 <U 3 < 275)0.75f3(30 ,6)max 1-(1-0.5)U 3 max( 0.5)0.51 <u 3 <min(,)205u 3 =1f3(30 ,11 )max130111 <U3 <min(,)205-(1-0.5)U3max( 0.5)U3 =10.5f2(45,15)0.8f3(30,11)0.80.50.4,0.992f3 (30, 6)12 Wmin(max 0.8 f3(60,14),0.96 f3(4

15、5,10),1 <u 2 <315f2(75,18)=max 0.8 0.75,0.96 0.75,0.992 0.50.72f1(105,21)=max 0.9 0.72,0.99 0.40.648状态转移图如下:*I<1*1(1051) = 0.*酚議2TCj-1=2-151»2 v»v>- 4u >尉段1结论：求得U1=1, u 2=2,u 3=2为最优方案，即 Di、D2、D3三种元件分别并联 1个、2 个和2个。总费用为100元，总重量为21克，可靠性为。B.正考复习知识点：1. 会按照样题解答那样分六步建立动态规划模型。文字说明方面

16、：准确说明各种变量的实际涵义；数学表达方面：能正确、规范地写出逆序解法的基本方程， 阶段变量必须逆着写 取值，明确边界条件；在建模时对取值明确的状态变量应该说明其具体值；会以规范的集合语言写出允许决策集合的具体形式； 具体写出状态转移方程函数形式； 写出阶段指标函数的 数学表达式。考试题目比此题的计算量要小，而且未必会考两个状态的情形。2. 比照样题中的解答步骤来书写答题过程，会绘制“状态转移图”并以此得出结论，会得出全过程最优指标函数值并给出依据。3. 清华大学教材编写组编写运筹学第三版237-238页例8计算过程可以参考（但fk（Sk）中xk的范围有错，请按照课件第四章 50-53张例来改

17、正，答题格式也须参照后者。（四）线性目标规划或运输问题的建模和求解A.正考样题一一非标准运输问题的建模与“表上作业法求解”有三个发电站产地 Bi，B2，B3需要从两个煤矿 Ai, A购买煤炭，各自的产量、需求量以 及每万吨煤炭的运价（千元）如表 5所示。问如何调运煤炭，使得总运输费用最小 表5产销平衡表和单位运价表发电站B煤矿ABiB2Bb产量（万吨）A2362236A1577212每月对煤的需求量（万吨）315要求：（1）请建立该问题的线性规划模型，如果有必要再化为标准问题。（2）用表上作业法求解：用最小元素法确定初始方案； 用闭回路法或者位势法验证初始方案是否最优如果 非最优，请用闭回路法

18、调整，直至求出最优方案。解:(1)设产地A（i=1,2 ）调运到销地Bj(j=1,2,3 )的煤炭为Xij万吨，可建立以下模型minz23i 1 jCij1Xij23 X1162 X1223 X1315 X2177 X2221 X23X11X12X136X21X22X232X11X213s.t.1X12X22X13X235Xij0( i1,2；j 1,2,3)（2）因为总产量8万吨（=6+2）小于总需求量9万吨（=3+1+5），所以本问题不是标准运输问题。增加一个虚拟产地A3,它的单位运价 C31=C32=C33=0,产量为9-8=1 （万吨）。（3） 第一步：用最小元素法确定初始方案（方案可

19、能有以下三种，随着添加 0位置不同而不同）23(0)6223(5) 6 (1)(0)7721-(6)001(0)315(0) (0)(0)方法二：伏格尔法（本题用此法求出的初始基可行解就是最优解）法一：用位势法求检验数。种初始方案）是否最优。求解见表6所示:销地产地B1B2B3UA0230620230A0152377621-8A00-39000-23V236223表6因为 min( (T 22, (T 23, (T 32, (T 33| (T ij <0)= (T 32=-39<0 ,所以初始方案并非最优方案，需进一步调整，X32为进基变量。法二：用闭回路法求检验数23(0)62(1) 23 157721t 22=77-15+23-62=23; t 23=21-15+23-23=6; t 33=0-0+23-23=0 ;t 32=0-0+23-62=-39 （注：图中画出了非基变量X32的闭回路）；因为min（ T 22, T 23, T 32, T 33| T ij <0） =T 32=-39<0 ,所以初始方案并非最优方案，需进一步 调整，X32为进基变量。第三步：求