第2讲线性规划与LINGO编程

1、华中农业大学数学建模创新实践基地系列课件华中农业大学数学建模创新实践基地系列课件第第2 2讲讲 线性规划与线性规划与LINGOLINGO编编程程华中农业大学华中农业大学内容说明内容说明 以下内容在以下内容在数学数学建模与数学实验建模与数学实验（第二版）（第二版） （汪晓银（汪晓银 ，周保，周保平主编）第平主编）第3章章2.1 什么是数学规划什么是数学规划2.2 连续性线性规划连续性线性规划2.3 敏感性分析敏感性分析2.4 整数线性规划整数线性规划2.5 0-1规划规划内容说明内容说明 数学规划数学规划俗称最优化俗称最优化, ,首先是一种理首先是一种理念念, ,其次才是一种方法其次才是一种方法

2、, ,它所追求的是一种它所追求的是一种“至善至善”之道之道, ,一种追求卓越的精神一种追求卓越的精神. .2.1 什么是数学规划什么是数学规划 小明同学，烧一壶水要小明同学，烧一壶水要8分钟，灌开水分钟，灌开水要要1分钟，取牛奶和报纸要分钟，取牛奶和报纸要5分钟，整理书包分钟，整理书包要要6分钟，为了尽快做完这些事，怎样安排分钟，为了尽快做完这些事，怎样安排才能使时间最少？最少需要几分钟？才能使时间最少？最少需要几分钟？ 十个人各提一只水桶，同时到水龙头十个人各提一只水桶，同时到水龙头前打水。设水龙头注满第一个人的桶需要前打水。设水龙头注满第一个人的桶需要1分钟，注满第二个人的桶需要分钟，注满

3、第二个人的桶需要2分钟，依此分钟，依此类推，注满第几个人的桶就需要几分钟，类推，注满第几个人的桶就需要几分钟，如果只有一只水龙头，适当安排这如果只有一只水龙头，适当安排这10个人个人的顺序，就可以使每个人所费的时间总和的顺序，就可以使每个人所费的时间总和尽可能小，问这个总费时至少是几分钟？尽可能小，问这个总费时至少是几分钟？ 2.1 什么是数学规划什么是数学规划 数学规划数学规划(最优化最优化)作为一门学科孕育于作为一门学科孕育于20世世纪的纪的30年代年代,诞生于第二次世界大战弥漫的硝烟诞生于第二次世界大战弥漫的硝烟中。中。 数学规划指在一系列客观或主观限制条件数学规划指在一系列客观或主观限

4、制条件下，寻求合理分配有限资源使所关注的某个或多下，寻求合理分配有限资源使所关注的某个或多个指标达到最大（或最小）的数学理论和方法个指标达到最大（或最小）的数学理论和方法，是运筹学里一个十分重要的分支。是运筹学里一个十分重要的分支。 2.1 什么是数学规划什么是数学规划最优化问题的最优化问题的数学模型的一般形式数学模型的一般形式为：为： xfzopt skjiRDxnkxtmjxglixhts , 1, 0 , 1, 0 , 1, 0 .（1）（2）三个要素：三个要素：决策变量决策变量decision bariable，目标函数目标函数objective function，约束条件约束条件co

5、nstraints。 2.1 什么是数学规划什么是数学规划 约束条件（约束条件（2）所确定的）所确定的x的范围称为的范围称为可行域可行域feasible region，满足（，满足（2）的解）的解x称为称为可行解可行解feasible solution，同时满足（，同时满足（1）（）（2）的解）的解x称为称为最优解最优解Optimal solution，整个可行域上的最优解，整个可行域上的最优解称为称为全局最优解全局最优解global optimal solution，可行域中，可行域中某个领域上的最优解称为某个领域上的最优解称为局部最优解局部最优解local optimal solution

6、。最优解所对应的目标函数值称为。最优解所对应的目标函数值称为最优值最优值optimum。 2.1 什么是数学规划什么是数学规划（一）（一）按有无约束条件按有无约束条件（2）可分为：）可分为：1.无约束优化无约束优化unconstrained optimization。2.约束优化约束优化constrained optimization。大部分实际问题都是约束优化问题。大部分实际问题都是约束优化问题。 优化模型的分类优化模型的分类2.1 什么是数学规划什么是数学规划（二）（二）按决策变量取值是否连续按决策变量取值是否连续可分为：可分为：1.数学规划或连续优化。数学规划或连续优化。可继续划分为可继

