解：将一个实际问题转化为线性规划模型有以下
几个步骤：
1．确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量 2．确定目标函数：家具厂的目标是销售收入最大 max z=50x1+30x2 3．确定约束条件： 4x1+3x2 120（木工工时限制） 2x1+x2 50 （油漆工工时限制）
C (c1 , c2 , , cn )
x1 x2 X , x n
a1 j a2 j Pj , a nj
b1 b2 b b m
一般情况，决策变量只取正值（非负值）
x1 0, x2 0
解：将一个实际问题转化为线性规划模型有以下
几个步骤：
1．确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量 2．确定目标函数：家具厂的目标是销售收入最大 max z=50x1+30x2 3．确定约束条件： 4x1+3x2120（木工工时限制） 2x1+x2 50 （油漆工工时限制） 4．变量取值限制：
21 1 22 2 2n 1n . 2 . . s .t . am1x1+am2 x2 + … +amn x1n≤ (或=, ≥) bm … x 1 , x 2 , , x n≥ 0
非负约束
约 束 条 件
max (或min) z = c1x1 + c2 x2 + … + c n x n
使不等式成为等式的非负变量
LP问题的标准形式
目标函数为收益最大, 目标函数为求支出最小, 如利润最大 如成本最小
max

Z cj xj
j 1
ij
n
a
j 1
n
x j b i (i 1, , m)
xj 0
( j 1,, n)
j 1 n ai j x j b i (i 1, , m) s.t. j 1 x j 0 ( j 1, , n)
a11x1+a12 x2 + … +a1n x1n≤ (或=, ≥) b1 a x +a x + … +a x ≤ (或=, ≥) b 2 21 1 22 2 . 2n 1n s .t . . . am1x1+am2 x2 + … +am n x1n≤ (或=, ≥) b m x1 , x 2 , … , x n≥ 0
其他典型问题：
•合理下料问题
其他典型问题：
•合理下料问题
•运输问题
其他典型问题：
•合理下料问题
•运输问题
•生产的组织与计划问题
其他典型问题：
•合理下料问题
•运输问题
•生产的组织与计划问题
•投资证券组合问题
其他典型问题：
•合理下料问题
•运输问题
•生产的组织与计划问题
•投资证券组合问题 •分派问题
第一部分
线性规划
（Linear Programming)
线性规划（概论）
线性规划（Linear Programming) 创始人： 1947年美国人G.B.丹齐克（Dantzing） 1951年提出单纯形算法（Simpler） 1963年Dantzing写成“Linear Programming and Extension” 1979年苏联的Khachian提出“椭球法”
解：将一个实际问题转化为线性规划模型有以下
几个步骤：
解：将一个实际问题转化为线性规划模型有以下
几个步骤：
1．确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量
解： 将一个实际问题转化为线性规划模型有以下几
个步骤：
1．确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量 2．确定目标函数：家具厂的目标是销售收入最大 max z=50x1+30x2
限制达到目标的条件是什么，即建立约束 条件。
线性规划问题的一般形式 目标函数
max (或min) Z = c1x1 + c2 x2 + … + c n x n
条件约束 a11x1+a12 x2 + … +a1n x1n≤ (或=, ≥) b1 a x +a x + … +a x ≤ (或=, ≥) b
简写形式
n
max (或 min) z c j x j
j 1
n
c i j x j (或 , ) b i s.t . j 1 xj 0
( i 1, , m ) ( j 1, , n)
max (或min)
n
Z C X
LP向量形式
Pj x j (或 , ) b s .t . j 1 X 0
min
Z cj xj
n
求最大目标函数为LP的标准形式（规定） 因为它们可以很方便地相互转换 1 目标函数为求得最大 2 约束条件全为等式 3 bi 0 (i 1, , m), b 非负
线性规划标准型的矩阵形式(3)：
Max S =
s.t.
CX
AX=b X0
转化为LP问题的标准形式的措施
解：将一个实际问题转化为线性规划模型有以下
几个步骤：
1．确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量 2．确定目标函数：家具厂的目标是销售收入最大 max z=50x1+30x2 3．确定约束条件： 4x1+3x2 120 （木工工时限制） 2x1+x2 50 （油漆工工时限制） 4．变量取值限制：
怎样辨别一个模型是线性规划模型？
其特征是：
1．解决问题的目标函数是多个决策变量的线性函数，
通常是求最大值或 最小值；
2．解决问题的约束条件是一组多个决策变量的线性
不等式或等式。
2 营养配餐问题
假定一个成年人每需要从食物中获 得3000千卡的热量、55克蛋白质和800 毫克的钙。如果市场上只有四种食品 可供选择，它们每千克所含的热量和 营养成分和市场价格见下表。问如何 选择才能在满足营养的前提下使购买 食品的费用最小？
线性规划基本概念
生产计划问题
如何合理使用有限的人力，物力 和资金，使得收到最好的经济效益。 如何合理使用有限的人力，物力 和资金，以达到最经济的方式，完 成生产计划的要求。
1 生产计划问题（资源利用问题） 胜利家具厂生产桌子和椅子两种家 具。桌子售价50元/个，椅子销售价格30 元/个，生产桌子和椅子要求需要木工和 油漆工两种工种。生产一个桌子需要木 工 4 小时，油漆工 2 小时。生产一个椅子 需要木工 3 小时，油漆工 1小时。该厂每 个月可用木工工时为120小时，油漆工工 时为 50 小时。问该厂如何组织生产才能 使每月的销售收入最大？
松弛变量
max Z = 2 x1 + 3 x2 + 0 x3 + 0 x4 + 0 x5
2 x1 + 2 x2 + x 3 = 12 4 x1 + x4 = 16 s .t . 5 x2 + x5 = 15 x1 , x 2 , x3 , x4 , x5 ≥ 0
决策变量 松弛变量
x1 max Z (2,3) x 2
LP向量形式
2 x1 P 4 , X , 1 x 2 0
2 P2 0 , 5
12 b 16 15
一般情况，决策变量只取正值（非负值）
x1 0, x2 0
数学模型
max S=50x1+30x2 s.t. 4x1+3x2 120 2x1+ x2 50 x1,x2 0 线性规划数学模型三要素： 决策变量、约束条件、目标函数
线性规划的数学模型由 决策变量 Decision variables 目标函数 Objective function 约束条件 Constraints 构成。称为三个要素。
其他典型问题：
•合理下料问题
•运输问题
•生产的组织与计划问题
•投资证券组合问题 •分派问题 •生产工艺优化问题
小结：建立线性规划数学模型
建立数学模型是学习线性规划的第一步 也是关键的一步。 建立正确的数学模型要掌握3个要素：
研究的问题是求什么，即设置决策变量；
问题要达到的目标是什么，即建立目标函 数，目标函数一定是决策变量的线性函数并 且求最大值或求最小值；
C ( 2, 3 )
2 2 12 4 x1 0 x2 16 0 5 15 s.t. x1 0 x2 0
n
cj xj Z ' Z
max Z c j x j
j 1
n
例a
max minZZ ’ = =xx ’-+22 xx -3 +x3 + 11 22 3’x 3 3 x 3 ’ + 0 x 4+ 0 x 5 - 2 x1’ + x2 + x (x = 9 3 3’– x3’’) + x4 ≤ - 3 x ’ + x +2 (x x3 ’– x3’’) - x5 = ≥ 4 1 2 s .t . 3x1 - 2x2 + -3 x (x = -6 ’+ =+ 3 3’– x3’’) x1 ≤ ’ ≥ 0 , x2 ≥ 0, x3 无约束 x3’, x3’’ ≥0 -1 × Z 无约束 max -1×Z =-1× (x1 + 2x2 +3 x3 ) 令 x3 = x 3’– x3’’ 且 x3’, x3’’ ≥0 x1’ = – x1