运筹学-整数规划.ppt

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

1、第四章整数规划第四章整数规划基本要求：基本要求：了解整数规划决策问题的特点了解整数规划决策问题的特点熟悉分枝定界法和割平面法的原理及其应用熟悉分枝定界法和割平面法的原理及其应用理解理解0-1规划及其求解方法隐枚举法规划及其求解方法隐枚举法掌握指派问题及其求解方法匈牙利法掌握指派问题及其求解方法匈牙利法第一节整数规划问题的提出第一节整数规划问题的提出一、什么是整数规划问题一、什么是整数规划问题决策变量要求取整数的线性规划叫做整数规划决策变量要求取整数的线性规划叫做整数规划（Integer Programming），简称），简称IP。二、整数规划的分类二、整数规划的分类l纯整数规划：纯整数规划：整

2、数规划中如果所有的决策变量都限制整数规划中如果所有的决策变量都限制为（非负）整数，称为纯整数规划或称为全整数规划。为（非负）整数，称为纯整数规划或称为全整数规划。l混合整数规划：混合整数规划：整数规划中如果仅有一部分决策变量整数规划中如果仅有一部分决策变量限制为（非负）整数，则称为混合整数规划。限制为（非负）整数，则称为混合整数规划。l0-1规划：规划：整数规划中如果决策变量取值仅限整数规划中如果决策变量取值仅限0或或1，则称为则称为0-1规划。规划。第一节整数规划问题的提出第一节整数规划问题的提出例：例：某公司拟在市东、西、南三区建立门市部，某公司拟在市东、西、南三区建立门市部，拟议中有拟议

3、中有7个位置个位置Ai(i=1,2,7)可供选择。规定可供选择。规定在东区，由在东区，由A1，A2，A3三个点中至多选两个；三个点中至多选两个；在西区，由在西区，由A4，A5两个点中至少选一个；两个点中至少选一个；在南区，由在南区，由A6，A7两个点中至少选一个。两个点中至少选一个。如选用如选用Ai点，设备投资估计为点，设备投资估计为bi元，每年可获利元，每年可获利润估计为润估计为ci元，但投资总额不能超过元，但投资总额不能超过B元。问应选择哪元。问应选择哪个点可使年利润最大？个点可使年利润最大？建模如下：建模如下：第一节整数规划问题的提出第一节整数规划问题的提出第一节整数规划问题的提出第一节

4、整数规划问题的提出例例.某厂拟用集装箱托运某厂拟用集装箱托运甲、乙两种货物，每箱的甲、乙两种货物，每箱的体积、重量、可获利润以体积、重量、可获利润以及托运所受限制如右表所及托运所受限制如右表所示。问两种货物各托运多示。问两种货物各托运多少箱，可使获得利润为最少箱，可使获得利润为最大？大？货物货物甲甲乙乙托运限制托运限制体积体积每箱（米每箱（米3）5424重量重量每箱（百公斤）每箱（百公斤）2513利润利润每箱（百元）每箱（百元）2010解：设甲、乙两种货物解：设甲、乙两种货物的托运箱数分别为的托运箱数分别为x1,x2。建模如下：。建模如下：x1x2012 3 4 5 6 7123456第一节整

5、数规划问题的提出第一节整数规划问题的提出整数规划的松弛问题整数规划的松弛问题解得：最优解：解得：最优解：X=（4.8,0）T最优值：最优值：Z=96X(1)=(5,0)TX(2)=(4,0)T(4,1)第一节整数规划问题的提出第一节整数规划问题的提出整数规划与其松弛问题之间的关系整数规划与其松弛问题之间的关系l整数规划问题的可行域是它的松弛问题可行域的整数规划问题的可行域是它的松弛问题可行域的一个子集；一个子集；l整数规划问题的最优值（最优解对应的目标函数整数规划问题的最优值（最优解对应的目标函数值）不会优于它的松弛问题的最优值；值）不会优于它的松弛问题的最优值；l对松弛问题的最优解中不符合整

6、数要求的分量简对松弛问题的最优解中不符合整数要求的分量简单地取整，所得到的解不一定是整数规划问题的最单地取整，所得到的解不一定是整数规划问题的最优解，甚至也不一定是整数规划问题的可行解。优解，甚至也不一定是整数规划问题的可行解。第二节分枝定界法第二节分枝定界法一、什么是分枝定界法一、什么是分枝定界法设有最大化的整数规划问题设有最大化的整数规划问题A，它的松弛问题为，它的松弛问题为问题问题B。从解问题。从解问题B开始，若其最优解不符合开始，若其最优解不符合A的整的整数条件，那么数条件，那么B的最优目标函数必是的最优目标函数必是A的最优目标函的最优目标函数数Z的上界，记作的上界，记作Z；而；而A的

