朝鲜辣白菜的腌制方法-圣诞节的图片

《线性规划》课程设计


题 目： 割平面法及其数值实现
院 系：数理科学与工程学院应用数学系
专 业： 数学与应用数学
姓名学号： *** 1******
*** 1******
*** 1******
*** 1******
指导教师： 张世涛


日 期： 2015 年 6 月 11 日

摘要

整数规划与线性规划有着密不可分的关系，它的一些基本算法的设计都是从 相应的线
性规划的最优解出发的。整数规划问题与我们的实际生活有着密切的联系，如合成下料问
题、建厂问题、背包问题、投资决策问题、旅行商问题、生产顺序表问题等都是求解整数
模型中的著名 问题。所以要想掌握生活中这些解决问题的方法，研究整数规划是必然的路
径。用于解决整数规划的方法 主要有割平面法，分支定界法，小规模0-1规划问题的解法，
指派问题和匈牙利法。本文重要对整数规 划中经常用的割平面法加以介绍及使用Matlab
软件对其数值实现。
割平面 法从线性规划问题着手,在利用单纯型法的时候,当约束矩阵中出现分数,给出
一种化分为整的方法。然 后在割平面方法来解决整数线性规划的理论基础上,把化分为
整的方法进行到底，直到求解出最有整数解 。

关键词：
最优化；整数规划；割平面法；数值实现；最优解；Matlab软件。

Abstract

The integer programming are closely related to the linear programming. Some of the basic
algorithms of the former are designed from the optimal solution of the corresponding linear
programming. What’s more, our daily life has a close relationship with it as well, such as
synthesis problem, plant problem, knapsack problem, investment decision problem, traveling
salesman problem and production sequence table problems. They are famous questions in
solving integer model. So, to study the integer programming is the inevitable way to master the
methods of solving these problems in life. The methods used in solving the integer
programming include cutting plane method, branch and bound method, and solving the
problem of small-scale 0-1 programming, assignment problem and Hungarian method. In this
paper, we introduce the cutting plane method and use Matlab to get its numerical
implementation in the integer programming.
Cutting plane method, giving us a
scores in the use of simplex method, starts from the linear programming problem. Then, based
on the theory of cutting plane method to solve the integer linear programming, we use
“integrated” method until the most integer solution is solved.
Keywords:
Optimization; Integer programming; Cutting plane method; Numerical
implementation; Optimal solution; Matlab software.

线性规划课程设计
目录
第一章 问题描述…………………………………………………………………2
1.1 整数规划问题概述………………………………………………………2
1.2 整数规划的基本定理……………………………………………………2
第二章 求解整数规划问题的割平面法………………………………………3
2.1 基本思想…………………………………………………………………3
2.2 算法步骤…………………………………………………………………3
2.3 算法流程图………………………………………………………………5
第三章 数值实验…………………………………………………………………6
3.1算例…………………………………………………………………………6
3.2 数值实现……………………………………………………………………7
总结………………………………………………………………………………8
参考文献……………………………………………………………………………
附录…………………………………………………………………………………








1

线性规划课程设计
第一章 问题描述
1.1 整数规划问题概述
规划中的变量（全部或部分）限制为整数，称为整数规划简称为IP问题。依
照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整
数规划、0－1 整数规划。
自1958年由R.E.戈莫里提出割平面法之后，整数规划开始形成独立分支，< br>30多年来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成
一个相关的问题， 称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更
易于求解的松弛问题（衍生问题称为松弛问 题的源问题）。通过松弛问题的解来
确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个 它本身的衍
生问题来替代它。随即,再选择一个尚未被舍弃的或替代的原问题的衍生问题，
重复 以上步骤直至不再剩有未解决的衍生问题为止。 其一般数学模型为：
minZ(或maxZ)
c
j
x
j
j1
n

n

a
ij
x
j
b
i

i1,2,... m





j1

x
j0

j1,2...n

且部分或全为整数

1.2整数规划问题的基本定理
对整数规划问题：
（IP）
maxzCX
（LP）
maxzCX
（IP问题的松弛问题）

AXb
< br>AXb

s.t

X0


s.t


X0


x为整数
j

(1)IP的可 行解域

松弛问题LP的可行解域

