最优化理论_第3章_整数规划课件.ppt

《最优化理论_第3章_整数规划课件.ppt》由会员分享，可在线阅读，更多相关《最优化理论_第3章_整数规划课件.ppt（76页珍藏版）》请在三一办公上搜索。

1、第3章 整数规划,哈尔滨工程大学 理学院戴运桃Email:,3.1 整数规划,定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。,整数规划的数学模型,若要求所有 xj 的解为整数，称为纯整数规划若要求部分 xj 的解为整数，称为混合整数规划对应没有整数解要求的线性规划称之为松弛问题整数规划的最优解不会优于其松弛问题的最优解,引例,某厂拟用火车装运甲、乙两种货物集装箱，每箱的体积、重量、可获利润以及装运所受限制如下：,问两种货物各

2、装运多少箱，可使获得利润最大？,返回,是不是可通过把不考虑整数要求求得的最优解经过“化整”得到满足整数要求的最优解呢？,容易求得相应的线性规划问题的最优解为 x1=4.8，x2=0，max z=96,现在来分析上述线性规划问题的最优解是否是整数规划问题的最优解因为x1表示的是托运甲种货物的箱数，目前得到的最优解不是整数，所以不合条件的要求。是不是可以把所得的非整数最优解经过“化整”就可得到合于条件的整数最优解呢?如将(x1=4.8，x2=0)凑整为(x1=5，x2=0)，这样就破坏了条件(关于体积的限制)，因而它不是可行解；如将(x1=4.8，x2=0)舍去尾数0.8，变为(x1=4，x2=0

3、)，这当然满足各约束条件，因而是可行解，但不是最优解，因为当x1=4，x2=0,时z=80；而当x1=4，x2=1(这也是可行解)时，z=90。,图中画(+)号的点表示可行的整数解。凑整得到的(5，0)点不在可行域内，而C点又不合于条件。为了满足题中要求，表示目标函数的z的等值线必须向原点平行移动，直到第一次遇到带“+”号B点(x1=4，x2=1)为止。这样，z的等值线就由z=96变到z=90，它们的差值为z=96-90=6，表示利润的降低，这是由于变量的不可分性(装箱)所引起的。,由上例看出，将其相应的线性规划的最优解经过“化整”来解原整数线性规划，虽是最容易想到的，但常常得不到整数线性规划

4、的最优解，甚至根本不是可行解。因此有必要对整数线性规划的解法进行专门研究。,在求解整数线性规划时，如果可行域是有界的，首先容易想到的方法就是穷举所有可行的整数解，即列出图中所有标有“+”的整数点，然后比较它们的目标函数值，从而确定最优解。对于规模较小的问题，变量个数很少，可行解的组合数也较小时，这个方法是可行的，也是有效的。如在例1中，变量只有x1和x2。由条件，x1所能取的整数值为0、1、2、3、4共5个；由条件，x2所能取的整数值为0、1、2共3个。因此所有可能的整数组合(不都是可行的)数是35=15个，穷举法还是勉强可用的。,对于大型问题，可行的整数组合数会很大。例如在指派问题中，将n项

5、任务指派n个人去完成，不同的指派方案共有n!种，当n=10时，可能的指派方案数超过300万；当n=20，超过21018。显然，穷举法是不可取的。,应寻找仅检查可行的整数组合的一部分，就能定出最优的整数解的方法。分支定界解法就是其中之一。分枝定界法可用于解纯整数或混合整数线性规划问题。20世纪60年代初由Land Doig和Dakin等提出，是解整数线性规划的重要方法之一。,分枝定界法,继续求解定界，重复下去，直到得到最优解为止。,基本思想,例 求解问题A min z=-10 x1-20 x2 5x1+8x260 x18 x24 x1，x20 x1，x2整数,例题演示,问题A对应的松弛问题B m

6、in z=-10 x1-20 x2 5x1+8x260 x18 x24 x1，x20,B1 min z=-10 x1-20 x2 5x1+8x260 x18 x24 x1，x20 x15,分枝,B2 min z=-10 x1-20 x2 5x1+8x260 x18 x24 x1，x20 x16,B21 min z=-10 x1-20 x2 5x1+8x260 x18 x24 x1，x20 x16 x23,分枝,B22 min z=-10 x1-20 x2 5x1+8x260 x18 x24 x1，x20 x16 x24,B211 min z=-10 x1-20 x2 5x1+8x260 x18

