运筹学基础整数规划

关于运筹学基础整数规划第1页，共41页，2022年，5月20日，14点8分，星期六2§4.1整数规划解决整数规划问题不能仅仅是在线性规划求解中，将解“四舍五入”就行了，因为化整后的解不见得是可行解；即便是可行解，也不一定是优解。注意：在前面讨论的线性规划问题中，有些最优解可能是分数或小数，但对于某些具体的问题，常有要求解答必须是整数的情形（称为整数解），解决这样的问题即为整数规划。一、整数规划问题的提出整数规划第2页，共41页，2022年，5月20日，14点8分，星期六3【例1】某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表：问两种货物各托运多少箱，可使利润为最大？建立线性规划模型为：

maxZ=

20x1+10x25x1+4x2≤242x1+5x2≤13

x1≥0,x2≥0利用单纯形法求得最优解为：x1＝4.8，x2＝0，maxZ＝96整数规划第3页，共41页，2022年，5月20日，14点8分，星期六4讨论：如何调整满足整数解（1）四舍五入：x1＝5，x2＝0，Z＝100但破坏了体积限制条件，因而不是可行解（2）舍小数：x1＝4，x2＝0，Z＝80是可行解，但不是最优解，因x1＝4，x2＝1，Z＝90也是可行解C(4.8,0)

maxZ=

20x1+10x25x1+4x2≤242x1+5x2≤13

x1≥0,x2≥0x2x111023234567++++++++++++B(4,1)x1＝4.8，x2＝0，maxZ＝96非整数解整数规划第4页，共41页，2022年，5月20日，14点8分，星期六5二、整数规划的求解方法1、分枝定解法2、割平面法3、利用EXCEL求解整数规划第5页，共41页，2022年，5月20日，14点8分，星期六61、整数规划之分枝定解法问题A：maxZ=

20x1+10x25x1+4x2≤242x1+5x2≤13

x1≥0,x2≥0

x1,x2整数问题B：maxZ=

20x1+10x25x1+4x2≤242x1+5x2≤13

x1≥0,x2≥0从问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数Z*的上界，记作，（如果是求最小值，即为下界）

分枝定界法就是将B的可行域分成子区域的方法，逐步减小和增大，最终逼近Z*。写出整数规划问题A的伴随线性规划问题为B

而A的任意可行解的目标函数值将是Z*的一个下界，记作，（如果是求最小值，即为上界）

≤Z*≤整数规划第6页，共41页，2022年，5月20日，14点8分，星期六7第一步：寻找替代问题并求解问题B：maxZ=

20x1+10x25x1+4x2≤242x1+5x2≤13

x1≥0,x2≥0利用单纯形法求得最优解为：x1＝4.8，x2＝0，Z＝96问题B1：maxZ=

20x1+10x2

5x1+4x2≤24

2x1+5x2≤13

x1≤4

x1≥0,x2≥0问题B2：maxZ=

20x1+10x2

5x1+4x2≤24

2x1+5x2≤13

x1≥5

x1≥0,x2≥0＝0≤Z*≤96＝利用单纯形法求得最优解为：x1＝4，x2＝1，Z＝90无解；第二步：分枝与定界x2x111023234567++++++++++++最后得最优解为：x1＝4，x2＝1，Z＝90整数规划第7页，共41页，2022年，5月20日，14点8分，星期六8【例2】问题A：maxZ=

40x1+90x29x1+7x2≤567x1+20x2≤70

x1≥0,x2≥0

x1,x2整数利用单纯形法求解问题B得最优解为：x1＝4.81，x2＝1.82，Z＝356问题B2：maxZ=

40x1+90x29x1+7x2≤567x1+20x2≤70

x1≥5

x1≥0,x2≥0＝0≤Z*≤356＝利用单纯形法求得最优解为：x1＝4，x2＝2.1，Z＝349利用单纯形法求得最优解为：x1＝5，x2＝1.57，Z＝341问题B：maxZ=

