第4讲 线性规划 (2).ppt

1、,线性规划,目的,内容,2. 掌握用数学软件包求解线性规划问题.,1. 了解线性规划的基本内容.,2. 用数学软件包MATLAB求解线性规划问题.,3. 用数学软件包LINDO、LINGO求解线性规划问题.,1. 引例.,生产计划问题,max f= 5x1 +2x2,求最大利润,三种材料量的限制,生产量非负,P38例2,线性规划模型三要素,决策变量：向量(x1 xn)T ,决策人要考虑和控制的因素非负； 约束条件：线性等式或不等式； 目标函数：Z=(x1 xn) 线性式，求Z极大或极小；,6,一般形式,目标函数,约束条件,线性规划模型,矩阵形式,1、满足约束条件的变量的值称为可行解。,2、可行

2、解的集合称为可行域。,3、使目标函数达到最大（小）值的可行解称为最优解。,4、相应的目标函数的值称为最优值。,线性规划模型相关概念,运输问题,解：设A1,A2调运到三个粮站的大米分别为x1， x2， x3， x4， x5， x6吨。,题设量可总到下表：,结合存量限制和需量限制得数学模型：,m个产地A1,Am联合供应n个销地B1,Bn,各产 地至各销地单位运价(单位:元/吨)为cij，问如何调运使 总运费最少?,一般运输问题,总运价,产量限制,需量限制,运量非负,假设产销平衡:,在很多实际问题中,解题思想和运输问题同出一辙, 也就是说我们可以用运输模型解决其他问题.,设有n件工作B1, B2,

3、Bn,分派给n人A1, A2, An去 做,每人只做一件工作且每件工作只派一个人去做,设Ai 完成Bj的工时为cij,问应如何分派才能完成全部工作的 总工时最少.,每件工作只派1人,每个人只派做1件,变量xi只取0和1,故建立 的模型也称0-1规划.,分派问题,选址问题,现要做100套钢架,用长为2.9m、2.1m和1.5m的元 钢各一根,已知原料长7.4m,问如何下料,使用的原材料 最省?,分析:,下料方式：,最省：,1.所用刚架根数最少；,2.余料最少,下料问题,线性规划模型,不同方法截得每种根长的总数至少100,此例的变量xi只取正整数, 故建立的模型也称整数规划. 0-1规划是整数规划

4、的特殊情形.,线性规划模型,应 用,市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划) 生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”) 库存管理(合理物资库存量，停车场大小，设备容量) 运输问题 财政、会计(预算，贷款，成本分析，投资，证券管理) 人事(人员分配，人才评价，工资和奖金的确定) 设备管理(维修计划，设备更新) 城市管理(供水，污水管理，服务系统设计、运用),练习：,1、某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台数及A、B两种原材料的消耗量，见表1-1。该工厂每生产一件产品可获利润2元，每生产一件产品可获利润3元，问应如何安排

5、生产计划使该工厂获得的利润最大？,生产计划问题,如何制定生产计划，使两种产品总利润最大？,2、某鸡厂共饲养1万只鸡，用大豆和谷物混合喂养，已知每只鸡消耗饲料1kg /天，鸡至少需要蛋白质、钙分别为0.22、0.06 kg/天，每公斤大豆含蛋白质、钙为50、0.2，每公斤谷物含蛋白质、钙为10、0.1，大豆和谷物售价0.4、0.2元/kg。,问饲料怎么混合才能使成本最低？,1、,2、设：每只鸡需要大豆x1公斤，谷物x2公斤，,设：养鸡场每天需要大豆x1公斤，谷物x2公斤,用MATLAB优化工具箱解线性规划,命令：x=linprog（c, A, b）,2. 模型：min z=cX,命令：x=lin

6、prog（c，A，b，Aeq,beq）,注意：若没有不等式： 存在，则令A= ，b= .,命令：1 x=linprog（c，A，b，Aeq,beq, VLB，VUB） 2 x=linprog（c，A，b，Aeq,beq, VLB，VUB, X0）,注意：1 若没有等式约束: , 则令Aeq= , beq= . 2其中X0表示初始点,4. 命令：x,fval=linprog() 返回最优解及处的目标函数值fval.,解: 编写M文件xxgh2.m如下： c=6 3 4; A=0 1 0; b=50; Aeq=1 1 1; beq=120; vlb=30;0;20; vub=; x,fval=li

