运筹学集合(4)

s. t. 3 x1 + x2 + x3+ x4 = 60 x 1- x 2 +2 x 3 + x5 = 10 x 1+ x 2- x 3 + x6 = 0

x 1, x 2 , x 3， x4、 x5、 x6，≥0……………3分 建初始单纯形表，进行迭代运算： ……………………… …9分

CB 0 0 0 ?1 0 2 0 ?2 0 2 -1 ?3 x4 x1 x2 x4 x1 x6 Xb x4 x5 x6 b’ 60 10 20 0 30 10 10 20 10 15 5 25 2 x1 3 [1] 1 2* 0 1 0 0 0 1 0 0 -1 x2 1 -1 1 -1 4 -1 [2] 1* 0 0 1 0 1 x3 1 2 -1 1 -5 2 -3 -3 1 0.5 -1.5 -1.5 0 x4 1 0 0 0 1 0 0 0 1 0 0 0 0 x5 0 1 0 0 -3 1 -1 -2 -1 0.5 -0.5 0 x6 0 0 1 0 0 0 1 0 -2 0.5 0.5 θ 20 10* 20 7.5 --- 5* -1.5 -0.5 由最优单纯形表可知，原线性规划的最优解为： ( 15 , 5 , 0 )T …2分

最优值为： z*=25。………2分

五、求解运输问题。共计18分 解：

（1）最小元素法：（也可以用其他方法，酌情给分） 设xij为由Ai运往Bj的运量（i=1,2,3; j=1,2,3,4）, 列表如下：

销 地 B1 B2 B3 B4 产 量 产 地 1 25 25 2 20 5 25 3 15 30 5 50 销 量 15 20 30 35 100

16

……………3分 所以，基本的初始可行解为：x14 =25； x22=20 ； x24 =5 ；

X31 =15； x33 =30； x34=5

其余的xij=0。 …………3分

（2）求最优调运方案：

1会求检验数，检验解的最优性：?11=2；?12=2；?13=3；

?21=1；?23=5；?32= - 1…………3分

2会求调整量进行调整：=5 …………2分

销 地 B1 B2 B3 B4 产 量 产 地 1 25 25 2 15 10 25 3 15 5 30 50 销 量 15 20 30 35 100 …3分

3再次检验 …………2分

4能够写出正确结论

解为：x14=25 ； x22 =15 ； x24 =10 x31 =15， x32 =5 x33=30

其余的xij=0。 ……1分

最少运费为： 535 ………1分。

六、灵敏度分析。共计8分 （1）（4分） ??8/3?2/3???10/3?max,??c?min????1 1/61/6?2/3????

?4??c1?5,6?10?4?c1??c1?10?5?15

（2）（4分） ?200/3????100/3?100?max??,??b?min,????1 5/3??2????2/3

?40??b1?10

七、建动态规划模型。共计8分

解：(1)设阶段变量k表示年度，因此，阶段总数n=3。

(2)状态变量sk表示第k年度初拥有的完好机床台数， 同时也是第 k–1 年度末时的完好机床数量。

(3)决策变量uk，表示第k年度中分配于生产产品 p1 的机器台数。于是sk– uk便为该年度中分配于生产产品 p1的机器台数．

（4） 状态转移方程为

17

sk?1?0.35uk?0.65(sk?uk)（5）允许决策集合,在第 k 段为 (sk)?{uk0?uk?sk}Uk（6）目标函数。设gk(sk,uk)为第k年度的产量，则

gk(sk,uk) = 45uk + 35(sk–uk) ,

因此，目标函数为 3 ??gk(sk,uk)Rk i?k（7）条件最优目标函数递推方程。

fk (sk)?max(uk(sk))u?U

令fk(sk)表示由第k年的状态sk出发，采取最优分配方案到第3年度结束这段时间的产品产量，根据最优化

原理有以下递推关系： {[45 uk?35(sk?uk)]?fk?1[0.35uk?0.65(sk?uk)]}（8）.边界条件为

f3?1(s3?1)?0

八、解决对策问题。共10分

（1）益损矩阵如下表所示：……3分

销 售 S1 S2 S3 S4 订 购 500 1000 1500 2000 A1 500 1500 1500 1500 1500 A2 1000 0 3000 3000 3000 －1500 A3 1500 1500 4500 4500 －3000 A4 2000 0 3000 6000 （2）悲观法：A1 ，订购500公斤。……2分 （3）后悔矩阵如下表所示：……3分

S1 S2 S3 S4 最大后悔值 A1 0 1500 3000 4500 4500 A2 1500 0 1500 3000 3000 A3 3000 1500 0 1500 3000 A4 4500 3000 1500 0 4500 按后悔值法商店应取决策为A2或A3 ，即订购1000公斤或1500公斤。……2分 九、求网络计划图的各时间参数。（8分） 14 8 14 0 5 8 2 5 8 9 3 3 11 0 0 260 4 6 1 4 7 26 0 7 11 7 2 8 3

6 7 3 kk

9 18 18 0 18

工序 工序 代号 时间 1-2 1-3 1-4 2-4 2-5 3-4 3-6 4-5 4-6 4-7 5-7 6-7 8 7 6 3 5 2 3 3 7 4 9 8 最早开 最早完 最晚开 最晚完 机动 工时间 工时间 工时间 工时间 时间 0 0 0 8 8 7 7 11 11 11 14 18 8 7 6 11 13 9 10 14 18 15 23 26 0 2 5 8 9 9 15 11 11 22 17 18 8 9 11 11 14 11 18 14 18 26 26 26 0 2 6 0 1 2 8 0 0 11 3 0

关键问题是：①→②；2→④；④→⑤；④→6；6→⑦ 关键线路是： 1

评分标准：①能正确给各顶点标号并填表......................4分

②正确写出关键问题.............. 2分

③正确画出关键线路............. ２分

十、用标号法求v1 到 v6 的最短路。（6分）

(4,v1)

V2 6

4 7 (0,0) V1 2

8 3

V3 (6,v2) 7 2 4 1 6 7 V4 (9,v3) (10,v2) 5 1 19 V5 2 (10,v4) (11,v2) V6 (12,v5) (14,v4)

最短路为：v1,v2,v3,v4,v5,v6 长度为：12

正确标号：4分；正确写出结论：2分

20

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库运筹学集合(4)在线全文阅读。