运筹学5至12章习题参考答案

运筹学5-12章参考答案

习题五

5.2 用元素差额法直接给出表5-52及表5-53下列两个运输问题的近似最优解．

A1 A2 A3 A4 Bj A1 A2 A3 Bj B1 19 14 25 7 15 B1 5 10 17 20 B2 16 13 30 8 25 B2 3 7 4 25 表5-52 B3 10 5 20 6 35 表5-53

B3 8 12 8 10 B4 21 24 11 10 20 B4 6 15 9 15 B5 9 7 23 4 5 Ai 16 24 30 Ai 18 30 10 42 【解】

双击演示过程→

表5-52。Z=824

表5-53结果如下，Z=495（最优值Z=480）

5.3 求表5-54及表5-55所示运输问题的最优方案． （1）用闭回路法求检验数（表5-54）

A1 A2 A3 bj B1 10 4 5 60 B2 5 3 6 60 表5-54

B3 2 1 4 40 B4 3 2 4 20 ai 70 80 30

（2）用位势法求检验数（表5-55）

A1 A2 A3 A4 bj B1 9 3 2 4 20 B2 15 1 10 5 15 表5-55

B3 4 7 13 8 50 B4 8 6 4 3 15 ai 10 30 20 40 解（1）最优表如下，最优值Z＝610

(2)解 最优表如下，最优值Z＝445

5.4 求下列运输问题的最优解

（1）C1目标函数求最小值； （2）C2目标函数求最大值

?3C1???6??11152?50?710?1413485?25C?2? ??13127??30?584520406030591520?6096??30 710??905040(3)目标函数最小值,B1的需求为30≤b1≤50, B2的需求为40，B3的需求为20≤b3≤60,A1不

可达B4 ，B4的需求为30．

?497??70?6532?20 ????84910??50【解】（1）

（2）

（3）先化为平衡表 A1 A2 A3 A4 bj B11 4 6 8 M 30 B12 4 6 8 0 20 B2 9 5 4 M 40 B31 7 3 9 M 20 7 3 9 0

B32 B4 M 2 10 M 30 ai 70 20 50 40 180 40 最优解如下表，最优值Z＝640

5.5（1）建立数学模型

设xij(I=1,2,3;j=1,2)为甲、乙、丙三种型号的客车每天发往B1，B2两城市的台班数，则

maxZ?40(80x11?65x12?60x21?50x22?50x31?40x32)?40x11?40x21?40x31?400?40x?40x?40x?6002232?12??x11?x12?5??x11?x22?10?x31?x32?15???xij?0(i?1,2,3;j?1,2)

(2)写平衡运价表

将第一、二等式两边同除以40，加入松驰变量x13,x23和x33将不等式化为等式，则平衡表为： B1 B2 B3 ai 80 65 0 5 甲 60 50 0 10 乙 50 40 0 15 丙 bj 10 15 5 为了平衡表简单，故表中运价没有乘以40，最优解不变 （3）最优调度方案：

即甲第天发5辆车到B1城市，乙每天发5辆车到B1城市，5辆车到B2城市，丙每天发10辆车到B2城市，多余5辆，最大收入为

Z=40（5×80+5×60+5×50+10×40）=54000（元）

5.6（1）设xij为第i月生产的产品第j月交货的台数，则此生产计划问题的数学模型为

minZ?x11?1.15x12?1.3x13?1.45x14?Mx21???0.98x44?x11?x21?x31?x41?50??x12?x22?x32?x42?40?x13?x23?x33?x43?60??x14?x24?x34?x44?80??x11?x12?x13?x14?65?x?x?x?x?65?21222324?x31?x32?x33?x34?65??x41?x42?x43?x44?65?xij?0,(i,j?1,?,4)?

