当前位置：文档之家 › 整数规划-模型资料

整数规划-模型资料

  • 格式：ppt
  • 大小：811.50 KB
  • 文档页数：16

下载文档原格式

  / 16

合集下载

(完整word版)整数规划的数学模型及解的特点

(完整word版)整数规划的数学模型及解的特点

整数规划的数学模型及解的特点整数规划IP (integer programming)：在许多规划问题中，如果要求一部分或全部决策变量必须取整数。

例如，所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP 。

松弛问题(slack problem)：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。

若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integer linear programming)。

一、整数线性规划数学模型的一般形式∑==nj jj x c Z 1min)max(或中部分或全部取整数n j nj i jij x x x mj ni x b xa ts ,...,,...2,1,...,2,10),(.211==≥=≥≤∑=整数线性规划问题可以分为以下几种类型1、纯整数线性规划(pure integer linear programming)：指全部决策变量都必须取整数值的整数线性规划。

有时，也称为全整数规划。

2、混合整数线性规划(mixed integer liner programming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。

3、0—1型整数线性规划(zero —one integer liner programming)：指决策变量只能取值0或1的整数线性规划。

1 解整数规划问题0—1型整数规划0—1型整数规划是整数规划中的特殊情形，它的变量仅可取值0或1，这时的⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤+≥+≤-+=且为整数0,5210453233max 2121212121x x x x x x x x x x z变量xi 称为0—1变量，或称为二进制变量。

0—1型整数规划中0—1变量作为逻辑变量(logical variable)，常被用来表示系统是否处于某一特定状态，或者决策时是否取某个方案。

整数规划模型

整数规划模型

决策变量全部取 0 或1的规划称为0-1 整数规划
王秋萍：整数规划模型
为(非负)整数
仅一部分变 量为整数
4
有些问题用线性规划数学模型无法描述，可以 通过设置逻辑变量建立整数规划的数学模型。
王秋萍：整数规划模型
5
逻辑变量在建立数学模型中的作用
m个约束条件中只有k个起作用
设m个约束条件可表为
∑a x
ij j =1
n
j
≤ bi
i = 1, 2, " , m
定义 又M为任意大的正数，则
n ⎧ ⎪ ∑ aij x j ≤ bi + Myi j =1 ⎨ ⎪ y + y +" + y = m − k 2 m ⎩ 1
王秋萍：整数规划模型
6
逻辑变量在建立数学模型中的作用
约束条件的右端项可能是r个值 ( b1 , b2 ," , br ) 中的一个，即 n
( i = 1," , m; j = 1," , m ) 则分配问题的数学模型为 min z = ∑∑ a x
m m i =1 j =1 ij
ij
⎧ m xij = 1 ( i = 1,", m ) ⎪ ∑ j =1 ⎪ m ⎪ ( j = 1,", m ) ⎨ ∑ xij = 1 ⎪ i =1 ⎪ xij = 0或1 ( i = 1," , m; j = 1," , m ) ⎪ ⎩
j = 1, 2, 3 ⎧ x j − My j ≤ 0 ⎪ x + x + x ≥ 4000 ⎪ 1 2 3 ⎨ ⎪ x1 ≤ 1500, x2 ≤ 2000 ⎪ ⎩ x j ≥ 0, y j = 1或0, j = 1, 2, 3
数学建模 -整数规划

数学建模 -整数规划

z1 3
松弛问题 L0： max z 30x1 20x 2 2 x1 3 x 2 14.5 s.t 4 x1 x 2 16.5 x1 0, x 2 0
z 2 130 剪枝 ( IP)的最优解：x 3，x 2 1 2
最优值：Z * 130
4x1+x2=16.5
3 L3：xx21 2 z 3 130 关闭
11 L4 x1 4 ，x2 3 28543;3x2=14.5
L5 x1 2，x2 7
剪枝 z 130 5
2
L6 剪枝
无可行解
· · · · · · · · · 1 2 3 4 5 6 7

19:01
分枝定界法

分枝定界法

（1）分枝：通常，把全部可行解空间反复地分割为越 来越小的子集，称为分枝； （2）定界：并且对每个子集内的解集计算一个目标下 界（对于最小值问题），这称为定界。 （3）剪枝：在每次分枝后，凡是界限超出已知可行解 集目标值的那些子集不再进一步分枝，这样，许多子 集可不予考虑，这称剪枝。 求解生产进度问题、旅行推销员问题、工厂选址问题、 背包问题及分配问题。
对（ IP） max z 30x1 20x 2 2 x1 3x 2 14.5 4 x1 x 2 16.5 s.t x 0, x 2 0 1 x1 , x 2为整数
父问题
松弛问题 ( L0 )： max z 30x1 20x 2 2 x1 3 x 2 14.5 s.t 4 x1 x 2 16.5 最优解： x1 3.5, x1 0, x 2 0
x 2 2 .5
子问题
( L1 ) max z 30x1 20x 2 ( L ) max z 30x 20x 2 1 2 2 x1 3 x 2 14.5 2 x1 3x2 14.5 4 x1 x 2 16.5 4 x1 x2 16.5 s.t s.t x1 3 x1 4 x1 0, x 2 0 x1 0, x2 0
整数规划(整数规划)

整数规划(整数规划)

想一想：
在生产管理和经营活动中若要求解：
• 安排上班的人数 • 运输车辆台数
第八章
整数规划（IP）
(Integer Programming)
主要内容： §1 整数规划的模型（掌握） §2 整数规划的计算机求解（掌握） §3 整数规划的应用（掌握）
（补充指派问题的匈牙利解法）
一、整数规划的模型
（一）整数规划实例 例1：某公司拟用集装箱托运甲、乙两种货物， 这两种货物每件的体积、重量，可获利润以及 托运所受限制如表所示：
用 图 解法求出最优解 x1＝3/2, x2 = 10/3 且有MaxZ = 29/6
x2
3
⑴
⑵
(3/2,10/3)
现求整数解（最优解）： 如用“舍入取整法”可得 到4个点即(1，3) (2，3) (1，4)(2，4)。显然，它们 都不可能是整数规划的最 优解。
3
x1
按整数规划约束条件，其可行解肯定在线性规划问题 的可行域内且为整数点。故整数规划问题的可行解集 是一个有限集，如图所示。
工作 人
B1 a11 a21 a31
B2 a12 a22 a32
B3 a13 a23 a33
A1 A2 A3
要求：1.将此分配问题的求解转化为一个网络图中求始点 与终点之间的最短路问题，画出该网络图，注明 节点和边的含义，并标明每一条边的aij值； 2.以上述网络图为基础，利用0－1变量建立该最短 路问题的0－1整数规划模型，列出该模型的数学 表达式。
设决策变量
xij =
1
0
分配第i 个人去做第j 件工作
相反
n
( I,j=1.2. …n )
min Z 其数学模型为：
c
整数规划模型

整数规划模型

整数规划模型整数规划模型是一种数学模型，用于解决优化问题。

在整数规划中，决策变量必须是整数。

这种模型广泛应用于工程、科学、运筹学和管理等领域。

整数规划模型的一般形式如下：\[\text{maximize} \quad c^Tx\]\[\text{subject to} \quad Ax \leq b\]\[x_j \text{整数} , j = 1,2,...,n\]其中，c是一个n维向量，表示目标函数的系数；x是n维向量，表示决策变量；A是m×n维矩阵，表示约束条件的系数矩阵；b是一个m维向量，表示约束条件的上界。

整数规划模型的目标是找到一个满足约束条件的决策变量向量x，使得目标函数值最大或最小。

由于决策变量必须是整数，所以整数规划模型要比普通的线性规划模型更复杂。

整数规划模型可以应用于许多实际问题。

例如，一个公司要决定生产哪种产品以最大化利润，但每种产品有一定的生产限制，需要整数规划模型来确定生产量；一个配送中心要决定如何分配物流资源以最小化成本，但每个分配决策都必须是整数，需要整数规划模型来求解。

求解整数规划模型可以使用多种算法。

例如，分支定界算法通过将问题分解为一个个子问题，并通过剪枝策略来减少搜索空间，最终找到最优解；约简与延迟约束算法通过线性松弛将整数规划转化为一个松弛线性规划问题，并通过迭代加入约束条件来逼近整数解。

整数规划模型的求解过程需要注意一些问题。

首先，由于整数规划是一个NP难问题，没有通用的多项式时间算法可以解决所有情况。

其次，整数规划模型可能有多个最优解，求解算法可能只能找到其中一个最优解。

最后，整数规划模型的求解过程可能需要大量的计算资源和时间。

总之，整数规划模型是一种重要的数学模型，可以用于解决各种实际优化问题。

但由于其复杂性和求解困难，需要合理选择算法和求解策略来获得满意的结果。

5 整数规划模型

5 整数规划模型

n
装第 i 件物品，价值ci 使价值达最大 装第 i 件物品，体积为 bi 共有容积为 b
max z ci xi ,
s.t.
与投资决策问题模型相同
0-1 i 1 规划 xi 0或1, i 1,2,, n
i i
b x
n
i 1
ILP
b,
5.3 合理下料问题
问 题 建 模
设要利用某类钢板下m 种零件的毛料。已知在一块钢板上， 已设计出 n 种不同的下料方案，设在第 j 种下料方案中， 可下得第 i 种零件的个数为 aij ，第 i 种零件的需要量为 bi 。 问应如何下料，才能既满足需要，又使所用钢板总数最少。 设采用第 j 种方案下料的钢板数为xj
x1 0, x2 0, x3 80
x1 0, x2 80, x3 0
x1 0, x2 80, x3 80
x1 80, x2 0, x3 0
x1 80, x2 80, x3 0

方法1：分解为8个LP子模型 其中3个子模型应去掉，然后 逐一求解，比较目标函数值， 再加上整数约束，得最优解：
i i
b x
n
i 1
ILP
b,
5.2 背包问题
问 题 建 模
设有一个容积为 b 的背包，有 n 个体积分别为 bi ，价值分 别为 ci 的物品可以装入背包，问应选择哪几件物品装入背 包，才能得到最大的使用价值。建数学模型 令
1, xi 0,
若装第 i 件物品， 否则，i 1,2,, nmax z cij xij ,
m
n
s.t.
x
i 1
m
x
j 1
i 1
整数规划(数据模型与决策)

整数规划(数据模型与决策)


0-1型整数线性规划：决策变量只能取值0或1的整数线性 规划。
整数规划的特点及应用
Page 4
例:指派问题或分配问题。人事部门欲安排四人到四个不同岗 位工作，每个岗位一个人。经考核四人在不同岗位的成绩 （百分制）如表所示，如何安排他们的工作使总成绩最好。
工作
人员 甲 乙 丙 丁
A 85 95 82 86
1 x ij 0
指派第 i个 人 做 第 j件 事 ( i , j 1,2,..., n) 不指派第 i个 人 做 第 j件 事
分配问题与匈牙利法
指派问题的数学模型为：
Page 8
min Z
c
i 1 j 1
n
n
ij
x ij
n x ij 1 ( i 1.2. .n) j 1 n x ij 1 ( j 1.2. .n) i 1 x ij 取0或1(i , j 1.2. .n)
Page 19
0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0
0 Ø 6 0 ◎ Ø 0
13 7 ◎ 0 ◎ 0 6 9 5 3 2 1 ◎ 0 Ø 0
独立0元素的个数为4 , 指派问题的最优指 派方案即为甲负责D工作，乙负责B工作， 丙负责A工作，丁负责C工作。这样安排 能使总的工作时间最少，为4＋4＋9＋11 ＝28。
2）试指派（找独立0元素）
Page 22
2 2 4 4 0
0 4 2 4 5 0 3 0 1 0 1 3 0 3 5 1 2 3 0 5
2 2 4 4 ◎ 0
◎ 0
5 1 0 Ø 2
4 2 4 0 3 ◎ 0 Ø ◎ 0 1 3 3 5 1 3 Ø 0 5
31 整数规划数学模型 Mathematical Model of IP32 整数规划

31 整数规划数学模型 Mathematical Model of IP32 整数规划


背包约束 旅行箱约束
其中M为充分大的正数。
当使用背包时( y1=1, y2=0 )，式(b)和(d)是多余的；
当使用旅行箱时( y1=0, y2=1 )，式(a)和(c)是多余的。
8 第3章整数规划
3.1 整数规划的数学模型
同样可以讨论对于有m个条件互相排斥、有m （≤m、≥m）个条件起作用的情形。 （1）右端常数是k个值中的一个时，类似式(3-2)的约束 条件为
5 第3章整数规划
3.1 整数规划的数学模型
【例3-2 】在例3-1中，假设此人还有一只旅行箱，最大 载重量为 12 公斤，其体积是 0.02m3 。背包和旅行箱只能 选择其一，建立下列几种情形的数学模型，使所装物品 价值最大。 （1）所装物品不变； （2）如果选择旅行箱，则只能装载丙和丁两种物品， 每件物品的重量、体积和价值如下表所示
第3章
整 数 规 划
Integer Programming
3.1 整数规划数学模型 Mathematical Model of IP 3.2 整数规划的求解 Solving Integer Programming 3.3 0－1规划的求解 Solving Binary Integer Programming
物品 丙 丁 重量（公斤/件） 体积（m3/件） 价值(元/件) 1.8 0.6 0.0015 0.002 4 3
第3章整数规划
6
3.1 整数规划的数学模型
【解】（1）引入0－1变量 yj，令
采用第j种方式装载时 1, yj 0， 不采用第j种方式装载时 ( j 1, 2)
j=1,2分别是采用背包及旅行箱装载。
a
j 1
9
n
ij
x j bi yi ，
0-1整数规划模型1

0-1整数规划模型1


二、指派问题
例 有一份说明书，需译成
英、日、德、俄四种文字。
任务
现有甲、乙、丙、丁四个人， 人员
他们将说明书译成不同文字
甲
所需的时间如下表。问应指
乙
派哪个人完成哪项工作，使
丙
所需的总时间最少？
丁
EJGR
2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9
一般地，有n项任务、n个完成人，第i人完成第j
例1（布点问题）某城市共有6个 地 1 2 3 4 5 6
区，每个区都可以建消防站。 区
市政府希望设置的消防站最少，1 0 10 16 28 27 20
2 10 0 24 32 17 10
但必须满足在城市任何地区发
生火火警时最，优消解防车要在15分
3 4
16 24 0 12 27 21 28 32 12 0 15 25
例：求max Z 3x1 5x2 2x3
x1 2x2 x3 2
s.t

x1 4x2 x1 x2

x3

42 3
（x1 x2 x3) Z值
（0 0 0） 0

4x2 x3 6
x1, x2, x3 0或1
（0 0 1） -2 （0 1 0） 5
钟内赶到x现2=场1,。x4据=1实地测定，
各区之间消防车行驶的时间见
5 6
27 17 27 15 0 14 20 10 21 25 14 0
右表。 请为该市制定一个 布点问题模型：
最节省的最计优划值
min Z x1 x2 x3 x4 x5 x6
解：xi
01型整数规划模型

01型整数规划模型

§5.4 0—1型整数规划模型1、 0—1型整数规划模型概述整数规划指的是决策变量为非负整数值的一类线性规划，在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主要有分枝定界解法及割平面解法（这里不作介绍，感兴趣的读者可参考相关书籍）。

在整数规划问题中，0—1型整数规划则是其中较为特殊的一类情况，它要求决策变量的取值仅为0或1，在实际问题的讨论中，0—1型整数规划模型也对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例，以说明这个事实。

0—1型整数规划的的数学模型为： 目标函数nn x c x c x c z M i n M a x +++= 2211)(约束条件为：⎪⎪⎩⎪⎪⎨⎧==≥≤++=≥≤++=≥≤++1 | 0 ) ,() ,() ,(22112222212111212111n m n mn m m n n n n x x x b x a x a x a b x a x a x a b x a x a x a , , ,21这里，0 | 1表示0或1。

2、0—1型整数规划模型的解法0—1型整数规划模型的解法一般为穷举法或隐枚举法，穷举法指的是对决策变量nx x x , , ,21 的每一个0或1值，均比较其目标函数值的大小，以从中求出最优解。

这种方法一般适用于决策变量个数n 较小的情况，当n 较大时，由于n 个0、1的可能组合数为n2，故此时即便用计算机进行穷举来求最优解，也几乎是不可能的。

隐枚举法是增加了过滤条件的一类穷举法，该法虽能减少运算次数，但有的问题并不使用。

此时，就只能用穷举法了。

3. 应用实例例1 工程上马的决策问题1）问题的提出某部门三年内有四项工程可以考虑上马，每项工程的期望收益和年度费用（千元）如下表所示：假定每一项已选定的工程要在三年内完成，是确定应该上马哪些工程，方能使该部门可能的期望收益最大。

2）模型分析与变量的假设这是工程上马的决策问题，对任一给定的工程而言，它只有两种可能，要么上马，要么不上马，这两种情况分别对应二进制数中的1、0，大凡这样的实际背景所对应的工程问题，大都可考虑用0—1型整数规划模型建立其相应的模型。

运筹学整数规划模型

运筹学整数规划模型

5.某企业利用一种设备生产某种试件。

该设备可以在高，低两种不同的负荷下进行生产。

在高负荷下生产的试件产量是投入生产设备数量的10倍，设备年完好率为75%；低负荷下生产的试件产量是投入生产设备数量的8倍，设备年完好率为90%。

现在企业有完好的设备200台，试制定一个5年计划，确定每年投入投入高，低两种负荷下生产的设备数量，使5年内试件的总产量达到最大。

整数规划模型设第i 年投入高负荷下生产的完好的设备数量为i x ，生产的试件数量为10i x ；第i 年投入低负荷下生产的完好的设备数量为i y ，生产的试件数量为8i y 。

模型为：∑∑==+=5151810max i i i i y x z20011=+y x ⌊0.75i x ⌋+⌊0.9i y ⌋-1+i x -1+i y =0i x ,i y 0≥且为整数，（i=1,2,3,4,5）Lingo 程序为：max=10*(x1+x2+x3+x4+x5)+8*(y1+y2+y3+y4+y5);x1+y1=200;z1=@FLOOR( 0.75*x1);u1=@FLOOR(0.9* y1);z1+u1-x2-y2=0;z2=@FLOOR( 0.75*X2);u2=@FLOOR( 0.9*y2);z2+u2-x3-y3=0;z3=@FLOOR( 0.75*X3);u3=@FLOOR( 0.9*y3);z3+u3-x4-y4=0;z4=@FLOOR( 0.75*X4);u4=@FLOOR( 0.9*y4);z4+u4-x5-y5=0;@gin(x1);@gin(x2);@gin(x3);@gin(x4);@gin(x5);@gin(y1);@gin(y2);@gin(y3);@gin(y4);@gin(y5);Lingo 求解结果为：s.t.Objective value: 6362.000Variable ValueX1 200.0000X2 1.000000X3 0.000000X4 119.0000X5 89.00000Y1 0.000000Y2 149.0000Y3 134.0000Y4 1.000000Y5 0.000000由结果可以得知，第1年200台完好的生产设备全部在高负荷下生产；第2年1台完好的生产设备在高负荷下生产，149台完好的生产设备在低负荷下生产；第3年134台完好的生产设备全部在低负荷下生产；第4年119台完好的生产设备在高负荷下生产，1台完好的生产设备在低负荷下生产；第5年89台完好的生产设备全部在高负荷下生产。

3整数规划模型

2）模型建立。
决策变量：用表示按第种模式切割的原料钢管的根 数，显然它们应当是非负整数。
目标函数：以切割后剩余的总余料量最少为目标， 则由表3.1可得
z1=3x1+x2+3x3+3x4+x5+x6+3x7 以切割原料钢管的总根数最少为目标，则有
z2=x1+x2+x3+x4+x5+x6+x7
下面分别在这两种目标下求解。
用Lindo软件求解
例3.2 合理下料问题
某钢管零售商从钢管厂家进货，将钢管按照顾客的要求 切割后售出，从钢管厂进货时得到的原料钢管都是19m.
1）现有一客户需要50根4m、20根6m和15根8m的钢 管，应如何下料最节省？
1）问题的分析。
首先，应当确定哪些切割模式是可行的。所谓一个 切割模式，是指按照客户需要在原料上安排切割的一 种组合。例如：我们可以将19m的钢管切割成3根4m的 钢管，余料为7m；或者将19m的钢管切割成4m、6m 和8m的钢管各1根，余料为1m。显然，可行的切割模 式是很多的。
解 设购买远程、中程、短程客机的数量分别为x1、x2 和x3架，问题的数学模型为 max z 420x1 300x2 230x3, s.t. 6300x1 5000x2 3500x3 75000,
x1 x2 x3 30, 54 3 x1 3 x2 x3 40, x1, x2 , x3 0, x1, x2 , x3均为整数。
3 整数规划模型
在一个数学规划模型中，如果它的某些决策变量或 全部变量要求取整数时，就称这个数学规划模型为整 数规划模型。整数规划模型可分为整数线性规划模型 与整数非线性规划模型。整数规划又分为整数规划、 混合整数规划及0-1规划。

整数规划的数学模型


2018/8/4
求解练习题
L1 求解单纯形表 cj 2 5 4 0 0 CB XB x1 x2 x3 x4 x7 4 x3 1/2 0 1 1 -1/2 5 x2 1/2 1 0 0 1/2 0 x6 3/2 0 0 -5 5/2 0 x7 0 1 0 0 0 σ 基变量系数向量单位化 cj 2 5 4 0 0 CB XB x1 x2 x3 x4 x7 4 x3 1/2 0 1 1 -1/2 5 x2 1/2 1 0 0 1/2 0 x6 3/2 0 0 -5 5/2 0 x7 -1/2 0 0 0 -1/2 -5/2 0 0 -4 -1/2 σ
2018/8/4
用分枝定界法解例5-1
x2
5 4
9x1+7x2=56
3
2 1
7x1+20x2=70
1 2 3 4 5 6 7 8 9 10
0
x1
L0 : x* = (4.81, 1.82), Z* =356 2018/8/4
用分枝定界法解例5-1
2.将L0分解为L1和L2 L1 ：max z = 40x1 + 90x2 9x1 + 7x2 56 7x1 +20x2 70 x1 4 x1，x2 0
2018/8/4
0 x5 0 0 1 0 0 x5 0 0 1 0 0
0 x6 0 0 0 1 0 x6 0 0 0 1 0 b 9/2 15/2 7/2 -1/2 b 9/2 15/2 7/2 7

求解练习题
线性规划 L1 的最终单纯形表 cj 2 5 4 0 CB XB x1 4 x3 1 5 x2 0 0 x6 -1 0 x5 1 -2 σ L1 有整数最优解 0 0 0 b 5 7 1 1 x2 x3 x4 x5 x6 x7 0 1 1 0 0 -1 1 0 0 0 0 1 0 0 -5 0 1 5 0 0 0 1 0 -2 0 0 -4 0 0 -1 X* =（0，7，5） ，Z*=55

管理运筹学 第三章 整数线性规划


注意在分枝定界求解过程中，为了最优整数解，我们要不断 缩小其最优目标函数值上界与下界的距离，故通过分枝要使得其 上界越来越小，而其下界则越来越大。 在例题中，通过对上下界的修改，上下界距离有所缩小，但 并不相等，所以还要继续分枝。
(5)在线性规划2和线性规划3中选择一个上界最大的线性规划， 即 线 性 规 划 3 ， 进 行 分 枝 。 线 性 规 划 3 的 最 优 解 为 x1=3 ， x2=2.86，把x2分成x2≤2和x2 ≥3两种情况，这样线性规划3分 解为线性规划4和线性规划5，如下： 线性规划4： s.t. 线性规划5： s.t.
分枝定界法是先求解整数规划的线性规划问题。如果其最优 解不符合整数条件，则求出整数规划的上下界，用增加约束条件 的办法，把相应的线性规划的可行域分成子区域（称为分枝）， 再求解这些子区域上的线性规划问题，不断缩小整数规划的上下 界的距离，最后得整数规划的最优解。
“ 分枝”为整数规划最优解的出现创造了条件， 而“定界”则提高了搜索的效率。
(6)进一步修改整数规划最优目标函数值z*的上下界。 由于线性规划 1 分枝为线性规划 2 和线性规划 3 ，线性规 划3又分枝为线性规划4和5，也就是线性规划1分枝为线性规 划 2、 4、 5，故从线性规划 2， 4，5中进一步修改整数规划 最优目标函数值的上下界。 因为线性规划2的最优目标函数值为13.90，线性规划4 的最优目标函数值为 14，而线性规划 5无可行解，可得整数 规划最优目标函数值的上界可修改为14，即 z =14， 取线性 规划2，4，5中的整数可行解的目标函数值的最大值。 又因为在线性规划2中可知存在整数规划可行解x1=2， x2=3，其目标函数值为13，在线性规划4中可知存在整数规 划可行解 x1=4 ， x2=2 ，其目标函数值为 14 ，而线性规划 5 无可行解，可知整数规划最优目标函数值的下界可修改为 14， z=14，也取线性规划2，4，5中的整数可行解的目标函数值 的最大值。

整数规划模型

第三章 整数规划模型一． 提出问题：工厂选址某企业欲建工厂，可选厂址有A 1、A 2、A 3、A 4四处，每个地址至多可建一个工厂，在各地址建立工厂的生产能力、在各地址经营工厂单位时间的固定成本、产品运往各需求点的单位运费如下表：问应如何选择厂址和安排运输计划，才能得到经济上花费最少的方案 二． 分析问题 1． A 1、A 2、A 3、A 4各处都有可能建厂，用变量y[i]来表示是否建厂y[i]=⎩⎨⎧地址不建厂在地址建厂在i i 01i=1,2,3,4;2． 设从i 地址运到j 需求点的运输量可设为x[i][j]为整数 3．运到各点的量应不小于需求(x[1][j]+x[2][j]+x[3][j]+x[4][j]>=b[j])； 4．各厂的生产总量不超过生产能力（x[i][1]+x[i][2]+x[i][3]+x[i][4]<=d[i]*y[i] i=1,2,3,4）；5． 运到各需求点的量如何计算b1[j]=x[1][j]+x[2][j]+x[3][j]+x[4][j]j=1,2,3,4; 6． 各厂的生产总量a1[i]= x[i][1]+x[i][2]+x[i][3]+x[i][4]; 7． 目标函数：总费用z=建厂费用+ 运输费用8．运输费用=单位运输费用*运输量（从i 地址运到j 需求点单位运输费用c[i][j]已知，从i 地址运到j 需求点的运输量可设为x[i][j]） 三． 模型建立根据分析建立整数规划模型： 设1(1,2,,4)0i i y i ⎧==⎨⎩ 在处建厂否则，ij x i j 表示从点运到点的货物数量(i,j=1,2,,4)，建立如下整数规划模型：4441114141..(1,2,,4)(1,2,,4)0,0ii ijiji i j iji i j ijj i ij i m in z ay cx s t xd y i xb j x y =====⎧=+⎪⎪⎪≤=⎪⎨⎪⎪≥=⎪⎪≥=⎩∑∑∑∑∑ 或1其中(,1,2,,4)ijc i j i j = 表示从点到点的单位运费，i i a A 为点处建厂经营的单位固定成本(i=1,2,,4)， j b j 表示需求点B 处的需求量(j=1,2,,4)，(1,2,,4)i i d A i = 表示处的生产能力。

第七章整数规划模型


0
1
2
x1
最优解逐步暴露在可行解区域的顶点上。
割平面构造原理涉及到对偶单纯形法，在此不多 加介绍。割平面法有很重要的理论意义，但在实际计 算中没有分支定界效率高，且涉及到对分数的处理， 因此几乎没有给予割平面法的软件。
二、分支定界法
分支定界法的基本思想是根据某种规则将原整数 规划模型的可行域分解为越来越小的子区域，并检查 某各子区域内整数解的情况，直到找到最优的整数解 或证明整数解不存在。根据整数规划模型性质的不同， 存在许多的分支界定法以及分支界定的技巧，在此只 对分支界定的一般原理作一简单的介绍。 在介绍具体算法之前，以下几个重要的实事是容 易理解的：
得到整数规划模型的最优解呢？在上例中整数规划模 T x * ( 3 , 1 ) 型的最优解 ，线性松弛模型的最优解为 1 T 0 T x ( 3 , 2 ) x ( 2.5,2) ，四舍五入得 ， x1 不是不是可行解，自然也不是最优解；若将 x 0 取整得 x 2 ( 2,2 )T ，虽然是可行解，但它不是最优解。 由此可见，刚刚的设想是行不通的，事实上整数规划 模型的求解是难题，至今还没有有效的算法（即多项 式算法）。
用LINDO软件解的程序为：
答案为：最优决策变量 目标函 数最优值为22。 （跳跃式成本模型） 设两种产品A和B每公 斤价格为10元和7元，每公斤需要的加工工时 为6小时和4小时，成本和工时的关系如图7.1所 示，要求建立一整数规划模型，是利润最大。 解 设两种产品的产量分别为 公斤， 设工时在2000以内为第一范围，2000到3000小 时为第二范围，3000到5000小时为第三范围。 再设当工时在第j范围内时， （j=1，2， 3）。则模型为：
x2
3 2
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

问题的目标函
数为总利润求
nm
z
rij xij
i1 j1
的最大值．
nm
max z
rij xij ,
i1 j 1
n
xij X j ( j 1, 2,L
, m),
s.t.
i 1 m
ajX
j
M,
j 1
xij
0且为整数(i
1, 2,L
, n),
X j 0且为整数( j 1, 2,L , m).
x1, x2 0且x1, x2取整数13其lFra bibliotekngo语句如下：
MODEL: sets: row/1..2/:b; arrange/1..2/:c,x; link(row,arrange):a; endsets data: b=6,20;c=1,1;a=2,1,4,5; enddata [OBJ]max=@sum(arrange(j):c(j)*x(j)); @for(row(i):@sum(arrange(j):a(i,j)*x(j))<=b(i);); @for(arrange(j):x(j)>=0;); @for(arrange(j):@gin(x(j));); END
源的单位价格为 a j ( j 1, 2,L , m) ，该企业现有资金 M 元.
试问该企业应购买多少第 j 种资源(总量为 X j ），又 如何分配给所属的 n 个生产车间，使得总利润最大？
2
解 设决策变量为 xij (i 1, 2,L , n; j 1, 2,L , m) 表示分
配给第 i 个生产车间的第 j 种资源的资源量，均为非负整 数，第 j 种资源的需求总量 X j ( j 1, 2,L , m) 也都为整数．
@for(row(i):@sum(arrange(j):a(i,j)*x(j))>=b(i););
@for(arrange(j):x(j)>=0;);
@for(arrange(j):@GIN(x(j)););
END
12
例：一个简单的整数规划模型
max z x1 x2
2x1 x2 6 4x1 5x2 20
3
在这个问题中，所求解均是整数，初看起来， 似乎只要把已得到的带有分数或小数的解经过“ 舍入化整”就可以了，实际上这常常是不行的， 因为化整后不见得是可行解，或虽是可行解但不 一定是最优解。这种求最优整数解的问题就是整 数规划。
整数规划中如果所有的变量都限制为（非负） 整数，称为纯整数规划；如果仅一部分变量限制 为整数，称为混合整数规划；整数规划一种特殊 的情形是0-1规划，它的变量取值仅限于0和1。
解就是(A)的最优解，计算结束；
问题(B)有最优解 X * ，但不是(A)的可行解，转下一步。
8
2）将 X * 代入目标函数，其值记为 z ，并用观察
法找出（A）的一个可行解（整数解，不妨可取
x j 0( j 1,2, , n) ），求得目标函数值（下界 值），记为 z ，则（A）的最优值记为 z * ，即有 z z * z ，转下一步；
4
2. 整数规划模型的一般形式
n
max(min)z c j x j j 1
(A)
n
aij x j
(, )bi (i 1,2,, m)
j1
x
j
0,
x j为整数(
j
1,2,, n)
•问题是如何求解整数规划问题呢？ •能否设想先略去决策变量整数约束，即变为线性 规划问题求解，再对其最优解进行取整处理呢？ •实际上，可借鉴这种思想来解决整数规划问题．
整数规划方法
一.整数规划的一般模型 二.整数规划的求解方法 三.0-1整数规划 四.整数规划案例分析
1
一.整数规划的一般模型
1. 问题的提出：固定资源分配问题 设某企业有 n 个生产车间需要 m 种资源，对于第 i 个
生产车间分别利用第 j 种资源 xij 进行生产，单位资源可 以获得利润为 rij (i 1, 2,L , n; j 1, 2,L , m) ．若第 j 种资
5
二.整数规划的求解方法
1. 分枝定界法的基本思想（举例说明）
n
max(min)z c j x j j 1
(A)
n
aij x j (, )bi (i 1,2,, m)
j1
x
j
0, x j为整数(
j
1,2,, n)
n
max(min)z cj xj j 1
(B)
n
aij x j
j
1, 2,, n)
data:
b=b(1),b(2),…,b(m); c=c(1),c(2),…,c(n);
a=a(1,1),a(1,2),…,a(1,n),
... ... ... ...
a(m,1),a(m,2),…,a(m,n);
enddata
[OBJ] min=@sum(arrange(j):c(j)*x(j));
(, )bi (i 1, 2,, m)
j1
x
j
0(
j
1, 2,, n)
将原问题（Ａ）中整数约束去掉变为问题（Ｂ）, 求出（Ｂ）的最优解.
分枝定界法.ppt
6
如果不是原问题（Ａ）的可行解，则通过附加线性不 等式约束(整数)，将问题(B)分枝变为若干子问题
(Bi )(i 1,2, , I ) ，即对每一个非整变量附加两个互
11
3. 整数规划的lingo解法
MODEL: sets: row/1..m/:b; arrange/1..n/:c,x; link(row,arrange):a; endsets
n
min z c j x j j 1
n
aij x j bi (i 1, 2,, m)
j1
x
j
0,
x j为整数(
相排斥（不交叉）的整型约束，就得两个子问题. 继续求解定界，重复下去，直到得到最优解为 止.
7
2. 分枝定界法的一般步骤
1)将原整数规划问题（A）去掉所有的整数约束变为线 性规划问题（B），用线性规划的方法求解问题（B）:
• 问题(B)无可行解，则(A)也无可行解，停止；
问题(B)有最优解 X * ，并是(A)的可行解，则此
最小者为新的上界 z ，从所有符合整数约束条 件的分枝中找出目标函数值最大的为新下界 z
10
4）比较与剪枝：各分枝问题的最优值同 z 比较，如果其值 小于 z ，则这个分枝可以剪掉，以后不再考虑。
如果其值大于 z ，且又不是（A）的可行解，则继续分 枝 ， 返 回 （ 3 ）， 直 到 最 后 得 到 最 优 解 使 z* z ， 即 x*j ( j 1,2,,n) 为最优解。
9
3) 分枝：在问题(B)的最优解中任选一个不满足整
数约束的变量 x j b j ，附加两个整数不等式约束： x j [b j ] 和 x j [bj ] 1 到问题(B)中，构成两个新 的子问题 (B1 ) 和 (B2 ) ，求 (B1 ) 和 (B2 ) 的解。
定界：对每一子问题的求解结果，找出最优值