7、续划分为线性规划线性规划(LP)Linear programming和和非线性规划非线性规划(NLP) Nonlinear programming。在。在非线性规划中有一种规划叫做非线性规划中有一种规划叫做二次规划二次规划(QP)Quadratic programming，目标为二次函数，目标为二次函数，约束为线性函数。约束为线性函数。2.离散优化或组合优化。离散优化或组合优化。包含：包含：整数规划整数规划(IP)Integer programming，整数，整数规划中又包含很重要的一类规划：规划中又包含很重要的一类规划：0-1（整数）规（整数）规划划Zero-one programming，

8、这类规划问题的决策，这类规划问题的决策变量只取变量只取0或者或者1。2.1 什么是数学规划什么是数学规划（三）（三）按目标的多少按目标的多少可分为：可分为：1.单目标规划。单目标规划。2.多目标规划。多目标规划。（四）（四）按模型中参数和变量是否具有不确定性按模型中参数和变量是否具有不确定性可分为：可分为：1.确定性规划。确定性规划。2.不确定性规划。不确定性规划。（五）（五）按问题求解的特性按问题求解的特性可分为：可分为：1.目标规划。目标规划。2.动态规划。动态规划。3.多层规划。多层规划。4.网络优化。网络优化。5.等等。等等。2.1 什么是数学规划什么是数学规划 LINGO软件和软件和

9、MATLAB软件。软件。 对于对于LINGO软件，线性优化求解程序通常使用软件，线性优化求解程序通常使用单纯形法单纯形法simplex method，单纯形法虽然在实际应用，单纯形法虽然在实际应用中是最好最有效的方法，但对某些问题具有指数阶的中是最好最有效的方法，但对某些问题具有指数阶的复杂性，为了能解大规模问题，也提供了复杂性，为了能解大规模问题，也提供了内点算法内点算法interior point method备选（备选（LINGO中一般称为障碍中一般称为障碍法，即法，即barrier），非线性优化求解程序采用的是），非线性优化求解程序采用的是顺序顺序线性规划法线性规划法，也可用，也可用顺

