整数线性规划word版

二、分配问题与匈牙利法
2.3 匈牙利法的基本思想
如果效率矩阵的所有元素aij≥0, 而其中存在一组位于不 同行不同列的零元素，则只要令对应于这些零元素位 置的xij = 1，其余的xij= 0，则所得到的可行解就是问 题的最优解。
0 9 23 7
14 20 0 12
9 0 3 14
主要内容
一、整数规划的特点及作用 二、分配问题与匈牙利法 三、分枝定界法 四、割平面法 五、应用举例
一、整数规划的特点及作用
1.1 整数规划的概念
整数规划(Integer Programming) ：决策变 量要求取整数的线性规划。
如果所有的决策变量、技术系数和右端项都 是非负整数，就称为纯整数规划。 如果所有的决策变量都是非负整数，技术系 数和右端项为有理数，称为全整数规划。 如果仅一部分决策变量为整数，则称为混合 整数规划。 如果变量取值仅限于0或1，称为0-1整数规划。
二、分配问题与匈牙利法
2.3 匈牙利法
分配问题可以用单纯形法或运输表求解。 库恩(W.W.Kuhn)于1955年提出了指派问题的解 法，他引用了匈牙利数学家克尼格(D.Kö nig)一 个关于矩阵中零元素的定理：系数矩阵中独立0 元素的最多个数等于能覆盖所有0元素的最少直 线数。这个解法称为匈牙利法。
2 10 9 7 2 0 8 7 5 第一步：找出每 4 14 8 4 11 0 10 4 行的最小元素， 15 每行对应减去这 11 2 3 5 0 13 14 16 11 个元素。 4 15 13 9 4 0 11 9 5
二、分配问题与匈牙利法
二、分配问题与匈牙利法
2.2 分配问题实例(1)
例：有一份中文说明书，需要译成英、日、德、 俄四种文字。现有甲、乙、丙、丁四人，他们 将中文说明书译成不同语种的说明书所需时间 如下，问应指派何人去完成工作，使所需总时 间最少? 人员

4
i=3 78 67.8 84.6 59.4
5
i=4 70 74.2 69.6 57.2
i=5 67.4 71 83.8 62.4
若选择队员i参加泳姿j 的比赛，记xij=1, 否则记xij=0
目标 函数
约束 条件
Min Z cij xij
j 1 i 1
每人最多入选泳姿之一
每种泳姿有且只有1人
模型求解
整数规划(Integer Programming,简记IP)
IP可用LINDO直接求解
max 2x1+3x2+4x3 st 1.5x1+3x2+5x3<600 280x1+250x2+400x3<60000 end gin 3 “gin 3”表示“前3个变量为 整数”，等价于： gin x1 gin x2 gin x3
x2=0 或 80 x3=0 或 80
LINDO 中 对 01变量的限定： int y1 int y2 int y3
x1 My1 , x1 80y1 , y1 {0,1} M为大的正数， x2 My2 , x2 80y2 , y2 {0,1} 可取1000
x3 My3 , x3 80y3 , y3 {0,1}
例3 选课策略
课号
1 2 3 4 5 6 7 8 9
Байду номын сангаас
课名
微积分 线性代数 最优化方法 数据结构 应用统计 计算机模拟 计算机编程 预测理论 数学实验
学分
5 4 4 3 4 3 2 2 3
所属类别
数学 数学 数学；运筹学 数学；计算机 数学；运筹学 计算机；运筹学 计算机 运筹学 运筹学；计算机

解： 引入0-1变量xij ，
xij =1：第i人做第j项工作
xij =0：第i人不做第j项工作
• 一人只能完成一项任务
x11 x12 x13 x14 1 x21 x22 x23 x24 1 x31 x32 x33 x34 1 x41 x42 x43 x44 1
三、分支定界法
不考虑整数限制先求出相应松弛问题的最优解， 若松弛问题无可行解，则ILP无可行解； 若求得的松弛问题最优解符合整数要求，则是 ILP的最优解； 若不满足整数条件，则任选一个不满足整数条件 的变量 xi0 来构造新的约束添加到松弛问题中形 成两个子问题

