2020/11/23
广东工业大学管理学院
10
配料问题：由若干种不同价格、不同成分含量的原料，用 不同的配比混合调配出一些不同规格的产品，在原料的供 应量限制和保证产品成分含量的前提下，如何进行配料来 获取最大利润或使总成本最低。
投资问题：如何从不同的投资项目中选出一个投资方案， 使得投资的回报达到最大。
甲
乙
丙
A B C 加工费
x11 60%以上 x12 20%以下 x13 0.50
x21 15%以上 x22 60%以下 x23 0.40
x31 x32 50%以下 x33 0.30
售价
3.40
2.85
2.25
原料成本 2.00 1.50 1.00
限制用量 2000 2500 1200
设该厂每月生产甲品牌糖果(x11 x12 x13)千克，其中用原料A x11千克，用原料B x12千克，用原料C x13千克; 生产乙品牌糖果(x21 x22 x23)千克，其中用原料A x21千克，用原料B x22千克，用原料C x23千克; 生产丙品牌糖果(x31 x32 x33)千克，其中用原料A x31千克，用原料B x32千克，用原料C x33千克。
设一共植了y棵树，男生中有x1人挖坑, x2人栽树, x3人浇水； 女生中有x4人挖坑, x5人栽树, x6人浇水.
max z y
20x1 10x4 y 0 30x2 20x5 y 0
s.t.
25x3
x1
x2
15x6 x3
y 30
0
x4
x5
x6
20
x1, x2 , x3 , x4 , x5 , x6 , y 0
松弛变量
xs 2 (2x1 3x2 x3)
2020/11/23
广东工业大学管理学院
24
（b）对于约束条件是“≥”型的不等式
3x1 2x2 4x3 3
在约束条件左端减去一个
非负的变量xs，则它化为
等价的等式约束条件 。
3x1 2x2 4x3 xs 3
变量xs实际上是原式左端减去右端的差，即 ：
am1x1+am2x2+…+amnxn≤(≥,=)bm x1,x2,…,xn ≥0
cj—价值系数 bi—资源常数 aij—工艺系数
技术系数
简化形式
n
max(min) z c j x j
s.t.
n
j 1
aijxj (, )bi (i 1,, m)
j1
xj 0(j 1,n)
2020/11/23
2020/11/23
广东工业大学管理学院
11
2.2 线性规划的图解法
➢可行解：我们将满足线性规划问题的所有约束 条件的变量的一组取值称为线性规划问题的一个 可行解。 ➢可行域：我们将可行解的集合称为可行域。 ➢最优解：使得目标函数取最优值的可行解。 ➢最优值：将最优解代入目标函数而得到的值。
2020/11/23
劳动力安排：某单位由于工作需要，在不同的时间段需要 不同数量的工作人员，在一定的安排规则：比如每个工作 人员在连续做5个工作日后接连休息两天下，如何安排工 作人员才能用最少的工作人员来满足工作的需求？
运输问题：一家公司有若干个生产单位和销售单位，产品 由各生产单位运往各销售单位的成本有差异，如何根据各 生产单位的产量和各销售单位的销售需要量制定一个最佳 的运输方案，使产品运往各销售单位的总运输费用最低？
广东工业大学管理学院
20
用向量、矩阵形式表示线性规划的数学模型
max(min) z CX
s.t.
n
Pjx
j1
X0
j
(, )b
C (c1, c2 ,, cn )
x1
X
x
2
x
n
b1
a1j
b
b2
pj
a 2j
b
m
a
mj
max(min) z CX
s.t.
广东工业大学管理学院
12
图解法步骤: ➢建立平面直角坐标系 ➢图示约束条件,求可行域 ➢图示目标函数 ➢求最优解
2020/11/23
广东工业大学管理学院
13
例: max z=x1+3x2
x1+ x2≤6 st. -x1+2x2≤8
x1 ≥0, x2≥0
x2 6
4
最优解 X*= (4/3, 14/3) z* = 46/3
如果记xj是计划期第j种产品的产量(j=1,2, … ,n),则一般的生产 计划问题的数学模型具有如下形式:
max z = c1x1+c2x2+…+cnxn a11x1+a12x2 +… + a1nxn ≤b1 a21x1+a22x2+… + a2nxn ≤b2
st. ……
am1x1+am2x2+…+amnxn≤bm x1,x2,…,xn ≥0
x2 4 3x2 9
x1, x2 0
2x1+x2=4
D C
x1+2x2=5 B
4x1+3x2=9
O
A
x1
2020/11/23
广东工业大学管理学院
16
3、无界解
指线性规划问题有可行解，但 是在可行域，目标函数值是无 界的，因而达不到有限最优值。 因此线性规划问题不存在最优 解。
x2 -3x1+2x2=1
剩余变量
xs 3x1 2x2 4x3 3
无论是松弛变量还是剩余变量在决策中都不产生实 际价值，因此它们在目标函数中的系数都应该为零。 有时也将松弛变量和剩余变量统称为松弛变量
s.t.
3xx2 12xx23
100 100
x1 , x2 , x3 0
2020/11/23
广东工业大学管理学院
6
2.10. 一家酒店24小时都需要安排服务员上班，在各时间段 中所需要的服务员数量见表
班次
1 x1
2 x2 3 x3 4 x4 5 x5 6 x6
时间 6:00-10:00 10:00-14:00 14:00-18:00 18:00-22:00 22:00-2:00 2:00-6:00
max z 2x1 3x2
3x1 2x2 1
x1
2x2
1
x1, x2 0
x1-2x2=1
O
x1
2020/11/23
广东工业大学管理学院
17
4、无可行解
指找不到一组变量能满足线性规划的所有约束条件的情况，
也就是线性规划问题不存在可行解，或者说可行域是空集。
例如线性规划问题：
x2
max z 2x1 x2
所需人数 60 70 60 50 20 30
设服务员分别在各时间区段一开始时上班，并连续工作八 小时，问该酒店至少配备多少名服务员。列出此问题的线 性规划模型。
2020/11/23
广东工业大学管理学院
7
min w x1 x2 x3 x4 x5 x6
x1 x6 ≥ 60
x1
x2
≥
70
x2
x3
≥
60
s.t.x3 x4 ≥ 50
x4
x5
≥
20
x5 x6 ≥ 30
x1
,
x2 ,
x3 ,
x4 ,
x5 ,
x6
0
2020/11/23
广东工业大学管理学院
8
2.11 某班有男生30人，女生20人，周日去植树。根据经验，一 天男生平均每人挖坑20个，或栽树30棵，或给25棵树浇水；女 生平均每人挖坑10个，或栽树20棵，或给15棵树浇水。问应怎 样安排，才能使植树（包括挖坑、栽树、浇水）最多？
约束条件
x1+2x2 ≤5 s.t. 2x1+ x2 ≤4
4x1+3x2 ≤9
x1 ,x2 ≥0
2020/11/23
广东工业大学管理学院
3
例1中的问题常称为生产计划问题或产品组合（product mix） 问题。一般的生产计划问题可以表述为：设用m种资源，生 产n种不同的产品。已知第 i种资源在一给定的计划期最多可 以使用bi个单位，每生产一个单位的产品 j 需要第 i 种资源 aij 个单位，并且产品 j 的单位利润为Cj 元。问在该计划期应如 何组织生产才能获得最大利润？
－x1+ 2x2=8
可行域
-8 0
目标函数等值线
2020/11/23
广东工业大学管理学院
6 x1
x1+ x2=6
14
max z 3x1 2x2
x1 2x2 5
s.
t.42
x1 x1
x2 4 3x2 9
x1, x2 0
x1 3 2 , x2 1
x2
2x1+x2=4 l* D
C
x1+2x2=5
等价于: max w 2x1 3x2 x3
2020/11/23
广东工业大学管理学院
23
2. 约束条件为不等式
（a）对于约束条件是“≤”的不等式
例如： 2x1 3x2 x3 2 约束条件左端加上一个非 负的变量xs(松弛变量)
等价为： 2x1 3x2 x3 xs 2
变量xs其实就是原式右端与左端的差，即:
2020/11/23
广东工业大学管理学院
9
2.12 某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、 乙、丙。已知各种牌号糖果中A、B、C三种原料的含量要求、 各种原料的单位成本、各种原料每月的限制用量、三种牌号 糖果的单位加工费及售价如表所示。问该厂每月生产这三种 牌号糖果各多少千克，才能使该厂获利最大？