2013参考数学建模常用方法整数规划

第二章整数规划1．整数规划的基本概念2．分枝定界法解整数规划3．０－１规划4.指派问题的解法第一节概述人们探讨某些线性规划问题，有时必须把全部或部分决策变量限制为整数。这样的线性规划问题，通常称为整数规划。作为线性规划的特殊情况，整数规划也有最小化和最大化之别。此外，整数规划还可以分成纯整数规划和混整数规划。二者的区别在于：前者的决策变量必定全部取整数。而后者的决策变量只是部分取整数。例1某医药公司现有两个制药厂A1和A2，三个销售店B1、B2和B3。公司打算由两个拟建的制药厂A3和A4中选择一个，来兴建新厂。各销售店每周药品需求量见表2-1。各制药厂每周药品产量和每箱药品运费见表2-2。新厂投产后，估计每周的操作费（含折旧费）：A3是100元，A4是120元。在两个拟建的制药厂中，应当选择哪个呢？销售店需求量（箱/周）B150B260B330产量制药厂(箱/周)运资(元/箱)B1B2B3A150323A2701058A3201310A420453表2－1表2－2设：制药厂Ai每周运到销售店Bj的药品为xij箱（i=1,2，3，4；j=1，2，3）；;,1,,0u33兴建新厂表示在兴建新厂表示不在AA;,1,,0v44兴建新厂表示在兴建新厂表示不在AA解：建立数学模型两个老厂A1和A2及一个新厂A3和A4每周的总费用为y元。新厂厂址的选择应该确保y达到最小值。于是，y是目标函数，xij、u和v都是决策变量。它们之间的关系可以表述为：y=3x11+2x12+3x13（A1每周的运费）+10x21+5x22+8x23（A2每周的运费）+x31+3x32+10x33（A3每周的运费）+4x41+5x42+3x43（A4每周的运费）+100u（A3每周的操作费）+120v（A4每周的操作费）(1)u和v全是0－1变量：约束条件：x11+x12+x13≤50x21+x22+x23≤70x31+x32+x33≤20ux41+x42+x43≤20vu,v=0,1(2)由A3和A4选择一个来兴建新厂：u+v=1(3)每个制药厂每周运到各销售店的药品不会超过其产量：(4)每个销售店每周药品的需求量能够得到各制药厂的充分供应：（5）药品箱数一定取非负值：xij≥0x11+x21+x31+x41=50x12+x22+x32+x42=60x13+x23+x33+x43=30例1的数学模型为：Miny=3x11+2x12+3x13+10x21+5x22+8x23+x31+3x32+10x33+4x41+5x42+3x43+100u+120vx11+x12+x13≤50x21+x22+x23≤70x31+x32+x33≤20ux41+x42+x43≤20vx11+x21+x31+x41=50x12+x22+x32+x42=60x13+x23+x33+x43=30xij≥0(i=1,2,3,4;j=1,2,3)u,v=0,1本数学模型属于最小化混整数规划例2某医疗器械厂生产A1和A2两种产品。出厂前，每种产品均须经过两道工序：先用机器B1制造，后由机器B2包装。每台产品的利润和加工时间见表2-3。在下周内，机器B1和B2分别可以使用45小时和6小时。问怎样安排下周的生产任务，才能使所获利润最大？解：建立数学模型设：在下周产品A1和A2分别生产x1合和x2合，所获利润为y百元。例2的数学模型为：产品利润（百元/合）加工时间（小时/合）B1B2A1551A2891,2,1,0,645958521212121xxxxxxxxyMax表2-3最大化纯整数规划其中：“xk´为整数”,称为整数条件。njjjxCyMaxMin1nkkjnjijij,x,xxxnk,,kx,n,,jx,,ib,xa211;;21为整数21021一般地，可把整数规划的数学模型写为：整数规划问题及其数学模型一律简称为整数规划；整数规划删去整数条件之前和之后，分别称为原整数规划和相应线性规划。按照四舍五入的规则，使相应线性规划的最优解整数化，在通常情况下，不能作为原整数规划的最优解。这可以从两个方面来说明：其一、相应线性规划的最优解化整后，已经不是原整数规划的可行解，当然也就不可能是它的最优解。其二、相应线性规划的最优解化整后，虽然是原整数规划的可行解，但是有可能不是它的最优解。例2是最大化纯整数规划，其相应线性规划为：0,645958521212121xxxxxxxxyMax下面求解这个相应线性规划。我们采用图解法。,2,1,0,645958521212121xxxxxxxxyMax并且最优解是：(x1,x2)=（2.25,3.75）。按照四舍五入的规则，将这个最优解整数化，就得到：(x1,x2)=（2，4）。它对应于点D，而点D却位于可行域R之外，因此,D（2，4）不是例2的可行解。从而，D（2，4）也不可能是例2的最优解。容易断定，点A（0，5）才是例2的最优解。图解法:相应线性规划的可行域R为图中的四边形OABC，5x1+9x2=45x1+x2=6B(2.25,3.75)D(2,4)x2ox19C(6,0)RA最优解A(0,5)整数规划常用的解法是分枝定界法和割平面法。一旦遇到仅含两个决策变量的情况，可以采用图解法，其计算方法与线性规划图解法大同小异，就不再赘述。求解整数规划不宜采用枚举法。第二节分枝定界法分枝定界法可以用来求解纯整数规划和混整数规划，它是整数规划的常用解法。分枝定界法可以划分为三步。现就每一步的主要特征、理论依据和具体作法说明如下：第一步第一步的具体作法是：首先，删去整数条件，把原整数规划化成相应线性规划。其次，求解相应线性规划。最后，如果相应线性规划的最优解也是原整数规划的最优解，那么整个计算过程即告结束；否则，便转入第二步。实现放宽之后，能够得到三个结论：原整数规划的可行域真包含于相应线性规划的可行域。不失一般性，单就最大化问题而言（下同），原整数规划的最优值不大于相应线性规划的最优解。若相应线性规划的最优解满足原整数规划的整数条件，则它也是原整数规划的最优解。主要特征就是放宽。指通过删去整数条件，把原整数规划化成相应线性规划。第二步主要特征是分枝。从相应线性规划的最优解中，任意选择一个不满足原整数规划整数条件的决策变量xj=bj。以使相应线性规划增加一个约束条件；xj小于bj的最大整数（或xj大于bj的最小整数），因而得到两个新的线性规划，称为分枝。其中每个新的线性规划，统称为枝。经过分枝之后，就有如下结论：原整数规划的可行域真包含于两枝可行域的并集。原整数规划的最优解不大于两枝最优值的最大值。第二步的具体作法是：先列出两枝各自的数学模型，后计算每枝的最优解和最优值。第三步主要特征就是定界，由各枝的最优值中选最大值，称为定界。而该最大值，称为界。最优值称为界的枝，称为界枝。完成定界之后，即可得到这样的结论：若界枝的最优解满足原整数规划的最优条件，则它也是原整数规划的最优解。第三步的具体做法为：进行定界，找出界枝。若界枝的最优解就是原整数规划的最优解，则计算过程便告结束；否则，回到第二步。解：它是例2的数学模型，并且属于最大化纯整数规划。为便于叙述，我们将其记作A。现在利用分枝定界法求解之。,2,1,0,645958521212121xxxxxxxxyMax例3利用分枝定界法求解：A放宽：由A得到相应线性规划，记作B。采取图解法或单纯形法，求得B的最优解（x1,x2）=（2.25,3.75）最优值ymax=41.25。0,645958521212121xxxxxxxxyMaxBB的最优解不满足A的整数条件，所以它并非A的最优解。0,36459585212212121xxxxxxxxxyMax分枝：由B的最优解中，选择决策变量x2=3.75，按照既定的原则写出B的两枝：0,46459585212212121xxxxxxxxxyMax把它们依次记作B1和B2。解B1得：最优解（x1，x2）=（3，3）,最优值ymax=39解B2得：最优解（x1，x2）=（1.8,4）,最优值ymax=41B1B2Bx1=2.25x2=3.75y=41.25B1x1=3x2=3y=39B2x1=1.8x2=4y=41x2≤3x2≥4已完成的求解过程和所得到的计算结果可用框图来表示，见下图。定界：由图可知。界为max{39，41}=41。于是界枝是B2。但是，B2的最优解不满足A的整数条件，从而它不是A的最优解。因此，应当再次分枝。第二次分枝：由B2的最优解中，选择决策变量x1=1.8，写出B2的两枝：0,1464595852112212121xxxxxxxxxxyMax0,2464595852112212121xxxxxxxxxxyMax解B21得：最优解（x1，x2）=（1，4），最优值ymax=40.不难判断，B22无可行解。B21B22至此，已完成的求解过程和所得到的计算结果运用框图来表示，如图所示：Bx1=2.25x2=3.75y=41.25B1x1=3x2=3y=39B2x1=1.8x2=4y=41B21x1=1x2=40/9y=365/9B22无可行解x2≤3x2≥4x1≤1x1≥2第三次分枝：0,414645958521212212121xxxxxxxxxxxyMax0,514645958521212212121xxxxxxxxxxxyMax解B211得：最优解（x1,x2）=（1,4）,最优值ymax=37。解B212得：最优解（x1,x2）=（0,5）,最优值ymax=40。B212B211第二次定界：由上图可知，界为max{39，365/9}=365/9。界枝为B21.因为B21最优解不满足A的整数条件，不是A的最优解。9442x由B21最优解中，选择变量把B21分成两枝：现在，已完成的求解过程和所得到的计算结果见下图：Bx1=2.25x2=3.75y=41.25B1x1=3x2=3y=39B2x1=1.8x2=4y=41B21x1=1x2=40/9y=365/9B22无可行解x2≤3x2≥4x1≤1x1≥2B211x1=1x2=4y=37B212x1=0x2=5y=40x2≥5x2≤4第三次定界：由上图可知，界为max{39,37,40}=40.所以，界枝是B212。由于B212的最优解满足A的整数条件，它一定也是A的最优解。于是，原整数规划的最优解为：（x1，x2）=（0，5），最优值ymax=40。例3是一个利用分枝定解法求解纯整数规划问题，其基本步骤也适用于混整数规划问题。A1A2A3A4A5A6A7A8需要量（根）钢管数（根）2.9211100001002.1021032101001.510130234100料头长度（米）0.10.30.901.10.20.81.4例4某卫生防疫站准备做100套钢架。每套钢架均由长为2.9米、2.1米和1.5米的钢管各一根所组成。已知原料长7.4米。如何下料方能使原料最省？解：原料的下料方式如下表。设按照方式Aj下料的原料有xj根（j=1，2，…，8）；所用原料为y根。于是，本下料问题的数学模型是：8,,2,1,2,1,01004323100232100287643176532432187654321jxxxxxxxxxxxxxxxxxxxxxxxxyMinj这是最小化纯整数规划，利用分枝定界法解之。采取单纯形法来求解。可知最优解（x1，x2，x3，x4，x5，x6，x7，x8）=（40，20，0，0