运筹学重点及部分习题

1、运筹学重点一、 选择题1、 线性规划问题没有可行解，对偶问题也（一定没有可行解）。2、 运输问题中常用(最小元素法)确定初始方案。3、 线性规划单纯形法中所有检验数0，基变量中有人工变量，则该问题(无可行解)。4、 求解产小于销的运输问题时，需要虚购一个(产地)。5、 某资源的(影子价格)的数值就是在给定的条件下，该资源每增加一个单位时，目标函数的增加数量。6、 经过计算运输问题初始方案检验数23=-6,从此点出发找出闭合回路，闭合回路各点的数值依次为（0, 12, 4, 6, 8， 3）， 调整后各点的运输为（3, 9, 7, 3, 11, 0）。7、 极大化线性问题的标准模型中，人工变量的

2、目标函数中的系数是（-M）。8、 最大流问题中，存在一条增广链，则增广链上的正向弧一定是(不饱和弧)。9、 某棵树有16个顶点，它的边数是(15)条。10、在网路计划图中，总时差为(0)的工序构成的路线称为关键路线。11、容量网络中，从发点到收点的最大流的流量等于网络(最小割)的容量12、一对对偶线性规划问题，若有一个最优解，则另一个也一定有最优解，并且这两个最优解对应的(目标函数值)相等。13、若边e的两个端点相连，则称边e为(环)。14、图中奇点的个数一定是(偶)数。15、线性规划问题全部可行解的集合称为(凸集)。16、图是欧拉回路的条件是图中的点都为(偶)点。17,、PERT网络图中，工

3、序在不影响下道工序最早开工时间条件下可以机动的时间称为(单时差)。18、线性规划数学模型的标准形式规定目标函数是求(最大值)，约束条件都是线性等式，对每个变量都有非负要求。19、存贮问题的数学模型中，不允许缺货时，缺货费用为(无穷大)。20、中国邮路问题的最优方案每天编最多重复(一)次。二、简答题1、PERT网络中关键工序的意义？2、试举两个可以应用最大流方法解决的实际问题？3、试举例可以应用最短路方法解决的实际问题？4、试举例可以应用最小数方法解决的实际问题？5、PERT网络优化的类型有哪些？6、动态规划的最优化原理的涵义？7,、线性规划数学模型通常可以解决那两类实际问题？8、简述对偶单纯形

4、法的思想？三、计算题1、 第九章 存储问题(必考)例 某公司生产产品每年需要甲材料40000公斤，材料单价100元，定购费用每次200元，年库存保管费用为25%，。 （1）、试计算最佳订购批量（2）、试计算最佳订购次数（3）、试计算最低年库存保管总费用（4）、试画出本例库存状态变化图2、第一章 线性规划 3、第二章 （1）对偶模型 （2） 灵敏度分析4、第六章 最短路问题（标号法）5、第六章 最大流问题6、第七章 EPRT网络图各参数的计算7、第八章 动态规划 （六个例题） （1）教科书习题八的第一题（2）某机械公司购置五台先进设备，需分给所属的甲，乙，丙三个工厂。各工厂获得这些设备后，每年为

5、公司提供的盈利（万元）见表： 设备数工厂 0 12345甲 03791213乙 0510111111丙046111212 问如何分配这些设备才能使公司得到的盈利额最大。 解：将问题按工厂划分为三个阶段，三个工厂的编号分别记为1，2，3。SK表示分配给第K个工厂到第3个工厂的设备台数，XK表示 分配给第K个工厂的设备台数： S1=5 SK+1 = SK - XK VK (XK)表示XK台设备分配到第K 个工厂得到的盈利值。FK (SK) 表示SK台设备分配到第K个工厂至第三个工厂所得的最大盈利。因此有递推关系： FK (SK)=Max VK (XK)+FK+1 (S

6、K - XK) (K=1,2,3) 0XKSK (K=1,2,3) F4 (S4) = 0现从最后一个阶段向前递推求解：阶段 K= 3 设把S3台设备（S3=0，1，2，3，4，5）全部分配给工厂3时，则最大盈利值为： F3 (S3)=Max V3 (X3) X3=0,1,2,3,4,5因为只有一个工厂，给不同台数的盈利就是每种情况下的最大盈利。因此最优方案是把全部设备放到工厂3去。数值计算及决策见表S3 X3 V3(x3) +F4 (S4 ) F3(s3)x3 *01234500    00104    412046 &#

