整数规划小结

1、上页上页下页下页返回返回整数规划v整数规划的数学模型v设置逻辑变量建立整数规划模型v分配问题与匈牙利法v分枝定界法、割平面法v应用举例上页上页下页下页返回返回匈牙利法 匈牙利法的基本思想如果效率矩阵 C 中存在 n 个位于不同行不同列的零元素,则只要令对应于这些零元素位置的决策变量xij=1,其余的决策变量xij=0,则可取到最小值0,即该分配方案最优. 如： 0141208302323020939140C100000100100000144ijxX上页上页下页下页返回返回匈牙利法 匈牙利法的计算步骤 第一步:找出效率矩阵每行的最小元素,并分别从每行中减去; 第二步:找出效率矩阵每列的最小元素

2、,再分别从每列中减去; 第三步:确定能否找出n个位于不同行不同列的零元素集合来.根据定理2,该问题转化为:要覆盖上面矩阵中的所有零元素,至少需要多少条直线;怎么得到覆盖零元素的最少直线数？从第一行开始,若该行只有一个零元素,就对这个零元素打上( )号,将打( )号零元素所在列画一条直线.若该行没有零元素或有两个以上零元素(已划去的不计在内),则转下一行,依次进行到最后一行;从第一列开始,若该列只有一个零元素就对这个零元素打上( )号(同样不考虑已划去的零元素),再对打( )号零元素所在行画一条直线.若该列没有零元素或有两个以上零元素,则转下一列,依次进行到最后一列;重复1和2两个步骤,可能出现

3、三种情况上页上页下页下页返回返回匈牙利法第一种情况 覆盖零元素的最少直线数(或打( )号的零元素个数)等于n第二种情况 打( )号的零元素个数小于n,但未被划去的零元素之间存在闭回路,这时可顺着闭回路的走向,对每个间隔的零元素打一( )号,然后对所有打( )号的零元素,或所在行,或所在列画一条直线.第三种情况 矩阵中所有零元素或被划去,或打上( )号,但打( )号的零元素个数仍小于n.上页上页下页下页返回返回v 匈牙利法 第四步:为设法使每一行都有一个打( )号零元素,需继续按定理1对矩阵进行变换： 从矩阵未被直线覆盖的数字中找出一个最小的数k; 对矩阵的每行,当该行有直线覆盖时,令ui=0,

4、无直线覆盖时,令ui=k;每行元素减去ui； 对矩阵中有直线覆盖的列,令vj=-k,对无直线覆盖的列,令vj=0;每列元素减去vj； 得到一个新矩阵；1. 第五步:回到第三步,反复进行,一直到矩阵的每一行都有一个打( )号零元素为止,即找到了最优分配方案.上页上页下页下页返回返回一般分配问题1、人数和工作任务不相等的分配问题(不平衡的分配问题) （1）人少任务多 （2）人多任务少 类似产销不平衡问题(虚设假想的人,增添假想任务)2、某项任务一定不能由某人做的分配问题 将相应的费用系数取作足够大的数M3、一个人可做几项任务的分配问题4、目标函数为求最大值(最大化的分配问题)效率矩阵中元素全为负数

5、,根据定理1,让效率矩阵中所有元素变成非负数,再利用匈牙利法求解.11maxnnijijijzc x11minnnijijijwcx上页上页下页下页返回返回 第一步第一步: 先不考虑整数约束先不考虑整数约束,解解A的松弛问题的松弛问题B,可能得到以下情况之一可能得到以下情况之一: 若若B没有可行解没有可行解,则则A也没有可行解也没有可行解,停止计算停止计算. 若若B有最优解有最优解,并符合并符合A的整数条件的整数条件,则则B的最优解即为的最优解即为A的最优解的最优解,停止计算停止计算. 若若B有最优解有最优解,但不符合但不符合A的整数条件的整数条件,转入下一步转入下一步.为讨为讨论方便论方便,

