1.4 线性规划的应用
一、使用线性规划方法处理实际问题
必须具备的条件 (建模条件 )：
1)优化条件 ---问题的目标有极大化或极
小化的要求,而且能用决策变量的线性
函数来表示 。
2)选择条件 ---有多种可供选择的可行方
案, 以便从中选取最优方案 。
3） 限制条件 ---达到目标的条件是有一定限
制的 （ 比如, 资源的供应量有限度等 ）,
而且这些限制可以用决策变量的线性等
式或线性不等式表示出来 。
此外, 描述问题的决策变量相互之
间应有一定的联系, 有可能建立数学关
系, 即这些 变量之间是内部相关 的 。
二、建模步骤,
? 第一步：设置要求解的决策变量 。 决策变量
选取得当, 不仅能顺利地建立模型而且能方便
地求解, 否则很可能事倍功半 。
? 第二步：找出所有的限制, 即约束条件, 并
用决策变量的线性方程或线性不等式来表示 。
当限制条件多, 背景比较复杂时, 可以 采用图
示或表格形式列出所有的已知数据和信息, 以
避免, 遗漏, 或, 重复, 所造成的错误 。
? 第三步：明确目标要求, 并用决策变量
的线性函数来表示, 确定对函数是取极大
还是取极小的要求 。
决策变量的非负要求可以根据问题的
实际意义加以确定 。
讨论：这三步的顺序可以颠倒吗？
为什麽？
三,经济管理领域中
几类 典型的 LP问题
经济管理领域中有大量的实际问题可以归结
为线性规划问题来研究, 这些问题背景不同,
表现各异, 但数学模型却有着完全相同的形式 。
尽可能多地掌握一些典型的模型不仅有
助于深刻理解线性规划本身的理论和方法, 而
且有利于灵活地处理千差万别的实际问题, 提
高解决实际问题的能力 。
（ 一 ） 生产组织与计划问题
1,产品计划问题
2,产品配套问题
1、产品计划问题
问题的一般提法,用若干种原材
料 （ 资源 ） 生产某几种产品, 原材
料 （ 或资源 ） 供应有一定限制, 要
求制定一个产品生产计划, 使其在
一定数量的资源限制条件下能得到
最大的收益 。
如果 用
，
单位产品所需资源数（如原材料、人
力、时间等）、所得利润及可供应的资源
总量已知，如表所示，问应如何组织生产
才能使利润最大？
种产品，，生产 nAAA ?21
种资源mBBB,,,21 ?
产品计划问题有关信息表
单位 产
产品 品
所需
资源 资源
n
AAA ?
21
可 供 应 资 源
m
B
B
B
?
2
1
mnmm
n
n
aaa
aaa
aaa
?
????
?
?
21
22121
11211
m
b
b
b
?
2
1
单位产品所得利润
n
ccc ?
21
设出产品的计划数, 可列出这类问
题的数学模型如下,
?
?
?
?
?
?
?
?
?
??
???
?
? ?
?
是负数）（产品计划生产数不能
），，（
总量）的总数不能超过可供应源（生产各种产品所需资
njx
Bts
xcM a x Z
j
j
n
j
jj
?
?
210
..
1
m)1,2,(i
i
b
n
1j
j
x
ij
a
一般的产品计划问题举例 例 1-7,
某工厂生产 A,B两种产品, 均需经过两道工序,
每生产一吨产品 A需要经第一道工序加工 2小时, 第
二道工序加工 3小时；每生产一吨产品 B需要经第一
道工序加工 3小时, 第二道工序加工 4小时 。 可供利
用的第一道工序为 12小时, 第二道工序为 24小时 。
生产产品 B的同时产出副产品 C,每生产一吨产品
B,可同时得到 2吨产品 C而毋需外加任何费用；副产
品 C一部分可以盈利, 剩下的只能报废 。
出售产品 A每吨能盈利 400元, 产品 B每吨能盈利
1000元, 每销售一吨副产品 C能盈利 300元, 而剩余
要报废的则每吨损失 200元 。 经市场预测, 在计划期
内产品 C最大销量为 5吨 。 试列出线性规划模型, 决
定 A,B两种产品的产量, 使工厂总的利润最大 。
?信息整理：
产 品 加 工 工 时（小时） 盈 利（百元）
工序 1 工序 2
A 2 3 4
B 3 4 1 0
1, 2
盈利（最大销量为 5 ） 3
C 报废 - 2
可供利用工时 1 2 2 4
?利润与产量的关系图：
利润与产量的关系图,
利润 利润
2 0 2 0 -
- -
- -
5 - 5
5 1 0 5 1 0
产品 A 的产量 产品 C 的产量
?数学模型：
设,x1—— 产品 A的产量, x2—— 产品 B的
产量, x3—— 产品 C的销售量, x4—— 产
品 C的报废量 。 依题意, 可得
?
?
?
?
?
?
?
?
?
?
?
??
??
??
????
0,,,
5
2
2443
1232
..
23104
4321
3
431
21
21
4321
xxxx
x
xxx
xx
xx
ts
xxxxM a x Z
2、产品配套问题
例 1-8 某产品由两个零件 I和三个
零件 II组成，每个零件均可由三个车间
各自生产，但各车间的生产效率和总工
时限制各不相同，表中给出了有关信息。
试确定各车间生产每种零件的工作时间，
使生产产品的件数最多。
例 1-8有关信息表
其中,xij表示第 i个车间生产第 j个零件的时间数
注意 — — Z是非线性表达式！
车 间
总 工 时
生产效率（件 / 小时）
零件 I 零件 II
生产工时数
零件 I 零件 II
1 100 8 6
11
x
12
x
2 50 10 15
21
x
22
x
3 75 16 21
31
x
32
x
分析,
生产出两种零件的数量分别是 322212312111
21156,16108 xxxxxx ????
组装成的产品数为 z=
?
?
?
?
?
?
?
?????
3
21156
,
2
16108
m i n
322212312111
xxxxxx
处理：
① 引入一个新变量 Y,
令 Y=
?
?
?
?
?
?
?
?????
3
21156
,
2
16108
m i n
322212312111
xxxxxx
则目标要求可以写成,M a x Z = Y
② 把 Y 的表达式改写成两个不等式增添到约束条件中去
;
3
21156
,
2
16108
322212312111
XXX
Y
XXX
Y
??
?
??
?
于是得到该问题的 LP模型为：
M a x Z =Y
?
?
?
?
?
?
?
?
?
?
?
?
???
???
??
??
??
0,,,,,,
3
32
21
22
15
12
6
2
31
16
21
10
11
8
75
3231
50
2221
1 0 0
2111
..
323122211211 y
yxxx
yxxx
xx
xx
xx
ts
xxxxxx
(二 ) 合理下料问题
在加工业中，经常遇到这类问题。
问题的一般提法是, 已知某种尺寸的棒
料或板材，需要将其切割成一定数量既
定规格的几种零件毛坯，问应如何选取
合理的下料方法，使得既满足对截出毛
坯的数量要求，又使所用的原材料最少
（或废料最少）？
解决这类问题一般有两个步骤：
? 步骤一, 按照一定的思路设法列出所有的 排
料方案 （ 也称下料方案或排料图 ）, 当方案
很多, 甚至无法一一列出时, 通常应先 确定
一些筛选原则, 把明显不合理的方案删除,
仅仅考虑剩余的为数不太多的方案；
? 步骤二, 设 xi表示按第ｉ种方案下料的棒料根
数 （ 或板材块数 ） i=1,2,…,n,按照问题的要
求建立 LP模型 。
例 1-9 某厂接受了一批加工定货,
客户要求加工 100套钢架, 每套由长
2.9米, 2.1米和 1.5米的圆钢各一根组
成 。 现在仅有一批长 7.4米的棒料毛坯,
问应如何下料, 使所用的棒料根数最
少？
最简单的处理方法,从一根棒料上截
取 2.9米,2.1米和 1.5米的棒料各一根，
正好配成一套钢架,100套钢架总共需要
100根棒料毛坯。每根棒料毛坯剩下 0.9
米的料头,100根毛坯总共剩 90米料头。
—— 这是最好的办法吗？
合理套裁 肯定会有更好的效果。
先设法列出所有的下料方案,思路如图。
排列下料方案思路图
原料（ 7,4 米长棒料）
1,截规格 1( 2,9 米 ) 2,截规格 2( 2,1 米 ) 截规格 3( 1,5 米 )
最多截
取根数
n 1 =2
n1= 1
最多截
取根数
n 2 =3
n 2 = 2
n 2 = 1
最 多 截
取根数
n 3 = 4
5,8
余料 1,6
用料 2, 9
余料 4, 5
用料 6, 3
余料 1, 1
用料 4,2
余料 3,2
用料 2, 1
余料 5, 3
用料 6,0
余料 1,4
余料 余料
N 够截规格 2 吗? N 够截规格 3 吗?
( 2, 1 米 ) ( 1,5 米 )
Y Y
n 2 = 2
用料 4,2
余料 0,3
n 2 = 1
用料 2, 1
余料 2, 4
n 2 = 0
余料 4, 5
n 3 = 2
用料 3,0
余料 0,2
n 3 = 3
用料 4,5
余料 0,8
余料
N 够截规格 3 吗?
( 1,5 米 )
Y
n 3 = 1
用料 1,5
余料 0,1
n 3 = 0
用料 0
余料 0,3
n 3 = 1
用料 1, 5
余料 0, 9
n 3 = 3
用料 4,5
余料 0
方案 I
截 201
余料 0,1
方案 II
( 120)
余料 0, 3
方案 Ⅲ
( 1 11 )
余料 0,9
方案 Ⅳ
( 1 03 )
余料 0
方案 Ⅴ
( 030 )
余料 1, 1
方案 Ⅵ
( 022)
余料 0,2
方案 Ⅶ
( 013 )
余料 0,8
方案 Ⅷ
( 0 0 4 )
余料 1, 4
设 xi为按第 i种方案下料的棒料根数,
建立 LP模型如下：
?
?
?
?
?
?
?
?
????????
????????
????????
? ?
?
0,,,
1 0 043203101
1 0 001230120
1 0 000001112
..
821
87654321
87654321
87654321
8
1
xxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
ts
xM i n Z
i
i
?
（ 三 ） 合理配料问题
问题的一般提法：由多种原料配置成含有
m种成分的产品，已知产品中所含各成分的
需要量及每种原料的价格，同时知道各种原
料中所含 m种成分的数量，要求给出 使产品
成本最低的配料方案 。如,伙食问题 （也称
营养问题）,饲料配比问题,化工产品中的
混合问题 等都属于这类问题。
例 1-10 营养问题
要求制定一个既经济又合乎健康标准的食谱 。
一个简单的例子：
现准备采购甲, 乙两种食品, 表中给出了
已知价格及相关的营养成分 。 最右栏给出
了按营养学标准每人每天的最低需要量 。
问应如何采购食品才能在保证营养要求的
前提下花费最省？
表 1-2 营养问题已知数据表
1 公斤食物所
含营养成 食品
分数量
营养
成分
甲
乙
每 天 的 最 低
需 要 量
（单位）
维 生 素
淀 粉
蛋 白 质
1
5
3
3
1
2
9 0
1 0 0
1 2 0
单 价（元） 1, 2 1, 9
设 x1,x2分别为甲, 乙两种食品的采购量,
则购买两种食品的总费用为 Z=1.2x1+1.9x2，
依题意可列出下面的线性规划：
M i n Z = 1, 2 x 1 + 1, 9 x 2
?
?
?
?
?
?
?
?
??
??
??
0,
1 2 023
1 0 05
903
..
21
21
21
21
xx
xx
xx
xx
ts
营养问题适用范围：
& 运动员集训队食谱设计；
& 幼儿园, 医院等特殊群体的营养配餐；
& 机关, 学校, 企业等企事业单位团体
伙食设计；
& 家庭食谱设计；
小实践选题建议 2,为所在班级同学设计
不同要求的食谱
?对不同对象的 营养要求
—— 从营养学资料和通过医生咨询得到；
?各种 食品的价格
—— 通过不同季节的市场调查获取；
?一些 特殊要求, 比如 饮食习惯, 偏好 等
—— 可通过适当处理, 转化为约束条件加入
模型；
资料获取渠道及特殊要求的处理建议：
例 1-11（饲料配比问题） 某配合饲料
厂生产以鸡饲料为主的配合饲料，现准
备研制一种新的 肉用仔鸡专用饲料,所
用原料的营养成分和饲养标准见表，希
望这种新饲料 能满足肉用仔鸡的喂养需
要 又使 总成本尽可能低,应如何设计配
比方案？
原料营养成分表
营养成分
（ % ）
原料
粗蛋白
钙
总磷
赖氨酸
蛋氨酸
色氨酸
光氨酸
玉 米
豆 饼
麦 麸
鱼 粉
骨 粉
鸡促进素
8,6
4 3 0
1 5,4
62
---
---
0,0 4
0,3 2
0,1 4
3,9 1
3 6,4
3 1,5
0,2 1
0,5
1,0 6
2,9
1 6,4
4,5
0,2 7
2,4 5
0,5 4
4,3 5
---
---
0,1 3
0,4 8
0,1 8
1,6 5
---
---
0,0 8
0,6 0
0,27
0,8
---
---
0,1 8
0,6 0
0,4 0
0,5 6
---
---
已 知 各 种原料 的购进 价 1 公斤 分 别
为,0.314(玉米 ),054(豆饼 ),0.22（ 麦麸 ）,
1.20（ 鱼粉 ）, 0.40（ 骨粉 ）, 0.50（ 鸡促
进素 ） 元 。
营养成分需求表
所需营养
成分 ( % )
饲料
品种
粗蛋白
钙
总 磷
赖氨酸
蛋氨酸
色氨酸
光氨酸
肉用仔鸡 19.0 1.0 0.70 0.94 0.36 0.19 0.32
设 每 100公斤 饲料中配给的玉米、豆
饼、麦麸、鱼粉、骨粉、鸡促进素分别
为 x1,x2,x3,x4,x5,x6公斤,则
饲料配比即为 x1,x2,x3,x4,x5,x6；
于是,可建立下面的线性规划：
是否可以将约束条件两边分别扩大一个
倍数再进行计算？
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??????
????
????
????
????
??????
??????
????
??????
0,,,,,
1 0 0
32.056.040.060.018.0
19.08.027.060.008.0
36.065.118.048.013.0
94.035.454.045.227.0
7.05.44.169.206.15.021.0
15.314.3691.314.032.004.0
19624.15436.8
..
5.04.020.122.054.03 1 4.0
654321
654321
4321
4321
4321
4321
654321
654321
4321
654321
xxxxxx
xxxxxx
xxxx
xxxx
xxxx
xxxx
xxxxxx
xxxxxx
xxxx
ts
xxxxxxM i n Z
（ 四 ） 运输问题
运输问题大体上可以分为四种类型：
1,产销平衡的运输问题 （ 也称物资调运
问题 ）
2,产销不平衡的运输问题
3,作物布局问题
一般提法是：在若干块土地上种植若
干种作物, 已知各块土地的面积, 作物
计划播种面积及单产, 问如何安排种植
计划, 使总产量最高？
4,工厂布局问题
一般提法； 设有 n个原料产地 A1,A2,…, A n生产
某种原料分别为 ai个单位, 同时又分别需要成品 bi个
单位 （ i=1,2,… n）, 而一个单位成品需 c个单位原
料制成 。 若在 Ai地设加工厂, 则产品加工费用为 di元 /
单位, 在 Ai地设厂对生产规划有一定的限制 —— 生产
成品的数量最多为 li个单位, 最少为 fi个单位 。 原料
的单位运价及成品的单位运价均为已知, 问应在何
地设厂, 生产多少成品才能既满足需要又使生产费
用 （ 包括原料和成品运费, 成品加工费 ） 最省？
例 1-12 某油田通过输油管道向港口输送
原油, 中间有 4个泵站, 每段管道上的
输送能力如图所示, 已知泵站没有储存
能力, 求这个系统的最大输送能力 。
（五）最大流量问题
泵站 4
泵站 3油田 S
泵站 2
泵站 1 码头 t
5 12
4
8 11
9 6
7
10
设从各点往其它点的输送量如下表所示
出发点 到达点 输送量
S
S
泵站 1
泵站 1
泵站 2
泵站 2
泵站 3
泵站 3
泵站 4
泵站 1
泵站 2
泵站 3
码头 t
泵站 3
泵站 4
泵站 4
码头 t
码头 t
x1
x2
x3
x4
x5
x6
x7
x8
x9
依题意：
目标函数 为 输送原油的总量 ；
约束条件有两类,
?一类是管道上的流量约束；
?另一类是每个中间泵站上的平衡约束, 即
中间泵站上的原油流入量和流出量相等
根据上述分析建立线性规划模型如下：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
???
??
??
??
0,,
12
11
5
7
6
4
8
9
10
..
91
9
8
7
6
5
4
3
2
1
967
8753
652
431
21
xx
x
x
x
x
x
x
x
x
x
xxx
xxxx
xxx
xxx
ts
xxM a x Z
?
1号泵站平衡约束
2号泵站平衡约束
3号泵站平衡约束
4号泵站平衡约束
相应弧上的约束
第四次作业：
P72 1-8,1-9,1-10
一、使用线性规划方法处理实际问题
必须具备的条件 (建模条件 )：
1)优化条件 ---问题的目标有极大化或极
小化的要求,而且能用决策变量的线性
函数来表示 。
2)选择条件 ---有多种可供选择的可行方
案, 以便从中选取最优方案 。
3） 限制条件 ---达到目标的条件是有一定限
制的 （ 比如, 资源的供应量有限度等 ）,
而且这些限制可以用决策变量的线性等
式或线性不等式表示出来 。
此外, 描述问题的决策变量相互之
间应有一定的联系, 有可能建立数学关
系, 即这些 变量之间是内部相关 的 。
二、建模步骤,
? 第一步：设置要求解的决策变量 。 决策变量
选取得当, 不仅能顺利地建立模型而且能方便
地求解, 否则很可能事倍功半 。
? 第二步：找出所有的限制, 即约束条件, 并
用决策变量的线性方程或线性不等式来表示 。
当限制条件多, 背景比较复杂时, 可以 采用图
示或表格形式列出所有的已知数据和信息, 以
避免, 遗漏, 或, 重复, 所造成的错误 。
? 第三步：明确目标要求, 并用决策变量
的线性函数来表示, 确定对函数是取极大
还是取极小的要求 。
决策变量的非负要求可以根据问题的
实际意义加以确定 。
讨论：这三步的顺序可以颠倒吗？
为什麽？
三,经济管理领域中
几类 典型的 LP问题
经济管理领域中有大量的实际问题可以归结
为线性规划问题来研究, 这些问题背景不同,
表现各异, 但数学模型却有着完全相同的形式 。
尽可能多地掌握一些典型的模型不仅有
助于深刻理解线性规划本身的理论和方法, 而
且有利于灵活地处理千差万别的实际问题, 提
高解决实际问题的能力 。
（ 一 ） 生产组织与计划问题
1,产品计划问题
2,产品配套问题
1、产品计划问题
问题的一般提法,用若干种原材
料 （ 资源 ） 生产某几种产品, 原材
料 （ 或资源 ） 供应有一定限制, 要
求制定一个产品生产计划, 使其在
一定数量的资源限制条件下能得到
最大的收益 。
如果 用
，
单位产品所需资源数（如原材料、人
力、时间等）、所得利润及可供应的资源
总量已知，如表所示，问应如何组织生产
才能使利润最大？
种产品，，生产 nAAA ?21
种资源mBBB,,,21 ?
产品计划问题有关信息表
单位 产
产品 品
所需
资源 资源
n
AAA ?
21
可 供 应 资 源
m
B
B
B
?
2
1
mnmm
n
n
aaa
aaa
aaa
?
????
?
?
21
22121
11211
m
b
b
b
?
2
1
单位产品所得利润
n
ccc ?
21
设出产品的计划数, 可列出这类问
题的数学模型如下,
?
?
?
?
?
?
?
?
?
??
???
?
? ?
?
是负数）（产品计划生产数不能
），，（
总量）的总数不能超过可供应源（生产各种产品所需资
njx
Bts
xcM a x Z
j
j
n
j
jj
?
?
210
..
1
m)1,2,(i
i
b
n
1j
j
x
ij
a
一般的产品计划问题举例 例 1-7,
某工厂生产 A,B两种产品, 均需经过两道工序,
每生产一吨产品 A需要经第一道工序加工 2小时, 第
二道工序加工 3小时；每生产一吨产品 B需要经第一
道工序加工 3小时, 第二道工序加工 4小时 。 可供利
用的第一道工序为 12小时, 第二道工序为 24小时 。
生产产品 B的同时产出副产品 C,每生产一吨产品
B,可同时得到 2吨产品 C而毋需外加任何费用；副产
品 C一部分可以盈利, 剩下的只能报废 。
出售产品 A每吨能盈利 400元, 产品 B每吨能盈利
1000元, 每销售一吨副产品 C能盈利 300元, 而剩余
要报废的则每吨损失 200元 。 经市场预测, 在计划期
内产品 C最大销量为 5吨 。 试列出线性规划模型, 决
定 A,B两种产品的产量, 使工厂总的利润最大 。
?信息整理：
产 品 加 工 工 时（小时） 盈 利（百元）
工序 1 工序 2
A 2 3 4
B 3 4 1 0
1, 2
盈利（最大销量为 5 ） 3
C 报废 - 2
可供利用工时 1 2 2 4
?利润与产量的关系图：
利润与产量的关系图,
利润 利润
2 0 2 0 -
- -
- -
5 - 5
5 1 0 5 1 0
产品 A 的产量 产品 C 的产量
?数学模型：
设,x1—— 产品 A的产量, x2—— 产品 B的
产量, x3—— 产品 C的销售量, x4—— 产
品 C的报废量 。 依题意, 可得
?
?
?
?
?
?
?
?
?
?
?
??
??
??
????
0,,,
5
2
2443
1232
..
23104
4321
3
431
21
21
4321
xxxx
x
xxx
xx
xx
ts
xxxxM a x Z
2、产品配套问题
例 1-8 某产品由两个零件 I和三个
零件 II组成，每个零件均可由三个车间
各自生产，但各车间的生产效率和总工
时限制各不相同，表中给出了有关信息。
试确定各车间生产每种零件的工作时间，
使生产产品的件数最多。
例 1-8有关信息表
其中,xij表示第 i个车间生产第 j个零件的时间数
注意 — — Z是非线性表达式！
车 间
总 工 时
生产效率（件 / 小时）
零件 I 零件 II
生产工时数
零件 I 零件 II
1 100 8 6
11
x
12
x
2 50 10 15
21
x
22
x
3 75 16 21
31
x
32
x
分析,
生产出两种零件的数量分别是 322212312111
21156,16108 xxxxxx ????
组装成的产品数为 z=
?
?
?
?
?
?
?
?????
3
21156
,
2
16108
m i n
322212312111
xxxxxx
处理：
① 引入一个新变量 Y,
令 Y=
?
?
?
?
?
?
?
?????
3
21156
,
2
16108
m i n
322212312111
xxxxxx
则目标要求可以写成,M a x Z = Y
② 把 Y 的表达式改写成两个不等式增添到约束条件中去
;
3
21156
,
2
16108
322212312111
XXX
Y
XXX
Y
??
?
??
?
于是得到该问题的 LP模型为：
M a x Z =Y
?
?
?
?
?
?
?
?
?
?
?
?
???
???
??
??
??
0,,,,,,
3
32
21
22
15
12
6
2
31
16
21
10
11
8
75
3231
50
2221
1 0 0
2111
..
323122211211 y
yxxx
yxxx
xx
xx
xx
ts
xxxxxx
(二 ) 合理下料问题
在加工业中，经常遇到这类问题。
问题的一般提法是, 已知某种尺寸的棒
料或板材，需要将其切割成一定数量既
定规格的几种零件毛坯，问应如何选取
合理的下料方法，使得既满足对截出毛
坯的数量要求，又使所用的原材料最少
（或废料最少）？
解决这类问题一般有两个步骤：
? 步骤一, 按照一定的思路设法列出所有的 排
料方案 （ 也称下料方案或排料图 ）, 当方案
很多, 甚至无法一一列出时, 通常应先 确定
一些筛选原则, 把明显不合理的方案删除,
仅仅考虑剩余的为数不太多的方案；
? 步骤二, 设 xi表示按第ｉ种方案下料的棒料根
数 （ 或板材块数 ） i=1,2,…,n,按照问题的要
求建立 LP模型 。
例 1-9 某厂接受了一批加工定货,
客户要求加工 100套钢架, 每套由长
2.9米, 2.1米和 1.5米的圆钢各一根组
成 。 现在仅有一批长 7.4米的棒料毛坯,
问应如何下料, 使所用的棒料根数最
少？
最简单的处理方法,从一根棒料上截
取 2.9米,2.1米和 1.5米的棒料各一根，
正好配成一套钢架,100套钢架总共需要
100根棒料毛坯。每根棒料毛坯剩下 0.9
米的料头,100根毛坯总共剩 90米料头。
—— 这是最好的办法吗？
合理套裁 肯定会有更好的效果。
先设法列出所有的下料方案,思路如图。
排列下料方案思路图
原料（ 7,4 米长棒料）
1,截规格 1( 2,9 米 ) 2,截规格 2( 2,1 米 ) 截规格 3( 1,5 米 )
最多截
取根数
n 1 =2
n1= 1
最多截
取根数
n 2 =3
n 2 = 2
n 2 = 1
最 多 截
取根数
n 3 = 4
5,8
余料 1,6
用料 2, 9
余料 4, 5
用料 6, 3
余料 1, 1
用料 4,2
余料 3,2
用料 2, 1
余料 5, 3
用料 6,0
余料 1,4
余料 余料
N 够截规格 2 吗? N 够截规格 3 吗?
( 2, 1 米 ) ( 1,5 米 )
Y Y
n 2 = 2
用料 4,2
余料 0,3
n 2 = 1
用料 2, 1
余料 2, 4
n 2 = 0
余料 4, 5
n 3 = 2
用料 3,0
余料 0,2
n 3 = 3
用料 4,5
余料 0,8
余料
N 够截规格 3 吗?
( 1,5 米 )
Y
n 3 = 1
用料 1,5
余料 0,1
n 3 = 0
用料 0
余料 0,3
n 3 = 1
用料 1, 5
余料 0, 9
n 3 = 3
用料 4,5
余料 0
方案 I
截 201
余料 0,1
方案 II
( 120)
余料 0, 3
方案 Ⅲ
( 1 11 )
余料 0,9
方案 Ⅳ
( 1 03 )
余料 0
方案 Ⅴ
( 030 )
余料 1, 1
方案 Ⅵ
( 022)
余料 0,2
方案 Ⅶ
( 013 )
余料 0,8
方案 Ⅷ
( 0 0 4 )
余料 1, 4
设 xi为按第 i种方案下料的棒料根数,
建立 LP模型如下：
?
?
?
?
?
?
?
?
????????
????????
????????
? ?
?
0,,,
1 0 043203101
1 0 001230120
1 0 000001112
..
821
87654321
87654321
87654321
8
1
xxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
ts
xM i n Z
i
i
?
（ 三 ） 合理配料问题
问题的一般提法：由多种原料配置成含有
m种成分的产品，已知产品中所含各成分的
需要量及每种原料的价格，同时知道各种原
料中所含 m种成分的数量，要求给出 使产品
成本最低的配料方案 。如,伙食问题 （也称
营养问题）,饲料配比问题,化工产品中的
混合问题 等都属于这类问题。
例 1-10 营养问题
要求制定一个既经济又合乎健康标准的食谱 。
一个简单的例子：
现准备采购甲, 乙两种食品, 表中给出了
已知价格及相关的营养成分 。 最右栏给出
了按营养学标准每人每天的最低需要量 。
问应如何采购食品才能在保证营养要求的
前提下花费最省？
表 1-2 营养问题已知数据表
1 公斤食物所
含营养成 食品
分数量
营养
成分
甲
乙
每 天 的 最 低
需 要 量
（单位）
维 生 素
淀 粉
蛋 白 质
1
5
3
3
1
2
9 0
1 0 0
1 2 0
单 价（元） 1, 2 1, 9
设 x1,x2分别为甲, 乙两种食品的采购量,
则购买两种食品的总费用为 Z=1.2x1+1.9x2，
依题意可列出下面的线性规划：
M i n Z = 1, 2 x 1 + 1, 9 x 2
?
?
?
?
?
?
?
?
??
??
??
0,
1 2 023
1 0 05
903
..
21
21
21
21
xx
xx
xx
xx
ts
营养问题适用范围：
& 运动员集训队食谱设计；
& 幼儿园, 医院等特殊群体的营养配餐；
& 机关, 学校, 企业等企事业单位团体
伙食设计；
& 家庭食谱设计；
小实践选题建议 2,为所在班级同学设计
不同要求的食谱
?对不同对象的 营养要求
—— 从营养学资料和通过医生咨询得到；
?各种 食品的价格
—— 通过不同季节的市场调查获取；
?一些 特殊要求, 比如 饮食习惯, 偏好 等
—— 可通过适当处理, 转化为约束条件加入
模型；
资料获取渠道及特殊要求的处理建议：
例 1-11（饲料配比问题） 某配合饲料
厂生产以鸡饲料为主的配合饲料，现准
备研制一种新的 肉用仔鸡专用饲料,所
用原料的营养成分和饲养标准见表，希
望这种新饲料 能满足肉用仔鸡的喂养需
要 又使 总成本尽可能低,应如何设计配
比方案？
原料营养成分表
营养成分
（ % ）
原料
粗蛋白
钙
总磷
赖氨酸
蛋氨酸
色氨酸
光氨酸
玉 米
豆 饼
麦 麸
鱼 粉
骨 粉
鸡促进素
8,6
4 3 0
1 5,4
62
---
---
0,0 4
0,3 2
0,1 4
3,9 1
3 6,4
3 1,5
0,2 1
0,5
1,0 6
2,9
1 6,4
4,5
0,2 7
2,4 5
0,5 4
4,3 5
---
---
0,1 3
0,4 8
0,1 8
1,6 5
---
---
0,0 8
0,6 0
0,27
0,8
---
---
0,1 8
0,6 0
0,4 0
0,5 6
---
---
已 知 各 种原料 的购进 价 1 公斤 分 别
为,0.314(玉米 ),054(豆饼 ),0.22（ 麦麸 ）,
1.20（ 鱼粉 ）, 0.40（ 骨粉 ）, 0.50（ 鸡促
进素 ） 元 。
营养成分需求表
所需营养
成分 ( % )
饲料
品种
粗蛋白
钙
总 磷
赖氨酸
蛋氨酸
色氨酸
光氨酸
肉用仔鸡 19.0 1.0 0.70 0.94 0.36 0.19 0.32
设 每 100公斤 饲料中配给的玉米、豆
饼、麦麸、鱼粉、骨粉、鸡促进素分别
为 x1,x2,x3,x4,x5,x6公斤,则
饲料配比即为 x1,x2,x3,x4,x5,x6；
于是,可建立下面的线性规划：
是否可以将约束条件两边分别扩大一个
倍数再进行计算？
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??????
????
????
????
????
??????
??????
????
??????
0,,,,,
1 0 0
32.056.040.060.018.0
19.08.027.060.008.0
36.065.118.048.013.0
94.035.454.045.227.0
7.05.44.169.206.15.021.0
15.314.3691.314.032.004.0
19624.15436.8
..
5.04.020.122.054.03 1 4.0
654321
654321
4321
4321
4321
4321
654321
654321
4321
654321
xxxxxx
xxxxxx
xxxx
xxxx
xxxx
xxxx
xxxxxx
xxxxxx
xxxx
ts
xxxxxxM i n Z
（ 四 ） 运输问题
运输问题大体上可以分为四种类型：
1,产销平衡的运输问题 （ 也称物资调运
问题 ）
2,产销不平衡的运输问题
3,作物布局问题
一般提法是：在若干块土地上种植若
干种作物, 已知各块土地的面积, 作物
计划播种面积及单产, 问如何安排种植
计划, 使总产量最高？
4,工厂布局问题
一般提法； 设有 n个原料产地 A1,A2,…, A n生产
某种原料分别为 ai个单位, 同时又分别需要成品 bi个
单位 （ i=1,2,… n）, 而一个单位成品需 c个单位原
料制成 。 若在 Ai地设加工厂, 则产品加工费用为 di元 /
单位, 在 Ai地设厂对生产规划有一定的限制 —— 生产
成品的数量最多为 li个单位, 最少为 fi个单位 。 原料
的单位运价及成品的单位运价均为已知, 问应在何
地设厂, 生产多少成品才能既满足需要又使生产费
用 （ 包括原料和成品运费, 成品加工费 ） 最省？
例 1-12 某油田通过输油管道向港口输送
原油, 中间有 4个泵站, 每段管道上的
输送能力如图所示, 已知泵站没有储存
能力, 求这个系统的最大输送能力 。
（五）最大流量问题
泵站 4
泵站 3油田 S
泵站 2
泵站 1 码头 t
5 12
4
8 11
9 6
7
10
设从各点往其它点的输送量如下表所示
出发点 到达点 输送量
S
S
泵站 1
泵站 1
泵站 2
泵站 2
泵站 3
泵站 3
泵站 4
泵站 1
泵站 2
泵站 3
码头 t
泵站 3
泵站 4
泵站 4
码头 t
码头 t
x1
x2
x3
x4
x5
x6
x7
x8
x9
依题意：
目标函数 为 输送原油的总量 ；
约束条件有两类,
?一类是管道上的流量约束；
?另一类是每个中间泵站上的平衡约束, 即
中间泵站上的原油流入量和流出量相等
根据上述分析建立线性规划模型如下：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
???
??
??
??
0,,
12
11
5
7
6
4
8
9
10
..
91
9
8
7
6
5
4
3
2
1
967
8753
652
431
21
xx
x
x
x
x
x
x
x
x
x
xxx
xxxx
xxx
xxx
ts
xxM a x Z
?
1号泵站平衡约束
2号泵站平衡约束
3号泵站平衡约束
4号泵站平衡约束
相应弧上的约束
第四次作业：
P72 1-8,1-9,1-10