7、nprog(c,A,b,Aeq,beq,vlb,vub),To MATLAB (xxgh2),解 编写M文件xxgh1.m如下： c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6; A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08; b=850;700;100;900; Aeq=; beq=; vlb=0;0;0;0;0;0; vub=; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),To MATLAB (xxgh1),P

8、40 例1，2,例3,编写M文件xxgh4.m如下： c = 40 36; A=-5 -3; b=-45; Aeq=; beq=; vlb = zeros(2,1); vub=9;15; %调用linprog函数： x,fval = linprog(c,A,b,Aeq,beq,vlb,vub),To MATLAB (xxgh4),结果为： x = 9.0000 0.0000 fval =360,注：若本问题有一个约束条件：x1、x2取整数. 故它是一个整数线性规划问题.这里把它当成一 个线性规划来解，求得其最优解刚好是整数：x1=9， x2=0，故它就是该整数规划的最优解.若用线性规 划解法求

9、得的最优解不是整数，将其取整后不一 定是相应整数规划的最优解，这样的整数规划应 用Lingo求解.,返 回,用LINDO、LINGO优化工具箱解线性规划,LINDO和LINGO的区别,LINDO和LINGO是美国LINDO系统公司开发的一套专门用于求解最优化问题的软件包。 LINDO用于求解线性规划和二次规划问题。 LINGO除了具有LINDO的全部功能,外，还可以用于求解非线性规划问题，也可以用于一些线性和非线性方程(组)的求解，等等。 由于LINGO可以实现LINDO的所有功能，LINDO已经不再发行了。,LINDO和LINGO软件能求解的优化模型,需要掌握的内容,1、能利用lingo求解

10、线性规划问题 2、正确阅读求解报告,使用Lingo的一些注意事项,“”与“=”功能相同。 变量与系数间相乘必须用”*”号，每行用”;”结束。 变量以字母开头，不能超过8个字符。 变量名不区分大小写（包括关键字）。 目标函数用min=3*x1+2*x2或max=3*x1+2*x2的格式表示。 “!”后为注释。 变量界定函数实现对变量取值范围的附加限制，共4种： bin(x) 限制x为0或1 bnd(L,x,U) 限制LxU free(x) 取消对变量x的默认下界为0的限制，即x可以取任意实数 gin(x) 限制x为整数,Model:min=7*x1+3*x2; x1+x2=345.5; x1=9

11、8; 2*x1+x2=600; gin(x1); gin(x2);end,lingo程序:,LINGO中完整的程序 model: title 生产计划问题; maxfmax=2*x1+3*x2; Ax1+2*x28; B4*x116; TIME4*x212; END,线性模型求解,运行结果 Model Title: 生产计划问题 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price MAXF 14.00000 1.000000 A 0.00000

12、0 1.500000 B 0.000000 0.1250000 TIME 4.000000 0.000000,50桶牛奶,时间: 480小时,至多加工100千克A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/千克，是否应改变生产计划？,每天：,例1 加工奶制品的生产计划,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),建立模型,max 72x1+64x2

13、 st 2）x1+x250 3）12x1+8x2480 4）3x1100 end,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE 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,20桶牛奶生产A1, 30桶生产A2，利润3360元.,模型求解,O

14、BJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE 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,原料无剩余,时间无剩余,加工能力剩余40,max 72x1+64x2 st 2）x1+x250 3）12x1+8x2480 4）3x1100 end,三种资源,“资源” 剩余为零的约束为紧

15、约束（有效约束）,结果解释,模型求解,reduced cost值表示当该非基变量增加一个单位时（其他非基变量保持不变）,目标函数减少的量(对max型问题) .,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE 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. ITERATION

16、S= 2,也可理解为： 为了使该非基变量变成基变量，目标函数中对应系数应增加的量,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE 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,结果解释,最优解下“资源”增加1单位时“效益”的增量,原料增1单位, 利润增48,时间增1单位, 利润增

17、2,能力增减不影响利润,影子价格,35元可买到1桶牛奶，要买吗？,35 48, 应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,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.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(SENSITIVITY) ANALYSIS?,Yes,x1系数范围(64,96),x2系数范围(48,72),A1获利增加到 30元/千克，应否改变生产计划,x1系数由243= 72 增加为303= 90，在允许范围内,不变！,(约束