若松弛问题LP无可行解，则
I P问题无可行解。
(2)IP的最优值

松弛问题LP的最优值

松弛问题LP的最优值是原整数规
划IP的目标函数值的上界。
(3)若 松弛问题LP可以找到一个整数解
X
，则
X
的目标函数值为IP最优值
的下界。
(4) 若松弛问题LP的最优解
X
*
为整数解，则< br>X
*
也是IP问题的最优解。

2

线性规划课程设计
第二章 求解整数规划问题的割平面法

2.1基本思想

先不考虑整数约束条件，求松弛问题的最优解，如果 获得整数最优解，即为
所求，运算停止。如果所得到的最优解不满足整数约束条件。则在此非整数解的< br>基础上增加新的约束条件重新求解。这个新增加的约束条件的作用就是去切割相
应松弛问题的可行 域，即割去松弛问题的部分非整数解（包括与已得到的非整数
最优解）。而把所有的整数解都保留下来， 故新称增加的约束条件为割平面。当
经过多次切割后，就会使保留下来的可行域上有一个坐标为整数的顶 点，它恰好
就是所求的问题的整数最优解，即所切割后所对应的松弛问题，与原整数规划问
题具 有相同的最优解。
割平面法的关键在于如何寻找适当的切割约束条件（即构造一个割平面），
且保证切掉的部分不含有整数解。由于用割平面法求解IP问题常常会遇到收敛
很慢的情况。所 以用它来求解IP问题的仍然不多，但在理论上是重要的。

2.2 算法步骤

（1）用单纯形法求解( IP )对应的松弛问题( LP )：
①若( LP )没有可行解，则( IP )也没有可行解，停止计算。
②若( LP )有最优解，并符合( IP )的整数条件，则( LP )的最优解即为( IP )
的最优解，停止计算。
③若( LP )有最优解，但不符合( IP )的整数条件，转入下一步。

（2）从(LP)的最优解中，任选一个不为整数的分量x
i
,,将最优单纯形表中该行
'
的系数
a
ij
和< br>b
i
'
分解为整数部分和非负真分数（纯小数）部分之和，并以该行为源
行，按下式作割平面方程：

jj
N

