(一)线性规划建模与求解B.样题: 活力公司准备在 5小时内生产甲、乙两种产品。

甲、乙两种产品每生产1单位分别消耗2小时、1小时。

又根据市场需求信息，乙产品的产量应该至少是甲产品产量 的3倍。

已知甲、乙两种产品每销售1单位的利润分别为 3百元和1百元。

请问：在5小时内，甲、乙两种产品各生产多少单位，才能够使得总销售利润最大？要求：1、建立该问题的线性规划模型。

2、用图解法求出最优解和最大销售利润值， 并写出解的判断依据。

如果不存在最优解，也请说明理由。

解: 1、(1)设定决策变量：设甲、乙两种产品分别生产 X]、X 2单位 _____________max z=2 X 1+X 2 _________________________________12X 1 亠X 2 乞5 s.t X 2 _3X !X,X 2 _01所示，其中可行域用阴影部分 目标函数只须画出其中一条等值线，求解过程如下：1•各个约束条件的边界及其方向如图 1中直线和箭头所示，其中阴影部分为可 行域，由直线相交可得其顶点 A(5,0)、 B(1,3)和 0(0,0)。

2. 画出目标函数的一条等值线 CD :2x 什X 2=0，它沿法线向上平移，目标函数 值z 越来越大。

3. 当目标函数平移到线段 AB 时时，z ⑵目标函数：.(3)约束条件如下:2、该问题中约束条件、目标函数、可行域和顶点见图 标记，不等式约束条件及变量约束要标出成立的方向， 顶点用大写英文字母标记。

-2 -1X 2> 3 X 4 B(1,3)3图1X25；A(5,O)T Max z 。

1MaX 2结论：本题解的情形是：无穷多最优解，理由:目标函数等值线z=2 X1+X2与约束条件2 X]+x?w 5的边界平行。

甲、乙两种产品的最优产量分别为(5,0)或(1,3)单位；最大销售利润值等于_5_百元。

(二)图论问题的建模与求解样题A.正考样题(最短路问题的建模与求解，清华运筹学教材编写组第三版267-268页例13)某企业使用一台设备，每年年初，企业都要做出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。

但是变卖旧设备可以获得残值收入，连续使用1年、2年、3年、4年以上卖掉的设备残值分别为8万元、6万元、3万元和0万元。

试制定一个5年的更新计划，使总支出最少。

已知设备在各年的购买费与维修费如表2所示。

要求：(1)建立某种图论模型；(2 )求出最少总支出金额。

解: (1)建立图论一一最短路问题模型。

①设点V i表示第i年年初，虚设一个点V6，表示第五年年底；②弧(V i, V j)表示第i年初购进一台设备一直使用到第j年初(即第i-1年年底)再卖掉并获得残值收入；③弧(V i, V j)上的权数表示第i年初购进一台设备，一直使用到第j年初所需支付的购买、维修及抵扣残值收入以后的全部费用(单位：万元) 。

例如：弧(V i, V4)上的费用权数（2）用Dijkstra法求解从V i到V的最短路。

给起点V i标号（O M）;1」={V l} ； J={V 2,V3,V4,V5,V6} 弧集合{［V 1,V2】、［V 1,V3】、［V l,V4】、［V l,V5】、［V l,V6】} s i2=l i +b12=0+8=8;S13=l 1+b13=0+16=16;s 14=l1+b14=0+27=27;S15=l1 +b15=0+41=41;S16=l 1 +b16=0+59=59T min{s 12,S13,S14,S15,sw}=min{8,16,27,41,59}=8= s 12=12 •••给^2标号（8,vJ2.I={V 1,V2} J={ V 3,V4,V5,V6}弧集合{［V 1,V3］、［V1,V4］、［V1,V5］、［V1,V6］、［ V2,V3］、［V2,V4］、［V2,V5］、［V2,V6］}S23=l2 + b23=8+8=16；S24=l2+b24=8+16=24；S25=l2 + b25=8+27=35；S26=b+b26=8+41=49Tmin{s 13,S14,S15,S16,S23,S24,S25,S26}=min{16,27,41,59,16,24,35,49}=16= s 13 或s23=l3 , ••任选一一个S13，选择给V3标号（16, V1）。

