运筹学例题解析

1、(一)线性规划建模与求解B.样题：活力公司准备在5小时内生产甲、乙两种产品。甲、乙两种产品每生产1单位分别消耗2小时、1小时。又根据市场需求信息，乙产品的产量应该至少是甲产品产量的3倍。已知甲、乙两种产品每销售1单位的利润分别为3百元和1百元。请问：在5小时内，甲、乙两种产品各生产多少单位，才能够使得总销售利润最大？要求：1、建立该问题的线性规划模型。2、用图解法求出最优解和最大销售利润值，并写出解的判断依据。如果不存在最优解，也请说明理由。解：1、(1)设定决策变量： 设甲、乙两种产品分别生产x1、x2单位 。(2)目标函数： max z=2 x1+x2 (3)约束条件如下：求解过程如下：1

2、.各个约束条件的边界及其方向如图1中直线和箭头所示，其中阴影部分为可行域，由直线相交可得其顶点A(5,0)、B(1,3)和O(0,0)。2. 画出目标函数的一条等值线CD：2x1+x2=0，它沿法线向上平移，目标函数值z越来越大。3. 当目标函数平移到线段AB时时，zMax z。2、该问题中约束条件、目标函数、可行域和顶点见图1所示，其中可行域用阴影部分标记，不等式约束条件及变量约束要标出成立的方向，目标函数只须画出其中一条等值线，顶点用大写英文字母标记。2x1+x25O54 3 2 1-1 x2-2 -1 0 1 2 3 4 5x1图1A(5,0)B(1,3)CDMaxx23 x1结论：本题

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

4、购买费与维修费如表2所示。要求：（1）建立某种图论模型；（2）求出最少总支出金额。表2解：（1）建立图论最短路问题模型。设点Vi表示第i年年初，虚设一个点V6，表示第五年年底；弧(Vi, Vj)表示第i年初购进一台设备一直使用到第j年初(即第i-1年年底)再卖掉并获得残值收入；171741282741v6v527v4v2v31616988v110959图2弧(Vi, Vj)上的权数表示第i年初购进一台设备，一直使用到第j年初所需支付的购买、维修及抵扣残值收入以后的全部费用（单位：万元）。例如：弧(V1, V4)上的费用权数30=11+(5+6+8)-3=27(万元)。模型如图2所示：（2）用D

5、ijkstra法求解从V1到V6的最短路。给起点V1标号（0,v1）；1.I=v1 ; J=v2,v3,v4,v5,v6 弧集合v1,v2、v1,v3 、v1,v4 、v1,v5 、v1,v6 s12=l1+b12=0+8=8;s13=l1+b13=0+16=16;s14=l1+b14=0+27=27; s15=l1+b15=0+41=41;s16=l1+b16=0+59=59mins12,s13,s14,s15,s16=min8,16,27,41,59=8= s12=l2 给v2标号（8,v1）2.I=v1,v2 J= v3,v4,v5,v6 弧集合v1,v3 、v1,v4 、v1,v5 、

6、v1,v6 、 v2,v3、v2,v4、v2,v5、v2,v6s23=l2+b23=8+8=16;s24=l2+b24=8+16=24;s25=l2+b25=8+27=35;s26=l2+b26=8+41=49mins13,s14,s15,s16,s23,s24,s25,s26=min16,27,41,59,16,24,35,49=16= s13或s23=l3 ， 任选一个s13，选择给v3标号（16, v1）。3.I=v1,v2,v3 J=v4,v5,v6 弧集合v1,v4、v1,v5 、v1,v6 、v2,v4、v2,v5 、v2,v6、v3,v4、v3,v5 、v3,v6 s34=l3+

7、b34=16+9=25; s35=l3+b35=16+27=35;s26=l2+b26=8+41=49 mins14,s15,s16,s24,s25,s26,s34,s35,s36=min27,41,59,24,35,49,25,35,49=24=s24=l4 给v4标号（24,v2）4.I=v1,v2,v3,v4 J=v5,v6 弧集合 v1,v5 、v1,v6 、v2,v5 、v2,v6、 v3,v5 、v3,v6、v4,v5 、v4,v6 s45=l4+b45=24+9=33; s46=l4+b46=24+17=41 mins15,s16,s25,s26,s35,s36,s45,s46=

8、min41,59,35,49,35,49,33,41=33=s45=l5 给v5标号（33,v4）5.I=v1,v2,v3,v4,v5 J=v6 弧集合 v1,v6、v2,v6、v3,v6、v4,v6、v5,v6 s56=l5+b56=33+10=43 mins16,s26,s36,s46,s56=min59,49,49,41,43=41=s46=l6 给v6标号（41,v4）6.I= J= 计算终止。由终点v6标号反向追踪，可得到v1到v6的最短路：v1v2v4v6,长度为l6=41,即5年内该设备的最小总支出金额为41万元。B.考题复习知识点：1.最短路问题求解的基本思想？请查阅课本或其他