f
ijij
xf
ij
( 其中
f
ij
是
a
ij
的小数部分，
f
i< br>是
b
i
'
的小数部分）
'
求割平面方程的一般化描述如下：
①设
x
B
i
是伴随规划单纯形表上第i行约束方程所对应的基变量，其取值为
非整数，则其约束方程式为：
3

线性规划课程设计

x
B
i

jJ
N

ax
'
ijj
b
i
'

'
其中
J
N
为非基变量的下标集。
a
ij
,b
i
'
分别为第i个约束中非基变量
x
j
的当前系数
及第i个约束的右端项的当前 值。
'
②将
a
ij
,b
i
'
拆分。记

b

b

f,
'
i
'
ii
''< br>a
ij
a
ij
f
ij
,jJ
N

式中

a

,b

'
ij
'
i
'
分别表示不超过
a
ij
, b
i
'
的最大整数，而
0f
ij
1,0f
i
1

于是，讲中的两式代入约束方程式，得
x
B
i

或
jJ
N


a

x

f
'
ijj
jJ
N
ij
x
j
b
i
'
f
i
< br>

'

'

fxfbxax

ijjiiB
i
ijj



jJ
N
jJ
N


由于
因此有

'

'

bxax
，及
fx0,0f1

B
i
ijij

为大于等 于0的整数。

ijji

i
jJ
N
jJN


jJ
N

f
ij
x
j
f
i
或

jJ
N

f
ij
x
j
f
i

再加松弛变量
x
s
，化为等式：

jJ
N
f
ij
x
j
x
s
f
i

此即割平面方程的最基本的形式。

（3）将所得的割平面方程作为一个新的约 束条件置于最优单纯形表中（同时增
加一个单位列向量），用对偶单纯形法求出新的最优解，返回1。


4

线性规划课程设计
2.3 算法流程图



用单纯形法（对偶单纯形法）求解
给定LP


LP无可行解
LP有可行解且为
最优解，设为x
*


IP无可行
解


x
*
是整数
解？
是
停止，输出x
*

停止计算




不是
作割平面方程：
jj
N

f
ijij
xf
ij

再加松弛变量
x
s
，化为等式：



f
jJ
N
ij
x
j
x
s
f
i


将所得的割平面方程作为一个新
的约束条件置于最优单纯形表中（同时增加一个单位列向量）

5

线性规划课程设计
第三章 数值实验
3.1 算例
用割平面法求解数规划问题：
maxZx
1
x
2

2x
1
x
2
6



4x
1
5x
2
2 0

x,x0且为整数

12
解：将该问题化为最小化问题（由于 我编写的程序用于求解最小化问题，故需
要将最大化问题转化为最小化问题）：
minw Zx
1
x
2

2x
1
x
2
6



4x
1
5x
2
20
x,x0且为整数

12
增加松弛变量
x
3
和
x
4
，得到(LP)的初始单纯形表和最优单纯形表：
初始表:
C
j

C
B

0
0
w
X
B

b
6
20

-1 -1 0 0
x
1

2
4
-1
最优表:
x
2

1
5
-1
x
3

1
0
0
x
4

0
1
0
x
3

x
4

C
j

C
B

-1
X
B

b
53
-1 -1 0 0
x
1

1
x
2

0
x
3

56
x
4

－16
x
1

6

线性规划课程设计
C
j

-1
w
-1
83
-133
0
0
-1
1
0
0
－23
16
0
13
16
x
2

在松弛问题最优解中，
x
1
,
x
2
均为非整数解，由上表有：
取割平面：
112
x
3
x
4


333
引入松弛变量
s
1
后得到下式，将此约束条件加到上表中，继续求解。
C
j

C
B

-1
-1
0
w
C
j

C
B

-1
-1
0
w
X
B

b
0
4
2
-4
X
B

b
53
83
-23
-133
-1 -1 0 0 0
x
1

1
0
0
0
-1
x
2

0
1
0
0
-1
x
3

56
－23
-13
16
0
x
4

－16
13
-13
16
0
s
1

0
0
1
0
0
x
1

x
2

s
1

x
1

1
0
0
0
x
2

0
1
0
0
x
3

0
0
1
0
x
4

－1
1
1
0
s
1

52
-2
-3
12
x
1

x
2

x
3

得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解：
X= (0, 4), Z = 4, 或X = (2, 2), Z = 4。
7
**

线性规划课程设计

3.2 数值实现
>> Example

X =

2 2

z =

-4
由于本程序求解的是最小化问题，故转化为最大化问题的最大值为Z=4，最
优解为X= (2, 2)。
程序运行结果截图如下：



8

线性规划课程设计
参考文献

[1] 何坚勇. 最优化方法（第1版）[M]. 北京: 清华大学出版社, 2007.
[2] 李裕梅, 连晓锋, 徐美萍,曹显兵. 整数规划中割平面法的研究[J]. 计算机工
程, 2011, 11(15): 32-35.
[3] 佚名. 百度百科割平面法[EBOL].(2014-06-26) [2015-05-28]
http:












9

线性规划课程设计
附录
Example.m文件：
clear
As=[2 1;4 5];
Ab=[];
b=[6;20];
c=[-1 -1];
[X,z]=CuttingPlaneMethod(As,Ab,b,c)

CuttingPlaneMethod.m文件：
%此程序采用割平面法求解整数规划问题
%该程序用于求解最小化问题；若为最大化问题，则必须化为最小化问题。
%As表示小于等 于的不等式约束，Ab表示大于等于的不等式约束,b表示不等式
约束的右端项，c表示价值系数。
function [X,z]=CuttingPlaneMethod(As,Ab,b,c)
s=length(c);
[A,As,b,c,X,z]=BigMMethod(As,Ab,b,c);
BL=0;
for i=1:s
if floor(X(i))==X(i)
BL=BL+1;
end
end
while BL i=1;
while i<=length(b) && floor(b(i))==b(i)
i=i+1;
end
if i<=length(b)
bm=b(i)-floor(b(i));
Ab=A(i,:)-floor(A(i,:));%为生成的割平面
As=A;
b=[b;bm];%由于A=[As;Ab]故bm应加到b的最后一个位置与Ab对应
[A,As,b,c,X,z]=BigMMethod(As,Ab,b,c);
end
BL=0;
10

线性规划课程设计
for i=1:s
if floor(X(i))==X(i)
BL=BL+1;
end
end
end
X=X(1:s);
z;

BigMMethod.m文件：
%此程序采用大M法求解线性规划问题
%该程序用于求解最小化问题；若为最大化问题，则必须化为最小化问题。
%As表示小于等 于的不等式约束，Ab表示大于等于的不等式约束,b表示不等式
约束的右端项，c表示价值系数。
function [A,As,b,c,X,z]=BigMMethod(As,Ab,b,c)
M=99999;
s=length(c);
if ~isempty(Ab)
c=[c,zeros(1,length(Ab(:,1)))];
As=[As,zer os(length(As(:,1)),length(Ab(:,1)))];
Ab=[Ab,-eye(length(Ab(:,1)))];
m1=0;
k=zeros(1,length(Ab(1,:)));
for j=1:length(Ab(1,:))
n=0;
for i=1:length(Ab(:,1))
if Ab(i,j)~=0
n=n+1;
end
end
if n==1
if find(Ab(:,j)==1)
m1=m1+1;
k(j)=find(Ab(:,j)==1);
end
end
end
11

线性规划课程设计
k=sort(k);
D=eye(length(Ab(:,1)));
for i=1:length(k)
if k(i)==1
D=D(:,2:length(D(1,:)));
k=k-1;
elseif k(i)>1 && k(i) D=[D(:,1:k(i)-1),D(:,k(i)+1:length(D(1,:)))];
k=k-1;
elseif k(i)==length(D(1,:))
D=D(:,1:length(D(1,:))-1);
k=k-1;
end
end
Ab=[Ab,D];
CE=ones(1,length(Ab(:,1))-m1)*M;
c=[c,CE];
As=[As,zeros(length(As(:,1)),length(D(1,:)))];
end
A=[As;Ab];
m2=0;
k=zeros(1,length(A(1,:)));
for j=1:length(A(1,:))
n=0;
for i=1:length(A(:,1))
if A(i,j)~=0
n=n+1;
end
end
if n==1
if find(A(:,j)==1)
m2=m2+1;
k(j)=find(A(:,j)==1);
end
end
end
D2=eye(length(A(:,1)));
12

线性规划课程设计
k=sort(k);
for i=1:length(k)
if k(i)==1
D2=D2(:,2:length(D2(1,:)));
k=k-1;
elseif k(i)>1 && k(i) D2=[D2(:,1:k(i)-1),D2(:,k(i)+1:length(D2(1,:)))];
k=k-1;
elseif k(i)==length(D2(1,:))
D2=D2(:,1:length(D2(1,:))-1);
k=k-1;
end
end
A=[A,D2];
X=zeros(1,length(A));
CB=zeros(1,length(b));
CE=zeros(1,length(A(:,1))-m2);
c=[c,CE];
xB=zeros(1,length(b));
for i=1:length(b)
F=zeros(length(b),1);
F(i)=1;
for j=1:length(A(1,:))
if A(:,j)==F
xB(i)=j;
end
end
end
for i=1:length(b)
CB(i)=c(xB(i));
end
P=zeros(1,length(A(1,:)));
for i=1:length(A(1,:))
P(i)=c(i)-CB*A(:,i);
end
if max(P)<=0
for i=1:length(b)
13

线性规划课程设计
X(xB(i))=b(i);
end
end
while min(P)<0
q=-ones(length(A(:,1)),1);
[~,t1]=min(P);
for j=1:length(q)
if A(j,t1)>0
q(j)=b(j)A(j,t1);
end
end
q(q==-1)=9999;
[~,t2]=min(q);
xB(t2)=t1;
CB(t2)=c(t1);
b(t2)=b(t2)A(t2,t1);
A(t2,:)=A(t2,:)A(t2,t1);
for i=1:length(A(:,t1))
if i~=t2 && A(i,t1)~=0
b(i)=b(i)-b(t2)*A(i,t1);
A(i,:)=A(i,:)-A(t2,:)*A(i,t1);
end
end
P=P-A(t2,:)*P(t1);
end
z=CB*b;
for i=1:length(b)
X(xB(i))=b(i);
end
X=X(1:s);

14