（2）化为运输问题后运价表（即生产费用加上存储费用）如下，其中第5列是虚设销地费用为零，需求量为30。 1 2 3 4 5 ai 1 1 1.15 1.3 1.45 0 65 2 M 1.25 1.4 1.55 0 65 3 M M 0.87 1.02 0 65 4 M M M 0.98 0 65 bj 50 40 60 80 30 (3)用表上作业法，最优生产方案如下表： 1 2 3 4 5 ai 1 50 15 65 2 25 10 30 65 3 60 5 65 4 65 65 Bi 50 40 60 80 30 上表表明：一月份生产65台，当月交货50台；二月份交货15台,二月份生产35台，当月交货25台，四月份交货10台；三月份生产65台，当月交货60台，四月份交货5台，4月份生产65台当月交货。最小费用Z=235万元。

5.7 假设在例5－16中四种产品的需求量分别是1000、2000、3000和4000件，求最优生产配置方案．

【解】将表5-35所示的单件产品成本乘以需求量，为计算简便，从表中提出公因子1000．

工厂1 工厂2 工厂3 工厂4 用匈牙利法得到最优表

产品1 58 75 65 82 产品2 138 100 140 110 产品3 540 450 510 600 产品4 1040 920 1000 1120

第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2； 总成本

Z＝1000×(58＋920＋510＋110)＝1598000

注：结果与例5.15的第2个方案相同，但并不意味着“某列（行）同乘以一个非负元素后最优解不变”结论成立。

5.8 求解下列最小值的指派问题，其中第（2）题某人要作两项工作，其余3人每人做一项工作．

?126915??20121826?? （1）C＝??35181025???6101520??【解】最优解

1???1??,Z?43 X???1????1??26?25（2）C＝??20??2238333031414447455259565327?21?? 25??20?【解】虚拟一个人，其效率取4人中最好的，构造效率表为

甲 乙 丙 丁 戊 1 26 25 20 22 20 2 38 33 30 31 30 3 41 44 47 45 41 4 52 59 56 53 52 5 27 21 25 20 20 1????1???，最优值Z=165 最优解：X??1??1???1???

甲～戊完成工作的顺序为3、5、1、2、4，

最优分配方案：甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。

5.9 求解下列最大值的指派问题：

?109617??15141020?? （1）C＝??18131319???1681226??1??109617???15141020??1?? 最优解X???,Z?64 【解】 C＝??18131319??1?????1???1681226?（2）【解】

?96510??96?4－85??40???C＝?710912???710???615716???615??9868????98?7101160??0?12168110??5?????96740???2???101900???3??781080????0

51016?8516??91216??71616?6816??

9460?151110??5040??0200?7380???09460??08350??5151110??5140100???????25040???35041? ????3020040201??????07380????06270???0?5??3??8??01?01006??0100?1

?020?5225??0431??1??????11????1?或X??1?；Z?44 最优解X??????11???????1????1?第5人不安排工作或第1人不安排工作。

5.10 学校举行游泳、自行车、长跑和登山四项接力赛，已知五名运动员完成各项目的成绩（分钟）如表5-57所示．如何从中选拔一个接力队，使预期的比赛成绩最好．

【解】设xij为第i人参加第j项目的状态，则数学模型为

表5-57 成绩表(分钟) 甲 乙 丙 丁 戊 游泳 自行车 长跑 登山 20 15 18 19 17 43 33 42 44 34 33 28 38 32 30 29 26 29 27 28 minZ?20x11?43x12?33x13?29x14??28x54?x11?x12?x13?x14?1?x?x?x?x?1?21222324?x31?x32?x33?x34?1??x41?x42?x43?x44?1?x?x?x?x?1?51525354??x11?x21?x31?x41?x51?1?x12?x22?x32?x42?x52?1??x13?x23?x33?x43?x53?1?x?x?x?x?x?1?1424344454??xij?0或1,i?1,2,?,5;j?1,2,3,4接力队最优组合 乙 长跑 丙 游泳 丁 登山 戊 自行车

甲淘汰。预期时间为107分钟。

习题六

6.1如图6－42所示，建立求最小部分树的0－1整数规划数学模型。

【解】边[i，j]的长度记为cij，设

图6－42

?1边[i,j]包含在最小部分树内 xij???0否则

数学模型为：

