第五章-运筹学整数线性规划

第五章整数线性规划第五章整数线性规划第1节整数线性规划的数学模型及解的特点第2节分支定界解法第3节0-1型整数线性规划第4节指派问题第1节整数线性规划的数学模型及解的特点一、整数线性规划的含义要求一部分或全部决策变量必须取整数值的线性规划问题。第1节整数线性规划的数学模型及解的特点二、整数线性规划的数学模型1112max(min)()12012njjjnijjijjnzcxaxbimxjnxxx或或，或，，，，，，，，，，，中部分或全部取整数第1节整数线性规划的数学模型及解的特点整数线性规划的松弛问题不考虑整数条件，由余下的目标函数和约束条件构成的线性规划问题。第1节整数线性规划的数学模型及解的特点三、整数线性规划的解的特点整数线性规划问题的可行域是它的松弛问题可行域的子集整数线性规划问题的可行解是它的松弛问题的可行解整数线性规划问题最优解的目标函数值不优于它的松弛问题最优解的目标函数值第1节整数线性规划的数学模型及解的特点四、整数线性规划的解法例1：某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表所示。问两种货物各托运多少箱，可使获得利润为最大？货物体积（米3/箱）重量（百公斤/箱）利润（百元/箱）甲5220乙4510托运限制2413第1节整数线性规划的数学模型及解的特点例1：解：设x1，x2分别为甲、乙两种货物的托运箱数maxz=20x1+10x25x1+4x2≤242x1+5x2≤13x1，x2≥0x1，x2整数第1节整数线性规划的数学模型及解的特点A松弛问题的最优解第1节整数线性规划的数学模型及解的特点A整数线性规划问题的最优解第1节整数线性规划的数学模型及解的特点例2：某宝石加工厂最近新到6粒大小、质量等级相似的钻石毛料，管理层有两种选择，一是切磨成一般的皇冠形，每粒可获利2.5千元；一是切磨成虽然较难切磨但当前市场较流行的心形，每粒可获利4千元。若切磨成皇冠形则每粒需要5个工作日，若切磨成心形则每粒需要9个工作日，由于工厂切工师傅较忙，最多只有45个工作日来做这批工作。另外，由于毛料自身形状的关系，其中只有4粒毛料可以切磨成皇冠形，而6粒毛料中任何一粒都可以切磨成心形。那么，管理层应如何决策才能使这批钻石获利最大？第1节整数线性规划的数学模型及解的特点例2：解：设x1，x2分别为切磨成皇冠形和切磨成心形的钻石粒数maxz=2.5x1+4x2x1+x2≤65x1+9x2≤45x1≤4x1，x2≥0x1，x2整数第1节整数线性规划的数学模型及解的特点完全枚举法对于可行域有界的整数线性规划问题，整数线性规划的可行解是一个有限集，将这个集内的每一个点对应的目标函数值都一一计算出来，然后从中找出最优者，则为整数线性规划的最优解。第1节整数线性规划的数学模型及解的特点小结（1）对整数线性规划问题的松弛问题的最优解中不符合整数要求的分量进行简单地取整，所得到的整数解可能不一定是整数线性规划问题的最优解，甚至也不一定是整数线性规划问题的可行解（2）对于复杂的模型，完全枚举法费时，甚至不可能实现第2节分支定界解法一、分支定界解法的思路分支定界解法是先求解整数线性规划的松弛问题，如果其最优解不符合整数条件，则用增加约束的办法求出整数线性规划问题的上下界，并把松弛问题的可行域分成互不重叠的子区域，再求解这些子区域的松弛问题，不断缩小整数线性规划问题上下界的差距，最后取得整数线性规划问题的最优解。第2节分支定界解法二、分支定界解法的含义分支定界解法是一种部分枚举法，通过不断地分割松弛问题的可行域并进行比较，最终求得整数线性规划问题的最优解。第2节分支定界解法三、分支定界解法的步骤第一步：求解松弛问题。（1）松弛问题无可行解，则整数线性规划问题无可行解，计算停止；（2）松弛问题有最优解，并且符合整数线性规划问题的整数条件，则松弛问题的最优解就是整数线性规划问题的最优解，计算停止；（3）松弛问题有最优解，但是不符合整数线性规划问题的整数条件，则松弛问题的最优值是整数线性规划问题最优值的上界值（求极大时）或下界值（求极小时），下界值（求极大时）可暂定为-∞或上界值（求极小时）可暂定为+∞。第2节分支定界解法第二步：分支。在松弛问题的最优解中任选一个不符合整数条件的变量xi，其值为bi，用[bi]表示小于bi的最大整数，构造以下两个约束条件：将这两个约束条件分别加入整数线性规划问题，形成两个子问题，再求解这两个子问题的松弛问题。+1iiiixbxb和第2节分支定界解法第三步：定界。以每个子问题的松弛问题为一分支标明求解的结果，与其他问题的解的结果相比较：（1）若解满足子问题的整数条件，则找到了一个整数线性规划问题的可行解，为新的下界值（求极大时）或上界值（求极小时）；（若计算中同时出现两个及以上整数线性规划问题可行解，则选取其中最大（求极大时）或最小（求极小时）的一个保留）（2）若解不满足子问题的整数条件，则为新的上界值（求极大时）或下界值（求极小时）。（若所有子问题的最优解都不是整数线性规划问题可行解，则选取边界值最大（求极大时）或最小（求极小时）的子问题进一步再细分子问题，并求解）第2节分支定界解法第四步：比较与剪支。各分支的目标函数值中，若小于下界值（求极大时）或大于上界值（求极小时），则剪去该分支（用打×表示）；若大于下界值（求极大时）或小于上界值（求极小时），且不符合整数条件，则回到第二步，对该分支继续分支。若除保留下来的可行解外，其余分支都被剪去，则该可行解是整数线性规划问题的最优解。第2节分支定界解法要求：用分支定界解法求解下列整数线性规划问题。例3：maxz=3x1+2x22x1+3x2≤14x1+0.5x2≤4.5x1，x2≥0x1，x2整数第2节分支定界解法例4：maxz=x1+4x2-2x1+3x2≤3x1+2x2≤8x1，x2≥0x1，x2整数第2节分支定界解法小结分支定界法：仅检查可行的整数组合的一部分，从而定出最优整数解。作业5-1作业5-1：用分支定界解法求解例2。maxz=2.5x1+4x2x1+x2≤65x1+9x2≤45x1≤4x1，x2≥0x1，x2整数第3节0-1型整数线性规划一、整数线性规划问题的类型1、纯（全）整数线性规划：全部决策变量都必须取整数值的整数线性规划第3节0-1型整数线性规划例5：某服务部门各时段（每2h为一时段）需要的服务员人数见下表。按规定，服务员连续工作8h（即四个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。时段12345678服务员最少数目10891113853第3节0-1型整数线性规划例5：解：设在第j时段开始时上班的服务员人数为xj。123451121231234234534545512345min108911138530zxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx，，，，，且均取整数值第3节0-1型整数线性规划2、0-1型整数线性规划：决策变量只能取值0或1的整数线性规划（1）0-1型变量的含义变量只能取值0或1。（2）0-1型变量的特点表示是或否表示系统是否处于某个特定状态表示决策时是否取某个特定方案当问题含有多项要素，每项要素都有两种选择表示二进制变量第3节0-1型整数线性规划例：令10PxPP，当决策取方案时，当决策不取方案时（即取时）第3节0-1型整数线性规划例：设问题有有限项要素E1，E2，…，En，其中每项Ej有两种选择Aj和，（j=1，2，…，n）。令jA1(12)0jjjjjEAxjnEA，若选择，，，，若选择第3节0-1型整数线性规划例：变量x可取0与9之间的任意整数。令0123012301232222901xxxxxxxxx其中，，，均为变量第3节0-1型整数线性规划例6：现有资金总额为B。可供选择的投资项目有7个，项目j所需投资额和预期收益分别为aj和cj(j=1,2,…,7)。此外，由于种种原因，有三个附加条件：第一，若选择项目1，就必须同时选择项目2。反之，则不一定；第二，项目3和4中至少选择一个；第三，项目5，6和7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？第3节0-1型整数线性规划例6：解：11270jjxjj，对项目投资设（，，，），对项目不投资112134567max1201127njjjnjjjjzcxaxBxxxxxxxxj或（=，，，）第3节0-1型整数线性规划3、混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划第3节0-1型整数线性规划例7：工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1，B2，B3，B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij（i，j=1，2，3，4）见下表。工厂A3或A4开工后，每年的生产费用估计分别为1200万元或1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用（即全部物资运费和新工厂生产费用之和）最少。BjAiB1B2B3B4生产能力（kt/年）A1A2A3A42934835776124525400600200200需求量（kt/年）350400300150第3节0-1型整数线性规划例7：解：34123410ijijxABijAyA设为由运往的物资数量（，，，，），若建工厂设，若建工厂44111121314112223242132333431424344411121314212223243132333441424344min12001500135040030015040060020020010ijijijijzcxyyxxxxxxxxxxxxxxxxxxxxxxxxxxxxyxxxxyx(1234)01ijy，，=，，，或第3节0-1型整数线性规划二、0-1型整数线性规划的解法1、完全枚举法定义：含有n个变量，产生2n个可能的变量组合（每一个组合即变量取值为0或1），比较目标函数值确定最优解特点：适于变量个数n≤10的0-1型整数线性规划第3节0-1型整数线性规划2、隐枚举法定义：只检查2n个可能的变量组合的一部分，确定问题的最优解第3节0-1型整数线性规划解题思路（1）某个变量组合不满足其中一个约束条件时，就不必再去检验其他约束条件是否可行（2）确定一个可行解的目标函数值：对于目标函数值比它差的变量组合就不必再去检验它的可行性；对于目标函数值比它好的变量组合再去检验它的可行性第3节0-1型整数线性规划解题步骤第一，按目标函数中各变量系数的大小顺序排列各变量，然后把约束条件做相应的调整。第二，在表中列出变量取值的全部组合（2n个），并分别计算各自的目标函数值。第三，以第一个可行解计算得出的目标函数值作为一个过滤条件，比较表中其它目标函数值与该过滤条件：比它差的变量取值组合舍弃；比它好的变量取值组合保留，并检验约束条件，同时以其计算得出的目标函数值作为新的过滤条件替换上一个过滤条件。重复这个过程，直至所有变量取值组合的目标函数值都比较完成，从而得到最优解。第3节0-1型整数线性规划要求：用隐枚举法求解下列0-1型整数线性规划。例8：maxz=3x1-2x2+5x3x1+2x2-x3≤2x1+4x2+x3≤4x1+x2≤34x1+x3≤6x1，x2，x3=0或1第3节0-1型整数线性规划例8：解：maxz=-2x2+3x1+5x32x2+x1-x3≤24x2+x1+x3≤4x2+x1≤34x1+x3≤6x1，x2，x3=0或1第3节0-