9、参考书籍，自行简答总结。2.掌握用上述“Dijkstra标号法”求解的步骤和处理方法，考试时书写格式请参照本样题。3.掌握最短路确定的反向追踪方法和最短距离。考试题比此题计算量小。4.掌握图论问题建模的程序，会说明图论模型各组分（弧或边、节点、权数）的实际涵义。（三）动态规划“复合系统工作可靠性问题”建模和求解）A正考样题及其解答：某厂设计一种电子设备，由三种元件D1、D2、D3组成。已知这三种元件的单位价格、单位重量和可靠性如表4，要求在设计中所使用元件的费用不超过105元，重量不超过21克。问应如何设计使设备的可靠性达到最大。解：（1）建立动态规划模型按元件的种类数划分阶段，k1,2,3。

10、每阶段阶段第k种元件并联几个。状态变量xk表示第k阶段初尚未使用的费用；状态变量yk表示第k阶段初剩余的可增加重量。显然x1=105,y1=21,xk0,yk0 。决策变量uk表示第k阶段元件Dk并联的个数。允许决策集合：ck表示第k种元件的单位费用；wk表示第k种元件的单位重量；状态转移方程：xk+1 xk-ckuk ； yk+1yk-wkuk 。阶段指标函数dk(uk)表示元件Dk正常工作的概率 ；最优指标函数fk(xk ,yk)表示从元件Dk到元件D3 正常运行的最大概率。逆序解法的基本方程如下：（2）用逆序解法求解第3阶段，k=3第2阶段，k=2 第1阶段，k=1由于x1=105,y1

11、=21,故问题为求出f1(105,21)即可。而状态转移图如下：结论： 求得u*1=1, u*2=2,u*3=2为最优方案，即D1、 D2、 D3三种元件分别并联1个、2个和2个。总费用为100元，总重量为21克，可靠性为0.648。B.正考复习知识点：1.会按照样题解答那样分六步建立动态规划模型。文字说明方面：准确说明各种变量的实际涵义；数学表达方面：能正确、规范地写出逆序解法的基本方程，阶段变量必须逆着写取值，明确边界条件；在建模时对取值明确的状态变量应该说明其具体值；会以规范的集合语言写出允许决策集合的具体形式；具体写出状态转移方程函数形式；写出阶段指标函数的数学表达式。考试题目比此题的

12、计算量要小，而且未必会考两个状态的情形。2.比照样题中的解答步骤来书写答题过程，会绘制“状态转移图”并以此得出结论，会得出全过程最优指标函数值并给出依据。3.清华大学教材编写组编写运筹学第三版237-238页例8计算过程可以参考（但fk(sk)中xk的范围有错，请按照课件第四章50-53张例4.6.1来改正，答题格式也须参照后者。（四）线性目标规划或运输问题的建模和求解A.正考样题非标准运输问题的建模与“表上作业法求解”有三个发电站产地B1，B2，B3需要从两个煤矿A1，A2购买煤炭，各自的产量、需求量以及每万吨煤炭的运价（千元）如表5所示。问如何调运煤炭，使得总运输费用最小？表5 产销平衡表

13、和单位运价表 发电站Bj煤矿AiB1B2B3产量（万吨）A12362236A21577212每月对煤的需求量（万吨）315要求：（1）请建立该问题的线性规划模型，如果有必要再化为标准问题。（2）用表上作业法求解：用最小元素法确定初始方案；用闭回路法或者位势法验证初始方案是否最优？如果非最优，请用闭回路法调整，直至求出最优方案。解：（1）设产地Ai（i=1,2）调运到销地Bj（j=1,2,3）的煤炭为xij万吨，可建立以下模型： （2）因为总产量8万吨（=6+2）小于总需求量9万吨（=3+1+5），所以本问题不是标准运输问题。增加一个虚拟产地A3，它的单位运价c31=c32=c33=0，产量为9

14、-8=1（万吨）。（3）第一步：用最小元素法确定初始方案（方案可能有以下三种，随着添加0位置不同而不同）。 或或方法二：伏格尔法（本题用此法求出的初始基可行解就是最优解） 第二步：求非基变量检验数，验证初始方案(最小元素法求得的第一种初始方案)是否最优。法一：用位势法求检验数。求解见表6所示： 表6销地产地B1B2B3UiA10230620230A20152377621-8A300-39000-23Vj236223 因为min(22,23,32,33|ij0)=32=-390，所以初始方案并非最优方案，需进一步调整，x32为进基变量。法二：用闭回路法求检验数22=77-15+23-62=23;23=21-15+23-23=6;33=0-0+23-23=0；32=0-0+23-62=-39（注：图中画出了非基变量x32的闭回路）；因为min(22,23,32,33|ij0)32=-390，所以方案二就是唯一最优方案。决策结论：产地A1向销地B1调运煤炭1万吨，向销地B3调运煤炭5万吨；产地A2向销地B1调运煤炭2万吨；销地B2的需求量由虚拟产地A3来满足，实际上它的需求量1万吨完全未得到满足。最小总运费=231+062+235+152+01=168（千元）。B.正考复习知识点：（1）本题是“销大于产”的非标准问题，但考试时也有可能考“产大于销”的非标准化问题。那么