线性规划习题(18)

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 当不选择si max z ? c1 x1 ? c2 x2 ? c3 x3 ? c4 x4 ? c5 x5 ? c6 x6 ? c7 x7 ? c8 x8 ? x1 ? x 7 ? x8 ? 1 ?x ? x ? 1 7 ? 6 ? x2 ? x5 ? 1 ? ? ? x1 ? x4 ? 1 ? x2 ? x3 ? 0 ? ? xi ? 0或1 ?

四、A、B 两个煤矿负责供应甲、乙、丙三个城市煤炭。已知 A、B 两矿年产量、三个城市 的需求量以及从两煤矿至各城市煤炭运价如下表。由于供不应求，经协商，甲城市必要时可 少供应 0－30 万吨，乙城市需求须全部满足，丙城市需求不少于 270 万吨。试求：将甲、乙 两矿煤炭全部分配出去，满足上述条件又使总运费最低的调运方案。 （15 分） 产 A B 销 甲 15 21 乙 18 25 丙 22 16 产量 400 450

销量（T）

320

250

350

解：(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 150 B 140 C 销量（T） 产 销 A 0 B 0 C M-5 V 21 M -5 21 21 0 0 M-8 24 16 15 0 21 1 M 15 0 25 0 M 0 16 18 12 16 0 0 -16 22 12 16 0 22 -6 290 甲’ M 30 甲’’ 21 30 0 250 乙 M 21 15 15 250 25 270 M 70 270 丙’ 80 丙’’ U （3）用位势法进行检验 16 10 0 70 16 450 18 22 22 400 甲’ 甲’’ 乙 丙’ 丙’’ 产量

(4) 做闭回路调整 调整后为： 产 销 A 150 B 140 C M 30 0 M 21 21 15 15 250 25 270 M 40 16 40 0 70 16 450 18 22 22 400 甲’ 甲’’ 乙 丙’ 丙’’ 产量

销量（T）

290

30

250

270

80

（5）进行进一步检验 产 销 A 0 B 0 C M-5 V 21 M 0 16 21 5 0 M-8 24 15 0 21 1 M M 16 15 0 25 0 M 0 16 18 12 16 0 0 -16 22 12 16 0 22 -6 甲’ 甲’’ 乙 丙’ 丙’’ U

(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