数学建模—线性规划

1、2022-5-31数学建模2022-5-31第三讲 线性规划应用实例分析线性规划问题的求解方法实验准备 如果生产某一类型汽车，则至少要生产如果生产某一类型汽车，则至少要生产8080辆，辆， 那么那么最优的生产计划应作何改变？最优的生产计划应作何改变？例例1 汽车厂生产计划汽车厂生产计划 汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量如下表。劳动时间的需求，利润及工厂每月的现有量如下表。 小型小型 中型中型 大型大型 现有现有量量钢材（吨）钢材（吨） 1.5 3 5 600劳动时间（小时）劳动时间（小时）

2、 280 250 400 60000利润（万元）利润（万元） 2 3 4 制订月生产计划，使工厂的利润最大。制订月生产计划，使工厂的利润最大。LP实例一 汽车生产设每月生产小、中、大型设每月生产小、中、大型汽车的数量分别为汽车的数量分别为x1, x2, x3，工厂的月利润为工厂的月利润为z z。321432xxxzMax6005351.321xxx.ts60000400250280321xxx0,321xxx汽车厂生产计划汽车厂生产计划 模型建立模型建立 小型小型 中型中型 大型大型 现有量现有量钢材钢材 1.5 3 5 600时间时间 280 250 400 60000利润利润 2 3 4

