解得:
x1 12, x2 0, x3 11, x4 5, x5 0, x6 8, x7 0. Z0 36
例4 某工厂要做100套钢架,每套用长为2.9m,2.1m, 和1.5m的圆钢各一根,已知原料每根长7.4m, 问应如何下料,可使所用原料最省.
分析: 每根原料做一套钢架, 下角料：0.9m 用套裁方式
1.1.1 线性规划模型 一、 线性规划问题举例
例1 （生产安排问题）假定某工厂生产甲、乙、丙三种产品， 每种产品都要经过三种不同的工序加工。每一件产品所需要 的加工时间（分钟）和每天对各道工序的加工能力（每天多 少分钟）以及销售各种产品的单位利润如下表所示：
工序 每件产品加工时间（分钟）
甲产品 乙产品 丙产品
星期五 售货员人数要求:
x1 x2 x3 x6 x7 31
星期六 售货员人数要求:
数学时模间型:
所需售货员人数
求 m星in期日Z 星期一
x1
x2
28人
15人
x7
x星1 期二x2 x3 x4 24人x5 28
x星2期三x3
星期四
x4
x525人x6 19人
15
x星3期五x4 x5 x631人x7 24
量如下表所示。
车间
每班进料数（克） 每班产量（个数） 第1种原材料 第2种原材料 A零件 B零件
甲
8
6
7
5
乙
5
9
6
9
丙
3
8
8
4
问这三个车间各应开多少班才能使这种产品的配套数达到最大
解：设x1，x2，x3分别是甲、乙、丙三个车间所开的生产班数
z 产品的配套数
约束条件为： 8x1 5x2 3x3 100 ,6x1 9x2 8x3 200 x1 0，x2 0，x3 0
解 设x1为周一开始休息的人数 ，x2为周二开始休息的人数 ，
x6为周六开始休息的人数 ，x7为周日开始休息的人数 ， Z表示商场的售货员人数 x1 x2 x7 求 min Z x1 x2 x7
约束条件 : xi为星期i日开始休息的人数 ,i 1,2,,7
星期日 售货员人数要求:
最优下料方案： 按方案1下料30根，方案2下料10根， 方案4下料50根， 共需原料90根。
例5 (产品配套问题）假定一个工厂的甲、乙、丙三个车间生产
同一个产品，每件产品包括4个A零件，和3个B零件。这两种
零件由两种不同的原材料制成，而这两种原材料的现有数额
分别为100克和200克。每个生产班的原材料需要量和零件产
x1 x2 x3 x4 x5 28
x2
x3
x4
x5
x6
15
x3 x4 x5 x6 x7 24
s.t
x1 x1
x4 x2
x5 x5
x6 x6
x7 x7
25 19
x1
x2
x3
x6
x7
31
x1 x2 x3 x4 x7 28
xi 0,i 1,2,,7
维生素 单位 甲
乙
丙
丁
每人每天 最低需要量
A
毫克 1000 1500 1750 3250
4000
B
毫克 0.6 0.27 0.68 0.3
1
C
毫克 17.5 7.5
0
30
30
单价（元）
0.8 0.5 0.9 1.5
现在我们希望每天得到的维生素不少于所规定的最低需要 量，问应该如何搭配各种食品才能使所花的费用最少？
下料方案：下料数
长度(根)
2.9m
方案1 方案2 方案3 方案4 方案5
1
2
0
1
0
2.1m 0
0
2
211.5m 31203
合计
7.4m 7.3m 7.2m 7.1m 6.6
下角料 0m 0.1m 0.2m 0.3m 0.8m
下料方案：下料数
长度(根)
方案1 方案2 方案3 方案4 方案5
2.9m 1
5、劳动力安排： 某单位由于工作需要，在不同时间段需要不同 数量的劳动力，在每个劳动力工作日连续工作 8小时的规定下，如何安排劳动力，才能用最少 的劳动力来满足工作的需要。
6、运输问题： 一个公司有若干个 生产单位与销售单位，根据 各生产单位的产量及销售单位的情况，如何制定 调运方案，将产品运到各销售单位而总的运费最少。
s.t
2x3 3x1
2x4 x2
2
x5 x3
100 3x5
100
x1 0, x2 0, x3 0, x4 0, x5 0.
例4 某工厂要做100套钢架,每套用长为2.9m,2.1m, 和1.5m的圆钢各一根,已知原料每根长7.4m, 问应如何下料,可使所用原料最省.
下料方案：下料数
第一章 线性规划 （Linear Programming )
• 运筹学的一个重要分枝 • 研究较早 • 发展较快 • 理论较成熟 • 应用极为广泛
简记为LP
典型的线性规划的在经济管理上的应用举例:
1、合理利用线材问题:
现有一批长度一定的钢管,由于生产的需要, 要求截出不同规格的钢管若干。试问应如何 下料，既满足了生产的需要，又使得使用的 原材料钢管的数量最少。
x1，x2，x3分别是甲、乙、丙三个车间所开的生产班数
z 产品的配套数 车间
目标函数：
每班进料数（克）
每班产量（个数）
第1种原材料 第2种原材料 A零件 B零件
三个车间共生产A零件： 甲
8
乙
5
7 x1 6x2 8x3
丙
3
6
7
5
9
6
9
8
8
4
三个车间共生产B零件
5x1 9x2 4x3
则z min 7x1 6x2 8x3 4
2
0
1
0
2.1m 0
0
2
2
1
1.5m 3
1
2
0
3
合计
7.4m 7.3m 7.2m 7.1m 6.6
下角料 0m 0.1m 0.2m 0.3m 0.8m
解：设xi为按i第种方案下料的原料根 数（i 1,2,3,4,5) Z表示总用料数
数学模型：求 min Z x1 x2 x3 x4 x5
x1 2x2 x4 100
线性
约束条 件
对第三道工序，有 x1 4x2 420
且有 x1 0，x2 0，x3 0 非负性约束条件
问题归结为：求 x1，x2，x3，使之满足以上四个约束条件，
并使z 3x1 2x2 5x3的值最大
例2 （营养搭配问题） 如果有甲、乙、丙、丁四种食品，都含 有不同成分的维生素，其含量和单价如下表所示
解：x1 每天采购甲食品的数量，x2 每天采购乙食品的数量 x3 每天采购丙食品的数量，x4 每天采购丁食品的数量
M 每天采购食品的费用
则有M 0.8x1 0.5x2 0.9x3 1.5x4
决策变量：
x1 每天采购甲食品的数量， x2 每天采购乙食品的数维量生素 单位 甲
乙
丙
a11x1 a12 x2 a1n xn (或 ，或 ）b1
s.t
a21 x1
a22
x2
a2n xn
(或
，或 ）b2
am1x1 am2 x2 amn xn (或 ，或 ）bm
x1 , x2 , xn 0
四、线性规划应用举例
例3 福安商场是个中型的百货商场，它对售货人员的 需求经过统计分析如下所示：
并使M
0.8x1
0.5x2
0.9x3
1.5
x
的值最小。
4
二、线性规划模型的建立
1、建模的一般步骤：
步骤一：确定决策变量 即用变量取不同的值来表示可供选择的各种不同方案
步骤二：建立目标函数 即找到目标值与决策变量的数量关系
步骤三：确定约束条件 即决策变量所受到的外界条件的制约。 约束条件一般为决策变量的等式或不等式
约束条件：1000 x1 1500 x2 1750 x3 3250 x4 4000 0.6x1 0.27 x2 0.68 x3 0.3x4 1
线性
17.5x1 7.5x2
30 x4 30
x1 0，x2 0，x3 0, x4 0
问题归结为：求 x1，x2，x3，x4 , 使之满足以上约束条件，
a22
x2
a2n xn
(或
，或 ）b2
am1x1 am2 x2 amn xn (或 ，或 ）bm
x1 , x2 , xn 0
约束方程
非负约束
其中aij , bi , c j (i 1,2,, m; j 1,2,, n) 为已知常数
决策变量
三、线性规划求解：
计算机应 用软件
max（或min ）z c1 x1 c2 x2 cn xn
x1 x2 x3 x4 x5 28
星期一 售货员人数要求:
x2 x3 x4 x5 x6 15
星期二 售货员人数要求:
x3 x4 x5 x6 x7 24
星期三 售货员人数要求:
x1 x4 x5 x6 x7 25
星期四 售货员人数要求:
x1 x2 x5 x6 x7 19
要求：目标函数与约束条件均是线性的， 且目标函数只能是一个。
2、线性规划模型的一般形式：
max（或min ）z c1 x1 c2 x2 cn xn
目标函数
maximum minimum
subject to
a11x1 a12 x2 a1n xn (或 ，或 ）b1
s.t