第一次培训资料.doc

线性（整数）规划线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素.只要确定决策变量、约束条件、目标函数就能建立相应的线性规划模型。示例某钢管零售商从钢管厂进货，将钢管按照顾客要求的长度进行切割，称为下料。假定进货时得到的原料钢管长度都是19m。1）现有一客户需要50根长4m、20根长6m和15根长8m的钢管。应如何下料最节省？2）零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本。所以该零售商规定采用的不同切割模式不能超过3种。此外。该客户除需要1）中的3种钢管外，还要10根长5m的钢管。应如何下料最节省？问题分析：对于下料问题首先要确定采用哪些切割模式。所谓切割模式，是指按照顾客要求的长度在原料钢管上安排切割的一种组合。例如，我们可以将19m的钢管切割成3根长4m的钢管，余料为7m；或者将长19m的钢管切割成长4m、6m和8m的钢管各1根，余料为1m。显然，可行的切割模式是很多的。其次，应当明确哪些切割模式是合理的。合理的切割模式通常还假设余料不应大于或等于客户需要钢管的最小尺寸。例如，可以将长19m的钢管切割成3根4m的钢管是可行的，但余料为7m，可进一步将7m的余料切割成4m钢管（余料为3m），或者将7m的余料切割成6m钢管（余料为1m）。经过简单的计 算可知，问题1）的 合理切割模式一共有7种，如表1所示模式4m钢管根数6m钢管根数8m钢管根数余料/m14003231013201341203511116030170022表1 钢管下料问题1）的合理切割模式于是问题转化为在满足客户需要的条件下，按照哪几种合理的模式，每种模式切割多少根原料钢管最为节省。而所谓节省，可以有两种标准，一是切割后剩余的总余料量最小，二是切割原料钢管的总根数最少。下面将对这两个目标分别讨论。问题1） 用xi表示按照表1第i种模式（i=1,2,7）切割的原料钢管的根数，若以切割后剩余的总余料量最小为目标，则按照表1最后一列可得minZ1 = 3x1+x2+3x3+3x4+x5+x6+3x7 若以切割原料钢管的总根数最少为目标，则有MinZ2 = x1+x2+x3+x4+x5+x6+x7约束条件为客户的需求，按照表1应有4x1+3x2+2x3+x4+x5 50x2+2x4+x5+3x6 20x3+x5+2x7 15最后，切割的原料钢管的根数xi显然应当是非负整数（用Z表示整数集合，Z+表示非负整数集合）：xi Z+ ， i=1,2,7 于是，问题1）归结为在约束条件下，使目标达到最小。显然这是线性整数规划模型。问题2） 如果按照问题1）的办法处理，首先要通过枚举法确定哪些切割模式是合理的，并从中选出不超过3种模式。而由于需求的钢管规格增加到4种，所以枚举法的工作量较大。下面介绍一种带有普遍性的方法，可以同时确定切割模式和切割数量。同问题1）一样，只使用合理的切割模式，其余料不应大于3m（因为客户需要的钢管最小尺寸为4m，而本题中参数都是整数）。由于不同切割模式不能超过3种，可以用用xi表示按照第i种模式（i=1,2,3）切割的原料钢管的根数。又设使用第i种切割模式下每根原料钢管生产长4m、5m、6m和8m的钢管数量分别为r1i，r2i，r3i，r4i。仅以使用的原料总根数最少为目标，即min x1+x2+x3满足客户需求的约束条件为r11x1+r12x2+r13x3 50 r21x1+r22x2+r23x3 10 r31x1+r32x2+r33x3 20 r41x1+r42x2+r43x3 15每一种切割模式必须可行、合理，所以每根原料钢管的成品量不能超过19m，也不能少于16m（余料不能大于3m），于是164r11+5r21+6r31+8r41 19164r12+5r22+6r32+8r42 19164r13+5r23+6r33+8r43 19 最后，加上非负整数约束：xi，rji Z+ ， i=1,2,3, j=1,2,3,4 于是，问题2）归结为在在约束条件下，求xi和r1i，r2i，r3i，r4i（i=1,2,3）使目标达到最小。当然，这是一个整数非线性规划模型。用LINGO求解整数规划LINGO软件用于线性或非线性规划（无论是连续规划还是整数规划），因此包含了LINDO的功能。在LINGO中，所有的函数均以“”符号开始，如约束中gin(x1)表示x1为整数。钢管下料问题1）的求解以切割后剩余的总余料量最小为目标，建立LINGO模型：min= 3*x1+x2+3*x3+3*x4+x5+x6+3*x7;4*x1+3*x2+2*x3+x4+x5 =50; x2+2*x4+x5+3*x6 = 20;x3+x5+2*x7 = 15;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);即按照模式2切割12根原料钢管，按照模式5切割15根原料钢管，共27根，总余料量27m。显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切割模式（模式2和模式5的余料为1m），这会导致切割原料钢管的总根数较多。以切割原料钢管的总根数最少为目标，建立LINGO模型：min= x1+x2+x3+x4+x5+x6+x7;4*x1+3*x2+2*x3+x4+x5 =50; x2+2*x4+x5+3*x6 = 20;x3+x5+2*x7 = 15;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);即按照模式2切割15根原料钢管，按照模式5切割5根原料钢管，按照模式7切割5根原料钢管，共25根，总余料量35m。与上面得到的结果相比，总余料量增加了8m，但是所用的原料钢管的总根数减少了2根，在余料没有什么用途的情况下，通常选择总根数最少为目标。钢管下料问题2）的求解LINGO模型为：min=x1+x2+x3;r11*x1+r12*x2+r13*x3=50; r21*x1+r22*x2+r23*x3=10; r31*x1+r32*x2+r33*x3=20; r41*x1+r42*x2+r43*x3=15; 4*r11+5*r21+6*r31+8*r41=19; 4*r12+5*r22+6*r32+8*r42=19; 4*r13+5*r23+6*r33+8*r43=16; 4*r12+5*r22+6*r32+8*r42=16;4*r13+5*r23+6*r33+8*r43=16;x1+x2+x3=26;x1+x2+x3=x2;x2=x3;gin(x1);gin(x2);gin(x3);gin(r11);gin(r12);gin(r13);gin(r21);gin(r22);gin(r23);gin(r31);gin(r32);gin(r33);gin(r41);gin(r42);gin(r43);即按照模式1，2，3分别切割10根，10根，8根原料钢管，使用原料钢管总根数为28根。第一种切割模式下一根原料钢管切割成3根4m钢管和1根6m钢管；第二种切割模式下一根原料钢管切割成2根4m钢管，1根5m钢管和1根6m钢管；第三种切割模式下一根原料钢管切割成2根8m钢管。思考题某投资公司拟制定今后5年的投资计划，初步考虑下面四个投资项目：项目A：从第1年到第4年每年年初可以投资，于次年年末收回成本，并可获利润15%；项目B：第3年年初可以投资，到第5年年末可以收回成本，并获得利润25%，但为了保证足够的资金流动，规定该项目的投资金额上限为不超过总金额的40%；项目C：第2年年初可以投资，到第5年年末可以收回成本，并获得利润40%，但公司规定该项目的最大投资金额不超过总金额的30%；项目D：5年内每年年初可以购买公债，于当年年末可以归还本金，并