第六章-整数规划课件.ppt

1、2/4/202312/4/20232 解解：设设托托运运甲甲 x 箱箱，乙乙x2箱箱。建建立立整整数数规规划划模模型型为为：max Z=20 x1+10 x2 5x1+4x2 24 2x1+5x2 13 x1,x2 0 0 x1,x2是是整整数数 2/4/202332/4/20234一、概念一、概念 对决策变量的取值有整数限制的规划问题，称为整数对决策变量的取值有整数限制的规划问题，称为整数规划。规划。二、整数规划的分类二、整数规划的分类1、线性整数规划与非线性整数规划、线性整数规划与非线性整数规划2、纯整数规划与混合整数规划、纯整数规划与混合整数规划3、0-1型整数线性规划：决策变量只能取值

2、型整数线性规划：决策变量只能取值0或或1的整数线性规的整数线性规划。划。三、线性整数规划的模型三、线性整数规划的模型 且部分或全部为整数或 n)1.2(j 0)2.1()min(max11jnjijijnjjjxmibxaxcZZ2/4/20235四、整数线性规划与一般线性规划的关系四、整数线性规划与一般线性规划的关系1、对整数线性规划的整数约束的放松，便得到一般的、对整数线性规划的整数约束的放松，便得到一般的线性规划，反之，对一般线性规划增加变量取整的要线性规划，反之，对一般线性规划增加变量取整的要求，则便变成整数线性规划。因此，整数线性规划的求，则便变成整数线性规划。因此，整数线性规划的约

3、束比一般线性规划的约束更紧。约束比一般线性规划的约束更紧。2、整数线性规划的可行域是一般线性规划问题可行域的、整数线性规划的可行域是一般线性规划问题可行域的子集。子集。3、整数线性规划问题的目标函数值以一般线性规划问题、整数线性规划问题的目标函数值以一般线性规划问题目标函数值为界，即整数线性规划问题的最优值，不目标函数值为界，即整数线性规划问题的最优值，不可能优于一般线性规划问题的最优值。可能优于一般线性规划问题的最优值。2/4/20236 例例6.2 工厂工厂A1和和A2生产某种物资。由于该种物资供不应求，生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有故需要再建一家

4、工厂。相应的建厂方案有A3和和A4两个。这种物资两个。这种物资的需求地有的需求地有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费各厂至各需求地的单位物资运费cij，见下表：，见下表：B1B2B3B4年生产能力A12934400A28357600A37612200A44525200年需求量350400300150工厂工厂A3或或A4开工后，每年的生产费用估计分别为开工后，每年的生产费用估计分别为1200万或万或1500万万元。现要决定应该建设工厂元。现要决定应该建设工厂A3还是还是A4，才能使今后每年的总费用，才能使

5、今后每年的总费用最少。最少。2/4/20237l解：这是一个物资运输问题，特点是事先不能解：这是一个物资运输问题，特点是事先不能确定应该建确定应该建A3还是还是A4中哪一个，因而不知道新中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入厂投产后的实际生产物资。为此，引入0-1变量：变量：)2,1(01 iyi若不建工厂若不建工厂若建工厂若建工厂再设再设xij为由为由Ai运往运往Bj的物资数量，单位为千吨；的物资数量，单位为千吨；z表示总费用，表示总费用，单位万元。单位万元。则该规划问题的数学模型可以表示为：则该规划问题的数学模型可以表示为：2/4/20238)2,1(1,0)4,3,2,