40x1+90x29x1+7x2≤567x1+20x2≤70

x1≥0,x2≥0问题B1：maxZ=

40x1+90x29x1+7x2≤567x1+20x2≤70

x1≤4

x1≥0,x2≥0＝0≤Z*≤349＝第一步：寻找替代问题并求解第二步：分枝与定界整数规划第8页，共41页，2022年，5月20日，14点8分，星期六9

分枝定解法求解（续）利用单纯形法求得最优解为：x1＝4，x2＝2，Z＝340利用单纯形法求得最优解为：x1＝1.52，x2＝3，Z＝327问题B11：maxZ=

40x1+90x29x1+7x2≤567x1+20x2≤70

x1≤4

x2≤2

x1≥0,x2≥0＝340≤Z*≤349＝x1＝4x2＝2.1Z＝349问题B12：maxZ=

40x1+90x29x1+7x2≤567x1+20x2≤70

x1≤4

x2≥3

x1≥0,x2≥0问题B21：maxZ=

40x1+90x29x1+7x2≤567x1+20x2≤70

x1≥5

x2≤1

x1≥0,x2≥0x1＝5x2＝1.57Z＝341x1＝5.44，x2＝1，Z＝308问题B21：maxZ=

40x1+90x29x1+7x2≤567x1+20x2≤70

x1≥5

x2≥2

x1≥0,x2≥0无可行解整数规划第9页，共41页，2022年，5月20日，14点8分，星期六10问题Bx1＝4.81x2＝1.82Z＝356问题B1x1＝4.00x2＝2.1Z＝349问题Bx1＝5.00x2＝1.57Z＝341问题B11x1＝4.00x2＝2.00Z＝340问题B12x1＝1.42x2＝3.00Z＝327问题B21x1＝5.44x2＝1.00Z＝308问题B22无可行解x1≤4x1≥5x2≤2x2≥3x2≤1x2≥2＝0≤Z*≤356＝＝0≤Z*≤349＝＝340≤Z*≤349＝Z*＝340

分枝定解法求解框图整数规划第10页，共41页，2022年，5月20日，14点8分，星期六11分枝为问题1、2后解可能出现如下几种情况序号问题1问题2说

明1无可行解无可行解整数规划无可行解2无可行解整数解此整数解即最优解3无可行解非整数解对问题2继续分枝4整数解整数解较优的一个为最优解5整数解，目标函数优于问题2非整数解问题1的解即最优解6整数解非整数解，目标函数优于问题1问题1停止分枝(剪枝)，其整数解为界，对问题2继续分枝情况2,4,5

找到最优解情况3

在缩减的域上继续分枝定界法情况6

问题1的整数解作为界被保留，用于以后与问题2的后续分枝所得到的整数解进行比较，结论如情况4情况1

无可行解整数规划第11页，共41页，2022年，5月20日，14点8分，星期六12分枝定界法的一般步骤如下

第一步，先不考虑原问题的整数限制，求解相应的松弛问题，若求得最优解，检查它是否符合整数约束条件；如符合整数约束条件，即转下一步。

第二步，定界。在各分枝问题中，找出目标函数值最大者Z*作为整数规划最优值的上界，从已符合整数条件的分枝中，找出目标函数值最大者作为下界，即

第三步，分枝。根据对变量重要性的了解，在最优解中选择一个不符合整数条件的xj

，令xj=b’j

，(b’j不为整数)则用下列两个约束条件：

第四步，应用对目标函数估界的方法，或对某一分枝重要性的了解，确定出首先要解的某一分枝的后继问题，并解此问题。若所获得的最优解符合整数条件，则就是原问题的解，若不符合整数条件，再回到第二步，并参照第四步终止后继问题。整数规划第12页，共41页，2022年，5月20日，14点8分，星期六13分枝定界法的EXCEL演示

整数规划第13页，共41页，2022年，5月20日，14点8分，星期六142、割平面解法

