第5章整数规划ppt课件

1、1,第五章 整数规划,2,1 整数规划的数学模型,一、整数规划的数学模型,整数规划(Integer Programming 简记IP) 要求一部分或全部决策变量必须取整数的规划问题 2. 松驰问题(Slack Problem) 不考虑整数约束，由余下的目标函数和约束条件构成的规划问题(也称伴随规划) 3. 整数线性规划(ILP) 若松驰问题是一个线性规划问题,3,1 整数规划的数学模型,一、整数规划的数学模型,整数线性规划数学模型的一般形式为,中部分或全部取整数,4,1 整数规划的数学模型,一、整数规划的数学模型,整数线性规划分为： 纯整数LPPure Integer Linear Progr

2、amming 混合整数LPMixed Integer Linear Programming 0-1型整数LPZero-One Integer Linear Programming,5,1 整数规划的数学模型,二、整数规划举例,例1：某厂生产A1和A2两种产品，需要经过B1，B2，B3三道工序加工，单件工时和利润以及各工序每周工时限额见下表，问工厂应如何安排生产，才能使总利润最大,6,1 整数规划的数学模型,二、整数规划举例,解：设工厂每周生产A1产品x1件， A2产品x2件。则该问题的数学模型为,且取整数值,7,1 整数规划的数学模型,二、整数规划举例,例2：见书P130 例1,8,1 整数规

3、划的数学模型,三、整数规划解的特点,1.整数规划问题的可行解集合是它的松驰问题可行解集合的一个 。 2.整数规划问题最优解的目标函数值 松驰问题最优解的目标函数值。 3.对松驰问题最优解中非零分量取整，所得到的解不一定是整数规划问题的最优解，甚至也不一定是整数规划问题的可行解,子集,不优于,9,例1:某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制见表.问每集装箱中两种货物各装多少箱,可使所获利润最大,10,解：设 分别为甲、乙两种货物的托运箱数.则这是一个纯整数规划问题。其数学模型为,1,11,若暂且不考虑 取整数这一条件。则(1)就变为下列线性规划,2,将式(2)

