第三章整数线性规划

第三章 整数线性规划【教学内容】整数线性规划问题举例、整数线性规划模型及其求解的困难性、可用线性规划求解的整 数线性规划问题、求解整数线性规划问题的Gomory割平面法、求解整数线性规划问题的分 枝定界方法、 01 规划问题举例、 01 规划问题的解法、整数线性规划问题的一些例子、 用LINGO软件包求解整数线性规划问题。【教学要求】要求学生熟悉整数线性规划模型，能熟练地掌握求解整数线性规划问题的Gomory割平 面法和分枝定界方法；熟悉并会求解 01 规划问题，能够建立整数线性规划模型并用软件 求解整数线性规划问题。【教学重点】整数线性规划模型，Gomory割平面法，分枝定界方法，01规划问题。【教学难点】Gomory 割平面法，分枝定界方法， 01 规划问题的求解。【教材内容及教学过程】整数线性规划（Integer Linear Programming，简记为ILP）问题研究的是要求变量取整数 值时，在一组线性约束条件下一个线性函数最优问题，是应用非常广泛的运筹学的一个重要 分支。其中变量只取 0 或 1 的整数线性规划问题称为 01 规划。只要求部分变量取整数值 的线性规划称为混合整数线性规划。整数线性规划与线性规划有着密不可分的关系，它的一些基本算法的设计都是以相应 的线性规划的最优解为出发点的。但是变量取整数值的要求本质上是一种非线性约束，因此 解整数线性规划的“困难度”大大超过线性规划，一些著名的“困难”问题都是整数线性规 划问题。本章主要介绍整数线性规划一些基本概念、基本理论、实际背景及常用算法。第一节 整数线性规划模型11 整数线性规划问题举例例311 工地上需要长度为l , l ,l的钢材数分别为b , b ,b根，取长为l的1 2 m 1 2 m 原材料进行截取。已知有 n 种截取方案：A =（a aa ）， i = 1,2, ni1i2 imi其中，a .表示一根原料用第i种方案可截得长为I.的钢材的根数（i -1，2， n，jijj 二 1,2,m ),因此l a +1 a +1 1i2 2 i+1 a l， i = 1,2, nm mi下料问题就是在满足要求：截取长度为l , l ,l的钢材数分别为b ,b ,b根时,1 2 m1 2 m用的原料材根数最少的方案。假定x表示按方案A截取用的原钢材数目，于是问题表示为:iimin z = x + x + x12厂a x + a x +11 112 2 a x + a x +21 122 2 -S.t b1n n 1+ a x b2 n n 2(3.1.1)a x + a x + a x bm1 Tm 2mn n mx 0,整数，i = 1, ni在许多实际问题中，我们所研究的量具有不可分割的性质，如人数、机器数、项目数等; 而开与关、取与舍、真与假等逻辑现象都需要用取值仅为0或 1的变量来进行数量化的描述 涉及这些量的线性规划问题，非整数的解答显然不合乎要求。12 整数线性规划模型及其求解的困难性考虑如下形式的整数线性规划问题 ILPmin cTxAx = b、门(3丄2)s.t 0、x为整数向量其中 A = (a )，c = (c ,c ,c )T，b = (b ,b ,b )T 以及x = (x ,x ,x )T，A，j mxn1 2n1 2m1 2nb，c中的元素皆为整数。在(3.1.2沖除去x为整数向量这一约束后，就得到对应的标准线 性规划问题min cTxAx = b(3.1.3)s.f vx 0称(3.1.3)是(3.1.2)的松弛问题。如果(3.1.2)对应的标准线性规划问题(3.1.3)的最优解是整数，则它也是(3.1.2)的最优解。对于标准线性规划问题，已有有效的算法。那么能不能通过求解 对应的线性规划问题，然后将其解舍入到最靠近的整数解呢？考察图 3.1.1 所示的情况，可以看出舍入方法是不可取的。整数点的数目就是有限的，可否用枚举法来解ILP问题呢？对一般ILP问题，枚举法是无能(49)!为力的。如50个城市的旅行售货员问题(见例3.4.4),所有可能的旅行路线个数为宁， 这是一个天文数字。由上可见，求解整数线性规划问题ILP比求解对应的线性规划问题LP要困难得多。事实上，整数线性规划模型并不是线性模型。仅以01规划而言，决策变量取值为0或1 这 个约束是可以用一个等价的非线性约束(3.1.4)x (1 一 x ) = 0, j = 1,njj来代替的。因而变量限制为整数本质上是一个非线性约束。第二节 求解整数线性规划问题的常用方法从 1959 年 R.E.Gomory 提出解整数线性规划的割平面算法至今，经过几十年的努力， 已经发展起来了一些常用算法，如各种类型的割平面算法、分枝定界算法、解01 规划的 隐枚举法、分解方法、群论方法、动态规划方法等等，本节主要介绍求解整数线性规划问题 的几个常用算法。21 可用线性规划求解的整数线性规划问题可用线性规划问题求解的整数线性规划问题，实际上是这样的一类问题，它的解就是 线性规划解，即可以通过单纯形法来求整数规划的解。定义321矩阵A二(a )，若它的任一子行列式的值均为0 , 1或者-1，则称这样 ij mxn的矩阵为幺模矩阵。幺模矩阵的所有元素都是0， 1或者一1。定理321若A = (a )是幺模矩阵，B是由A中的m个列向量组成的矩阵，若B可j mxn逆，则B -1的所有元素都是0 , 1或者-1。定理3.2.2若A = (a )是幺模矩阵，B是由A中的m个列向量组成的可逆矩阵，j mx nx = B-1b，若b是整数，则x是整数。BB因此，对于规划问题(3.1.2),若系数矩阵A = (a ) 为幺模矩阵，且右端项b是整数， ij mx n则可以用单纯形方法直接求解对应的标准线性规划问题(3.1.3)，就可以得到它本身的最优整 数解。2. 2求解整数线性规划问题的Gomory割平面法1、整数线性规划问题与其对应的松弛问题的关系解整数线性规划问题的割平面法有多种类型，但它们的基本思想是相同的。以下我们 介绍Gomory割平面法。它在理论上是重要的，被认为是整数线性规划的核心部分。设(3.1.2)的可行域为D,对应的松弛问题(3.1.3)的可行域为Do (多面凸集)，当D北0 时它是由有限个或可数的整数点构成的集合。问题(3.1.2)和问题(3.1.3)之间具有如下明显的 关系：(1) . D u D ；0(2) .若问题(3.1.3)无可行解，则问题(3.1.2)无可行解；.问题(3.1.3)的最优值是问题(3.1.2)的最优值的一个下界；(4).若问题(3.1.3)的最优解x0是整数向量，则x0是问题(3.1.2)的最优解。2、割平面法的基本思想用单纯形法先解松弛问题(3.1.3)，若问题(3.1.3)的最优解x0是整数向量，则x0是ILP 问题(3.1.2)的最优解；若问题(3.1.3)的最优解x0的分量不全是整数，设法构造一个线性约束 条件(称它为割平面条件)，新增加的这个割平面条件将问题(3.1.3)的可行区域D。割掉一块， 且这个非整数解x0恰好在被割掉的区域内，而原ILP问题(3.1.2)的任何一个可行解(整数点) 都没有被割去。给问题(3.1.3)增加这个约束条件，用得到的问题替换问题(3.1.3)，继续以上 过程。3、Gomory割平面法的割平面条件用单纯形方法求解问题(3.1.2)的松弛问题(3.1.3)，得到最优基本可行解x0，设它对应的 基为B = (A ,A )，x，,x为基变量，基变量的下标集合为S，非基变量的下标 BBBB1m1m集合为S。最优解所对应的问题(3.1.3)是min z =工匚 x + z-j j 0jwSs.t x + 工 a x - b , i -1, m(3.2.1)Bi- ij j ijeS 为使符号简便计，令x - z， a =匚，b - z。如果b , i - 0,1, m，全是整数，已B00 j j 00i经得到了问题(3.1.2)的最优解x0 ；否则至少有一个b不是整数(0 l m)，设b所对应的约束方程是Bl+工a x- lj j jwS(3.2.2)我们用a表示不超过a的最大整数，则有(3.2.3)a = a + f , j G S jj_ ijijb = b + flll其中f ( 0 f 1, j g S )是a的分数部分；f( 0 f 1 )是b的分数部分。由于ljljljlll方程(3.2.2)中的变量是非负的，因此有工a x 工 a xlj j-ijjjGSjGS(3.2.4)从而方程(3.2.2)变为x + 工a x bBi- ij jijGS(3.2.5)因为x为整数向量，故(325)式左端为整数，所以右端用b的整数部分去代替后，(3.2.5)式 的不等式关系仍成立，即有(3.2.2)减去(3.2.6)，得x +a x b - b jljjiijGS(3.2.6)(3.2.7)注意到(3.2.3)关系式，我们得到线性约束工 f x f_ ij ji(3.2.8)jGs称它为对应于生成行1的Gomory割平面条件。将(328)改写为(引进松弛变量s )超平面方程(329)(3.2.9)_工 f x + s = - fij jijGs称它为割平面。将割平面(3.2.9)加到问题(3.2.1)，就得到了一个新的线性规划问题，且已经 具有满足最优性条件的基本不可行解。定理3.2.3如果把割平面(3.2.9)加到问题(3.2.1)中，那么没有割掉问题(3.1.2)的任何整 数可行点，当b不是整数时，新问题是一个满足最优性条件的不可行基本解。i4、 Gomory 割平面法计算步骤第1 步 求解问题(3.1.3)。若问题(3.1.3)没有最优解(包括无可行解和无有限最优解)， 则问题(3.1.2)也没有最优解；若问题(3.1.3)有最优解x0，且x0是整数向量，则x0是问题(3.1.2) 的最优解，输出X0 ；否则转第2步。第2步 任选x0的一个非整数分量b (0 l m)，按关系式(3.2.2)和(3.2.3)得到割平 面方程-工 f x + s = -f(3.2.10)-j j1jws第3步 将(3.2.10)加到第1步所得的问题(3.1.3)的最优形式(3.2.1)中，用对偶单纯形法 求解这个问题。若其最优解为整数解，则它是问题P)的最优解，输出这个最优解；否则将 这个最优解重新记为X0，返回第2步。若对偶单纯形算法发现了对偶问题是无界的，此时 原 ILP 问题是不可行的。23 求解整数线性规划问题的分枝定界方法 分枝定界法可用于解纯整数线性规划和混合整数线性规划，它是目前求解整数线性规划 的成功方法之一。本节介绍该方法的基本思想和计算步骤。1、 分枝定界方法的基本思想分枝定界法是以“巧妙”的枚举问题(3.1.2)的可行解的思想为依据设计的。 与割平面方法类似，求解不是直接针对问题(3.1.2)，而是求解它的松弛问题(3.1.3)。设 问题(3.1.3)的最优解为x0，则ctx0是问题(3.1.2)的最优值的一个下界。若x0的某个分量x0i不是整数，由于问题(3.1.2)的整数最优解的第i个分量必定落在区域x xo +1中，因此可将原问题(3.1.2)分为两个子问题来求解。这两个子问题是： iimin cT x Ax = bx 0(3.2.11)s.t x 为整数向量x 0(3.2.12)s.t x 0 + 1ii这两个子问题将问题(3.1.2)的可行域分成两部分，且把不满足整数要求的问题(3.1.3)的 最优解x0排斥在外。这一步称为分枝。分别用(3.2.11)和(3.2.12)代替原问题(3.1.2),贝V分枝 过程一直可以进行下去。每得到松弛问题的一个解，都会修正原问题目标函数最优值的下界。假设在某一时刻，到当时为止所得到的最好的满足整数要求解的目标函数值是z(目m标函数最优值的一个上界)，而且我们正打算由某一点xk分枝，该点所对应的ILP的下界为 z = CTXk，若z z，这意味着点xk的所有后代得到的各个解X的目标函数值均有 kk mCTx z zkm因此无须由Xk继续分枝。在这种情况下，我们说Xk已被剪枝。这个过程可以“巧妙”地减 少一些不必要的分枝。总之，分枝定界方法的思想是按照下面三步进行的：第一步，通过求解松弛问题对原问题进行分枝；第二步，通过每个松弛问题的最优目标函数值对原问题的目标函数值定界； 第三步，一旦某个松弛问题的最优解是整数，就得到原问题最优解的一个近似，其目 标函数值就是原问题目标函数值的一个近似值(上界)。如果以后某个松弛问题的最优目标 函数值比这个近似值大，那么这个松弛问题及它的所有子问题都不用求解了。之所以说分枝定界方法是“巧妙”的枚举方法，主要是因为“剪枝”步骤，通过“剪 枝”步骤就不用枚举问题的所有可行解。2、 分枝定界法计算步骤第1 步 求解问题(3.1.3)。若问题(3.1.3)没有最优解(包括无可行解和无有限最优解)，则问题(3.1.2)也没有最优解;若问题(节叫有最优解x0，且x0是整数向量，则x0是问题(3.1.2) 的最优解，输出x0 ；否则，令 ：=hU ：=+s，x :二，转第2步。第2步 若。二，则转第7步，否则，选择一个分枝点xk eQ，Q :=Q ixk ；第3步 解xk对应的松弛问题，若此问题无解，转第2步；第4步 若xk对应的松弛问题的最优值z U，则点xk被剪枝，转第2步；k第5步 若xk对应的松弛问题的最优解x0为整数，则U： = ctx0，x := x0，转第2步;第6步若xk对应的松弛问题的最优解x0不是整数，按x0某个非整数分量生成x0的 两个分枝点x0i和x02，令Q :=QU01u02，转第2步；第7步 若x :=，U ：=+s，贝卩原ILP问题无解；否则，x为原ILP问题的最优解, U 是最优值，计算停止。分枝定界法的思想不仅适用于解ILP问题，也适用于任何组合最优化问题。第三节 01 规划问题及其求解方法01 规划是整数规划中的特殊情况，它的变量仅取值0或 1。31 01 规划问题举例例3.3.H1某部门在今后五年中可用于投资的资金总额为B万元，有n(n 2)个可以 考虑的投资项目，假定每个项目最多投资一次，第j个项目所需的资金为万元，将会获 得的利润为c .万元。问应如何选择投资项目，才能使获得的总利润最大。1，设投资决策变量为xj科0,决定投资第/个项目；j=1 决定不投资第个项目；,n设获得的总利润为z，则上述问题的数学模型为max z =工 c xjjj=10 工 b x Bjjj=1x = 0 或 1，j = 1, j,n(3.3.1)显然，问题(3.3.1)是一个01规划。32 01 规划问题的解法 由于01规划问题的特殊性，虽然上面介绍过的割平面方法和分枝定界方法都可以用来求解，但是正是由于它的特殊性，这里介绍专门用来求解01规划问题的一些方法。 1、DFS 搜索法DFS是Depth First Search的缩写，即深度优先搜索的意思。典型的思想可以从下面例 子看出。例3.3.2用DFS搜索法求解0-1整数规划问题max z = x + x + x123f2x - 6x + 6x -4(3.3.2)St 123I x , x , x = 0或 1123首先确定搜索树假定自上而下的搜索顺序为t，9引进栈S用以记录搜索过程, 栈是按后进先出的顺序来建立数据结构。属于s栈的变量定义为固定变量。FNS，属于F的变量定义为自由变量。s = x = x = 0, x = 1，作为约定栈顶兀素为x = 0，中间3123为x =0，栈底为x = 1。若从S中取走栈顶元素，则取出的是x = 0,取走之后的S为1 23 x = 0, x = 1 ，栈顶元素则为 x = 0 。1 2 1搜索空间即搜索树(如图3.3.1 所示)。1) S = x = 0, k = 1，由于x = 0 , x和x不论为0或1均不能满足 2 2 1 32x -6x + 6x -4。故x = 0应放弃。1 2 3 22) S = x = 1，前进一步 S = x = 0, x = 1，再前进一步2 1 2S = x = 0, x = 0, x = 1， k = 3， z = 1。 3123) 从栈顶元素 x = 0 后退，改为 S = x = 1, x = 0, x = 1 ， k = 3 。3 3124) S =x =1,x =0,x =1不满足约束，应放弃。3125) S = x = 1,x = 1，前进一步为S = x = 0, x = 1,x = 1，应放弃。123126) 进入S =x =1,x = 1,x = 1，不满足约束，应放弃，故后退。直到k = 0,312停止。故得最优解 x = 1, x = x = 0, z = 1 。2132、隐枚举法隐枚举法是通过建立过滤条件而使计算工作量大为减少的穷举法，用下面的例题加以 说明。(3.3.3)例 3.3.3 用隐枚举法求解0 -1整数规划问题max z = 3x 一 2x + 5x123x + 2 x 一 x 2(1)123x+ 4 x+ x 4(2)123x+ x 3(3)124x+ x 3，于是增加一个约束条件：3x 一 2x + 5x 3(3.3.4)123 后加的条件称为过滤的条件。这样，原问题的线性约束条件就变成5个。用全部枚举的方法， 3个变量共有23 = 8个解，原来四个约束条件，共需32次运算。现在增加了过滤条件(3.3.4), 如按下述方法进行，就可减少运算次数，将5个约束条件按(0)一(4)顺序排好(表3.3.1)， 对每个解，依次代入约束条件左侧，求出数值，看是否适合不等式条件，如某一条件不适合，同行以下各条件就不必再检查，因而减少了运算次数。本例计算过程如表 3.3.1，实际只作24 次运算。表3.3.1占八、条件满足条件？ 是(V)否(X)z值(0)(1)(2)(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于是求得最优解(x , x , x )二(1,0,1)，max z = 8。123在计算过程中，若遇到z值已超过条件(3.3.4)右边的值，应改变条件(3.3.4)，使右边为 迄今为止最大者，然后继续作。例如，当检查点(0，0，1)时因z = 5( 3)，所以应将条 件(3.3.4)换成3x - 2+ 5 5(3.3.5)这种对过滤条件的改进，更可以减少计算量。注：一般重新排列 x 的顺序使目标函数中 x 的系数是递增(递减)的。在上例中，改写ii123213213述顺序取值：(0, 0，0)，(0，0，1)，(0，1，0)，(0，1，1)，这样，最优解容易比z 二 3x 一 2x + 5x =2x + 3x + 5x ,因为2，3，5 是递增的。变量(x , x , x )也按下较早的发现。再结合过滤条件的改进，更可使计算简化。第四节 整数线性规划问题的一些例子例3.4.1 （分配问题）设有n个人被分配去做n件工作，规定每个人只做一件工作, 每件工作只能由一个人去做。已知第i个人去做第j件工作的效率（时间或费用）为c总时间或ij（i=口 n ；j=陀n）并假设cij - 。问应如何分配才能使总效率总费用）最高（最少）？设决策变量xij卩，若分配第个人去做第j件工作j=, 否则那么第 i 个人去做第2 x = 1iji=1j件工作的效率为c x，从而工另c x即为总效率, ij ijij iji=1j=1（j = 1,2,n ）表示每件工作都有人去做，工x =1 （i = 1,2,n）表示每个人都有工ijj=1作做；于是分配问题的数学模型为min z =工区i=1 j=1cxij ij2n x =1,ijj=12n x =1,iji=1x = 或 1,iji = 1,2, nj =1,2, ,ni, j = 1,2, n例3.42 （旅行售货员问题）有一推销员，从城市V 岀发要遍访城市匚V 2,各一次最后返回V 已知从V到Vj的旅费为cy.，问他应该按怎样的次序访问这些城市使得总旅费最少？（设c = M，M为充分大的正数，i = 0,1,n ）。 ii对每一对城市v和v，我们指定一个变量x，令ijij1, 如果推销员决定从v直接进入V；x = ijij0,其它情况该问题的数学模型为min z =艺 c xij iji, j=0艺 x = 1,ij i=0 艺 x = 1,iji = 0, n(3.1.3)j=ou - u + nx 0，单位价值为 jc 0( j二1,2,n )。问此人应如何选择携带物品的方案，使总价值最大?j设x为第j种物品的装入件数，则问题的数学模型是 jmax z =艺 c xjjj=1Qax 0且为整数，j = 1,2, nj第五节用LINGO软件包求解整数线性规划问题例如，用LINGO求解线性规划问题:-200ymax z = 3x + 4x + 8x -100y -150y123122 x + 4 x + 8 x 5001232x + 3x + 4x 300123x + 2x + 3x 1001233x + 5x2 + 7x3 700s.t.123x 200 y11x 150y22x2 0且为整数,j = 1,2,3 y = 0或1, j =1,2,3 j1、 模型的输入使用LINGO求解上述整数规划模型，LINGO程序如下:MODEL: max=3*x1+4*x2+8*x3-100*y1-150*y2-200*y3; 2*x1+4*x2+8*x3=500;2*x1+3*x2+4*x3=300;x1+2*x2+3*x3=100;3*x1+5*x2+7*x3=700;x1=200*y1;x2=150*y2;x3=300*y3;GIN(x1);GIN(x2);GIN(x3);BIN(y1);BIN(y2);BIN(y3);END2、执行点击LING O菜单下的SOLVE键，或按CTRL+S键，即可求得问题的解。 此问题的解为： x = 100, x = 0, x = 0, y = 1, y = 0, y = 0 ，最优值为：200。123123当运用LING O求解此问题后，系统会弹出一个名为Solution Report的文本框，其文本框 中包含了求解的详细信息，如下：Rows= 8 Vars= 6 No. integer vars= 6 ( all are linear) Nonzeros= 28 Constraint nonz= 18( 4 are +- 1) Density=0.500 Smallest and largest elements in abs value= 1.00000 700.000 No. : 0, Obj=MAX, GUBs = 3Single cols= 0Global optimal solution found at step:4Objective value:200.0000Branch count:0VariableValueReduced CostX1100.0000-3.000000X20.0000000-4.000000X30.0000000-8.000000Y11.000000100.0000Y20.0000000150.0000Y30.0000000200.0000RowSlack or SurplusDual Price1200.00001.0000002300.00000.00000003100.00000.000000040.00000000.00000005400.00000.00000006100.00000.000000070.00000000.000000080.00000000.00000003、 LINGO 程序注解MODEL： LINGO模型程序的开始标志。END： LINGO模型程序的结束标志。max=3*xl+4*x2+8*x3-100*yl-150*y2-200*y3 :表明目标函数是3x + 4x + 8x 100y 150y 200y，问题为求最大值。1231232*x1+4*x2+8*x3v=500:对应约束条件2x + 4x + 8x 500，其余类似。123GIN(x1):对应约束条件x1为整数，函数 GIN用来限定变量为整数，其余类似。BIN(y1):对应约束条件y 1为01变量，函数 BIN用来限定变量为二进制整数。 关于LINGO的详细使用方法，参见本部分附录的LINGO使用手册。练习题1、 食油厂精炼两种类型的原料油硬质油和软质油，并将精制油混合得到一种食油产 品。硬质原料油来自两个产地:产地1 和产地 2，而软质原料油来自另外三个产地:产 地3 ，产地4和产地5 。据预测，这5种原料油的价格从一至六月份分别为附录表1所 示，产品油售价 200 元/吨。硬质油和软质油需要由不同的生产线来精炼。硬质油生产线的每月最大处理能力为200 吨，软质油生产线最大处理能力为 250 吨/月。五种原料油都备有贮罐，每个贮罐的容量 均为1 000吨，每吨原料每月的存贮费用为5元。而各种精制油以及产品无油罐可存贮。 精炼的加工费用可略去不计。产品的销售没有任何问题。产品食油的硬度有一定的技术要求，它取决于各种原料油的硬度以及混合比例。产品食 油的硬度与各种成分的硬度以及所占比例呈线性关系。根据技术要求，产品食油的硬度 必须不小于3.0 而不大于6.0。各种原料油的硬度如附录表2（精制过程不会影响硬度）。 假设在一月初，每种原料油都有500 吨存贮而要求在六月底仍保持这样的贮备。问题 1：根据附录表1 预测的原料油价格，编制逐月各种原料油采购量、耗用量及库存 量计划，使本年内的利润最大。问题 2：考虑原料油价格上涨对利润的影响。据市场预测分析，如果二月份硬质原料油 价格比附录表1中的数字上涨X%，则软质油在二月份的价格将比附录表1中的数字上 涨2X%。相应地，三月份，硬质原料油将上涨2X%，软质原料油将上涨4X%，依此 类推至六月份。试分析x从1到20的各情况下，利润将如何变化？附加下列条件后，求解新的问题：（1）每一个月所用的原料油不多于三种。（2）如果在某一个月用一种原料油，那么这种油不能少于20吨。（3）如果在一个月中用了硬质油1或硬质油2，则在这个月中就必须用软质油5。附录表1原料油的价格（元/吨）硬质1硬质2软质3软质4软质5一月110120130110115二月13013011090115三月11014013010095四月120110120120125五月100120150110105六月9011014080135附录表2各种原料油的硬度（无量纲）硬质1硬质2软质3软质4软质58.86.12.04.25.02、机械加工厂生产7种产品（产品1到产品7）。该厂有以下设备：四台磨床、两台立式钻 床、三台水平钻床、一台镗床和一台刨床。每种产品的利润（元/件，在这里，利润定义 为销售价格与原料成本之差）以及生产单位产品需要的各种设备的工时（小时）如附录 3，其中的短划表示这种产品不需要相应的设备加工。从一月份至六月份，每个月中需要检修的设备见附录表4所示（在检修的月份，被检修 的设备全月不能用于生产）。每个月各种产品的市场销售量的上限如附录表5 所示。每种产品的最大库存量为100件，库存费用为每件每月0.5元，在一月初，所有产品都 没有库存；而要求在六月底，每种产品都有50 件库存。工厂每天开两班，每班8 小时， 为简单起见，假定每月都工作24天。生产过程中，各种工序没有先后次序的要求。问题1：制定六个月的生产、库存、销售计划，使六个月的总利润最大。问题 2：在不改变以上计划的前提下，哪几个月中那些产品的售价可以提高以达到增加 利润的目的。价格提高的幅度是多大？问题 3：哪些设备的能力应该增加？请列出购置新设备的优先顺序。问题 4：是否可以通过调整现有设备的检修计划来提高利润？提出一个新的设备检修计 划，使原来计划检修的设备在这半年中都得到检修而使利润尽可以有增加。问题 5：最优设备检修计划问题：构造一个最优设备检修计划模型，使在这半年中各设 备的检修台数满足案例中的要求而使利润为最大。附录表3 产品的利润（元/件）和需要的设备工时（小时/件）产品1234567单位产品利润10.006.003.004.001.009.003.00磨床0.500.700.300.200.50立钻0.102.000.300.60水平钻0.206.000.800.60镗床0.050.030.070.100.08刨床0.010.050.05附录表 4 设备检修计划月份计划检修设备及台数月份计划检修设备及台数一月一台磨床四月一台立式钻床二月二台立式钻床五月一台磨床和一台立式钻床三月一台镗床六月一台刨床和一台水平钻床附录表 5 产品的市场销售量上限（件/月）产品1234567一月5001000300300800200100二月6005002000400300150三月30060000500400100四月2003004005002000100五月010050010010003000六月500500100300110050060参考文献1、刁在筠等编，运筹学，北京：高等教育出版社，2001年2、卢开澄，单目标、多目标与整数规划，北京：清华大学出版社，19993、甘应爱等，运筹学，北京：北京：清华大学出版社，1990