minZ?cijxij??xij?5?i,j?x?x?x?2,x?x?x?2232434?121323?x34?x36?x46?2,x35?x36?x56?2??x12?x13?x24?x34?3 ?x?x?x?x?334354656??x23?x24?x46?x36?3??x12?x13?x24?x46?x36?4?x23?x35?x24?x46?x56?4,??x12?x13?x24?x35?x46?x56?5?x?1或0,所有边[i,j]?ij

6.2如图6－43所示，建立求v1到v6的最短路问题的0－1整数规划数学模型。 【解】弧(i，j)的长度记为cij，设

?1弧(i,j)包含在最短路径中 xij???0否则数学模型为：

minZ??cijxiji,j?x12?x13?1??x12?x23?x24?x25?0?x?x?x?x?013233435 ???,x24?x34?x45?x46?0?x?x?x?x?0?25354556?x46?x56?1???xij?1或0,所有弧(i,j)图6－43

6.3如图6－43所示，建立求v1到v6的最大流问题的线性规划数学模型。

【解】 设xij为弧（i,j）的流量，数学模型为

minZ?x12?x13?x12?x13?x46?x56?x?x?x?x232425?12 ??x13?x23?x34?x35??x24?x34?x45?x46?x25?x35?x45?x56???0?xij?cij,所有弧(i,j)

6.4求图6－41的最小部分树。图6-41（a）用破圈法,图6-41（b）用加边法。

图6－44

【解】图6-44（a），该题有4个解，最小树长为22，其中一个解如下图所示。

图6-44（b），最小树长为20。最小树如下图所示。

6.5 某乡政府计划未来3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。根据勘测，10个村之间修建公路的费用如表6-20所示。乡镇府如何选择修建公路的路线使总成本最低。

表6-20

1 2 3 4 5 6 7 8 9 10 两村庄之间修建公路的费用(万元) 1 2 12.8 3 10.5 9.6 4 8.5 7.7 13.8 5 12.7 13.1 12.6 11.4 6 13.9 11.2 8.6 7.5 8.3 7 14.8 15.7 8.5 9.6 8.9 8.0 8 13.2 12.4 10.5 9.3 8.8 12.7 14.8 9 12.7 13.6 15.8 9.8 8.2 11.7 13.6 9.7 10 8.9 10.5 13.4 14.6 9.1 10.5 12.6 8.9 8.8 【解】属于最小树问题。用加边法，得到下图所示的方案。

最低总成本74.3万元。

6.6在图6－45中，求A到H、I的最短路及最短路长，并对图(a)和(b)的结果进行比较。

图6－45

【解】图6－45(a):

A到H的最短路PAH={A,B,F,H},{A,C,F,H}最短路长22；A到I的最短路PAI={A,B,F,I},{A,C,F,I}最短路长21。 对于图6－45(b)：

A到H的最短路PAH={A,C,G,F,H},最短路长21；A到I的最短路PAI={A,C,G,F,I},最短路长20；

结果显示有向图与无向图的结果可能不一样。

6.7已知某设备可继续使用5年，也可以在每年年末卖掉重新购置新设备。已知5年年初购置新设备的价格分别为3.5、3.8、4.0、4.2和4.5万元。使用时间在1～5年内的维护费用分别为0.4、0.9、1.4、2.3和3万元。试确定一个设备更新策略，使5年的设备购置和维护总费用最小。

【解】设点vj为第j年年初购置新设备的状态，（i，j）为第i年年初购置新设备使用到第j年年初，弧的权为对应的费用（购置费＋维护费），绘制网络图并计算，结果见下图所示。

总费用最小的设备更新方案为：第一种方案，第1年购置一台设备使用到第5年年末；第二种方案，第1年购置一台设备使用到第2年年末，第3年年初更新后使用到第5年年末。总费用为11.5万元。

6.8图6－46是世界某6大城市之间的航线，边上的数字为票价（百美元），用Floyd算法设计任意两城市之间票价最便宜的路线表。

【解】教师可利用模板求解：data\\chpt6\\ch6.xls