7、任意可行解对应的目标的任意可行解对应的目标函数值将是函数值将是Z的一个下界，记作的一个下界，记作Z。分枝定界法就。分枝定界法就是将是将B的可行域分成子区域（称为分枝）的方法。逐的可行域分成子区域（称为分枝）的方法。逐步减小步减小Z和增大和增大Z，最终求得，最终求得Z。第二节分枝定界法第二节分枝定界法例：用分枝定界法求解下面问题例：用分枝定界法求解下面问题问题问题Bx1=4.81x2=1.82z0=356问题问题B1x1=4.00 x2=2.10z1=349问题问题B2x1=5.00 x2=1.57z2=341问题问题B3x1=4.00 x2=2.00z3=340问题问题B4x1=1.42x2=

8、3.00z4=327x14x15z=0，z=356z=0，z=349x22x23z=340 x21x22z=341问题问题B5x1=5.44x2=1.00z5=308问题问题B6无可行解无可行解z=340z*图解法图解法x2x104 52314321656787 8 9 10第二节分枝定界法第二节分枝定界法二、分枝定界法的求解步骤：二、分枝定界法的求解步骤：将要求解的整数规划问题称为将要求解的整数规划问题称为A，将与它相应的线性规划问题称，将与它相应的线性规划问题称为问题为问题B。(1)解问题解问题B，可能得到以下情况之一：，可能得到以下情况之一：（a）B没有可行解，这时没有可行解，这时A也没

9、有可行解，则停止。也没有可行解，则停止。（b）B有最优解，并符合问题有最优解，并符合问题A的整数条件，的整数条件，B的最优解即为的最优解即为A的最优解，则停止。的最优解，则停止。（c）B有最优解，但不符合问题有最优解，但不符合问题A的整数条件，记它的目标函的整数条件，记它的目标函数值为数值为Z。第二节分枝定界法第二节分枝定界法(2)用观察法找问题的一个整数可行解，一般可取用观察法找问题的一个整数可行解，一般可取xj=0(j=1,2,n)，求得其目标函数值，并记作，求得其目标函数值，并记作Z。以。以Z表示问表示问题题A的最优目标函数值；这时有的最优目标函数值；这时有进行迭代进行迭代第一步：分枝，

10、在第一步：分枝，在B的最优解中任选一个不符合整数条件的最优解中任选一个不符合整数条件的变量的变量xj，其值为，其值为bj，以，以bj表示小于表示小于bj的最大整数。构造两的最大整数。构造两个约束条件个约束条件xjbj和和xjbj+1将这两个约束条件，分别加入问题将这两个约束条件，分别加入问题B，求两个后继规划问题，求两个后继规划问题B1和和B2，不考虑整数条件求解这两个后继问题。，不考虑整数条件求解这两个后继问题。第二节分枝定界法第二节分枝定界法定界，以每个后继问题为一分枝标明求解的结果，与其它问定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果比较，找出最优目标函数值最大者作为

11、新的上界题的解的结果比较，找出最优目标函数值最大者作为新的上界Z。从已符合整数条件的各分支中，找出目标函数值最大者作为新的从已符合整数条件的各分支中，找出目标函数值最大者作为新的下界下界Z，若无符合整数条件的解，若无符合整数条件的解，Z0。第二步：比较与剪枝，各分枝的最优目标函数中若有小于第二步：比较与剪枝，各分枝的最优目标函数中若有小于Z者，则剪掉这枝（用打者，则剪掉这枝（用打表示），即以后不再考虑了。若大于表示），即以后不再考虑了。若大于Z，且不符合整数条件，则重复第一步骤。一直到最后，且不符合整数条件，则重复第一步骤。一直到最后ZZ为止。为止。得最优整数解得最优整数解xj*(j=1,2,

12、n)。第二节分枝定界法第二节分枝定界法用分枝定界法解下列问题：用分枝定界法解下列问题：问题问题Bx1=3.71x2=2.35Z0=14.47问题问题B1x1=3x2=2.67Z1=14问题问题B2x1=4x2=2.14Z2=14.43问题问题B6无可行解无可行解问题问题B5x1=4.2x2=2Z2=14问题问题B3x1=2.25x2=3Z1=13.5问题问题B4x1=3x2=2Z1=12x13x14x23x22x22x23第三节割平面法第三节割平面法一、什么是割平面法（基本思想）一、什么是割平面法（基本思想）先不考虑变量的整数限制，求解其对应的线性规划问题。先不考虑变量的整数限制，求解其对应的

