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

1、,线性规划,历史悠久、理论成熟、应用广泛、许多方法的基础。,1939年苏联数学家康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视。,1951年美国经济学家库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。,线性规划研究的主要问题：,1、有一定的人力、财力、资源条件下， 如何合理安排使用，使得效益最高？,2、某项任务确定后，如何安排人、财、 物，使之最省？,一、生产计划问题,max f= 5x1 +2x2,求最大利润,三种材料量的限制,生产量非负,线性规划模型三要素,决策变量：向量(x1 xn)T ,决策人要考虑和控制的因素，一般为非负量

2、； 约束条件：线性等式或不等式； 目标函数：Z=(x1 xn) 线性式，求Z极大或极小；,7,一般形式,目标函数,约束条件,线性规划模型,矩阵形式,9,现有A1，A2，A3三个产粮区，可供应 粮食分别为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3（万吨）。产粮地到需求地的单位运价（元/吨）如下表所示. 问如何安排一个运输计划，使总的运输费用最少。,二、运输问题,10,设 xij (i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，,则运输费用为：,11,从产粮区运出去的量,12,运给需求地的量,13,这样得到下列运输问题的

3、数学模型：,m个产地A1,Am联合供应n个销地B1,Bn,各产 地至各销地单位运价(单位:元/吨)为cij，问如何调运使 总运费最少?,总运价,产量限制,需量限制,运量非负,1、产销平衡:,一般运输问题,m个产地A1,Am联合供应n个销地B1,Bn,各产 地至各销地单位运价(单位:元/吨)为cij，问如何调运使 总运费最少?,16,2、当产大于销时,数学模型为,即,17,3、当销大于产时,即,数学模型为,在很多实际问题中,解题思想和运输问题同出一辙, 也就是说我们可以用运输模型解决其他问题.,18,有三台机床加工三种零件，计划第i台（i=1,2,3）的生产任务为50、60、40个零件(三种零件

4、)，第 j 种(j=1,2,3)零件的需要量为 70、30、50个。第 i 台（i=1,2,3）机床加工每个零件需要的时间如下表所示。问如何安排生产任务使总的加工时间最少？,19,【解】 设 xi j (i=1,2,3；j=1,2,3,)为第 i 台机床加工第 j 种零件的数量，,则总的加工时间为,20,则此问题的数学模型为,练习p48.2题,现要做100套钢架,用长为2.9m、2.1m和1.5m的元 钢各一根,已知原料长7.4m,问如何下料,使用的原材料 最省?,分析:,下料方式：,最省：,1.所用刚架根数最少；,2.余料最少,三、下料问题,不同方法截得每种根长的总数至少100,此例的变量x

5、i只取正整数, 故建立的模型也称整数规划.,现有4份工作，4个人应聘，由于各人技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一人承担，试求使总费用最小的分派方案。,工作,人,费用,1 2 3 4,1 2 3 4,3 5 4 5,6 7 6 8,8 9 8 10,10 10 9 11,1,0,第i人做第j 件事,i=1,2, 3,4; j=1,2, 3,4,第i人不做第j 件事,四、指派问题,设有n件工作B1, B2, Bn,分派给n人A1, A2, An去 做,每人只做一件工作且每件工作只派一个人去做,设Ai 完成Bj的工时为cij,问应如何分派才

6、能完成全部工作的 总工时最少.,每件工作只派1人,每个人只派做1件,变量xi只取0和1,故建立 的模型也称0-1规划. 0-1规划是整数规划的特殊情形.,指派问题的一般形式,选址问题,应 用,市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划) 生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”) 库存管理(合理物资库存量，停车场大小，设备容量) 运输问题 财政、会计(预算，贷款，成本分析，投资，证券管理) 人事(人员分配，人才评价，工资和奖金的确定) 设备管理(维修计划，设备更新) 城市管理(供水，污水管理，服务系统设计、运用),练习：,1、某工厂在计划期内要安排生产

7、、两种产品，已知生产单位产品所需的设备台数及A、B两种原材料的消耗量，见表1-1。该工厂每生产一件产品可获利润2元，每生产一件产品可获利润3元，问应如何安排生产计划使该工厂获得的利润最大？,如何制定生产计划，使两种产品总利润最大？,2、某鸡厂共饲养1万只鸡，用大豆和谷物混合喂养，已知每只鸡消耗饲料1kg /天，鸡至少需要蛋白质、钙分别为0.22、0.06 kg/天，每公斤大豆含蛋白质、钙为50、0.2，每公斤谷物含蛋白质、钙为10、0.1，大豆和谷物售价0.4、0.2元/kg。,问饲料怎么混合才能使成本最低？,1、,2、设：每只鸡需要大豆x1公斤，谷物x2公斤，,用MATLAB优化工具箱解线性

