数学建模(线性规划).

数学规划模型数学规划模型是在实际问题的数学建模中应用最广泛的模型之一，也是运筹学的一个重要分支。在生产实践中，经常要制定使问题的某一项指标“最优”的方案，这里的最优包括“最大”、“最小”、“最多”、“最少”等。如：如何合理地分配、使用有限的资源（人力、物力及资金等）以获得“最大收益”等诸如此类的问题，就是所谓数学规划问题，数学规划又分为线性规划、非线性规划、整数规划、动态规划等。•线性规划•非线性规划•整数规划•动态规划1.线性规划模型1.1例生产计划问题。某工厂制造甲乙两种产品，每单位产品消耗和获得的利润如表1.1表1.1生产计划问题的数据单位消耗产品原料甲产品/t乙产品/t现有原料总量钢材/t95360电力/(kw.h)45200工作日/个310300单位产品的利润/(万元/t)712试拟订生产计划，使该厂获得利润最大121212121212712max712,..95360,45200,xxzzxxzxxzxxstxxxx解设甲、乙两种产品计划生产量分别为和吨，利润为万元则，我们的任务是求的最大值，且，受到钢材的限制、电力的限制工作日的限制、非负条件的限制等，可得线性规划的数学模型1212310300,0,0xxxx（1.1），121212(1.1)(,)zfxxxxxx式中，目标函数是和的线性函数，而约束条件是和的线性不等式，因此称式(1.1)为线性规划模型。线性规划模型的解法•两个变量的线性规划模型的图解法•单纯形法•数学软件，如Lindo软件、Lingo软件、Matlab等例1.2投资方案的确定某部门要进行投资，现有四个投资项目。项目A：从第一年到第四年的每年年初需要投资，并于次年年末回收本利115﹪；项目B：从第三年年初需要投资，到第五年年末回收本利125%，但规定最大投资额不超过40万元；项目C：第二年初需要投资，到第五年末才能回收本利140%，但规定最大投资额部超过30万元；项目D：五年内每年的年初可买公债，于当年年末归还，并可获得6%的利息。已知该部门现有资金100万元，试为该部门确定投资方案，使得第五年末它拥有的资金本利总额最大？1）模型建立。①决策变量。决策变量为每年年初向四个项目的投资额，设第i(i=1,2,3,4,5)年年初向A,B,C,D(j=1,2,3,4)四个项目的投资额为xij（万元）。②目标函数。设第五年年末拥有的资金本利总额为z，为了方便，将所有可能的投资列于下表1.2年份项目12345投资限额/万元Ax11x21x31x41Bx3240Cx2330Dx14x24x34x44x54413223541.151.251.401.06zxxxx目标函数应该是四项投资在第五年年末回收的本利之和，于是，目标函数为③约束条件a为了获得最大的投资收益，每年年初应将手头的全部资金投出去，因此第一年的投资总额应是100万元，即x11+x14=100b第二年的投资总额应是第一年年底回收的各项投资的本利，即x21+x23+x24=106%x14同理，第三、四、五年的投资额应是上一年年底回收的各项投资本利，即x31+x32+x34=106%x24+115%x11,x41+x44=106%x34+115%x21,x54=106%x44+115%x31.3224132235411142123241431323424114144342154.40,30.max1.151.251.401.06,..1001.06,1.061.15,1.061.15,cxxzxxxxstxxxxxxxxxxxxxxxx由于投资的限制，因此还有由此得投资问题的数学模型为443132231.061.15,40,30,0,1,,5;1,4ijxxxxxij2）模型求解。用Lindo软件求解，求得投资方案的最优解为x11=71.698112万元，x14=28.301888万元，x23=30万元，x32=40万元，x34=42.452831万元，x41=45万元，其余决策变量均为零，最优值z=143.75万元。例1.3货机装运。某货机有三个货舱：前舱、中舱、后舱。三个货舱所能装载的货物的最大重量和体积都要限制，如表1.3所示。并且，为了保持飞机的平衡，三个货舱中实际装载货物的重量必须与其最大容许重量成比例。表1.3三个货舱装载货物的最大容许量和体积前舱中舱后舱重量限制/t10168体积限制/m3680087005300现有四类货物供该货机本次飞行装运，其有关信息如表1.4，最后一列指装运后获得的利润。表1.4四类装运货物的信息质量/t空间/(m3/t)利润(元/t)货物1184803100货物2156503800货物3235803500货物4123902850应如何安排装运，使该货机本次飞行利润最大？1）模型假设。问题中没有对货物装运提出其他要求，我们可做如下假设：①每种货物可以分割到任意小；②每种货物可以在一个或多个货舱中任意分布；③多种货物可以混装，并保证不留空隙。2）模型建立。①决策变量：用xij表示第i种货物装入第j个货舱的重量（吨），货舱j=1,2,3分别表示前舱、中舱、后舱。②目标函数：决策目标是最大化总利润，即目标函数为1112132122233132334142433100()3800()3500()2850().zxxxxxxxxxxxx③约束条件：约束条件包括以下4个方面：111213212223313233414243112131411222324213233343.18,15,23,12;10,16,8;axxxxxxxxxxxxxxxxxxxxxxxx供装载的四种货物的总重量约束，即b.三个货舱的重量限制，即112131411222324213233343112131411222324213233343.4806505803906800,4806505803908700,4806505803905300;.1016.8cxxxxxxxxxxxxdxxxxxxxxxxxx三个货舱的空间限制三个货舱装入重量的平衡约束，即3）模型求解。将以上模型输入Lindo模型，可以得到结果：最优解为x21=10t,x23=5t,x32=12.947t,x33=3t,x42=3.053t,其余变量均为零，最优值z=121515.8t2.非线性规划模型非线性规划问题可以看作是线性规划问题的一种自然推广，亦是数学规划的一个重要组成部分。凡目标函数和约束条件中包含有非线性函数的数学规划问题都称为非线性规划问题。较之线性规划模型而言，非线性规划模型更能真实地反映问题的实质。例2.1设用甲、乙、丙三种有限资源生产A,B,C,D四种产品，产品的资源消耗定额及资源的有限供应量如表2.1所示表2.1产品的消耗定额与资源供应量消耗定额产品资源ABCD资源可供应量甲1232200乙7981300丙3017400假定A,B,C,D四种产品价格随产量的扩大而递减，其需求函数分别为p1=11-0.01x1,p2=12-0.02x2,p3=13-0.03x3,p4=14-0.04x4,试确定四种产品的产量，以便使总收益最大。12341234112233441122334412,,,(,,,)(110.01)(120.02)(130.03)(140.04)(11121ABCDxxxxzxxxxpxpxpxpxxxxxxxxxxx解设四种产品的产量分别为,,和，则问题的目标函数（总收益函数）3422221234314)(0.010.020.030.04)xxxxxx其中，第一项是不变价格下的总收益，第二项是需要扣除的因价格变动造成的收益值，注意到资源的约束，上述问题可表为12342222123412341234134max(11121314)(0.010.020.030.04),..23220079830037400,0,1,2,3,4jzxxxxxxxxstxxxxxxxxxxxxj显然，上述问题是一个非线性规划问题。在实际经济活动中，产量规模对价格的影响常常是一个不开忽略的重要因素：上述模型由于适当地考虑了价格的可变部分对总收益的影响，而相应的线性规划模型，总收益函数只能在假定某不变价格的情况下由产量x1、x2、x3和x4线性确定，故较之线性模型更能真实地反映问题的实质。非线性规划模型求解非线性规划模型的求解具有一定的难度，并且求解非线性规划问题的方法是多种多样的，解某些问题的有效方法，对另外的问题却未必有效。我们可以用一些数学软件来求解。例2.2工程造价问题假定要建造容积为1500m3的长方形仓库，已知每平方米墙壁、屋顶和地面的造价分别为4元、6元、12元，基于美学考虑，要求宽度应为高度的2倍，试建立使造价最省的数学模型。1）模型建立。①决策变量：设仓库的宽、高、长分别为x1,x2,x3(m)②目标函数：墙壁面积为2(x1x2+x2x3)，造价为8(x1x2+x2x3)；屋顶与地面面积为x1x3，造价为18x1x3，则目标函数为z=8(x1x2+x2x3)+18x1x3③约束条件。容积限制x1x2x3-1500=0,比例限制x1-2x2=0，及非负限制x1,x2,x3≥0由此得到数学模型2131312312123min8()18,..15000,20,,,0zxxxxxstxxxxxxxx此为一非线性等式约束规划模型。2）模型求解。用Lingo软件求解。例2.3经营计划问题某公司经营两种设备，假设每种设备的单位售价以及售出单位设备所需的营业时间及该公司在某段时间内的总营业时间见表2.2（表中x1,x2为两种设备的售出数量），建立营业额最大的营业营业计划模型。表2.2经营计划的数据设备ⅠⅡ公司可使用营业时间单位售价/元30450800售出单位设备的营业时间/h0.52+0.25x23整数规划模型在一个数学规划模型中，如果它的某些决策变量或全部变量要求取整数时，就称这个数学规划模型为整数规划模型。整数规划模型可分为整数线性规划模型与整数非线性规划模型。整数规划又分为整数规划、混合整数规划及0-1规划。整数规划模型的一般形式1212min(,,,),..(,,,)0,1,2,,,0,1,2,,,,1,2,,.ninjjfxxxsthxxximxjnxjn为整数1212(1,2,,),,,(1,2,,),,,(1,2,,)ininjfhimxxxfhimxxxxjn当和均是的线性函数时,我们称模型为整数线性规划模型；当和中至少有一个是的非线性函数时，称模型为整数非线性规划模型。若整数规划模型中的决策变量只能取0或1，则称模型为0-1规划.例3.1某航空公司为满足客运量日益增长的需要，欲购置一批新的远程及短程客机。每架客机价格6300万元，中程客机5000万元，短程客机3500万元。该公司现有资金7.5亿元可用于购买飞机。估计年净利润每架远程客机为420万元，中程客机300万元，短程客机230万元。该公司现有熟练驾驶员可用来配备30架新飞机。维修设备足以维修新增加40架新的短程客机，每架中程客机的维修量相当于4/3架短程客机，而每架远程客机的维修量相当于5/3架短程客机。为获取最大利润，该公司应购买各类客机多少架？123123123123123123123max420300230,..63005000350075000,30,5440,33,,0,,,xxxzxxxstxxxxxxxxxxxxxxx解设购买远程、中程、短程客机的数量分别为、和架，问题的数学模型为均为整数。用Lindo软件求解例3.2合理下料问题某钢管零售商从钢管厂家进货，将钢管按照顾客的要求切割后售出，从钢管厂进货时得到的原料钢管都是19m.1）现有一客户