3、线性线性规划规划模型模型(LP)模型求解模型求解 3） 模型中增加条件：模型中增加条件：x1, x2, x3 均为整数，重新求解。均为整数，重新求解。 %汽车生产计划：线性规划模型%format short c=-2;-3;-4;a=1.5,3,5;280,250,400;b=600;60000;x =linprog(c,a,b,zeros(3,1)FVAL=(-c*X)结果为小数，结果为小数，怎么办？怎么办？1）舍去小数：取）舍去小数：取x1=64，x2=167，算出目标函数值，算出目标函数值z=629，与与LP最优值最优值632.2581相差不大。相差不大。2）试探：如取）试探：如取x1=

4、65，x2=167；x1=64，x2=168等，计算函等，计算函数值数值z，通过比较可能得到更优的解。，通过比较可能得到更优的解。 但必须检验它们是否满足约束条件。为什么？但必须检验它们是否满足约束条件。为什么？汽车厂生产计划汽车厂生产计划 例例2 投资方案确定投资方案确定LP实例二 投资问题某企业要进行投资，现有四个投资项目。项目A：从第一年到第四年的每年年初需要投资，并于次年年末回收本利115；项目B：从第三年年初需要投资，到第五年年末回收本利125%，但规定最大投资额不超过40万元；项目C：第二年初需要投资，到第五年末才能回收本利140%，但规定最大投资额不超过30万元；项目D：五年内每

5、年的年初可买公债，于当年年末归还，并可获得6%的利息。已知该部门现有资金100万元，试为该企业确定投资方案，使得第五年末它拥有的资金本利总额最大？模型建立模型建立LP实例二 投资问题u决策变量。决策变量为每年年初向四个项目的投资额，设第i(i=1,2,3,4,5)年年初向A,B,C,D(j=1,2,3,4)四个项目的投资额为xij（万元）。u目标函数。设第五年年末拥有的资金本利总额为z。项目年份12345投资限额/万元Ax11x21x31x41Bx3240Cx2330Dx14x24x34x44x54所有可能的投资项目表LP实例二 投资问题投资方案要使得第五年末资金本利总额最大，目标函数应该是四

6、项投资在第五年年末的本利之和，于是 约束条件模型建立模型建立54233241061401251151 x.x.x.x.zMax1001411xx（1）为了获得最大的投资收益，每年年初应将手头的全部资金投出去，因此第一年的投资总额应是100万元，即（2）b第二年的投资总额应是第一年年底回收的各项投资的本利，.xxxLP实例二 投资问题模型建立模型建立（3）同理，第三、四、五每年的投资额应是上一年年底回收的各项投资的本利，即第三年：第四年：第五年：314454213444411124343231151061151061151061x.x.xx.x.xxx.x.xxx项目年

7、份12345投资限额/万元Ax11x21x31x41Bx3240Cx2330Dx14x24x34x44x54LP实例二 投资问题（4）由于投资的限额，因此还有模型建立模型建立30,402332xx数学模型数学模型4,1;5 ,1,0jixij314454213444411124343231151061151061151061x.x.xx.x.xxx.x.xx.xxx1001411xx54233241061401251151 x.x.x.x.zMaxs . t .LP实例二 投资问题（3）用matlab的linprog函数求解，可得模型求解%线性规划：投资问题%c=ze

8、ros(3,1);-1.4;0;0;-1.25;0;-1.15;0;-1.06;a=zeros(6,1),1,zeros(4,1);zeros(3,1),1,zeros(7,1);b=40;30;aeq_one=1,1,zeros(9,1);aeq_two=0,-1.06,1,1,1,zeros(6,1);aeq_three=-1.15,zeros(3,1),-1.06,1,1,1,zeros(3,1);aeq_four=0,0,-1.15,zeros(4,1),-1.06,1,1,0;aeq_five=zeros(5,1),-1.15,zeros(3,1),-1.06,1;Aeq=aeq_o

9、ne;aeq_two;aeq_three;aeq_four;aeq_five;beq=100;0;0;0;0;x=linprog(c,a,b,Aeq,beq,zeros(11,1)vlaue=(-c*x)LP实例二 投资问题模型分析 投资方案表第五年末资金本利总额最大为143.75万元。问题：有没有其它的投资组合，在第五年末获得更大或者相同的资本总额？项目年份12345Ax11=62.2643x21=9.9999x31=17.0592x41=26.9173Bx32=40Cx23=30Dx14=37.7357x24=0 x34=14.5448x44=0 x54=19.6181x11=71.698

10、112万元，x14=28.301888万元，x23=30万元，x32=40万元，x34=42.452831万元，x41=45万元，例例3 飞机运输安排飞机运输安排LP实例三 运输问题某货机有三个货舱：前舱、中舱、后舱。三个货舱所能装载的货物的最大重量和体积都要限制，如下表所示。并且，为了保持飞机的平衡，三个货舱中实际装载货物的重量必须与其最大允许的重量成比例。前舱中舱后舱重量限制/t10168体积限制/m3680087005300三个货舱装载货物的最大容许量和体积例例3 3 飞机运输安排飞机运输安排LP实例三 运输问题现有四类货物供该货机本次飞行装运，其有关信息如下表所示，最后一列表示装运该货

11、物后获得的利润。质量/t空间/(m3/t)利润(元/t)货物1184803100货物2156503800货物3235803500货物4123902850四类装运货物的信息问题：应如何安排装运，使该货机本次飞行利润最大？2022-5-31LP实例三 运输问题1.模型假设题目中没有对货物形状提出要求，我们可做如下假设：每种货物可以分割到任意小；每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙。决策变量：用xij表示第i种货物装入第j个货舱的重量（吨），货舱j=1,2,3分别表示前舱、中舱、后舱。目标函数：决策目标是最大化总利润，即目标函数为2.模型建立11121321222

12、33132334142433100()3800()3500()2850().zxxxxxxxxxxxx 2022-5-31LP实例三 运输问题约束条件：约束条件包括以下4个方面：2.模型建立2022-5-31LP实例三 运输问题约束条件：约束条件包括以下4个方面：2.模型建立2022-5-31LP实例三 运输问题将以上模型参数输入matlab中 模型，可以得到结果。参考结果：最优解为x21=10t, x23=5t, x32=12.947t, x33=3t, x42=3.053t, 其余变量均为零，最优值z=121515.8t。建模过程中假设的严谨程度？如果货物运输过程中有风险？如何加入风险控制

13、？模型的适用范围？是否达到建模的目的？思考其它类似的问题:劳动力的安排问题；原料比例分配问题等3.模型求解4.模型分析2022-5-31线性规划问题线性规划（LP）数学规划问题：有限的人力、物力、财力等资源做最优决策当得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时的数学模型。LP问题的数学建模过程（1）列出约束条件及目标函数决策变量106目标函数（线性函数）约束条件104（2）约束条件所表达的可行域单纯形法（改进单纯形法、对偶单纯形法、多项式时间算法）（3）在可行域内求目标函数的最优解及最优值2022-5-31线性规划问题求解方法单纯形法LP问题的可行域是n维向量空间Rn的多面凸集，其最优解如果存在，必在该凸集的某顶点处达到。凸集：任意两点的连线都在集合S内，称S为凸集欧式空间：直观上，凸集就是凸的。一维：直线，线段，射线；二维：圆，椭圆，扇面；三维：球可行解：满足所有约束条件的解可行域：所有可行解的集合基本可行解：顶点所对应的可行解最优解：是目标函数达到最大或最小值的可行解存在一个：某个顶点所对应的基本可行解存在无穷多个不存在：约束条件不阻止目标函数值的（负方向）无限增大2022-5-31线性规划问题求解方法单纯形法最优解如存在，一定在可行域的顶点处达到基本可行解个数有限，可以在基本可行解中寻找最优解需要解决的问题？如何找到顶