7、160; 62304611  11340461112 1245046111212125阶段 K=2 设把S2台（S2=0，1，2，3，4，5）设备全部分给工厂3、工厂2时，则最大盈利值为： F2 (S2)=Max V2 (X2)+ F3 (S2- X2) X2= 0,1,2,3,4,5选择X2数值使F2 (S2)最大决策及计算结果如表67： x2s2 V2 (X2)+ F3 (S2- X2)F2 (s2)X2*01234500    0010+45+0    5120+65+410+0 

8、;  10230+115+610+411+0  14240+125+1110+611+411+0 161&250+125+1210+1111+611+411+0212阶段 K=1 设把S1台设备（S1=5）分配给1，2，3三个工厂，则最大盈利值为： F1 (S1)=Max V1 (X1)+ F2 (S1 - X1) X1=0,1,2,3,4,5现选取X1的值，使F1 (S1)最大，数值计算见表 x1s1 V1 (X1)+ F2 (S1 - X1)F1 (s1)X1*01234550+21 3+167+149+1012+513+0210&

9、amp;2由表中可知：最优方案有二个：(1) X1=0 X2=2 X3=3 F1(S1)=21 (2) X1=2 X2=2 X3=1 F1(S1)=21（3）例8-7某个公司新购某种机床125台。这种设备5年后将被其它新设备代替，此机床如在高负荷状态下工作年损坏率为1/2，每台年收益为10万元；如在低负荷下工作年损坏率为1/5，每台年收益为6万元。问应如何安排这些机床的生产负荷，才能使5年内所获收益最大？解：按年度划分为5个阶段，用K表示阶段序号。状态变量SK 为第K年拥有完好设备的数量，决策变量XK 为第K年中处于高负荷工作的设备数量，决策变量(SKXK )为第K年中处于低负荷工作的设备数量

10、状态转移函数即第K+1年年初完好的设备台数: SK+1 = SK1/2 XK 1/5(SKXK) = 4/5 SK3/10 XK第K阶段允许决策集合为 DK (SK)= XK / 0XKSK VK (SK, XK)为第K年度的收益则 VK = VK (SK= XK)=10 XK +6(SKXK)=6SK +4XK 因此基本方程为: FK (SK)=Max 6SK +4XK + FK+1 (SK+1) 0XKSK K=1,2,3,4,5 F6 (S6 )=0 下面求解问题：阶段 K = 5 F6 (S6 )=0 有： F5 (S5 )= Max4X5 +6S5 0X5 S5 因为4X5 +6S5

11、随X5单调递增，所以取X5 =S5此时 X5 =S5 F5 (S5 )= 10 S5 阶段 K= 4 F4 (S4)=Max4X4 +6S4+ F5 (S5 ) 0X4S4 = Max 4X4 +6S4+ F5 (S5) = Max 4X4 +6S4+8S4-3X4 = Max X4 +14S4 0X4S4因为X4+14S4单凋递增。所以取X4= S4此时X4=S4 F4 (S4)=15 S4阶段 K = 3 F3 (S3) = Max 4X3 +6S3 + F4 (S4) = Max 4X3 +6S3+15 S4 = Max 4X3 +6S3+ 15(0.8 S3 -0.3X3 = Max

12、18S3 (1/2)X3 0X3 S3 由于18S3 (1/2)X3随X3单调递减所以取X3 =0此时： X3 = 0 F3 (S3) = 18S3 阶段 K = 2 F2 (S2)= Max 4 X2+6 S2+ F3 (S3) = Max 4 X2+6 S2+18S3 = Max 4 X2+6 S2 +18(0.8 S2-0.3 X2) = Max20.4 S2-1.4 X2 0X2S2同理取 X2=0此时 X2 =0 F2 (S2) = 20 .4S2阶段 K=1 F1 (S1)= Max 4 X1 +6 S1+F2 (S2) = Max 4 X1 +6 S1+20 .4S2 = Max

13、 4 X1 +6 S1 +20.4(0.8 S1-0.3 X1) = Max 22.32 S1-2.12 X1 0X1S1同理取X1=0此时 X1=0 F1 (S1) = 22.32 S1将S1 =125代入得: F1 (S1) = F1 (125) =22.32X125=2790(万元)n 即公司五年内可获得最大收益值为2790万元，最优生产计划方案为表69所示 表69 年份项目12345状态S125100806432高负荷X1=0X2=0X3=0X4=64X5=32低负荷1251008000（4）例8-8 某造船股份有限责任公司根据合同，从现在起连续4年每年年未要向客户提供型号相同的大型远

14、洋客船，每年的交货数及生产每条船的生产费用见表810所示。年度 项目一二三四生产费用（CK)百万元/条 6.0 6.0 6.3 6.5 需交付船（dK）条/年度 1 3 2 2该公司的生产能力设计为每年6条船。每个计划年度造船公司固定费用为60万元。若造出的船当年不交货，则每条船积压一年的损失为40万元。假定开始时及第四年年未交货后均无积压船只，问公司应如何安排四年的生产计划，使所支付总费用最经济？解 按年度划分阶段，四年分为4个阶段，k=1，2，3，4。状态变量SK为第K阶段初存储的船只数量。状态变量SK需要满足以下条件：不能超过本年和以后各年交船数的总和 0SK di为保证按时交船，每年年