6、1,(01200200600400150300400350.15001200min21244434241134333231242322211413121144342414433323134232221241312111414121iyjixyyyxxxxyxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsyyxcziijijijij混合整数规划问题混合整数规划问题2/4/20239例例6.3 现有资金总额为现有资金总额为B。可供选择的投资项目有。可供选择的投资项目有n个，项目个，项目j所需投资额和预期收益分别为所需投资额和预期收益分别为aj和和cj（j1,2,.,n），此外由于种种原

7、因，有三个附加条件：），此外由于种种原因，有三个附加条件：若选择项目若选择项目1，就必须同时选择项目，就必须同时选择项目2。反之不。反之不一定一定 项目项目3和和4中至少选择一个；中至少选择一个；项目项目5,6,7中恰好选择中恰好选择2个。个。应该怎样选择投资项目，才能使总预期收益最大。应该怎样选择投资项目，才能使总预期收益最大。2/4/202310解：对每个投资项目都有被选择和不被选择两解：对每个投资项目都有被选择和不被选择两种可能，因此分别用种可能，因此分别用0和和1表示，令表示，令xj表示第表示第j个项目的个项目的决策选择决策选择，记为：，记为：),.,2,1(01njjjxj 不投资不

8、投资对项目对项目投资投资对项目对项目投资问题可以表示为：投资问题可以表示为：）（或或者者nxxxxxxxxBxatsxczjnjjjnjjj,2,1j1021.max7654312112/4/202311l例例6.4试引入试引入01变量将下题分别表达为一般线性约束条件。变量将下题分别表达为一般线性约束条件。l【解】设【解】设M为充分大的正数，引入为充分大的正数，引入01变量。由于变量。由于3个约束只个约束只有有1个起作用，则其一般线性约束条件为：个起作用，则其一般线性约束条件为：3,2,11,02204210646321321221121iyyyyMyxxMyxxMyxxi621 xx1064

9、21 xx204221 xx或或2/4/202312l也可表示为：也可表示为：3,2,11,01)1(2042)1(1064)1(6321321221121iyyyyMyxxMyxxMyxxi2/4/202313例例6.56.5试引入试引入0 01 1变量将下列各题分别表达为一般线变量将下列各题分别表达为一般线性约束条件：性约束条件：（1 1）若）若x x1 166，则，则x x2 211；否则；否则x x2 21010。（2 2）取值）取值1 1，3 3，5 5，7 7，9 9。【解】（【解】（1）引入）引入01变量，因两组约束只有一组起作变量，因两组约束只有一组起作用，则其一般线性约束条件

10、为：用，则其一般线性约束条件为：61x10)1(101)1(662211，yMyxyMxMyxyMx2/4/202314（2 2）引入01变量，因右端常数是5个值中的1个，其一般线性约束条件为：61x5,4,3,2,11,01975354321543211jyyyyyyyyyyyxj，2/4/202315l一、一、“公理公理”1、对一个整数线性规划问题，如果不考虑变量、对一个整数线性规划问题，如果不考虑变量取整的要求，由此求得的整数最优解取整的要求，由此求得的整数最优解X，也一，也一定是整数线性规划问题的最优解。定是整数线性规划问题的最优解。2、对于一个非整数线性规划问题，如果不考虑、对于一个

11、非整数线性规划问题，如果不考虑变量取整的要求，由此求得的非整数最优解，变量取整的要求，由此求得的非整数最优解，则一定可以断定整数线性规划问题的最优解则一定可以断定整数线性规划问题的最优解不会好于非整数最优解。不会好于非整数最优解。3、在求解的过程中最先出现的整数解，不会好、在求解的过程中最先出现的整数解，不会好于最优整数解。于最优整数解。2/4/202316l二、分枝定界的含义二、分枝定界的含义 1、分枝的含义。、分枝的含义。按按“公理公理”的要求，对一般线性规的要求，对一般线性规划的可行域进行分解。划的可行域进行分解。2、定界的含义、定界的含义 通过分枝不断调整整数最优解的上通过分枝不断调整

12、整数最优解的上下界。下界。2/4/202317l三、分枝定界法的解题思路三、分枝定界法的解题思路1、对于给定的整数线性规划问题，先不考虑变、对于给定的整数线性规划问题，先不考虑变量取整的要求，把它当作一般的线性规划问题量取整的要求，把它当作一般的线性规划问题来处理，并求其最优解，如果该最优解都是整来处理，并求其最优解，如果该最优解都是整数，则同时也就得到了整数线性规划问题的最数，则同时也就得到了整数线性规划问题的最优解，问题求解到此为止。优解，问题求解到此为止。2、若由一般线性规划求出的最优解不是整数解，、若由一般线性规划求出的最优解不是整数解，假定基变量假定基变量Xj=bj不是整数，那么作如

13、下处理不是整数，那么作如下处理,构构造两个约束条件：造两个约束条件：Xjbj，Xj bj+1。3、将构造的两个新约束条件，分别加到问题中、将构造的两个新约束条件，分别加到问题中去，形成两个整数规划问题。去，形成两个整数规划问题。2/4/202318两个新的整数规划问题为：两个新的整数规划问题为：（I）Max Z=CX （II）Max Z=CX St AX(=、)b St AX(=、)b Xjbj Xj bj+1 X0,且取整数且取整数 X0,且取整数且取整数 l4、分别按一般线性规划求解这两个整、分别按一般线性规划求解这两个整数规划，直到能够确定整数规划的最优数规划，直到能够确定整数规划的最优

14、解或能够判定其无最优解时为止。解或能够判定其无最优解时为止。2/4/202319l例例6.6 用分枝定界法求解用分枝定界法求解 且且均均取取整整数数,0,255.22108.02.134max21212121xxxxxxxxZ解解:先求对应的松弛问题（记为先求对应的松弛问题（记为LP0）)(0,255.22108.02.134max021212121LPxxxxxxstxxZ 用图解法得到最优解用图解法得到最优解X(3.57,7.14),Z0=35.7,如下图所示。如下图所示。2/4/2023201010108.02.121 xx255.2221 xx松弛问题松弛问题LP0的最优解的最优解X=

15、(3.57,7.14),Z0=35.7x1x2oABC2/4/202321得得到到两两个个线线性性规规划划及及增增加加约约束束4311 xx10 x2oABC 0,3255.22108.02.1:134max211212121xxxxxxxLPxxZLP1LP234LP1:X=(3,7.6),Z1=34.8 0,4255.22108.02.1:234max211212121xxxxxxxLPxxZLP2:X=(4,6.5),Z2=35.52/4/20232210 x1x2oABCLP1LP2134LP21:X=(4.33,6),Z21=35.33 0,64255.22108.02.1:2134

16、max2121212121xxxxxxxxLPxxZ，不不可可行行，得得到到线线性性规规划划，显显然然及及进进行行分分枝枝，增增加加约约束束选选择择目目标标值值最最大大的的分分枝枝7762222 xxxLP6不可行72x 0,74255.22108.02.1:2234max2121212121xxxxxxxxLPxxZ，2/4/20232310 x1x2oACLP134可可行行域域是是一一条条线线段段即即，,40,464255.22108.02.1:21134max121121212121 xxxxxxxxxxLPxxZ：及及，得得线线性性规规划划及及进进行行分分枝枝，增增加加约约束束，选选择

17、择由由于于212211542111121LPLPxxLPZZ 6 0,65255.22108.02.1:21234max2121212121xxxxxxxxLPxxZ，LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355LP2122/4/202324LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x13x14LP21:X=(4.33,6)Z21=35.33x26LP211:X=(4,6)Z211=34LP212:X=(5,5)Z212=35x14x15LP22无可行解无可行解x2

18、7LP212的最优解就是原整数规划的最优解，其最优解为：的最优解就是原整数规划的最优解，其最优解为：X=(5，5)T，Z=35。2/4/202325l分枝定界法解的判定标准分枝定界法解的判定标准（I）（II）说明说明无可行解无可行解 无可行解无可行解 整数规划无解整数规划无解无可行解无可行解 整数解整数解 （II）的解为最优解）的解为最优解无可行解无可行解 非整数最优解非整数最优解 对（对（II）继续求解）继续求解整数解整数解 整数解整数解 较优解为最优整数解较优解为最优整数解整数解且整数解且目标函数目标函数优于（优于（II）非整数解非整数解 （I）的解为最优解）的解为最优解整数解整数解 非整

19、数解且非整数解且 目标函数优于（目标函数优于（I）只对（只对（II）继续求解）继续求解 2/4/202326学习要点：学习要点：掌握一般整数规划问题概念及模型结构掌握一般整数规划问题概念及模型结构 掌握分支定界法原理掌握分支定界法原理 能够用分支定界法求解一般整数规划问题能够用分支定界法求解一般整数规划问题2/4/202327l一、割平面法的基本思想一、割平面法的基本思想 解整数规划时，先不考虑变量取整的要求，把解整数规划时，先不考虑变量取整的要求，把它当作一般的线性规划问题来处理，假定它当作一般的线性规划问题来处理，假定X为一般规为一般规划问题的最优解，如果划问题的最优解，如果X是整数，则得

20、到整数规划的是整数，则得到整数规划的最优解，如果最优解，如果X不是整数，则构造一个约束方程（用不是整数，则构造一个约束方程（用几何术语称为几何术语称为割平面割平面），使使X不满足该方程，但原不满足该方程，但原问题的所有整数可行解却满足该方程问题的所有整数可行解却满足该方程，然后再解增，然后再解增加约束后的线性规划问题，直到求出最优解为止。加约束后的线性规划问题，直到求出最优解为止。2/4/202328这个方法是这个方法是Gomory提出来的，又称为提出来的，又称为Gomory的割的割平面法，我们只讨论平面法，我们只讨论纯整数纯整数规划情形。现举例说明。规划情形。现举例说明。例例3 求解求解 m

21、ax Z=x1+x2 -x1+x2 1 3x1+x2 4 x1,x2 0 0 x1,x2是整数是整数 如不考虑整数约束，可求得相应的线性规划的最优解为：如不考虑整数约束，可求得相应的线性规划的最优解为：x1=3/4,x2=7/4,max z=10/4 2/4/202329x2 x2 O x1 O x1 （a）（b）最优解就是图（就是图（a）中域）中域R的极点的极点A，它不符合整数条件。我，它不符合整数条件。我们想，如能找到象们想，如能找到象BC那样的直线去切割域那样的直线去切割域R（图（图(b)），去掉三角形），去掉三角形域域ACB，那么具有整数坐标，那么具有整数坐标C 点（点（1,1）就是新

22、域的一个极点，如在）就是新域的一个极点，如在新域上求解线性规划，而得到的最优解又恰巧在新域上求解线性规划，而得到的最优解又恰巧在C点就得到原问题的点就得到原问题的整数解，所以解法的关键就是怎样构造一个这样的整数解，所以解法的关键就是怎样构造一个这样的“割平面割平面”BC，尽管它可能不是唯一的，也可能不是一步能求到的。下面仍就本例说尽管它可能不是唯一的，也可能不是一步能求到的。下面仍就本例说明：明：2/4/202330在在原原问问题题的的前前两两个个不不等等式式中中增增加加松松弛弛变变量量（0），使使两两式式成成等等式式约约束束：-x1+x2+x3 =1 （1 1）3x1+x2 +x4 =4 （

23、2 2）不不考考虑虑整整数数条条件件，用用单单纯纯型型表表解解题题，请请见见下下表表。C Cj j 1 1 1 1 0 0 0 0 C CB B X XB B b b X X1 1 x x2 2 x x3 3 x x4 4 0 0 x x3 3 1 1 -1 1 1 1 1 1 0 0 0 0 x x4 4 4 4 3 3 1 1 0 0 1 1 初初始始计计算算表表 C Cj j-Z Zj j 1 1 1 1 0 0 0 0 1 1 x x1 1 3 3/4 4 1 1 0 0 -1 1/4 4 1 1/4 4 1 1 x x2 2 7 7/4 4 0 0 1 1 3 3/4 4 1 1/4

24、 4 最最终终计计算算表表 C Cj j-Z Zj j 0 0 0 0 -1 1/2 2 -1 1/2 2 从从最最终终计计算算表表中中，得得到到非非整整数数的的最最优优解解：x1=3/4,x2=7/4,x3=x4=0,max z=5/2 2/4/202331 由最终计算表得到变量简单关系式为：由最终计算表得到变量简单关系式为：434141431xxx 474143432xxx 2/4/2023322/4/202333 现考虑整数条件，要求现考虑整数条件，要求x1、x2都是非负整数，于都是非负整数，于是由条件（是由条件（1）、（）、（2）可知）可知x3、x4也都是非负整数。也都是非负整数。在上

25、式中（其实在上式中（其实只考虑一式即可只考虑一式即可）从等式左边看是）从等式左边看是整数；在等式右边的（）内是整数；在等式右边的（）内是非负数非负数；整个等式右；整个等式右边只可能边只可能小于小于1，那么只能小于或等于零，所以等式，那么只能小于或等于零，所以等式右边必是负数。就是说右边必是负数。就是说整数条件约束条件可由下式整数条件约束条件可由下式所代替，所代替，即：即：x1、x2都都是是非非负负整整数数，于于是是由由条条件件（1）、（2）可可知知 x3、x4也也都都是是非非负负整整数数。在在上上式式中中（其其实实只只考考虑虑一一式式即即可可）从从等等式式左左边边看看是是整整数数；在在等等式式

26、右右边边的的（）内内是是正正数数；整整个个等等式式右右边边不不可可能能大大于于 1，那那么么只只能能小小于于或或等等于于零零，所所以以等等式式右右边边必必是是负负数数。就就是是说说，整整数数条条件件约约束束条条件件可可由由下下式式所所代代替替，即即：43414343xx0-3x3-x4-3 这这就就得得到到一一个个切切割割方方程程，引引入入松松弛弛变变量量 x5，得得到到等等式式：-3x3-x4+x5=-3 将将这这新新的的约约束束方方程程加加到到表表上上面面的的最最终终计计算算表表，用用对对偶偶单单纯纯形形法法计计算算得得下下表表：2/4/202334C Cj j 1 1 1 1 0 0 0

27、 0 0 0 C CB B X XB B b b x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 1 1 X X1 1 1 1 1 1 0 0 0 0 1/31/3 1/121/12 1 1 X X2 2 1 1 0 0 1 1 0 0 0 0 1/41/4 0 0 X X3 3 1 1 0 0 0 0 1 1 -1 1 -1/31/3 C Cj j-Z Zj j 0 0 0 0 0 0 -1/31/3 -1/61/6 2/4/202335 2/4/202336综上所述，可以将用割平面法求解整数规划问题的步骤如下：综上所述，可以将用割平面法求解整数规划问题的步骤如下：第一

28、步：第一步：先不考虑整数约束，变成一般的先不考虑整数约束，变成一般的LP问题，用单纯形问题，用单纯形法求其最优解，记为法求其最优解，记为X(0)第二步：第二步：若求得最优解若求得最优解X(0)刚好就是整数解，则该整数解就刚好就是整数解，则该整数解就是原整数规划问题的最优解；否则，转下一步是原整数规划问题的最优解；否则，转下一步第三步：第三步：寻求附加约束，即割平面方程寻求附加约束，即割平面方程 从最优化表中抄下从最优化表中抄下非整数解的约束方程非整数解的约束方程：其中其中bi是基变量是基变量xi的非整数解的非整数解 将该约束方程所有系数和常数分解为将该约束方程所有系数和常数分解为整数整数N和和

29、正真分数正真分数f之和：之和：xi+(Nik+fik)xk=Nbi+fbi 2/4/202337第四步：第四步：将割平面方程标准规范化：将割平面方程标准规范化：加到原最优表中，用对偶单纯形法求新的最优解。加到原最优表中，用对偶单纯形法求新的最优解。第五步：第五步：重复第三、四步直到获得原问题的最优整数解重复第三、四步直到获得原问题的最优整数解为止。为止。kkikbibikkikixffNxNx 1、现现在在提提出出变变量量（包包括括松松弛弛变变量量）为为整整数数的的条条件件（当当然然还还有有非非负负的的条条件件），这这时时，上上式式由由左左边边看看必必须须是是整整数数，但但由由右右边边看看，因

30、因为为 0fi1，所所以以不不能能为为正正，即即 bikikikfxxf1,)(0kkikbixff2/4/202338 例例4：某厂拟建两种不同类型的冶炼炉。甲种炉每某厂拟建两种不同类型的冶炼炉。甲种炉每台需投资为台需投资为2单位，乙种炉每台需投资为单位，乙种炉每台需投资为1单位，总投单位，总投资不能超过资不能超过10 个单位；又该厂被许可用电量为个单位；又该厂被许可用电量为2 单位，单位，乙种炉每台投产后要用电为乙种炉每台投产后要用电为2 单位，但甲种炉利用余热单位，但甲种炉利用余热发电，不仅能满足本身需要的用电量，还能供出电量发电，不仅能满足本身需要的用电量，还能供出电量1 单位。已知甲

31、种炉每台的收益为单位。已知甲种炉每台的收益为6 单位，乙种炉每台单位，乙种炉每台的收益为的收益为4 单位。试问：应建单位。试问：应建 甲乙两种炉各几台，使甲乙两种炉各几台，使总收益为最大？总收益为最大？l解：依题意有下表解：依题意有下表 冶炼炉 收益每台投资用电量甲炉62-1乙 炉412限量1022/4/202339解：解：1.解除整数约束，引入非负的整松驰变量解除整数约束，引入非负的整松驰变量x3，x4。将原数学模。将原数学模型化为型化为 2x1+x2+x3=10 -x1+2x2+x4=2 x1,x2,x3,x4 0且为整数且为整数 2/4/202340用单纯形法求最优解用单纯形法求最优解

32、C Cj j 6 6 4 4 0 0 0 0 C CB B X XB B b b X X1 1 x x2 2 x x3 3 x x4 4 0 0 x x3 3 1 10 0 2 2 1 1 1 1 0 0 0 0 x x4 4 2 2 -1 1 2 2 0 0 1 1 初初始始计计算算表表 C Cj j-Z Zj j 6 6 4 4 0 0 0 0 1 1 x x1 1 1 18 8/5 5 1 1 0 0 2 2/5 5 -1 1/5 5 1 1 x x2 2 1 14 4/5 5 0 0 1 1 1 1/5 5 2 2/5 5 最最终终计计算算表表 C Cj j-Z Zj j 0 0 0

33、0 -1 16 6/5 5 -2 2/5 5 从从最最终终计计算算表表中中，得得到到非非整整数数的的最最优优解解：x1=1 18 8/5 5,x2=1 14 4/5 5,x3=x4=0,max z=32.8 2.确立割平面方程（确立割平面方程（取取b 值小数部分最大的方程，可以减少值小数部分最大的方程，可以减少“切割切割”次数次数）43243252515425145251xxxxxx即取2/4/202341即为割平面方程052515443xx3.将割平面方程规范化得将割平面方程规范化得545251543xxx4.将割平面约束加入到最优单纯形表中，用对偶单纯形法求解将割平面约束加入到最优单纯形表中，用对偶单纯形法求解p 经常不断地学习,你就什么都知道。你知道得越多,你就越有力量p Study Constantly,And You Will Know Everything.The More You Know,The More Powerful You Will Be写在最后Thank You在别人的演说中思考，在自己的故事里成长Thinking In Other PeopleS Speeches，Growing Up In Your Own Story讲师：XXXXXX XX年XX月XX日