运筹学习题及答案1

一、用动态规划方法求解下列问题

某公司有资金400万元，向A，B，C三个项目追加投资，三个项目可以有不同的投资额度，相应的效益值如下表所示，问如何分配资金，才使总效益值最大？

投资额 效益值 A B C

0 47 49 46 1 51 52 70 2 59 61 76 3 71 71 88 4 76 78 88 二、推导确定型存贮问题中“不允许缺货，补充需要一定时间”的数学模型。

其中包括：假设条件、库存状态变化分析图、存贮费用分析、最佳经济批量、最小存贮费用

三、作图题，请写明步骤

1、用避圈法找出下图的最小支撑树，并绘出最小支撑数图

2 V1 5 V3 7 V5 3 6 3 4 V2 7 V4 3 4 5 V6 6 V7

2、求出图中从V1~V6的最短路线；

V1

V2 1 2 5 V4 8 8 V3 9 V6 3 10 V5 3 7 4 V7 9 四、绘制网络图，计算时间参数，找出关键线路，若资源限量为10人/天，试用资源安排方法求出“资源有限，工期最短”的网络计划。 工作名称 A B C D E F G H

紧前工作 C ----- ----- B ABCDF B AD CF 工作时间(天) 5 4 3 4 3 2 3 4 工作资源（人） 5 2 6 4 3 1 5 2 第 2 页 共 8 页

答案

一、用动态规划方法求解下列问题

1、解：1、阶段划分：按项目划分为三个阶段；

2、状态变量yk； 3、决策变量xk；

4、状态转移方程：yk1ykxk 5、阶段收益vk—查表

6、指标函数：fk(yk)max[vkfk1(yk1)] 7、边界条件：f40

K=3时

y3 x3 f3 0 0 46 1 1 70 2 2 76 K=2时

3 3 88 4 4 88 x2 f2 y2 0 1 2 3 4 95* 119* 125* 137* 137 98 122 128 140 107 131 137 K=1时

117 141* 124 0 1 2 3 4 y1 x1 4 0 188 4 1 188 4 2 184 4 3 190* 4 4 170 f1 第 3 页 共 8 页

回溯过程：

y14 x13 y21 x20 y31 x31

f1(y1)190万

二、推导确定型存贮问题中“不允许缺货，补充需要一定时间”的数学模型。其中包括：假设条件、库存状态变化分析图、存贮费用分析、最佳经济批量、最小存贮费用

(一)、假设条件：

1、补充需要一定的时间；生产（供货）时间T；速度为P； 2、生产（订购）产量：Q=P·T

3、C1、C3为常数，C2=0，若缺货C2 ∞

4、需求速度：R是一连续而均衡的常数，R＜P； 5、补充周期t：

Rt QRtPTTPS(PR)T;SR(tT)(PR)TR(tT)PTRTRtRT PTRtRtTP在T区间内，库存量以P－R的速率在增加，在t－T区间内，库存量以R的速率在减少，因而在T时间内以(P－R)的速度供应产品应等于在t－T时间内以R的速度的需求消耗。(PR)TR(tT)

(二)、存贮状态变化图（边生产边向外输出）

[0，T] P－R＞0

[T，t] S—最大库存量，S＜Q（以一个周期内单位库存费用最小为目标）

Q P－R S T t t－T T t R S t－T T S t－T 第 4 页 共 8 页

1、存贮费(三角形的面积)：111RttSC1tC1(PR)TtC1(PR)222P1PRt2C1R2P2、订购费(生产费)C33、单位时间平均库存费：(存贮费与订购费之和加上缺货损失费0)C3112PR1PRC(t)[tC1RC3]tC1Rt2P2Pt（三）费用分析： （四）寻优：

C2C3PdC(t)1PRC1R230t*dt2PtC1R(PR)d2C(t)2C3t3＞02dt2C3Pt*C1R(PR)Q*Rt*2C3PRC1R(PR)(2)(1)C(t)*1*PRCtC1R*32Pt12C3PPRCCR(PR)C1RC3312C1R(PR)P2C3P2C1C3(PR)R2PPRP(3)2C3PR22PC1R(PR)2C3RPC1(PR)(4)

