《管理运筹学》03-整数规划.ppt

《《管理运筹学》03-整数规划.ppt》由会员分享，可在线阅读，更多相关《《管理运筹学》03-整数规划.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第 3 章章Integer ProgrammingI P整整 数数 规规 划划3.1 3.1 整数整数规划划问题及其建模及其建模3.2 3.2 分支定界法分支定界法3.3 3.3 割平面法割平面法3.4 0-13.4 0-1型整数型整数线性性规划的解法划的解法3.5 3.5 指派指派问题3.6 3.6 整数整数规划划应用用第3章 整数规划2整数整数规划划：变量取整数的线性规划；纯整数整数规划划：所有变量都取整数的线性规划；混合整数混合整数规划：划：部分变量取整数的线性规划；0-10-1规划：划：所有变量都取0、1两个值的规划；0-10-1混合混合规划：划：部分变量取0、1两个值的规划。例3-

2、1背包问题 4线性规划最优解为:x1=0，x2=0，x3=2.5而整数规划的最优解是 x1=1，x2=0，x3=2maxmaxz=z=17x17x1 1+72x+72x2 2+35x+35x3 3s.t.s.t.10 x10 x1 1+42x+42x2 2+20 x+20 x3 35050 x x1 1,x x2 2,x x3 30 0 x x1 1,x x2 2,x x3 3为整数为整数例3-2厂址选择问题在N个地点中选r个（Nr）建厂，在第i个地点建厂（i=1，2，N）所需投资为Ii万元，占地Li亩，建成以后的生产能力为Pi万吨。现在有总投资I万元，土地L亩，应如何选择厂址，使建成后总生产

3、能力最大。设 5整数规划模型为:0-10-1规划规划例3-3 考虑固定成本的最小生产费用问题 在最小成本问题中，设第j种设备的固定成本为 ，运行的变动成本为 ，则生产成本与设备运行时间的关系为：6混合混合0-10-1规划规划设第j种设备运行每小时可以生产第i种产品 件，而第i种产品定货为 件。要满足定货同时使设备运行的总成本最小的问题为：7线性规划整数规划X*=（13/5，19/5）Z*=89/5=17.8X*=（5，3）Z*=17基本思想分支（Branch）定界（Bound）第3章 整数规划8x xr rIIr rx xr r Ir+1分支（Branch）这两个子问题的可行域都是原线性规划问

4、题可行域的子集，这两个子问题的最优解的目标函数值都不会比原线性规划问题的最优解的目标函数值更小。如果这两个问题的最优解仍不是整数解，则继续选择一个非整数的变量，继续将这个子问题分解为两个更下一级的子问题。这个过程称为“分枝（Branch）”。定界（Bound）如果某一个子问题的最优解是整数解，则它的目标函数值可作为整数规划最优目标函数值的上界。如果某一个子问题的解还不是整数解，但这个非整数解的目标函数值已经超过这个上界，那么这个子问题不必再进行分枝。如果在分枝过程中得到新的整数解且该整数解的目标函数值小于已记录的上界，则用较小的整数解的目标函数值代替原来的上界。上界的值越小，就可以避免更多不必

5、要的分枝。确定整数解目标函数值上界并不断更新上界，并且不断“剪除”目标函数值超过上界的分枝的过程，称为定界（Bound）。第3章 整数规划9例例3-43-4 用分枝定界法求解以下整数规划先求得相应的线性规划的最优解，为第3章 整数规划1011Sub-6无可行解原问题原问题Sub-2Sub-1Sub-3Sub-4Sub-5Sub-7Sub-9Sub-8Sub-10无可行解x22x23x15x15x21x22x14x16x20 x21图3-3.探索过程示意图13.3.1 3.3.1 3.3.1 3.3.1 割平面法基本思想割平面法基本思想割平面法基本思想割平面法基本思想第3章 整数规划12首先放弃

6、变量的整数要求，求得线性规划的最优解。首先放弃变量的整数要求，求得线性规划的最优解。如果最优解恰是一个整数解，则线性规划的最优解就是相如果最优解恰是一个整数解，则线性规划的最优解就是相应的整数规划的最优解。应的整数规划的最优解。如果线性规划的最优解不是整数解，则要构造一个新的约如果线性规划的最优解不是整数解，则要构造一个新的约束，对线性规划问题的可行域进行切割，切除已经得到的束，对线性规划问题的可行域进行切割，切除已经得到的线性规划的最优解，但保留原可行域中所有的整数解，求线性规划的最优解，但保留原可行域中所有的整数解，求解新的线性规划问题解新的线性规划问题如果最优解仍不是整数解，再增加附加的