10、序二次规划法顺序二次规划法，广义既约梯度，广义既约梯度法，另外可以使用多初始点（法，另外可以使用多初始点（LINGO中称中称multistart）找多个局部最优解增加找全局最优解的可能，还具有找多个局部最优解增加找全局最优解的可能，还具有全局求解程序全局求解程序分解原问题成一系列的分解原问题成一系列的凸规划凸规划。求解优化问题常用的软件求解优化问题常用的软件2.1 什么是数学规划什么是数学规划线性规划的一般形式：线性规划的一般形式： njjjxczz1)max(min或njxmibxatsjijij, 1, 0 , 1,)( n1j.或或2.2 连续性线性规划连续性线性规划 一般线性规划问题都

11、可以通过引入非负的松弛一般线性规划问题都可以通过引入非负的松弛变量变量slack variable与非负的剩余变量与非负的剩余变量surplus v-ariable的方法化为的方法化为标准形式标准形式（约束全是等约束）。（约束全是等约束）。 线性规划问题的可行域线性规划问题的可行域feasible region是一个凸是一个凸集集convex set（任意两点的连线上的点都在区域内部，（任意两点的连线上的点都在区域内部，可以看作是没有凹坑的凸多面体），所以最优解可以看作是没有凹坑的凸多面体），所以最优解Optimal solution/point在凸多面体的某个顶点上达在凸多面体的某个顶点上达

12、到到 求解方法：单纯形算法求解方法：单纯形算法simplex method。 2.2 连续性线性规划连续性线性规划1.比例性比例性：每个决策变量对目标函数以及右端项：每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比。的贡献与该决策变量的取值成正比。2.可加性可加性：每个决策变量对目标函数以及右端项：每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关。的贡献与其他决策变量的取值无关。3.连续性连续性：每个决策变量的取值都是连续的。：每个决策变量的取值都是连续的。 连续线性规划问题的性质连续线性规划问题的性质要解决的问题的目标可以用数值指标反映要解决的问题的目标可以用数值

13、指标反映对于要实现的目标有多种方案可选择对于要实现的目标有多种方案可选择有影响决策的若干约束条件有影响决策的若干约束条件2.2 连续性线性规划连续性线性规划。问问如如何何调调运运使使运运费费最最低低如如下下公公里里单单位位距距离离两两个个粮粮库库到到三三个个粮粮站站的的吨吨大大米米分分别别为为三三个个粮粮站站至至少少需需要要吨吨吨吨为为两两个个粮粮库库现现存存大大米米分分别别调调运运大大米米向向三三个个粮粮站站有有两两个个粮粮库库,):(,5 , 4 , 2,8 ,4, 32121BBBAA例例1 运输问题运输问题2.2 连续性线性规划连续性线性规划解解 设设A1,A2调运到三个粮站的大米分别

14、为调运到三个粮站的大米分别为x1，x2， x3， x4， x5， x6吨。吨。题设量可总到下表：题设量可总到下表：2.2 连续性线性规划连续性线性规划结合存量限制和需量限制得数学模型结合存量限制和需量限制得数学模型：65432124123082412minxxxxxxf 0,54284.654321635241654321xxxxxxxxxxxxxxxxxxts2.2 连续性线性规划连续性线性规划程序编写程序编写1model:min=12*x1+24*x2+8*x3+30*x4+12*x5+24*x6 ;x1+x2+x34 ;x4+x5+x62 ;x2+x54 ;x3+x65 ;end提示：课

15、件中的程提示：课件中的程序请先粘贴在记事序请先粘贴在记事本中再本中再转帖于转帖于lingo软件软件中中2.2 连续性线性规划连续性线性规划运行结果运行结果 Global optimal solution found. Objective value: 160.0000 Total solver iterations: 0 Variable Value Reduced Cost X1 2.000000 0.000000 X2 0.000000 28.00000 X3 2.000000 0.000000 X4 0.000000 2.000000 X5 4.000000 0.000000 X6 3.

16、000000 0.000000 Row Slack or Surplus Dual Price 1 160.0000 -1.000000 2 0.000000 16.00000 3 1.000000 0.000000 4 0.000000 -28.00000 5 0.000000 -12.00000 6 0.000000 -24.000002.2 连续性线性规划连续性线性规划84库库存存量量x23x22x21A2542需要量需要量x13x12x11A1B3B2B1粮库粮库粮站粮站距离及运量距离及运量12122430824变量更换为：变量更换为：2.2 连续性线性规划连续性线性规划2322211

17、3121124123082412xxxxxxf min 054284232221131211231322122111232221131211xxxxxxxxxxxxxxxxxxts,.模型模型:2.2 连续性线性规划连续性线性规划程序编写程序编写MODEL:TITLE 调运大米的运输问题程序调运大米的运输问题程序3;!定义集合段定义集合段;SETS:LIANGKU/1.2/:A;!定义粮库的集合定义粮库的集合;LIANGZHAN/1.3/:B;!定义粮站的集合定义粮站的集合;YULIANG(LIANGKU,LIANGZHAN):X,C;!定义运量和距离定义运量和距离;ENDSETSDATA:!

18、粮库到粮站的距离粮库到粮站的距离;C= 12 24 8 30 12 24;2.2 连续性线性规划连续性线性规划!粮库的限量粮库的限量;A=4 8 ;!粮站的限量粮站的限量;B=2 4 5;ENDDATAOBJMIN=SUM(YULIANG:C*X);!粮库上限的约束粮库上限的约束;FOR(LIANGKU(I):LK SUM(LIANGZHAN(J):X(I,J)B(J);END 2.2 连续性线性规划连续性线性规划程序的调试程序的调试1.直接点击运行，如果出错会弹出错误提示，根直接点击运行，如果出错会弹出错误提示，根据提示做相应的修改；据提示做相应的修改；2.可以用可以用“！”把约束变成说明语

19、句，而把这条把约束变成说明语句，而把这条语句屏蔽掉，缩小寻找出错的范围；语句屏蔽掉，缩小寻找出错的范围；3.可以边写程序边运行，保证每行书写都是正确可以边写程序边运行，保证每行书写都是正确的程序；的程序；2.2 连续性线性规划连续性线性规划例例2 阶段生产问题阶段生产问题 某公司生产某产品某公司生产某产品,最大生产能力为最大生产能力为10000单位单位,每每单位存储费单位存储费2元元,预定的销售量与单位成本如下预定的销售量与单位成本如下:月份单位成本(元) 销售量1234 70 6000 72 7000 80 12000 76 6000求一生产计划求一生产计划,使使 1)满足需求满足需求; 2

20、)不超过生产能力不超过生产能力;3)成本成本(生产成本与存储费之和生产成本与存储费之和)最低最低.2.2 连续性线性规划连续性线性规划 1 je 解解 假定假定1月初无库存月初无库存,4月底买完月底买完,当月生产的不库当月生产的不库存存,库存量无限制库存量无限制.为为单单位位成成本本，为为存存储储费费，为为销销售售量量，月月产产量量，为为第第：设设模模型型iiiicedix jiijiidx11 31j 41jjjxc fmin 4 ,23, 11000003 , 2 , 1.414111ixdxjdxtsiiiiijijiii2.2 连续性线性规划连续性线性规划model:title 生产计