割平面法也是求解整数规划问题常用方法之一。【基本思路】

如果所得到最优解不满足整数约束条件，则在此非整数解的基础上增加新的约束条件重新求解。这个新增加的约束条件的作用就是去切割相应松弛问题的可行域，即割去松弛问题的部分非整数解(包括原已得到的非整数最优解)。而把所有的整数解都保留下来，故称新增加的约束条件为割平面。

当经过多次切割后，就会使被切割后保留下来的可行域上有一个坐标均为整数的顶点，它恰好就是所求问题的整数最优解。即切割后所对应的松弛问题，与原整数规划问题具有相同的最优解。

先不考虑整数约束条件，求松弛问题的最优解，如果获得整数最优解，即为所求，运算停止。整数规划第14页，共41页，2022年，5月20日，14点8分，星期六15

割平面法的具体求解步骤如下：1.对于所求的整数规划问题，先不考虑整数约束条件，求解相应的松弛问题2.如果该问题无可行解或已取得整数最优解，则运算停止；前者表示原问题也无可行解，后者表示已求得整数最优解。如果有一个或更多个变量取值不满足整数条件，则选择某个变量建立割平面。3.增加为割平面的新约束条件，用前面介绍的灵敏分析的方法继续求解，返回1。整数规划第15页，共41页，2022年，5月20日，14点8分，星期六16【例1】求解下列整数规划问题解：引入松弛变量，写成标准形式（1）ïîïíì³＝++＝+++=,0,,,;2054;62;max432142132121xxxxxxxxxxxxz（2）对上述模型不考虑整数条件，用单纯形法求解相应松弛问题的最终单纯形表为Cj比值CBXBb检验数jx1x2x3x411005/3105/6-1/68/301-2/31/3x1x211-13/300-1/6-1/6最优解为x1＝5/3，x2＝8/3不是整数解整数规划第16页，共41页，2022年，5月20日，14点8分，星期六17

显然，x1=5/3,x2=8/3为非整数解。为求得整数解，想办法在原约束条件的基础下引入一个新的约束条件，以保证一个或几个变量取值为整数。为此，选择分数部分较大的非整数变量，如x2

，写出如下表达式：将上式的所有变量的系数及右端常数均改写成一个整数与一个非负真分数之和的形式。上式可以改写成

若将带有整数系数的变量留在方程的左边，其余移到方程的右边，则有

由于要求变量取值为正整数，方程的左边必为整数。当然，方程的右边也应为整数。又x3≥0,x4≥0于是，必有x3≥1,x4≥1（3）（4）≤0此时，也可以选择x2-x3-2≤0，只是因为先分析出方程右端≤0整数规划第17页，共41页，2022年，5月20日，14点8分，星期六18

整理后得

为了直观地在图形上描述，可将(2)式的两个约束方程代入(5)式即ïîïíì³＝++＝+++=且为整数,0,,,;2054;62;max432142132121xxxxxxxxxxxxz则(5)式成为（5）这就是割平面的方程B(5/3,8/3)x1x2246246-20-4AECO

加入新的约束条件，便形成新的线性规划问题，其可行域为新的凸集OAEC。

即图中红色直线割去了红色直线以外的△ABE部分，其中包括原所求得的非整数最优解点B(5/3,8/3)。三个方程是等价的，任意一个都可增加的新的约束条件整数规划第18页，共41页，2022年，5月20日，14点8分，星期六19

建立割平面以后，便可以把割平面方程作为新的约束条件加到原整数规划问题(2)式中，在仍然不考虑整数条件的情况下，利用单纯形法或对偶单纯形法继续求解。以选择第一个为例，引入松驰变量x5，代入新增加的约束条件中

从上面的推导过程可以看出，新约束对原约束方程起到了这样的作用：对整数规划(1)式所对应的线性规划的可行域，保留了其中的所有整数可行解，但割掉了一部分非整数解。三个约束条件任选其一-1/3x3-1/3x4+