13、线性规划问题。如果得到的解不是整数解，则不断增加适当的约束，割掉原如果得到的解不是整数解，则不断增加适当的约束，割掉原可行域中不含整数解的一部分，最终得到一个具有若干整数可行域中不含整数解的一部分，最终得到一个具有若干整数顶点的可行域，而这些顶点中恰有一个顶点是原问题的最优顶点的可行域，而这些顶点中恰有一个顶点是原问题的最优整数解。整数解。步骤步骤1：不考虑变量的整数限制，求解相应的线性规划问题，：不考虑变量的整数限制，求解相应的线性规划问题，如果该问题无可行解或最优解已是整数解，则停止计算，否如果该问题无可行解或最优解已是整数解，则停止计算，否则转入一下步；则转入一下步；步骤步骤2：对上述线

14、性规划问题的可行域进行：对上述线性规划问题的可行域进行“切割切割”，去掉，去掉不含整数解的一部分可行域，即增加适当的约束条件不含整数解的一部分可行域，即增加适当的约束条件（Gomory约束约束），然后转入步骤），然后转入步骤1。第三节割平面法第三节割平面法二、二、Gomory约束的求解步骤：约束的求解步骤：1、设、设xi是相应线性规划最优解中一个不是整数的基是相应线性规划最优解中一个不是整数的基变量，将最终单纯形表中该基变量对应的行还原成约变量，将最终单纯形表中该基变量对应的行还原成约束方程。即束方程。即其中其中iQ(Q指构成基变量下标的集合指构成基变量下标的集合)kK(K指构成非基变量下标的

15、集合指构成非基变量下标的集合)第三节割平面法第三节割平面法2、将、将bi和和aik都分解成整数部分都分解成整数部分N与非负真分数与非负真分数f之和之和,即即bi=Ni+fi，其中，其中0fi1 aik=Nik+fik，其中其中0fik1代入（代入（1）式得）式得由于变量有整数的限制，所以上式左边必为整数。则由于变量有整数的限制，所以上式左边必为整数。则右边也应该是整数，但由于右边也应该是整数，但由于0fi1，所以不能为正，所以不能为正，即即第三节割平面法第三节割平面法例：用割平面法求解下列问题例：用割平面法求解下列问题第三节割平面法第三节割平面法初始单纯形表初始单纯形表最终单纯形表最终单纯形表

16、CBXBb1100 x1x2x3x40 x31-11100 x443101cj-zj1100CBXBb1100 x1x2x3x41x13/410-1/41/41x27/4013/41/4cj-zj00-1/2-1/2第三节割平面法第三节割平面法Gomory约束约束切割方程切割方程Ox1x212341234AB第四节第四节0-1整数规划整数规划决策变量只能取决策变量只能取0或或1的整数规划，叫做的整数规划，叫做0-1整数规整数规划。决策变量称为划。决策变量称为0-1变量变量(二进制变量、逻辑变量二进制变量、逻辑变量)。0-1变量作为逻辑变量，常被用来表示系统是否处于某变量作为逻辑变量，常被用来表

17、示系统是否处于某个特定状态，或者决策时是否取某个特定方案。个特定状态，或者决策时是否取某个特定方案。一、什么是一、什么是0-1整数规划整数规划第四节第四节0-1整数规划整数规划1、投资场所的选定相互排斥的计划、投资场所的选定相互排斥的计划例：某公司拟在市东、西、南三区建立门市部，拟议中有例：某公司拟在市东、西、南三区建立门市部，拟议中有7个个位置位置Ai(i=1,2,7)可供选择。规定可供选择。规定在东区，由在东区，由A1，A2，A3三个点中至多选两个；三个点中至多选两个；在西区，由在西区，由A4，A5两个点中至少选一个；两个点中至少选一个；在南区，由在南区，由A6，A7两个点中至少选一个。两

18、个点中至少选一个。如选用如选用Ai点，设备投资估计为点，设备投资估计为bi元，每年可获利润估计为元，每年可获利润估计为ci元，元，但投资总额不能超过但投资总额不能超过B元。问应选择哪个点可使年利润最大？元。问应选择哪个点可使年利润最大？0-1规划的实际问题：规划的实际问题：建模如下：建模如下：st.第四节第四节0-1整数规划整数规划2、相互排斥的约束条件、相互排斥的约束条件例：本章例例：本章例1中，关于货运的体积限制为中，关于货运的体积限制为5x1+4x224(车车)。今设运货有车运和船运两种方式，上面的条件系用车运时的限制条今设运货有车运和船运两种方式，上面的条件系用车运时的限制条件，如用船

