(一)线性规划建模与求解
B.样题：活力公司准备在5小时内生产甲、乙两种产品。甲、乙两种产品每生产1
单位分别消耗2小时、1小时。又根据市场需求信息，乙产品的产量应该至少是甲产品产量的3倍。已知甲、乙两种产品每销售1单位的利润分别为3百元和1百元。请问：在5小时内，甲、乙两种产品各生产多少单位，才能够使得总销售利润最大？
要求：1、建立该问题的线性规划模型。
2、用图解法求出最优解和最大销售利润值，并写出解的判断依据。如果不存在最优解，也请说明理由。
解：1、(1)设定决策变量： 设甲、乙两种产品分别生产x1、x2单位 。
(2)目标函数： max z=2 x1+x2 ?(3)约束条件如下：s..t?x2?3x1?2x1?x2?5?x,x?0?12
2、该问题中约束条件、目标函数、可行域和顶点见图1所示，其中可行域用阴影部分标记，不等式约束条件及变量约束要标出成立的方向，目标函数只须画出其中一条等值线，顶点用大写英文字母标记。 求解过程如下： x2 A(5,0) 1.各个约束条件的边界及其方向如图5 1中直线和箭头所示，其中阴影部分为可 行域，由直线相交可得其顶点A(5,0)、4 x2≥3 x1 B(1,3)和O(0,0)。
2. 画出目标函数的一条等值线CD： B(1,3) 3 C 2x1+x2=0，它沿法线向上平移，目标函数
Max 值z越来越大。 2
3. 当目标函数平移到线段AB时时，z2x1+x2≤5
→Max z。 1
O -2 -1 0 1 2 3 4 5 x1 -1 D 图1
结论：本题解的情形是： 无穷多最优解 ，理由： 目标函数等值线z=2 x1+x2与约束条件2 x1+x2≤5的边界平行 。甲、乙两种产品的最优产量分别为 (5,0)或(1,3)单位；最大销售利润值等于 5 百元。
（二）图论问题的建模与求解样题
A.正考样题（最短路问题的建模与求解，清华运筹学教材编写组第三版267-268页例
13）某企业使用一台设备，每年年初，企业都要做出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。但是变卖旧设备可以获得残值收入，连续使用1年、2年、3年、4年以上卖掉的设备残值分别为8万元、6万元、3万元和0万元。试制定一个5年的更新计划，使总支出最少。已知设备在各年的购买费与维修费如表2所示。要求：（1）建立某种图论模型；（2）求出最少总支出金额。
表2
解：（1）建立图论——最短路问题模型。
①设点Vi表示第i年年初，虚设一个点V6，表示第五年年底；
②弧(Vi, Vj)表示第i年初购进一台设备一直使用到第j年初(即第i-1年年底)再卖掉并获得残值收入；
③弧(Vi, Vj)上的权数表示第i年初购进一台设备，一直使用到第j年初所需支付的购买、维修及抵扣残值收入以后的全部费用（单位：万元）。例如：弧(V1, V4)上的费用权数30=11+(5+6+8)-3=27(万元)。
模型如图2所示： 59 27 28 41 16 17
8 9 10 8 9 v1 v3 v2 v6 v4 v5 17
16 27 41
图2
（2）用Dijkstra法求解从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=59
∵min{s12,s13,s14,s15,s16}=min{8,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] 、[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=l2+b26=8+41=49
∵min{s13,s14,s15,s16,s23,s24,s25,s26}=min{16,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+b34=16+9=25; s35=l3+b35=16+27=35;s26=l2+b26=8+41=49
∵min{s14,s15,s16,s24,s25,s26,s34,s35,s36}=min{27,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
∵min{s15,s16,s25,s26,s35,s36,s45,s46}=min{41,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 ∵min{s16,s26,s36,s46,s56}=min{59,49,49,41,43}=41=s46=l6 ∴给v6标号（41,v4）
6.I={Φ} J={Φ} 计算终止。
由终点v6标号反向追踪，可得到v1到v6的最短路：v1→v2→v4→v6,长度为l6=41,即5年内该设备的最小总支出金额为41万元。 B.考题复习知识点：
1.最短路问题求解的基本思想？请查阅课本或其他参考书籍，自行简答总结。
2.掌握用上述“Dijkstra标号法”求解的步骤和处理方法，考试时书写格式请参照本样题。 3.掌握最短路确定的反向追踪方法和最短距离。考试题比此题计算量小。
4.掌握图论问题建模的程序，会说明图论模型各组分（弧或边、节点、权数）的实际涵义。
（三）动态规划——“复合系统工作可靠性问题”建模和求解）
A．正考样题及其解答：某厂设计一种电子设备，由三种元件D1、D2、D3组成。已
知这三种元件的单位价格、单位重量和可靠性如表4，要求在设计中所使用元件的费用不超过105元，重量不超过21克。问应如何设计使设备的可靠性达到最大。 解：（1）建立动态规划模型
①按元件的种类数划分阶段，k＝1,2,3。每阶段阶段第k种元件并联几个。
②状态变量xk表示第k阶段初尚未使用的费用；状态变量yk表示第k阶段初剩余的可增加重量。显然x1=105,y1=21,xk>0,yk>0 。
③决策变量uk表示第k阶段元件Dk并联的个数。允许决策集合：
??x-?cy-?w?? ?1≤u≤min([ ],[],k=1,2???cwD(x, y)=?u ? ??xy??1≤u≤min([ ],[]cw?? ??ck表示第k种元件的单位费用；wk表示第k种元件的单位重量； ④状态转移方程：xk+1＝ xk-ck·uk ； yk+1＝yk-wk·uk 。
dk(uk)=1-(1-pk)uk；⑤阶段指标函数dk(uk)表示元件Dk正常工作的概率 最优指标函数fk(xk ,yk)
表示从元件Dk到元件D3 正常运行的最大概率。 ⑥逆序解法的基本方程如下： ??dk(uk)?fk?1(xk?1,yk?1)? k=3,2,1?fk(xk,yk)?uk?maxDk(xk,yk) ?? ?f4(x4,y4)?1（2）用逆序解法求解 ①第3阶段，k=3 f3(x3,y3)=maxd3(u3)??1-(1-0.5)u3?y??x1≤u3≤=min?[3 ],[3]? 5??20
②第2阶段，k=2 u2?f2(x2,y2)?max[1-(1-0.8)]?f3(x2?c2u2,y2?w2u2)???x?20y?5 1≤u2≤min([2 ],[2])154③第1阶段，k=1
u1? f1(x1,y1)?max[1-(1-0.9)]?f2(x1?30u1,y1?3u1)??x1?20?15y1?5?4?1≤u1≤min([ ],[]) 303④由于x1=105,y1=21,故问题为求出f1(105,21)即可。而
33kkkkj=k+1kj=k+1kkkkkk33333 f1(105,21)??[1-(1-0.9)u]?f2(105?30u1,21?3u1)?max?105?20?1521?5?4?1≤u≤min([ ],[])303
=max?0.9f2(75,18),0.99f2(45,15)?1≤u≤2
?[1-(1-0.8)u]?f3(75?15u2,18?4u2)?f(75,18)?max?75?2018?5? 21≤u≤min([ ],[])154 =max?0.8f3(60,14),0.96f3(45,10),0.992f3(30,6)?1≤u≤3 f2(45,15)??max[1-(1-0.8)u]?f3(45?15u2,15?4u2)???45?2015?51≤u≤min([ ],[])154
?0.8f3(30,11)??0.8f3(30,11) =maxu?1 f3(60,14)?max[1-(1-0.5)u]?max(0.5,0.75)?0.7560141≤u≤21≤u≤min([ ],[])205
max[1-(1-0.5)u]?max(0.5,0.75)?0.75 f3(45,10)?1≤u≤min([45101≤u≤2 ],[])205
f3(30,6)?max[1-(1-0.5)u]?max(0.5)?0.5306u=11≤u≤min([ ],[]) 205 f3(30,11)?max[1-(1-0.5)u]?max(0.5)?0.53011u=11≤u≤min([ ],[])205
f(45,15)?0.8f3(30,11)?0.8?0.5?0.4 2 f2(75,18)=max?0.8?0.75,0.96?0.75,0.992?0.5??0.72 f1(105,21)=max?0.9?0.72,0.99?0.4??0.648∴
状态转移图如下：
111222222333333333333
结论：
求得u*1=1, u*2=2,u*3=2为最优方案，即D1、 D2、 D3三种元件分别并联1个、2 个和2个。总费用为100元，总重量为21克，可靠性为0.648。 B.正考复习知识点：
1.会按照样题解答那样分六步建立动态规划模型。文字说明方面：准确说明各种变量的实际涵义；数学表达方面：能正确、规范地写出逆序解法的基本方程，阶段变量必须逆着写取值，明确边界条件；在建模时对取值明确的状态变量应该说明其具体值；会以规范的集合语言写出允许决策集合的具体形式；具体写出状态转移方程函数形式；写出阶段指标函数的数学表达式。考试题目比此题的计算量要小，而且未必会考两个状态的情形。
2.比照样题中的解答步骤来书写答题过程，会绘制“状态转移图”并以此得出结论，会得出全过程最优指标函数值并给出依据。
3.清华大学教材编写组编写《运筹学》第三版237-238页例8计算过程可以参考（但fk(sk)中xk的范围有错，请按照课件第四章50-53张例4.6.1来改正，答题格式也须参照后者。
（四）线性目标规划或运输问题的建模和求解
A.正考样题——非标准运输问题的建模与“表上作业法求解”
有三个发电站产地B1，B2，B3需要从两个煤矿A1，A2购买煤炭，各自的产量、需求量以及每万吨煤炭的运价（千元）如表5所示。问如何调运煤炭，使得总运输费用最小？
表5 产销平衡表和单位运价表
B1 B2 B3 发电站Bj 煤矿Ai A1 23 62 23 A2 15 77 21 3 1 5 每月对煤的需求量（万吨） 产量（万吨） 6 2 要求：（1）请建立该问题的线性规划模型，如果有必要再化为标准问题。（2）用表上作业法求解：用最小元素法确定初始方案；用闭回路法或者位势法验证初始方案是否最优？如果非最优，请用闭回路法调整，直至求出最优方案。 解：（1）设产地Ai（i=1,2）调运到销地Bj（j=1,2,3）的煤炭为xij万吨，可建立以下模型：
min z???cij?xij?23x11?62x12?23x13?15x21?77x22?21x23i?1j?123?x11?x12?x13?6?x?x?x?22223?21??x11?x21?3s.t.??x12?x22?1?x13?x23?5???xij?0(i?1,2;j?1,2,3)
（2）因为总产量8万吨（=6+2）小于总需求量9万吨（=3+1+5），所以本问题不是标准运输问题。增加一个虚拟产地A3，它的单位运价c31=c32=c33=0，产量为9-8=1（万吨）。 （3）第一步：用最小元素法确定初始方案（方案可能有以下三种，随着添加0位置不同而不同）。
?23(0)62(1)23(5)?6(1)(0)?(2)?157721??2(0) ? 0(1) 0 0???1(0) 3 1 5 (2) (0) (0) (0)?015??15??15??2??20??2?0?????? ?????1?或??1?或??1?方法二：伏格尔法（本题用此法求出的初始基可行解就是最优解）
?23(1)62(0)23(5)?6[0](5)(0)?(2)?157721??2[6](0)? 0 0(1) 0???1[0](0)?105? 3 1 5?2? [15] [77] [21]?? [ 8] (0) [ 2] (1) [ -] ??1?? [ -] ( 0) (0)第二步：求非基变量检验数，验证初始方案(最小元素法求得的第一种初始方案)是否最优。 法一：用位势法求检验数。
求解见表6所示： 表6 B1 B2 B3 Ui 销地 产地 A1 0 23 0 62 0 23 0 A2 0 15 23 77 6 21 -8 A3 0 0 -39 0 0 0 -23 Vj 23 62 23 因为min(σ22,σ23,σ32,σ33|σij<0)=σ32=-39<0，所以初始方案并非最优方案，需进一步调整，x32为进基变量。
法二：用闭回路法求检验数
?23(0)?(2)?15? 0(1)?62(1)77 023(5)??21?σ22=77-15+23-62=23;σ23=21-15+23-23=6;σ33=0-0+23-23=0； 0??σ32=0-0+23-62=-39（注：图中画出了非基变量x32的闭回路）；
因为min(σ22,σ23,σ32,σ33|σij<0)＝σ32=-39<0，，所以初始方案并非最优方案，需进一步调整，x32为进基变量。
第三步：求θ值，调整初始方案。 过程如下：
?0????2?1??? 1 ???? 5???以??X32作为进基变量。调整量θ＝min(1,1)=1，按照左图所示进行调
整，选择x31作为出基变量。
方案调整后为方案二（注：另一个基可行解），如下：
?105??2??? ??1??
用位势法可求出方案二非基变量检验数,见表7。 表7 B1 B2 B3 Ui 销地 产地 A1 0 23 0 62 0 23 0 A2 0 15 23 77 6 21 -8 A3 39 0 0 0 39 0 -62 Vj 23 62 23 因为非基变量检验数σ22,σ23,σ31,σ33>0，所以方案二就是唯一最优方案。
决策结论：产地A1向销地B1调运煤炭1万吨，向销地B3调运煤炭5万吨；产地A2向销地B1调运煤炭2万吨；销地B2的需求量由虚拟产地A3来满足，实际上它的需求量1万吨完全未得到满足。最小总运费=23×1+0×62+23×5+15×2+0×1=168（千元）。
B.正考复习知识点：
（1）本题是“销大于产”的非标准问题，但考试时也有可能考“产大于销”的非标准化问题。那么后一种情况该如何建模、标准化处理呢？请参看课件第一章“运输问题”的相应内容：96-98张。
（2）掌握运输问题求解的“表上作业法”（非标准问题标准化后才能求解）。确定初始方案请熟练掌握“最小元素法”即可，对“伏格尔法”不需要掌握；求方案的检验数请务必掌握“位势法”；对方案的优化改进，能找出进基变量的闭回路、确定θ值，并对方案加以优化调整。掌握变量检验数的经济含义（第三版84页最后两段）
（3）最优方案是唯一的，还是有多个呢？能给出判断依据，并且得出最优方案、最优目标函数值。