下载文档原格式
整数规划的割平面法计算流程与举例下载温馨提示:该文档是我店铺精心编制而成，希望大家下载以后，能够帮助大家解决实际的问题。
文档下载后可定制随意修改，请根据实际需要进行相应的调整和使用，谢谢!并且，本店铺为大家提供各种各样类型的实用资料，如教育随笔、日记赏析、句子摘抄、古诗大全、经典美文、话题作文、工作总结、词语解析、文案摘录、其他资料等等，如想了解不同资料格式和写法，敬请关注!Download tips: This document is carefully compiled by theeditor.I hope that after you download them,they can help yousolve practical problems. The document can be customized andmodified after downloading,please adjust and use it according toactual needs, thank you!In addition, our shop provides you with various types ofpractical materials,such as educational essays, diaryappreciation,sentence excerpts,ancient poems,classic articles,topic composition,work summary,word parsing,copy excerpts,other materials and so on,want to know different data formats andwriting methods,please pay attention!整数规划中的割平面法计算流程与实例解析整数规划是运筹学中的一个重要分支，它涉及到在满足一系列线性约束条件下，寻找整数变量的最大值或最小值。
《线性规划》课程设计题目：割平面法及其数值实现院系：数理科学与工程学院应用数学系专业：数学与应用数学姓名学号：*** 1********* 1********* 1********* 1******指导教师：***日期：2015 年 6 月11 日整数规划与线性规划有着密不可分的关系，它的一些基本算法的设计都是从相应的线性规划的最优解出发的。
整数规划问题与我们的实际生活有着密切的联系，如合成下料问题、建厂问题、背包问题、投资决策问题、旅行商问题、生产顺序表问题等都是求解整数模型中的著名问题。
所以要想掌握生活中这些解决问题的方法，研究整数规划是必然的路径。
用于解决整数规划的方法主要有割平面法，分支定界法，小规模0-1规划问题的解法，指派问题和匈牙利法。
本文重要对整数规划中经常用的割平面法加以介绍及使用Matlab 软件对其数值实现。
割平面法从线性规划问题着手,在利用单纯型法的时候,当约束矩阵中出现分数,给出一种"化分为整"的方法。
然后在割平面方法来解决整数线性规划的理论基础上,把"化分为整"的方法进行到底，直到求解出最有整数解。
关键词：最优化；整数规划；割平面法；数值实现；最优解；Matlab软件。
AbstractThe 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 "integrated" method when we meet the constraint matrix 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 整数规划问题概述规划中的变量（全部或部分）限制为整数，称为整数规划简称为IP 问题。
运筹学与最优化MATLAB 编程实验报告割平面法求解整数规划问题一、 引言：通过对MATLAB 实践设计的学习，学会使用MATLAB 解决现实生活中的问题。
该设计是在MATLAB 程序设计语言的基础上，对实际问题建立数学模型并设计程序，使用割平面法解决一个整数规划问题。
经实验，该算法可成功运行并求解出最优整数解。
二、 算法说明：割平面法有许多种类型，本次设计的原理是依据Gomory 的割平面法。
Gomory 割平面法首先求解非整数约束的线性规划，再选择一个不是整数的基变量，定义新的约束，增加到原来的约束中，新的约束缩小了可行域，但是保留了原问题的全部整数可行解。
算法具体设计步骤如下：1、首先，求解原整数规划对应的线性规划,*)(min x c x f =⎩⎨⎧≥≤0..x bAx t s ，设最优解为x*。
2、如果最优解的分量均为整数，则x*为原整数规划的最优解；否则任选一个x*中不为整数的分量，设其对应的基变量为x p ，定义包含这个基变量的切割约束方程con jj ij p b x r x =+∑，其中x p 为非基变量。
3、令][ij ij ij r r r -=，][con con con b b b -=，其中[]为高斯函数符号，表示不大于某数的最大整数。
将切割约束方程变换为∑∑-=-+jjij con con jj ij p x r b b x r x ][][，由于0<ij r <1，0<con b <1，所以有1<-∑jj ij con x r b ，因为自变量为整数，则∑-jj ij con x r b 也为整数，所以进一步有0≤-∑jj ij con x r b 。
4、将切割方程加入约束方程中，用对偶单纯形法求解线性规划⎪⎪⎩⎪⎪⎨⎧≥≤-≤=∑00..,*)(min x x r b b Ax t s x c x f j j ij con ，然后在转入步骤2进行求解，直到求出最优整数解停止迭代。
割平面法的基本思想割平面法主要用于求解整数规划问题的方法。
1958年由美国格莫理提出。
基本思路是：先不考虑整数性约束，求解相应的线性规划问题。
若线性规划问题的最优解恰好是整数解，则此解即为整数规划问题的最优解。
否则，就增加一个新的约束条件,称为割平面。
割平面必须具有两条性质：（1)从线性规划问题的可行域中至少割掉目前的非整数最优解；（2)不割掉任何整数可行域，然后在缩小的可行域上继续解线性规划问题。
重复以上做法，经有限次切割后，必可在缩小的可行域的一个整数极点上达到整数规划问题的最优解。
混合整数线性规划（MILP）的割平面法通过将整数问题线性松弛为非整数线性问题，并对其进行求解，来求解MILP 问题。
线性规划理论说明，在温和的假定下（如果线性规划存在最优解，并且可行域不包含一条线），总存在一个极值点或顶点是最优的。
检验所获的最优解是否为整数解。
如否，则必然存在一线性不等式将最优点和真可行集的凸包分离。
找到这样的不等式是分离问题，而这样的不等式就是切割。
切割可以被加入到被松弛的线性规划中，使得当前的非整数解对松弛不再可行。
该过程不断重复，直到找到最优整数解。
用于普遍的凸连续优化和变体的割平面法有不同的名称：Kelley 法，Kelley-Cheney-Goldstein 法和捆绑法。
它们常用于不可微的凸最小化问题。
对于这类问题，通常的可微优化的梯度法无法使用，而使用这些方法可以高效地得到凸目标函数及其次梯度。
这种情况最常出现在双拉格朗日函数的凹优化中。
另一种常见情形是Dantzig-Wolfe分解应用于结构优化问题中，这类问题通常有含有指数级变量的表达式。
通过延迟列生成法按需生成这些变量等同于在对应的对偶问题上切割平面。
图1.割平面法例，如上图1，单位立方体与切割平面。
在三节点的旅行推销员问题中，该（弱）不等式表明每次旅行必须连接至少两个点。
2Gomory 切割切割平面法由Ralph Gomory 在19 世纪50 年代提出，用于解决整数规划和混合整数规划问题。
割平面法
求解整数规划问题：
Max Z=3x1+2x2
2x1+3x2≤14
4x1+2x2≤18
x1,x2≥0，且为整数
解：首先，将原问题的数学模型标准化，这里标准化有两层含义：（1）将不等式转化为等式约束，（2）将整数规划中所有非整数系数全部转化为整数，以便于构造切割平面。
从而有：
Max Z=3x1+2x2
2x1+3x2+x3=14
2x1+x2+x4=9
x1,x2≥0，且为整数
利用单纯形法求解，得到最优单纯形表，见表1：
表1
最优解为：x1=13/4, x2=5/2, Z=59/4
根据上表，写出非整数规划的约束方程，如：x2+1/2x3-1/2x4=5/2 (1)
将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式，即：
(1+0)x2+(0+1/2)x3+(-1+1/2)x4=2+1/2
把整数及带有整数系数的变量移到方程左
边，分数及带有分数系数的变量称到方程右边，得：
x2 - x4-2 =1/2-(1/2x3+1/2x4) (2)
由于原数学模型已经“标准化”，因此，在整数最优解中，x2和x4也必须取整数值，所以(2)式左端必为整数或零，因而其右端也必须是整数。
又因为x3,x4≥0，所以必有：
1/2-(1/2x3+1/2x4)<1
由于(2)式右端必为整数，于是有：
1/2-(1/2x3+1/2x4)≤0 (3)
或
x3+x4≥1 (4)
这就是考虑整数约束的一个割平面约束方程，它是用非基变量表示的，如果用基变量来表示割平面约束方程，则有：
2x1+2x2≤11 (5)
从图1中可以看出，(5)式所表示的割平面约束仅割去线性规划可行域中不包含整数可行解的部分区域，使点E(3.5，2)成为可行域的一个极点。
图1
在(3)式中加入松弛变量x5，得：
-1/2x3-1/2x4+x5=-1/2 (6)
将(6)式增添到问题的约束条件中，得到新的整数规划问题：
Max Z=3x1+2x2
2x1+3x2+x3=14
2x1+x2+x4=9
-1/2x3-1/2x4+x5=-1/2
x i 0，且为整数，i=1,2,…,5
该问题的求解可以在表1中加入(6)式，然后运用对偶单纯形法求出最优解。
具体计算过程见表2：
表2
由此得最优解为：x1=7/2, x2=2, z=58/4
该最优解仍不满足整数约束条件，因而需进行第二次切割。
为此，从表2中抄下非整数解x1的约束方程为：
x1+x4-1/2x5 = 7/2
按整数、分数归并原则写成：
x1+x4-x5-3 = 1/2-1/2x5≤0 (7)
这就是一个新的割平面方程，用基变量来表示，得：
x1+x2≤5 (8)
在(7)中加入松弛变量x6，得：
-1/2x5+x6=-1/2 (9)
将(9)式增添到前一个问题的约束条件中去，得到又一个新的整数规划问题，对它求解可以在表2中加入(7)式，然后运用对偶单纯形法求出最优解。
具体计算过程见表3：
表3
由此得最优解为：x1=4, x2=1,z=14。
该最优解符合整数条件，因此也是原整数规划问题的最优解。
从图1中可以看出，由(8)式表示的割平面约束，不仅割去线性规划可行域中剩下的不含整数解域，而且使最优整数解x1=4, x2=1（即图2中的G点），成为新的线性规划可行域的一个极点。
图2。