19、运时关于体积的限制条件为件，如用船运时关于体积的限制条件为7x1+3x245(船船)。（这两。（这两条件是互相排斥的）条件是互相排斥的）例例1.某厂拟用集装箱托运某厂拟用集装箱托运甲、乙两种货物，每箱甲、乙两种货物，每箱的体积、重量、可获利的体积、重量、可获利润以及托运所受限制如润以及托运所受限制如右表所示。问两种货物右表所示。问两种货物各托运多少箱，可使获各托运多少箱，可使获得利润为最大？得利润为最大？货物货物甲甲乙乙托运限制托运限制体积体积每箱（米每箱（米3）5424重量重量每箱（百公斤）每箱（百公斤）2513利润利润每箱（百元）每箱（百元）2010解：设甲、乙两种货物的解：设甲、乙两种货

20、物的托运箱数分别为托运箱数分别为x1,x2。设变量设变量y表示运货的方式，表示运货的方式，当当y为为1时，用车运，时，用车运，y为为0时，用船运。时，用船运。+(1-y)M+yM第四节第四节0-1整数规划整数规划二、二、0-1整数规划的解法整数规划的解法隐枚举法：只检查变量取值的组合的一部分的方法。隐枚举法：只检查变量取值的组合的一部分的方法。(x1,x2,x3)Z值abcd过滤条件过滤条件(0,0,0)0Z0(0,0,1)5Z5(0,1,0)-2(0,1,1)3(1,0,0)3Z8(1,0,1)(1,1,0)81(1,1,1)6按目标函数中各变量系数的大小重新排列各变量按目标函数中各变量系数

21、的大小重新排列各变量最大化问题：由小到大最大化问题：由小到大最小化问题：由大到小最小化问题：由大到小第五节指派问题第五节指派问题一、什么是指派问题一、什么是指派问题某单位需完成任务某单位需完成任务n项任务，恰好有项任务，恰好有n个人可承担个人可承担这些任务，由于每人的专长不同，各人完成不同任务这些任务，由于每人的专长不同，各人完成不同任务效率也不同。于是产生应指派哪个人去完成哪项任务，效率也不同。于是产生应指派哪个人去完成哪项任务，使完成使完成n项任务的总效率最高。这类问题称为项任务的总效率最高。这类问题称为指派问题指派问题(分派问题、分配问题分派问题、分配问题)B1B2BnA1c11c12c

22、1nA2c21c22c2nAncn1cn2cnn人人任务任务cij表示第表示第i个人完成第个人完成第j项项任务的效率。任务的效率。第五节指派问题第五节指派问题二、指派问题的数学模型二、指派问题的数学模型=(Cij)B1B2BnA1c11c12c1nA2c21c22c2nAncn1cn2cnn人人任务任务解：设解：设例：某单位现在、例：某单位现在、四项工作需完成，、四项工作需完成，现在甲、乙、丙、丁四个现在甲、乙、丙、丁四个人均可完成这四项任务。人均可完成这四项任务。每人完成各项任务所用的每人完成各项任务所用的时间如右表所示，问应指时间如右表所示，问应指派何人去完成何项任务，派何人去完成何项任务

23、，使所需时间最少？使所需时间最少？甲甲215134乙乙1041415丙丙9141613丁丁78119ABCD任务任务人员人员满足所有约束条件的可行解满足所有约束条件的可行解xij也可也可写成表格或矩阵形式，称为写成表格或矩阵形式，称为解矩阵解矩阵(xij)=就是上例的就是上例的一个可行解一个可行解矩阵矩阵第五节指派问题第五节指派问题(cij)=第五节指派问题第五节指派问题指派问题数学模型的性质：指派问题数学模型的性质：若从指派问题的系数的系数矩阵（若从指派问题的系数的系数矩阵（cij）的一行（列）各元）的一行（列）各元素中分别减去该行（列）的最小元素，得到新矩阵（素中分别减去该行（列）的最小元

24、素，得到新矩阵（bij），那），那么以（么以（bij）为系数矩阵求得的最优解和用原系数矩阵求得的最）为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。优解相同。独立的独立的0元素：元素：位于不同行不同列的位于不同行不同列的0元素称为独立的元素称为独立的0元素。元素。结论：结论：若能在系数矩阵若能在系数矩阵(bij)中找出中找出n个独立的个独立的0元素；则令解矩阵元素；则令解矩阵(xij)中对应这中对应这n个独立的个独立的0元素取值为元素取值为1，其它元素取值为，其它元素取值为0。将。将其代入目标函数中得到其代入目标函数中得到zk=0，它一定是最小。这就是以，它一定是最小。这就是以(bij)

