《线性规划问题的Lingo求解.ppt》由会员分享，可在线阅读，更多相关《线性规划问题的Lingo求解.ppt（70页珍藏版）》请在三一办公上搜索。
1、第五章线性规划问题的Lingo求解,5.1 一般线性规划模型的建立与求解,5.1.1 基本理论,线性规划问题的标准形式是等约束的，用矩阵表示如下：,一般线性规划问题都可以通过引入松弛变量与剩余变量的方法化成标准形式。,线性规划模型的一般性质：(1)比例性，每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比。(2)可加性，每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关。,单纯形算法的实质：在保证可行(最小比值法则)的前提下，先在可行解上取一个顶点，判断是否达到最优解，如果没有，则通过一定的规则(入基，旋转等)到另一个更优的顶点，如此迭代下去直到最优，或者判断不可行或者
2、判断无界为止。,(3)连续性，每个决策变量的取值都是连续的。比例性和可加性保证了目标函数和约束条件对于决策变量的线性性质，连续性则允许得到决策变量的实数最优解。,5.1.2 应用举例,例5-1(运输问题)两个粮库A1,A2,向三个粮站B1,B2,B3调运大米，两个粮库现存大米分别为4t，8t，三个两站至少需要大米分别为2t,4t,5t，两个粮库到三个粮站的距离(km)如下表，求使运费最低。,解：(1)问题分析：总需求量为11t，小于总库存量12t，所以问题可行。(2)从线性规划的三个要素出发，,决策变量：问题是各个粮仓向粮站调运了多少大米，此调运量就是决策变量。目标函数：运费和运量和距离有关系
3、，即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*x23,s.t.x11+x12+x13=2 x12+x22=4 x13+x23=5 x11,x12,x13,x21,x22,x23=0,(4)转化成对应的Lingo建模语言程序1，求解模型，结果如下页图示：,程序说明:(1)这是一种比较直观的输入方式，和书写的基本一致，注意乘号*不
4、能省略。(2)在Lingo中没有严格的不等号，因此表示小于等于。(3)model:和end两个关键字可以不要。(4)不能将公式编辑器下编写的模型直接粘贴到Lingo中。,通过选择Lingo|Generate|Display model将模型展开，方便查看求解报告的第三部分。,相应的添加的剩余变量或者松弛变量。,程序改进一、上面解法是一种傻瓜式的直接输入法，适用于程序规模不大的问题，如果问题规模很大的话用这种方式很费力，可以使用矩阵生成器来编写程序2,min f=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23,s.t.x11+x12+x13+y1=4 x21+x
5、22+x23+y2=8 x11+x21-y3=2 x12+x22-y4=4 x13+x23-y5=5 x11,x12,x13,x21,x22,x23,y1,y2,y3,y4,y5=0,转换成Lingo语言如下所示：,说明：1、写程序要习惯给程序用title命名 2、为了方便查看报告，用行号区分约束 3、此程序的格式可以固定为标准形式的求解模式。,程序改进三：可以减少引入的变量个数，将模型修改为下面的形式,min f=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23,s.t.x11+x12+x13=0,写成lingo语言如下所示：,说明：1、改程序把不等式约束全部
6、转化为小于等于约束，是为了将约束可以写到一个循环语句中实现，如果还有等是约束的话，则要在写一个循环语句来控制约束。2、当程序比较大的时候，一般将约束按性质进行分类,程序改进四：将约束进行分类，代码如下：,注：1、在进行调试程序时，可以用!号某些语句屏蔽，缩小寻找出错的范围。2、可以编写程序边运行，保证每行书写都是正确的。3、常见的出错情况有：(1)定义了多个长度一样的集合，而在使用中区分不明确；(2)定义了同名的属性；(3)漏掉了括号；(4)分号不是英文半角；(5)使用的字母没有定义；(6)循环语句中元素下标颠倒或者不明；(7)约束错误变成不可行或者无界；(8)关系运算符误用成逻辑运算符；(9
7、)函数调用错误等等,例5-2（阶段生产问题）某公司产品最大生产能力为10000单位，每单位存储费2元，预定的销售量与单位成本如下表所示：,求一生产计划，使(1)满足需求；(2)不超过生产能力；(3)成本(生产成本与存储费之和最低),问题分析：这是一个多阶段生产计划问题，设计多阶段存储，只需要制定14月份的生产计划，不妨假定1月初无库存，4月底卖完，当月生产的不作为当月的库存，库存量无限制。,模型建立（1）：设xi为第i月产量，di为销售量，ei为存储费，ci为单位成本，则目标生产成本为:,第j月到j+1月的库存量(记作第j+1月的库存量)应该是1月到j月的总产量减去1月到j月的总销售量，即：,
8、总的库存费用为：,总成本为：,即求总成本的最小值。,约束条件1：如果每个月都有非负的存储量，显然满足要求，可用约束：,约束条件3：产量限制，0=xi=10000。,综上，建立如下数学模型：,约束条件2：4个月的总产量等于总需求量即：,转成相应的Lingo语言如下：,模型改进(2)：引入库存变量，再利用库存平衡方程使模型更加流畅简洁。设xi为第i个月的产量，di为销售量，ei为存储费，ci为单位成本，设第i个月的库存为si,则：,程序编写如下：,模型改进(3)：将该模型转化成运输问题。设xij表示第i个月生产的产品在第j个月卖出去的数量，cij表示第i个月生产的产品在第j月卖出去时的生产成本与存
9、储成本之和，,dj表示第j月的销售量，则生产月生产的产品在需求月卖出时单位总成本如下表所示：,建立模型如下：,相应的Lingo程序如下：,表示第二个下标大于第一个下标。,例5-3（连续投资问题）某部门在今后5年内考虑给下列项目投资，已知：(1)项目A，从第1年到第4年每年初要投资，次年末回收本利1.15；(2)项目B，第3年初投资，到第5年末回收本利1.25，最大投资4万元;(3)项目C，第2年初投资，到第5年末回收本利1.40，最大投资3万元；(4)项目D，每年初购买国债，当年末回收本利1.06;该部门现有资金10万元，问应如何投资到第5年末总资本最大。,问题分析：将可能的投资情况设为变量，
10、如下表所示,因为具有项目D，所以可以认为该部门每年都把自己全部投出去，而且年末的总资本等于第二年初的总投资额。由此可建立模型如下：,转换成Lingo程序如下所示：,5.2 灵敏性分析与影子价格,5.2.1 灵敏性分析,例5-4(生产计划问题)某工厂计划安排生产I II两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及A,B两种原材料的消耗，现有原材料和设备台时的定额见下表所示：,求：(1)怎么样安排生产使得工厂利润最大？(2)产品I的单位利润降低到1.8万元，要不要改变生产计划，如果降低到1万元呢？(3)产品II的单位利润增大到5万元，要不要改变生产计划？(4)如果产品I,II的单位
11、利润同时降低了1万元，要不要改变生产计划？,建立模型：用x1,x2分别表示计划生产产品I II的数量，可建立如下模型,编写lingo程序如下：,程序执行结果：,通过执行结果对问题进行分析：,问题1：安排生产产品I为4个单位，II为2个单位，最大利润为14万元。灵敏性分析：打开LINGO中的灵敏性分析开关，LINGO|Options|General Solver|Dual Computations|Prices and Ranges 分析结果通过点击Lingo|Range命令获得,说明1：(1)红框内的部分是对目标函数进行的灵敏性分析，第一列是变量，第二列是对应的系数，第三列是允许增加量，第四列
12、是允许减少量，允许增加和允许减少都是在当前系数基础上改变的。,在其他变量系数都不变的情况下有：当x1在(2-0.5,2+)=(1.5,)之间变化时,最优解不变；当x2在(3-3,3+1)=(0,4)之间变化时，最优解不变。,问题2：产品I的单位利润降低到1.8万元，在(1.5,)之间，所以不改变生产计划；而降低到1万元，则需要重新制定生产计划；,问题3：5万不在(0,4)范围内，故要重新制定生产计划。修改程序之后运行结果如下：,问题4：因为两个系数同时发生变化，所以只能更改程序的数据，重新运行。运行结果和灵敏性分析结果如下：,说明2、红框内所示为保持最优基不变的约束右端项的变化范围，即原材料A
13、的量在(8-4，8+2)=(4,10)，原材料B的量在(16-8,16+16)=(8,32)，设备台时在(12-4,12+)=(8,)内变化时，最优基保持不变。,5.2.2 对偶问题,两个线性规划问题：,称为对称形式的对偶问题(dual problem),互为对偶问题的(I)和(II)一个称为原问题，一个称为原问题的对偶问题。称对偶问题的最优解为原问题约束条件的影子价格(shadow price),1、一对对称形式的对偶问题有如下的对应关系：,(1)若一个模型为目标求极大，约束为小于等于的不等式，则它的对偶模型为目标求极小，约束为大于等于的不等式，即”max=”,(2)从约束系数的矩阵看，一个
14、模型为A，一个模型为AT，一个模型为m个约束，n个变量，另一个则为n个约束，m个变量。(3)从数据b和c的位置看，在两个规划模型中两者互换。(4)两个模型中的变量皆非负。,2、非对称形式的对偶规划一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。（1）将模型统一为“max，”或“min，”的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式
15、。,下面对关系（2）作一说明。对于关系（3）可以给出类似的解释。设原规划中第一个约束为等式：a11x1+a1nxn=b1那么，这个等式与下面两个不等式等价：,则原规划模型可以写成如下形式：,此时已转化为对称形式，可以直接写出其对偶问题：,这里，把y1看作是y1=y1-y1，于是y1没有非负限制，关系（2）的说明完毕。,对偶定理：若互为对偶问题的线性规划问题(I)和(II)中有一个最优解，则另一个必有最优解，且目标函数值相同。,例5-5(生产决策问题)某工厂可以用A，B两种原料生产I,II,III三种产品，每种产品需要同时用两种原料，有关数据如下表(单位消耗与资源限制)：,求：(1)若目前市场上
16、原料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+y22,也就是一定比生产产品I赚得多。产品II，III同理。亦即对偶问题的约束条件保证了资源直接在市场上出售一定不会比生产产品获得的利润低，另一方面，为了增强出售资源的市场竞争力，定价希望低一些，定价的目标是在比生产产品获得更多利润
17、的前提下的最小利润，这个定价模型就是对偶问题。,如果把资源A的量由7增加到8，会导致什么结果呢？,影子价格：在最优情况下，y1的值就是资源A的影子价格，所以要把影子价格与资源A的市场价格做比较，如果影子价格大于市场价格，考虑出售部分资源以获得更大利润，否则，则从市场买进该资源。,影子价格的经济意义：在资源得到最优配置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量。,影子价格是一种静态的资源最优配置价格，不能表现资源在不同时期动态配置时的最优价格，只反映某种资源的稀缺程度和资源与总体积极效益之间的关系，不能代替资源本身的价值。,程序编写：,执行结果如下：,说明：从红框部分知道，
18、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(奶制品的加工问题),50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,(
19、1)35元可买到1桶牛奶，买吗？若买，每天最多买多少?,(2)可聘用临时工人，付出的工资最多是每小时几元?,(3)A1的获利增加到 30元/公斤，应否改变生产计划？,每天：,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end,OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE RED
20、UCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2,20桶牛奶生产A1,30桶生产A2，利润3360元。,模型求解,模型求解,reduced cost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题),OBJECTIVE FUNCTION VALUE 1)3360.000 VARI
21、ABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2,也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量,OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000
22、X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000,原料无剩余,时间无剩余,加工能力剩余40,max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end,三种资源,“资源”剩余为零的约束为紧约束（有效约束）,结果解释,OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.00
23、0000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000,结果解释,最优解下“资源”增加1单位时“效益”的增量,时间加1单位,利润增2,影子价格,35元可买到1桶牛奶，要买吗？,35 48,应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLO
24、WABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,最优解不变时目标系数允许变化范围,DO RANGE
25、(SENSITIVITY)ANALYSIS?,Yes,x1系数范围(64,96),x2系数范围(48,72),A1获利增加到 30元/千克，应否改变生产计划,x1系数由243=72 增加为303=90，在允许范围内,不变！,(约束条件不变),结果解释,结果解释,RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.
26、000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶，每天最多买多少？,最多买10桶？,(目标函数不变),注意:充分但可能不必要,5.3 整数线性规划,例5-7(下料问题)做10
27、0套钢架，用长为2.9m,2.1m,1.5m的元钢各一根，已知原料长为7.4m，问如何下料，所用最省？,问题分析：每一种下料方式用了多少根钢材，合理的下料方式是剩余料头的长度不能超过最短原料需求(1.5m)，可首先利用lingo搜索出全部的下料方式，然后从中筛选出符合条件的方式：,模型建立：设xi为按第i种方式下料的根数，i=1,8，建立如下模型：,x1,x8,说明：(1)目标函数有两种取法，一是剩余的料最少，二是所用原料的根数最少。(2)决策变量限制取整数。(3)这种全方式设变量的模型只适合小型下料问题，大型下料问题或者对下料方式有限制的问题将不再合适。,程序编写：,补充例5-7(下料问题2
28、),问题1.如何下料最节省?,问题2.客户增加需求：,节省的标准是什么？,由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？,按照客户需要在一根原料钢管上安排切割的一种组合。,切割模式,合理切割模式的余料应小于客户需要钢管的最小尺寸,下料问题,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？,合理切割模式,2.所用原料钢管总根数最少,下料问题1,两种标准,1.原料钢管剩余总余量最小,xi 按第i 种模式切割的原料钢管根数(i=1,2,7),约束,满足需求,决策变量,目标1（总余量）,按模式2切割12根,按模式5切割15根，余料2
29、7米,最优解：x2=12,x5=15,其余为0；最优值：27,整数约束：xi 为整数,当余料没有用处时，通常以总根数最少为目标,目标2（总根数）,下料问题1,约束条件不变,最优解：x2=15,x5=5,x7=5,其余为0；最优值：25。,xi 为整数,按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米,虽余料增加8米，但减少了2根,与目标1的结果“共切割27根，余料27米”相比,下料问题2,对大规模问题，用模型的约束条件界定合理模式,增加一种需求：5米10根；切割模式不超过3种。,现有4种需求：4米50根，5米10根，6米20根，8米15根，用枚举法确定合理切割模式，
30、过于复杂。,决策变量,xi 按第i 种模式切割的原料钢管根数(i=1,2,3),r1i,r2i,r3i,r4i 第i 种切割模式下，每根原料钢管生产4米、5米、6米和8米长的钢管的数量,满足需求,模式合理：每根余料不超过3米,整数非线性规划模型,下料问题2,目标函数（总根数）,约束条件,整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数,增加约束，缩小可行域，便于求解,原料钢管总根数下界：,特殊生产计划：对每根原料钢管模式1：切割成4根4米钢管，需13根；模式2：切割成1根5米和2根6米钢管，需10根；模式3：切割成2根8米钢管，需8根。原料钢管总根数上界：31,模式排列顺
31、序可任定,下料问题2,需求：4米50根，5米10根，6米20根，8米15根,每根原料钢管长19米,LINGO求解整数非线性规划模型,Local optimal solution found at iteration:12211 Objective value:28.00000Variable Value Reduced CostX1 10.00000 0.000000X2 10.00000 2.000000X3 8.000000 1.000000R11 3.000000 0.000000R12 2.000000 0.000000R13 0.000000 0.000000R21 0.000000
32、 0.000000R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.000000,模式1：每根原料钢管切割成3根4米和1根6米钢管，共10根；模式2：每根原料钢管切割成2根4米、1根5米和1根6米钢管，共10根；模式3：每根原料钢管切割成2根8米钢管，共8根。原料钢管总根数为28根。,例5-8(选址问题)A，B
33、，C三个区，7个位置M1,M7,约束：(1)在A区从M1,M2,M3中选择至多两个；(2)在B区从M4,M5中选择至少一个；(3)在C区，从M6,M7中选择至少一个。已知，M1.M7分别投资为200，300，350，250，350，200，400，预计每年获利50，80，12-，70，100，60，120，总资金1200，问如何建立？,模型分析：典型的0-1规划问题，设选择M1,M7的投资分别为bi万元，每年获利ci万元，总资金b万元，设0-1变量xi(i=1,7)为：1(选择)或0(不选择),建立模型：,例5-9(拍卖与投标)5类艺术品拍卖，来自4个投标人的投标书，投标价格如下表，假定每个投
34、标人对每类艺术品只能购买一件，每个投标人对每类艺术品最多只能购进一件，每个投标人竞购总数不能超过3件，则哪些艺术品能卖出去？卖给谁？每类物品的清算价格是多少？,问题分析：供应能力与需求能力达到平衡时的产品的价格称为清算价格，清算价格pi满足如下条件：,(1)不超过物品数量的限制；(2)报价低于pj的将不能获得物品；(3)物品没有全部卖出，可认为清算价格为0，除非拍卖方指定最低保护价；(4)报价高于pj的投标人有权获得物品，如果他有权获得的物品超过三件，假设他总是希望自己的满意度（报价与清算价之差来衡量）最大,模型建立：设有N类物品要拍卖，第j类的物品数量Sj(j=1,N)，有M个投标者，投标者
35、i(i=1,M)对第j类物品的投标价格为bij，投标者购买点额总件数不能超过Tj，用0-1变量xij表示是否分配一件第j类物品给投标者i，xij=1(分配)或0(不分配),程序编写:,说明：(1)从Excel中读取数据有两种方式，一种是根据Excel表格中指定的名称与Lingo程序中设定的名称一致来读取，另一种是采用指定位置的读取数据。(2)Excel区域命名的方法(3)Excel文件的位置需要指定文件的具体路径,求解结果为：,例5-10(面试顺序问题)4名同学到一家公司参加3个阶段的面试，要经过初试-复试-面试，不允许插队，面试时间如下表所示:,4名同学约定他们全部面试完以后一起离开公司，假定现在时间是早上8点，请问他们最早何时离开。,模型建立：记tij为第i名同学参加第j阶段面试需要的时间，xij表示第i名同学参加第j阶段面试的开始时刻(为了方便，记早上8点为0时刻)(i=1,.,4,j=1,.,3),T为完成全部面试的最少时间，则优化目标为：,个人时间的先后次序约束：,同阶段不同同学时间不相容(同阶段靠前同学的完成时间小于靠后同学的开始时间)：,不妨给定i,k的关系为ik。目标可写为如下线性优化：,程序编写：,计算结果：,
