第一次培训资料.doc

线性（）线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素 只要确定决策变量、约束条件、目标函数建立相应的线性规划模型。 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钢管根数 余料/m 1 4 0 0 3 2 3 1 0 1 3 2 0 1 3 4 1 2 0 3 5 1 1 1 1 6 0 3 0 1 7 0 0 2 2 表1 钢管下料问题1）的合理切割模式 于是问题转化为在满足客户需要的条件下，按照哪几种合理的模式，每种模式切割多少根原料钢管最为节省。而所谓节省，可以有两种标准，一是切割后剩余的总余料量最小，二是切割原料钢管的总根数最少。下面将对这两个目标分别讨论。 问题1） 用xi表示按照表1第i种模式（i=1,2,…,7） minZ1 = 3x1+x2+3x3+3x4+x5+x6+3x7 若以切割原料钢管的总根数最少为目标，则有 MinZ2 = x1+x2+x3+x4+x5+x6+x7 约束条件为客户的需求，按照表1应有 4x1+3x2+2x3+x4+x5 ≥ 50 x2+2x4+x5+3x6 ≥ 20 x3+x5+2x7 ≥ 15 最后，切割的原料钢管的根数xi显然应当是非负整数（用Z表示整数集合，Z+表示非负整数集合）： xi ∈ Z+ ， i=1,2,…,7 问题2） 如果按照问题1）的办法处理，首先要通过枚举法确定哪些切割模式是合理的，并从中选出不超过3种模式。而由于需求的钢管规格增加到4种，所以枚举法的工作量较大。下面介绍一种带有普遍性的方法，可以同时确定切割模式和切割数量。 同问题1）一样，只使用合理的切割模式，其余料不应大于3m（因为客户需要的钢管最小尺寸为4m，而本题中参数都是整数）。 由于不同切割模式不能超过3种，可以用用xi表示按照第i种模式（i=1,2,3） 仅以使用的原料总根数最少为目标，即 min x1+x2+x3 满足客户需求的约束条件为 r11x1+r12x2+r13x3 ≥ 50 r21x1+r22x2+r23x3 ≥ 10 r31x1+r32x2+r33x3 ≥ 20 r41x1+r42x2+r43x3 ≥ 15 每一种切割模式必须可行、合理，所以每根原料钢管的成品量不能超过19m，也不能少于16m（余料不能大于3m），于是 16≤4r11+5r21+6r31+8r41 ≤19 16≤4r12+5r22+6r32+8r42 ≤19 16≤4r13+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中，所