运筹学考试试题答案与整理出来的复习题 下载本文

y1*=0,y2*=1

(3) 最优解不变的情况下,求产品A的利润允许变化范围; 最优解不变的情况下,?c1?0,c1?3

(4)假定能以10元的价格购进15单位的材料,这样做是否有利,为什么? 有利

单位材料的影子价格是1元,10元钱购进15单位的材料的单位价格为2/3元,低于影子价格。同时,在保持最优基不变的情况下

?30?b2?15

购进15吨的原材料,最优基不变。该材料的影子价格仍为1元。

(5)当可利用的资源增加到60单位时,求最优解。

b'?B?1b?1?1??45???15?

1????????060??12?????5??cj CB 0 5 0 5 x5 x3 XB x4 x3 b -15 12 15 9 3 x1 3 3/5 0 -3 6/5 -3 1 x2 -1 4/5 -3 1 3/5 -2 5 x3 0 1 0 0 1 0 0 x4 1 0 0 -1 1/5 -1 0 x5 【-1】 1/5 -1 1 0 0 最优解为X*=(x1,x2,x3,x4,x5)T=(0,0,9,0,15)T,最优目标值z*=45

(6)当产品B的原材料消耗减少为2个单位时,是否影响当前的最优解,为什么? x2在最有表是非基变量,该产品的原材料消耗只影响x2的检验数。

P2'?B?1P2?1?1??3??1?

1??????2???02?5???????5???2?c2?CBB?1P2'?1??1??05??2???1???5?所以最优解不变?2?0

(7)增加约束条件2x1+x2+3x3≤20,对原最优解有何影响,对对偶解有何影响? 增加的约束条件,相当于增加了一个约束方程

2x1?x2?3x3?x6?20

cj CB 0 5 0 0 5 0 x4 x3 x6 XB x4 x3 x6 b 15 6 20 15 6 2 2 x1 3 3/5 2 0 3 3/5 4/5 0 4 x2 -1 4/5 1 -3 -1 4/5 -7/5 -3 1 x3 0 1 3 0 0 1 0 0 0 x4 1 0 0 0 1 0 0 0 0 x5 -1 1/5 0 -1 -1 1/5 -3/5 -1 0 x6 0 0 1 0 0 0 1 0 对原问题的最优解无影响,对对偶问题的最优解也无影响。

二、某钻井队要从8个可供选择的井位中确定4个钻井探油,使总的钻探费用最省。若8个

井位的代号是s1、s2、…、s8,相应的钻探费用为c1、c2、…、c8,并且井位满足下列条件限制:(10分) i. 或选择s1和s7,或选择s8; ii. s6和s7中选一个; iii. s2和s5不能同时选; iv. 选择了s1的话就不能选择s4; v. 选择了s2的话必须选择s3

试用:整数规划方法建模。

?1当选择si令:xi???0当不选择simaxz?c1x1?c2x2?c3x3?c4x4?c5x5?c6x6?c7x7?c8x8 ?x1?x7?x8?1?x?x?17?6??x2?x5?1??x1?x4?1?x2?x3?0???xi?0或1

四、A、B两个煤矿负责供应甲、乙、丙三个城市煤炭。已知A、B两矿年产量、三个城市的需求量以及从两煤矿至各城市煤炭运价如下表。由于供不应求,经协商,甲城市必要时可少供应0-30万吨,乙城市需求须全部满足,丙城市需求不少于270万吨。试求:将甲、乙两矿煤炭全部分配出去,满足上述条件又使总运费最低的调运方案。(15分) 产 销 A B 销量(T) 甲 15 21 320 乙 18 25 250 丙 22 16 350 产量 400 450 解:(1)依题意得产销平衡表如下: 产 甲’ 销 A B C 销量(T) 15 21 M 290 15 21 0 30 18 25 M 250 22 16 M 270 22 16 0 80 400 450 70 甲’’ 乙 丙’ 丙’’ 产量

(2)做初始的调运方案(伏格尔法) 产 甲’ 销 A B C 销量(T) 290 15 150 140 M 30 甲’’ 15 21 30 0 250 乙 18 15 21 M 270 丙’ 22 250 18 25 270 M 22 16 10 70 80 丙’’ 22 U 0 70 22 16 450 400 甲’’ 乙 丙’ 丙’’ 产量 (3)用位势法进行检验 产 甲’ 销 A 15 0 B C V 0 M-5 21 21 M 0 0 -5 21 21 0 1 M-8 24 25 M 12 0 16 16 M 12 0 0 16 16 0 -6 0 -16 0

(4) 做闭回路调整 调整后为:

产 甲’ 销 A B C 销量(T) 290

(5)进行进一步检验 产 甲’ 销 A B C V 0 M-5 21 M 0 15 21 0 5 0 16 0 15 21 1 M-8 24 M 0 18 25 12 0 M 16 M 22 16 12 0 0 16 0 22 16 -6 0 -16 甲’’ 乙 丙’ 丙’’ U 15 150 140 M 21 30 30 0 250 15 21 M 270 250 18 25 270 M 22 16 40 40 80 0 70 22 16 450 400 甲’’ 乙 丙’ 丙’’ 产量 (6) 调整后的方案为最优方案 最低费用=150×15+250×18+140×21+270×16+40×16+30×0+40×0=14650

五、分配甲、乙、丙、丁四人去完成5项任务。每人完成各项任务时间如下表所示。由于任务数多于人数,故规定其中有一人可兼完成两项任务,其余三人每人完成一项,试确定总花费时间最少的指派方案。(15分)

甲 乙 丙 丁 A 25 39 34 24 B 29 38 27 42 C 31 26 28 36 D 42 20 40 23 E 37 33 32 45 解:假设增加一个人戊完成各项工作的时间取A、B、C、D、E最小值。 得效率矩阵为: