8 数学规划方法建模(2)

第六章数学规划方法建模,第六章数学规划方法建模,6.1线性规划模型,6.2非线性规划模型,6.3整数规划模型,6.2非线性规划模型,凡目标函数和约束条件中包含有非线性函数的数学规划问题都称为非线性规划问题。它主要分为无约束非线性规划与约束非线性规划。,6.2.1非线性规划模型简介,1.无约束的非线性规划模型（以最小目标为例）,若记,则其模型的矩阵形式为,2.约束非线性规划模型,无约束的非线性规划模型与约束非线性规划模型统称为非线性规划模型，本节主要介绍约束线性规划模型，简记成NLP。,6.2.1非线性规划模型简介,设用甲、乙、丙三种有限资源生产A,B,C,D四种产品、产品的资源消耗定额及资源的有限供应量如表6.8所示。,表6.8产品的消耗定额与资源供应量,假定A、B、C、D四种产品价格随产量的扩大而递减，其需求函数分别为,试确定四种产品的产量，以便使总受益最大。,例6.10,6.2.1非线性规划模型简介,设A,B,C,D四种产品的产量分别为,例6.10的求解,则问题的目标函数（总收益函数）,6.2.1非线性规划模型简介,注意到资源约束，上述问题可表为,在实际经济活动中，产量规模对价格的影响常常是一个不可忽略的重要因素：上述模型由于适当地考虑了价格的可变部分对总收益的影响，而相应的线性规划模型，总收益函数只能在假定某不变价格的情况下由产量线性确定，故较之线性模型更能真实地反映问题的实质。,非线性规划问题,6.2.1非线性规划模型简介,例6.10的求解,6.2.2非线性规划模型的求解,非线性规划模型的求解具有一定的难度，并且求解非线性规划问题的方法是多种多样的，解某些问题有效的方法，对另外的问题却未必有效。,一般来说，求解非线性规划的全局最优解是困难的，通常所得到的是局部最优解。,在此介绍用LINGO软件来求解非线性规划模型。,还有,求解非线性规划问题的迭代常常是无限的，即在迭代中将产生一个无穷点列，换言之，所得到的结果一般是满足一定精度的近似解。,Model:max=11*x1+12*x2+13*x3+14*x4-x5;x5=0.01*(x1*x1+2*x2*x2+3*x3*x3+4*x4*x4);x1+2*x2+3*x3+2*x4200;7*x1+9*x2+8*x3+x4300;3*x1+x3+7*x4400;end,6.2.2非线性规划模型的求解,例6.11求解例6.10中的非线性规划模型,用LINGO软件求解，打开LINGO执行文件，编程如下：,程序以“Model：”开始,每行最后加“；”,最后以“end”结束,非负约束可以缺省,式子中可以有括号，右端可有数学符号。,解：,乘号“*”不能省略,为了编制程序的方便，我们引入了中间变量,Objectivevalue:1003.010VariableValueReducedCostX10.0000001.713858X26.9006080.4349500E-07X323.004760.000000X453.856460.000000X5132.84970.000000,最优解,是中间变量),6.2.2非线性规划模型的求解,例6.11求解例6.10中的非线性规划模型,选择菜单“Solve”进行求解，得到输出：,最优值,6.2.2非线性规划模型的实例,例6.12工程造价问题,试建立使造价最省的数学模型。,假定要建造容积为1500m的长方形仓库，已知每平方米墙壁、屋顶和地面的造价分别为4元，6元，12元，基于美学考虑，要求宽度应为高度的2倍。,墙壁面积为,造价为,屋顶与地面面积为,造价为,则目标函数为,6.2.2非线性规划模型的实例,例6.12工程造价问题,1.模型建立,2）目标函数。,容积限制,比例限制,非负限制,由此得到数学模型为,非线性等式约束规划模型,用LINGO软件求解，得到仓库的设计方案为：,最小造价为,例6.12工程造价问题,3）约束条件,2.模型求解,表6.9经营计划的数据,某公司经营两种设备，假设每种设备的单位售价以及售出单位设备所需的营业时间及该公司在某段时间内的总营业时间均见表6.9（表中为两种设备的售出数量）,建立营业额最大的营业计划模型。,6.2.2非线性规划模型的实例,例6.13经营计划问题,两种设备的售出数量为待确定的决策变量,3）约束条件公司可使用营业时间的限制,非负限制,例6.13经营计划问题,模型建立与求解,数学模型,1）决策变量,2）目标函数即为最大营业额,设z为总营业额,则目标函数为,设两杆平面桁架如图6.4所示，元件是在A点铰支的钢管。在A点,结构受到垂直负荷载2P。设已选定管壁厚度为h，跨度为2b。试选择钢管的平均直径D桁架高度H，使杆件既不屈服又不失平稳，而且桁架的总重量最轻。,例6.14两杆平面桁架的优化设计,6.2.2非线性规划模型的实例,图6.4两杆平面桁架结构图,设桁架的总重量为W,其中，为钢的容重。,例6.14两杆平面桁架的优化设计,例6.14的分析与建模,桁架的总重量最轻,建模的目的,要不屈服保持平衡,模型的决策变量,钢管的平均直径D,桁架高度H,目标函数,由于制造上的原因，D与H应有最大值及最小值的限制，即,此处，,圆管杆件中的压应力不超过压杆稳定的临界应力，即,其中，E为材料的弹性模量。,例6.14两杆平面桁架的优化设计,例6.14的分析与建模,圆管杆件中的压应力应不超过材料的屈服应力,即,两杆平面桁架优化设计问题的模型为：,例6.14两杆平面桁架的优化设计,例6.14的分析与建模,6.3整数规划模型,在一个数学规划模型中，如果它的某些决策变量或全部变量要求取整数时，就称这个数学规划模型为整数规划模型。,整数规划模型,整数线性规划模型,整数非线性规划模型,整数规划,混合整数规划,0-1规划,整数规划模型,整数规划简记成IP（integerprogramming）,6.3.1整数规划模型,整数规划模型的一般形式,的线性函数,整数线性规划模型,若整数规划模型中的决策变量只能取0或1,整数非线性规划模型,0-1规划,某航空公司为满足客运量日益增长的需要，欲购置一批新的远程、中程及短程客机。每架远程客机价格6700万元，中程客机5000万元，短程客机3500万元。该公司现有资金7.5亿元可用于购买飞机。估计年净利润每架远程客机为420万元，中程客机300万元，短程客机230万元。该公司现有熟练驾驶员可用来配备30架新飞机。维修设备足以维修新增加40架新的短程客机，每架中程客机的维修量相当于4/3架短程客机，而每架远程客机的维修量相当于5/3架短程客机。,例6.15,6.3.1整数规划模型,设购买远程、中程、短程客机的数量分别为架，问题的数学模型为：,例6.15的模型建立,6.3.1整数规划模型,整数线性规划模型,6.3.2整数规划模型的求解,LINDO与LINGO软件来求解整数规划模型,实际问题中的整数规划模型的求解,可先略去整数约束的条件,利用线性规划或非线性规划的方法求解,然后对其最优解进行取整处理,简单,可利用穷举法,先根据约束条件确定所有的可行解,后将所有可行解代入目标函数，比较其值，求出最优解,分枝定界算法割平面法,实际上，用这种方法得到的解未必是原整数规划模型的最优解。因此，该种方法是不足取的，但可借鉴这种思想。事实上，求解整数规划的松弛法就借鉴了这种思想。,max420 x1+320 x2+230 x3st2)6300 x1+5000 x2+3500 x3750003)x1+x2+x3304)5x1+4x2+3x3120endgin3,例6.16求解例6.15中的整数规划模型,将例6.15中的模型输入LINDO如下：,LINDO中不能出现分数(小数可以)，语句4)是将对应的约束条件恒等变形得到的。,“3个变量均为整数”的说明语句,选择菜单“Solve”进行求解,得最优解,得最优值,例6.17汽车厂生产计划,小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）234,6.3.3整数规划模型实例,一汽车厂生产小、中、大三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润以及每月工厂钢材、劳动时间的现有量如表6.10所示。,试制订月生产计划，使工厂的利润最大。,进一步讨论：由于各种条件限制,如果生产某一类型汽车,则至少要生产80辆，那么最优的生产计划应做何改变。,设每月生产小、中、大型汽车的数量分别为x1,x2,x3,模型建立,线性规划模型(LP),例6.17汽车厂生产计划,模型求解,3）模型中增加条件：x1,x2,x3均为整数，重新求解。,OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOSTX164.5161290.000000X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.0000000.003226,结果为小数，怎么办？,1）舍去小数:取x1=64，x2=167,算出目标函数值z=629,与LP最优值632.2581相差不大。,2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解。,但必须检验它们是否满足约束条件。为什么？,例6.17汽车厂生产计划,LINDO直接求解,“gin3”表示“前3个变量为整数”，等价于：ginx1ginx2ginx3,IP的最优解x1=64，x2=168，x3=0，最优值z=632,max2x1+3x2+4x3st1.5x1+3x2+5x30;gin(x1);gin(x2);gin(x3);end,模型求解,用LINGO软件求解,例6.17汽车厂生产计划,Objectivevalue:610.0000VariableValueReducedCostX180.00000-2.000000X2150.0000-3.000000X30.0000000.000000,最优解同前,模型求解,结果输出,事实上，用LINGO软件求解非线性规划问题往往得到是局部最优解，其结果常依赖初值的选择，一般地仅当初值非常接近全局最优解时，才能得到正确的结果，这一点同学们要引起注意.,例6.17汽车厂生产计划,如选用Ai，设备投资估计为bi元，每年可获利润估计为ci元，问在投资总额不得超过b元的条件下，怎样选址可使公司年利润最大？假设投资总额b为1000万元，设备投资估计bi与每项投资每年获利ci列于表6.11，试求最优选址方案。,某公司拟在市东、西、南三区建立门市部，假设三个区共有7个位置点Ai选择，且规定：东区只能在A1，A2，A3中至多选两个点；西区只能在A4，A5中两个点中至少选一个点；南区只能在A6，A7中至少选一个点。,6.3.3整数规划模型实例,例6.18选址问题,1）决策变量。决策变量是确定是否选择Ai点,设,2）目标函数。如何选址使年利润最大,用z表示利润,则目标函数为,3）约束条件。xi应满足选址限制及投资总额不超过b元的限制,例6.18选址问题,1.模型建立,建立数学模型为,例6.18选址问题,1.模型建立,0-1整数规划模型,max25x1+46x2+60 x3+53x4+55x5+17x6+16x7st2)150 x1+180 x2+300 x3+200 x4+300 x5+100 x6+80 x716)x6+x71endint7,例6.18选址问题,2.模型求解,用LINDO软件求解，编程如下：,所有的7个决策变量均是0-1变量,求解得到最优选址方案为:东区选A3；西区选A4，A5；南区选A6,A7。公司获得的最大年利润为201万元.,生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小,按照工艺要求，确定下料方案，使所用材料最省，或利润最大,例6.19合理下料问题,6.3.3整数规划模型实例,问题1.如何下料最节省?,问题2.客户增加需求：,节省的标准是什么？,由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？,例6.19合理下料问题,6.3.3整数规划模型实例,按照客户需要在一根原料钢管上安排切割的一种组合。,切割模式,合理切割模式的余料应小于客户需要钢管的最小尺寸,钢管下料,例6.19合理下料问题,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？,合理切割模式,2.所用原料钢管总根数最少,钢管下料问题1,两种标准,1.原料钢管剩余总余量最小,例6.19合理下料问题,约束,满足需求,决策变量,目标1（总余量）,按模式2切割12根,按模式5切割15根，余料27米,最优解：x2=12,x5=15,其余为0；最优值：27。,整数约束：xi为整数,例6.19合理下料问题,当余料没有用处时，通常以总根数最少为目标,目标2（总根数）,钢管下料问题1,约束条件不变,最优解：x2=15,x5=5,x7=5,其余为0；最优值：25。,xi为整数,按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米,虽余料增加8米，但减少了2根,与目标1的结果“共切割27根，余料27米”相比,例6.19合理下料问题,钢管下料问题2,对大规模问题，用模型的约束条件界定合理模式,增加一种需求：5米10根；切割模式不超过3种。,现有4种需求：4米50根，5米10根，6米20根，8米15根，用枚举法确定合理切割模式，过于复杂。,决策变量,xi按第i种模式切割的原料钢管根数(i=1,2,3),r1i,r2i,r3i,r4i第i种切割模式下，每根原料钢管生产4米、5米、6米和8米长的钢管的数量,例6.19合理下料问题,满足需求,模式合理：每根余料不超过3米,整数非线性规划模型,钢管下料问题2,目标函数（总根数）,约束条件,整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数,例6.19合理下料问题,增加约束，缩小可行域，便于求解,原料钢管总根数下界：,特殊生产计划：对每根原料钢管模式1：切割成4根4米钢管，需13根；模式2：切割成1根5米和2根6米钢管，需10根；模式3：切割成2根8米钢管，需8根。原料钢管总根数上界：13+10+8=31,模式排列顺序可任定,钢管下料问题2,需求：4米50根，5米10根，6米20根，8米15根,每根原料钢管长19米,例6.19合理下料问题,LINGO求解整数非线性规划模型,Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.0000000.000000R210.0000000.000000R221.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000