L1 v1 v2 v3 v4 v5 v6 v1 0 8.8 9 5.6 8 6 v2 8.8 v3 9 v4 5.6 v5 8 v6 6 0 10 5 4 10 0 3 5 100 4 3 0 4.8 14 12 100 0 9 0 L2 v 1 v2 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v2 8.8 v3 8.6 v4 5.6 v5 8 v6 6 0 8 5 4 8 0 3 14 L3 v1 v2 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v2 8.8 v3 8.6 v4 5.6 v5 8 v6 6 0 8 5 4 8 0 3 12 5 3 0 9 13 7.8 0 9 4 9 9 0 4.8 12 5 3 0 9 13 7.8 0 9 4 9 9 0 4.8 14 图6－46

100 4.8 12 14 100 9 13 4.8 7.8 13 4.8 7.8 最优票价表：

v1 v2 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v2 v3 v4 v5 v6

0 8 0 5 3 0 13 7.8 0 4 9 9 0 4.8 12 v1、v2、?、v6到各点的最优路线图分别为：

6.9 设图6－46是某汽车公司的6个零配件加工厂，边上的数字为两点间的距离(km)。现要在6个工厂中选一个建装配车间。

（1）应选那个工厂使零配件的运输最方便。

（2）装配一辆汽车6个零配件加工厂所提供零件重量分别是0.5、0.6、0.8、1.3、1.6和1.7吨，运价为2元/吨公里。应选那个工厂使总运费最小。 【解】(1)利用习题6.8表L3的结果

L?minmax?Lij??8.8

ijv1 v2 v3 v4 v5 v6 Max v1 0 8.8 8.6 5.6 8 6 8.8 v2 8.8 v3 8.6 v4 5.6 v5 8 v6 6 选第1个工厂最好。

0 8 5 4 8 0 3 12 5 3 0 9 13 7.8 0 9 4 12.8 9 0 9 12 4.8 12 12 9 12.8 13 4.8 7.8

(2)计算单件产品的运价，见下表最后一行。计算单件产品的运费，见下表最后一列。

v1 v2 v3 v4 v5 v6 单件产品运费 v1 0 8.8 8.6 5.6 8 6 84.88 v2 v3 v4 v5 v6 运价 8.8 8.6 5.6 8 6 1 0 8 5 4 1.2 8 0 3 12 1.6 5 3 0 9 2.6 13 7.8 0 9 3.2 4 9 9 0 3.4 89.16 82.16 71.96 81.92 82.2 4.8 12 13 4.8 7.8 选第4个工厂最好。

6.10 如图6－47，（1）求v1到v10的最大流及最大流量；（2）求最小割集和最小割量。

【解】给出初始流如下

图6－47

第一轮标号：得到一条增广链，调整量等于5，如下图所示

调整流量。

第二轮标号：得到一条增广链，调整量等于2，如下图所示

调整流量。

第三轮标号：得到一条增广链，调整量等于3，如下图所示

调整流量。

第四轮标号：不存在增广链，最大流量等于45，如下图所示