21、划程序生产计划程序1;Sets:yuefen/1.4/:c,x,e,d;endsetsdata:c=70 71 80 76;d=6000 7000 12000 6000;e=2 2 2 2 ;a=10000;enddatamin=sum(yuefen:c*x)+ sum(yuefen(j)|j#lt#4: sum(yuefen(i)|i#le#j:x-d)*e(j+1);for(yuefen(j)|j#lt#4: sum(yuefen(i)|i#le#j:x) sum(yuefen(i)|i#le#j:d);sum(yuefen:x)= sum(yuefen:d);for(yuefen:xa)

22、;end 2.2 连续性线性规划连续性线性规划.iiiiisicedix月月初初的的库库存存量量为为为为单单位位成成本本，设设第第为为存存储储费费，为为销销售售量量，月月产产量量，为为第第：设设模模型型 4141miniiiiiisexcf.ts 1is, iiidxs 4 , 3 , 2 , 1 i0051 ss432104321100000， isixii2.2 连续性线性规划连续性线性规划Model:Title 生产计划程序生产计划程序2;Sets:yuefen/1.4/:c,x,e,d,s;endsetsdata:c=70 71 80 76;d=6000 7000 12000 6000

23、;e=2 2 2 2 ;a=10000;enddatamin=sum(yuefen:c*x+e*s);for(yuefen(i)|i#lt#4:s(i+1)=s(i)+x(i)-d(i);s(4)+x(4)-d(4)=0;s(1)=0;for(yuefen:xa);End2.2 连续性线性规划连续性线性规划.,:月月的的销销售售量量示示的的第第表表存存储储费费之之和和月月卖卖出出时时的的生生产产成成本本与与生生产产的的产产品品在在第第月月表表示示第第月月卖卖出出的的数数量量月月生生产产的的产产品品在在第第表表示示第第设设化化为为运运输输问问题题模模型型jdjicjixjijij 月份单位成本(

24、元) 销售量1234 70 6000 72 7000 80 12000 76 60002.2 连续性线性规划连续性线性规划76827676-80-7472-747270生产月10000100001000010000产量产量600041200070006000销量销量4321321需求月费用cij2.2 连续性线性规划连续性线性规划且且为为整整数数010000.min41,411 ijijijjijijjjiijijxxdxtsxcf建立模型如下：建立模型如下：2.2 连续性线性规划连续性线性规划model:title 生产计划程序生产计划程序3;sets:yuefen/1.4/:a,d,xx;

25、!定义上三角矩阵定义上三角矩阵;link(yuefen,yuefen)|&2#ge#&1:c,x;endsetsdata:c=70 72 74 76 71 73 75 80 82 76;d=6000 7000 12000 6000;a=10000 10000 10000 10000;enddatamin=sum(link:c*x);for(yuefen(i):sum(yuefen(j)|j#ge#i:x(i,j)d(j););!得到每个月的生产量得到每个月的生产量;for(yuefen(i):xx=sum(yuefen(j)|j#ge#i:x(i,j);End2.2 连续性线性规划连续性线性规

26、划Model Title: :生产计划程序生产计划程序1 Variable Value Reduced Cost A 10000.00 0.000000 C( 1) 70.00000 0.000000 C( 2) 71.00000 0.000000 C( 3) 80.00000 0.000000 C( 4) 76.00000 0.000000 X( 1) 10000.00 0.000000 X( 2) 10000.00 0.000000 X( 3) 5000.000 0.000000 X( 4) 6000.000 0.000000 E( 1) 2.000000 0.000000 E( 2) 2

27、.000000 0.000000 E( 3) 2.000000 0.000000 E( 4) 2.000000 0.000000 D( 1) 6000.000 0.000000 D( 2) 7000.000 0.000000 D( 3) 12000.00 0.000000 D( 4) 6000.000 0.000000 2.2 连续性线性规划连续性线性规划 设有两个工厂设有两个工厂A、B，产量都是，产量都是10万个，工厂万个，工厂有三个仓库有三个仓库x，y，z，产品都先送到仓库。现有四，产品都先送到仓库。现有四个顾客分别为甲，乙，丙，丁，需求量分别为个顾客分别为甲，乙，丙，丁，需求量分别为3，

28、5，4，5万个。工厂到仓库、仓库到顾客的运费单价万个。工厂到仓库、仓库到顾客的运费单价（元（元/个）见下表所示。试求总运费最少的运输方个）见下表所示。试求总运费最少的运输方案以及总运费。案以及总运费。 AB甲乙丙丁x43571020y2196715z5220674课后训练课后训练model:title 转运问题转运问题;sets: Plant /A, B/: produce; Warhouse /x, y, z/; Customer /1.4/: require; LinkI ( Plant, Warhouse): cI, xI; LinkII ( Warhouse, Customer): c

29、II, xII;endsetsdata: produce = 10, 10; require = 3, 5, 4, 5; cI = 4, 2, 5, 3, 1, 2; cII = 5, 7, 10, 20, 9, 6, 7, 15, 20, 6, 7, 4;enddata课后练习课后练习OBJ min = sum( LinkI: cI * xI) + sum( LinkII: cII * xII);! The supply constraints;for( Plant(i): SUP sum( Warhouse(j): xI(i,j) = produce(i);! 运进仓库的量等于运出的量运进

30、仓库的量等于运出的量;for( Warhouse(j): MID sum( Plant(i): xI(i,j)=sum( Customer(k): xII(j,k);! The demand constraints;for( Customer(k): DEM sum( Warhouse(j): xII(j,k) = require(k);课后练习课后练习连续投资连续投资10万元万元A：从第：从第1年年 到第到第4年每年初要投资，次年末回收年每年初要投资，次年末回收本利本利1.15B：第第3年初投资，到第年初投资，到第5年末回收年末回收1.25，最大投资，最大投资4万元万元C：第第2年初投资，到

31、第年初投资，到第5年末回收年末回收1.40，最大投资，最大投资3万元万元D：每年初投资，每年末回收每年初投资，每年末回收1.11。求：求：5年末总资本最大。年末总资本最大。练习练习2 2 连续投资连续投资课后练习课后练习第1年第2年第3年第4年第5年Ax1Ax1Ax1Ax1ABx3BCx2CDx1Dx1Dx1Dx1Dx1D练习练习2解答解答变量设置变量设置课后练习课后练习模型建立模型建立 423511222123331234423534max1.151.401.251.11101.1131.151.1141.151.111.151.11,0,15ACBDADACDDCABDADBADADDAD

32、iAiBiCiDfxxxxxxxxxxxxxxxxxxxxxxxxxxxxi 课后练习课后练习程序编写程序编写model:title 投资问题投资问题;max=1.15*x4a+1.40*x2c+1.25*x3b+1.06*x5d;x1a+x1d=100000;x2a+x2c+x2d=1.06*x1d;x3a+x3b+x3d=1.15*x1a+1.06*x2d;x4a+x4d=1.15*x2a+1.06*x3d;x5d=1.15*x3a+1.06*x4d;x3b=40000;x2c=30000;课后练习课后练习运行结果运行结果Global optimal solution found. Obj

33、ective value: 143750.0 Total solver iterations: 2 Model Title: 投资问题投资问题 Variable Value Reduced Cost X4A 45000.00 0.000000 X2C 30000.00 0.000000 X3B 40000.00 0.000000 X5D 0.000000 0.000000 X1A 71698.11 0.000000 X1D 28301.89 0.000000 X2A 0.000000 0.000000 X2D 0.000000 0.3036000E-01 X3A 0.000000 0.0000

34、00 X3D 42452.83 0.000000 X4D 0.000000 0.2640000E-01课后练习课后练习 例例3 生产计划问题生产计划问题某工厂计划安排生产某工厂计划安排生产，两种产品，已知每两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及种单位产品的利润，生产单位产品所需设备台时及A,B两种原材料的两种原材料的消耗，现有原材料和设备台时的定额如表所示，问：消耗，现有原材料和设备台时的定额如表所示，问：）怎么安排生产使得工厂获利最大？）怎么安排生产使得工厂获利最大？）产品）产品的单位利润降低到的单位利润降低到1.8万元，要不要改变生产计划，如果万元，要不要改变生产计划

35、，如果降低到降低到1万元呢？万元呢？）产品）产品的单位利润增大到的单位利润增大到5万元，要不要改变生产计划？万元，要不要改变生产计划？）如果产品）如果产品，的单位利润同时降低了的单位利润同时降低了1万元，要不要改变生产万元，要不要改变生产计划？计划？ 产品产品产品产品最大资源量最大资源量设备设备128台时台时原材料原材料A4016kg原材料原材料B0412kg单位产品利润单位产品利润232.3 敏感性分析敏感性分析2.3 敏感性分析敏感性分析程序编写程序编写model:title 生产计划问题生产计划问题;maxfmax=2*x1+3*x2;TIMEx1+2*x28;A4*x116;B4*x2

36、12;END2.3 敏感性分析敏感性分析运行结果运行结果 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.000000 1.500000 B 0.000000 0.1250000 TIME 4.000000 0.000000 对问题对问题1，安排是生产产品，安排是生产产品4单位，产品单位，产品2单位，最大盈单位，最大盈利为利为14万元万元 。2.3

37、 敏感性分析敏感性分析目标函数的系数变化的敏感性分析目标函数的系数变化的敏感性分析如果目标函数的系数发生变化，将会影响目标函数 f 斜率的变化，但是只要f 的斜率小于等于-1/2（也就是直线l夹在l1与l2之间时），最优解都在(4,2)上取到，最优解不变，从而生产计划不会变. 2.3 敏感性分析敏感性分析要使用敏感性分析要使用敏感性分析必须要在这里选择必须要在这里选择Prices & Ranges然后然后保存保存退出退出路径：路径：LINGOOptionsGeneral Solver(通用求解程序通用求解程序)选项卡选项卡2.3 敏感性分析敏感性分析要调出敏感性分析的结果，要调出敏感性分析的结

38、果，必须必须先求解先求解后再后再在程序窗在程序窗口下口下点击点击LINGORange， 2.3 敏感性分析敏感性分析Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allowable A

39、llowable RHS Increase Decrease A 8.000000 2.000000 4.000000 B 16.00000 16.00000 8.000000 TIME 12.00000 INFINITY 4.000000 当前变量系数允许增加量允许减少量对问题对问题2，产品，产品的单位利润降低到的单位利润降低到1.8万元，在（万元，在（1.5，）之间，所以不）之间，所以不改变生产计划。如果降低到改变生产计划。如果降低到1万元，不在（万元，不在（1.5，）内，要改变生产计划。）内，要改变生产计划。在程序中将目标函数的系数在程序中将目标函数的系数“2”改为改为“1”，可得新的计

40、划为，可得新的计划为安排是生产产品安排是生产产品2单位，产品单位，产品3单位，最大盈利为单位，最大盈利为11万元万元.对问题对问题3，要改变生产计划，更改程序得新计划为生产产品，要改变生产计划，更改程序得新计划为生产产品2单位，产品单位，产品3单位，最大盈利为单位，最大盈利为19万元万元.对问题对问题4，因为两个系数同时改变了，所以只有更改程序的数据，重新运，因为两个系数同时改变了，所以只有更改程序的数据，重新运行得：不改变生产计划，但是最大利润降低到行得：不改变生产计划，但是最大利润降低到8万元万元. 2.3 敏感性分析敏感性分析2.3 敏感性分析敏感性分析12121112max232841

41、6. .412,0fxxxxxstxx x0,34224. .12168min3213221321yyyyyyyt syyyg把y1,y2,y3作为三种原料的定价，定价的目标是在比生产产品获得更多利润的前提下的最小利润. 在最优情况下，在最优情况下，y的值就是资的值就是资源的源的影子价格，影子价格，影子价格有意影子价格有意义是有范围的义是有范围的。影子价格经济含义是：在资源得到最优配影子价格经济含义是：在资源得到最优配置，使总效益最大时，该资源投入量每增置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量加一个单位所带来总收益的增加量 2.3 敏感性分析敏感性分析Ranges i

42、n which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease A 8.000000 2.000000 4.000000 B 16.0

43、0000 16.00000 8.000000 TIME 12.00000 INFINITY 4.000000 运行结果运行结果 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.000000 1.500000 B 0.000000 0.1250000 TIME 4.000000 0.000000 2.3 敏感性分析敏感性分析1桶牛奶 3公斤A1 12

44、小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到的获利增加到 30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？ 每天：每天：例例4 加工奶制品的生产计划加工奶制品的生产计划2.3 敏感性分析敏感性分析x1桶牛奶生产桶牛奶生产A1 x2桶牛奶

45、生产桶牛奶生产A2 获利获利 243x1 获利获利 164 x2 原料供应原料供应 5021 xx劳动时间劳动时间 48081221 xx加工能力加工能力 10031x决策变量决策变量 目标函数目标函数 216472xxzMax每天获利每天获利约束条件约束条件非负约束非负约束 0,21xx线性线性规划规划模型模型(LP)2.3 敏感性分析敏感性分析Max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100; OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000

46、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= 220桶牛奶生产桶牛奶生产A1, 30桶生产桶生产A2，利润，利润3360元。元。 2.3 敏感性分析敏感性分析 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.00000

47、0 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？ 35 50; x2 + 2*x4 + x5 + 3*x6 20; x3 + x5 + 2*x715;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);end程序编写程序编写2.4 整数规划整数规划按模式按模式2切割切割12根根, ,按模式按模式5切割切割15根，余

48、料根，余料27米米 最优解：最优解：x2=12, x5=15, 其余为其余为0；最优值：最优值：27最优解：最优解：x2=15, x5=5, x7=5, 其余为其余为0；最优值：最优值：25。按模式按模式2切割切割15根，按模式根，按模式5切割切割5根，按模式根，按模式7切割切割5根，共根，共25根，余料根，余料35米米 当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以总根数最少为目标 2.4 整数规划整数规划练习练习3某服务部门一周中每天需要不同数目的雇员，某服务部门一周中每天需要不同数目的雇员，周一到周四每天至少需要周一到周四每天至少需要50人，周五至少需要人，周五至少需要

49、80人，人，周六和周日至少需要周六和周日至少需要90人，现规定应聘者需连续工人，现规定应聘者需连续工作作5天，试确定聘用方案。天，试确定聘用方案。解解 周一至周日分别聘用X(i)（i1,2，7）个人上班，最少所需人数为R(i)，总人数为Z. 5 , 2 , 121. .min71iiRiXiXZtsXZii课后练习课后练习MODEL:SETS:DAYS/MON.SUN/:R,X;ENDSETSDATA:R=50 50 50 50 80 90 90;ENDDATAMIN=Z;N=SIZE(DAYS);!集合的长度集合的长度;Z=SUM(DAYS:X);FOR(DAYS(I):Z-X(WRAP(I

50、+1,N)-X(WRAP(I+2,N)R(I);!WRAP()相当于求余数，返回相当于求余数，返回1到到N之间的数之间的数;FOR(DAYS:GIN(X);END课后练习课后练习?,1,2:),(),(),(),(),(),(),(:7, 7654321的的年年利利润润最最大大问问如如何何选选择择地地址址使使公公司司元元总总投投资资不不超超过过元元每每年年可可获获利利元元投投资资若若选选个个汉汉口口汉汉阳阳至至少少个个武武昌昌至至多多并并规规定定汉汉商商二二十十一一世世纪纪行行街街步步武武广广司司门门口口亚亚贸贸中中商商个个地地址址有有拟拟议议中中汉汉阳阳建建立立专专卖卖店店汉汉口口某某公公司

51、司拟拟定定在在在在武武昌昌bcbAAAAAAAAiii例例6 选址问题选址问题2.5 0-1规划规划 否否则则选选择择解解, 0, 1:iiAx 71maxiiixcf 7,.,2 , 110112.765432171ixxxxxxxxbxbtsiiii或或2.5 0-1规划规划 例例7 面试顺序问题面试顺序问题有有4名同学到一家公司参加三个名同学到一家公司参加三个阶段的面试，公司要求每个同学都必须首先找公司秘书初试，阶段的面试，公司要求每个同学都必须首先找公司秘书初试，然后到主管部门处复试，最后到经理处参加免试，并且不允然后到主管部门处复试，最后到经理处参加免试，并且不允许插队，由于许插队，由于4名同学的专业背景不同，所以每人在三个阶段名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如表所示，这的面试时间也不同，如表所示，这4名同学约定他们全部面试名同学约定他们全部面试完以后一起离开公司，假定现在时间是早上完以后一起离开公司，假定现在时间是早上8：00，请问他们，请问他们最早何时能离开公司？最早何时能离开公司？ 秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201610同学丁810152.5