7、约束将其切除，如果最优解仍不是整数解，再增加附加的约束将其切除，但仍保持最初可行域中所有的整数解，如此一直进行，直但仍保持最初可行域中所有的整数解，如此一直进行，直至得到一个整数的最优解为止。至得到一个整数的最优解为止。3.3.1 3.3.1 3.3.1 3.3.1 割平面法基本思想割平面法基本思想割平面法基本思想割平面法基本思想第3章 整数规划13设放弃变量整数要求得到的线性规划的最优单纯形表如下：设放弃变量整数要求得到的线性规划的最优单纯形表如下：设其中基变量设其中基变量Xr的值的值br不是整数，以不是整数，以I表示整数，以表示整数，以 F表表示正的真分数，令示正的真分数，令yrj=Irj

8、+Frj (0 Frj 1)b b r=Ir r+Fr r (0 Fi i 1)将上面两式代入将上面两式代入约束约束r中，得中，得第6章 整数规划14改写成改写成因此对于整数可行解，约束（因此对于整数可行解，约束（3-2）可以写成更严格的不等式）可以写成更严格的不等式这就是源于第这就是源于第r r行的行的割平面割平面割平面割平面。线性规划的任何整数可行解都满足这个约束；线性规划的任何整数可行解都满足这个约束；未切割掉未切割掉任何一个整数解。任何一个整数解。线性规划的非整数最优解不满足这个约束。线性规划的非整数最优解不满足这个约束。切割掉了非切割掉了非整的整的LP解解X；第3章 整数规划15 2

9、 若若Xk的分量全的分量全为为整数整数，则，则Xk即为原问题的最优解，停止计算即为原问题的最优解，停止计算；否则根据否则根据Xk的一个非整分量所在单纯形表的那一行，譬如第的一个非整分量所在单纯形表的那一行，譬如第 r 行，行，构造源于第构造源于第 i行行的的割平面，割平面，割平面，割平面，给它引入一个弛变量给它引入一个弛变量 x xn+k+1，得得 Frj x xj+x xn+k+1=-F-Fr rj=m+1 -3 把把这这个新个新约约束添到最束添到最优单纯优单纯形表中，并增加一列形表中，并增加一列(即即 x xn+k+1列列)，用对偶单纯形法继续迭代，求得一个新解，用对偶单纯形法继续迭代，求

10、得一个新解Xk+1，令令k:=k+1，返，返2。3.3.2 3.3.2 割平面法基本步骤割平面法基本步骤割平面法基本步骤割平面法基本步骤 1 用用单纯单纯形法求解形法求解IP的伴随的伴随LP问题问题，得到其解得到其解X0，令，令k=0；n第6章 整数规划16 min z=3x1+4x23x1+x24x1+2x24 x1,x20 x1,x2 为整数s.t.例例3-53-5 试用割平面法求解以下整数规划：试用割平面法求解以下整数规划：解解 求解线性规划得最优单纯形表求解线性规划得最优单纯形表选择一个非整数的基变量，例如选择一个非整数的基变量，例如 x x2 2=8/5=8/5，构造约束条件，构造约