8、规划,命令：x=linprog（c, A, b）,2. 模型：min z=cX,命令：x=linprog（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;

9、Aeq=1 1 1; beq=120; vlb=30;0;20; vub=; x,fval=linprog(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=li

10、nprog(c,A,b,Aeq,beq,vlb,vub),To MATLAB (xxgh1),P40 例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取整数. 故它是一个整数线性规划问题.这里把它当成一 个线性规划来解

11、，求得其最优解刚好是整数：x1=9， x2=0，故它就是该整数规划的最优解.若用线性规 划解法求得的最优解不是整数，将其取整后不一 定是相应整数规划的最优解，这样的整数规划应 用Lingo求解.,返 回,用LINGO优化工具箱解线性规划,需要掌握的内容,1、能利用lingo求解线性规划问题 2、正确阅读求解报告,使用Lingo的一些注意事项,“”与“=”功能相同。 变量与系数间相乘必须用”*”号，每行用”;”结束。 变量以字母开头，不能超过8个字符。 变量名不区分大小写（包括关键字）。 目标函数用min=3*x1+2*x2或max=3*x1+2*x2的格式表示。 “!”后为注释。 变量界定函数

12、实现对变量取值范围的附加限制，共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=98; 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: 生产

13、计划问题 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.000000 1.500000 B 0.000000 0.1250000 TIME 4.000000 0.000000,50桶牛奶,时间: 480小时,至多加工100千克A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/千

14、克，是否应改变生产计划？,每天：,例1 加工奶制品的生产计划,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),建立模型,max 72x1+64x2 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 O

15、R 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元.,模型求解,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.00000

16、0 3) 0.000000 2.000000 4) 40.000000 0.000000,原料无剩余,时间无剩余,加工能力剩余40,max 72x1+64x2 st 2）x1+x250 3）12x1+8x2480 4）3x1100 end,三种资源,“资源” 剩余为零的约束为紧约束（有效约束）,结果解释,模型求解,reduced cost值表示当该非基变量增加一个单位时（其他非基变量保持不变）,目标函数减少的量(对max型问题) .,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.0

17、00000 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 X2 30.000000 0.000000 ROW SLACK O

18、R SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000,结果解释,最优解下“资源”增加1单位时“效益”的增量,原料增1单位, 利润增48,时间增1单位, 利润增2,能力增减不影响利润,影子价格,35元可买到1桶牛奶，要买吗？,35 48, 应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE AL

19、LOWABLE 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(SENSITI

20、VITY) ANALYSIS?,Yes,x1系数范围(64,96),x2系数范围(48,72),A1获利增加到 30元/千克，应否改变生产计划,x1系数由243= 72 增加为303= 90，在允许范围内,不变！,(约束条件不变),结果解释,例1中给出的A1 ， A2两种奶制品的生产条件、利润，及工厂的“资源”限制都不变。为增加工厂的获利，开发了奶制品的深加工技术：用2小时和3元加工费，可将1公斤A1加工成0.8公斤高级奶制品B1 ，可将1公斤A2加工成0.75公斤高级奶制品B2 ，每公斤B1可获利44元，每公斤B2可获利32元，试为该厂制订一个生产销售计划，使每天的净利润最大，并讨论一下问题

21、：,例2 奶制品的生产销售计划,(1)若投资30元可以增加供应1桶牛奶，投资3元可以增加1小时劳动时间，应否做这些投资，若每天投资150元，可赚回多少？ (2)每公斤B1 ，B2的获利经常有10的波动，对制订的生产销售计划有无影响？若每公斤B1的获利下降10，计划应该变化吗？,奶制品的生产销售计划,制订生产计划，使每天净利润最大,50桶牛奶, 480小时,至多100公斤A1,出售x1 千克 A1, x2 千克 A2，,x3千克 B1, x4千克 B2,原料供应,劳动时间,加工能力,决策变量,目标函数,利润,约束条件,非负约束,x5千克 A1加工B1， x6千克 A2加工B2,附加约束,基本模型

22、：,Lingo程序： max=24*x1+16*x2+44*x3+32*x4-3*x5-3*x6; 4*x1+3*x2+4*x5+3*x6600; 4*x1+2*x2+6*x5+4*x6480; x1+x5100; x3=0.8*x5; x4=0.75*x6;,模型求解,软件实现,LINDO 6.1,OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.0000

23、00 X5 24.000000 0.000000 X6 0.000000 1.520000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2,OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.00