3.I={V 1,V2,V3} J={V4,V5,V6} 弧集合{［V1,V4】、［V1,V5］、［V1,V6］、［V2,V4】、［V2,V5】、［V2,V6】、［V3,V 小［V3,V5］、［V3,V6］ }S34=l3 + b34=16+9=25; S35=l3+b35 = 16+27=35;S26 = l2+b26=8+41=49■/ min{s 14,S15,S16,S24,S25,S26,S34,S35,S36}=min{27,41,59,24,35,49,25,35,49}=24=s 24=14 •••给V4标号（24,V2）4.I={V 1,V2,V3,V4} J={v 5,V6} 弧集合{ ［V 1 ,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■/ min{s 15,S16,S25,S26,S35,S36,S45,S46}=min{41,59,35,49,35,49,33,41}=33=s 45=15 •••给V5 标号（33,V4）5.I={V 1,V2,V3,V4,V5} J={V6} 弧集合{ ［V1,V6】、［V2,V6】、［V3,V6】、［V4,V6】、［V5,V6】}S56=l5+b56=33+10=43 ■/ min{s 16,S26,S36,S46,S56}=min{59,49,49,41,43}=4仁s 46=l6 •••给V6标号（41,V4）6」=｛①｝ J=｛①｝ 计算终止。

由终点v 6标号反向追踪，可得到 v 1到v 6的最短路：v 1^v v^v 4^v 6,长度为l 6=41,即5 年内该设备的最小总支出金额为 41万元。

B.考题复习知识点：1•最短路问题求解的基本思想？请查阅课本或其他参考书籍，自行简答总结。

2•掌握用上述“ Dijkstra 标号法”求解的步骤和处理方法，考试时书写格式请参照本样题。

3•掌握最短路确定的反向追踪方法和最短距离。

考试题比此题计算量小。

4•掌握图论问题建模的程序，会说明图论模型各组分(弧或边、节点、权数)的实际涵义。

(三)动态规划——“复合系统工作可靠性问题”建模和求 解)A .正考样题及其解答 :某厂设计一种电子设备，由三种元件D i 、D v 、D 3组成。

已知这三种元件的单位价格、单位重量和可靠性如表 4,要求在设计中所使用元件的费用不超过105元，重量不超过21克。

问应如何设计使设备的可靠性达到最大。

k = 1,2,3。

每阶段阶段第k 种元件并联几个。

X k 表示第k 阶段初尚未使用的费用；状态变量 y k 表示第k 阶段初剩余的可X 1=105,y 1=21,x k >0,y k >0。

U k 表示第k 阶段元件D<并联的个数。

3 _3_-j tC k 表示第k 种元件的单位费用； w 表示第k 种元件的单位重量； ④ 状态转移方程： X k+1 = X k -C k U k ; y k+1 = y k -w k U k 。

⑤ 阶段指标函数d k (u k )表示元件D 正常工作的概率ck (u<) = 1-(1-P k )U< ;最优指标函数f k (X k ,y k ) 表示从元件 D 到元件D 正常运行的最大概率。