取 V1?{v1,v2,v3,v4,v5,v6,v8},V1?{v7,v9,v10}，最小截集{(3,7),(4,7),(6,9),(8,10)，最小截量等于45。

6.11 将3个天然气田A1、A2、A3的天然气输送到2个地区C1、C2，中途有2个加压站B1、B2，天然气管线如图6－48所示。输气管道单位时间的最大通过量cij及单位流量的费用dij标在弧上(cij, dij)。求(1)流量为22的最小费用流；（2）最小费用最大流。

图6－48

【解】虚拟一个发点和一个收点

T6.11－1

得到流量v＝22的最小费用流，最小费用为271。求解过程参看习题部分答案PPT文档。

T6.11－13

最小费用最大流如下图，最大流量等于27，总费用等于351。

6.12如图6－46所示，（1）求解旅行售货员问题；（2）求解中国邮路问题。

图6-46

【解】（1）旅行售货员问题。

1 2 3 4 5 1 ∞ 8.8 9 5.6 8 距离表C 2 3 8.8 ∞ 10 5 ∞ 9 10 ∞ 3 4.8 4 5.6 5 3 ∞ 12 5 8 ∞ 4.8 12 ∞ 6 6 4 14 ∞ 9 ∞ 6 6 4 14 9 ∞ 在C中行列分别减除对应行列中的最小数，得到距离表C1。 距离表C1 1 2 3 4 5 1 2 3 4 5 ∞ 2.8 4 0.6 1.2 3.2 ∞ 7 2 ∞ 3.4 6 ∞ 0 0 0 1 0 ∞ 7.2 0.6 ∞ 0 7.2 ∞ 6 0.4 0 11 ∞ 9 6 0 0 10 3.2 ∞ ∞ 由距离表C1，v1到v4， H1={ v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1}, C(H1)=5.6+3+4.8+9+4+8.8=35.2 去掉第1行第四列，d41=∞，得到距离表C2。

得到距离表C2 1 2 3 5 6 2 2.8 6 0 ∞ ∞ 3 4 7 0 11 ∞ 4 2 0 7.2 ∞ ∞ 5 1.2 0 9 ∞ ∞ 6 0 0 10 3.2 ∞ 距离表C2的每行每列都有零，H2= H1={ v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1}就是总距离最小的Hamilton回路，C(H1) =35.2。

(2)中国邮路问题。虚拟一条边

取回路H1＝{v1，v3，v4}，C(H1)=9+5+3=17,C(v1，v3)=9> C(H1)/2，调整回路。

所有回路满足最短回路的准则，上图是最短的欧拉回路，其中边(v1, v4)和(v4, v3)各重复一次。

习题七

7.2(1)分别用节点法和箭线法绘制表7-16的项目网络图，并填写表中的紧前工序。 (2) 用箭线法绘制表7-17的项目网络图，并填写表中的紧后工序

表7-16

工序 A B C E E B D G F A,B I E A、C G G B H,J F － G H D,G I G B、D、E、F － I C,E,F,H L 紧前工序 － － － A 紧后工序 D,E G 工序 紧前工序 紧后工序 A - F 表7-17

B - E,D,F,G C - I,K D B J D,G M K C,E M L I M M J,K,L － H,J I,K

【解】（1）节点图：

箭线图：

（2）节点图：

箭线图：

7.3根据项目工序明细表7-18： （1）画出网络图。

（2）计算工序的最早开始、最迟开始时间和总时差。 （3）找出关键路线和关键工序。

表7-18

工序 紧前工序 A - B A 6 C A 12 D B,C 19 E C 6 F D,E 7 G D,E 8 工序时间（周） 9 【解】(1)网络图

(2)网络参数

工序 A 0 0 0 B 9 15 6 C 9 9 0 D 21 21 0 E 21 34 13 F 40 41 1 G 40 40 0 最早开始 最迟开始 总时差 (3)关键路线：①→②→③→④→⑤→⑥→⑦；关键工序：A、C、D、G；完工期：48周。 7.4 表7-19给出了项目的工序明细表。

表7-19

工序 紧前工序 A B C - - 5 - 7 D 12 E 8 F 17 G E 16 H D,G 8 I E J K L M 15 N 12 A,B B B,C E H F,J I,K,L F,J,L 工序时间(天) 8 14 5 10 23 （1）绘制项目网络图。 （2）在网络图上求工序的最早开始、最迟开始时间。

（3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差。 （4）找出所有关键路线及对应的关键工序。 （5）求项目的完工期。 【解】(1)网络图

（2）工序最早开始、最迟开始时间

（3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差 工序 t TES TEF TLS TLF 总时差S 自由时差F A 8 0 8 9 17 9 0 B 5 0 5 0 5 0 0 C 7 0 7 7 7 0 0 D 12 8 20 17 29 9 9 E 8 5 13 5 13 0 0 F 17 7 24 7 24 0 0 G 16 13 29 13 29 0 0 H 8 29 37 29 37 0 0 I 14 13 27 33 47 20 20 J 5 13 18 19 24 6 6 K 10 37 47 37 47 0 0 L 23 24 47 24 47 0 0 M 15 47 62 47 62 0 0 N 12 47 59 50 62 3 3 (4)关键路线及对应的关键工序

11→○12；关键工序：B,E,G,H,K,M 关键路线有两条，第一条：①→②→⑤→⑥→⑦→○

11→○12；关键工序：C,F,L,M 第二条：①→④→⑧→⑨→○

（5）项目的完工期为62天。

7.5已知项目各工序的三种估计时间如表7-20所示。

求： 表7-20 （1）绘制网络图并计算各工序的期望时间和工序的三种时间（小时） 工序 紧前工序 方差。 a m b （2）关键工序和关键路线。

A 9 10 12 － （3）项目完工时间的期望值。

B A 6 8 10 （4）假设完工期服从正态分布，项目在56小

C A 13 15 16 时内完工的概率是多少。

D B 8 9 11 （5）使完工的概率为0.98，最少需要多长时

E B,C 15 17 20 间。

F D,E 9 12 14 【解】（1）网络图

工序 紧前工序 工序的三种时间（小时） a m b 期望值 方差 A B C － A A 9 6 13 10 8 15 12 10 16 10.17 14.83 0.25 0.25 8 0.4444 D E F B B,C D,E 8 15 9 9 17 12 11 20 14 9.167 0.25 17.17 0.6944 11.83 0.6944 (2)关键工序：A,C,E,F；关键路线：①→②→④→⑤→⑥

(3) 项目完工时间的期望值：10.17+14.83+17.17+11.83＝54(小时)

完工期的方差为0.25+0.25+0.6944+0.6944＝1.8889

?＝1.8889＝1.37437

(4)X0=56，???X0??n??56?54???Φ??＝?(1.4552）＝0.927

?1.37437???n?56天内完工的概率为0.927

(5) p=0.98，p{X?X0)??(Z)?0.98,Z?2.05

X0＝Z????2.05?1.3744?54?56.82

要使完工期的概率达到0.98，则至少需要56.82小时。

7.6 表7-21给出了工序的正常、应急的时间和成本。

表7-21

工序 A B C D E F G 紧前工序 A A B,C D C E,F 时间(天) 正常 成本 时间的最大缩量(天) 3 2 3 2 4 3 2 应急增加成本（万元/天） 5 10 3 15 3 5 12 应急 正常 应急 15 12 7 13 14 16 10 12 10 4 11 10 13 8 50 65 100 120 80 89 60 90 40 52 45 60 60 84 （1）绘制项目网络图，按正常时间计算完成项目的总成本和工期。 （2）按应急时间计算完成项目的总成本和工期。

（3）按应急时间的项目完工期，调整计划使总成本最低。

（4）已知项目缩短1天额外获得奖金4万元，减少间接费用2.5万元，求总成本最低的项目完工期。

(1) 正常时间项目网络图 项目网络图

总成本为435，工期为64。 (2)应急时间项目网络图

总成本为560，工期为51。 (3)应急时间调整

工序C、F按正常时间施工，总成本为560-9-15＝536，完工期为51。 (4) 总成本最低的项目完工期

工序A、E分别缩短3天，总成本为435+15+12-6.5×7＝416.5，完工期为57。

7.7继续讨论表7-21。假设各工序在正常时间条件下需要的人员数分别为9、12、12、6、8、17、14人。

（1）画出时间坐标网络图

（2）按正常时间计算项目完工期，按期完工需要多少人。

（3）保证按期完工，怎样采取应急措施，使总成本最小又使得总人数最少，对计划进行系统优化分析。 【解】（1）正常时间的时间坐标网络图

minP??pi(xi)i?1n （8.9） ?ncx?C??ii?i?1?x?0并且为整数，i?1,2,?,n?j 利用式(8.8)或（8.9）求解下列问题。

（1）工厂设计的一种电子设备，其中有一系统由三个电子元件串联组成。已知这三个元件的价格和可靠性如表8-27所示，要求在设计中所使用元件的费用不超过200元，试问应如何设计使设备的可靠性达到最大。

表8-27

元件 1 2 3 单价 40 35 20 可靠性 0.95 0.8 0.6 （2）公司计划在5周内必须采购一批原料，而估计在未来的5周内价格有波动，其浮动价格和概率根据市场调查和预测得出，如表8-28所示，试求在哪一周以什么价格购入，使其采购价格的期望最小，并求出期望值。

表8-28

单 价 550 650 800 900

【解】（1）数学模型为

概 率 0．1 0．25 0．3 0．35 maxZ?(1?0.05x1)(1?0.2x2)(1?0.4x3)?40x1?35x2?20x3?200??x1,x2,x3?0并且为整数

最优解X=(1，2，4)；可靠性Z=0.888653，总费用190。

（2）

设阶段k，可按采购期限分为5段，k＝l，2，3，4，5 决策变量为xk，第k周采购则xk＝l，若不采购则xk＝0 状态变量sk表示第k周原料实际价格

用Qk表示当第k周决定等待，而在以后采购时的采购价格期望值，即

Qk?0.1fk?1(550)?0.25fk?1(650)?0.3fk?1(800)?0.35fk?1(900)

最优指标函数fk(sk)表示第k周实际价格为sk时，从第k周到第5周采取最优决策所花费的最低期望价格，递推公式为

?fk(sk)?min?sk,Qk?,sk?Dk，k?4,3,2,1?f5(s5)?s5，s5?D5 ?Dk为状态集合?550,650,800,900?则k＝5时，因为若前四周尚未购买，则无论本周价格如何，该企业都必须购入原料 所以

*?550, 当s5?550，x5?1?*?650, 当s5?650，x5?1

f5(s5)??*?800, 当s5?800，x5?1?900,*当s5?800，x5?1?当k＝4时，

Q4?0.1f5(550)?0.25f5(650)?0.3f5(800)?0.35f5(900)?0.1?550?0.25?650?0.3?800?0.35?900?772.5

f4(s4)?min?s4,Q4??min?s4,772.5?s4?D4*?550, 当s4?550，x4?1 ?*??650， 当s4?650，x4?1?* s4?800或900，x4?0?772.5，当当k＝3时，

Q3?0.1f4(550)?0.25f4(650)?0.3f4(800)?0.35f4(900)?0.1?550?0.25?650?(0.3?0.35)?772.5?719.625f3(s3)?min?s3,Q3??min?s3,719.625?s3?D3*?550, 当s3?550，x3?1 ?*??650， 当s3?650，x3?1?*719.625， 当s?800或900，x?033?

当k＝2时，

Q2?0.1f3(550)?0.25f3(650)?0.3f3(800)?0.35f3(900)?0.1?550?0.25?650?0.3?（0.3?0.35）?719.625?685.256f2(s2)?min?s2,Q2??min?s2,685.256?s2?D2*?550, 当s2?550，x2?1 ?*??650， 当s2?650，x2?1?*685.256， 当s?800或900，x?022?

当k＝1时，

Q1?0.1f1(550)?0.25f2(650)?0.3f2(800)?0.35f2(900)?0.1?550?0.25?650?0.3?（0.3?0.35）?685.256?662.92f1(s1)?min?s1,Q1??min?s1,662.92?s1?D1*?550, 当s1?550，x1?1 ?*??650， 当s1?650，x1?1?*662.92， 当s?800或900，x?011?

最优采购策略：

若前面四周原料价格为550或650时，则立即采购，否则在以后的几周内再采购。第五周无论当时的价格为多少都必须采购。期望价格为 f1(s1)?0.1?550?0.25?650?(0.3?0.35)?662.92?648.4（元）

习题九

9.1某蛋糕店有一服务员，顾客到达服从?=30人/小时的Poisson分布，当店里只有一个顾客时，平均服务时间为1.5分钟，当店里有2个或2个以上顾客时，平均服务时间缩减至1分钟。两种服务时间均服从负指数分布。试求： （1）此排队系统的状态转移图； （2）稳态下的概率转移平衡方程组； （3）店内有2个顾客的概率； （4）该系统的其它数量指标。 【解】（1）此系统为[M/M/1]:[?/?/FCFS]排队模型，该系统的状态转移图如下：

（2）由转移图可得稳态下的差分方程组如下：

??P0??1P1??P??P?(???)P?02211 ???P1??2P3?(?2??)P2???Pn?1??2Pn?1?(?2??)Pn??2?3?n?P1?P0 P2?P0 P3?P0 Pn?P0 2n?1?1?1?2?1?2?1?211（3）已知??30 （人/小时）?1＝＝40（人/小时）?2＝＝60（人/小时）1.516060由

?P?1得

ii?0??nP0[1??]?1n?1??n?112?????1P0??1??1????2??303?301令 ?1＝＝＝,?2＝＝＝，有

?1404?2602???????1

3?P0?[1?1]?1?[1?4]?1?0.411??21?

2?nn?1pn?p???p0012n?1?1?2则 P2??1?2P0??31??0.4?0.15 42?（4）系统中的平均顾客数（队长期望值）

L??nPn??n?1?2n?1P0??1P0(1?2?2?3?3?...)

n?0n?031??1P0??0.4??1.2(人)22(1??2)4(1?0.5)Lq??(n?1)Pn??nPn??Pnn?1n?1n?12n?1?L??1P0(1??2??2?...??2?...)?L????1

在队列中等待的平均顾客数（队列长期望值）

?1p0

1??23?0.44?1.2??0.6(人)11?2系统中顾客逗留时间

W?系统中顾客等待时间

L?Lq?1.2?0.04(小时) 30Wq???0.6?0.02(小时) 30

9.2某商店每天开10个小时，一天平均有90个顾客到达商店，商店的服务平均速度是每小时服务10个，若假定顾客到达的规律是服从Poisson分布，商店服务时间服从负指数分布，试求：

（1）在商店前等待服务的顾客平均数。 （2）在队长中多于2个人的概率。 （3）在商店中平均有顾客的人数。

（4）若希望商店平均顾客只有2人，平均服务速度应提高到多少。 【解】此题是属于[M/M/1]:[?/?/FCFS]系统，其中：

?=9（个/小时） ?=10(个/小时) ???/?=9/10

(1) Lq??/(1??)?8.1（个）

2?3?0.729

(3) L??/(1??)?9（个） (4) L??/(???)?2

??2?9?18??13.5(个/小时) ??(2) P(N?2)?22

9.3为开办一个小型理发店，目前只招聘了一个服务员，需要决定等待理发的顾客的位子应设立多少。假设需要理发的顾客到来的规律服从泊松流，平均每4分钟来一个，而理发的时间服从指数分布，平均每3分钟1人。如果要求理发的顾客因没有等待的位子而转向其他理发店的人数占要理发的人数比例为7％时，应该安放几个位子供顾客等待？ 【解】此题属于[M/M/1]:[N/?/FCFS]模型,依题意知：

?＝1/4，?=1/3，???/??3/4，由题意解方程

???e?0.07 ????e??1?e?1?1?PN?PN?0.07 ???N??N?1PN??0.07N?11???N??N?1?0.07?N?1??N(1?0.93?)?0.070.070.07????0.23141?0.93?1?0.93?0.75ln0.2314N??5.087ln0.75N

则应设立4个座位供顾客排队。

9.4某服务部平均每小时有4个人到达，平均服务时间为6分钟。到达服从Poisson流，服务时间为负指数分布。由于场地受限制，服务部最多不能超过3人，求：

（1）服务部没有人到达的概率； （2）服务部的平均人数； （3）等待服务的平均人数；

（4）顾客在服务部平均花费的时间； （5）顾客平均排队的时间。

【解】依题意，这是[M/M/1]:[N/?/FCFS]排队系统。其中：

N=3，?=4，?=10，???/?=0.4

1?ρ4

（1）P0?=（1-0.4）/[1-（0.4）]=0.6158 N?11-ρ（2）L?0.5616（人）

（3）Lq?0.1616（人） （4）W?0.1404（小时） （5）Wq?0.0404（小时）

9.5某车间有5台机器，每台机器连续运转时间服从负指数分布，平均连续运转时间为15分钟。有一个修理工，每次修理时间服从负指数分布，平均每次12分钟。求该排队系统的数量指标，P0，Lq，L，Wq，W和P5。

【解】由题意知，每台机器每小时出故障的平均次数服从泊松分布，故该排队系统为[M/M/1]:[?/m/FCFS]系统，其中： ?=1/15，m=5，?=1/12，???/?=0.8

?5?5!P0????k??k?0(5?k)!??1?0.0073

本文来源：https://www.bwwdw.com/article/k3y6.html