第五章整数规划

《第五章整数规划》由会员分享，可在线阅读，更多相关《第五章整数规划（19页珍藏版）》请在装配图网上搜索。

1、word第五章整数规划主要内容：1、分枝定界法；2 、割平面法；3 、0 1型整数规划；4 、指派问题。重点与难点：分枝定界法和割平面法的原理、求解方法，0-1型规划模型的建立与求解步骤，用匈牙利法求解指派问题的方法和技巧。要求：理解本章内容，熟练掌握求解整数规划的方法和步骤，能够运用这些方法解决实际问题。 1问题的提出要求变量取为整数的线性规划问题，称为整数规如此问题简称 IP丨。如果所有的变量都要求 为非负整数，称之为纯整数规划或全整数规划；如果仅一局部变量要求为整数，称为混合整数 规划。例1求解如下整数规划问题maxz 20x110x25x1 4x2242x1 5x213x1, x20x

2、1, x2为整数如果不考虑整数约束，就是一个线性规划问题称这样的问题为原问题相应的线性规划问题 很容易求得最优解为：花 4.8, X20 , maxz 96。50 / 16用图解法将结果表示于图中画“ +号的点都是可行的整数解，为满足要求，将等值线向原点方向移动，当第一次遇到“+号点Xi4 , X21时得最优解为为 4 , x2 1，最优值为z=90。由上例可看出，用枚举法是容易想到的，但常常得到最优解比拟困难，尤其是遇到变量的取值 更多时，就更困难了。下面介绍几种常用解法。 2分枝定界法分枝定界法可用于解纯整数或混合的整数规划问题。根本思路：设有最大化的整数规划问题 A,与之相应的线性规划问

3、题B,从解B开始，假如其最优解不符合 A的整数条件，那么B的最优值必是A的最优值 Z 的上界，记为 Z ;而A的任意可行解的目标函数值是 Z 的一个下界 Z， 采取将B的可行域分枝的方法，逐步减少Z和增大z，最终求得z*。现举例说明：maxz40X90x29x17x2567x120x270X1,X20例2求解AX1 ,X2为整数解：先不考虑条件，即解相应的线性规划B-，得最优解Xi4.81,X21.82,wordZ0356见如下图显然，它不符合整数条件。这时，zo为问题A的最优值z*的上界，记z zo，而xi 0, X2 0显然是问题A的一个整数可行 解，这时z=0，是z*的一个下界，记z 0

4、，即0 z* 256。分枝定界法的解法，首先注意其中一个非整数变量的解，如Xi，在B中=4.81，于是对原问题增加两个约束条件：Xi 4、xi 5，可将原问题分解为两个子问题 Bi、B2即两枝，给每枝增加一5i / i6显然未得到全部变量是整数解，ZiZ2，将 z 改为 349 z =349，冋题Bi问题B2zi 349z234ixi 4xi5X2X2word0 z*349。继续对问题Bi、B2进展分解，ZiZ2,先分解Bi为两枝，增加条件X22的问题称为B3 ；增加条件x2 3的问题称为B4 o在上图中再去掉x2 2与X2 3之间的可行域，再求解问题 B3、B4，其结果列在如下图中，可见问题

5、 B3的解已都是整数，它的目标函数值Z3 340， 取z =340,而它大于z4 327，所以再分解B4已无必要，而问*题B2的Z2341，所以Z可能在340 z341之间有整数解，于是再对B2分解,得问题B5,B6，B5为非整数解，且Z5308 Z3，问题B6为无可行解，于是可断定:*z3 z z 340，x14, x22为最优整数解。67 / 164 xi 5冋题B2Xi5X2Z234iz 0 , z 349问题B3X22 x23问题B4问题BXix2z 0 , Z 356z0356Xi问题Bixi 4X2zi 349z 341340 z z*由以上解题过程可得到分枝定界法的求解步骤:1.

6、 给定原问题的初始上界z解与原问题A相应的线性规划问题B,可能出现以下情况之一： B没有可行解，这时A也没有可行解，如此停止； B有最优解，并符合A的整数条件，B的最优解即为A的最优解，如此停止; B有最优解，但不符合A的整数条件，记它的目标函数值z0为z。2. 给定原问题的初始下界z用观察法找出问题A的一整数可行解，一般取Xj 0, j 1,2, ,n。求得其目标函数值，记作z。 这样，就有z z* z。3. 分枝在B的最优解中任选一个不符合整数条件的变量Xj，其值为bj，以bj表示小于bj的最大整数，构造两个约束条件：Xj bj和 Xj bj 1并将其分别参加问题B,求两个后继规划问题B1