4、称为(1)的松驰问题，解(2)得到最优解,3,但它不满足(1)的整数要求。因此它不是(1)的最优解,12,若取X1=(5,0)T，它不满足 (1) 中的约束条件1。 若取X2=(4,0)T，X2是 (1) 的可行解, 但它却不是(1) 的最优解,因为当X2=(4,0)T 时,Z = 80, 当X3=(4,1)T时,Z=90Z,即松驰问题的最优解通过“舍零取整”得到的X1,X2都不是(1)的最优解。因此通过松驰问题最优解的“舍零取整”的办法 , 一般得不到原整数规划问题的最优解,13,k0 =(0,0),(0,1),(0,2),(1,0),(1, l),(1,2),(2,0),(2,1), (3

5、,0),(3,1),(4,0),(4, l) 将C点“舍零取整”后得到的X1=(5,0)T不在K0中,而X2=(4,0)T在K0中,但不是(1)的最优解,最优解在B点,松驰问题(2)的可行域K如图,则原整数规划(1)的可行域 K0应是K中有限个格点(整数点）的集合。图中“*”为整数点(格点,例2：见书P132 例4,14,由于整数规划问题(1)可行解的个数较少，故可用“穷举法”来求解,即将 K0 中所有整数点的目标函数值都计算出来,然后逐一比较找出最优解,取 =0,1,2,3,4,其组合最多为15个(其中有不可行的点,0,1,2,但对大型问题，这种组合数的个数可能大得惊人! 如在指派问题中，有

6、n项任务指派n个人去完成，不同的指派方案共有n!种。当n=20时，这个数超过21018。如果用穷举法每一个方案都计算一遍，就是用每秒亿次的计算机，也要几十年,15,显然“穷举法”并不是一种普遍有效的方法。因此研究求解整数规划的一般方法是有实际意义的。自20世纪60年代以来，已发展了一些常用的解整数规划的算法，如各种类型的割平面法、分枝定界法、解0-1规划的隐枚举法、分解方法、群论方法、动态规划方法等等。近十年来有人发展了一些近似算法及用计算机模拟法，也取得了较好的效果,16,2 解纯整数规划的割平面法,割平面法在1958年由R.E.Gomory首先提出,一、割平面法的思想 若松驰问题的最优解不

7、满足整数约束，就设法在问题上增加一个约束，把包含这个非整数解的一部分可行域从原来的可行域中割掉，但不割掉任何一个整数可行解，这个新增加的约束条件就称为割平面约束或Gomory约束,17,且为整数,p (3/4,7/4,q (1,1,18,二、割平面法步骤,1. 解松驰问题的最优解； 2. 若X*的所有分量均为整数，则满足整数约束，X*即为整数规划的最优解。若存在X*的某个分量为小数，则选取分数部分最大的分量，构造新的约束条件； 3. 将新的约束条件加入松驰问题中，形成一个新的线性规划，对这个新的线性规划求解； 4. 若新的解满足整数约束，则此解为整数规划的最优解，否则重复第2，3步，直到获得最

8、优解为止,19,三、新约束条件的构造,在松驰问题的最优单纯形表中，m个约束方程可表示为,其中Q为m个基变量的下标集合，K为n-m个非基变量的下标集合,20,三、新约束条件的构造,若 不是整数，其对应的约束方程： 分解 和 成两部分，一部分是不超过该数的最大整数，另一部分是余下的正小数。即,21,三、新约束条件的构造,且为整数,且为整数,构造新的约束条件为,割平面约束,22,四、新增约束条件的性质,性质1：原松驰问题的非整数最优解不满足新增约束条件。 性质2：原松驰问题的整数可行解均满足新增的约束条件，也就是说，整数可行解始终保留在每次形成的线性规划的可行域中,23,下面说明新增约束： 能够“割

9、掉”松驰问题中的非整数可行解,证明：设X*为松驰问题的最优解，将其代入新增约束有： ，（因非基变量取值为0,这与 矛盾，即X*不满足新增约束,注：经验表明若从最优单纯形表上选择具有最大小数部分的非整数分量所在行构造割平面约束，往往可以提高“切割”效果，减少“切割”次数,24,例1：用割平面法求解整数规划,且为整数,解：引入松驰变量x3，x4，将问题化为标准形式，用单纯形法解其松驰问题，得最优单纯形表如下,25,割平面约束为,引入松驰变量x5，得割平面方程,x1,x2的最大分量均为3/4，不妨选取x2，得,26,27,例2：用割平面法求解整数规划,且为整数,解：引入松驰变量x3，x4，x5，将问

10、题化为标准形式，用单纯形法解其松驰问题，得最优单纯形表如下,28,割平面约束为,引入松驰变量x6，得割平面方程,29,30,31,割平面约束为,引入松驰变量x7，得割平面方程,32,33,上表中给出的最优解x=(1,2,4,3,1,0,0)已满足整数约束，因而，原整数规划问题的最优解为： x1=1, x2=2, max z=1,34,35,3 分枝定界法,在20世纪60年代初Land Doig 和 Dakin 等人提出了分枝定界法。由于该方法灵活且便于用计算机求解，所以目前已成为解整数规划的重要方法之一。分枝定界法既可用来解纯整数规划，也可用来解混合整数规划,分枝定界法的主要思路是首先求解整数

11、规划的伴随规划,如果求得的最优解不符合整数条件,则： 增加新约束缩小可行域; 将原整数规划问题分枝分为两个子规划,再解子规划的伴随规划； 通过求解一系列子规划的伴随规划及不断地定界。最后得到原整数规划问题的整数最优解,36,例1：某公司计划建筑两种类型的宿舍。甲种每幢占地0.25103m2, 乙种每幢地0.4103m2。该公司拥有土地3103m2. 计划甲种宿舍不超过8幢，乙种宿舍不超过4幢。甲种宿舍每幢利润为10万元，乙种宿舍利润为每幢20万元。问该公司应计划甲、乙两种类型宿舍各建多少幢时，能使公司获利最大,37,解：设计划甲种宿舍建 幢,乙种宿舍建 幢,则本题数学 模型为,这是一个纯整数规

12、划问题,称为问题 。将(1)中约束条件,的系数全化为整数,改为,1,38,然后去掉整数条件,得到问题 的伴随规划(2), 称之为 问题,2,39,8,4,5.6,4,求解问题 , 得到最优解及最优值,40,1. 计算原问题 目标函数值的初始上界,因为问题 的最优解不满足整数条件,因此 不是 的最优解,又因为 的可行域 问题 的可行域 , 故问题 的最优值不会超过问题 的最优值。即有,因此可令 作为 的初始上界,即,41,2. 计算原问题 目标函数值的初始下界,若能从问题 的约束条件中观察到一个整数可行解，则可将其目标函数值作为问题 目标函数值的初始下界，否则可令初始下界Z=-。给定下界的目的，

13、是希望在求解过程中寻找比当前 更好的原问题的目标函数值,对于本例,很容易得到一个明显的可行解X=(0,0)T,Z=0。问题 的最优目标函数值决不会比它小,故可令 =0,42,3. 增加约束条件将原问题分枝,当问题 的最优解 不满足整数条件时,在 中任选一个 不符合整数条件的变量。如本例选 ，显然问题 的 整数最优解只能是 或 ,而绝不会在5与6之间。 因此当将可行域 切去 部分时,并没有切去 的 整数可行解。可以用分别增加约束条件 及 来达 到在 切去 部分的目的。 切去 后就分 为 及 两部分,即问题 分为问题 及问题 两枝子 规划,43,问题,问题,则问题 的可行域为 见图,44,8,4,

14、5.6,4,K1,K2,5,6,解为,解为,5,4,6,3.75,45,问题 的解 是整数最优解,它当然也是问题 的整数可行解,故 的整数最优解,同时问题 也被查清, 成为“树叶,因为 ,不满足整数条件, 故问题 分别增加约 束条件： 及 。建立相应的伴随规划问题 与,46,问题,问题,它们的可行域分别为,因为 ，问题 无可行解，此问题已是“树叶”，已被查清,47,8,4,B1,K2,6,3,K3,求解问题 , 得到最优解,7.2,3,48,因为 ,不满足整数条件, 故问题 分别增加约 束条件： 及 。建立相应的伴随规划问题 与,49,8,4,B1,B2,6,3,K3,7,K5,K6,解为,7

15、,3,8,2.5,50,当解完一对分枝 后, 得到 因此所有分枝均已查明。故已得到问题 的最优解,或,故该公司应建甲种宿舍7幢、乙种宿舍3幢; 或甲种5幢、乙种4幢时,获利最大，获利为130万元,51,问题,问题,问题,问题,问题,问题,问题,不可行,52,分枝定界法步骤,第1步:将原整数线性规划问题称为问题 。去掉问题 的整数条件,得到伴随规划问题,第2步:求解问题 , 有以下几种可能,l) 没有可行解, 则 也没有可行解, 停止计算,2) 得到 的最优解, 且满足问题 的整数条件, 则 的最优解也是 的最优解, 停止计算,3) 得到不满足问题 的整数条件的 的最优解,记它的目标函数值为 ,

16、 这时需要对问题 (从而对问题 )进行分枝，转下一步,53,第3步:确定初始上下界 与,以 作为上界 ， 观察出问题 的一个整数可行解,将其 目标函数值记为下界 。若观察不到,则可记 = -，转 下一步,第4步: 将问题 分枝,在 的最优解 中,任选一个不符合整数条件的变量,其值为 , 以 表示小于 的最大整数。构造两个约束条件,54,将这两个约束条件分别加到问题 的约束条件集中,得到 的两个分枝:问题 与,对每个分枝问题求解,得到以下几种可能,1) 分枝无可行解该分枝是 “ 树叶,2) 求得该分枝的最优解, 且满足 的整数条件。将该最 优解的目标函数值作为新的下界 , 该分枝也是“树叶,3)

