线性规划问题的Lingo求解new.ppt

第五章线性规划问题的Lingo求解5.1 一般线性规划模型的建立与求解5.1.1 基本理论线性规划问题的标准形式是等约束的，用矩阵表示如下 ：一般线性规划问题都可以通过引入松弛变量与剩余变量的方法化成标准形 式线性规划模型的一般性质：(1)比例性，每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比2)可加性，每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关单纯形算法的实质：在保证可行(最小比值法则)的前提下，先在可行解上取一个顶点，判断是否达到最优解，如果没有，则通过一定的规则(入基，旋转等)到另一个更优的顶点，如此迭代下去直到最优，或者判断不可行或者判断无界为止3)连续性，每个决策变量的取值都是连续的比例性和可加性保证了目标函数和约束条件对于决策变量的线性性质，连续性则允许得到决策变量的实数最优解5.1.2 应用举例例5-1(运输问题) 两个粮库A1,A2,向三个粮站B1,B2,B3调运大米，两个粮库现存大米分别为4t，8t，三个两站至少需要大米分别为2t,4t,5t，两个粮库到三个粮站的距离(km)如下表，求使运费最低B1B2B3库库存 A1122484 A23012248 需求245解：(1)问题分析：总需求量为11t，小于总库存量12t，所以问题可行。

2)从线性规划的三个要素出发，决策变量：问题是各个粮仓向粮站调运了多少大米，此调运量就是决策变量目标函数：运费和运量和距离有关系，即t*km最小，所以要将运量与相应的距离相乘然后使总和最小约束条件：两个粮库的库存量限制和三个粮站需求量的限制3)建立模型，设A1,A2分别向B1,B2,B3运送大米x11,x12,x13,x21,x22,x23，则有： min f=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23s.t. x11+x12+x13=2x12+x22=4x13+x23=5x11,x12,x13,x21,x22,x23=0(4)转化成对应的Lingo建模语言程序1，求解模型，结果如下页图示：程序说明:(1) 这是一种比较直观的输入方式，和书写的基本一致，注意乘号*不能省略2)在Lingo中没有严格的不等号，因此=0转换成Lingo语言如下所示：说明：1、写程序要习惯给程序用title命名2、为了方便查看报告，用行号区分约束3、此程序的格式可以固定为标准形式的求解模式程序改进三：可以减少引入的变量个数，将模型修改为下面的形式min f=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23s.t. x11+x12+x13=0写成lingo语言如下所示：说明：1、改程序把不等式约束全部转化为小于等于约束，是为了将约束可以写到一个循环语句中实现，如果还有等是约束的话，则要在写一个循环语句来控制约束。

2、当程序比较大的时候，一般将约束按性质进行分类程序改进四：将约束进行分类，代码如下：注：1、在进行调试程序时，可以用!号某些语句屏蔽，缩小寻找出错的范围2、可以编写程序边运行，保证每行书写都是正确的3、常见的出错情况有：(1)定义了多个长度一样的集合，而在使用中区分不明确；(2)定义了同名的属性；(3)漏掉了括号；(4)分号不是英文半角；(5)使用的字母没有定义；(6)循环语句中元素下标颠倒或者不明；(7)约束错误变成不可行或者无界；(8)关系运算符误用成逻辑运算符；(9)函数调用错误等等…例5-2 （阶段生产问题）某公司产品最大生产能力为10000单位，每单位存储费2元，预定的销售量与单位成本如下表所示：月份单单位成本销销售量 1706000 2717000 38012000 4766000求一生产计划，使(1)满足需求；(2)不超过生产能力；(3)成本(生产成本与存储费之和最低)问题分析：这是一个多阶段生产计划问题，设计多阶段存储，只需要制定1~4月份的生产计划，不妨假定1月初无库存，4月底卖完，当月生产的不作为当月的库存，库存量无限制模型建立（1）： 设xi为第i月产量，di为销售量，ei为存储费，ci为单位成本，则目标生产成本为:第j月到j+1月的库存量(记作第j+1月的库存量)应该是1月到j月的总产量减去1月到j月的总销售量，即：总的库存费用为：总成本为： 即求总成本的最小值。

约束条件1：如果每个月都有非负的存储量，显然满足要求，可用约束：约束条件3：产量限制，0=”(2)从约束系数的矩阵看，一个模型为A，一个模型为AT，一个模型为m个约束，n个变量，另一个则为n个约束，m个变量3)从数据b和c的位置看，在两个规划模型中两者互换4)两个模型中的变量皆非负2、非对称形式的对偶规划一般称不具有对称形式的一对线性规划为非对称形式的对偶规划对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划1）将模型统一为“max，≤”或“min，≥” 的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式下面对关系（2）作一说明对于关系（3）可以给出类似的解释设原规划中第一个约束为等式： a11x1 + … + a1nxn = b1那么，这个等式与下面两个不等式等价：则原规划模型可以写成如下形式：此时已转化为对称形式，可以直接写出其对偶问题：这里，把y1看作是y1=y1’ - y1’’，于是y1没有非负限制，关系（2）的说明完毕。