7、 x24 x1，x20 x16 x23 x17,分枝,B212 min z=-10 x1-20 x2 5x1+8x260 x18 x24 x1，x20 x16 x23 x18,x1 5,x16,问题B的解为:z0=-136 x1=5.6 x2=4,问题B2为:z1=-135x1=6.00 x2=3.75,问题B1为:z1=-130 x1=5.00 x2=4.00,-136=Z*=-130,-136=Z*=0,-135=Z*=-130,问题B21为:z1=-132 x1=7.2 x2=3.00,问题B22为:无可行解,x2 3,x24,问题B211为:z1=-130 x1=7.00 x2=3.0

8、0,问题B212为:z1=-130 x1=8.00 x2=2.50,x1 7,x18,-132=Z*=-130,-130=Z*=-130,分枝定界法一般步骤,问题(B)无可行解，则(A)也无可行解，停止；,0-1型整数规划是整数规划的一种特殊形式，它的变量xj仅取值0或1。这种只能取0或1的变量称为0-1变量或二进制变量。,3.2 0-1整数规划,例：某公司拟在市东、西、南三区建立门市部。拟议中有7个位置Ai（i=1，2,7）可供选择规定 在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5，两个点中至少选一个；在南区，由A6，A7，两个点中至少选一个。如果选择Ai点，设备投资估

9、计为bi元，每年可获利润ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？,则该问题的数学模型为：,在整数规划中，如果变量xi仅取0或1，这时变量xi称为01变量，这时的整数规划称为01型整数规划。,28,在本章开始的例1中，关于运货的体积限制为 5x1+4x224(1)今设运货有车运和船运两种方式，上面的条件系用车运时的限制条件，如用船运时关于体积的限制条件为 7x1+3x245(2)这两个条件是互相排斥的。为了统一在一个问题中，引入0-1变量y，令,含有互斥约束条件的问题,Max z20 x1+10 x2(1)5x1+4x224(2)2x1+5x213(3)x1,x20(4

10、)x1,x2为整数(5),29,于是，(1)式和(2)式可由下述条件(3)式和(4)式来代替：5x1+4x224+yM(3)7x1+3x245+(1 y)M(4)其中M是充分大的数。,可以验证:当y=0时，(3)式就是(1)式，而(4)式自然成立，因而是多余的。当y=1时，(4)式就是(2)式，而(3)式是多余的。,引入的变量y不必出现在目标函数内，即认为在目标函数内y的系数为0。,30,如果有m个互相排斥的约束条件(型)：i1x1+i2x2+inxnbi，i=1，2，,m 为了保证这m个约束条件只有一个起作用，我们引入m个0-1变量yi(i=1,2,，m)和一个充分大的常数M，且下面这一组m

11、+1个约束条件 i1x+i2x2+inxnbi+yiM i=1,2,，m(5)y1+y2+ym=m 1(6)就合乎上述的要求。这是因为，由于(6)式，m个yi中只有一个能取0值，设yi*=0，代入(5)式，就只有i=i*这个约束条件起作用，而别的式子都是多余的。,对于0-1型整数规划，一般采用隐枚举法，而不必采用完全枚举法。包括:(1)只要发现某个变量组合不满足其中一个约束条件时，就不必再去检验其他约束条件是否可行。(2)若已发现一个可行解，则可根据它的目标函数值产生一个过滤条件，对于目标函数值比它差的变量组合就不必再去检验它的可行性；在以后的求解中每当发现更好的可行解就替换原来的过滤条件。,

12、0-1型整数规划的解法,例:用隐枚举法求解下列01型整数规划,该条件称为过滤条件,解：,先通过试探找一个可行解，,(0，0，0),(0，0，1),(0，1，0),(1，0，0),(0，1，1),(1，0，1),(1，1，0),(1，1，1),0,5,-1,1,0,1,5,-2,3,1,1,1,0,5,3,1,5,8,0,2,1,1,8,1,6,2,6,(0，0，0),(0，0，1),(0，1，0),(1，0，0),(0，1，1),(1，0，1),(1，1，0),(1，1，1),0,5,-1,1,0,1,5,-2,3,3,8,0,2,1,1,8,1,6,0,0,0,0,0,(1，0，1),(1，

13、1，1),(0，1，1),(1，0，0),(0，1，1),(1，1，0),(0，0，0),(0，1，0),8,6,5,3,3,1,0,-2,0,2,1,1,8,36,注意：一般常重新排列xi的顺序使目标函数中xi的系数是递增(不减)的，在上例中，改写 z=3x1 2x2+5x3=2x2+3x1+5x3 因为 2，3，5是递增的序，变量(x2，x1，x3)也按下述顺序取值：(0，0，0)，(0，0，1)，(0，1，0)，(0，1，1)，这样，最优解容易比较早的发现。再结合过滤条件的改进，更可使计算简化。,37,z=3x1 2x2+5x3=2x2+3x1+5x3,指派问题,指派问题的标准形式及其数