17、 求得该分枝的最优解,且不满足 的整数条件,但其目标函数值不大于当前下界 , 则该分枝是“枯枝”需要剪枝,55,4) 求得不满足 整数条件的该分枝的最优解,且其目标函数值大于当前下界 ,则该分枝需要继续进行分枝,若得到的是前三种情形之一,表明该分枝情况已探明,不需要继续分枝,若求解一对分枝的结果表明这一对分枝都需要继续分枝，则可先对目标函数值大的那个分枝进行计算，且沿着该分枝一直继续进行下去，直到全部探明情况为止。再返过来求解目标函数值较小的那个分枝,56,第5步:修改上、下界,修改下界 ：每求出一次符合整数条件的可行解时, 都要考虑修改下界 , 选择迄今为止最好的整数可行解,相应的目标函数值

18、作下界,2) 修改上界 ：每求解完一对分枝,都要考虑修改上界 上界的值应是迄今为止所有未被分枝的问题的目标函数值 中最大的一个,57,若仍有 ,则说明仍有分枝没查明，需要继续分枝, 将需要进行分枝的问题称为问题B0，回到第4步,58,P138 例6,A(3/2,10/3)z=29/6,B(2,23/9)z=41/9,C(1,7/3)z=10/3,59,P138 例6,C(1,7/3)z=10/3,D(33/14,2)z=61/14,E(3,1)z=4,F(2,2)z=4,60,4 0-1型整数规划,一、0-1型整数规划的概念,0-1型整数规划是整数规划的特殊情形，它的变量xj仅取值0或1，这时

