数学建模案例之整数规划

数学建模

数学建模案例之整数规划

数学建模

内容： 如何建立整数规划模型举例 整数规划模型的求解方法 要求： 掌握整数规划模型的建立方法 掌握利用数学软件求解整数规划问题的方法 理解分支定界法的思想和实施步骤 重点、难点： 重点: 整数规划模型的建立和软件求解 难点: 整数规划问题的理论求解方法__分支定界法

数学建模

简介最优化问题中的所有变量均为整数时，这类问题称 为整数规划问题 如果线性规划中的所有变量均为整数时，称这类问 题为整数线性规划问题 整数规划可分为整数线性规划和整数非线性规划， 以及混合整数规划等 混合整数规划指部分变量可以取非整数的整数规划 (混合整数线性规划问题还没有统一的解法)

数学建模

原料下料类问题： 生产中通过切割、剪裁、冲压等手段，将 原材料加工成所需大小 按照工艺要求，确定下料方案，使所用材 料最省，或利润最大

数学建模

例题1:钢管下料问题某钢管零售商从钢管厂进货，将钢管按照顾客的要 求切割后售出，从钢管厂进货时得到的原料都是19米。 (1)现有一顾客需要50根4米、20根6米和15根8 米的钢管。应如何下料最节省？ (2)零售商如果采用的不同切割模式太多，将会 导致生产过程的复杂化，从而增加生产和管理成本，所 以该零售商规定采用的不同切割模式不能超过3种。此 外，该客户除需要(1)中的三种钢管外，还需要10根5 米的钢管。应如何下料最节省。

数学建模

例1 钢管下料客户需求 50根 4米50根 6米20根 20根 原料钢管:每根 米 原料钢管:每根19米 15根 8米15根 节省的标准是什么？ 节省的标准是什么？ 5米10根 米 根

问题1. 问题 如何下料最节省 ? 问题2. 客户增加需求： 问题 客户增加需求：

由于采用不同切割模式太多，会增加生产和管理成本， 由于采用不同切割模式太多，会增加生产和管理成本， 规定切割模式不能超过3种 如何下料最节省？ 规定切割模式不能超过 种。如何下料最节省？

数学建模

钢管下料

切割模式,例如： 切割模式 例如： 例如

按照客户需要在一根原料钢管上安排切割的一种组合。 按照客户需要在一根原料钢管上安排切割的一种组合。 4米 1根 4米 1根 6米 1根 6米 1根 8米 1根 6米 1根 8米 1根 余料1 余料1米 余料3 余料3米 余料3 余料3米

8米 1根

合理切割模式的余料应小于客户需要钢管的最小尺寸 合理切割模式的余料应小于客户需要钢管的最小尺寸

数学建模

钢管下料问题1 钢管下料问题1模式 1 2 3 4 5 6 7 4米钢管根数 米钢管根数 4 3 2 1 1 0 0 6米钢管根数 米钢管根数 0 1 0 2 1 3 0

合理切割模式8米钢管根数 米钢管根数 0 0 1 0 1 0 2 余料(米 余料 米) 3 1 3 3 1 1 3

为满足客户需要，按照哪些种合理模式，

为满足客户需要，按照哪些种合理模式，每种模式 切割多少根原料钢管，最为节省？ 切割多少根原料钢管，最为节省？ 两种 标准 1.原料钢管剩余总余量最小 1.原料钢管剩余总余量最小 2.所用原料钢管总根数最少 2.所用原料钢管总根数最少

数学建模

模型构成引入决策变量xi~按第i 种模式切割的原料钢管根数(i=1,2,…7)

构建目标函数总余料最少

Min Z1 = 3x1 + x2 + 3x3 + 3x4 + x5 + x6 + 3x7总根数最少

Min Z2 = x1 + x2 + x3 + x4 + x5 + x6 + x7

数学建模

模型构成约束条件需求约束：4 x1 + 3 x2 + 2 x3 + x4 + x5 ≥ 50模 式 1 2 3 4 5 6 7 需 求 4米 米 根数 4 3 2 1 1 0 0 50 6米 米 根数 0 1 0 2 1 3 0 20 8米 米 根数 0 0 1 0 1 0 2 15 余 料 3 1 3 3 1 1 3

x2 + 2 x4 + x5 + 3 x6 ≥ 20

x3 + x5 + 2 x7 ≥ 15

决策变量取值约束： xj为非负整数

数学建模

数学模型目标：总余料最少

Min Z1 = 3x1 + x2 + 3x3 + 3x4 + x5 + x6 + 3x7s.t.

4 x1 + 3 x2 + 2 x3 + x4 + x5 ≥ 50

x2 + 2 x4 + x5 + 3 x6 ≥ 20

x3 + x5 + 2 x7 ≥ 15xj为非负整数，j=1,2,…,7 为非负整数，

数学建模

数学模型目标：总根数最少

Min Z2 = x1 + x2 + x3 + x4 + x5 + x6 + x7s.t.

4 x1 + 3 x2 + 2 x3 + x4 + x5 ≥ 50

x2 + 2 x4 + x5 + 3 x6 ≥ 20

x3 + x5 + 2 x7 ≥ 15xj为非负整数，j=1,2,…,7 为非负整数，

数学建模

整数线性规划问题解法--分支定界法分支定界法简介与基本思想 分支定界法可用于解纯整数或混合的整数规划问题。在20世 60年代初由Land Doig和Dakin等人提出。由于这方法灵活且便于 用计算机求解，所以现在它已是解整数规划的重要方法。 设有最大化的整数规划问题A,与它相应的线性规划为问题 A B,从解问题B开始，若其最优解不符合A的整数条件，那么B的 最优目标函数必是A的最优目标函数z*的上界，记作z2,而A的任意 可行解的目标函数值将是z*的一个下界z1,分支定界法就是将B的 可行域分成子区域(称为分支)的方法，逐步减小z2和增大z1,最 终求到z*。

数学建模

分支定界法解纯整数规划和混合整数规划问题1.首先忽略整数约束求解，求得原问题的最优解 x 2.如果决策变量 xi 本是整数要求，但是得到的结果xi =u(不是整数), 则将原问题归结为2个区域的线性规划求解，这个两个区域为分别增加约 束条件

xi ≥ceil(u) 和 xi ≤floor(u)3.然后分别都这两个规划模型重复上面的步骤，直到满足整数要求为止。 4.再选出最优解。

数学建模

分支定界法的计算举例例：利用分支定界算法求解IP问题： max s .t . z = 5 x1 + 8 x2 x1 + x2 ≤ 6 5 x1 + 9 x2 ≤ 45 xi ≥ 0, xi ∈ I , i = 1, 2.

数学建模

分支定界法的计算举例P00≤z*≤41.25 ≤

x1=2.25 x2=3.75 z=41.25x2≤3

max s .t . max s .t . max s .t .

z = 5 x1 + 8 x2 x1 + x2 ≤ 6 5 x

1 + 9 x2 ≤ 45 xi ≥ 0, i = 1, 2.z = 5 x1 + 8 x2 x1 + x2 ≤ 6 5 x1 + 9 x2 ≤ 45 x1 ≥ 0, x2 ≥ 4z = 5 x1 + 8 x2 x1 + x2 ≤ 6 5 x1 + 9 x2 ≤ 45 x1 ≥ 0, x2 ≤ 3 ( P2 )

( P0 )

x2≥4

( P1 )

P1 x1=1.8 x2=4 z=41

P2 x1=3 x2=3 z=39