搜索
第五章整数规划第一节整数规划数学模型及解的特点第二节割平面法第四节0-1型整数规划第五节指派问题1/68第一节整数规划模型及解的特点一、整数规划模型一般形式2/683/68Maxz=CXs.t.AX≤或=或≥bX≥0，b≥0C=(c1,c2,…,cn)X=(x1,x2,…,xn)T有些或全部xj取整数b=(b1,b2,…,bm)Ta11a12…a1nA=a21a22…a2n.........mnam1am2…amn4/68若对决策变量不提整数要求，则上述规划问题称为该整数规划问题的松弛问题。若松弛问题是线性规划问题，则该整数规划问题叫做整数线性规划。整数线性规划有如下几种类型：1.纯整数线性规划——全部决策变量须取整数，亦称全整数规划。2.混合整数线性规划——部分决策变量须取整数。3.0-1型整数线性规划——决策变量只取0或1的整数线性规划。5/68二、整数规划之例[例1]某商场拟用集装箱托运两种货物，每箱体积、重量、可获利润以及所受限制如下表。问：两种货物各托运多少，利润最大？货物体积立方米/箱重量百斤/箱利润千元/箱服装5220玩具4510托运限制24136/68用x1和x2将表示服装和玩具的托运箱数，则该问题可表示如下：Maxz=20x1+10x2(1)s.t.5x1+4x2≤24(2)2x1+5x2≤13(3)x1，x2≥0，(4)x1，x2取整数(5)7/68[例2]某地区要建水电站，有15处可行，可用资金总额为B。各处所需投资和预期收益分别为aj和cj(j=1,3,…,15)。要求是：若在第一处建，第二处也要建；但是，第二处建；第一处不一定建；第三和第四处至少有一处必须建；第五、六和第七处建两个。问：如何在这15处布置水电站，才能预期最大收益？8/68用xj=1表示在第j处建水电站，用xj=0表示不在第j处建水电站，则上述问题可表示成：Maxz=𝒄𝒋𝒙𝒋𝟏𝟓𝒋=𝟏s.t.𝒂𝒋𝒙𝒋𝟏𝟓𝒋=𝟏≤Bx2≥x1x3+x4≥1x5+x6+x7=2xj=1或0，j=1,2,…,159/68[例3]现有A1和A2生产某产品，在B1、B2、B3和B4销售。因供不应求，计划再建一厂。新厂有方案A3和A4，建成后年生产费用分别为1200和1500万元。从产地到销地运费见下表。问哪一方案使新厂建成后年运费与生产费用总和最少？B1B2B3B4产能（千吨/年）A12934400A28357600A37612200A44525200需求量（千吨/年）35040030015010/68用A3还是A4，待定。如何计算新厂建成后年运费与生产费用总和？y=1表示用A3，y=0表示用A4。分别用xij和cij表示从Ai到Bj的运量和单位运费，z表示年运费与生产费用总和，Minz=𝒄𝒊𝒋𝒙𝒊𝒋𝟒𝒋=𝟏𝟒𝒊=𝟏+1200y+1500(1-y)s.t.𝒙𝒊𝟏𝟒𝒊=𝟏=350，𝒙𝒊𝟐𝟒𝒊=𝟏=400，𝒙𝒊𝟑𝟒𝒊=𝟏=300，𝒙𝒊𝟒𝟒𝒊=𝟏=150，𝒙𝟏𝒋𝟒𝒋=𝟏=400𝒙𝟐𝒋𝟒𝒋=𝟏=600，𝒙𝟑𝒋𝟒𝒋=𝟏=200y，𝒙𝟒𝒋𝟒𝒋=𝟏=200(1-y)xij≥0，y=1或0xj=1或0，j=1,3,…,1511/68三、解的特点整数线性规划的解一定是松弛问题的解，可行域是松弛问题可行域的子集。目标函数值不会超过松弛问题目标函数值。反过来，不一定成立。不能将松弛问题的解四舍五入当作整数线性规划的解。xj=1或0，j=1,3,…,1512/68现在看托运问题：Maxz=20x1+10x2s.t.5x1+4x2≤242x1+5x2≤13x1，x2≥0，x1，x2取整数先用图解法解松驰问题，得13/684x1x23225x1+4x2=24z=20x1+10x2=96z=15oA(4.8,0)2x1+5x2=136z=90(4,1)z=1014/68最优解是(x1,x2)=(4.8,0)Maxz=96再看整数规划问题，若取x1=5，x2=0，破坏了约束条件5x1+4x2≤24若取x1=4，x2=0，z=20x1+10x2=80，实际上，(x1,x2)=(4,1)也是可行解，z=90可见，将松弛问题的解四舍五入不能求得整数线性规划的解。第二节解整数规划的割平面法就是在解松驰问题过程中逐一去掉非整数解域，寻找整数解的方法，也就是“切割”可行域平面。切割的办法是增加约束条件。15/68He(born7May1929inBrooklyn)isanappliedmathematician.HeworkedatIBMasaresearcherandlaterasanexecutiveandhisresearchledtothecreationofnewareasofappliedmathematics.Afterhiscareerinthecorporateworld,hebecamethepresidentoftheAlfredP.SloanFoundation,whereheoversawprogramsdedicatedtobroadeningpublicunderstandinginthreekeyareas:theeconomicimportanceofscienceandresearch;theeffectsofglobalizationontheUnitedStates;andtheroleoftechnologyineducation.16/68RalphEdwardGomory17/68[例1]Maxz=x1+x2s.t.-x1+x2≤13x1+x2≤4x1，x2≥0，x1，x2取整数先用图解法解松驰问题，得18/68x1x2211-x1+x2=1z=x1+x2=2.5o4/33x1+x2=4A(3/4,7/4)C(1,1)R19/68最优解是(x1,x2)=(3/4,7/4)Maxz=10/4整数点C不是顶点，所以目标函数就向非整数点A呼啸而去，若将C改成顶点，就可能拦截目标函数。20/68x1x2211-x1+x2=1o4/33x1+x2=4C(1,1)整数点C已经改成顶点，但还拦不住目标函数。DAR’21/68x1x2211-x1+x2=1o4/33x1+x2=4C(1,1)再切一次，整数顶点C拦住了目标函数。DBAR’’22/68如何构造用来切割平面的直线呢？在松弛问题约束条件中添加松弛变量：-x1+x2+x3=13x1+x2+x4=4x1，x2≥0，然后，列出初始单纯形表：23/68cj1100θicBxBB-1bx1x2x3x40x31-1110-0x44[3]1014/3z1100σj0x37/30[4/3]11/37/41x14/311/301/34z02/30-1/3σj24/68cj1100θicBxBB-1bx1x2x3x41x27/4013/41/41x13/410-1/41/4z10/400-1/2-1/2σj从中可得到x1-x3/4+x4/4=3/4x2+3x3/4+x4/4=7/4将其中的系数和常数项均分解成整数和非整数两部分：25/68可得到x1-x3=3/4-(3x3/4+x4/4)x2–1=3/4-(3x3/4+x4/4)从-x1+x2+x3=13x1+x2+x4=4可知，x1和x2若是非负整数，x3和x4也是非负整数。所以，根据x1-x3=3/4-(3x3/4+x4/4)x2–1=3/4-(3x3/4+x4/4)左边判断，3/4-(3x3/4+x4/4)应当是整数，26/68而(3x3/4+x4/4)是正数，一定要比3/4大，两者之差才可能是整数，即，必须有3x3/4+x4/4≥3/4，-3x3-x4≤-3，添加松弛变量x5后得到：-3x3-x4+x5=-3，叫做切割方程，将其添加到最终单纯形表中，得cj11000θicBxBB-1bx1x2x3x4x51x27/4013/41/401x13/410-1/41/400x5-300[-3]-11z---1/2/-3-1/2/-1-σj/alj27/68最终单纯形表已经得到整数线性规划最优解。(x1,x2,x3,x4)=(1,1,1,0)，Maxz=2。cj11000θicBxBB-1bx1x2x3x4x51x2101001/41x111001/3-1/120x310011/3-1/3z2000-1/3-1/6σj/alj28/68建立切割方程步骤：1.从松弛问题中选择数值为分数（小数）的基变量xi，从最终单纯形表中找到：xi+𝒂𝒊𝒌𝒙𝒌𝒌=(B-1b)i其中i是基变量编号，k是非基变量编号。2.将aik和(B-1b)i分解为整数N和非负真分数f之和:(B-1b)i=Ni+fi，其中0fi1aik=Nik+fik，其中0≤fik1Ni表示不大于(B-1b)i的最大整数，例如(B-1b)i=2.35，Ni=2，fi=0.35(B-1b)i=-0.45，Ni=-1，fi=0.5529/68于是，xi+𝒂𝒊𝒌𝒙𝒌𝒌=(B-1b)i变成xi+𝑵𝒊𝒌𝒙𝒌𝒌-Ni=fi-𝒇𝒊𝒌𝒙𝒌𝒌3.建立决策变量和松弛变量为非负整数的条件。上式左边是整数，右边也应为整数，但是，fi-𝒇𝒊𝒌𝒙𝒌𝒌fi1，所以，fi-𝒇𝒊𝒌𝒙𝒌𝒌≤0添加松弛变量后便得到切割方程。经验表明，在最终单纯形表中选取具有最大真分数（小数）部分的非整分量所在行构造切割方程，可提高效率。上述方法是Gomory于1958年提出的。缺点是有时候收敛慢，常和其他方法配合使用。30/68[例2]用Gomory切割法求解如下问题。Maxz=3x1-x2s.t.3x1-2x2≤35x1+4x2≥102x1+x2≤5，x1，x2为非负整数。先解松驰问题Maxz=3x1-x2+0x3+0x4-Mx5+0x6s.t.3x1-2x2+x3=35x1+4x2-x4+x5=102x1+x2+x6=5x1，x2≥031/68cj3-100-M0θicBxBB-1bx1x2x3x4x5x60x33[3]-210003/3-Mx510540-11010/50x652100015/2z5M+34M-10-M00初始单纯形表3x111-2/31/3000--Mx550[22/3]-5/3-11015/220x6307/3-2/30019/7z022M/3-5M/3-M0032/683x116/11102/11-1/11-0--1x215/2201-5/22-3/22-0-0x631/2200-3/22[7/22]-131/7z00-17/222/11-0cj3-100-M0θicBxBB-1bx1x2x3x4x5x63x113/7101/70-2/7-1x29/701-2/70-3/70x431/700-3/71-22/7z30/700-5/70--3/733/68构造切割方程，13/7、9/7和31/7中真分数最大的是13/7，对应最终单纯形表中第一行，所以，选取x1+x3/7+2x6/7=13/7x1-1=6/7-x3/7-2x6/7-x3/7-2x6/7≤-6/7添入松弛变量x7得-x3/7-2x6/7+x7=-6/7将其添入上面的最终单纯形表，得34/683x113/7101/702/70-1x29/701-2/703/700x431/700-3/7122/700x7-6/700-1/70[-2/7]1z00503/2cj3-10000θicBxBB-1bx1x2x3x4x6x73x11100001-1x2001-1/2003/20x4-500[-2]10110x63001/201-7/2001/400-35/68cj3-10000θicBxBB-1bx1x2x3x4x6x73x11100001-1x25/4010-1/40-5/40x35/2001-1/20-11/20x67/40001/41-3/4z7/4000