§3.4 生产组织与计划问题
例 某工厂用 m 台机床： A1, A2,L Am ，加工 n 种零件： B1, B2,L Bn .在一个生产周期内，已知第 i 台机床 Ai 只能 工作 ai 个机时，i 1, 2,L m .工厂必须完成加工零件 B j 的数量为 b j 个，j 1, 2,L n .机床 Ai 加工零件 B j 一个所 需的机时和成本分别为 tij （机时/个）和 cij（元/个）. 问：在这个生产周期，应如何安排各机床的生产任务， 才能既完成加工任务，又使总的加工成本最小。
模型建立
设xi
1, 对第i个项目投资，
0，
否则， i 1, 2,L
n
Z 为总利税收入（亿元）
则模型为：
max z m ci xi
i 1
n
s.t. bi xi b
i 1
xi 0或1
§3.2 背包问题
例 设有一个容积为b ,有n 个体积分 别为 bi (i 1,2,L n) ，使用价值分别为 ci (i 1,2,L n) 的物品可以装入背包，问 应选择哪几件物品装入背包，才 能得到最大的使用价值？试建立 数学模型.
4x1 3x2 2x3 x4 x5 50 x2 2x4 x5 3x6 20
x3 x5 2x7 15
xi 为整数
最优解：x2=15, x5=5, x7=5, 其余为0；
最优值：25。
按模式2切割15根， 与目标1的结果“共切割
按模式5切割5根， 27根，余料27米” 相比
按模式7切割5根， 共25根，余料35米
目标1（总余量） Min Z1 3x1 x2 3x3 3x4 x5 x6 3x7
模 4米 6米 8米 余 式 根数 根数 根数 料
14
0
03
约束 满足需求
4x1 3x2 2x3 x4 x5 50
23
1
0 1 x2 2x4 x5 3x6 20
32
0
1 3 x3 x5 2x7 15
xi 0且xi I={0,1,2,L }，i 1, 2,3
练习:
现有长度为500cm的钢管， 要截98cm,78cm的两种 钢管，各要1000根，2000 根。问：怎样截，用原料最 少？
方案
规 格
每根 下料 数
B1
B2
B3
B4
B5
B6
需求量
A1 5
4
3
2
1
0
1000根
A2 0
1
2
3
5
6
2000根
模型建立
• 设 x为j 采用方案 下Bj 料所用钢板的 数量， y为所用钢板总数
n
min y xj
j 1
n
s.t. aij x j bi ,i 1, 2,L m
j 1
x
j
0,且x j I ,
j
1, 2,L
n, I
{0,1, 2,L }
客户需求
例3 钢管下料 原料钢管:每根19米
合理切割模式 6米钢管根数 8米钢管根数
1
4
0
0
2
3
1
0
3
2
0
1
4
1
2
6
0
3
0
7
0
0
2
余料(米) 3 1 3 3 1 1 3
为满足客户需要，按照哪些种合理模式，每种模式
切割多少根原料钢管，最为节省？
两种 标准
1. 原料钢管剩余总余量最小 2. 所用原料钢管总根数最少
决策变量
xi ~按第i 种模式切割的原料钢管根数(i=1,2,…7)
4米50根
6米20根
8米15根
问题: 如何下料最节省 ? 节省的标准是什么？
钢管下料
切割模式
按照客户需要在一根原料钢管上安排切割的一种组合。
4米1根 6米1根
8米1根
余料1米
4米1根 6米1根
6米1根
余料3米
8米1根
8米1根
余料3米
合理切割模式的余料应小于客户需要钢管的最小尺寸
钢管下料问题
模式
1 4米钢管根数
41 51
2 1
0 1
3 1
整数约束： xi 为整数
60
3
0 1 最优解：x2=12, x5=15,
70
需 50 求
0 20
23 15
其余为0； 最优值：27
按模式2切割12根,按模式5切割15根，余料27米
目标2（总根数） Min Z2 x1 x2 x3 x4 x5 x6 x7
约束条 件不变
方案
规 每根原料下 B1
B2
格 管根数
B3 需求量
3米长
3个 2个 0个
5根
4米长 余料量
0个 1个 1米 0米
2个
5根
所用钢 2米 筋数最
少
模型建立
• 设 x1, x2为, x3采用方案 为所用y钢筋总数
B1所, B2用, B钢3 筋数，
min y x1 x2 x3
s.t.3x1 2x2 5 x2 2x3 5
虽余料增加8米，但减少了2根
1.当余料没有用处时，通常以总根数最少为目标
2.在需求的规格数量不多的情况下，可采用“列 举 法”，确定可行的、合理的切割模式。当规格数量 >=4时，列举工作量就很大了。
3.下料问题建模，由两部分构成
确定下料可行、合理的模式--无通用的方法
构造优化模型—选择合适的目标
4.对于一维（钢管、钢筋等）下料问题，当所需要的 规格数量不多时，可采用枚举法求解。
模型建立
•令
1, 装第i件物品，
xi 0,
否则 i 1, 2,L , n
• 设装入物品的总价值为z，则上述背包问
题的数学模型为
n
max z ci xi ,
i 1
n
s.t. bi xi b,
i 1
xi
0或1，i 1, 2,L
n
§3.3 合理下料问题
例 1 某工厂有 10 米长的钢管若干 根，要截取 3 米、4 米长的钢管各 5 根，问：如何截取，使所用钢筋数 最少？
第3章 整数规划模型
§3.1 投资决策问题
例 某市有 b 亿元资金用于 n 个项目投 资，对第 i 个项目投资需要 bi 亿元，可 获 得 利 税 收 入 ci 亿 元 . 试 确 定 投 资 方 案，使得该市的利税收入最多.
问题分析
• 目标：利税收入； • 决策量：由于每个项目投资数额已定，
只是投与不投，我们选择0-1变量； • 约束：总资金b亿元.
模型的建立
解：设 xi 为采用第 i 种方案所用原料数， y 为
原料总数
6
min y xi
s.t.x1
4x2
3x3
i 1
2x4
x5
1000;
x2
2x3
3x4
5x5
6x6
2000;
xi 0,且xi为整数(i=1,2,L 6)
例 2 假设要用某类钢板下 m 种零件 A1, A2,L Am 的毛料. 根据既省料又容易操作的原则，人们在一块钢板 上，已经设计出 n 种不同的下料方案，设在第 j 种 下料方案中，可下得第 i 种零件 Ai 的个数为 aij ，第 i 种零件的需要量为 bi ,i 1, 2,L m .问应如何下料， 才能既满足需要，又使所用的钢板总数最少？