运筹学习题及答案1整理.pdf

一、用动态规划方法求解下列问题某公司有资金 400 万元，向 A，B，C 三个项目追加投资，三个项目可以有不同的投资额度，相应的效益值如下表所示，问如何分配资金，才使总效益值最大？投资额效益值0 1 2 3 4 A 47 51 59 71 76 B 49 52 61 71 78 C 46 70 76 88 88 二、推导确定型存贮问题中“不允许缺货，补充需要一定时间”的数学模型其中包括：假设条件、库存状态变化分析图、存贮费用分析、最佳经济批量、最小存贮费用三、作图题，请写明步骤1、用避圈法找出下图的最小支撑树，并绘出最小支撑数图V7V6V4V2V5V3V16 4 3 7 2 7 3 5 4 3 6 5 第 2 页 共 8 页2、求出图中从 V1V6的最短路线；四、绘制网络图，计算时间参数，找出关键线路，若资源限量为10 人/天，试用资源安排方法求出“资源有限，工期最短”的网络计划工作名称紧前工作工作时间 (天) 工作资源（人）A C 5 5 B - 4 2 C - 3 6 D B 4 4 E ABCDF 3 3 F B 2 1 G AD 3 5 H CF 4 2 V79 1 8 V4V3V6V2V55 2 8 7 3 9 4 3 10 V1第 3 页 共 8 页答案一、用动态规划方法求解下列问题1、解：1、阶段划分：按项目划分为三个阶段；2、状态变量ky；3、决策变量kx；4、状态转移方程：kkkxyy15、阶段收益kv查表6、指标函数：)(max)(11kkkkkyfvyf7、边界条件：04fK=3时3y0 1 2 3 4 3x0 1 2 3 4 3f46 70 76 88 88 K=2时2x2f2y0 1 2 3 4 0 95*1 119*98 2 125*122 107 3 137*128 131 117 4 137 140 137 141*124 K=1时1y4 4 4 4 4 1x0 1 2 3 4 1f188 188 184 190*170 第 4 页 共 8 页回溯过程：41y31x12y02x13y13x万190)(11yf二、推导确定型存贮问题中 “不允许缺货， 补充需要一定时间” 的数学模型。

其中包括：假设条件、库存状态变化分析图、存贮费用分析、最佳经济批量、最小存贮费用(一)、假设条件：1、补充需要一定的时间；生产（供货）时间T；速度为 P；2、生产（订购）产量： Q=PT 3、C1、C3为常数， C2=0，若缺货 C24、需求速度： R 是一连续而均衡的常数， RP；5、补充周期 t：PtRTTPtRQPRtTtRTPTRtRTRTPTtRTRPTtRSTRPS)()()(;)(二)、存贮状态变化图（边生产边向外输出）0，T PR0 T，t S最大库存量， SQ（以一个周期内单位库存费用最小为目标）在 T 区间内，库存量以PR 的速率在增加，在 tT 区间内，库存量以 R 的速率在减少， 因而在 T 时间内以(PR)的速度供应产品应等于在 tT 时间内以 R 的速度的需求消耗)()(TtRTRPR PR Q tT t T t t tT T T T S S S 第 5 页 共 8 页（三）费用分析：（四）寻优：)4()(2)(2)(2)3(22)(22)()(22121)(13122313*31313133113*31*RPPCRCRPRCPPRCRPRCPCPRtPRTPRPRCCRPRPCCPCRPRCCCRPRPCRPRCPCtCRPRPCttC三、作图题，请写明步骤tCRPRPCtCRPRPCtttCCRPRPCtPRtRPCtTRPCtCSt3131231211121211)()0(3)(221)(21)(2121)(1上缺货损失费存贮费与订购费之和加：、单位时间平均库存费生产费、订购费：三角形的面积、存贮费)2()(2)(202)()1()(2021)(13*13*332213*231RPRCPRCRtQRPRCPCttCdttCdRPRCPCttCRPRPCdttdC第 6 页 共 8 页6 4 3 7 2 7 3 5 4 3 6 5 V7V6V4V2V5V3V1（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-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算法求最短路(1) 步骤L11=0；L1r=mind12,d13=8=L13; L1p=minL11+d12，L13+d32,L13+d34,L13+d36=9=L12 L1p=minL12+d23，L12+d24,L12+d25,L13+d32,L13+d34,L13+d36=10=L15 L1p=minL12+d24，L12+d23,L15+d56,L15+d57,L13+d32,L13+d34,L13+d36=11=L14 L1p=minL15+d56，L15+d57,L14+d43,L14+d46,L14+d45,L13+d34,L13+d36=13=L17 （2）最短路 L17=13四、绘制网络图，计算时间参数，找出关键线路1、绘制网络图2、计算时间参数V79 1 8 V4V3V6V2V55 2 8 7 3 9 4 3 10 V1第 7 页 共 8 页3、找出关键线路4、网络优化工作日程1 2 3 4 5 6 7 8 9 10 11 12 13 资源耗费8 人/天7 10 13 10 8 4/6 8 62 8 8 11 0 3 3 8 0 4 5 6 1 0 0 4 0 0 0 3 0 6 7 10 1 4 8 4 4 8 8 11 0 4 4 8 0 3 7 3 4 H（2 人）4 天G（5 人）3 天F（1 人）2 天E（3 人）3 天D（4 人）4 天C（6 人）3 天B （2 人）4 天A（5 人）5 天1/1 2 4 5 3 2/T=11天6 8 62 8 8 11 0 3 3 8 0 4 5 6 1 0 3 0 3 0 0 4 0 0 0 3 0 6 7 10 1 4 8 4 4 8 8 11 0 4 4 8 0 3 7 3 4 H（2 人）4 天G（5 人）3 天F（1 人）2 天E（3 人）3 天D（4 人）4 天C（6 人）3 天B（2 人）4 天A （5 人）5 天1/1 2 4 5 3 2/4/第 8 页 共 8 页工作日程1 2 3 4 5 6 7 8 9 10 11 12 13 资源耗费8 人/天7 10 9 7 10 5 4 9 4 4 2 3 8 9 111 2/8 9 80 3 3 8 0 4 6 6 0 0 3 0 3 0 0 4 0 0 0 3 0 8 8 12 0 8 9 11 1 4 4 8 0 3 8 3 3 H（2 人）4 天G（5 人）3 天F（1 人）2 天E（3 人）3 天D（4 人）4 天C（6 人）3 天B （2 人）4 天A（5 人）5 天1/1 4 5 4/3/6 8 6 2 。