6、设设B的最优解为：的最优解为： .z), 1(,)0 , 0 ,(0)1)0(目标函数最优值为不全为整数mibbbXiTm分枝定界法分枝定界法上页上页下页下页返回返回第二步第二步: :定界定界 记记A的目标函数最优值为的目标函数最优值为z z* *, ,以以z(0)作为作为z z* * 的上界的上界, ,记为记为 = =z(0). .再用观察法找的一个整数可再用观察法找的一个整数可行解行解X X, ,并以其相应的目标函数值并以其相应的目标函数值z z作为作为z z* *的下的下界界, ,记为记为z zz z, ,也可以令也可以令z z, ,则有则有: :z*zzz分枝定界法分枝定界法上页上页下

7、页下页返回返回第三步第三步: :分枝分枝 在以上界在以上界 所对应的解所对应的解 中中, ,任选一个不符合整数条件的变量任选一个不符合整数条件的变量, ,例如例如 ( (不不为整数为整数),),以以 表示不超过表示不超过 的最大整数的最大整数. .构造构造两个约束条件两个约束条件 将这两个约束条件分别加入问题将这两个约束条件分别加入问题B B中中, ,形成形成两个子问题两个子问题B1B1和和B2B2, ,再对这两个子问题进行求解再对这两个子问题进行求解. .rbrbrb1rrrrxbxb和分枝定界法分枝定界法TmrbbbX)0 , 0 ,(1z上页上页下页下页返回返回 第四步第四步: : 修改

8、上修改上、下界下界, ,按照以下两点规则按照以下两点规则进行进行 在各分枝问题中在各分枝问题中, ,找出目标函数值最大者找出目标函数值最大者 作为新的上界作为新的上界; ; 从已符合整数条件的分枝中从已符合整数条件的分枝中, ,找出目标函找出目标函 数值最大者作为新的下界数值最大者作为新的下界. .分枝定界法分枝定界法上页上页下页下页返回返回如此反复进行如此反复进行,直到得到直到得到 为止为止,即得即得最优解最优解 X* .第五步：比较与剪枝第五步：比较与剪枝 各分枝的目标函数值中各分枝的目标函数值中,若有小于若有小于 者者,则剪则剪掉此枝掉此枝,表明此子问题已经探清表明此子问题已经探清,不必

9、再分枝了不必再分枝了;否则继续分枝。否则继续分枝。 z分枝定界法分枝定界法*zzz上页上页下页下页返回返回v 1958由由Gomory提出的一种求解整数规划问题提出的一种求解整数规划问题的方法的方法v基本思想：基本思想：v 依次引进依次引进线性约束条件线性约束条件(称称Gomory约束约束或或割平面割平面)v 切割掉问题的部分非整数解切割掉问题的部分非整数解v 直到使问题的目标函数值达到最优的整数直到使问题的目标函数值达到最优的整数点成为缩小后可行域的一个顶点点成为缩小后可行域的一个顶点割平面法割平面法上页上页下页下页返回返回 第一步：把问题中所有约束条件的系数均第一步：把问题中所有约束条件的

10、系数均化为整数化为整数, ,用单纯形法求解该整数规划对应的松用单纯形法求解该整数规划对应的松弛问题弛问题. 若松弛问题没有可行解若松弛问题没有可行解,则原整数问题也没有则原整数问题也没有可行解可行解,停止计算停止计算. 若松弛问题有最优解若松弛问题有最优解,并符合原整数问题的整并符合原整数问题的整数条件数条件,则该最优解即为原整数问题的最优解则该最优解即为原整数问题的最优解,停停止计算止计算. 若松弛问题有最优解若松弛问题有最优解,但不符合原整数问题的但不符合原整数问题的整数条件整数条件,转入下一步转入下一步. 割平面法割平面法上页上页下页下页返回返回第二步：第二步：从松弛问题的最优解中从松弛

11、问题的最优解中, ,任选一个不为整任选一个不为整数的分量数的分量x xr,r, ,将最优单纯形表中该行的系数将最优单纯形表中该行的系数 和和 分解为整数部分和小数部分之和分解为整数部分和小数部分之和, ,并以该行为源行并以该行为源行, ,按下式作割平面方程：按下式作割平面方程：rjarb nmjjrjrxff10 的小数部分的小数部分的小数部分的小数部分rjarb割平面法割平面法上页上页下页下页返回返回第三步：第三步：将所得的割平面方程作为一个新的约束将所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位列条件置于最优单纯形表中（同时增加一个单位列向量）向量）, ,用对偶单

12、纯形法求出新的最优解。用对偶单纯形法求出新的最优解。若表中得到的解仍为非整数解若表中得到的解仍为非整数解, ,重复第二步重复第二步, ,直至直至找到整数解找到整数解. .割平面法割平面法上页上页下页下页返回返回习题四4.2)10, 1( 102115 . .min0i1109625438171101i101ixxxxxxxxxxxxxtsxczxiiiiii或否则号井位参与钻探表示第设上页上页下页下页返回返回习题四4.31096109532485724679278310283)(au1=2u2=2u3=2u4=2u5=64304331026350245705618061v1=1 v2=2 v3

13、=0 v4=1 v5=132022200052400346036070403202220005240034603607040k=2上页上页下页下页返回返回习题四4.3（a）u1=0u2=2u3=2u4=2u5=21020002223022212421407040v1=0 v2=-2 v3=-2 v4=-2 v5=0320222000524003460360704012020000030400126034092601202000003040012603409260 x15=1 x23=1 x32=1 x44=1 x51=1,其余变量值为0，z=21上页上页下页下页返回返回习题四4.3642691

14、44523107496651675392)(bu1=2u2=1u3=3u4=1u5=24204703341074165540553170v1=0 v2=0 v3=0 v4=2 v5=0k=140047013410541653405511704004701341054165340551170上页上页下页下页返回返回习题四4.3（a）u1=1u2=1u3=1u4=1u5=04004710230143054231440061v1=-1 v2=-1 v3=0 v4=0 v5=-1x11=1 x22=1 x35=1 x44=1 x53=1,其余变量值为0，z=1240047013410541653405

15、5117050058002410431652305500705005800241043165230550070上页上页下页下页返回返回4.5已知下列五名运动员各种姿势的游泳成绩(各为50m)如下表.试问(a)如何从中选拔一个450m混合泳的接力队,使预期的比赛成绩为最好？(b)以4项成绩总和计算,运动员周应列第二,但选拔结果周被淘汰,从中可得到什么启示.需时(s)队员项目习题四上页上页下页下页返回返回解:非标准的分配问题,先转化成标准分配问题.习题四需时(s)队员项目111213141521222324253132333435410-11( ,1,2,3,4,5)0min37.732.938.

16、837.035.443.433.142.234.741.833.328.538.930.433.629.226ijijxi jijzxxxxxxxxxxxxxxxx设变量表示项目由运动员 完成表示项目 不由运动员 完成建立问题的数学模型为4243444541424344555151.429.628.531.10000011,2,3,4,5. .11,2,3,4,501,1,2,3,4,5ijjijiijxxxxxxxxxxis txjxi j或上页上页下页下页返回返回37.732.938.837.035.44.805.94.12.543.433.142.234.741.810.309.11.6

17、8.733.328.538.930.433.64.8010.41.95.129.226.429.628.531.12.803.22.14.70000000000CC续 ： 该 问 题 的 效 率 矩 阵 为第 三 步 ：执 行 匈 牙12345123451.61.61.61.6001.60004.805.94.12.53.204.33.50.910.309.11.68.78.707.507.14.8010.41.95.13.208.80.33.52.803.22.14.71.201.60.00000uuuuuvvvvvCC 利 法 第 一 步 和 第 二 步 ：第 四 步 ： k=1.653.

18、100000习题四上页上页下页下页返回返回12345123450.90.90.90.9000.900.903.204.33.50.92.303.43.508.707.507.17.806.606.23.208.80.33.52.307.90.32.61.201.60.53.10.300.70.52.20000000.uuuuuvvvvvCC 续 ： 第 五 步第 六 步 ： k=0.91234512345000.30.3000.3000900.902.303.43.502.30.33.43.507.806.606.27.80.36.606.22.307.90.32.62.007.6020.30

19、0.70.52.200.900.90uuuuuvvvvvCC 第 七 步 ：第 八 步 ： k=0.3.3000.40.11.900.600.90习题四上页上页下页下页返回返回2.30.33.43.50000017.80.36.606.2000102.007.602.301000000.40.11.91000000.600.9000100sCX 续 ： 第 九 步最 优 解 方 案 :周 参 加 仰 泳 ;王 参 加 蛙 泳 ;钱 参 加 蝶 泳 ;赵 参 加 自 由 泳预 期 比 赛 最 好 成 绩 为 127.8 .习题四上页上页下页下页返回返回习题四4.6分配甲、乙、丙、丁四个人去完成A

20、、B、C、D、E五项任务.每个人完成各项任务的时间如表所示.由于任务数多于人数，故考虑：(1)任务E必须完成.其它4项可任选3项完成。(2)其中一人完成两项.其他每人完成一项。(3)任务A由甲或丙完成.任务C由丙或丁完成.任务E由甲、乙或丁完成.且规定4人中乙或丁完成两项任务.其他每人完成一项；试分别确定最优分配方案.使完成任务的总时间最少。上页上页下页下页返回返回习题四 解：1) 这是不平衡的分配问题，首先转换为标准型，再用匈牙利法求解。由于任务数多于人数，所以假定一名虚拟人，设为戊。因为工作E必须完成，故设戊完成E的时间为M(M是非常大的数)，其余效率系数为0，则标准型效率矩阵表为：上页上