19、xj称为0-1变量（或二进制变量，逻辑变量）。 xj仅取0或1，可表示为： 它和一般的整数规划的约束条件在形式上是一致的,为整数,P130 例2,在实际问题中，如果引入0-1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论,61,二、引入0-1变量的实际问题,1.投资场所的选定相互排斥的计划 例1:某公司拟在市东、西、南三区建立门市部。拟议中有7个位置A1,，A7可供选择。规定: 在东区：由A1,A2,A3三个点中至多选两个； 在西区：由A4,A5两个点中至少选一个； 在南区：由A6,A7两个点中至少选一个。 如选用Ai点，设施投资估计为bi元，每平方米可获利润估计为Ci

20、元，但投资总额不能超过B元，问应选择哪几个点可使年利润最大,62,解：引入0-1变量，令,于是问题的数学模型为,i=1,2,7,63,二、引入0-1变量的实际问题,2.相互排斥的约束条件,或,为了统一在一个问题中，引入0-1变量y，则上述约束条件可改写为,其中M是充分大的数,P142 例7,64,二、引入0-1变量的实际问题,3.固定费用问题,P143 例8,4.工件排序问题,P144 例9(略,65,三、0-1型整数规划的过滤隐枚举法,设0-1型整数规划,解的步骤,1)列出n个分量的2n种组合，算出相应的目标函数值。 (2)X*为任一组合，判断X*是否满足所有约束条件，若满足则转下一步，否则

21、舍弃该组合,66,三、0-1型整数规划的过滤隐枚举法,解的步骤,3)设Z*=CX*，将ZZ*作为过滤条件。 (4)对其它组合，若不满足过滤条件，则舍弃；对满足过滤条件的，看其是否满足所有约束，不满足舍弃。设满足所有约束的组合为X,将Z=CX作为新的过滤条件。 (5)检查所有可能的组合，最终可得最优解,67,例2：求解0-1型整数规划,a) (b) (c) (d,注：为了进一步减少运算量，对于最大化（最小化）问题，常按目标函数中各变量系数从小到大（从大到小）的顺序重新排列各变量，以使最优解可能较早出现,68,例3：求解0-1型整数规划,a) (b) (c,69,四、0-1型整数规划的分枝定界解法

22、,解的步骤,1)目标函数极小化，约束条件为。 (2)目标函数系数非负化。 (3)目标函数中，变量按系数从小到大排列，约束条件中各变量的排列顺序也做相应变化。 (4)令所有变量为零，检查约束条件是否满足，若满足此解即为最优解，否则转下一步,70,四、0-1型整数规划的分枝定界解法,解的步骤,5)按在目标函数中排列顺序（从左到右）依次令各变量分别取“0”或“1”，将问题分为两个子问题，各自检查是否满足约束条件，若满足，则保留所有可行解中目标函数值最小的分枝进行定界，将可行解中目标函数值大的分枝剪去。若不满足，则对目标函数值较小的分枝优先进行下一步分枝。直到所有分枝均检查清楚为止。这时保留下来的分枝

