《8 数学规划方法建模(2).ppt》由会员分享，可在线阅读，更多相关《8 数学规划方法建模(2).ppt（54页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 Mathematical Modeling 2008 Department of Mathematics HUST第六章第六章 数学规划方法建模数学规划方法建模 第六章第六章 数学规划方法建模数学规划方法建模 6.1 线性规划模型线性规划模型 6.2 非线性规划模型非线性规划模型6.3 整数规划模型整数规划模型 Mathematical Modeling 2008 Department of Mathematics HUST 6.2 非非线性规划模型线性规划模型凡目标函数和约束条件中包含有非线性函数的凡目标函数和约束条件中包含有非线性函数的数学规划问题都称为非线性规划问题。它主要数学规划问题
2、都称为非线性规划问题。它主要分为无约束非线性规划与约束非线性规划。分为无约束非线性规划与约束非线性规划。较之线性规划模型而言，较之线性规划模型而言，非线性规划模型更能真非线性规划模型更能真实地反映问题的实质。实地反映问题的实质。Mathematical Modeling 2008 Department of Mathematics HUST6.2.1 非线性规划模型简介非线性规划模型简介 1.1.无约束的非线性规划模型（以最小目标为例）无约束的非线性规划模型（以最小目标为例）其中，其中，f 是是的的非线性函数，非线性函数，称为可行域。称为可行域。若若记记,则则其模型的矩其模型的矩阵阵形式形式为
3、为 Mathematical Modeling 2008 Department of Mathematics HUST2.2.约束非线性规划模型约束非线性规划模型无约束的非线性规划模型与约束非线性规划模无约束的非线性规划模型与约束非线性规划模型统称为非线性规划模型，本节主要介绍约束线型统称为非线性规划模型，本节主要介绍约束线性规划模型，简记成性规划模型，简记成NLPNLP。6.2.1 非线性规划模型简介非线性规划模型简介 其中，其中，的的非非线线性函数。性函数。中至少有一个是中至少有一个是 若若记记,则则其模型的矩其模型的矩阵阵形式形式为为 Mathematical Modeling 2008
4、 Department of Mathematics HUST 设用甲、乙、丙三种有限资源生产设用甲、乙、丙三种有限资源生产A,B,C,D四种产品、四种产品、产品的资源消耗定额及资源的有限供应量如表产品的资源消耗定额及资源的有限供应量如表6.8所示。所示。表表6.8 产产品的消耗定品的消耗定额额与与资资源供源供应应量量消耗定额消耗定额 产品产品资源资源ABCD资源可供应量资源可供应量甲甲1 12 23 32 2200200乙乙7 79 98 81 1300300丙丙3 30 01 17 7400400 假定假定A、B、C、D四种产品价格随产量的扩大而递减，四种产品价格随产量的扩大而递减，其需求
5、函数分别为其需求函数分别为试确定四种产品的产量，以便使总受益最大。试确定四种产品的产量，以便使总受益最大。例例6.106.2.1 非线性规划模型简介非线性规划模型简介 Mathematical Modeling 2008 Department of Mathematics HUST设设A,B,C,D四种产品的产量分别为四种产品的产量分别为例例6.10的求解的求解则问题的目标函数（总收益函数）则问题的目标函数（总收益函数）第一项是不变价格下的总收益，第一项是不变价格下的总收益，第二项是需要扣除的因价格变动造成的收益值第二项是需要扣除的因价格变动造成的收益值6.2.1 非线性规划模型简介非线性规划
6、模型简介 Mathematical Modeling 2008 Department of Mathematics HUST注意到资源约束，上述问题可表为注意到资源约束，上述问题可表为在实际经济活动中，在实际经济活动中，产量规模对价格的影响产量规模对价格的影响常常常常是一个不可忽略的重要因素：上述模型由于适当是一个不可忽略的重要因素：上述模型由于适当地考虑了价格的可变部分对总收益的影响，而相地考虑了价格的可变部分对总收益的影响，而相应的线性规划模型，总收益函数只能在假定某不应的线性规划模型，总收益函数只能在假定某不变价格的情况下由产量变价格的情况下由产量 线性确定，线性确定，故较之线性模型更能
7、真实地反映问题的实质。故较之线性模型更能真实地反映问题的实质。非线性非线性规划问题规划问题6.2.1 非线性规划模型简介非线性规划模型简介 例例6.10的求解的求解 Mathematical Modeling 2008 Department of Mathematics HUST6.2.2 非线性规划模型的求解非线性规划模型的求解非线性规划模型的求解具有一定的难度，并且求非线性规划模型的求解具有一定的难度，并且求解非线性规划问题的方法是多种多样的，解非线性规划问题的方法是多种多样的，解某些问解某些问解某些问解某些问题有效的方法，对另外的问题却未必有效题有效的方法，对另外的问题却未必有效题有效的
8、方法，对另外的问题却未必有效题有效的方法，对另外的问题却未必有效。一般来说，求解非线性规划的全局最优解是困一般来说，求解非线性规划的全局最优解是困难的，通常所得到的是难的，通常所得到的是局部最优解局部最优解局部最优解局部最优解。在此介绍用在此介绍用LINGOLINGO软件来求解非线性规划模型。软件来求解非线性规划模型。还有还有,求解非线性规划问题的迭代常常是无限的，求解非线性规划问题的迭代常常是无限的，即在迭代中将产生一个无穷点列，换言之，所得到即在迭代中将产生一个无穷点列，换言之，所得到的结果一般是的结果一般是满足一定精度的近似解满足一定精度的近似解满足一定精度的近似解满足一定精度的近似解。
9、Mathematical Modeling 2008 Department of Mathematics HUSTModel: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;end6.2.2 非线性规划模型的求解非线性规划模型的求解例例6.11 求解例求解例6.10中的非线性规划模型中的非线性规划模型用用LINGO软件求解，打开软件求解，打开LINGO执行文件，编程如下：执行文件，编程如
10、下：程序以程序以“Model：”开始开始 每行最后加每行最后加“；”最后以最后以“end”结结束束非非负约负约束可以缺省束可以缺省式子中可以有括号，右端可有数学符号。式子中可以有括号，右端可有数学符号。解解：乘号乘号“*”不能省略不能省略为为了了编编制程序的方便，我制程序的方便，我们们引入了中引入了中间变间变量量 Mathematical Modeling 2008 Department of Mathematics HUSTObjective value:1003.010 Variable Value Reduced Cost X1 0.000000 1.713858 X2 6.900608
11、 0.4349500E-07 X3 23.00476 0.000000 X4 53.85646 0.000000 X5 132.8497 0.000000最优解最优解是中间变量是中间变量)6.2.2 非线性规划模型的求解非线性规划模型的求解例例6.11 求解例求解例6.10中的非线性规划模型中的非线性规划模型选择菜单选择菜单 “Solve”进行求解，得到输出：进行求解，得到输出：最优值最优值 Mathematical Modeling 2008 Department of Mathematics HUST6.2.2 非线性规划模型的实例非线性规划模型的实例例例6.12 工程造价问题工程造价问题
12、 试建立使造价最省的数学模型。试建立使造价最省的数学模型。假定要建造容积为假定要建造容积为15001500m 的长方形仓库，的长方形仓库，已知每平方米墙壁、屋顶和地面的造价分别已知每平方米墙壁、屋顶和地面的造价分别为为4元，元，6元，元，12元，基于美学考虑，要求宽元，基于美学考虑，要求宽度应为高度的度应为高度的2倍。倍。Mathematical Modeling 2008 Department of Mathematics HUST1）决策变量。）决策变量。设仓库的宽、髙、长分别为设仓库的宽、髙、长分别为(m)。墙壁面积为墙壁面积为造价为造价为屋顶与地面面积为屋顶与地面面积为造价为造价为则目
13、标函数为则目标函数为6.2.2 非线性规划模型的实例非线性规划模型的实例例例6.12 工程造价问题工程造价问题 1.模型建立模型建立2）目标函数。）目标函数。Mathematical Modeling 2008 Department of Mathematics HUST容积限制容积限制比例限制比例限制非负限制非负限制由此得到数学模型为由此得到数学模型为非线性等式约束规划模型非线性等式约束规划模型非线性等式约束规划模型非线性等式约束规划模型用用LINGO软件求解，得到仓库的设计方案为：软件求解，得到仓库的设计方案为：最小造价为最小造价为例例6.12 工程造价问题工程造价问题 3）约束条件）约束
14、条件2.模型求解模型求解 Mathematical Modeling 2008 Department of Mathematics HUST表表6.9 经营计经营计划的数据划的数据设备设备公司可使用营业公司可使用营业时间（时间（h）单位售价（元）单位售价（元）3030450450800800售出单位设备花营业售出单位设备花营业时间（时间（h）0.50.5 2+0.25 2+0.25某公司经营两种设备，假设每种设备的单位售某公司经营两种设备，假设每种设备的单位售价以及售出单位设备所需的营业时间及该公司在价以及售出单位设备所需的营业时间及该公司在某段时间内的总营业时间均见表某段时间内的总营业时间均
15、见表6.9（表中（表中 为两种设备的售出数量）为两种设备的售出数量）,建立营业额最大的营建立营业额最大的营业计划模型。业计划模型。6.2.2 非线性规划模型的实例非线性规划模型的实例例例6.13 经营计划问题经营计划问题 Mathematical Modeling 2008 Department of Mathematics HUST两种设备的售出数量两种设备的售出数量 为待确定的决策变量为待确定的决策变量3 3）约束条件）约束条件 公司可使用营业时间的限制公司可使用营业时间的限制非负限制非负限制例例6.13 经营计划问题经营计划问题 模型建立与求解模型建立与求解数学数学模型模型LINGOLI
16、NGO软件软件1）决策变量）决策变量2）目标函数）目标函数 即为最大营业额即为最大营业额,设设z z为总营业额为总营业额,则目标函数为则目标函数为 Mathematical Modeling 2008 Department of Mathematics HUST设两杆平面桁架如图设两杆平面桁架如图6.4所示，元件是在所示，元件是在A点铰支的钢点铰支的钢管。在管。在A点点,结构受到垂直负荷载结构受到垂直负荷载2 2P。设已选定管壁厚度。设已选定管壁厚度为为h，跨度为，跨度为2 2b。试选择钢管的平均直径。试选择钢管的平均直径D桁架高度桁架高度H，使杆件既不屈服又不失平稳，而且桁架的总重量最轻。使
17、杆件既不屈服又不失平稳，而且桁架的总重量最轻。例例6.14 两杆平面桁架的优化设计两杆平面桁架的优化设计 6.2.2 非线性规划模型的实例非线性规划模型的实例图图6.4 两杆平两杆平面桁架面桁架结构图结构图 Mathematical Modeling 2008 Department of Mathematics HUST设桁架的设桁架的总重量为总重量为W其中，为钢的容重。其中，为钢的容重。例例6.14 两杆平面桁架的优化设计两杆平面桁架的优化设计 例例6.14的分析与建模的分析与建模 桁架的总重量最轻桁架的总重量最轻建模的目的建模的目的要不屈服保持平衡要不屈服保持平衡模型的决策变量模型的决策变
18、量钢管的平均直径钢管的平均直径D桁架高度桁架高度H目标函数目标函数 Mathematical Modeling 2008 Department of Mathematics HUST由于制造上的原因，由于制造上的原因，D与与H应有最大值及最小值的限制，即应有最大值及最小值的限制，即此处，此处，圆管杆件中的压应力不超过压杆稳定的临界应力，即圆管杆件中的压应力不超过压杆稳定的临界应力，即其中，其中，E为材料的弹性模量。为材料的弹性模量。例例6.14 两杆平面桁架的优化设计两杆平面桁架的优化设计 例例6.14的分析与建模的分析与建模 Mathematical Modeling 2008 Depart
19、ment of Mathematics HUST圆圆管杆件中的管杆件中的压应压应力力应应不超不超过过材料的屈服材料的屈服应应力力 即即两杆平面桁架优化设计问题的模型为：两杆平面桁架优化设计问题的模型为：例例6.14 两杆平面桁架的优化设计两杆平面桁架的优化设计 例例6.14的分析与建模的分析与建模 Mathematical Modeling 2008 Department of Mathematics HUST6.3 整数规划模型整数规划模型在一个数学规划模型中，如果它的在一个数学规划模型中，如果它的某些某些某些某些决策变量或全部变量要求取整数决策变量或全部变量要求取整数决策变量或全部变量要求
20、取整数决策变量或全部变量要求取整数时，就称时，就称这个数学规划模型为这个数学规划模型为整数规划整数规划整数规划整数规划模型。模型。整数规划模型整数规划模型整数线性规划模型整数线性规划模型整数非线性规划模型整数非线性规划模型整数规划整数规划 混合整数规划混合整数规划 0-10-1规划规划整数规划模型整数规划模型整数规划简记成整数规划简记成IP（integer programming）Mathematical Modeling 2008 Department of Mathematics HUST6.3.1 整数规划模型整数规划模型整数规划模型的一整数规划模型的一般形式般形式的线性函数的线性函数整
21、数线性规划模型整数线性规划模型中至少有一个是中至少有一个是的非线性函数的非线性函数若整数规划模型中的决策变量若整数规划模型中的决策变量 只能取只能取0或或1整数非线性规划模型整数非线性规划模型0-1规划规划 Mathematical Modeling 2008 Department of Mathematics HUST某航空公司为满足客运量日益增长的需要，欲购置某航空公司为满足客运量日益增长的需要，欲购置一批新的远程、中程及短程客机。每架远程客机价格一批新的远程、中程及短程客机。每架远程客机价格6700万元，中程客机万元，中程客机5000万元，短程客机万元，短程客机3500万元。万元。该公司
22、现有资金该公司现有资金7.5亿元可用于购买飞机。估计年净利亿元可用于购买飞机。估计年净利润每架远程客机为润每架远程客机为420万元，中程客机万元，中程客机300万元，短程万元，短程客机客机230万元。该公司现有熟练驾驶员可用来配备万元。该公司现有熟练驾驶员可用来配备30架架新飞机。维修设备足以维修新增加新飞机。维修设备足以维修新增加40架新的短程客机，架新的短程客机，每架中程客机的维修量相当于每架中程客机的维修量相当于4/3架短程客机，而每架架短程客机，而每架远程客机的维修量相当于远程客机的维修量相当于5/3架短程客机。架短程客机。例例6.15 6.3.1 整数规划模型整数规划模型为获取最大利
23、润，该公司应购买各类客机多少架为获取最大利润，该公司应购买各类客机多少架？Mathematical Modeling 2008 Department of Mathematics HUST设购买远程、中程、短程客机的数量分别设购买远程、中程、短程客机的数量分别为为 架，问题的架，问题的数学模型数学模型为：为：例例6.15 的模型建立的模型建立6.3.1 整数规划模型整数规划模型整数线性整数线性规划模型规划模型 Mathematical Modeling 2008 Department of Mathematics HUST6.3.2 整数规划模型的求解整数规划模型的求解 LINDO与与LING
24、O软件来求解整数规划模型软件来求解整数规划模型实际问题中实际问题中的整数规划的整数规划模型的求解模型的求解可先略去可先略去整数约束整数约束的条件的条件利用线性规划利用线性规划或非线性规划或非线性规划的方法求解的方法求解然后对其最然后对其最优解进行取优解进行取整处理整处理简简单单可利用可利用穷举法穷举法先根据约束条先根据约束条件确定所有的件确定所有的可行解可行解后将所有可行解代后将所有可行解代入目标函数，比较入目标函数，比较其值，求出最优解其值，求出最优解分枝定界算法割平面法分枝定界算法割平面法实际上，用这种方法得到的解未必是实际上，用这种方法得到的解未必是原整数规划模型的最优解。因此，该种原整
25、数规划模型的最优解。因此，该种方法是不足取的，但可借鉴这种思想。方法是不足取的，但可借鉴这种思想。事实上，求解整数规划的事实上，求解整数规划的松弛法松弛法就借鉴就借鉴了这种思想。了这种思想。Mathematical Modeling 2008 Department of Mathematics HUSTmax 420 x1+320 x2+230 x3st2)6300 x1+5000 x2+3500 x3750003)x1+x2+x3304)5x1+4x2+3x3120endgin 3例例6.16 求解例求解例6.15中的整数规划模型中的整数规划模型将例将例6.15中的模型输入中的模型输入LIN
26、DO如下：如下：LINDO中不能出现分中不能出现分数数(小数可以小数可以)，语句，语句4)是将对应的约束条件恒是将对应的约束条件恒等变形得到的。等变形得到的。“3 3个变量均为整数个变量均为整数”的说明语句的说明语句选择菜单选择菜单“Solve”进行求解进行求解,得最优解得最优解得最优值得最优值 Mathematical Modeling 2008 Department of Mathematics HUST例例6.17 汽车厂生产计划汽车厂生产计划 小型小型 中型中型 大型大型 现有量现有量钢材钢材（吨）1.5 3 5 600劳动时间劳动时间（小时）280 250 400 60000利润利润
27、（万元）2 3 4 6.3.3 整数规划模型实例整数规划模型实例 一汽车厂生产小、中、大三种类型的汽车，已知各类型每一汽车厂生产小、中、大三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润以及每月工厂钢材、辆车对钢材、劳动时间的需求，利润以及每月工厂钢材、劳动时间的现有量如表劳动时间的现有量如表6.10所示。所示。试制订月生产计划，使工厂的利润最大。试制订月生产计划，使工厂的利润最大。进一步讨论：由于各种条件限制进一步讨论：由于各种条件限制,如果生产某一类型汽车如果生产某一类型汽车,则至少要生产则至少要生产8080辆，那么最优的生产计划应做何改变。辆，那么最优的生产计划应做何改变。M
28、athematical Modeling 2008 Department of Mathematics HUST设每月生产小、中、大型汽车的数量分别为设每月生产小、中、大型汽车的数量分别为x1,x2,x3模型建立模型建立 线性线性规划规划模型模型(LP)例例6.17 汽车厂生产计划汽车厂生产计划 Mathematical Modeling 2008 Department of Mathematics HUST模型求解模型求解 3 3）模型中增加条件：模型中增加条件：x1,x2,x3 均为整数，均为整数，重新求解重新求解重新求解重新求解。OBJECTIVE FUNCTION VALUE 1)63
29、2.2581VARIABLE VALUE REDUCED COST X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 0.731183 3)0.000000 0.003226结果为小数，怎么办结果为小数，怎么办？1 1）舍去小数）舍去小数）舍去小数）舍去小数:取取x1=64，x2=167,算出目标函算出目标函数值数值z=629,与与LP最优最优值值632.2581相差不大。相差不大。2 2）试试试试探探探探：如如取取x1=65
30、，x2=167；x1=64，x2=168等等，计计算算函函数数值值z，通过比较可能得到更优的解通过比较可能得到更优的解通过比较可能得到更优的解通过比较可能得到更优的解。但必须检验它们是否满足约束条件。为什么？但必须检验它们是否满足约束条件。为什么？例例6.17 汽车厂生产计划汽车厂生产计划 Mathematical Modeling 2008 Department of Mathematics HUSTLINDO直接求解直接求解“gin 3”表示表示“前前3个变量为个变量为整数整数”，等价于：，等价于：gin x1gin x2gin x3 IP 的最优解的最优解x1=64，x2=168，x3=
31、0，最优值，最优值z=632 max 2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin 3 OBJECTIVE FUNCTION VALUE 1)632.0000VARIABLE VALUE REDUCED COST X1 64.000000 -2.000000 X2 168.000000 -3.000000 X3 0.000000 -4.000000 模型求解模型求解 结果输出结果输出例例6.17 汽车厂生产计划汽车厂生产计划 Mathematical Modeling 2008 Department of Mathem
32、atics HUST其中其中3个个子模型应子模型应去掉，然后去掉，然后逐一求解，比较目标函数值，逐一求解，比较目标函数值，再加上整数约束，得最优解：再加上整数约束，得最优解：方法方法1：分解为：分解为8个个LP子模型子模型 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1,x2,x3=0 或或 80 x1=80，x2=150，x3=0，最优值，最优值z=610例例6.17 汽车厂生产计划汽车厂生产计划 Mathematical Modeling 2008 Department of Mathematics HUSTLINDO中对中对0-1变量的限
33、定：变量的限定：int y1int y2int y3 方法方法2：引入引入0-1变量，化为整数规划变量，化为整数规划 M为大的正数，为大的正数，可取可取1000 OBJECTIVE FUNCTION VALUE 1)610.0000VARIABLE VALUE REDUCED COST X1 80.000000 -2.000000 X2 150.000000 -3.000000 X3 0.000000 -4.000000 Y1 1.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000 x1=0 或 80 x2=0 或 80 x3=0
34、 或 80最优解最优解同前同前 例例6.17 汽车厂生产计划汽车厂生产计划 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。Mathematical Modeling 2008 Department of Mathematics HUST方法方法3：化为整数非线性规划化为整数非线性规划 x1=0 或 80 x2=0 或 80 x3=0 或 80这样，原模型就变成了这样，原模型就变成了整数非线性规划模型整数非线性规划模型 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。例例6.17 汽车厂生产计划汽车厂生产计
35、划 Mathematical Modeling 2008 Department of Mathematics HUSTx1,x2,x3=0 或或 80Model:max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x30;x2*(x2-80)0;x3*(x3-80)0;gin(x1);gin(x2);gin(x3);end模型求解模型求解用用LINGO 软件求解软件求解语句语句“gin(x1)”是是“x1是整数是整数”的说明语句，其余的说明语句，其余相同（若相同（若y1是是0-1变量，应该用变量，应该用“int(y1)”来说明）来说
36、明）例例6.17 汽车厂生产计划汽车厂生产计划 程序以程序以“Model：”开始开始 每行最后加每行最后加“；”最后以最后以“end”结结束束非非负约负约束可以缺省束可以缺省式子中可以有括号式子中可以有括号,右端可有数学符号右端可有数学符号乘号乘号“*”不能省略不能省略 Mathematical Modeling 2008 Department of Mathematics HUSTObjective value:610.0000 Variable Value Reduced Cost X1 80.00000 -2.000000 X2 150.0000 -3.000000 X3 0.00000
37、0 0.000000最优解同前最优解同前 模型求解模型求解结果输出结果输出事实上，用事实上，用LINGO软件求解非线性规划问题往往软件求解非线性规划问题往往得到是局部最优解，其结果常依赖初值的选择，得到是局部最优解，其结果常依赖初值的选择，一般地仅当初值非常接近全局最优解时，才能得一般地仅当初值非常接近全局最优解时，才能得到正确的结果，这一点同学们要引起注意到正确的结果，这一点同学们要引起注意.例例6.17 汽车厂生产计划汽车厂生产计划 Mathematical Modeling 2008 Department of Mathematics HUST如选用如选用Ai，设备投资估计为设备投资估计
38、为bi元，每年可获利润估计为元，每年可获利润估计为ci元，问在投资总额不得超过元，问在投资总额不得超过b元的条件下，怎样选址元的条件下，怎样选址可使公司年利润最大？可使公司年利润最大？假设投资总额假设投资总额b为为10001000万元，设备投资估计万元，设备投资估计bi与每项投资与每项投资每年获利每年获利ci列于表列于表6.11，试求最优选址方案。，试求最优选址方案。i1 12 23 34 45 56 67 7b bi(万元万元)1501501801803003002002003003001001008080c ci(万元万元)2525464660605353555517171616某公司拟在
39、市东、西、南三区建立门市部，假设三个区共有某公司拟在市东、西、南三区建立门市部，假设三个区共有7个位置点个位置点Ai 选择，且规定：东区只能在选择，且规定：东区只能在A1，A2，A3中至多选两个点；西区只能在中至多选两个点；西区只能在A4，A5中两个点中至中两个点中至少选一个点；南区只能在少选一个点；南区只能在A6，A7中至少选一个点。中至少选一个点。6.3.3 整数规划模型实例整数规划模型实例 例例6.18 选址问题选址问题 Mathematical Modeling 2008 Department of Mathematics HUST1）决策变量决策变量。决策变量是确定是否选择。决策变量
40、是确定是否选择Ai点点,设设2）目标函数目标函数。如何选址使年利润最大。如何选址使年利润最大,用用z表示利润表示利润,则目标函数为则目标函数为3）约束条件约束条件。xi应满足选址限制及投资总额不超过应满足选址限制及投资总额不超过b元的限制元的限制例例6.18 选址问题选址问题 1.1.模型建立模型建立 Mathematical Modeling 2008 Department of Mathematics HUST建立数学模型为建立数学模型为例例6.18 选址问题选址问题 1.1.模型建立模型建立0-1整数规划模型整数规划模型 Mathematical Modeling 2008 Depart
41、ment of Mathematics HUSTmax 25x1+46x2+60 x3+53x4+55x5+17x6+16x7st2)150 x1+180 x2+300 x3+200 x4+300 x5+100 x6+80 x710003)280 x1+250 x2+400 x3600004)x1+x2+x316)x6+x71endint 7例例6.18 选址问题选址问题 2.2.模型求解模型求解用用LINDO软件求解，编程如下：软件求解，编程如下：所有的所有的7个决策变量均是个决策变量均是0-1变量变量求解得到最优选址方案为求解得到最优选址方案为:东区选东区选A A3 3；西区选；西区选A
42、A4 4，A A5 5；南区选南区选A A6 6,A,A7 7。公司获得的最大年利润为。公司获得的最大年利润为201201万元万元.Mathematical Modeling 2008 Department of Mathematics HUST生产中通过切割、剪裁、冲压等生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小手段，将原材料加工成所需大小按照工艺要求，确定下料方案，按照工艺要求，确定下料方案，使所用材料最省，或利润最大使所用材料最省，或利润最大例例6.19 合理下料问题合理下料问题6.3.3 整数规划模型实例整数规划模型实例 Mathematical Modeling 200
43、8 Department of Mathematics HUST问题问题1.如何下料最节省如何下料最节省?问题问题2.客户增加需求：客户增加需求：原料钢管原料钢管:每根每根19米米 4米米50根根 6米米20根根 8米米15根根 客户需求客户需求节省的标准是什么？节省的标准是什么？由于采用不同切割模式太多，会增加生产和管理成本，由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过规定切割模式不能超过3种。如何下料最节省？种。如何下料最节省？5米米10根根 例例6.19 合理下料问题合理下料问题6.3.3 整数规划模型实例整数规划模型实例 Mathematical Modelin
44、g 2008 Department of Mathematics HUST按照客户需要在一根原料钢管上安排切割的一种组合。按照客户需要在一根原料钢管上安排切割的一种组合。切割模式切割模式余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根 余料余料3米米 4米米1根根 6米米1根根 6米米1根根 合理切割模式合理切割模式的余料应小于客户需要钢管的最小尺寸的余料应小于客户需要钢管的最小尺寸余料余料3米米 8米米1根根 8米米1根根 钢管下料钢管下料 例例6.19 合理下料问题合理下料问题 Mathematical Modeling 2008 Department of Mathemati
45、cs HUST为满足客户需要，按照哪些种合理模式，每种模式为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？切割多少根原料钢管，最为节省？合理切割模式合理切割模式2.所用原料钢管总根数最少所用原料钢管总根数最少 钢管下料问题钢管下料问题1 1 两种两种标准标准1.原料钢管剩余总余量最小原料钢管剩余总余量最小例例6.19 合理下料问题合理下料问题 Mathematical Modeling 2008 Department of Mathematics HUST约束约束满足需求满足需求 决策变量决策变量 目标目标1（总余量）（总余量）按模式按模式2切割切割12根根,按模式按
46、模式5切割切割15根，余料根，余料27米米 模模式式4米米根数根数6米米根数根数8米米根数根数余余料料14003231013201341203511116030170023需求需求502015最优解：最优解：x2=12,x5=15,其余为其余为0；最优值：最优值：27。整数约束：整数约束：xi 为整数为整数例例6.19 合理下料问题合理下料问题xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数(i=1,2,，7)Mathematical Modeling 2008 Department of Mathematics HUST当余料没有用处时，当余料没有用处时，通常以总根数最少为
47、目标通常以总根数最少为目标 目标目标2（总根数）（总根数）钢管下料问题钢管下料问题1 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 合理下料问题合理下料问题 Mathematical Modeling 2008 Department of
48、 Mathematics HUST钢管下料问题钢管下料问题2对大规模问题，用模型的约束条件界定合理模式对大规模问题，用模型的约束条件界定合理模式增加一种需求：增加一种需求：5米米10根；切割根；切割模式不超过模式不超过3种。种。现有现有4种种需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根，用枚举法确定合理切割模式，过于复杂。根，用枚举法确定合理切割模式，过于复杂。决策变量决策变量 xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数(i=1,2,3)r1i,r2i,r3i,r4i 第第i 种切割模式下，每根原料钢管种切割模式下，每根原料钢管生产生产
49、4米、米、5米、米、6米和米和8米长的钢管的数量米长的钢管的数量例例6.19 合理下料问题合理下料问题 Mathematical Modeling 2008 Department of Mathematics HUST满足需求满足需求模式合理：每根模式合理：每根余料不超过余料不超过3米米整数非线性规划模型整数非线性规划模型钢管下料问题钢管下料问题2目标函数（目标函数（总根数）总根数）约束约束条件条件整数约束：整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整为整数数例例6.19 合理下料问题合理下料问题 Mathematical Modeling 2008 Departmen
50、t of Mathematics HUST增加约束，缩小可行域，便于求解增加约束，缩小可行域，便于求解原料钢管总根数下界：原料钢管总根数下界：特殊生产计划：对每根原料钢管特殊生产计划：对每根原料钢管模式模式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根，根