第六章---运筹学-整数规划案例

时间：2020-11-03 20:18:23　来源：勤学考试网本文已影响人

第六章整数规划

用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域 ( 在图上用“×” 标出 ) 。

1 、 max z=3 x1+2x2

. 2 x1+3x2≤ 12

2x1+x2≤ 9

x1、x2≥ 0

解：

2 、 min f=10 x1+9x2

. 5 x1+3x2≥ 45

x1 ≥ 8

x2 ≤ 10

x1、x2≥ 0

求解下列整数规划问题

1 、 min f=4 x1+3x2+2x3

. 2 x1-5 x2+3x3≤ 4

4x1+x2+3x3≥3

x2+x3≥ 1

x1、x2、x3=0 或 1

解：最优解（ 0， 0， 1），最优值： 2

2 、 min f=2 x1+5x2+3x3+4x3

. -4 x1+x2+x3+x4≥2

-2 x1+4x2+2x2+4x2≥ 4

x1+x2- x2+x2≥ 3

x1、x2、x3、x3=0 或 1

解：此模型没有可行解。

3、max Z=2 x1+3x2+5x3+6x4

. 5 x1+3x2+3x3+x4≤ 30

2x1+5x2- x2+3x2≤ 20

- x1+3x2+5x2+3x2≤ 40 3x1- x2+3x2+5x2≤ 25

x1、x2、x3、x3=正整数

解：最优解（ 0， 3， 4，3），最优值： 47

4、 min z =8 x1 +4 x 2+3 x 3 +5 x 4+2 x 5＋ 3 x 6＋ 4 x 7＋ 3 x 8+4 x 9+9 x 10+7 x 11 +

5 x 12 +10 x 13+4 x 14+2 x 15+175 x 16+300 x 17+375 x 18 +500 x 19

约束条件 x1 + x 2+x3≤ 30

x4 + x 5＋ x 6-10 x 16 ≤0 x7 + x 8＋ x 9-20 x 17 ≤0 x10 + x 11＋ x 12-30 x 18≤ 0 x13 + x 14＋ x 15-40 x 19≤ 0

x1 + x 4+ x 7+x10+ x 13＝ 30 x2 + x5+ x 8+x11+ x 14＝ 20 x3 + x 6+ x 9+x12+ x 15＝ 20

xi 为非负数（ i=1,2 ? ..8 ）

xi 为非负整数（ i=9,10 ?..15 ）

xi 为为 0－ 1 变量（ i=16,17 ? ..19 ）

解：最优解（ 30， 0， 0， 0，0， 0， 0，0， 0， 0， 0， 0， 0， 20， 20， 0， 0，0， 1），最优值： 860

一餐饮企业准备在全市范围内扩展业务，将从已拟定的 14 个点中确定 8 个点建立分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的 14 个店的费用情况如下表：

店名 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14

费用 ( 万元 )

公司办公会决定选择原则如下：

B5、B3 和 B7 只能选择一个。

选择了 B1 或 B14 就不能选 B6。

B2、B6、B1、B12，最多只能选两个。

B5、B7、B10、B8，最少要选两个。

　问应选择哪几个点，使总的建店费用为最低解：数学模型：

min f ＝ x 1+ x 2+ x 3+ x 4+ x 5+ x 6+ x 7+ x 8+ x 9+3 x 10+ x 11+ x 12+ x 13+ x 14

. x 1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14=8

x 3+ x 5-2 x 7=2

x 1+ x 6=1

x6+ x 14 =1

x1+x2+x6+x12≤ 2

x5+x7+x8+x10≥ 2

xi ≥0 且 xi 为 0－ 1 变量， i ＝ 1，2， 3，?， 14。

最优解：（ 1， 1， 1， 1， 1， 0， 0， 0， 1， 0， 0， 0， 1， 1）最优值：。即： B1， B2， B3， B4,B5,B9,B13,B14 选中，建店的最低费用万元。

有四个工人（甲、乙、丙、丁），要分别指派他们完成四项不同的工作（ A、B、C、D），请按以下要求求解指派问题。

1、每人做各项工作所消耗的时间如下表所示，问应如何分配工作，才能使总的消耗时间为最少

是工作

否

每人完成各项工作的所需时间小时

工人分配甲1816-19乙-201620

工人

分

配

甲

乙

丙

丁

2、每人做各项工作所创的利润如下表所示，问应如何指派工作，才能使总的创利为最

多

所工作

创

利

工人益

工作 A 工作 B 工作 C 工作 D

甲 4 5 7 9

乙 7 5 6 8

丙 3 4 3 5

丁 7 6 8 8

解： 1、消耗时间为最少问题线性规划数学模型：

min f = 18x1+16x2+19x3+20x4+16x5+20x6+19x7+18x8 +17x9+21x10+12x11+15x12 +20x13

. x 1+x2+x3 =1

x4+x5+x6=1 x7+x8+x9+x10=1 x11+x12+x13=1 x1+x7+x11 =1

x2+x4+x8 +x12 =1

x5+x9+x13 =1

x3+x6+x10 =1

xi ≥ 0 且 xi 为 0－ 1 变量， i ＝1， 2， 3，?， 13。

最优解：（ 0， 1， 0， 0， 1， 0， 0， 0， 0， 1， 1， 0， 0，），最优值： 65。

即：给甲分配工作 B，给乙分配工作 C，给丙分配工作 D，给丁分配工作 A，所用最少的时间为 65 小时。

2、总的创利为最多问题线性规划数学模型：