21、页下页下页返回返回习题四 解续：用匈牙利法求出最优分配方案为：即甲-B，乙-D，丙-E，丁-A，任务C放弃，最少时间为105h。0100000010000011000000100X上页上页下页下页返回返回4.6续： （2） 考虑其中一人完成两项，其他每人完成一项。试确定最优分配方案，使完成任务的总时间最少。 解：虚拟戊，戊这一行数为相应列的最小数，则标准型效率矩阵表为：上页上页下页下页返回返回习题四 解续：用匈牙利法求出最优分配方案为：即甲-B，乙-C、D，丙-E，丁-A，最少时间为131h。0100000100000011000000010X 上页上页下页下页返回返回v4.6续 分配考虑任务

22、A由甲或丙完成，任务C由丙或丁完成，任务E由甲、乙或丁完成，且规定4人中乙或丁完成两项任务，其他每人完成一项。试确定最优分配方案，使完成任务的总时间最少。解：虚拟戊，戊这一行数为（M，38，36，20，33），则标准型效率矩阵表为：上页上页下页下页返回返回习题四 解续：用匈牙利法求出最优分配方案为：即甲-A，乙-D、E，丙-B，丁-C，最少时间为141h。1000000010010000010000001X 上页上页下页下页返回返回4.9 分别用分枝定界法和割平面法求解下列整数规划问题.且为整数, 0,35763-. .97max)(21212121xxxxxxtsxxza)4 , 1(035

23、763-. .97max42132121ixxxxxxxtsxxzi将它的松弛问题化为标准型：列初始单纯形表最终单纯形表上页上页下页下页返回返回习题四4.94.9题续：题续：( (分枝定界法分枝定界法) )因因松弛问题的解不是整数解松弛问题的解不是整数解, ,需需继续进行分枝继续进行分枝, ,加入约束条件加入约束条件x x2 233，当前界为：，当前界为：630z上页上页下页下页返回返回习题四（a）续：这一枝对应的解为：x1=32/7，x2=3，目标函数值z=59.上页上页下页下页返回返回习题四（a）续：另一枝加入约束条件x24这一枝无可行解,综合起来可重新定界为：0Z59上页上页下页下页返回

24、返回（a）续：需继续进行分枝,加入约束条件x14上页上页下页下页返回返回（a）续：加入约束条件x14这一枝对应的解为：x1=4，x2=3，目标函数值z=55.上页上页下页下页返回返回（a）续：加入约束条件x15上页上页下页下页返回返回（a）续：加入约束条件x15这一枝的目标函数值35小于左边枝的55，应不予考虑。所有的分枝都讨论完，修改上下界都应该为55，上界等于下界，即max Z Z=55，对应的最优解为x1 = 4, x2 = 3。上页上页下页下页返回返回4.9(a)续：且为整数, 0,35763-. .97max)(21212121xxxxxxtsxxza)4 , 1(035763-.

25、.97max42132121ixxxxxxxtsxxzi将它的松弛问题化为标准型：列初始单纯形表最终单纯形表上页上页下页下页返回返回4.9(a)续：续：(割平面法割平面法)找出非整数解变量中分数部分最大的找出非整数解变量中分数部分最大的一个基变量，写下这一行的约束，再将生成的割平面条件一个基变量，写下这一行的约束，再将生成的割平面条件加入松弛变量，然后加最终单纯形表中：加入松弛变量，然后加最终单纯形表中：21221227143sxx上页上页下页下页返回返回4.9(a)续：重新将生成割平面条件，并加入松弛变量续：重新将生成割平面条件，并加入松弛变量再加入当前单纯形表中：再加入当前单纯形表中：74

26、7671214ssx上页上页下页下页返回返回4.9 分别用分枝定界法和割平面法求解下列整数规划问题.且为整数, 0,30561652. .max)(21212121xxxxxxtsxxzb给出它的松弛问题B,用图解法求解上述线性规划问题B.12121212:max2516. . 6530,0Bzxxxxs txxx x上页上页下页下页返回返回图解法： 、 、 、 、 、 、 、 、 、 、 、0 1 2 3 4 5 6 7 8 9 108 -7 -6 -5 -4 -3 -2 -1 -B12( 0 ):3.51.85.3Bxxz不是原问题的解但 ( 0 )zz3 . 5, 4zz定界：0,305

27、61652max:21212121xxxxxxxxzB上页上页下页下页返回返回分枝： 12(0):3.51.85.3Bxxzz3:11xB4:12xB356,0zz 0 1 2 3 4 5 6 7 43213:11xB2BB0,30561652max:21212121xxxxxxxxzB上页上页下页下页返回返回1212121121: max2+5166530. . 3,0Bzxxxxxxs txxx0,4 30 561652.max:2211212121xxxxxxxtsxxzB接下来求出（接下来求出（B1）和（）和（B2）的最优解即可。）的最优解即可。v 分枝后原B问题转化成B1和B2两个子

28、问题.上页上页下页下页返回返回图解法： 0 1 2 3 4 5 6 7 43213:11xB00.500.200.3:)1(211zxxB20.520.100.4:)2(212zxxB2 . 553 . 54zzzz和和修改上下界：2B12(0):3.51.85.3Bxxz13x 14x 上页上页下页下页返回返回图解法： 0 1 2 3 4 5 6 7 43213:11xB16.500.116.4:)21(2121zxxB无可行解:22B16. 552 . 55zzzz和和修改上下界：2B212(2 ):4.01.25.2Bxxz21x22x上页上页下页下页返回返回121212121221:

29、max2+5166530. . 4 1,0Bzxxxxxxs txxxx0,2 4 30 561652.max:222121212121xxxxxxxxtsxxzBv 分枝后原B2问题转化成B21和B22两个子问题.上页上页下页下页返回返回图解法： 0 1 2 3 4 5 6 7 43213:11xB00.500.100.4:)211(21211zxxB00. 500. 000. 5:)211(21212zxxB00. 5516. 55zzzz和和修改上下界：2B2112(2):4.161.005.16Bxxz14x 15x 上页上页下页下页返回返回分枝定界的全过程：3.580.150.3:)0(21zxxB00.500.200.3:)1(211zxxB20.5