整数规划演示教案

整数规划第1节整数规划问题的特点及其作用第2节分支定界方法第3节割平面方法第4节0-1规划第5节指派（分配）问题整数规划（1）§1.整数规划问题的提出整数规划:若一个规划的最优解要求部分或全部决策变量是整数的问题纯整数规划:整数规划中如果所有的变量都为非负整数,(PureIntegerProgramming)(IntegerProgramming),简称IP或称为全整数规划(AllIntegerProgramming)混合整数规划:若整数规划中仅一部分变量限制为整数,

则称为混合整数规划(MixedIntegerProgramming)整数规划（2）0--1规划：若整数规划中的变量都仅限制为0或1,则称为0--1规划整数线性规划：若整数规划问题的目标函数和约束条件都是线性的，则称该整数规划是整数线性规划本章中，我们讨论的主要对象是整数线性规划，下面的讨论中将省略线性二字整数规划（3）问:两种货物各托运多少箱,可使获利最大?则其数学模型设x1,x2分别为托运甲、乙两种货物的数量例1.某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利及托运限制如下表:货物体积重量利润

(每箱立方米)(每箱百斤)(每箱百元)

甲5220

乙4510托运限制2413

它是一个纯整数规划,整数规划（4）它与线性规划的区别仅在于要求x1,x2为整数的条件则是否可以把所得的非整数的最优解经过”化整”来得到整数规划的最优解呢?易求出最优解为x1=4.8x2=0z*=96若不考虑整数条件,则变成一个线性规划问题但它不是原整数规划的最优解.若通过四舍五入的办法，得解为x1=5x2=0但它不是可行解故这种办法不可取的若通过取整的办法，得解为x1=4x2=0,z=80但有解x1=4x2=1,z=90整数规划的常见解法：整数规划（5）二、割平面法：常用于求解纯整数规划问题一、分支定界法：可用于求解纯整数或混合整数规划问题；解法的基本思想：(1)通过求解线性规划问题来求得整数线性规划问题的最优解；(2)在使没有整数约束的可行域以“割掉非整数解，保留需要的所有的整数可行解”的原则来压缩可行域。§2.整数规划的解法一通过例子来说明分支定界解法的步骤分支定界解法解:

先不考虑条件(5)例即解相应的线性规划(1)-----(4)的最优解分支定界解法(1)称为原问题的松驰问题用单纯形法解上述问题得x1=4.809,x2=1.817，z=355.89又由于当x1=x2=0时，是原规划的一个整数可行解，而此时z＝0。因此，原问题的最优值满足：

0≤z*≤355这就是分支定界解法中的定界含义。分支定界解法(2)9x1+7x2=567x1+20x2=70x22108642ACB0x1z＝40x1+90x2由于最优解是非整数，首先注意其中一个非整数变量(可任选),例如x1=4.809，我们可认为整数最优解x1是x14或x15,而在4和5之间是不合整数条件的,于是把原问题分解成两支,各支都增加了约束条件:即区域也分成两块R1和R2最优解：x1=4.809,x2=1.817，z=355.89R2R1这就是分支定界解法中的分支含义分支定界解法(3)9x1+7x2=567x1+20x2=70x22108642ACB0x1z＝40x1+90x2R2R1这就是分支定界解法中的分支含义分支定界解法(4)问题1有x1=4,x2=2.1z1=349.0问题2有x1=5,x2=1.571z2=341.39由于没有得到整数最优解,继续分解问题(1)和问题(2)0≤z*≤349分支定界解法(5)先分解问题(1)问题(3)有x1=4,x2=2z3=340问题(4)有x1=1.428,x2=3z4=327.12问题1有x1=4,x2=2.1z1=349.0340≤z*≤341分支定界解法(6)因为问题（3）的最优解是整数解，最优值为340但我们可以肯定,原问题的最优解不会在问题(4)中,那么该整数解是否为原问题的最优解？对问题(2)进行分解,得问题(5)和问题(6)：所以问题(4)不必去分解了.原问题的最优解可能在问题(2)中,因为问题(2)的最优值大于340这是因为,问题(4)的最优值小于问题(3)的最优值分支定界解法(7)

问题(5)有x1=5.44,x2=1,z5=308问题(6)

无可行解原问题的最优解不会在问题(5)和(6)中,这是因为问题(5)的最优值小于340,(6)没有可行解原问题的最优解:x1=4,x2=2,最优值:z*=340原问题的松驰问题：x1=4.809,x2=1.817，z=355.89分支定界解法(8)

因此，原问题的最优解:x1=4,x2=2,最优值:z*=340问题1

z1=349.0x1=4,x2=2.1问题2

z2=341.39