25、为为系数矩阵的指派问题的最优解。也就得到了问题的最优解。系数矩阵的指派问题的最优解。也就得到了问题的最优解。第五节指派问题第五节指派问题三、指派问题的解法（匈牙利法）三、指派问题的解法（匈牙利法）第一步第一步:使指派问题的系数矩阵经变换，在各行各列都出现元素。使指派问题的系数矩阵经变换，在各行各列都出现元素。（）从系数矩阵的每行元素减去该行的最小元素；（）从系数矩阵的每行元素减去该行的最小元素；（）再从所得系数矩阵的每列元素中减去该列的最小元素。（）再从所得系数矩阵的每列元素中减去该列的最小元素。2497min24min经第一步变换后，系数矩阵中每行每列都已有了经第一步变换后，系数矩阵中每行每

26、列都已有了0元素；元素；只需找出只需找出n个独立的个独立的0元素，若能找出，就以这些独立的元素，若能找出，就以这些独立的0元素元素对应解矩阵中的元素为对应解矩阵中的元素为1，其作为，其作为0，这就得到最优解。找独，这就得到最优解。找独立立0元素的步骤如下：元素的步骤如下：第二步：进行试指派，以寻求最优解。第二步：进行试指派，以寻求最优解。第五节指派问题第五节指派问题0（1）从只有一个从只有一个0元素的行开始，给这个元素的行开始，给这个0元素加圈，记作元素加圈，记作.然然后再划去后再划去所在列的其它所在列的其它0元素，记作元素，记作 。（2）给只有一个给只有一个0元素的列的元素的列的0元素加圈，

27、记作元素加圈，记作；然后划去；然后划去所在行的所在行的0元素，记作元素，记作 。0（3）反复反复(1),(2)两步，直到所有两步，直到所有0元素都被圈出和划掉为止。元素都被圈出和划掉为止。（4）若各行各列均有多于若各行各列均有多于2个的个的0元素未被圈出或划掉，中任选元素未被圈出或划掉，中任选其中任意一个其中任意一个0元素加圈。元素加圈。（5）若若元素的数目元素的数目m等于矩阵的阶数等于矩阵的阶数n，那么指派问题的最优，那么指派问题的最优解已得到，若解已得到，若m4）,x23又又M为任意大为任意大正数，则问题正数，则问题可表达为：可表达为：第六节应用举例第六节应用举例4、用以表示固定费用的函数

28、、用以表示固定费用的函数生产费用函数：生产费用函数：引入变量引入变量yj复习题复习题一、判断下列说法是否正确一、判断下列说法是否正确1、整数规划的目标函数值一般优于其相应的线性规、整数规划的目标函数值一般优于其相应的线性规划问题（松弛问题）的解的目标函数值。划问题（松弛问题）的解的目标函数值。2、用分枝定界法求解一个极大化的整数规划问题时，、用分枝定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的任何一个可行解的目标函数值是该问题目标函数值的下界。下界。3、用分枝定界法求解一个极大化的整数规划问题，、用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行

29、解时，通常可任取其中一个作为当得到多于一个可行解时，通常可任取其中一个作为下界值，再进行比较、剪枝。下界值，再进行比较、剪枝。4、用割平面法求解整数规划时，构造的割平面有可、用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。能切去一些不属于最优解的整数解。复习题复习题一、判断下列说法是否正确一、判断下列说法是否正确5、用割平面法求解纯整数规划时，要求包括松弛变、用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。量在内的全部变量必须取整数值。6、指派问题效率矩阵的每个元素都乘上同一常数、指派问题效率矩阵的每个元素都乘上同一常数k，将不影响最优指派方案

30、。，将不影响最优指派方案。7、指派问题数学模型的形式同运输问题十分相似，、指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解。故也可以用表上作业法求解。8、求解、求解0-1规划的隐枚举法是分枝定界法的特例。规划的隐枚举法是分枝定界法的特例。9、分枝定界法在需要分枝时必须满足：一是分枝后、分枝定界法在需要分枝时必须满足：一是分枝后的各子问题必须容易求解；二是各子问题解的集合的各子问题必须容易求解；二是各子问题解的集合必须覆盖原问题的解。必须覆盖原问题的解。复习题复习题2、用匈牙利法求解最小化的指派问题，效率矩阵如下：、用匈牙利法求解最小化的指派问题，效率矩阵如下：min76746复习题复习题3、应用建模：教材、应用建模：教材128页页4.16