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最小值。 得效率矩阵为：