运筹学习题及答案

1、一、用动态规划方法求解下列问题某公司有资金400万元，向A，B，C三个项目追加投资，三个项目可以有不同的投资额度，相应的效益值如下表所示，问如何分配资金，才使总效益值最大？ 投资额效益值01234A4751597176B4952617178C4670768888二、推导确定型存贮问题中“不允许缺货，补充需要一定时间”的数学模型。其中包括：假设条件、库存状态变化分析图、存贮费用分析、最佳经济批量、最小存贮费用三、作图题，请写明步骤1、用避圈法找出下图的最小支撑树，并绘出最小支撑数图V7V6V4V2V5V3V16437273543652、求出图中从V1V6的最短路线； V7918V4V3V6V2V

2、55287394310V1四、绘制网络图，计算时间参数，找出关键线路，若资源限量为10人/天，试用资源安排方法求出“资源有限，工期最短”的网络计划。工作名称紧前工作工作时间(天)工作资源（人）AC55B-42C-36DB44EABCDF33FB21GAD35HCF42答案一、用动态规划方法求解下列问题1、解：1、阶段划分：按项目划分为三个阶段；2、状态变量； 3、决策变量；4、状态转移方程：5、阶段收益查表6、指标函数：7、边界条件：K=3时01234012344670768888K=2时01234095*1119*982125*1221073137*128131117413714013714

3、1*124K=1时4444401234188188184190*170回溯过程： 二、推导确定型存贮问题中“不允许缺货，补充需要一定时间”的数学模型。其中包括：假设条件、库存状态变化分析图、存贮费用分析、最佳经济批量、最小存贮费用 (一)、假设条件：1、补充需要一定的时间；生产（供货）时间T；速度为P；2、生产（订购）产量：Q=PT3、C1、C3为常数，C2=0，若缺货C2 4、需求速度：R是一连续而均衡的常数，RP；在T区间内，库存量以PR的速率在增加，在tT区间内，库存量以R的速率在减少，因而在T时间内以(PR)的速度供应产品应等于在tT时间内以R的速度的需求消耗。5、补充周期t：(二)、

4、存贮状态变化图（边生产边向外输出）0，T PR0RPRQtTtTttTTTtTSSST，t S最大库存量，SQ（以一个周期内单位库存费用最小为目标）（三）费用分析：（四）寻优：三、作图题，请写明步骤 643727354365V7V6V4V2V5V3V1 （a）步骤： 解：（1）从V1出发，与V1点相联的边是V1-V2，V1-V3，V1-V4，从中选出赋权最小的V1-V2；（2）从V1和V2点出发，找到与两点相联的边V1-V3，V1-V4，V2-V4，V2-V7，从中选出赋权值最小者V2-V4；（3）从V1、V2、V4点出发，找到与其相联的边V1-V3，V2-V7，V4-V3，V4-V6，V4-

5、V7，从中选出赋权值最小者V4-V7；（4）从V1、V4、V7点出发，找到与其相联的边V1-V3，V4-V3，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）最小支撑数=192、用Dijkstra算法求最短路V7918V4V3V6V2V55287394310V1(1)步骤L11=0；L1r=mind12,d13=8=L13;L1p

6、=minL11+d12，L13+d32,L13+d34,L13+d36=9=L12L1p=minL12+d23，L12+d24,L12+d25,L13+d32,L13+d34,L13+d36=10=L15L1p=minL12+d24，L12+d23,L15+d56,L15+d57,L13+d32,L13+d34,L13+d36=11=L14L1p=minL15+d56，L15+d57,L14+d43,L14+d46,L14+d45,L13+d34,L13+d36=13=L17（2）最短路L17=13四、绘制网络图，计算时间参数，找出关键线路。1、绘制网络图2、计算时间参数3、找出关键线路4、网

7、络优化4/68628811033804561004000306710148448811044803734H（2人）4天G（5人）3天F（1人）2天E（3人）3天D（4人）4天C（6人）3天B（2人）4天A（5人）5天1/124532/T=11天工作日程12345678910111213686288110338045610303004000306710148448811044803734H（2人）4天G（5人）3天F（1人）2天E（3人）3天D（4人）4天C（6人）3天B（2人）4天A（5人）5天1/124532/4/资源耗费8人/天71013108工作日程12345678910111213891112/8980338046600303004000