10MW 10
2 5
140 0 20
15MW 15 15 1 4 6 8
15 30 45
40MW
3 7 20
图4
11.有A、B、C、D四项任务需分派给甲、乙、丙、丁四个人去做，这四个人都能承担上述四项任务，但完成各项任务所需时间如下表所示。问应如何分派任务可使完成任务的总工时最少？要求①建立该问题的线性规划模型。②用匈牙利法求出其最优解。 任务 A B C D 人 甲 乙 丙 丁 9 12 8 7 17 7 17 9 16 14 14 11 7 16 17 9 12.设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可选择，而进口港又有三个可选择，进口后可经由两个城市到达目的地，其间的运输费用如图所示（单位：百元），试把该问题描述成一个多阶段决策问题，并用动态规划方法求解。 70 C 1 10 B1 40 40D 20 1 30 60 30 40 C20 2 A B 230 E 40 30 30 40 10
D 30 B 2 50 C 3 3
13.试用表上作业法求解下面运输问题的最优解。（要求用行列差值法给初始解，用位势法求检验数。）
销地 B1 B2 B3 供应量 产地 A1 A2 需求量 6 8 3 4 5 3 2 7 3 4 5 第6页共13页
参考答案
一、判断题：
1.√ 2.╳ 3.√ 4.√ 5.√ 6.√ 7.√ 8.√ 9.╳ 10.√ 11.╳ 12.√ 13.╳ 14.√ 15.╳ 16.√ 17.√ 18.√ 19.╳ 20.╳ 21.√ 22.√ 23.╳ 24.√ 25.╳ 26.╳ 27.√ 28.√ 29.√ 30.√ 31.√ 32.╳ 33.√ 34.╳ 35.√ 36.╳ 二、建模题：
1.见教材1.2节线性规划问题建模。
2.解：设在100cm宽的薄铜板上能切割40㎝宽的薄铜板U个，32㎝宽的薄铜板V个，24㎝宽的薄铜板W个，则有以下切割方式：
U V W 余料<24
① 2 0 0 20 ② 1 1 1 4 ③ 1 0 2 12 ④ 0 3 0 4 ⑤ 0 2 1 12 ⑥ 0 1 2 20 ⑦ 0 0 4 4
设xj为上述第j种切割方式切割100㎝铜板数，有：
Min Z?20x1?4x2?12x3?4x4?12x5?20x6?4x7?2x1?x2?x3 ?50?? x2 ?3x4?2x5?x6 ?110?? x2?2x3 ? x5?2x6?4x7 ?75?xj?0(j?1,?7)?3.其对偶问题为：
maxw?8y1?15y2?30y3 ?2y1?8y2 ?5 ? 5y?4y?4 ?23 或 ??7y1?4y2?6y3?3 ?y?0,y?0,y为自由变量 23?1maxw?8y1?15y2?30y3 ?2y1?8y2 ?5 ? ?5y?4y?4 ?23 ??7y1?4y2?6y3?3 ?y?0,y?0,y为自由变量 23?14.见教材2.1对偶规划。
三、填空题： 1.
T
1) X＝(0,0,0,0.5,10,0,1.25)。 2) Z＝110。
3) y1,y2,y3分别为甲、乙、丙三种资源出售带来的价值增值（或利润）。 4) Y=(y1，y2，y3)=(1，0，10)。 5) 甲、丙资源。
提示：若原问题是Max型，则对偶变量的值为相应松弛变量检验数的负值。
T
2. 1） （0,0,0,8000,3000） 2） x5 3750 3） 单位列向量 4） x4， x1 5）-1/2 6） 1500 7） 0 -3 -2 提示：求该题时注意：
（1）单纯形表中基变量的系数列向量为单位列向量，检验数为0。
第7页共13页
（2）根据单纯形表的计算公式Rj?cj?CBPj求出各变量xj的检验数，由Z?CBXB计算目标函数的值或某个基变量的值。
（3）在最优单纯形表中，松驰变量x4,x5两列系数向量为当前基的逆矩阵B-1，由XB?B?1b（向量b为初始单纯形表中方程右边常数向量），也可求出基变量的值。如此题：
?1-3/2??8000??3500? XB?B?1b=?=??????01/2??3000??1500?四、计算题：
1.见教材1.4.5 单纯形表。
2.解：把问题分为4个阶段，A→B（可选B1,B2）, B→C（可选C1,C2）, C→D（可选D1,D2）, D→G各为一个阶段。
设Sk为每一阶段的起点，xk为第k阶段的决策变量，状态转移方程为：SK+1＝xk(Sk)。k=1,2,3,4。阶段指标函数dk(Sk,xk)为Sk到xk(Sk)的距离值，最优指标函数fk(Sk)为第k阶段状态为Sk时，从Sk到终点G的最短距离值。指标函数递推方程：fk(Sk)?min{fk?1(Sk?1)?dk(Sk,xk)}，k=3,2,1
xk边界方程为：f4(S4)?d4(S4,G)。 下面列表计算如下： k=4时： x4 d4(S4,G) f4(S4) x4 S4 G D1 D2 k=3时： x3 S3 C1 C2 C3 k=2时： x2 S2 B1 B2 k=1时： x1 S1 A
第8页共13页
30 40 30 40 x4 D1 G G d3(S3,x3)?f4(S4) D1 0+30 40＋30 － D2 － 30＋40 0＋40 f3(S3) 30 70 40 D1或D2 D2 x4 C1 C2 x4 B2 d2(S2,x2)?f3(S3) C1 70+30 C2 60+70 10＋70 C3 － 50＋40 f2(S2) 100 80 d1(S1,x1)?f2(S2) B1 20+100 B2 30＋80 f1(S1) 110 最优路线有两条：A→B2→C2→D1→G或A→B2→C2→D2→G，最短距离值为110。 3.①产大于销，增添假想销地B4，列出产销平衡表，用行列差值法给初始解如下表示：
销地 产地 A1 A2 A3 需求量 列差值
②用位势法求初始可行解对应的各非基变量的检验数：
对基变量有：Rij=cij－(ui+vj)=0，求出行、列位势，如表示：
销地 产地 A1 A2 A3 需求量 列位势
③利用Rij=cij－(ui+vj)求出非基变量的检验数：R11=5，R13=5，R14=3，R21=1，R32=－1，R34=1。 ④选x32为入基变量，作闭回路调整，调整量为0，如表示： ⑤ 销地 B1 B2 B3 B4 行位势 产地 A1 A2 A3 列位势
再次利用Rij=cij－(ui+vj)求出非基变量的检验数： R11=4，R13=4，R14=2，R21=1，R22=1，R34=1。
当前调运方案为最优方案，如上表示，最小运费Z＝2×8＋3×5＋1×4＝35。
4.用T、P标号算法：
①给v1点标P标号，其他点标T标号，为＋∞。
②从v1点出发，修改v2、v3 、v4点的T标号，并把其中最小者改为P标号。 T(v2)=4=P(v2)，T(v3)=6，T(v4)=5= P(v4)。
③从刚刚获得P标号的点v2出发，可达v3,v5（与其相邻的且还未获得P标号的点）,修改其T标号，并把最小T标号v3,v5改为P标号。
T(v3)=min{6，p(v2)+d23}=min{6,4+1}=5=P(v3)，T(v5)=11。 ④依此类推，各点的P标号如图所示。
第9页共13页
B1 4（×） 3（×） 1（4） 4 2,2,- B2 2（8） 5（0） 3（×） 8 1,1,3 B3 5（×） 3（5） 2（0） 5 1,1,2 B4 0（×） 0（2） 0（×） 2 2,- 产量 8 7 4 行差值 2,2,3 3,0,2 1,1,- B1 4（×） 3（×） 1（4） 4 v1=－1 B2 2（8） 5（0） 3（×） 8 v2=2 B3 5（×） 3（5） 2（0） 5 v3=0 B4 0（×） 0（2） 0（×） 2 v4=－3 产量 8 7 4 行位势 u1=0 u2=3 u3=2 4（×） 3（×） 1（4） v1=0 2（8） 5（×） 3（0） v2=2 5（×） 3（5） 2（0） v3=1 0（×） 0（2） 0（×） v4=－2 u1=0 u2=2 u3=1 从v1到v7的最短路为：v1 →v2→v3→v5→v7或v1 →v2→v3→v6→v5→v7，距离为16。
4 v 2 7 10
4 v5 1 6 5 5
6 v 1 v 7 v 3 1 0 4 v6 8 2 5
9 5 v 4
5
5.见教材1.4.5 单纯形表。
6.解：由题意有：α＝5000元，β＝2000元
16 SL??????50005000?20002?0.714
由表中的累计概率可知：?p(x)?0.40?x?0??????p(x)?0.75
x?03最优决策是订购3箱。
获利期望值：E[C(Q)]＝－2000×3×0.05＋（5000－2000×2）×0.1＋（5000×2－2000×1）×0.25＋5000×3×0.6＝10800元。 同理可计算出最小损失期望值为2950元。
??2y2?17.解：（1）其对偶问题为：??y1 ?y2?5?y ?2y?62?1??yj?0,j?1,2min W?8y1?12y2?2y1 ?2y2?2
（2）设对偶问题的松驰变量为ys1，ys2，ys3，ys4，把y1*?4,y2*?1代入对偶问题中的约束方程，知ys1≠0，ys2≠0，由互补松驰性有：x1=x2=0。
又由y1*?4,y2*?1，均不等于0，由互补松驰性知原问题的两个约束对应的松驰变量
?x3+x4=8xs1＝0，xs2＝0，则原问题约束方程可化为：?，解得x3＝4，x4＝4。
x+2x=12?34即原问题最优解为：X＝（0,0,4,4），Z＝44。
8.解：设给每一个地区设置一个销售点为一个阶段，共三个阶段。 xk为给第k个地区设置的销售点数。 Sk为第k阶段还剩余的销售点数，S1＝4 状态转移方程为：Sk+1=Sk－xk
第10页共13页
*
T