24、0000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2,结果解释,每天销售168 千克A2和19.2 千克B1， 利润3460.8（元）,

25、将得到的24千克A1全部加工成B1 8桶牛奶加工成A1，42桶牛奶加工成A2，,除加工能力外均为紧约束,为了激活灵敏性分析，运行LINGO|Options，选择General Solver Tab，在Dual Computations列表框中，选择Prices and Ranges选项。,结果解释,OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.00000

26、0 X5 24.000000 0.000000 X6 0.000000 1.520000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000,增加1桶牛奶使利润增长3.1612=37.92,增加1小时时间使利润增长3.26,30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？,投资150元增加5桶牛奶，可赚回189.6元。（大于增加时间的

27、利润增长）,结果解释,B1,B2的获利有10%的波动，对计划有无影响,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 24.000000 1.680000 INFINITY X2 16.000000 8.150000 2.100000 X3 44.000000 19.750002 3.166667 X4 32.000000 2.026667 INFINITY X5 -3.000000 15.8

28、00000 2.533334 X6 -3.000000 1.520000 INFINITY ,B1获利下降10%，超出X3 系数允许范围,B2获利上升10%，超出X4 系数允许范围,波动对计划有影响,生产计划应重新制订：如将x3的系数改为39.6计算，会发现结果有很大变化。,若每公斤B1的获利向下波动10，应将原模型目标函数式中x3的系数改为39.6，重新计算，得到最优解为x1 0， x2 =160， x3 =0, x4 =30, x5 =0, x6 =40,最优值为=3400。计划变化比较大。 最优生产计划对B1或B2获利的波动很敏感。,例3 某储蓄所每天的营业时间为上午9点到下午17点.

29、根据经验, 每天不同时间所需要的服务员数量为:,储蓄所可以雇佣全时和半时两类服务员. 全时服务员每天报酬100元, 从上午9点到下午5点工作, 但中午12点到下午2点之间必须安排1小时的午餐时间.储蓄所每天可以不超过3名的半时服务员, 每个半时服务员必须连续工作4小时, 报酬40元, 问 （1）该储蓄所该如何雇佣全时和半时服务员? （2）如果不能雇佣半时服务员, 每天至少增加多少费用？ （3）如果雇佣半时服务员的数量没有限制, 每天可以减少多少费用?,分析：,解决此问题的关键是确定聘用全时服务员及半时服务员的人数, 但还要考虑全时服务员有吃午餐的时间, 故把全时服务员分为两类: 午餐时间为12

30、时至下午1时的及下午1时至下午2时的; 而半时服务员按上班时间进行划分.,关键是类别划分,模型建立,设 为午餐时间为下午12时的全时服务员的人数, 为午餐时间为下午1时的全时服务员的人数, 而 分别 表示从9点, 10点, 11点, , 1点开始上班的半时服务员 人数, 则目标函数为,约束条件按各个小时需要的服务员人数确定, 则有,此外, 对半时服务员人数的限制,对决策变量的限制为,为整数.,由上述分析, 得到相应的数学模型为,为整数.,Lingo程序： min=100*x1+100*x2+40*y1+40*y2+40*y3+40*y4+40*y5; x1+x2+y14; x1+x2+y1+y

31、23; x1+x2+y1+y2+y34; x2+y1+y2+y3+y46; x1+y2+y3+y4+y55; x1+x2+y3+y4+y56; x1+x2+y4+y58; x1+x2+y58; y1+y2+y3+y4+y53; gin(x1); gin(x2);gin(y1);gin(y2);gin(y3);gin(y4);gin(y5);,Global optimal solution found at step: 11 Objective value: 820.0000 Branch count: 1 Variable Value Reduced Cost X1 2.000000 100.

32、0000 X2 5.000000 100.0000 Y1 0.0000000 40.00000 Y2 0.0000000 40.00000 Y3 2.000000 40.00000 Y4 0.0000000 40.00000 Y5 1.000000 40.00000 Row Slack or Surplus Dual Price 1 820.0000 1.000000 2 3.000000 0.0000000 3 4.000000 0.0000000 4 5.000000 0.0000000 5 1.000000 0.0000000 6 0.0000000 0.0000000 7 4.000000 0.0000000,（1）在Lingo下得到问题的解:,（2）若不能雇佣半时服务员（添加y1+y2+y3+y4+y50;） 则最优解为,因而多支出 元.,（3）若对半时服务员人数没有限制（去掉y1+y2+y3+y4+y53;） 则最优解为,节省开支260元.,例3 投资的收益和风险,二、基本假设和符号规定,1.总体风险用所投资的Si中最大的一个风险来衡量，即：,三、模型的建立与分析,3.建立模