第六章_整数规划 (1)

运筹学运 筹 帷 幄 之 中 决 胜

整数规划

千 里 之 外

教学要求 掌握线性整数规划的建模方法，特别是0-1变量的运用； 掌握分支定界求解方法的基本原理； 了解割平面求解方法的基本原理； 重点掌握指派问题的建模与求解。

整数规划建模 分枝定界法 割平面法 指派问题

重点：分枝定界、隐枚举法 难点：分枝定界法、指派问题求解

目录 第一节 整数规划实例与模型 第二节 0-1整数规划的建模方法 第三节 分支定界法 第四节 割平面法 第五节 指派问题 第六节 应用举例和Excel求解

第一节 整数规划实例与模型

在现实生活中，经常遇到一些需要变量取整数才 有实际意义的问题，例如制定计划、规划时需要 确定工人的人数，设备的台数等。 许多有名的最优化问题，如旅行商问题、背包问 题、下料问题、工序安排问题等，也都可以归结 为整数规划问题。

第一节 整数规划实例与模型一、实例1某工厂准备备用集装箱托运甲、乙两种货物，已知， 每箱货物的体积、利润、重量、托运限制如下表，问甲 乙两种货物各托运多少箱才能使总利润最大？货物 甲 每箱体积 每箱重量 每箱利润 5 2 20

乙托运限制

424

513

10

解：设甲乙两种货物各托运x1,x2箱，依题意得： Max z=20x1+10x2 s.t 5x1+4x2≤24 2x1+5x2 ≤13 x1,x2≥0 x1,x2取整数

第一节 整数规划实例与模型一、实例2 现有一位于城市B5的工厂，其年生产量是30000 件，产品被运往A1,A2,A3三个城市的销售中心。经 预测该厂产品的需求量将会增长，工厂决定将在B1, B2,B3,B4四个城市中的一个或多个城市中新建工厂 以增加生产力。综合考虑在这四个城市中新建工厂的 年固定成本和生产能力，以及每件产品从每个工厂送 到每个销售中心的运费。问如何选择新的厂址，才能 使该工厂每年的总成本最小。

第一节 整数规划实例与模型生产地 B1 B2 B3 B4 B5 需求量 销售中心 A1 5 4 9 10 8 30 A2 2 3 7 4 4 2010 20 30 40

A3 3 4 5 2 3 20

年固定成 年生产力 本 (千件) 175 300 375 500 10 20 30 40

B1B2 B3 B4 B5

A1 A2 A3

30 20

20

总成本=年固定成本+运输成本

30

第一节 整数规划实例与模型首先做如下假设： 如果在B1建新厂，y1=1;否则，y1=0。 如果在B2建新厂，y2=1;否则，y2=0。 如果在B3建新厂，y3=1;否则，y3=0。 如果在B4建新厂，y4=1;否则，y4=0。 xij:表示从工厂i 到销售中心j的运输量；i=1,…,5;j=1,2,3。 利用已知的数据，年运输成本为： TC1=5x11+2x12+3x13+4x21+3x22+4x23+9x31+7x32 +5x33+10x41+4x42+2x43+8x51+4x52+3x53

建新工厂的年固定成本为：TC2=175y1+300y2+375y3+500y4; 总成本为：TC=TC1+TC2; 生产能力的约束条件为：

从新工厂B1运到A1,A2,A3三个城市销售中心的总量应小于等 于B1的生产能力，所以约束条件为： x11+x12+x13≤10y1 B1的生产能力； 同理可得： x21+x22+x23≤20y2 B2的生产能力； x31+x32+x33≤30y3 B3的生产能力； x41+x42+x43≤40y4 B4的生产能力； x51+x52+x53≤30 B5的生产能力； 三个销售中心的需求量为： x11+x21+x31+x41+x51=30 A1的需求量； x12+x22+x32+x42+x52=20 A2的需求量； x13+x23+x33+x43+x53=20 A3的需求量；

第一节 整数规划实例与模型所以选址模型为： min TC= TC1+TC2 s.t.x11+x12+x13≤10y1 x21+x22+x23≤20y2 x31+x32+x33≤30y3 x41+x42+x43≤40y4 x51+x52+x53≤30 x11+x21+x31+x41+x51=30 x12+x22+x32+x42+x52=20 x13+x23+x33+x43+x53=20xij≥0,对所有的i,j; y1,y2,y3,y4=0,1

第一节 整数规划实例与模型二、整数规划一般模型max( 或 min) ci xii 1 n

s.t.

a xi 1 i

n

i

b (或 b 或 b)

xi 0, 且为整数或部分为整数 i 1,2, , n如果决策变量全部为整数，则称为纯整数规划 部分决策变量是整数，其他变量可以是非整数，则称为混合整数 规划 如果变量仅取0或1,此时的整数规划称为 0-1规划，是整数规 划的特殊情况

第一节 整数规划实例与模型整数规划模型是一类特殊的线性规划模型，但用 求解线性规划模型的单纯形法所得到的最优解往往不能 保证其一定是整数。 解相应的线性规划问题得到最优解之后，采用最 优解凑整的方法，往往得不到整数规划的最优解，甚至 得不到可行解

第一节 整数规划实例与模型Max z=20x1+10x2 s.t 5x1+4x2≤24 2x1+5x2 ≤13 x1,x2≥0,且为整数将x1,x2取 整条件去掉

Max z=20x1+10x2 s.t 5x1+4x2≤24 2x1+5x2 ≤13 x1,x2≥0

通过单纯法可求得最优解为x1=4.8,x2=0 maxz=96 若采用凑整的方法得 (1) X1=5 x2=0 根本不是原整数规划的可行解 (2) x1=4 x2=0 z=80 不是整数规划的最优解 实际上原问题的最优解为 X1=4,x2=1 max z=90

第一节 整数规划实例与模型用穷举法求解： Max z=20x1+10x2 s.T 5x1+4x2≤24 ① 2x1+5x2 ≤13 ② x1,x2≥0,且为整数 解：在① ②中令x2=0 得 x1≤[24/5]=4 x1 ≤[13/2]=6 所以 x1 只能取 0,1,2,3,4 同理 在① ②中令x1=0 得 0≤x2 ≤2 故 x2只能取0,1,2 x1 ≤4

第一节 整数规划实例与模型点(0,0) (0,1) (0,2)

条件

可行解

Z值0 10 20

(1,0)(1,1) (1,2) (2,0) (2,1) (2,2) (3,0) (3,1) (3,2) (4,0) (4,1) (4,2)

① √ √ √ √ √ √ √ √ √ √ √ √ √ √

② √ √ √ √ √ √ √ √ √ √ √ √

√ √ √ √ √ √ √ √ √ √ √ √

2030 40 40 50 1 60 70 1 80 90