2．当一项任务量确定以后，研究如何统筹安排，才 能使完成任务耗费的资源量为最小。
第一节 线性规划及其数学模型
一、实例
【例1-1】某工厂在计划期内要安排生产 Ⅰ、Ⅱ两种产品，已知生产单位产品所 需的设备台时及A、B两种原材料的消耗， 如表1-2所示。
资源 产 品 设备 原材料 A 原材料 B
表1-1
线性规划及其数学模型 图解法和解的性质 单纯形法 单纯形法的进一步讨论 线性规划应用举例
本章学习目的和要求
通过本章的学习，要求学员掌握如何建立 线性规划模型，了解线性规划的图解法，深刻 理解单纯形法的解题思路，熟练掌握其运算步 骤，并能在实际问题中加以运用。
主要研究
1．已有一定数量的人力、物力、财力资源，研究如 何充分合理地使用才能使完成的任务量最大。
n
aij x j
(, )bi
j1
x
j
0
i 1, 2, , m j 1, 2, , n
向量形式：
矩阵和向量形式：
max(min)z CX
n
Pj x j (, )b
j1
x1, , xn 0
max(min)z CX
AX (, )b
X
0
式中：X=（x1，x2，…，xn）T C=（c1，c2，…，cn） b=（b1，b2，…，bm）T Pj=（a1j，a2j，…，amj）T A=（aij）m×n
化工厂1每天排放含有某种有害物质的工业污水2万 立方米，化工厂2每天排放的工业污水为1.4万立方米。 从化工厂1排出的污水流到化工厂2前，有20%可自然 净化。根据环保要求，河流中工业污水的含量应不 大于0.2%。因此两个工厂都需处理一部分工业污水。 化工厂1处理污水的成本是1000元/万立方米,化工厂2 处理污水的成本是800元/万立方米。问:
二、 线形规划问题的标准形式
n
max z j bi
j1
x
j
0
i 1, 2, , m j 1, 2, , n
称为线性规划问题的标准形式（其中常数b1， b2，…，bm≥0（若bi < 0 ，两边乘-1））。
起源
• 运筹学问题典型模式：给出一个目标 函数及一批约束条件, 要在约束条件 的限制下求目标函数的最优值。
• 当目标函数是线性的，而且约束条件 是线性的等式或不等式时, 称为线性 规划。当其中有非线性函数时则称为 非线性规划。当须求其整数解时,则 称为整数规划。
第一章 线性规划与单纯形法
第一节 第二节 第三节 第四节 第五节
（3）有一个需要优化的目标，它也是变量的线性函 数。
具备以上三个特点的数学模型称为线性规划 （Linear Programming，简记为LP）。
线性规划模型的一般形式：
max(min)z c1x1 c2 x2 cn xn （1-1）
a11x1 a12 x2 a21x1 a22 x2
4、（1-2）为技术约束，系数aij称为技术系数
5、满足全部约束条件的变量值（x1，…xn） 称为可行解，其集合称为可行域，记为R；
6、使目标函数取得最大（最小）值的可行解 （x1，…xn）称为最优解。
采用求和符号Σ，线性规划的一般 形式可以简写为：
n
max(min)z cj x j j 1
在满足环保要求的条件下，每厂各应处理多少工业污水， 使两个工厂处理工业污水的总费用最小。
得到本问题的数学模型为：
目标函数 min z 1000x1 800x2
约束条件
x1 1
0.8x1 x2 1.6
x1 2
x2 1.4
x1 , x2 0
【课堂练习】 某厂生产P、Q两种产品，主要消 耗A、B、C三种原料，已知单位产品的原料消 耗数量等资料如表所示。
运
决
筹
胜
帷 线性规划与单纯 千
幄 之
形法
里 之
中
外
起源
• 1939年苏联康托洛维奇（ H.B.Kahtopob ）、美国希奇柯克（ F.L.Hitchcock）提出
• 1947年，旦茨格，单纯形方法 • 1951年由库恩（H.W.Kuhn）和塔克
（A.W.Tucker），非线性规划 • 到了70年代，数学规划发展迅速
Ⅰ
Ⅱ
1
2
4
0
0
4
拥有量 8台时 16 kg 12 kg
每生产一件产品Ⅰ可获利2元，每生产 一件产品Ⅱ可获利3元，问应如何安排 计划使该工厂获利最多?
用数学关系式描述这个问题
•设 x1, x2分别表示计划生产 I,II产品的数量， 称它们为决策变量。 • 生产x1,x2的数量多少，受资源拥有量的限制, 这是约束条件。即x1 2x2 8;4x1 16;4x2 12
•生产的产品不能是负值 ,即x1, x2 0
• 如何安排生产，使利润最大,这是目标。
得到本问题的数学模型为:
目标函数 max z 2x1 3x2
x1 2x2 8
约束条件
:
4 x1
16 4x2 12
x1 ,x2 0
【例1-2】靠近某河流有两个化工厂，流经第一化工厂 的河流流量为每天500万立方米，在两个工厂之间有一 条流量为每天200万立方米的支流。
问题的数学模型为：
max z 2x1 5x2
x1 2x2 8
5x1
2 x2 4 x2
20 12
x1, x2 0
上述三个问题属于同一类型的决策优化问题，它 们具有下列共同特点：
（1）每个行动方案可用一组变量（x1，…，xn）的 值表示，这些变量一般取非负值；
（2）变量的变化要受某些限制，这些限制条件用一 些线性等式或不等式表示；
产品 单位消耗 原料
A B C 产品利润
P
1 5 0 2万元
Q
2 2 4 5万元
原料总量/吨
8 20 12
要求确定P、Q的产量，使利润最大。
产品 单位消耗 原料
A B C 产品利润
P
1 5 0 2万元
Q
原料总量/吨
2
8
2
20
4
12
5万元
解：设P、Q的产量分别为x1，x2，即决策变量 目标函数？ 约束条件？
a1n xn (, )b1 a2n xn (, )b2
（1-2）
am1x1 am2 x2 amn xn (, )bm
x1, x2 , , xn 0
（1-3）
1、变量x1，x2，…，xn称为决策变量
2、目标函数中变量系数cj称为价值系数
3、bi称为右端常数，约束条件（1-3）称为非 负约束