11、束条件(3-4(3-4）b2=8/5=1+3/5，I2=1，F2=3/5 y23=1/5=0+1/5，I23=0，F23=1/5 y24=-3/5=-1+2/5，I24=-1，F24=2/5附加的约束条件 为 3/5-（1/5x3+2/5x4）0即1/5x3+2/5x43/5将这个约束加到线性规划的最优单纯形表中，并增加一个松弛变量x5,得下表得下表第3章 整数规划17第3章 整数规划18用对偶单纯形法，用对偶单纯形法，x5x5离基，离基，x3x3进基进基已获得整数的最优解已获得整数的最优解：X*=（2，1）Z*=10为了得到切割约束1/5x3+2/5x43/5在（x1,x2）平面中的表达式，

12、将其中的松弛变量x3，x4用x1，x2表示 x3=3x1+x2-4，x4=x1+2x2-4代入切割约束，得到 x1+x23这个切割过程的图解如下图第3章 整数规划19整数规划最优解0123451234切割直线线性规划最优解 隐枚举法（Implicit Eumeration）例例3-6 3-6 用隐枚举法求解下列问题 可行解：X=(1，0，0)，Z=3 增加过滤条件（filtering constraint）第3章 整数规划20第3章 整数规划21按价值系数从小到大排列max z=-2x2+3x1+5x3 -2x2+3x1+5x33 2x2+x1-x32 4x2+x1+x34 x2+x1 3 4

13、x1+x36 第3章 整数规划22点条件满足条件？是（T）否（F）Z（0 0 0）0F（0 0 1）5-1101T5第3章 整数规划23点条件满足条件？是（T）否（F）Z（0 1 0）3F（0 1 1）80215T8-2x-2x-2x-2x2 2 2 2+3x+3x+3x+3x1 1 1 1+5x+5x+5x+5x3 3 3 38 8 8 8 点条件满足条件？是（T）否（F）Z（1 0 0）-2F（1 0 1）3F（1 1 0）1F（1 1 1）6F指派指派问题或分派或分派问题（assignment problemassignment problem）：）：需完成n项任务，恰好有n个人可承担这

14、些任务。各人完成任务的效率(或所费时间)不同。应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或所需总时间最小)。例例3-5 3-5 甲、乙、丙、丁四人配送A,B,C,D四种货物,所需时间如下表所示。若一种货物只交一人送货，则应指派何人配送何种货物,能使总的时间最少？第3章 整数规划24工工件件工人工人ABCD甲149415乙117910丙132105丁1791513效率矩阵设xij=1表示第 i人送j货，否则xij=0 上述问题的模型为：第3章 整数规划25一般指派问题的模型指派指派问题的求解方法的求解方法匈牙利法匈牙利法性性质3-13-1.若从系数矩阵(cij)的一行(列)各元素中

15、分别减去该行(列)的最小元素，得到新矩阵(bij)，那么以(bij)为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。性性质3-23-2.若一个方阵的一部分元素为0，另一部分元素不为0，则覆盖方阵内所有0元素的最少直线数恰好等于独立0元素（位于不同行，不同列的0元素）的最多个数。第3章 整数规划26例3-7：匈牙利法的步骤一、系数矩一、系数矩阵经变换，在各行各列中都出，在各行各列中都出现0 0元素。元素。二、二、寻找独立找独立0 0元素元素最优值为：Z*=11+9+4+5=29第3章 整数规划27甲甲C C，乙乙A A，丙丙D D，丁丁B B例3-5：先减列元素独立0元素的个数为3，小于矩

16、阵的阶数。第3章 整数规划28三、找出找出能覆盖非最能覆盖非最优阵中所有中所有0 0元的元的最少直最少直线集合集合第6章 整数规划29(1)对没有对没有 元的行打元的行打号；号；0(2)对打对打号的行上所有号的行上所有 元所在的列打元所在的列打号；号；0(3)对打对打号的列上所有号的列上所有 元所在的行打元所在的行打号；号；0 (4)重复重复(2)、(3)步骤，直到找不出新的打步骤，直到找不出新的打 号的行、列为止；号的行、列为止；(5)对没有打对没有打号的行画横线，对所有打号的行画横线，对所有打号号 的列画竖线，这就是能覆盖所有的列画竖线，这就是能覆盖所有0元的最少元的最少 直线的集合。直线

17、的集合。三、用最少的直三、用最少的直线数覆盖矩数覆盖矩阵中的所有中的所有0 0元素元素第3章 整数规划30四、增加矩四、增加矩阵中的中的0 0元素元素 在没有被直线覆盖的部分中找出最小元素。然后在打行各元素中都减去这最小元素，而在打列的各元素都加上这最小元素。若得到n个独立的0元素，则已得最优解，否则回到第三步重复进行。第3章 整数规划31最优解可令可令 b bijij=M-c=M-cijij 。其中。其中M M是足够大的常数是足够大的常数(如选如选（c cijij）中中最大元素为最大元素为M M即可即可)，这时系数矩阵可变换为，这时系数矩阵可变换为B=(bB=(bijij)第3章 整数规划3

18、2目标函数经变换后，即解目标函数经变换后，即解所得所得(b(bijij)最小解即为原问题最小解即为原问题(c(cijij)的最大解。的最大解。例例3-83-8某航空公司是一家经营小型飞机、短途航线的运输企业。管理层准备拓展经营领域，面临的问题是：是采购更多的小型飞机来开辟一些新的短途航，还是开始通过为一些跨地区航线购买大型飞机来进军全国市场，或者两种方法同时进行，已知采购成本、年利润、最多购买的数量限制如下表。并且可用资金为1亿元，如何进行决策，能使年利润达到最大？第3章 整数规划33小小飞飞机机大大飞飞机机每个每个飞飞机年利机年利润润100万元万元500万元万元每个每个飞飞机采机采购购成本成

19、本500万元万元5000万元万元最多采最多采购购数量数量2无限制无限制x1x2第3章 整数规划34整数规划模型为：整数规划模型为：例例3-9 3-9 某速递公司的线路选择问题。公司提供快递服务，所有快件两天内都能送到。快件在晚上到达各收集中心，并于第二天早上装上送往该区域地区的几辆汽车。因为快递行业竞争激烈，为了减少平均送货时间，必须将各快件根据目的地的地理位置加以分类，并分装到不同的汽车上。假设每天有三辆汽车，汽车可行的路线有10条，如下表所示。表中的各列的数字表示送达的顺序，最后一行是各方案的汽车运行时间（小时），现假设有9个不同地点的快件需要送出，试求出总运行时间最短的方案。第3章 整数规划35第3章 整数规划36地点可行路线12345678910A111B21222C3333D211E223F12G3123H131I342时间6475465376该问题可视为0-1规划问题。设 表示第i个方案是否被选择（0表示不选择，1表示选择）第3章 整数规划37