2010年东大暑期建模培训课件优化方法7月30日

1、优化问题的建模方法优化专题一线性规划模型二非线性规划模型三动态规划生产计划问题线性规划模型 2x1 + x2 8 s.t . x1 3 x2 4 x1，x2 0 max f= 5x1 +2x2 求最大利润三种材料量的限制生产量非负线性规划模型运输问题线性规划模型解：设A1,A2调运到三个粮站的大米分别为x1，x2， x3， x4， x5， x6吨。题设量可总到下表：线性规划模型结合存量限制和需量限制得数学模型：线性规划模型 m个产地A1,Am联合供应n个销地B1,Bn,各产地至各销地单位运价(单位:元/吨)为cij，问如何调运使总运费最少?一般运输问题总运价产量限制需量限制运量非负线性规划模型

2、假设产销平衡: 在很多实际问题中,解题思想和运输问题同出一辙,也就是说我们可以用运输模型解决其他问题.线性规划模型 设有n件工作B1, B2, 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.余料最少下料

3、问题线性规划模型原料截成所需长度的根数下料方法所需根长2.9m211100002.1m021032101.5m10130234剩余料头0.10.30.901.10.20.81.4线性规划模型不同方法截得每种根长的总数至少100例3,4中的此例的变量xi只取正整数,故建立的模型也称整数规划.0-1规划是整数规划的特殊情形.线性规划模型 某公司生产某产品,最大生产能力为100单位,每单位存储费2元,预定的销售量与单位成本如下:月份单位成本(元) 销售量1234 70 60 72 70 80 120 76 60求一生产计划,使 1)满足需求; 2)不超过生产能力;3)成本(生产成本与存储费之和)最低

4、.阶段生产问题线性规划模型 解:假定1月初无库存,4月底买完,当月生产的不库存,库存量无限制.第j+1个月的库存量第j+1个月的库存费共3个月的库存费到本月总生产量大于等于销售量4个月总生产量等于总销售量4个月总生产成本线性规划模型线性规划模型月份单位成本(元) 销售量1234 70 60 72 70 80 120 76 60线性规划模型76827676-80-7472-747270生产月100100100100产量6041207060销量4321321需求月费用cij线性规划模型本题3个模型为整数规划模型.线性规划模型线性规划模型特点决策变量：向量(x1 xn)T ,决策人要考虑和控制的因素

5、非负；约束条件：线性等式或不等式；目标函数：Z=(x1 xn) 线性式，求Z极大或极小；线性规划模型一般形式目标函数约束条件线性规划模型矩阵形式线性规划模型满足约束条件的变量的值称为可行解，可行解的集合称为可行域。使目标函数达到最大（小）值的可行解称为最优解，相应的目标函数的值称为最优值。线性规划模型线性规划问题的性质:比例性 每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比.可加性 每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关.连续性 每个决策变量的取值都是连续的.线性规划模型应 用市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划)生产计划制

6、定(合理下料，配料，“生产计划、库存、劳力综合”)库存管理(合理物资库存量，停车场大小，设备容量)运输问题财政、会计(预算，贷款，成本分析，投资，证券管理)人事(人员分配，人才评价，工资和奖金的确定)设备管理(维修计划，设备更新)城市管理(供水，污水管理，服务系统设计、运用)线性规划模型线性规划问题的基本理论用图解法求解线性规划问题是一簇斜率为-5/2的平行直线族斜率为-2C/2为直线与y轴的交点x10 x28443x240 x1834如图所示: 显然直线向右上移动时，与y轴交点越高，从而c/2越大，使得目标函数值c 越大。线性规划问题的基本理论从上述几何直观可看出：线性规划问题的任意两个可行

7、解联线上的点都是可行解；线性规划问题的任意两个最优解联线上的点都是最优解；线性规划问题的最优值若存在，则一定在某个顶点达到。线性规划问题的基本理论任何一个线性规划问题都可以化为标准形式，我们的求解方法都是针对标准形式的。线性规划问题的基本理论标准形式:如果给定的LP问题是极大化问题,即可化为极小化问题约束条件不变,其最优解是一致的,但目标函数值的符号相反.则:结论:如果问题是求目标函数的最大值,则化为求 f 的最小值;1.关于目标函数线性规划问题的基本理论2.关于约束条件(1) 如果给定的LP有约束不等式线性规划问题的基本理论注意:新引入的变量在目标函数和约束条件中的系数均为0.(2) 如果给

8、定的LP有约束不等式线性规划问题的基本理论3.关于变量 在标准形式中,所有的变量都有非负限制,如果某些变量没有非负限制,则称这些变量为自由的.两种处理办法:线性规划问题的基本理论线性规划问题的基本理论线性规划问题的基本理论相应的典式如下:最优值为5.非基可行解是最优解，线性规划问题的基本理论 1 2 3 4 5 6 7 8 96 5 4 3 2 1（2.25，3.75） 1 2 3 4 5 6 7 8 96 5 4 3 2 1分枝定界法线性规划问题的基本理论隐枚举法过滤条件检验可行目标值可行检验过滤检验(0,0,0) 0(0,0,1) 55(0,1,0) - 2(0,1,1) 3(1,0,0)