x5=-2/3整数规划第19页，共41页，2022年，5月20日，14点8分，星期六20

Cj比值CBXBb检验数jx1x2x3x4x5110005/3105/6-1/608/301-2/31/30-2/300-1/3-1/31x1x2x5110-13/300-1/6-1/60Cj比值CBXBb检验数jx1x2x3x4x5110000100-15/240101-2x1x2x6110-40000-1/220011-3x1＝0，x2＝4为最优解，最优值为Z＝4整数规划第20页，共41页，2022年，5月20日，14点8分，星期六21

Cj比值CBXBb检验数jx1x2x3x4x5110005/3105/6-1/608/301-2/31/30-2/300-1/3-1/31x1x2x5110-13/300-1/6-1/60Cj比值CBXBb检验数jx1x2x3x4x51100021010-1/2201-101x1x2x6110-40000-1/220011-3x1＝2，x2＝2为最优解，最优值为Z＝4另一选择第21页，共41页，2022年，5月20日，14点8分，星期六22分析因为上述的线性规划的最优解已是整数解，所以得整数规划问题（1）的最优解：E(2,2)A(0,4)x1x2246246-20-4x1=0，x2=4。此最优解位于图A点。x1=2，x2=2。此最优解位于图E点。整数规划第22页，共41页，2022年，5月20日，14点8分，星期六23【例2】求解下列整数规划问题解：引入松弛变量，写成标准形式：（1）（2）

第一步：对上述模型不考虑整数条件，用单纯形法求解相应松弛问题的最终单纯形表为Cj比值CBXBb检验数jx1x2x3x432005/2011/2-1/213/410-1/43/4x2x123-59/400-1/4-5/4最优解为x2＝5/2，x1＝13/4此最优解非整数解整数规划第23页，共41页，2022年，5月20日，14点8分，星期六24

第二步：x1

＝13/4

,x2＝5/2为非整数解，找出非整数解变量中分数部分最大的一个基变量x2，写出这一行的约束：将上式的所有变量的系数及右端常数均改写成一个整数与一个非负真分数之和的形式得：

若将带有整数系数的变量整数项留在方程的左边，其余移到方程的右边，则有

由于要求变量取值为正整数，方程的左边必为整数。方程的右边也应为整数。又由于x3≥0,x4≥0于是，有方程右端小于等于零。≤0整数规划第24页，共41页，2022年，5月20日，14点8分，星期六25

即

为了直观地在图形上描述，可将标准式的两个约束方程代入上式，则成为-(14-2x1-3x2)

–(9-2x1-x2)≤-1三个方程的任意一个都可做为后面增加的新的约束条件整理后得2x1+2x2≤11这就是割平面的方程整数规划第25页，共41页，2022年，5月20日，14点8分，星期六26

B(13/4,5/2)AEC2x1+2x2≤11F

加入新的约束条件，便形成新的线性规划问题，其可行域为新的凸集OAEFC。即图中所示的红色直线的下半部分。显然它割去了除红色直线上所有点以外的△BEF部分，其中包括原所求得的非整数最优解点B(13/4,5/2)。x1x2246246-20-4O这就是割平面的方程整数规划第26页，共41页，2022年，5月20日，14点8分，星期六27

建立割平面以后，便可以把割平面方程作为新的约束条件加到原整数规划问题中，在仍然不考虑整数条件的情况下，利用单纯形法或对偶单纯形法继续求解。

将其作为新的约束条件，加入到前面的最终表中，便形成新的线性规划问题。用对偶单纯形法求解。

第三步：引入松驰变量x5，代入新增加的约束条件中-1/2x3-1/2x4

+x5＝-1/22x1+2x2≤11任意一个都可做为增加的新的约束条件整数规划第27页，共41页，2022年，5月20日，14点8分，星期六28

