我爱学习大二下课程运筹学or03整数

运筹帷幄之中决胜千里之外运筹学课件整数线性规划IntegerLinearProgramming整数线性规划

IntegerProgramming整数线性规划问题的提出割平面解法分支定界解法

0-1型整数线性规划指派问题

3.1.1模型及整数规划的实例例1某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表所示。问两种货物各托运多少箱，可使获得利润为最大?3.1整数规划问题

设x1，x2分别为甲、乙两种货物的托运箱数(当然都是非负整数)。这是一个(纯)整数线性规划问题，用数学式可表示为：

maxz=20x1+10x2①5x1+4x2≤24②2x1+5x2≤13③x1，x2≥0④x1，x2整数⑤整数线性规划问题的分类全整数线性规划混合整数线性规划0-1整数线性规划整数线性规划问题的一般形式3.1.2解的特点整数规划问题去掉整数约束条件后得到的线性规划称为原整数规划的松弛问题。为了满足整数解的要求，似乎只要把松弛问题的带有分数或小数的解经过“舍入化整”就可以了。但这常常是不行的，因为化整后不见得是可行解；或虽是可行解，但不一定是最优解。当放弃整数约束时得到的线性规划称为整数规划的松弛问题。整数规划的可行域是松弛问题的可行域，反之不成立。

例1中，对于松弛问题，最优解为:x1=4.8，x2=0，maxz=96maxz=20x1+10x2①5x1+4x2≤24②2x1+5x2≤13③x1，x2≥0④

如将(x1=4.8，x2=0)凑整为(x1=5，x2=0)，这样就破坏了条件②，它不是可行解；如将(x1=4.8，x2=0)舍去尾数0.8，变为(x1=4，x2=0)，是可行解，但不是最优解，因为此时z=80.

但当x1=4，x2=1(这也是可行解)时，z=90。3.2全整数规划的求解

---Gomory割平面方法

割平面解法的思路是：首先不考虑变量是整数，仍然是用解线性规划的方法去解整数线性规划问题，若得到非整数的最优解，然后增加能割去非整数解的线性约束条件(或称为割平面)使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。

例3-5用割平面法求解整数规划问题目标函数maxz=x1+x2①

约束条件：

-x1+x2≤1②3x1+x2≤4③(3-5)x1，x2≥0④x1，x2

整数⑤相应的松弛问题的最优解：

x1=3/4，x2=7/4，maxz=10/4

它就是图中域R的极点A，但不合于整数条件。现设想，如能找到像CD那样的直线去切割域R，去掉三角形域ACD，那么具有整数坐标的C点(1，1)就是域R′的一个极点，

如在域R′上求解①～④，而得到的最优解又恰巧在C点就得到原问题的整数解，所以解法的关键就是怎样构造一个这样的“割平面”CD，尽管它可能不是唯一的，也可能不是一步能求到的。对于松弛问题，增加非负松弛变量x3、x4，使两式变成等式约束：-x1+x2+x3=1⑥3x1+x2+x4=4⑦最终表中，最优解：x1=3/4，x2=7/4，x3=x4=0，maxz=5/2

不能满足整数最优解的要求。为此考虑将带有分数的最优解的可行域中分数部分割去，再求最优解。就可以得到整数的最优解。可从最终计算表中得到非整数变量对应的关系式：为了得到整数最优解。将上式变量的系数和常数项都分解成整数和非负真分数两部分之和(1+0)x1+(-1+3/4)x3+1/4x4=0+3/4x2+(3/4)x3+(1/4)x4=1+3/4然后将整数部分与分数部分分开，移到等式左右两边，得：

得到一个割平面约束，将它作为增加约束条件。

引入松弛变量x5，得到等式即割平面方程-3x3-x4+x5=-3

将这新的约束方程加到最终计算表