23、即为最优解,71,例4：用分枝定界法求解0-1型整数规划,例5：用分枝定界法求解0-1型整数规划,72,注：当发生下列三种情况之一时，该分枝不再继续往下分，或保留或剪枝 (1)该分枝为可行解，这时应保留所有可行解中目标函数值最小的分枝，将可行解中目标函数值大的分枝剪去。 (2)不管是否为可行解，分枝目标函数值已超过保留下来的可行解的目标函数值的分枝剪去。 (3)当该分枝中某些变量的值已确定的情况下，其余变量不管取什么值都无法满足一个或几个约束时，即该分枝无可行解，实行剪枝,73,5 指派问题,一、指派问题的标准形式及其数学模型,在现实生活中，有各种性质的指派问题，如，有若干项工作需要分配给若干

24、人来完成；有若干项合同需要选择若干个投票者来承包；有若干班级需要安排各教室上课等。 指派问题的标准形式是：有n个和n件事，已知第i做第j件事的费用为cij(i,j=1,2,n)，要求确定人和事之间的一一指派方案，使完成这n件事的总费用最少,74,5 指派问题,一、指派问题的标准形式及其数学模型,一般称矩阵,为指派问题的效率矩阵（coefficient matrix,矩阵C中，第i行中各元素表示第i个人做各事的费用；第j列各元素表示第j事由各人做的费用,75,5 指派问题,一、指派问题的标准形式及其数学模型,令,i,j=1,2,n,指派问题的数学模型为,a) (b) (c) (d,每件事有且只有

25、一个人去做,每个人做且只做一件事,76,5 指派问题,一、指派问题的标准形式及其数学模型,对于问题的每一个可行解，可用解矩阵来表示,矩阵每列元素中有且只有一个 ，以满足约束条件 。 矩阵每行元素中有且只有一个 ，以满足约束条件 。 指派问题有 可行解,1,1,b,c,n,77,5 指派问题,二、指派问题的匈牙利解法,指派问题是0-1规划的特例，也是运输问题的特例，因此可用整数规划或运输问题的解法求解，然而这就如同用单纯形法解运输问题一样是不够合算的，利用指派问题的特点可有更简便的解法匈牙利解法,匈牙利解法的基本原理就是效率矩阵的任一行(或列)减去(或加上)任一常数对原指派问题的最优解不会发生影

26、响,78,5 指派问题,三、匈牙利解法的一般步骤,1)变换系数矩阵 先对各行元素分别减去本行中的最小元素； 再对各列元素分别减去本列中的最小元素； 这样，系数矩阵中每行及每列中至少有一个零元素，同时不出现负元素,2)在变换后的系数矩阵中确定独立零元素 若独立零元素有n个，则已得出最优解；若独立零元素少于n个，则转下一步。 (3)作能覆盖所有零元素的最少直接数目的直线集合,79,5 指派问题,三、匈牙利解法的一般步骤,1)变换系数矩阵 先对各行元素分别减去本行中的最小元素； 再对各列元素分别减去本列中的最小元素； 这样，系数矩阵中每行及每列中至少有一个零元素，同时不出现负元素,2)在变换后的系数矩阵中确定独立零元素 若独立零元素有n个，则已得出最优解；若独立零元素少于n个，则转下一步,3)作能覆盖所有零元素的最少直接数目的直线集合,80,5 指派问题,三、匈牙利解法的一般步骤,4)继续变换系数矩阵 在未被直线覆盖的元素中找出一个最小元素，对未被直线覆盖的元素所在行(或列)中各元素都减去这个最小元素。这样，在未被直线覆盖的元素中必会出现