0 0 xi xi ; xi xi 1
1 xj 0
选中第j个项目投资 不 选中第j个项目投资
max Z 160x1 210x2 60x3 80x4 180x5 210x1 300x2 150x3 130x4 260x5 600 x1 x2 x3 1 x3 x 4 1 x x 1 5 x1 , x2 , x3 , x4 , x5 0或1
x1 ≤ 1
LP1 ： 7 10 x1 1, x2 , Z 3 3
41 10 9 3
x2 ≥3
x2≤2
LP3 ： x1 33 61 , x2 2, Z 14 14
LP4：无解，查清
x1 ≥3
LP6：
61 10 14 3
x1≤2
LP5：
10 4, 3 x1 3, x2 1, Z 4，查清 x1 2, x2 2, Z 4，查清 LP1被剪枝
假设：yj=1，要租用生产线j yj=0，不租用生产线j

1.整数规划（ interger programming,简称IP） 要求部分或全部决策变量取整数值的规划问题称为整数规划。 变量限制为整数的线性规划则称为整数线性规划（interger linear programming，简称ILP）。 2.整数线性规划问题的种类： （1）纯整数线性规划（pure interger linear programming）：
（3.1.1 ）

整数规划与线性规划在形式上相差不多 , 但是由于整
数规划的解是离散的正整数 ,实质上它属于非线性规划 .若
去掉整数规划的整数约束 ——— x j 为整数 ,则该规划就变
成了一个线性规划 ,一般称这个线性规划为该整数规划的 松弛问题 .
§6.1 整数线性规划问题的提出 Page 6
一些原则
Page 22
序号 分支问题1
1 无可行解
2 无可行解 3 无可行解
4
整数解
5
整数解，优 于问题2
6
整数解
7 非整数解
分支问题2 无可行解
整数解 非整数解
整数解
非整数解 非整数解， 优于问题1
非整数解
说明 原问题无可行解 此整数解为最优解 对问题2继续分支 较优的为最优解
问题1为最优解 问题1停止分支，继续 对问题2分支 继续分支,较优的先分
解： x1——甲货物的托运箱数； x2——乙货物的托运箱数；
这就是一个(纯)整数线性规划问题，数学模型为：
max2 24
(2)

2
x1

5 x2

13
(3)

x1
,
x2

0
(4)
x1 , x2为整数.

0
b
j 1
j
xj B
• 目标—总收益最大
max
c
j1
n
j
x
j
max
c
j1
n
j
x
j
n b j x j B s .t . j 1 x 1 , 0 ; j 1 , 2 ..., n j
旅游售货员问题
• 背景
• 案例 • 模型
背 景
• 旅游线路安排 预定景点走且只走一次 路上时间最短 • 配送线路—货郎担问题 送货地到达一次 总路程最短

混合整数规划模型
min c x Ax b s .t . x 0 x i 为整数 , i 1, 2 ,..., p

§2.2 整数线性规划算法
• 与线性规划的关系
• 分支定界算法
• 割平面算法 • 近似算法
与线性规划的关系
放松的线性规划 整数规划
min c

min c
x ij 1, 0 ; i 1, 2 ..., 17 , j 1, 2 , 3
• 约束
包裹容量限制
c
i 1
3
17
i
x ij r j ; j 1, 2 , 3
必带物品限制

3
x ij 1; i 1, 2 ..., 7
j 1
选带物品限制
x ij 1; i 8 , 2 ..., 17
3. 对于问题B，任选一个不符合整数条件的变量 xj=bj，对问题B进行分支，增加两个约束条件： xj[bj] 和 xj[bj] +1，形成两个后继问题B1 和 B2 ,求它们的松弛问题，得到目标函数值的上 界。转步骤4 。 4. 考察所有后继问题， (a)如果它的目标函数值的上界不如zb，舍去该支， 转步骤4 。 (b)如果没有后继问题, 则当前最优解就是原问题 的最优解，stop。 (c)寻找目标函数值的界最好的后继问题,转步骤5。