15、初的存船数加上本年度的最大可能生产量不得小于本年度的交船数 SK +6 dK此外，还有S1 = S5 =0 决策变量XK为第K阶段生产的船只数,且XK必须满足以下条件：某年末所拥有的存船数，不应超过本年度及以后各年交船数的总和： XK+ SK di某年初所拥有的存船数加上当年生产船只数量，不应少于本年度的交船数 XK + SK dK状态转移函数 S K =S K +X KdK=1,2,3,4即第K年初的存船数加上第K年船只的生产数，再减去第K年交付的船数，就等于第K+1年初的存船数。第K阶段的指标函数VK就是第K年度生产费用与存贮费用两部分之和。 0.6+C K X K +0.4S K 当X

16、K >0 VK(SK,XK) k=1,2,3，4 0.4SK 当 K=0 动态规划的基本方程为： FK(SK)=MinVK(S K, X K )+Fk+1(Sk+1) ( K=1,2,3,4) 0XK 6 F5 (S5 ) = 0阶段，K=4，d4=2 S40,1,2 X42,1,0 0.6 + 6.5X4+ 0.4S 4 当X 4 >0 V4 = 0.4S4 当 X4= 0计算结果见表所示阶段k 期初存船（S4） 可能的生产量（X4） 本期 费用（ V 4） 期末 存船（S5 ） 以后各期费用F5 (S5) 总费用V4+F5 最佳生产量（X4）40213.60013 .62117

17、.5007.51200.8000.80阶段，K=3，D3=2，故: S30,1,2,3,4 0.6 + 6.3X3+ 0.4S3 当X 3 >0 V 3 = 0.4 S3 当 X3= 0计算结果如下表阶段k 期初 存船（S3） 可能的生产量（X3） 本期 费用（ V 3） 期末 存船（S4） 以后各期费用F4(S4) 总费用V3+F4 最佳生产量（X3）30213.2013.626.8 4319.517.527425.820.826.61 1 7.3 0 13.6 20.9 3 2 13.6 1 7.5 21.1 3 19.9 2 0.8 20.7 可能的生产量（X3） 本期 费用（V

18、3） 期末 存船（S4） 以后各期费用F4(S4) 总费用V3+F4 0 0.8 0 13.6 14.4 1 7.7 1 7.5 15.2 2 14 2 0.8 14.8 01.2 17.58.7 18.1 20.88.9 0 1.6 2 0.8 2.4阶段，K=2，D2=3，故S 20,1,2,3,4,5 0.6 + 6.5X2+ 0.4S2 当X2 >0 V2= 0.4 S2 当 X2= 0计算结果见表所示阶段k 期初 存船（S2） 可能的生产量（X2） 本期 费用（ V 2） 期末 存船（S3 ） 以后各期费用F3 (S3) 总费用 V2+F3 最佳生产量（X2）20 318.60

19、26.645.2 5424.6120.745.3530.6214.445.0636.638.745.3 可能的生产量（X2） 本期 费用（V 2） 期末 存船（S3） 以后各期费用 F3 (S3) 总费用 V2+F32 13 026.6 39.63 19 120.7 39.74 25 214.439.45313 8.739.76374 2.439.417.4026.6 34213.4120.7 34.1319.4214.433.8425.43 8.734.15 31.44 2.433.8 可能的生产量（X2） 本期 费用（ V 2） 期末 存船（S3 ） 以后各期费用F3 (S3) 总费用 V