x1=5,x2=1.571问题3x1=4,x2=2z3=340问题4x1=1.428x2=3z4=327.12问题5x1=5.44x2=1z5=308问题6

无可行解(2)用单纯形法解(IPL);分支定界解法的步骤(3)若求得(IPL)的最优解,

(1)称原整数规划问题为(IP)称相应的线性规划(即不考虑整数条件)为松驰问题(IPL)若(IPL)没有可行解,则(IP)也没可行解.检查它是否符合整数条件,

若符合整数条件,它就是问题(IP)的最优解;否则转(4)(4)在(IPL)的解中,任选一个不符整数条件的变量xj,(i)xjbj

,(ii)xjbj

+1不考虑整数条件,分别求解这两个后继问题(5)在现有的且还没有分解后继问题的各可行问题中,选目标函数为最优的问题,重新称这个问题为(IPL),转(3)重复进行若xj=bj非整;

作两个后继问题,它们是对(IPL)分别各增加一个约束条件:

分支定界解法的注释(1)在用单纯形法继续求解后继问题时，可借助上一级终表添加约束条件进一步计算，借助单纯形法或对偶单纯形法进行计算；(2)对分支中最优值较大者先分支，得到整数解的后继问题不必继续分支；对最优值低于目前下界的后继问题不必继续分支；无可行解的后继问题不必继续分支；当所有后继问题都无法继续分支时，最优解才得到。§3.整数规划的解法二考虑纯整数规划问题：设其中aij(i=1,2,…,m;j=1,2,…,n)和bi(i=1,2,…,m)皆为整数（若不为整数，可乘上一个倍数化为整数）割平面法：(2)用单纯形法解(IPL);§3.整数规划的解法二(3)若求得(IPL)的最优解,

1.(1)称原整数规划问题为(IP)称相应的线性规划(即不考虑整数条件)为松驰问题(IPL)若(IPL)没有可行解,则(IP)也没可行解.检查它是否符合整数条件,

若符合整数条件,它就是问题(IP)的最优解;否则转2割平面法的步骤：2.(1)令xi是(IPL)的最优解中取值为非整的一个基变量，由单纯形终表可得：割平面法的步骤（2）(2)将和αij都分解成整数部分N和非整真分数f之和，即：将(2),(3)代入(1)整理，移项，得(3)考虑整数约束，(4)式由左边看是整数，且0<fi<1,所以有：割平面方程(4)用割平面方程去替代整数约束求解，具体操作为：将(5)式作为新增加的约束条件，引入松弛变量xn+1,利用对偶单纯形法求解；割平面法的步骤（3）(5)若求得整数最优解，停止计算；否则，仍有非整分量，从2.(1)开始重复，继续添加线性约束条件，相当于在已经割过的可行域上进一步再割，直到达到最优。注1：割平面方程真正进行了切割，至少把非整数最优解这一点割掉了；注2：割平面方程没有割掉任何整数可行解；注3：当(IPL)最优解中存在多个非整基变量时，选择分数部分为最大的非整基分量所在行构造割平面方程，往往可以减少“切割”次数。割平面法例子：例：用割平面法求解纯整数规划：解：求解原问题的松弛问题,前两个不等式中引入非负松弛变量x3、x4，使两式变成等式约束：-x1+x2+x3=13x1+x2+x4=4用单纯形法求解，得：割平面法例子（2）XBbx1x2x3x4

初表x3x414-13111001-z01100终表x1x23/47/41001-1/43/41/41/5-z-5/200-1/2-1/2由单纯形终表中第一行产生割平面方程：松弛问题的最优解为：x1=3/4,x2=7/4;割平面法例子（3）现考虑整数约束，得割平面方程为：将它作为新增的约束条件，再解其对应的松弛问题，引入松弛变量x5，得到：将原终表中加入一行一列，得：割平面法例子（4）XBbx1x2x3x4x5x1x2x53/47/4-3/4100010-1/43/4-3/41/41/4-1/4001-z-5/200-1/2-1/20XBbx1x2x3x4x5x1x2x31111000100011/301/3-1/121/4-1/3-z-2000-1/3-1/6此时，x*=(1,1,1,0,0)T已满足整数要求，故原整数规划问题的最优解为：x1=1,x2=1最优值为：z*=2割平面法例子（5）下面从几何角度了解一下本题中可行域的切割过程：割平面方程为：§4.0--1规划例1.在高校篮球联赛中,我校男子篮球队要从８名队员中选择平均身高最高的出场阵容,队员的号码、身高及擅长的位置如下表：0-1变量----若变量只能取值0或1,则称其为0-1变量.通常作为逻辑变量,常被用来表示系统是否处于某个特定状态,或决策时是否取某个特定方案.0--1规划的数学模型(2)同时，要求出场阵容满足以下条件：

⑶