Cj比值CBXBb检验数jx1x2x3x4x5320005/2011/2-1/2013/410-1/4¾0-1/200-1/2-1/21x2x1x5230-59/400-1/4-5/40Cj比值CBXBb检验数jx1x2x3x4x5110002010-117/21001-1/2x2x1x3230-29/2000-1-1/210011-2x1＝7/2，x2＝2为最优解，最优值为Z＝29/2，不是整数解第28页，共41页，2022年，5月20日，14点8分，星期六29

由于仍有非整数解，重复第二步：写出另一行的约束：将上式的所有变量的系数及右端常数均改写成一个整数与一个非负真分数之和的形式得：

若将带有整数系数的变量整数项留在方程的左边，其余移到方程的右边，则有此得到新约束：整数规划第29页，共41页，2022年，5月20日，14点8分，星期六30

2x1+2x2≤11

又加入的新约束条件，便形成新的线性规划问题，其可行域又随之改变B(13/4,5/2)AECFx1x2246246-20-4Ox1+x2≤5整数规划第30页，共41页，2022年，5月20日，14点8分，星期六31

2010-110

将其作为新的约束条件，加入到前面的最终表中，便形成新的线性规划问题。用对偶单纯形法求解。

第三步：引入松驰变量x6，代入新增加的约束条件中-1/2x5+x6＝-1/2Cj比值CBXBb检验数jx1x2x3x4x5x63200007/2100

1-1/20x2x1x3x62300-29/2000-1-1/2010011-20-1/20000-1/21新增加的约束条件整数规划第31页，共41页，2022年，5月20日，14点8分，星期六32

Cj比值CBXBb检验数jx1x2x3x4x5x63200004100

10-1x2x1x3x62300-14000-10-1300110-41010-102100001-2x1＝4，x2＝1为最优解，最优值为Z＝14，是整数解整数规划第32页，共41页，2022年，5月20日，14点8分，星期六33

E‘(1,4)因为上述的线性规划的最优解已是整数解，所以得整数规划问题的最优解：x1=1，x2=4。maxZ＝14B(13/4,5/2)AECFx1x2246246-20-4O整数规划第33页，共41页，2022年，5月20日，14点8分，星期六34【例3】求解下列整数规划问题解引入松弛变量，写成标准形式：（1）ïîïíì³＝++＝+++=,0,,,;43;1-;max432142132121xxxxxxxxxxxxz（2）对上述模型不考虑整数条件，用单纯形法求解相应松弛问题的最终单纯形表为Cj比值CBXBb检验数jx1x2x3x411003/410-1/41/47/4013/41/4x1x211-5/200-1/2-1/2ïîïíì³£+£++=且为整数,0,;43;1-;max21212121xxxxxxxxz最优解为x1＝3/4，x2＝7/4整数规划第34页，共41页，2022年，5月20日，14点8分，星期六35

显然，x1＝3/4，x2＝7/4

为非整数解。找出非整数解变量中分数部分最大的一个基变量，写出相应的约束：将上式的所有变量的系数及右端常数均改写成一个整数与一个非负真分数之和的形式。据此，上式可以改写成

若将带有整数系数的变量整数项留在方程的左边，其余移到方程的右边，则有

,4/34/14/1431=+-xxx,4/74/14/3432=++xxx,4/30)4/10()4/31()01(431+=+++-++xxx,4/31)4/10()4/30()01(432+=+++

++xxx43314/14/34/3xxxx--=-4324/14/34/31xxx--=-整数规划第35页，共41页，2022年，5月20日，14点8分，星期六36

整理后得

为了直观地在图形上描述，可将标准式的两个约束方程代入上式，则成为

由于要求变量取值为正整数，方程的左边必为整数。当然，方程的右边也应为整数。又由于x3≥0,x4≥0于是，有,04/14/34/343£--xx-3x3-x4

≤-3x2

≤1ïîïíì³＝++＝+++=且为整数,0,,,;43;1-;max432142132121xxxxxx