20、2+F30 1.2026.6 27.81 7.8120.7 28.52 13.8214.428.2319.83 8.728.5425.84 2.428.201.6120.7 22.318.2214.422.6214.23 8.722.9320.24 2.422.602.0214.416.418.63 8.717.3214.64 2.4 17.0阶段，K=1，D1=1，故S1 =0, X11,2,3,4,5,6 V1=0.6+6.0X1计算结果见表 阶段k 期初 存船（S1） 可能的 生产量（X1） 本期 费用（ V 1） 期末 存船（S2） 以后各期费用F2(S2) 总费用 V1+F2 最佳生

21、产量（X1）10 1 6.6 0 45.0 51.6 1212.61 39.452.0318.62 33.852.4424.63 27.852.4530.64 22.352.9636.65 16.4 53.0由表知第1年应该生产1艘船，整个过程的最小费用为F1（0）=51.6百万元。由递推关系可得问题的最佳策略，详见表 年度期初存船 (S k）最佳生产量 （X k） 期末 存船（Sk+1） 本期费用VK (SK) 最小总费用min(VK+Fk+1 ) 101 06.651.6 20 5230.645.032000.814.4402013.613 .6即第1年船厂应该安排生产1艘船，第2年安排生

22、产5艘船，第3年不安排生产，第4年安排生产2艘船，船厂按此策略安排生产计划才能既满足客户要求又能使支出总费用最小，总费用为5160万元（4）某公司有三种货物需要装飞机运输，各种货物的重量和可能获得的收益见表。飞机允许装载能力为6吨，问应如何装载才能使公司获得最大收益？货物种类（i）货物重量（W i）吨收益（Vi）(千克)12802313034180解：按货物种类划分阶段：K=1表示装载第1种货物；K=2表示装载第2种货物；K=3表示装载第3种货物。状态变量SK表示第K阶段可以利用的装载能力。 S1=6 SK=0，1，2，3，4，5，6 K=2，3决策变量XK为第K种货物的装载数量。允许决策集合

23、：XK DK (SK ) =0,1,2,-, SK / a K K=1, 2, 3 状态转移函数：SK+1=SKWKXK阶段指标函数为：VK XK动态规划基本方程： FK (SK)= Max VKXK + FK+1(SK+1) ( K=3,2,1 ) XKDK (SK ) F4(S4) = 0阶段 K=3 W3=4, V3=180, S30,1,2., 6因为X30,1, S3/4=0,1 所以：F3 (S3)=Max180X3+0 X3(0,1) S30,1,2, 6计算结果如下阶段 X3S3180X3F3 (S3) X3* S401300 00010 00120 00230 0034018

24、0+01801050180+01801160180+018012阶段 K=2 W2=3, V2=130, S20,1,2,3,4,5,6 因为: X20,1, S2/3= 0,1,2 S3=S23X2 所以: F2 (S2)= Max130X2+F3 (S3) = Max 130X2+F3 (S2-3X2)计算结果如下表818阶段 X2S2130X2+F3 (S3)F2 (S2) X2* S301 2200 00010 00120 00230130 +01301040+180130 +0 1800450+180130 +01800560+180130 +0 260+026020阶段 K=1 W

25、1=2, V1=80, S1=6因为: X10,1, 6/2=0,1,2,3 S2=S1-2X1所以: F1 (S1)=Max80X1+F2 (S2) =Max 80X1+F2 (S1-2X1) X10,1,2,3 S1=6 计算结果见表阶段X2S2 80X1+F2 (S2)F1 (S1) X1* S20123160+26080+180160+0240+02600 & 16 & 4即最优方案有二个为： (1) X1 =0 X2=2 X3 =0 F1 (S1 )=260(千元) (2) X1 =1 X2=2 X3 =1 F1 (S1 )=260(千元) 公司可获得的最大收益为260万元，此时飞机装载第2种货物2件或装载第1种货物和第3种货物各1件。（6）、有一位推销保险的先生，他的业务范围涉及中国大陆4个城市，城市间的距离见表，如他从城市1出发，经过每个城市一次且仅一次，最后又返回城市1，那么他应如何安排行进路线，使总的行程距离最小？城市Vi城市Vi 123410 679280973580846550解：动态规划基本方程为 FK ( i, S )=MinFK-1(j,S/j