14、学模型匈牙利解法求解指派问题 一般的指派问题,有n项任务，恰好n个人承担，第i人完成第j 项任务的花费(时间或费用等)为cij，要求确定人和事之间的一一对应的指派方案，使总花费最省？,指派问题的标准形式及其数学模型,例4 有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需时间如下表。问应指派何人去完成何工作，使所需总时间最少？,指派问题的标准形式及其数学模型,指派问题的系数矩阵如下：,Cij的含义可以不同，如费用、成本、时间等。,为建立标准指派问题的数学模型，引入nn个0-1变量：,指派问题的数学模型可写成

15、如下形式：,若派第i人做第j事0 若不派第i人做第j事（ij=1，2,，n）,第j项工作由一个人做,第i人做一项工作,指派问题的每个可行解，可用矩阵表示如下：,矩阵X中，每行各元素中只有1个元素为1,其余各元素等0；每列各元素中也只有1个元素为1,其余各元素等0。指派问题有n！个可行解。,匈牙利法解题步骤,1955年，库恩利用匈牙利数学家康尼格的关于矩阵中独立零元素的定理，提出了解指派问题的一种算法，称为匈牙利解法。,标准指派问题是一种特殊的整数规划问题，又是特殊的0-1规划问题。,匈牙利解法的关键是利用了指派问题最优解的如下性质：若从指派问题的系数矩阵C的某行（或某列）各元素分别减去该行（或

16、列）的最小元素，得到一个新的矩阵C，则以C和C 为系数矩阵的两个指派问题有相同的最优解。（系数矩阵的变化并不影响数学模型的约束方程组，而只是目标函数值减少了常数k，所以最优解不变）,匈牙利法,-2-4-9-7,若某行(列)已有0元素，那就不必再减了。例1的计算为：,1.使系数矩阵各行、各列出现零元素 作法：系数矩阵各行元素减去所在行的最小元素，再从所得矩阵的各列减去所在列最小元素。(因一行中xij 取值一个1，其余为0，cij 同时减去一常数不影响xij取值)。,匈牙利法解题步骤如下：,-4-2,这就保证每行每列至少有一个0元素，同时不出现负元素。,2.试求最优解。,作法：由独立0元素的行（列

17、）开始，独立0元素处画 标记，在有 的行列中划去其它0元素；再在剩余的0元素中重复此做法，直至不能标记 为止。,（1）当遇到在所有的行和列中，0元素都不止一个时（存在0元素的闭回路），可任选其中一个0元素加圈，同时划去同行和同列中其他0元素。（2）如能找出n个位于不同行不同列的零元素，令对应的xij=1，其余xij=0，得最优解，结束；否则，看下面的例题转第3步。,例 求表中所示效率矩阵的指派问题的最小解。,经行运算即可得每行每列都有0元素的系数矩阵。,再按上述步骤运算，得到：,3.作能覆盖所有0元素的最少直线数的直线集合(1)对没有 的行打 号；(2)对已打 号的行中所有0元素的所在列打 号

18、；(3)再对打有 号的列中 0 元素的所在行打 号；(4)重复(2),(3)直到得不出新的打 号的行(列)为止；(5)对没有打 号的行画一横线，对打 号的列画一 纵线，这就得到覆盖所有0元素的最少直线数,4.未被直线覆盖的最小元素为cij0,在打 号行中各元素都减去cij0,打 号列中的各元素都加上cij0。,Cij=2,解为,5.返回步骤2，重复上述步骤。,一般的指派问题 在实际应用中，常会遇到各种非标准形式的指派问题。通常的处理方法是先将它们转化为标准形式，然后用匈牙利解法求解。最大化指派问题 设最大化指派问题系数矩阵C中最大元素为m。令矩阵B=(bij)=(m-cij),则以B为系数矩阵

19、的最小化指派问题和以C为系数矩阵的原最大化指派问题有相同的最优解。,人数和事数不等的指派问题 若人少事多，则添上一些虚拟的“人”。这些虚拟的人作各事的费用系数可取0，理解为这些费用实际上不会发生。若人多事少，则添上一些虚拟的“事”。这些虚拟的事被各人做的费用系数同样也取0。一个人可做几件事的指派问题 若某个人可做几件事，则可将该人看做相同的几个人来接受指派。这几个人作同一件事的费用系数当然都一样。某事一定不能由某人作的指派问题 若某事一定不能由某个人做，则可将相应的费用系数取做足够大的数M。,例：某大型工程有五个工程项目，决定向社会公开招标，建设公司A1，A2，A3参加招标承建，根据实际情况，