9、 3(1,0,1) 88（最优）(1,1,0) 1(1,1,1) 6线性规划问题的基本理论练习 某服务部门一周中每天需要不同数目的雇员：周一到周四每天至少需要50人，周五至少需要80人，周六和周日至少需要90人现规定应聘者需连续工作5天，试确定应聘方案，即周一到周日每天聘用多少人，使在满足需要的条件下聘用总人数最少 线性模型题目1 生产计划问题某工厂计划安排生产，两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及A,B两种原材料的消耗，现有原材料和设备台时的定额如表所示，问：）怎么安排生产使得工厂获利最大？）产品的单位利润降低到1.8万元，要不要改变生产计划，如果降低到1万元呢？）产

10、品的单位利润增大到5万元，要不要改变生产计划？）如果产品，的单位利润同时降低了1万元，要不要改变生产计划？ 产品产品最大资源量设备128台时原材料A4016kg原材料B0412kg单位产品利润23 线性模型建立 线性模型求解程序编写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

11、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万元 。 线性模型敏感性理论1目标函数的系数变化的敏感性分析如果目标函数的系数发生变化，将会影响目标函数 f 斜率的变化，但是只要f 的斜率小于等于-1/2（也就是直线l夹在l1与l2之间时），最优解都在(4,2)上取到，最优解不变，从而生产计划不会变. 线性模型敏感性分析1要使用敏感性分析必须要在这里选择Prices & Ra

12、nges然后保存退出路径：LINGOOptionsGeneral Solver(通用求解程序)选项卡 线性模型敏感性分析1要调出敏感性分析的结果，必须先求解后再在程序窗口下点击LINGORange， 线性模型敏感性分析1Ranges 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.

13、000000 Righthand Side Ranges Row Current Allowable Allowable 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”，可得新的计划为安排是生产产品2单位，产品3单

14、位，最大盈利为11万元.对问题3，要改变生产计划，更改程序得新计划为生产产品2单位，产品3单位，最大盈利为19万元.对问题4，因为两个系数同时改变了，所以只有更改程序的数据，重新运行得：不改变生产计划，但是最大利润降低到8万元. 线性模型敏感性理论2 线性模型影子价格理论把y1,y2,y3作为三种原料的定价，定价的目标是在比生产产品获得更多利润的前提下的最小利润. 在最优情况下，y的值就是资源的影子价格，影子价格有意义是有范围的。影子价格经济含义是：在资源得到最优配置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量 线性模型综合讨论Ranges in which the bas

15、is 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.00000 16.00000 8

16、.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 线性模型题目21桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利1

17、6元/公斤 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划，使每天获利最大 35元可买到1桶牛奶，买吗？ 可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到 30元/公斤，应否改变生产计划？ 每天：加工奶制品的生产计划 线性模型建立x1桶牛奶生产A1 x2桶牛奶生产A2 获利 243x1 获利 164 x2 原料供应 劳动时间 加工能力 决策变量 目标函数 每天获利约束条件非负约束 线性规划模型(LP) 线性模型求解Max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100; OBJECTIVE FUNCTION VALUE 1)

18、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= 220桶牛奶生产A1, 30桶生产A2，利润3360元。 线性模型影子价格 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1

19、 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 35元可买到1桶牛奶，要买吗？35 0，初始可行点xk,初始步长k0,在xk线性化得线性规划问题：非线性规划有约束问题 求出此线性规划问题得最优解xk1，检验是否为原问题的的可行解，若是转，否则缩短步长转；判断精度。则取最优解x*=xk+1,停，否则令k=k+1转。非线性规划有约束问题（2）罚函数法转化为无约束最优化问

20、题：M为足够大的正数。称为罚因子。算法分析：设可行域为S，构造函数：非线性规划有约束问题 求无约束问题得最优解为X(M),直观看出，只有当X(M) S才可能真正取得极小值，若就加大罚因子M，使X(M) 向S逼近，当M时，点列非线性规划有约束问题计算步骤：（第k次迭代）非线性规划有约束问题 露天矿里铲位已分成矿石和岩石: 平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间5分钟。 卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。 矿石卸点需要的铁含量要求都为29

