运筹学与最优化MATLAB编程实验报告
院系：专业：姓名：学号：指导老师：完成日期：
割平面法求解整数规划问题
一、引言：通过对MATLAB实践设计的学习，学会使用MATLAB解决现实
生活中的问题。该设计是在MATLAB程序设计语言的基础上，对实际问题建立数学模型并设计程序，使用割平面法解决一个整数规
f划问题。经实验，该算法可成功运行并求解出最优整数解。
二、算法说明：
割平面法有许多种类型，本次设计的原理是依据Gomory的割平
面法。Gomory割平面法首先求解非整数约束的线性规划，再选择一
个不是整数的基变量，定义新的约束，增加到原来的约束中，新的约
束缩小了可行域，但是保留了原问题的全部整数可行解。
算法具体设计步骤如下：
1、首先，求解原整数规划对应的线性规划
mi

f
x

c

x
Axb
st
x

0
，设最优解为
x。
2、如果最优解的分量均为整数，则x为原整数规划的最优解；
否则任选一个x中不为整数的分量，设其对应的基变量为xp，定义
包含这个基变量的切割约束方程xprijxjbco
，其中xp为非基变量。
j
3、令rijrijrij，bco
bco
bco
，其中为高斯函数符号，表
示不大于某数的最大整数。将切割约束方程变换为
xprijxjbco
bco
rijxj，由于0rij1，0bco
1，所以有
j
j
bco
rijxj1，因为自变量为整数，则bco
rijxj也为整数，所以进
j
j
一步有bco
rijxj0。
j
4、将切割方程加入约束方程中，用对偶单纯形法求解线性规划
mi

f
x

c

x
stbco

Ax
brijx
j
0

j
x0
，然后在转入步骤2进行求解，直
到求出最优整数解停止迭代。
f三、程序实现：程序设计流程图如图1，具体设计代码见附录。
开始
初始化并赋值
否
用单纯形法求最优解
初始解是否为最优解
是
用对偶单纯形法求出最优解
是否找到最优解
是
是否为整数解
否
构建切割方程并形成新的约束矩阵
否
是
输出“找不到最优解”
输出最优整数解
程序结束
图1
四、算例分析：已知AM工厂是一个拥有四个车间的玩具生产厂商，该厂商今年
新设计出A、B、C、D、E、F六种玩具模型，根据以前的生产情况及市场调查预测，得知生产每单位产品所需的工时、每个车间在一季度的工时上限以及产品的预测价格，如下表所示。问：每种设计产品在这个季度各应生产多少，才能使AM工厂这个季度的生产总值达到最大？
f产品
每个车间每季
A
B
C
D
E
F
车间
度工时上限
甲001001001003003003
850
乙002
005
700
丙
002
005
100
丁
003
008
900
单价201416r