⑥ 逆序解法的基本方程如下：f k (X k ,yQ 二 max 」cl k (U k ) f k 1(X k 1,y k 1)1 k=3,2,1!u k D k (X k ,y k )f 4(&,y 4)=1(2 )用逆序解法求解 ①第3阶段，k=3f 3(X 3,y 3)=max也(匕)丨=1-(1-0.5)u 31~3 吕min [2^ ],[罟]②第2阶段，k=2解：(1)建立动态规划模型① 按元件的种类数划分阶段,② 状态变量 增加重量。

显然D k (x k , y k )= u kx k -、c ky k-、w k1 < u k < min([ 工 ],[ 工 ],kc kw k1 < u 3 <min([ 匕],[2±]c 3 w 3f2(X2, y2)二③第1阶段, f", yj =maxX2 -20 y2 -51<u2 <min([- ],[15k=1||[1- (1- 0.8) u2] f3(X2 —C2u2, y2 勺2氏) 4 ]) _maxz ([违严]，[于])],[[1-(1-0.9)u1]讦2(为-305,%-35)④由于X1=105,y1=21,故问题为求出f1(105,21)即可。

而f 1(105,21)=max 〔0.9 0.72,0.99 0.4 -0.648状态转移图如下:结论:求得u 1=1, u 2=2,u 3=2为最优方案，即 D 1、 D 2、 D 3三种兀件分别并联 1个、2 个和2个。

总费用为100元，总重量为21克，可靠性为0.648。

B.正考复习知识点：1. 会按照样题解答那样分六步建立动态规划模型。

文字说明方面：准确说明各种变量的实际涵义；数学表达方面：能正确、规范地写出逆序解法的基本方程， 取值，明确边界条件；在建模时对取值明确的状态变量应该说明其具体值； 语言写出允许决策集合的具体形式；具体写出状态转移方程函数形式；数学表达式。

考试题目比此题的计算量要小，而且未必会考两个状态的情形。

2. 比照样题中的解答步骤来书写答题过程，会绘制“状态转移图”并以此得出结论，会 得出全过程最优指标函数值并给出依据。

3.清华大学教材编写组编写 《运筹学》第三版237-238页例8计算过程可以参考（但f k （s k ） 中X k 的范围有错，请按照课件第四章 50-53张例461来改正，答题格式也须参照后者。

（四）线性目标规划或运输问题的建模和求解有三个发电站产地 B 1, B 2, B 3需要从两个煤矿 A 1, A ?购买煤炭，各自的产量、需求量 以及每J (105, 21) max“ 105 20 15 .21 5 4 ”1 <u 1 <min([ _________ 站 • • ],[ § • • •])max 0.9 f 2 (75,18),0.99 <u 1 <2],[ --------- ------- [1- (1-0.9) u 1] ,f 2 (105 「30 u ’，21 _3u Jf 2 (45,15)]f 2(75,18)f 2(45,15)f 3(60,14)0.8)]十3(75「15口2,18「4±)U 2max[1- (11 <u 2<min([ 75 201,[ 18自)」154|0.8 f 3 (60,14),0.96[1- (1- 0.8) u 2] f 3(45f 3(45,10),0.992 u2max1 <U2 <3max45 2015 51 «2 <min([ 歹 ],【_^])丄 0.8 f 3(30,11) | -0.8 f 3(30,11) max u21 <umax [1- (1- 0.5) u 希([孰敦 ],[]二 max (0.5, 1叫<2f 3 (30, 6)]-15 u 2,15 - 4u 2)0.75) = 0. 75max[1- (1- 0.5) 4510 ■*' ’<min([酊],[丁])max [ 1- (1- 0.5) 11 <u 3 <min([竺],[£])3205 f 3 (30 ,11 ) =max 30 11 [ 1- (1- 0.5)1<u3<min([20- ],[Tf 2(45,15) =0.8f 3(30,11) =0.8 0.5 =0.4f 2(75,18)=max0.8 0.75,0.96 0.75,0.992 0.5 - 0.72f 3 (45 , 10 )1 <uf 3 (30 , 6)二],[u3]=max^ 0.5, 0.75 ) = 0.75]=max( 0.5) = 0 .5u3=1u3]=max( 0.5) = 0.5u3 =1阶段变量必须逆着写会以规范的集合写出阶段指标函数的 A.正考样题非标准运输问题的建模与“表上作业法求解”阶段3岂 a 』万吨煤炭的运价（千元）如表5所示。