X3 24 5 4 1
0
X4 13 2 5
0
1
-z -96 0 -6 -4 0
X1 24/5 1 4/5 1/5 0 X4 17/5 0 17/5 -2/5 1
X* =
4.8 0
,Z* =96为上界,下界0
选X1分枝 问题(2)
(1) X1 4
问题(3)
(1) X1 5
解(2)的松弛问题
X1 X2 X3 X4 X5 -z -96 0 -6 -4 0 0
问题(3)无可行解.
(2)
S0 =0
4
1
90
X1 4
(1)
S0 =0
4.8
0
960
X1 5
(3)
S0 =90
无可行解
分枝定界法一般步骤:(min)
(1)、(A), 先解(A)的松弛问题(B)
(2)、① (B)无可行解→(A)无可行解。 ② (B)最优解符合(A)要求，停。 ③ (B)最优解不符合(A)要求，转(3)。
(LP)
条件--保留整数解删除最优解
割平面生成方法
xB
B 0 I
xN
N cB B1b
B1N B1b0
xr arj x j br jN
对应的单纯形表
cB B1b
b1
b
2
b
r
bm
x1 x 2 x r x m x m 1 x n
0 0 0 0 m1 0 n 0
1
1
1
1
a1m 1 a 1n
。
第章 整数线性规划
整数线性规划的标准形式：
n
min Z C i X i i1
n i1

(P)
(8.8)
可先求其对应的线性规划问题
max z max CX
( P0 )
AX b st. X 0
(8.9)
8.4 整数线性规划问题的求解—分枝定界法
Step1 求解相应的线性规划问题 ( P0 ) ，并确定初始上、下界
求解相应的线性规划问题 ( P0 ) ，若 ( P0 ) 无解，则 (P) 无解，停止计算； 若 ( P0 ) 的最优解满足整数要求，就得到 (P) 的最优解，计算完毕；若 ( P0 ) 的 最优解中有非整数分量，其最优目标函数值是 (P) 的初始上界，记为 z ，任意 选的一个整数可行解（一般可取 x j 0, j 1,2, n ） ，求得其目标函数值作 为初始下界，并记为 z ，以 z * 表示问题 (P) 的最优目标函数值；这时有
8.3 整数线性规划问题的求解——割平面法
1． 基本思想 给出整数规划
min z min CX
(P)
AX b st. X0 x 整数（ j 1,2, ,n) j
(8.5)
可先求其相应的线性规划问题
min z min CX
( P0 )
AX b st. X 0
这三个不等式相加，不论 u 3 ,u 4 ,u 5 取任何实数值均导致 5 4 的矛盾，第 三组约束所起的这个作用是可以严格证明。根据定义，旅行售货员问题是一个 混合整数线性规划问题。有许多实际应用问题的数学模型都是（8.3）的形式， 如生产顺序表问题、集成电路的布线问题等。
8.2 整数规划的图解法
8.1 整数线性规划问题的提出
在前面讨论的线性规划问题中，最优解可能是分数或小数，但对于某些 具体问题常要求最优解是整数。我们称这样的线性规划问题为整数线性规划 问题（Integer Linear Programming 简记为 ILP） 。 在整数规划中如果所有的变量都限制为整数，就称为纯整数规划（Pure ILP）,如果仅一部分变量限制为整数，就称为混合整数规划（Mixed ILP）, 整数规划的一个特例就是 0—1 规划，它的变量仅取 0 或 1。 例 8-1 投资决策问题 某部门在今后五年中可用于投资的资金总额为 B 万元，有 n ( n 2)个可 以投资的项目，假定每个项目最多投资一次，第 j （ j n ）个项目所需投资 资金为 b j 万元，获得的利润为 c j 万元，问如何选择投资项目，才能使获得的 总利润最大。

min c x
Ax b s.t.x 0,i 1,2,...,n
xi为整数,i 1,2,...,p
1 整数线性规划问题举例
•例311 某财团有 B 万元的资金，有 n(n 2) 个可以考
虑的投资项目，假定每个项目最多投资一次。其中
第 j 个项目需投资金额为 b j 万元，将会获得的利润
为 c j 万元，问应如何选择项目才能使得获得的总 利润最大？
2 解整数线性规划问题的困难性
LP的可行集合
费用下降方向 LP问题的最优解
ILP问题的最优解
2 解整数线性规划问题的困难性续
• 最优解不一定在顶点上达到 • 最优解不一定是松弛问题最优解的邻近整数解 • 整数可行解远多于松弛问题的顶点;枚举法不可
取 • 解ILP问题要远难于解松弛的LP问题 • 如果松弛的LP问题无解;显然原ILP问题无解 反
bjxj B
j1
x
j
0或 1;
j
1, 2..., n
旅行售货员问题
• 此外;运筹学还有一个著名的问题：
旅行售货员问题TSP
显示问题
2 解整数线性规划问题的困难性
整数规划
min z c x Ax b
s.t.x 0, x为整数
松弛的线性规划问题
min z c x
s.t. xAห้องสมุดไป่ตู้x
0
b
可行解是松弛问题的可行解 最优值大于等于松弛问题的最优值
第一节 整数线性规划问题
• 整数线性规划问题举例 • 解整数线性规划问题的困难性
整数线性规划问题
• 整数线性规划ILP具有下述形式
min c x
Ax b
s .t .
x

