2 1
(4,1) 2x1+3x2=14
x1+x2=5
0
x1
1 2 34 5 6 7 8 9
确定割平面方程的练习:
x 2 （ 03 4 ） x 3 （ 01 4 ） x 4 1 3 4
x141x341x4
3 4
x234x341x474
x 1 （ 1 3 4 ） x 3 （ 0 1 4 ） x 4 0 3 4
即：
1 21 2x31 2x4 0
加上松弛变量之后得到
1 21 2x31 2x4x5 0
根据右端为整数且变量非负的要求，得到：
1 21 2x31 2x4
11 2
第3步.在最优单纯形表中求解增加约束条件后的LP问题的最优解；
cj CB 基 b
2
x2
21 2
3
x1
31 4
0c
第四章 整数规划与分配问题
Integer Programming,简称IP
• 整数规划的特点及作用 • 分枝定界法 • 割平面法 • 分配问题与匈牙利法 • 应用举例
整数规划的特点
整数规划是研究决策变量只能取正整数的一类规划问题。 有纯整数规划、混合整数规划与0-1整数规划等类型。我 们只研究线性整数规划。
21 2
x1
31 4
cj zj
将上式所有常数分写成整数与正分数之和：
23 00
x1 x2 x3 x4
0 1 1 1
22
1
0
1 4
3 4
0 0 15
44
x 2 （ 0 1 2 ） x 3 （ 1 1 2 ） x 4 2 1 2
分数移项到右端，整数项到左端：
x2x421 21 2x31 2x4
割平面法的基础仍然是用解线性规划的方法去解整数规 划问题：首先不考虑变量为整数这一条件，但增加线性约束 条件（Gomory约束，称为割平面），使得原可行解域中切掉 一部分，这部分只包含非整数解，但没切割掉任何整数可行 解，切除的结果使整数解可能成为顶点。
割平面法的步骤
求松弛问题的 最优基可行解
判断是否 为整数解
31 4
0c
j x5
z

j
1 2
cj zj
2 x2 2
3
x1
31 2
0 x3 1
cj zj
23 00 0
x 1 x 2 x 3 x 4 x5
0
1
1 1 22
0
1
0
1 4
3 4
0
0 0 0
00 0
11 142

15 524
1 0
44
0 1 0 1 1
2
1 0 0 1 1
束
分别用图解法求得最优解
6
5
X(1)=(3,2.67)T, Z(1)=14.33
4
X(2)=(4,1)T,
Z(2)=14
3
Z(1) ＞ Z(2) =14
2
(4,1) (1)
1
子问题2停止分枝，其整数解作为界；
0 1 2 3 4 5 6 7 8 9 x子1 问题1对x2=2.67进行分枝
子问题1
子问题2
分配问题的提出【指派问题】
若干项工作或任务需要若干个人去完成。由于 每人的知识、能力、经验的不同，故各人完成不同 任务所需要的时间不同（或其他资源）。
3
x1
31 4
cj zj
23 00
x1 x2 x3 x4
0
1
1 1 22
1
0
1 4
3 4
0 0 15
44
第2步.寻找割平面方程；
cj
Gomory 约束
C一个基变 2
量，并写出该行在最终表中的约束方程
3
x21 2x31 2x4
21 2
x2
2 x1 3x2 14
4xx1 1
x2
2 x2 2
18 3 分枝
约
束
x1 , x2 0
max Z 3x1 2 x2
2 x1 3 x2 14
4xx1 1


2x2 18 3
x2 3 分枝约束
x1 , x2 0
添加x2≤2
问题(3) x1=3,x2=2
Z(3)=13
问题(1) x1=3,x2=8/3 Z(1)=14.33
添加x2≥3
问题(4) x1=2.5,x2=3
Z(4)=13.5
问题(2)
√ x1=4,x2=1 Z(2)=14
分枝问题解可能出现的情况表
序号
问题 1
问题 2
说明
1
无可行解
无可行解
整数规划无可行解
将系数和常数项都分解为整数和正分数之和并移项得：
x1

x3

3 4

3 4
x3

1 4
x4

0
x2
1

3 4

3 4
x3

1 4
x4
0
第四章 整数规划与分配问题
Integer Programming,简称IP
• 整数规划的特点及作用 • 分枝定界法 • 割平面法 • 分配问题与匈牙利法 • 应用举例
子问题46
5 4
max Z 3x1 2 x2
2 x1 3x2 14
4xx1 1
x2
2 x2 2
18 3 分枝
约
束
x1 , x2 0
max Z 3x1 2 x2
2 x1 3 x2 14
4xx1 1


2x2 18 3
分枝定界法
实质：在保留原问题全部整数可行解的前提下，将原 问题分枝为若干容易求解的子问题，并利用子问题的 整数解的目标值来判定分枝的界限<定界>。 分 枝
边界
【例】某厂拟购进甲、乙两类机床生产新产品。已知两类机床进价
分别为2万元和3万元，安装占地面积分别为4m2和2m2，投产后的收 益分别为3百元/日和2百元/日。厂方仅有资金14万元，安装面积18m2， 为使收益最大，厂方应购进甲、乙机床各多少台？
j x5
z

j
1 2
cj zj
2 x2 2
3
x1
31 2
0 x3 1
cj zj
23 00 0
x 1 x 2 x 3 x 4 x5
0
1
1 1 22
0
1
0
1 4
3 4
0
0 0 0
00 0
11 142

15 524
1 0
44
0 1 0 1 1
2
1 0 0 1 1
2
0 0 1 1 2
(2)
4x1+2x2=18
6
5
4
1、去掉变量为整数约束，可 3
用图解法求得最优解；
2 1
(3.25,2.5)T (1) 2x1+3x2=14
x1=3.25非整数，进行分枝
0 1 2 3 4 5 6 7 8 9 x1
x1=3.25非整数，进行分枝
2、得两个子问题的数学模型:
子问题(1)
max Z 3 x 1 2 x 2
子问题(1)
Z(1) < Z(2) =14
max Z 3 x 1 2 x 2
2 x 1 3 x 2 14
子问题2停止分枝，其整数解作为界；


4 x x
x
1 1
12 3
x分2 枝1约8
,x2 0
束

子问题1对x2=2.67进行分枝
子问题(3)
子问题(4)
x2
写出该行在最终表中的约束方程
根据右端为整数且变量非负的要求，得到：
1
1
x1
x4
2
x5
3 2
1 2

1 2
x5

0
将上式所有常数分写成整数与正分数之和： 加上松弛变量之后得到
x1x4 （ 11 2） x531 2
分数移项到右端，整数项到左端：
11 22
x5
x6
0
11 x1x4x5322x5
分别用图解法求得最优解
最优解：X*=X(2) =(4,1)T 最优值：Z*=14
X(3)=(3,2)T, X(4)=(2.5,3)T,
Z(3)=13 Z(4)=13.5
Z(3) < Z(2) ; Z(4) < Z(2)
添加x1≤3
问题(0) x1=3.25,x2=2.5
Z(0)=14.75
添加x1≥4
2
0 0 1 1 2
0 0 0 1 1
2
1 21 2x31 2x4x5 0
最优解仍为非整数解 继续寻找Gomory约束
2
x2 2 0 1
0 1 1
2
3
x1
31 2
1
0 0 1 1
2
0 x3 1
0 0 1 1 2
cj zj
0 0 0 1 1
2
最优解仍为非整数解 继续寻找Gomory约束
Z(1) < Z(2) =14
max Z 3 x 1 2 x 2
2 x 1 3 x 2 14
子问题2停止分枝，其整数解作为界；


4 x x
x
1 1
12 3
x分2 枝1约8