7、、B2，不考虑整数条件，解这两个后继问题。4. 定界修改上、下界以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界z，从已符合整数条件的各分支中，找出目标函数值的最大者作为新的下界z。5. 比拟与剪枝各分枝的最优目标函数值中假如有小于 z者，如此剪掉这枝，以后不再考虑了，假如大于z，且不符合整数条件，如此继续分枝直到得到 z* z为止，求得最优整数解x*(j 1,2, ,n)。 3割平面法这个方法的根底仍是用解线性规划的方法去解整数规划问题，首先不考虑变量Xj是整数这个条件，但增加线性约束条件用几何术语，称为割平面使得由原可行域中切割掉一局部，这

8、局部 只包含非整数解，但没有切割掉任何整数可行解。 这个方法就是指出怎样找到适当的割平面 不见 得一次就找到，使切割后最终得到这样的可行域，它的一个有整数坐标的极点恰好是问题的最优 解。例3求解如不考虑条件，求得相应的线性规划的最优解:3X1, X24710,max z44就是图中可行域将原问题化为标准型max z %X20X3 0X4X! X23%x2Xj 0 j Xj为整数X341,2,4X4j 1,2,4maxzX1x2X1X213x1X24X1,X20X1,X2整数不考虑整数条件，用单纯形法求解相应线性规划的最优解。110 0CBXbB X1X2X3X40X31- 11100X4431

9、01j111X13/410-1/41/41X27/4013/41/4j-1/2-1/2表最终表3 75x1, x2, max z 4 42由最终表中得到变量间的关系式：113Xl 产343 17x2x3x44 44将系数和常数项都分解为整数和非负真分数之和，并移项变为14x4X2现考虑整数条件，X1,X2为非负整数，那么X3,X4也是非负整数。对上式，从等式左边看是整数,等式右边的是正数，所以等式右边定一为负数，即专 I40整理得：3X3 X43-切割方程将新的约束方程，引入松驰变量，得到3X3 X4X53，将其列入最终表11000CBbX1X2X3X4X51X13/4-11-1/41/401

10、X27/4313/41/400X5-300-3-11j-1/2-1/21X111001/31/121X2101001/40X31001-1-1/3j-1/3-1/6最优解X(1,1,1,0,0)T ，最优值z=2一、割平面法的解题步骤：1假如abi中有分数，先全部整数化，而后引入松驰变量，暂不考虑整数约束条件， 形法求出相应线性规划的最优解。2. 求切割方程 令人是相应线性规划最优解中为分数值的一个基变量，由最终单纯形表得到xiaikxk bi1k其中：i QQ指构成基变量下标的集合k K K指构成非基变量下标的集合 将bi和aik都分解成整数局部N与真分数f之和，即bi Ni fi ,其中

11、0 fi 12aikN ik fik，其中 0 fik 1而N表示不超过b的最大整数，如：b=- 0.45,女口此 N=-将2代入1得XNik Xk Ni fifikXkkk 现在提出变量为整数的条件，上式由左边看必是整数，由右边看，因为0 fi 1为正，即fifikXk 0 割线方程k3. 把切割方程作为新的约束条件，并入单纯形最优表。继续换算，取得最优解。二割平面法的性质1. 害平面法割去了整数规划原问题相应的线性规划问题的最优解。2. 割平面未割去整数规划原问题的任一可行解，即未割去其相应的线性规划问题的任一 可行解。用单纯所以不能整数 4 0- 1规划、0-1变量与其应用0-1型整数规

12、划是整数规划的特殊情形，它的变量为仅取值0或1,这时Xi称为0-1变量，或 称二进制变量。0-1变量作为逻辑变量logical variable ,常用来表示系统是否处于某个特定 状态，或者决策时是否取某个特定方案。例如1X0当决策取方案P时当决策不取方案P时(即取P时)当问题含有多项要素，而每项要素皆有两种选择时，可用一组0-1变量来描述。一般地，设问题有有限项要素E1,E2, ,En，每项Ei有两种选择A和Ai(i 1,2, ,n)，如此可令1Xi0若Ei选择Ai-(i 1,2,n)若Ej选择Ai那么，向量(兀山2,Xn)T就描述了问题的特定状态或方案，即(1,1,1,1)T,若选择(A1

13、,A2, ,An 1, An)T(1,1,1,0)T,若选择(A1,A2,An 1, An)T(X1X,Xn)T(1,0, ,0,0)T,若选择(A1,A2, ,An 1,An)T (0,0, ,0,0)T,若选择(A1 , A2 , , An 1, An)T1、选址问题-相互排斥的计划例4某公司拟在市东、西、南三区建立门市部，拟议中有7个位置Ai (i 1,2, ,7)可供选择,规定在东区，由A,A2,A3三个点中至多项选择两个;在西区，由A4,A5两个点中至少选一个；在西区，由A6, A7二个点中至少选一个如选用A点，设备投资估计为bi元，每年可获利润估计为Ci元，但投资总额不能超过 B元

