数学建模案例之整数规划.ppt

《数学建模案例之整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数学建模案例之整数规划内容：如何建立整数规划模型举例整数规划模型的求解方法要求：掌握整数规划模型的建立方法掌握利用数学软件求解整数规划问题的方法理解分支定界法的思想和实施步骤重点、难点：重点:整数规划模型的建立和软件求解难点:整数规划问题的理论求解方法__分支定界法简介最优化问题中的所有变量均为整数时，这类问题称为整数规划问题如果线性规划中的所有变量均为整数时，称这类问题为整数线性规划问题整数规划可分为整数线性规划和整数非线性规划，以及混合整数规划等混合整数规划指部分变量可以取非整数的整数规划(混合整

2、数线性规划问题还没有统一的解法)原料下料类问题：生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小按照工艺要求，确定下料方案，使所用材料最省，或利润最大例题1：钢管下料问题某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出，从钢管厂进货时得到的原料都是19米。（1）现有一顾客需要50根4米、20根6米和15根8米的钢管。应如何下料最节省？（2）零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需

3、要（1）中的三种钢管外，还需要10根5米的钢管。应如何下料最节省。问题1.如何下料最节省?例1钢管下料问题2.客户增加需求：原料钢管:每根19米4米50根6米20根8米15根客户需求节省的标准是什么？由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？5米10根按照客户需要在一根原料钢管上安排切割的一种组合。切割模式,例如：余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料应小于客户需要钢管的最小尺寸余料3米8米1根8米1根钢管下料

4、为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？合理切割模式2.所用原料钢管总根数最少模式4米钢管根数6米钢管根数8米钢管根数余料(米)14003231013201341203511116030170023钢管下料问题1两种标准1.原料钢管剩余总余量最小模型构成引入决策变量xi～按第i种模式切割的原料钢管根数(i=1,2,…7)构建目标函数总余料最少总根数最少模型构成约束条件需求约束：决策变量取值约束：xj为非负整数模式4米根数6米根数8米根数余料14003231013201

5、341203511116030170023需求502015数学模型目标：总余料最少s.t.xj为非负整数，j=1,2,…,7数学模型目标：总根数最少s.t.xj为非负整数，j=1,2,…,7整数线性规划问题解法--分支定界法分支定界法简介与基本思想分支定界法可用于解纯整数或混合的整数规划问题。在20世60年代初由LandDoig和Dakin等人提出。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。设有最大化的整数规划问题A，与它相应的线性规划为问题B，从解问题B开始，若其最优解不

6、符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作z2,而A的任意可行解的目标函数值将是z*的一个下界z1,分支定界法就是将B的可行域分成子区域（称为分支）的方法，逐步减小z2和增大z1,最终求到z*。分支定界法解纯整数规划和混合整数规划问题1.首先忽略整数约束求解，求得原问题的最优解x2.如果决策变量xi本是整数要求，但是得到的结果xi=u（不是整数）,则将原问题归结为2个区域的线性规划求解，这个两个区域为分别增加约束条件xi≥ceil(u)和xi≤floor(u)3.然后分

7、别都这两个规划模型重复上面的步骤，直到满足整数要求为止。4.再选出最优解。分支定界法的计算举例例：利用分支定界算法求解IP问题：分支定界法的计算举例P0x1=2.25x2=3.75z=41.25x1=1.8x2=4z=41x1=3x2=3z=390≤z*≤41.25P1x2≥4P2x2≤3分支定界法的计算举例x1=1.8x2=4z=41P1不可行x1=1x2=40/9z=365/9P3x1≥2P4x1≤1分支定界法的计算举例x1=1x2=40/9z=365/9P4P5x2≤4P6x2≥5x1=1x2=

8、4z=37z*≥37x1=0x2=5z=40z*≥40分支定界法的计算举例P1x2≥4P2x2≤3P3x1≥2P4x1≤1P5x2≤4P6x2≥5P0最优解为：x*=(0,5)T最优值为：z*=40.模型求解：Lindo程序（总余料最小）min3x1+x2+3x3+3x4+x5+x6+3x7s.t.4x1+3x2+2x3+x4+x5>=50x2+2x4+x5+3x6>=20x3+x5+2x7>=15endgin7（gin7表示模型中出现的7个变量均为整型