max Z = 41+52+73+94+75+5x6+6x7+8x8+3x9+4x10 +3x11+5x12+7x13+6x14+8x15+8x16

. x 1+x2+x3 +x4 =1

x5+x6+x7+x8=1 x9+x10+x11+x12=1 x13+x14+x15+x16=1 x1+x5+x9 +x13 =1 x2+x6+x10+x14=1 x3+x7+x11+x15=1 x4+x8+x12+x16=1

xi ≥ 0 且 xi 为 0－ 1 变量， i ＝ 1，2， 3，?， 16

最优解：（ 0， 0， 0， 1， 1， 0， 0， 0， 0， 1， 0， 0， 0， 0,1,0 ），最优值： 28。

即：给甲分配工作 D，给乙分配工作 A，给丙分配工作 B，给丁分配工作 C，所创最多的利润为 28 元。

某企业在 A1 地已有一个工厂，其产品的生产能力为 3 万箱，为了扩大生产，打算在 A2， A3，A4，A5 地中再选择几个地方建厂。已知在 A2 地建厂的固定成本为万元，在 A3 地建厂的固定成本为 30 万元，在 A4 地建厂的固定成本为万元，在 A5 地建厂的固定成本为 50 万元，另外，五个产地建成后的产量、销地的销量以及产地到销地的单位运价（万元 / 万箱）如下表所示。

运销地

输

价

产地格

B1 B2 B3

固定成本

（万元）

产量（万箱）

A1 8 4 3 0 3

A2 5 2 3 1

销量（箱）

（ 1）问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小；

（ 2）如果由于政策要求必须在 A2， A3 地建一个厂，应在哪几个地方建厂

解（ 1）

整数规划数学模型：

min z =8 x1 +4 x 2+3 x 3+5 x 4+2 x 5＋ 3 x 6＋ 4 x 7＋ 3 x 8+4 x 9+9 x 40+7 x 11+

5 x 12 +10 x 13+4 x 14+2 x 15+ x 16 +30x17+ x 18 +50 x 19

. x1 + x 2+x3≤ 3

x4 + x 5＋ x 6- x 16≤ 0 x7 + x 8＋ x 9-2 x17≤ 0 x10 + x 11＋ x 12-3 x18≤ 0 x13 + x 14＋ x 15-4 x19≤ 0

x1 + x 4+ x 7+x10+ x 13＝ 3 x2 + x5+ x 8+x11+ x 14＝ 2 x3 + x 6+ x 9+x12+ x 15＝ 2

xi 为非负整数 (i=1,2 ? ..15)

xi 为 0－1 变量 (i=16,17 ?..19)

最优解：（ 3， 0， 0， 0， 0， 0， 0， 0， 0， 0， 0， 0， 0， 2， 2， 0， 0，0， 1）最优值： 86。

即：安排 A1 地到 B1 地 3 万箱， A5 地到 B2， B3 地各 2 万箱，选中 A5 地。

(2) 我们只要在以上模型上加上一个约束条件： x16+ x 17=1，就得到了问题（ 2）的数学模型：

min z =8 x1 +4 x 2+3 x 3+5 x 4+2 x 5＋ 3 x 6＋ 4 x 7＋ 3 x 8+4 x 9+9 x 40+7 x 11+

5 x 12 +10 x 13+4 x 14+2 x 15+ x 16 +30x17+ x 18 +50 x 19

. x1 + x 2+x3≤ 3

x4 + x 5＋ x 6- x 16≤ 0 x7 + x 8＋ x 9-2 x17≤ 0 x10 + x 11＋ x 12-3 x18≤ 0 x13 + x 14＋ x 15-4 x19≤ 0

x1 + x 4+ x 7+x10+ x 13＝ 3 x2 + x5+ x 8+x11+ x 14＝ 2 x3 + x 6+ x 9+x12+ x 15＝ 2 x16 + x 17=1

xi 为非负整数 (i=1,2 ? ..15)

xi 为 0－1 变量 (i=16,17 ?..19)

最优解：（ 0， 1， 2， 0， 1， 0， 0， 0， 0， 3， 0， 0， 0， 0， 0， 1， 0， 1，0）最优值： 94。

即：安排 A1 地到 B2 地 1 万箱， B3 地 2 万箱

A2 地到 B2 地 1 万箱A4 地到 B1 地 3 万箱A4 地到 B1 地 3 万箱选中 A2，A4 两地。

某航空公司经营兰州、北京、广州三个城市之间的航线，其中兰州—北京飞行时间为 2

设飞机在机场停留期间的费用与停留时间的平方成正比，又每架飞机从降落到再起飞至少需要 2 小时的时间准备。确定一个使总的停留费用损失为最小的方案。解：现在有两本题需注意的两个问题、三个城市间的飞行，航班的安排分别是在三个城市中完成的；、到站的航班必须 2小时后才能起飞。这是一个指派问题，（ 1）

设飞机在机场停留期间的费用与停留时间的平方成正比，

又每架飞机从降落到再起飞至

少需要 2 小时的时间准备。确定一个使总的停留费用损失为最小的方案。

解：现在有两本题需注意的两个问题

、三个城市间的飞行，航班的安排分别是在三个城市中完成的；

、到站的航班必须 2小时后才能起飞。这是一个指派问题，

（ 1）城市兰州

效益表：

起

到达

飞

1011 2011 2012 1012 1013 起飞

航班号

起飞城市

起飞时间

到达城市

到达时间

1011

兰州