割平面法
IP LP xl*
Yes xI* = xl*
判别是否整数解
No 加入割平面条件 用对偶单纯型方法继续求解
§3.3 分枝定界方法
分枝定界方法的基本思想 分枝定界方法的实现——例题
1 分枝定界方法的基本思想
如果松弛问题(P0)无解，则(P)无解；
如果(P0)的解为整数向量，则也是(P)的解；
min -(x1 x2 ) s.t.-4x1 2 x2 1 (P1 ) 4x1 2 x2 11 x1 1 x1 , x2 0, Integer
P2
约束 x1 1, x1 2 (它们将x1=3/2排除在外)，得到两个子问题：
min -(x1 x2 ) s.t.-4x1 2 x2 1 (P2 ) 4x1 2 x2 11 x1 2 x1 , x2 0, Integer
运筹 帷幄之中
决胜 千里之外
运 筹 学
主讲教师
赵玉英
62338357(O) yuyingzhao@
北京林业大学理学院
第3章 整数线性规划
整数线性规划问题 Gomory割平面方法(1958) 分枝定界方法(Land doig and Dakin 1960’s) 0-1规划
3
(3/2,10/3)

3
x1
3 整数线性规划问题的求解
思路2：由于纯整数线性规划的可行集合就是一些离散 的格点，可否用穷举的方法寻找最优解？ 当格点个数较少时，这种方法可以； 对一般的ILP问题，穷举方法无能为力。

3 整数线性规划问题的求解
目前，常用的求解整数规划的方法有： 割平面法和分枝定界法； 对于特别的0－1规划问题采用隐枚举法和匈牙利法。

