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