对偶定理：若互为对偶问题的线性规划问题(I)和(II)中有一个最优解，则另一个必有最优解，且目标函数值相同例5-5(生产决策问题)某工厂可以用A，B两种原料生产I,II,III三种产品，每种产品需要同时用两种原料，有关数据如下表(单位消耗与资源限制)：产产品I产产品II产产品III现现有原料/t原料A2127原料B13211单位产品利润/万元231求：(1)若目前市场上原料A的实际价格为0.5万元/t，工厂应如何决策？(2)若目前市场上原料B的实际价格为0.8万元/t，工厂应如何决策？解：建立模型，设x1,x2,x3分别表示I，II，III的生产量，则模型如下：对偶问题模型讨论：若把y1,y2当作原料A，B的定价，用两个单位的A，1个单位的B，若生产产品I只能赚2万元，现在考虑把资源拿到市场上卖，定价y1,y2,使得2y1+y2≥2,也就是一定比生产产品I赚得多产品II，III同理亦即对偶问题的约束条件保证了资源直接在市场上出售一定不会比生产产品获得的利润低，另一方面，为了增强出售资源的市场竞争力，定价希望低一些，定价的目标是在比生产产品获得更多利润的前提下的最小利润，这个定价模型就是对偶问题。

如果把资源A的量由7增加到8，会导致什么结果呢？影子价格：在最优情况下，y1的值就是资源A的影子价格，所以要把影子价格与资源A的市场价格做比较，如果影子价格大于市场价格，考虑出售部分资源以获得更大利润，否则，则从市场买进该资源影子价格的经济意义：在资源得到最优配置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量影子价格是一种静态的资源最优配置价格，不能表现资源在不同时期动态配置时的最优价格，只反映某种资源的稀缺程度和资源与总体积极效益之间的关系，不能代替资源本身的价值程序编写：执行结果如下：说明：从红框部分知道，A的影子的价格为0.6，B的影子价格为0.8，松弛变量的值都是0，说明约束是紧约束(约束取等号)，即资源没有剩余，影子价格有意义必须是紧约束影子价格是对应最优基来说的，如果约束的改变使得最优基发生改变，当前的影子价格也就没有任何意义了通过对右端项的灵敏性分析：在最优基不变时，A,B的右端项变化范围分别为(4.67,22)和(3.5,21)对问题(1)0.50.6，应该售出部分原料将使利润更大，最大售出量为3.33t,利润将会增加(0.8-0.6)*3.33=0.66万元例5-6(奶制品的加工问题)1桶 牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶 时间480小时 至多加工100公斤 A1 制订生产计划，使每天获利最大 (1)35元可买到1桶牛奶，买吗？若买，每天最多买多少?(2)可聘用临时工人，付出的工资最多是每小时几元? (3)A1的获利增加到 30元/公斤，应否改变生产计划？ 每天：1桶 牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产A1 x2桶牛奶生产A2 获利 24×3x1 获利 16×4 x2 原料供应 劳动时间 加工能力 决策变量 目标函数 每天获利约束条件非负约束 线性 规划 模型 (LP)时间480小时 至多加工100公斤A1 50桶牛奶 每天max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100endOBJECTIVE FUNCTION VALUE1) 3360.000VARIABLE VALUE REDUCED COSTX1 20.000000 0.000000X2 30.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 48.0000003) 0.000000 2.0000004) 40.000000 0.000000NO. ITERATIONS= 220桶牛奶生产A1, 30桶生产A2，利润3360元。

模型求解 模型求解 reduced cost值表 示当该非基变量 增加一个单位时 （其他非基变量 保持不变）目标 函数减少的量(对 max型问题) OBJECTIVE FUNCTION VALUE1) 3360.000VARIABLE VALUE REDUCED COSTX1 20.000000 0.000000X2 30.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 48.0000003) 0.000000 2.0000004) 40.000000 0.000000NO. ITERATIONS= 2也可理解为：为了使该非基变 量变成基变量， 目标函数中对应 系数应增加的量OBJECTIVE FUNCTION VALUE1) 3360.000VARIABLE VALUE REDUCED COSTX1 20.000000 0.000000X2 30.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 48.0000003) 0.000000 2.0000004) 40.000000 0.000000原料无剩余 时间无剩余 加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三 种 资 源 “资源” 剩余为零的约束为紧约束（有效约束） 结果解释 OBJECTIVE FUNCTION VALUE1) 3360.000VARIABLE VALUE REDUCED COSTX1 20.000000 0.000000X2 30.000000 。