第三章 整数线性规划本章, 我们介绍三种解决整数线性规划问题的软件:第一种: MATLAB 中的optimization toolbox 中的若干程序;第二种: LINDO 软件;第二种: LINGO 软件.1. MATLAB 程序说明程序名: intprogram, L01p_e, L01p_ie, transdetobi, biprogramintprogram 是利用分支定界法解决整数规划问题, 是全部的整数规划问题;L01p_e 是利用枚举法解决0-1规划问题, 变量要求全部为0或者1;L01p_ie 是利用隐枚举法解决0-1规划问题, 变量要求全部为0或者1;Transdetobi 是枚举法和隐枚举法中利用到的将十进制数转化为二进制数的函数; Biprogram 是MATLAB6.5以上版本中有的求解0-1规划的函数的程序.intprogram 执行实例1：12121212max 2010s.t.54242513,0, f x x x x x x x x =++≤+≤≥ 且为整数在命令窗口的程序执行过程和结果如下:>> c=[-20,-10]; %将最大转化为最小;>> a=[5,4;2,5];>> b=[24;13];>> [x,f]=intprogram(c,a,b,[0;0],[inf;inf],[],0,0.0001) % c,a,b 之后[0;0] is the value of low bound;[inf;inf] is the value of up bound;[] is the initialization;0 is the number of the equation constraints; 0.0001 is the concise rate. x =4.00001.0000f =-90intprogram 执行实例2: 书中例题3.3.1在命令窗口的程序执行过程和结果如下:>> c=[-1,-1];>> a=[-4,2;4,2;0,-2]; >> b=[-1;11;-1];>> [x,f]=intprogram(c,a,b,[0;0],[inf;inf],[],0,0.0001)x =2 21 1f =-3L01p_e 和L01p_ie 执行实例:1231231231223123max 325s.t.2244346,,01f x x x x x x x x x x x x x x x x =-++-≤++≤+≤+≤=　－ 或在命令窗口的程序执行过程和结果如下:>> c=[3,-2,5]; %将最大转化为最小;>> a=[1,2,-1;1,4,1;1,1,0;0,4,1];>> b=[2;4;3;6];>> x1=L01p_e(c,a,b);x2=L01p_ie(c,a,b); %x1表示利用枚举法解决0-1规划问题，x2表示用隐% 枚举法解决问题, 结果是一样的>> x1x1 =1>> x2x2 =1biprogram 执行实例: 12341234341324min ()9564s.t.6352910f x x x x x x x x x x x x x x x =---+++≤+≤+≤-+≤　－ -在命令窗口的程序执行过程和结果如下：the program is with the binary linear programmingPlease input the constraints number of the programming m=4m =4Please input the variant number of the programming n=4n =4Please input cost array of the objective function c(n)_T=[-9,-5,-6,-4]'c =-9-5-6-4Please input the coefficient matrix of the constraints A(m,n)=[6,3,5,2;0,0,1,1; -1,0,1,0;0,-1,0,1]A =6 3 5 20 0 1 1-1 0 1 00 -1 0 1Please input the resource array of the program b(m)_T=[9,1,0,0]'b =91Optimization terminated successfully.x =11程序的相关知识:Solve binary integer programming problems of the formwhere f, b, and beq are vectors, A and Aeq are matrices, and the solution x is required to be a binary integer vector -- that is, its entries can only take on the values 0 or 1.语法如下:x = bintprog(f)x = bintprog(f, A, b)x = bintprog(f, A, b, Aeq, beq)x = bintprog(f, A, b, Aeq, beq, x0)x = bintprog(f, A, b, Aeq, beq, x0, options)[x, fval] = bintprog(...)[x,fval, exitflag] = bintprog(...)[x, fval, exitflag, output] = bintprog(...)解释:x = bintprog(f) solves the binary integer programming problemx = bintprog(f, A, b) solves the binary integer programming problemx = bintprog(f, A, b, Aeq, beq) solves the preceding problem with the additional equality constraint.x = bintprog(f, A, b, Aeq, beq, x0) sets the starting point for the algorithm to x0. If x0 is not in the feasible region, bintprog uses the default initial point.x = bintprog(f, A, b, Aeq, Beq, x0, options) minimizes with the default optimization options replaced by values in the structure options, which you can create using the function optimset.[x, fval] = bintprog(...) returns fval, the value of the objective function at x.[x,fval, exitflag] = bintprog(...) returns exitflag that describes the exit condition of bintprog. See Output Arguments.[x, fval, exitflag, output] = bintprog(...) returns a structure output that contains information about the optimization. See Output Arguments.2．LINDO 程序说明LINDO 也提供了解决全整数规划、混合整数规划以及0-1规划的方法.2.1 解决全整数规划问题程序名: intlpallintlpall 执行实例:min 1110s.t.21231 ,0, x yx y x y x y ++<->> 且为整数在命令窗口键入以下内容:max 11x+10yst2x+y<12x-3y>1endgin x ! the general integer statement – GIN 将变量约束为整数gin y ! the general integer statement – GIN 将变量约束为整数按solve 键在reports window 出现:LP OPTIMUM FOUND AT STEP 7OBJECTIVE VALUE = 72.4285736NEW INTEGER SOLUTION OF 66.0000000 AT BRANCH 0 PIVOT 12BOUND ON OPTIMUM: 66.00000ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 12LAST INTEGER SOLUTION IS THE BEST FOUNDRE-INSTALLING BEST SOLUTION...OBJECTIVE FUNCTION VALUE1) 66.00000VARIABLE VALUE REDUCED COSTX 6.000000 -11.000000Y 0.000000 -10.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 0.0000003) 5.000000 0.000000NO. ITERATIONS= 12BRANCHES= 0 DETERM.= 1.000E 0]2.2 解决混合整数规划问题：程序名：intlpsecintlpsec 执行实例：min 1110s.t.21231,0, x yx y x y x y x ++<->> 且为整数在命令窗口键入以下内容:max 11x+10yst2x+y<12x-3y>1endgin x ！only the general integer statement – GIN 只将变量x 约束为整数按solve 键在reports windows 中出现以下内容:LP OPTIMUM FOUND AT STEP 2OBJECTIVE VALUE = 72.4285736SET X TO >= 6 AT 1, BND= 66.00 TWIN= 68.33 16NEW INTEGER SOLUTION OF 66.0000000 AT BRANCH 1 PIVOT 16 BOUND ON OPTIMUM: 68.33334FLIP X TO <= 5 AT 1 WITH BND= 68.333336NEW INTEGER SOLUTION OF 68.3333359 AT BRANCH 1 PIVOT 16 BOUND ON OPTIMUM: 68.33334DELETE X AT LEVEL 1ENUMERATION COMPLETE. BRANCHES= 1 PIVOTS= 16LAST INTEGER SOLUTION IS THE BEST FOUNDRE-INSTALLING BEST SOLUTION...OBJECTIVE FUNCTION VALUE1) 68.33334VARIABLE VALUE REDUCED COSTX 5.000000 -14.333333Y 1.333333 0.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.666667 0.0000003) 0.000000 -3.333333NO. ITERATIONS= 17BRANCHES= 1 DETERM.= 1.000E 02.3 解决0-1整数规划问题：程序名：intlp01intlp01执行实例：max 1002012s.t.100117 ,001x y zy x y z z y z x -++-<+<<>= 或在命令窗口键入以下内容:max -100x+20y+12zsty-10x<0y+z<11z<7endint x ！约束x 为0-1变量按solve 键在reports windows 中出现以下内容:LP OPTIMUM FOUND AT STEP 3OBJECTIVE VALUE = 124.000000SET X TO >= 1 AT 1, BND= 112.0 TWIN= 84.00 9NEW INTEGER SOLUTION OF 112.000000 AT BRANCH 1 PIVOT 9BOUND ON OPTIMUM: 112.0000DELETE X AT LEVEL 1ENUMERATION COMPLETE. BRANCHES= 1 PIVOTS= 9LAST INTEGER SOLUTION IS THE BEST FOUNDRE-INSTALLING BEST SOLUTION...OBJECTIVE FUNCTION VALUE1) 112.0000VARIABLE VALUE REDUCED COSTX 1.000000 20.000000Y 10.000000 0.000000Z 1.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 8.0000003) 0.000000 12.0000004) 6.000000 0.000000NO. ITERATIONS= 10BRANCHES= 1 DETERM.= 1.000E 03. LINGO 程序说明除了特别说明, LINGO 默认变量是非负的以及连续的, 但是可用以下命令使得变量满足要求:@GIN restricts a variable to being an integer value,@BIN makes a variable binary (i.e., 0 or 1),@FREE allows a variable to assume any real value, positive or negative @BND limits a variable to fall within a finite range 等.程序名: intlp (该程序主要是解决整数线性规划问题的, 用上述命令赋予变量属性.) intlp 执行实例:max 100150s.t.2160100120,0, x yx y x y x y ++<≤≤> 且为整数在模型命令窗口键入以下内容:max =100*x+150*y;x<=100;y<=120;x+2*y<=160;@gin (x);@gin (y);！若要只限制x,只要限制x 即可.按运行按钮在solution report 窗口得到以下结果:Global optimal solution found at iteration: 2 Objective value: 14500.00Variable Value Reduced Cost X 100.0000 -100.0000 Y 30.00000 -150.0000Row Slack or Surplus Dual Price 1 14500.00 1.000000 2 0.000000 0.000000 3 90.00000 0.000000 4 0.000000 0.000000程序名: bilpbilp 的执行实例:1231231231223123max 325..2244346,,01f x x x s t x x x x x x x x x x x x x or =-+-+-≤++≤+≤+≤= 在模型命令窗口键入以下内容:max =-3*x1+2*x2+5*x3;x1+2*x2-x3<=2;x1+4*x2+x3<=4;x1+x2<=3;4*x2+x3<=6;@bin (x1);@bin (x2);@bin (x3);按运行按钮在solution report 窗口得到以下结果:Global optimal solution found at iteration: 0Objective value: 5.000000Variable Value Reduced Cost X1 0.000000 3.000000 X2 0.000000 -2.000000 X3 1.000000 -5.000000Row Slack or Surplus Dual Price 1 5.000000 1.000000 2 3.000000 0.000000 3 3.000000 0.000000 4 3.000000 0.0000005 5.000000 0.000000注：范本无法思考和涵盖全面，最好仔细浏览后下载使用，感谢您的关注！。