这就是(x1，x2)平面内形成新的可行域，即包括平行于x1轴的直线x2=1和这直线下的可行区域，整数点也在其中，没有切割掉。求一个切割方程的步骤（1）令xi是相应线性规划最优解中为分数值的一个基变量，由单纯形表的最终表得到其中k∈K(K指构成非基变量号码的集合)（2）将bi和αik都分解成整数部分N与非负真分数f之和，即

bi=Ni+fi，其中0＜fi＜1αik=Nik+fik，其中0≤fik＜1

而N表示不超过b的最大整数。（3）代入（3-20）分析，得到割平面约束加上松弛变量化为割平面方程3.3混合整数规划的求解

---分枝定界方法分枝：当不符合整数要求时，构造两个约束条件：加入松弛问题分别形成两个子问题（分枝）定界：当子问题获得整数规划的一个可行解，则它的目标函数值就构成一个界限例132X254X1231S解S得：132X254X1231S2对S分枝：构造约束：和形成分枝问题S1和S2，得解B和CS1SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9132X254X1231S2对S1分枝：构造约束：和形成分枝问题S11和S12，得解DS12S11无可行解SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11无可行解S12D:x1=33/14,x2=2Z=61/14132X254X1231S2对S12分枝：构造约束：和形成分枝问题S121和S122，得解E和FS121S122SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11无可行解S12D:x1=33/14,x2=2Z=61/14S122F:x1=2,x2=2Z=4S121E:x1=3,x2=1Z=4从以上解题过程可得到，用分支定界法求解整数线性规划(最大化)问题的步骤为：ILP称为问题A，相应的松弛问题称为问题B。(1)解问题B，可能得到以下情况之一。①B没有可行解，这时A也没有可行解，则停止。②B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则停止。③B有最优解，但不符合问题A的整数条件，它的目标函数值为z*的上界

第一步：分支，在B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以［bj］表示小于bj的最大整数。构造两个约束条件

xj≤［bj］和xj≥［bj］+1

将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。不考虑整数条件求解这两个后继问题。定界，以每个后继问题为一分支标明求解的结果，与其他问题的解的结果中，找出最优目标函数值最大者作为新的上界。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界，若无可行解，

第二步：比较与剪枝各分支的最优目标函数中若有小于下界者，则剪掉这支(用打×表示)，即以后不再考虑了。若大于下界，且不符合整数条件，则重复第一步骤。一直到最后得到z*为止，得最优整数解xj*，j=1，…，n。

用分支定界法可解纯整数线性规划问题和混合整数线性规划问题。它比穷举法优越。因为它仅在一部分可行解的整数解中寻求最优解，计算量比穷举法小。若变量数目很大，其计算工作量也是相当可观的。3.40-1整数规划变量只能取0或1的整数线性规划3.4.10-1规划的应用项目投资预算变量假设:模型:0-1规划的应用-工厂-销售点配置问题生产厂顾客需求销售点45DCBA7IIIII213I工厂-销售点配置问题问题:为使经营成本最低,应开设那些工厂及销售点?固定成本问题高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为150万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。

解：这是一个整数规划的问题。设x1，x2，x3分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设yi=1(当生产第i种容器,即xi＞0时)或0（当不生产第i种容器即xi=0时）。引入约束xi≤Myi，i=1，2，3，M充分大，以保证当yi=0时，xi=0。

这样我们可建立如下的数学模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300

x1+2x2+3x3≤100xi≤Myi，i=1，2，3，M充分大

xj≥0yj

为0--1变量，i=1,2,3

解0-1型整数线性规划最容易想到的方法，和一般整数线性规划的情形一样，就是穷举法，即检查变量取值为0或1的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的2n个组合。对于变量个数n较大(例如n＞10)，这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法(implicitenumeration)，分枝定界法也是一种隐枚举法。当然，对有些问题隐枚举法并不适用，所以有时穷举法还是必要的。3.4.20-1规划的解法最优解（x1,x2,x3)=(1,0,1)