如果１号队员和４号队员都上场，则６号队员不能出场⑴

中锋最多只能上场一个⑵

至少有一名后卫问应当选择哪5名队员上场,才能使出场队员平均身高最高?试写出上述问题的数学模型。⑷

２号队员和６号队员必须保留一个不出场。0--1规划的数学模型(3)约束条件:⑶

如果１号队员和４号队员都上场，则６号队员不能出场(1）中锋最多只能上场一个,即⑵至少有一名后卫解:设Xj=1表示第j号队员上场,

Xj=0表示第j号队员不上场

j=1,2,...,8⑷

２号队员和６号队员必须保留一个不出场。(5）篮球比赛恰好5人上场0--1规划的数学模型故该问题的数学模型为:其中cj表示第j号队员的身高(j=1,2,…,8)0--1规划的数学模型(例2)例2.某公司有机会对B1、B2、B3三个项目进行投资。根据预算,前两年每年可投资6(万元),后两年每年可投资7(万元)。三个项目每年所需投资额和纯利润如下表:

问公司应对哪几个项目进行投资,才能使获得的利润最大?试建立这个问题的整数规划模型.解:设0--1规划的数学模型(例2)故数学模型为0--1规划的数学模型(例3)队员的挑选要满足下列条件:例3.某校篮球队准备从以下六名预备队员中选拔三名为正式队员,并使平均的身高尽可能高。这六名预备队员情况如下表所示：⑴

至少补充一名后卫队员;⑵大李或小田中间恰有一名入选;⑶最多补充一名中锋;⑷无论大李或小赵入选,小周就不能入选.试建立这个问题的整数规划模型.0--1规划的数学模型(例3)解:

设j=4,5,...,9约束条件:

⑴至少补充一名后卫队员⑵

大李或小田中间恰有一名入选;(3)最多补充一名中锋⑷无论大李或小赵入选,小周就不能入选0--1规划的数学模型(例3)则数学模型为例6.求解下面的0-1型整数规划问题：0-1规划的解法解：借助隐枚举法，列表如下：0-1规划的解法（2）该问题的最优解:x1=1,x2=0,x3=1；最优值:z*=8×(1,1,1)T×(1,1,0)T×(0,1,1)T8(1,0,1)T×(1,0,0)T×(0,1,0)T

5(0,0,1)T0(0,0,0)T（4）（3）（2）（1）件条束约z值全体组合2.用0-1变量表示含有互相排斥的约束条件例4．某厂拟用运货车或船托运甲乙两种货物,每箱的体积、重量、可获利及托运限制如下表:问:两种货物各托运多少箱,可使获利最大?试建立这个问题的整数规划模型.货物体积重量利润

(每箱立方米)(每箱百斤)(每箱百元)

甲5(7)220

乙4(3)510托运限制24(45)13

用0-1变量表示含有互相排斥的约束条件解：设甲乙两种货物分别托运x1和x2箱目标函数

z=20x1+10x2约束条件：重量限制

2x1+5x2≤13体积限制：当船托运时为7x1+3x2≤45但托运时用汽车或用船的两种方式中只能选择一种故引0-1变量yy=0表示采用车运方式；y=1表示采用船运方式体积限制的约束可用以下条件来代替：当汽车托运时为5x1+4x2≤245x1+4x2≤24+yM7x1+3x2≤45+(1-y)M（其中M是充分大的数）用0-1变量表示含有互相排斥的约束条件

则数学模型为：用0-1变量表示含有互相排斥的约束条件注：若有m个互相排斥的约束条件（≤型）为了保证这m个约束条件只有一个起作用我们引入m个0-1变量yi(i=1,2,...,m)和一个充分大的常数M可用下列m+1个约束条件表示：用0-1变量表示含有互相排斥的约束条件例5.利用0-1变量把下列各题分别表示成一般线性约束条件用0-1变量表示含有互相排斥的约束条件解：设用0-1变量表示含有互相排斥的约束条件§5.指派问题指派问题(或称分配问题)(AssignmentProblem)有n项任务要完成，恰好有n个人可以分别去完成其中每一项,但由于任务性质和各人专长不同,因此各人去完成不同的各种任务的效率(或所费时间)就有差别,则应当如何指派哪个人去完成哪项任务使总效率为最高(或所花时间为最小)?

例1:

有一份说明书,要分别译成英、日、德、俄四种文字（分别称为任务Ｅ，Ｊ，Ｇ，Ｒ），要交甲、乙、丙、丁四人去完成，每人完成一种翻译；因各人专业不同，他们翻译成不同文字所需时间如下表，问应指派哪个人完成哪项任务可使总的花费时间为最小？

指派问题（2）例2.某游泳队有4名运动员A1,A2,A3,A4,他们的50米自由泳、蛙泳、蝶泳、仰泳的成绩如下表所示.现在要将他们组成一个450混合接力队,问应该分配

A1,A2,A3,A4各游什么项目,才能使总成绩最好?指派问题（3）类似有：有n项加工任务，怎么样指派到n台机床上分别完成的问题；有n条航线，怎么样指定N艘船去航行问题....系数矩阵:对每个指派问题都有类似上述表格中的元素

cij>0，由这些元素构成的矩阵为效率矩阵令

则指派问题的数学模型

表示指派第i个人去完成第j项任务

表示不指派第i个人去完成第j项任务

指派问题（4）指派问题是0-1规划的特例，也是运输问题的特例。指派问题的一个可行解可用一个矩阵表示：称之为解矩阵若从系数矩阵（cij）的一行（列）各元素中分别减去该行（列）的最小数，得到新矩阵（bij），则以（bij）为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。利用此性质，可使原系数矩阵变换为含有很多0元素的新系数矩阵，而最优解保持不变。我们称系数矩阵中位于不同行不同列的0元素为独立的0元素。指派问题的最优解的性质：指派问题（5）如下的系数矩阵中存在4个独立的0元素若能在系数矩阵（bij）中能找出n个独立的0元素，则令解矩阵（xij）中对应这n个独立的0元素的元素取1，其余元素取0，将其代入目标函数中得到zb=0，它一定是最小。这就是以B为系数矩阵的指派问题的最优解，也得到原问题的最优解。指派问题（6）1955年库恩（W.W.Kuhn）提出了指派问题的解法。他引用了匈牙利数学家康尼格（D.Konig）一个关于矩阵中0元素的定理：系数矩阵中的独立0元素的最多个数等于能覆盖所有0元素的最少的直线数目。所以称此解法为匈牙利解法。下面我们介绍匈牙利解法的步骤：匈牙利解法第一步：使系数矩阵出现0元素

(A)从系数矩阵的每行元素减去该行的最小元素;(B)再从所得系数矩阵的每列元素中减去该列的最小元素;

由0元素最少的行(或列)开始,圈出一个0元素,用表示,然后划去同行同列的0元素,用表示,这样依次做完各行各列,已划去就不能再圈,第二步：试求最优解如果能得到n个,这就完成了求最优解的过程;第三步：作能覆盖所有0元素的最少数目的直线集合如果圈出的不够n个,则转(3)匈牙利解法

(A)对没有的行打号;(B)在已打号的行中，对

所在列打号;(C)在已打号的列中，对所在行打号;(D)重复(B)(C),直到再也找不到可以打号的行或列为止;(E)对没有打号的行画横线,所有打的列画纵线,这样就得到了覆盖所有零元素的最少直线数目的直线集合.第四步：在没有被直线覆盖的部分中找出最小元素,然后对没画直线的行的各元素都减去这最小元素,

对画直线的列的各元素都加上这最小元素,这样得到新的系数矩阵;若有n个不同行不同列的0元素,则求解过程完成;若没有n个不同行不同列的0元素,转第三步执行.匈牙利解法(举例1)例1解:甲译俄文；乙译日文；丙译英文；丁译德文总的花费时间为28

由于已有4个独立0元素，故最优解为：匈牙利解法(举例2)

例2

求下表所示效率矩阵的指派问题的最小解。解：匈牙利解法(举例2)

最后一个矩阵中，已得到5个独立0元素，则得最优解为：匈牙利解法(举例2)最优方案为：

甲→B

乙→D

丙→E

丁→C

戊→A

或甲→B

乙→C

丙→E

丁→D

戊→A总的耗费时间为32个单位。匈牙利解法(举例2)

解2：

(A)对没有的行打号;(B)在已打号的行中，对

所在列打号;(C)在已打号的列中，对所在行打号;(D)重复(B)(C),直到再也找不到可以打号的行或列为止;(E)对没有打号的行画横线,所有打的列画纵线,这样就得到了覆盖所有零元素的最少直线数目的直线集合.匈牙利解法(举例2)(4)在没有被直线覆盖的部分中找出最小元素,然后,对没画直线的行的各元素都减去这最小元素,对画直线的列的各元素都加上这最小元素,这样得到新的系数矩阵;第3,5行各元素减去2第1列各元素加上2匈牙利解法(举例2)最优方案为：甲→B

乙→D

丙→E丁→D

戊→A

或甲→B

乙→C

丙→E

丁→C

戊→A最后一个矩阵中，已得到5个独立0元素，则得最优解为：总的耗费时间为32个单位。二．极大化的指派问题极大化指派问题的数学模型

需把它化为极小化问题但不能象线性规划问题那样，令目标函数的相反数此时令bij=M-cij

其中M是足够大的常数则系数