14、,问应选择哪几个点可使利润为最大？解：先引入0- 1变量xi (i 1,2,7)令Xi1,2,7)1 ,当Ai点被选用.0 ,当Ai点未被选用(i7于是问题可列成：max zcixiXi X2X3X4 X51X6X71Xi0或 12、相互排斥的约束条件例5.某厂决定生产两种产品，有两种加工方法可供选用，设备供给情况:方法III每日可供使用工时ABABd1543212d2128问选用哪种加工方法收益最大。解：设A产品的日产量为X1，B产品的日产量为X2假如采用I，其约束条件：5x1 4x2 12假如采用II，其约束条件:3x1 2x212x1 2x28由于最终只能选用一种方法，我们引入0-1变量

15、和一个任意大的正数 M1 ,选用I时0，选用II时于是，上述约束条件可变为：5x1 4x2 12 (1 y)M3x1 2x2 12 yMx1 2x28 yM假如选用第一种方法生产，如此y=1，约束条件就变成5X1 4X2 12，其余的约束条件就失去了作用；假如选用第二种方法生产，如此 y=0,第一个约束条件由于右侧多了一个 M成了多余的限 制。注意：引入的变量y不必出现在目标函数内，即认为在目标函数中y的系数为0。3、关于固定费用问题(Fixed cost Problem)例6某厂生产某种产品，有几种生产方式可供选择，如选定的生产方式投资高自动化程度 高的设备，由于产量大，因而分配到每件产品的

16、变动本钱就降低，反之，分配到每件产品的变动本钱就可能增加，所以应全面考虑。设有三种方式可供选择，令Xj表示采用第j种方式时的产量Cj表示采用第j种方式时每件产品的变动本钱kj表示采用第j种方式时的固定本钱如此采用各种方式的总本钱分别为Pjkj CjXj , Xj0xj00 j123引入0-1变量和任意大的正数M令1 ,采用第j种生产方式，即xj 00 ,不采用第j种生产方式，即xj 0于是目标函数min z (ki yiC1X1) (k2 y2 C2X2) (ksy3 C3X3)约束条件Xj yiM , j1,2,3当Xj 0时,yi1 ； 当 Xj0时，yi 0,才有意义。二、0- 1规划的

17、解法解0-1规划最容易想到的方法，就是穷举法，即检查变量取值为0或1的每一种组合，比拟目 标函数值以求得最优解，这就需要检查变量取值的2n个组合。对于变量个数n较大如n10时,，下面举例说明这种方法。是不可能的。因此，人们设计一种方法，只检查变量取值的组合的一局部，就能求到问题的最优解， 这种方法称为隐举法Implicit Enumerationmaxz 3x1 2x2 5x3例7解题时，先通过试探的方法找一个可行解，容易看出(X1，X2，X3)(1,0,0)就适合1-5条X12X2X32(1)X14XX 34(2)X1X23(3)4 X1X36(4)X1 , x2,x30或1(5)件，计算出

18、相应的目标函数值z=3。我们求最优解，对于极大化问题，当然希望z 3，于是增加一个约束条件:3x1 2x2 5x33 0 个，假如用全部枚举的方法，3个变量8个解，原来4个约束条件，共需32次运算；现增加了过 滤条件，如按隐枚举法，就可减少运算次数。后加的条件称为过滤条件(Filteri ng Con strai nt)，这样，原问题的线性约束条件就变成5将5个约束条件按0-4顺序排好，对每个解，依次代入约束条件左侧，求出数值，看 是否适用不等式条件，如某一条件不适合，同行以下各条件就不必再检查，因而就减少了运算次数。 计算过程列表如下：占八、条件是否满足条件？ 是/否XZ值(0)(1)(2)

19、(3)(4)(0,0,0)0X(0,0,1)5-1101V5(0,1,0)-2X(0,1,1)315X(1,0,0)31110V3(1,0,1)80211V8(1,1,0)1X(1,1,1)626X最优解(x1,x2,x3)(1,0,1)，最优值 max z 8注意：在计算过程中，假如遇到Z值已超过条件0右边的值，应改变条件0，使右边为当前 为止最大者，如当检查点(0,0,1)时，因z=5(3)，所以将条件0换成3x1 2x2 5x35(0)这样对过滤条件的改良，更可以减少计算量。 5指派问题在实际工作中经常遇到这样的问题：某单位需完成 n项任务，恰好有n个人可承当这些任务。 由于每人的专长不

20、同，各人完成任务不同或所费时间，效率也不同。于是产生应指派哪个人去 完成哪项任务，使完成n项任务的总效率最高或所需时间最少的问题，这类问题称为指派问题 或分派问题。一、指派问题的数学模型例8有一份说明书，需译成英、日德、俄四种文字。现有甲、乙、丙、丁四人，他们将说明 书翻译成不同文字所需时间单位：小时如下表，问应指派何人去完成何工作，使所需总时间最 少？人员、.央日德俄甲215134乙1041415丙9141613丁78119类似有：有n项加工任务，怎样指派到n台机床上分别完成的问题；有n条航线，怎样指定n 艘船去航行问题等等。对应每个指派问题，需有类似上表的数表，称之为效率矩阵或系数矩阵，其

21、元素 Cj 0（i,j 1,2, ,n）表示指派第i个人去完成第j项工作时的效率或时间、本钱。我们引入0- 1变量，令1 ,指派第i人去完成第j项任务xij 0，不指派第i人去完成第j项任务数学模型当问题要求极小化时：min zxiicij xiji j,n(1)j 1 ,j1,2,xij 1, i1,2,n(2)jxij1或03约束条件1说明第j种任务只能由1人去完成；约束条件2说明第i个人只能完成1项任务。二、指派问题的解法1. 指派问题最优解的性质：假如从系数矩阵（Cj）的一行列各元素中分别减去该行列的最小元素，得到新矩阵 （bj）, 那么以（bj）为系数矩阵求得的最优解和用原系数矩阵求

22、得的最优解一样。根据这个性质，可使原系数矩阵变换为每行每列中均有0元素的新系数矩阵，并使这几个 0元素位于不同行或不同列，如此令相应的 Xj 1,其余的Xj全为0,这样就得到了最优解，这种解 法称为匈牙利法。2. 解指派问题的步骤：1使系数矩阵经变换各行各列中都出现 0元素。 每行各元素减去该行最小元素； 每列各元素减去该列最小元素。假如某行列已有0元素，就不必再减了。2min2151314201311(Cij )10414154601011914161390574781197014242 min013706069c(bj)(II)053201002用最少的直线划去所有0元素，当所划直线数l=

23、n矩阵阶数时，就可得到最优方案7630初始指派。用最少的直线画去II中的所有0元素。0(III)0元素。920l =n=4，已得到最优方案假如得不到最优方案，需进展改良。A、未被划去的所有元素减去其中最小元素，以便得到新的50541030B横、竖直线交叉处的所有元素增加 A中所减的最小元素以防止重复指派和消除等不正当 指派，得到新矩阵，并以最少直线划去所有 0元素。如：0 0 4 00 0 4 03 2 0 03 2 0 0 A0 14 2-28 0 4 08 0 4 03最优方案确实定 0元素最少的行列先指派使 0元素所在格的Xj 1: 所有行、列只有一个x 1，其余Xj 0。对例8,由矩阵

24、III先指派X22 1,X31 1，然后指派X14 1兀3 1。即派甲译俄文、乙译日 文、丙译英文、丁译德文，所需总时间最少，min zCjXj C31 C22 C43 C1428小时i j三、特殊的指派问题1、极大化的指派问题maxzqXji j令bjMCj，M等于q中最大元素，如此系数矩阵可变换为B(bj)bj 0符合匈牙利法的条件min zbj x nMCj xi ji j这样就将极大化问题化为极小化问题了。例9有四台机器分别完成四项任务，完成不同任务的效率见下表，问如何分派任务才能使效 率最高？效率机器J、任务B1B2B3B4A3594A6754A32585A8261min64 056

25、405解：(bj) (M q)人数和事数不等的指派问题假如人少事多，如此添上一些虚拟的“人。这些虚拟的“人做各事的费用系数可取0,理解为这些费用实际上不会发生。假如人多事少，如此添上一些虚拟的“事。这些虚拟的“事被 各人做的费用系数同样也取0。 一个人可做几件事的指派问题假如某人可做几件事，如此可将该人化作一样的几个“人来承受指派。这几个“人做同的一件事的费用系数当然都一样。4、某事不能由某人做的指派问题2 452102374 141630317 38106273 min6-4-0-21-0-0-6-3-0-00-6-n Z.-4l n 4先指派X131，X411，然后指派X221 , X341,即最优指派为AB3, A2B2, A3B4，ABio最大效率maxz C|3 c22C34 c419 7 5 8 29假如某事一定不能由某个人做，如此可将相应的费用系数取作足够大的数M