2C1C3RRRTt*PP*2C3PC1R(PR)

三、作图题，请写明步骤

第 5 页 共 8 页

（a）步骤： 2 V5 解：（1）从V1出发，与V1点相联

V3 的边是V1-V2，V1-V3，V1-V4，从中5 V1 选出赋权最小的V1-V2；

7 （2）从V1和V2点出发，找到与两3 点相联的边V1-V3，V1-V4，V2-V4，6 4 V2-V7，从中选出赋权值最小者

V6 3 5 V2-V4；

4 （3）从V1、V2、V4点出发，找到V4 与其相联的边V1-V3，V2-V7，V2 6 3 V4-V3，V4-V6，V4-V7，从中选出赋

权值最小者V4-V7； 7 （4）从V1、V4、V7点出发，找到与其相联的边V1-V3，V4-V3，V7 V7-V6，V4-V6，从中选择最小者V4-V3；

（5）从V3、V4、V7点出发，找到与其相联的边V3-V5，V3-V6，V4-V6，V7-V6，从中选择最小者V3-V5；

（6）从V3、V5、V7点出发，找到与其相联的边V3-V6，V5-V6，V7-V6，从中选择最小者V3-V6，则构成最小生成树。如图所示。 （b）最小支撑数=19

2、用Dijkstra算法求最短路 V2 V5 1 3 9 2 7 5 V7 V1 4 V4 3 8 8 10 V3 9 V6 (1)步骤 L11=0；

L1r=min{d12,d13}=8=L13;

L1p=min{L11+d12，L13+d32,L13+d34,L13+d36}=9=L12

L1p=min{L12+d23，L12+d24,L12+d25,L13+d32,L13+d34,L13+d36}=10=L15

L1p=min{L12+d24，L12+d23,L15+d56,L15+d57,L13+d32,L13+d34,L13+d36}=11=L14 L1p=min{L15+d56，L15+d57,L14+d43,L14+d46,L14+d45,L13+d34,L13+d36}=13=L17 （2）最短路L17=13

四、绘制网络图，计算时间参数，找出关键线路。

1、绘制网络图 2、计算时间参数

第 6 页 共 8 页

3、找出关键线路 4、网络优化 0 0 1 4 0 B（2人） 1/ A（5人） 3 3 5天 8 0 4 4 8 0 2 D（4人） 4天 4 8 4 4 6 6 4 G（5人） 3天 8 8 11 8 0 8 0 11 2/ 8 2 E（3人） 3天 5 T=11天

4天 4 5 F（1人）C（6人） 3天 4/ 6 1 2天 3 3 7 3 4 0 0 3 0 H（2人） 4天 6 10 7 1 工作日程 1 1 2 3 4 1/ 5 6 7 8 9 4 10 11 12 13 A（5人） 3 3 5天 G（5人） 3天 0 3 0 3 0 0 4 0 B（2人） 4天 0 0 3 0 C（6人） 3天 4/ 4 5 F（1人）2天 6 1 3 3 7 3 4 8 0 4 4 8 0 2 D（4人） 4天 4 8 4 4 6 6 8 8 11 8 0 8 0 11 2/ 8 2 E（3人） 3天 5 H（2人） 4天 6 10 7 1 资源耗费 8人/天 7 10 13 10 8 第 7 页 共 8 页

工作日程 1 1 0 3 0 3 0 0 2 3 4 1/ 5 6 A（5人） 7 8 9 4 10 11 12 13 G（5人） 3天 8 11 3 3 5天 8 0 4 4 8 0 2 D（4人） 4天 4 9 4 4 8 8 9 1 9 0 E（3人） 8 9 3天 1 5 4 0 B（2人） 4天 0 0 3 0 C（6人） 3天 4/ 2/ 4 6 F（1人）6 0 2天 3 3 8 3 3 6 8 6 2 3/ 11 H（2人） 4天 8 12 8 0 资源耗费 8人/天

7 10 9 7 10 5 第 8 页 共 8 页