20、可允许每家建设公司承建一项或二项工程。求使总费用最少的指派方案。,上面的系数矩阵有6行5列，为了使“人”和“事”的数目相同，引入一件虚拟的事B6，使之成为标准指派问题的系数矩阵：,解：由于每家建筑公司最多可以承建两项，因此可把每家建筑公司看成两家建筑公司，其系数矩阵为,然后，用匈牙利解法求解。可得费用最省为4+7+9+8+7=35（百万元）,1.用图解法和单纯形法求解线性规划问题,作业：,2.用单纯形法求解线性规划问题,3.求解整数规划问题 max z=3x1+2x2 2x1+3x214 2x1+x29 x1，x20 x1，x2整数,4.设有A、B、C、D四人去完成甲、乙、丙、丁四项任务，不同

21、的人完成不同的任务时间不同，资料如下，求总时间最小的分配方案。,ABCD,甲 乙 丙 丁,5.设有A、B、C、D四人去完成甲、乙、丙、丁四项任务，不同的人完成不同的任务赢得不同，资料如下，求总赢得最大的分配方案。,ABCD,甲 乙 丙 丁,6.设有A、B、C、D、E五人去完成甲、乙、丙、丁四项任务，每人完成各项工作如表所示。规定每项工作只能有一个人去完成，每人最多承担一项工作，又假定D因某种原因决定不承担丁项目，问应该如何分配，才能使4项工作总得花费时间最少？,A B C D E,甲 乙 丙 丁,例 求解整数规划问题A max z=3x1+2x2 2x1+3x2 70 2x1+x270 x1，

22、x20 x1，x2整数,解：先不考虑条件，即解相应的线性规划B,(见图，得最优解x1=4.81，x2=1.82，z0=356,可见它不符合整数条件。这时z0是问题A的最优目标函数值z*的上界，记作z0=。而在x1=0，x2=0时，显然是问题A的一个整数可行解，这时z=0，是z*的一个下界，记作=0，即0z*356。,分枝,因为 当前均为非整数，故不满足整数要求，任选一个进行分枝。设选 进行分枝，把可行集分成2个子集：因为4与5之间无整数，故这两个子集内的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划求解如下：,问题B1为:Max z=40 x1+90 x2 9x1+7x256

23、 7x1+20 x2 70 x1 4 x1,x20,问题B2为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 5 x1,x2 0,68,x14，x15,B1:z1=349 x1=4.00 x2=2.10,B2:z2=341 x1=5.00 x2=1.57,69,显然，仍没有得到全部变量是整数的解。因z1z2，故将 改为349，那么必存在最优整数解，得到z*，并且 0z*349继续对问题B1和B2进行分解。因z1z2，故先分解B1为两支。增加条件x22，称为问题B11；增加条件x23，称为问题B21。相当于在图中再去掉x22与x23之间的区域，进行第二次

24、迭代。,问题B11为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 4 x2 2 x1,x20,问题B12为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 4 x2 3 x1 0,z11=340 x1=4.00 x2=2.00,z12=327x1=1.42x2=3.00,对问题B1再进行分枝得问题B11和B12，它们的最优解为:,再定界：，并将B12剪枝。,340z*349,71,继续对问题B2进行分解,对问题B2再进行分枝得问题B21和B22，它们的最优解为:,无可行解。,将 剪枝，于是可以断定原问题的最优解

25、为：,z0=356 x1=4.81 x2=1.82,x1 4,x15,问题B为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x270 x1,x20,问题B11为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 4 x2 2 x1,x20,问题B12为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 4 x2 3 x1 0,问题B2为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 5 x1,x2 0,问题B1为:Max z=40 x1+90 x2 9

26、x1+7x256 7x1+20 x2 70 x1 4 x1,x20,z1=349x1=4.00 x2=2.10,z2=341x1=5.00 x2=1.57,z11=340 x1=4.00 x2=2.00,z12=327x1=1.42x2=3.00,问题B11为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 5 x2 1 x20,问题B12为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 5 x2 2,z21=308x1=5.44x2=1.00,无可行解,0=Z*=349,340=Z*=341,0=Z*=356,课堂作业：,2.某商业公司计划开5家新商店，为了尽早建成营业，决定由建筑公司A1、A2、A3来承建。根据实际情况，可以允许每家建筑公司承建一家或两家商店，已知每家建筑公司的建造费用报价如下表所示。问如何指派建筑任务，才能使总费用最少？,人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。,