21、.5%1%(品位限制），搭配量在一个班次（8小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为154吨，平均时速28km,平均卸车时间为3分钟。问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次 ? 露天矿生产的车辆安排(CUMCM-2003B) 露天矿生产的车辆安排(CUMCM-2003B)距离铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏5.265.194.214.002.952.742.461.900.641.27倒装1.900.991.901.131.272.251.482.043.093.51岩场5.895.615.614

22、.563.513.652.462.461.060.57岩石漏0.641.761.271.832.742.604.213.725.056.10倒装4.423.863.723.162.252.810.781.621.270.50铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石量095105100105110125105130135125岩石量125110135105115135105115135125铁含量30%28%29%32%31%33%32%31%33%31% 露天矿生产的车辆安排(CUMCM-2003B)与典型的运输问题明显有以下不同：这是运输矿石与岩石两种物资的问题；属

23、于产量大于销量的不平衡运输问题；为了完成品位约束，矿石要搭配运输；产地、销地均有单位时间的流量限制；运输车辆只有一种，每次满载运输，154吨/车次；铲位数多于铲车数意味着要最优的选择不多于7个产地作为最后结果中的产地；最后求出各条路线上的派出车辆数及安排。近似处理：先求出产位、卸点每条线路上的运输量(MIP模型)然后求出各条路线上的派出车辆数及安排 问题分析卡车在一个班次中不应发生等待或熄火后再启动的情况；在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；空载与重载的速度都是28km/h，耗油相差很大；卡车可提前退出系统，等等。

24、 模型假设(近似)xij ：从i铲位到j号卸点的石料运量 （车） 单位： 辆；cij ：从i号铲位到j号卸点的距离 公里；Tij :从i号铲位到j号卸点路线上运行一个周期平均时间 分；Aij ：从i号铲位到j号卸点最多能同时运行的卡车数 辆；Bij ：从i号铲位到j号卸点路线上一辆车最多可运行的次数 次；pi：i号铲位的矿石铁含量 p=(30,28,29,32,31,33,32,31,33,31) %qj : j号卸点任务需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 吨cki ：i号铲位的铁矿石储量 万吨cyi ：i号铲位的岩石储量 万吨fi :描述第i号铲位是否使用的0-

25、1变量，取1为使用；0为关闭 符号说明（4）铲位储量约束（1）道路能力(卡车数)约束（2）电铲能力约束（3）卸点能力约束 模型建立优化模型xij为非负整数fi 为0-1整数（5）产量任务约束（8）整数约束 （7）电铲数量约束（6）铁含量约束 模型建立 程序编写model:title CUMCM-2003B-01;sets:cai / 1.10 /:crate,cnum,cy,ck,flag;xie / 1 . 5 /:xsubject,xnum;link( xie,cai ):distance,lsubject,number,che,b;endsetsdata:crate=30 28 29 3

26、2 31 33 32 31 33 31;xsubject= 1.2 1.3 1.3 1.9 1.3 ;distance= 5.26 5.19 4.21 4.00 2.95 2.74 2.46 1.90 0.64 1.27 1.90 0.99 1.90 1.13 1.27 2.25 1.48 2.04 3.09 3.51 5.89 5.61 5.61 4.56 3.51 3.65 2.46 2.46 1.06 0.57 0.64 1.76 1.27 1.83 2.74 2.60 4.21 3.72 5.05 6.10 4.42 3.86 3.72 3.16 2.25 2.81 0.78 1.62

27、 1.27 0.50;cy = 1.25 1.10 1.35 1.05 1.15 1.35 1.05 1.15 1.35 1.25;ck = 0.95 1.05 1.00 1.05 1.10 1.25 1.05 1.30 1.35 1.25; enddata 程序编写!目标函数;min=sum( cai (i): sum ( xie (j): number (j,i)*154*distance (j,i);!卡车每一条路线上最多可以运行的次数;for (link (i,j):b(i,j)=floor(8*60-(floor(distance(i,j)/28*60*2+3+5)/5)-1)*5)

28、/(distance(i,j)/28*60*2+3+5);!每一条路线上的最大总车次的计算;for( link (i,j):lsubject(i,j)=(floor(distance(i,j)/28*60*2+3+5)/5)*b(i,j);!计算各个铲位的总产量;for (cai(j): cnum(j)=sum(xie(i):number(i,j);!计算各个卸点的总产量;for (xie(i): xnum(i)=sum(cai(j):number(i,j); 程序编写!道路能力约束;for (link (i,j): number(i,j)=lsubject(i,j);!电铲能力约束;for

29、(cai (j) : cnum(j) = flag(j)*8*60/5 );!电铲数量约束 - added by Xie Jinxing, 2003-09-07;sum(cai(j): flag(j) ) =7; !卸点能力约束;for (xie (i): xnum (i)=8*20);!铲位产量约束;for (cai (i): number(1,i)+number(2,i)+number(5,i)=ck(i)*10000/154);for (cai (i): number(3,i)+number(4,i)= xsubject (i)*10000/154); 程序编写!铁含量约束;sum(cai (j): number(1,j)*(crate(j)-30.5) )=0;sum(cai (j): number(2,j)*(crate(j)-30.5) )=0;sum(cai (j): number(5,j)*(crate(j)-30.5) )=0;sum(c