线性规划模型、求解和灵敏度分析.doc

开课学院、实验室：数理学院DS1401 实验时间 ：2011年5月 2日课程名称数学实验实验项目名 称线性规划模型、求解及灵敏度分析实验项目类型验证演示综合设计其他指导教师李东成 绩实验目的1 学习最优化技术和基本原理，了解最优化问题的分类；2 掌握线性规划的建模技巧和求解方法；3 学习灵敏度分析问题的思维方法；4 熟悉MATLAB软件求解线性规划模型的基本命令；5 通过范例学习，熟悉建立线性规划模型的基本要素和求解方法。 通过该实验的学习，使学生掌握最优化技术，认识面对什么样的实际问题，提出假设和建立优化模型，并且使学生学会使用MATLAB软件进行线性规划模型求解的基本命令，并进行灵敏度分析。解决现实生活中的最优化问题是本科生学习阶段中一门重要的课程，因此，本实验对学生的学习尤为重要。基础实验一、实验内容1最优化问题的提出，提出不同的假设可以建立不同的最优化模型；2建立线性规划模型的基本要素和步骤；3使用MATLAB命令对线性规划模型进行计算与灵敏度分析；4利用优化数值解与图形解对最优化特征作定性与定量分析；二、实验过程（一般应包括实验原理或问题分析，算法设计、程序、计算、图表等， 实验结果及分析）基础实验1求解下述线性规划问题min s.t. 用matlab编程如下：c=-5;-4;-6A=1 -1 1;3 2 4;3 2 0b=20;42;30xL=zeros(3,1)x fmin=LINPROG(c,A,b,xL)Bond1=x(1);Bond2=x(2);Bond3=x(3);Returnexpectation=-fmin结果为：x = 0.0000 15.0000 3.0000fmin =-78.0000Returnexpectation =78.0000应用实验2. 两种面包产品的产量配比问题田园食品公司生产的面包很出名。他们生产两种面包：一种是叫“唐师”的白面包，另一种是叫“宋赐”的大黑面包。每个唐师面包的利润是0.05元，宋赐面包是0.08元。两种面包的月生产成本是固定的4000元，不管生产多少面包。该公司的面包生产厂分为两个部：分别是烤制和调配。烤制部有10座大烤炉，每座烤炉的容量是每天出140台，每台可容纳10个唐师面包或5个更大的宋赐面包。可以在一台上同时放两种面包，只需注意宋赐面包所占的空间是唐师面包的两倍。调配部每天可以调配最多8000个唐师面包和5000个宋赐面包。有两个自动调配器分别用于两种面包的调配而不至于发生冲突。田园公司决定找出这两种面包产品的最佳产量配比，即确定两种面包的日产量，使得在公司面包厂的现有生产条件下利润最高。作出假设：TS：为唐师面包的日产量（个/日）SC：为宋赐面包的日产量（个/日）建立模型：根据题目，面包的日产量可以归结为以下的最优化模型:目标函数：fmax=0.05TS+0.08SC-4000/30约束条件：0.1TS+0.2SC 14000 TS 80000 SC 5000用MATLAB编程：c=-0.05;-0.08A=0.1 0.2b=1400xL=0;0xU=8000;5000x,fmin=LINPROG(c,A,b,xL,xU)Bond1=x(1);Bond2=x(2);Fmax=-fmin结果如下：x =8000 3000fmin =-640.0000Fmax =640.0000所以唐师面包的日产量8000个/日，宋赐面包的日产量,5000个/日时，利润最大为640-400/3=506.67元。3. 航空公司的机舱设计及机票销售在五个城市A、B、C、D、E之间，有唯一一家航空公司提供四个航班服务，这四个航班的“出发地目的地”分别为AC、BC、CD、CE，可搭载旅客的最大数量分别为100人、115人、120人、110人，机票的价格分头等舱和经济舱两类。经过市场调查，公司销售部得到了每天旅客的相关信息，见下表。该公司应该在每条航线上分别分配多少张头等舱和经济舱的机票？出发地-目的地头等舱经济舱需求（人）价格（元）需求（人）价格（元）AC311905290AD(经C转机)2224441193AE(经C转机)1026160199BC2517033110BD(经C转机)2026031150BE(经C转机)828041165CD341405980CE1318615103分析：题中以“顾客的起点、终点”将顾客分成5类，现将飞机航线也做相应的分类：AC、AD、AE、CD、CE、BC、CD、CE，依次编号为 相应的头等舱需求记为ai，价格记为 pi；相应的经济舱需求记为bi价格记 qi; 相应的头等舱机票数记为xi，经济舱机票数记为yi。 建模：所以目标函数为：s.t.航班AC上的销售机票总数为3个航线AC、AD、AE的销售机票数之和，不准超过班机容量100，故有航班BC上的销售机票总数为3个航线BC、BD、BE的销售机票数之和，不准超过班机容量115，故有在另外两个航班CD、CE上，有同样的容量限制，故有每条航线上有需求量的限制，故有所以s.t.目标函数为：用matlab编程：c=-190;-244;-261;-140;-186;-170;-260;-280;-90;-193;-199;-80;-103;-110;-150;-165A=1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0;0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1;0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0; 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1b=100;115;120;110xL=zeros(16,1)xU=31;22;10;34;13;25;20;8;52;41;60;59;15;33;31;41x,fmin=LINPROG(c,A,b,xL,xU)fmax=-fmin运行结果如下：x =31.0000 22.0000 10.0000 34.0000 13.0000 25.0000 20.000 8.0000 0.0000 2.0000 35.0000 42.0000 15.0000 33.0000 0.0000 29.0000fmin = -5.3407e+004fmax = 5.3407e+004方案如下：AC、AD、AE、CD、CE、BC、CD、CE上经济舱票数分别为：31 22 10 34 13 25 20 8；AC、AD、AE、CD、CE、BC、CD、CE上豪华舱票数分别为：0 2 35 42 15 33 0 29；最大收入为53407元。4. 运输问题 Toronto 1Detroit 2Chicago 3Buffalo 4New York 5Phila. 6St. louis 7SourceTransshipment PointDestination从Toronto和Detroit两市分别有两批货物途径Chicago和Buffalo最终到达New York、Phila.和St.louis市.之间的路线表述如图所示，其中Toronto和 Detroit 分别有600和500的货物需要运出,New York、Phila. 和St.louis的货物需求分别是450、350和300. 每一段上的运输单价如表1和表2。问：如何进行运输安排使整个的运输费用最少？试建立问题的数学模型并求出最优解。表1 第一段的运输单价ToFromChicagoBuffaloSupplyTorontoDetroit$4$ 5$ 7$ 7600500表2 第二段的运输单价ToFromNew YorkPhila.St.louisChicagoBuffaloDemand$3$ 1450$ 2$ 3350$ 2$ 4300建立模型：Xij为i地到j地运输的货物量（0xij）。s.t.：x13+x14=600x23+x24=500-x13- x23+x35+x36+x37 =0-x14- x24+x45+x46+x47 =0x35+ x45=450x36+ x46=350x37+ x47=300目标函数：Min=4x13+7x14+7 x23+5x24+ 3x35+2x36+x37+ x45+3x46+4x47用matlab编程如下：c=4;7;7;5;3;2;1;1;3;4xL=zeros(10,1)Aeq=1 1 0 0 0 0 0 0 0 0;0 0 1 1 0 0 0 0 0 0;-1 -1 0 0 1 1 1 0 0 0;0 0 -1 -1 0 0 0 1 1 1;0 0 0 0 1 0 0 1 0 0;0 0 0 0 0 1 0 0 1 0;0 0 0 0 0 0 1 0 0 1seq=600;500;0;0;450;350;300x,fmin=LINPROG(c,Aeq,seq,xL)结果如下：x =600.0000 0.0000 0.0000 500.0000 0.0000 300.0000 300.000 450.0000 50.0000 0.0000fmin = 6400运输方案如下：Toronto的600全运到Chicago，Detroit的500全运到Buffalo，Chicago600中的300运到Phila，剩下的运到St.louis，Buffalo中的450运到New York，剩下的运到Phila。运费最少为6400.5. 投资策略某部门现有资金10万元，五年内有以下投资项目可供选择：项目A：从第一年到第四年每年初投资，次年末收回本金且获利15%；项目B：第三年初投资，第五年末收回本金且获利25%，最大投资额为4万元；项目C：第二年初投资，第五年末收回本金且获利40%，最大投资额为3万元；项目D：每年初投资，年末收回本金且获利6%；问如何确定投资策略使第五年末本息总额达最大？ 分析：先考虑只能投资一次的项目C，项目A连续投资两次，其利润为32.25%，项目D连续投资4次其利润为26.25%，明显项目C的利润要高，所以第二年首先选择项目C的3万元。再考虑只能投资一次的项目B，可以由项目A和项目D组合而成，而其利润为21.90%，所以第三年首先投资4万元到项目B。再考虑项目A和项目D，两年为限时，项目A的收益高于项目D。所以第二年至少要30000元的资金回笼，30000/(1+0.06)=28301.8868元第三年要至少有40000元资金回笼，40000/(1+1.15)=34782.6087元1.第一年初投资28301.8868元在项目D上，其余全部投资在项目A上，第一年末资金回笼为30000元。2.第二年初，30000元全部投资在项目C上，第二年末收益为(100000-28301.8868)1.15=82452.8302。3.第三年初投资40000元在项目B上，剩余42452.8302元全部投资在项目A上。4.第四年末收益为42452.8302(1+0.15)=48820.7547元5.第五年初投资4890.7547元在项目D上，第五年年末收益为48820.7547(1+0.06)=51750.0000,300001.40=42000,400001.25=50000，共计143750.0000元。建模：设Xij为第i年向项目j的投资。将以上列出的目标函数和约束条件写在一起，并加上对的非负要求，就得到该问题的优化模型：max A=1.15X41+1.40X23+1.25X32+1.06X54s.t.X11+X14=10-1.06X14+X21+X23+X24=0-1.15X11-1.06X24+X31+X32+X34=0-1.15X21-1.06X34+X41+X44=0-1.15X31-1.06X44+X54=0X324X2330Xij在matlab下用相关函数实现为：c=0;0;0;-1.4;0;0;-1.25;0;-1.15;0;-1.06a=1 1 0 0 0 0 0 0 0 0 00 -1.06 1 1 1 0 0 0 0 0 0;-1.15 0 0 0 -1.06 1 1 1 0 0 0;0 0 -1.15 0 0 0 0 -1.06 1 1 0;0 0 0 0 0 -1.15 0 0 0 -1.06 1;0 0 0 1 0 0 0 0 0 0 0;0 0 0 0 0 0 1 0 0 0 0b=10;0;0;0;0;3;4xL=0 0 0 0 0 0 0 0 0 0 0x,fmin=LINPROG(c,a,b,xL)fmax=-fmin结果如下：x = 5.5477 4.4523 1.7194 3.0000 0.0000 1.0763 4.0000 1.3036 3.3591 0.0000 1.2377fmin = -14.3750fmax=14.3750即：第1年项目A,D分别投资3.8268和6.1732万元；第2年项目A,C分别投资3.5436和3万元；第3年项目A,B分别投资0.4008和4万元)；第4年项目A投资4.0752万元；第5年项目D投资0.4609万元；所以最大利润为14.3750万，盈利43.75%综合实验6. 奶制品加工一奶制品加工厂用牛奶生产A1, A2两种初级奶制品，它们可以直接出售，也可以分别深加工成B1, B2两种高级奶制品再出售。按目前技术每桶牛奶可加工成2公斤A1和3公斤A2,每桶牛奶的买入价为10元，加工费为 5元，加工时间为15小时。每公斤A1可深加工成0.8公斤B1，加工费为4元，加工时间为12小时；每公斤A2可深加工成0.7公斤B2，加工费为3元，加工时间为10小时；初级奶制品A1, A2的售价分别为每公斤10元和9元，高级奶制品B1, B2的售价分别为每公斤30元和20元，工厂现有的加工能力每周总共2000小时，根据市场状况，高级奶制品的需求量占全部奶制品需求量的20%至40%。试在供需平衡条件下为该厂制订（一周的）生产计划，使利润最大，并进一步讨论如下问题：1）拨一笔资金用于技术革新，据估计可实现下列革新中的某一项：总加工能力提高10%，各项加工费用均减少10%。初级奶制品A1，A2的产量提高10%；高级奶制品B1，B2的产量提高10%。问应将资金用于哪一项革新，这笔资金的上限（对于一周而言）应为多少？2）该厂的技术人员又提出一项技术革新，将原来的每桶牛奶可加工成2公斤A1和3公斤A2，变为每桶牛奶可加工成4公斤A1或者6公斤A2。设原题目给的其它条件都不变，问应否采用这项革新，若采用，生产计划如何。已知条件：1、 A1， A2，B1，B2的售价分别为10， 9， 30， 20元/公斤。2、 牛奶的买入和加工的总费用为15元/桶3、 A1，A2的深加工费用分别为4， 3元/公斤。4、 每桶牛奶可加工成2公斤A1和3公斤A2，每公斤A1可深加工成0.8公斤B1，每公斤A2可深加工成0.7公斤B2。5、 每桶牛奶的加工时间为15小时，每公斤A1，A2的深加工时间分别为12， 10小时，工厂的总加工能力为t=2000小时。6、 牛奶必须购买整数桶。变量设定：1、 设A1， A2，B1，B2一周的销售量为x1，x2，x3，x4桶；2、 设A1，A2一周的生产量为x5，x6桶；3、 A1，A2深加工的数量为x7，x8桶；4、 购买的牛奶数量x9桶 建立模型：是用matlab编程解答可得：购买68.3桶牛奶，A1和A2的总产量分别为136.6公斤和204.9公斤，其中55.3公斤的A1和全部的A2用于销售，余下的81.3公斤A1深加工得到65.0公斤的B1。所得收益为2998.4元。技术革新项目及最大利润的情况：(1)总加工能力提高10%，即t=2200小时。最大利润为329