B1
A1 A2 A3 A4 年需求 量 2 8 7 4 350
B2
9 3 6 5 400
B3
3 5 1 2 300
B4
4 7 2 5 150
年生产能力
400 600 200 200
工厂A3或A4开工后，每年的生产费用估计分别为 1200万或1500万元。 现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少。
首先不考虑整数约束，得到线性规划问题（一般称 为松弛问题）。
max Z x1 x 2 14 x1 9 x 2 51 6 x1 3 x 2 1 x , x 0 1 2
用图解法求出最优解为：x1＝3/2, x2 = 10/3，且有Z = 29/6
现求整数解（最优解）：如用 x2 “舍入取整法”可得到4个点即(1， 3) (2，3)(1，4)(2，4)。显然，它 们都不是整数规划的可行解,因而不 3 是最优解。
5
4 24
2
5 13
20
10
解：设X1 , X2 为甲、乙两货物各托运箱数
maxZ = 20 X1 + 10 X2 5X1+4X2 24 2X1+5X2 13 X1 , X2 0
X1 , X2为整数
例4.2 背包问题
背包可装入8单位重量，10单位体积物品 物品 1 2 名称 书 摄像机 重量 5 3 体积 2 1 价值 20 30
变量约束：
x12 x 22 x 32 x 42 1 x13 x 23 x 33 x 43 1 x14 x 24 x 34 x 44 1
xij 0或，、 1 i j 1, 2,3, 4
整数线性规划问题数学模型的一般形式：

§3.1 整数线性规划整数线性规划( Integer Linear Programming ，简记为 ILP )⎪⎪⎩⎪⎪⎨⎧⊂∈∈≥=},,2,1{,0..min n J i I x x b Ax t s x c i T Λ （3.1.1）其中，},2,1,0{Λ=I<1>若 },,2,1{},1,0{n J I Λ==，则称（3.1.1）为0-1规划问题；<2>若 J 是 },,2,1{n Λ的非空真子集，则称（3.1.1）是混合整数线性规划问题；<3>若 },,2,1{n J Λ=，则称（3.1.1）是纯整数线性规划问题。

1、整数线性规划问题举例例 3.1.1 某部门在今后五年中有 B 万元的资金可以用于投资，有 )2(≥n n 个可以考虑的投资项目。

假定每个项目最多投资一次，其中第 j 个项目需投资金额为 j b 万元，将会获得的利润为 j c 万元，问应如何选择项目，才能使获得的总利润最大？解：设投资决策变量为n j j j x j ,,1,0,1Λ=⎩⎨⎧=个项目，决定不投资第个项目，决定投资第，设获得的总利润为 z ，则⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≤<=∑∑==n j x Bx b t s x c z j n j j j n j jj ...,2,1;010..max 11或 （3.1.2） 问题（3.1.2）是一个0-1规划。

01或=j x 这个约束可以用一个等价非线性约束0)1(=-j j x x来代替它。

因而变量限制为整数本质上是一个非线性约束。

例 3.1.2 某建筑公司承包两种类型宿舍。

甲种宿舍每幢占地面积为 31025.0⨯平方米；乙种宿舍每幢占地面积为 3104.0⨯平方米。

该公司已购进 3103⨯平方米的建筑用地。

计划要求建甲种宿舍不超过8幢，乙种宿舍不超过4幢。

建甲种宿舍每幢可获利10万元，建乙种宿舍每幢可获利20万元。

第八章整數線性規劃本章內容：8.1 各類型的整數線性規劃模式8.2 全整數規劃問題的圖解法及電腦解8.3 包含0-1變數應用8.4 0-1變數賦予的建模彈性1⏹8.1 各類型的整數線性規劃模式●一線性規劃中，所有變數都限定為整數，稱為“全整數線性規劃（all integer linear program）”。

下列為一全整數線規劃摸式：Max 2X1＋3X2s.t. 3X1＋3X2≦121X2＋1X2≦41X1＋2X2≦6X1，X2≧0且為整數2●刪除整數線性規劃決策變數的「整數」限定後線性規劃問題，稱為“整數線性規劃的LP寬鬆式（LP Relaxation）”。

●一線性規劃中，僅有部份變數被限定為整數稱為混合整數線性規劃（mixed integer linear programming MILP）下列為一混合整數線性規劃模式：Max 3X1＋4X2s.t. －1X1＋2X2≦81X2＋2X2≦122X1＋1X2≦16X1，X2≧0且X2為整數3此例中將“X2為整數”的要求刪去後之線性規劃稱為“混合整數線性規劃的LP寬鬆式”。

●在全整數或混合整數線性規劃中，整數值的變數為離散變數（discrete variable），其他變數稱為連續變數（continuous variable）。

●一整數規劃中，整數變數只允許0或1稱為0－1或二元（binary）整數規劃。

48.2 全整數規劃問題的圖解法及電腦解例：東生不動產公司目前有2,000,000元可用來投資出租房屋計劃。

公司將投資方案限於在住宅區的別墅及公寓，別墅每棟282,000元，而目前只有五戶別墅可買得到，每棟公寓售價400,000元，公寓的數量則很多。

公司管理人員每月有140小時間來管理這些投資的不動產。

每棟別墅需4小時管理，每棟公寓需40小時。

每月利潤，別墅每棟為10,000元，公寓每棟為15,000元，公司要如何分配資金投資到別墅及公寓，以使總利潤最高。

整数线性规划问题的最优解
A
第1节 整数线性规划的数学模型及解的特点
例2：某宝石加工厂最近新到6粒大小、质量等级 相似的钻石毛料，管理层有两种选择，一是切 磨成一般的皇冠形，每粒可获利2.5千元；一 是切磨成虽然较难切磨但当前市场较流行的心 形，每粒可获利4千元。若切磨成皇冠形则每 粒需要5个工作日，若切磨成心形则每粒需要9 个工作日，由于工厂切工师傅较忙，最多只有 45个工作日来做这批工作。另外，由于毛料自 身形状的关系，其中只有4粒毛料可以切磨成 皇冠形，而6粒毛料中任何一粒都可以切磨成 心形。那么，管理层应如何决策才能使这批钻 石获利最大？
例5：某服务部门各时段（每2h为一时 段）需要的服务员人数见下表。按规 定，服务员连续工作8h（即四个时段 ）为一班。现要求安排服务员的工作 时间，使服务部门服务员总数最少。
时段 1 2 3 4 5 6 7 8
服务员最少数目
10
8
9
11 13
8
5
3
第3节 0-1型整数线性规划
例5： 解：设在第j时段开始时上班的服务员人数为xj。
min z cij xij 1200 y 1500 1 y
i 1 j 1 4 4
x11 x21 x31 x41 350 x x x x 400 12 22 32 42 x13 x23 x33 x43 300 x14 x24 x34 x44 150 x x x x 400 11 12 13 14 x x x x 600 21 22 23 24 x31 x32 x33 x34 200 y x41 x42 x43 x44 200 1 y x 0，， (i j =1， 2， 3， 4) ij y 0或1

x1(x1 80) 0 x2 (x2 80) 0
x1, x2 , x3为非负整数
IP 结果输出
280x1+250x2+400x3< 60000 end
OBJECTIVE FUNCTION VALUE
1)
632.0000
VARIABLE VALUE REDUCED COST
X1
64.000000
-
2.000000
X2
168.000000
-
“gignin3 3”表示“前3个变 量为整数”，等价于： gin x1 gin x2 gin x3
模型求解 整数规划(Integer Programming,简记
Max z 2x1 3x2 4x3
IPIP可) 用LINDO直接求解
s. t. 1.5x1 3x2 5x3 600 280 x1 250 x2 400 x3 60000
max 2x1+3x2+4x3 st 1.5x1+3x2+5x3<600
模型建立
令xj表示对第j个发展项目的投资数量
n
Max z cj x j j 1 n
s. t. a j xj b j 1
xj 0或1(j=1,2, ,n)
整数 线性 规划 0－ 1模 型 (IP)
整数线性规划及0－1规划
例1 汽车厂生产计划
汽车厂生产三种类型的汽车，已知各类型每辆车对钢 材、劳动时间的需求，利润及工厂每月的现有量。
x1,x2,, x3=0 或 80 方法1：分解为8个LP子模型
其中3个子模型应去掉，然后 逐一求解，比较目标函数值， 再加上整数约束，得最优解：