线性规划的一般形式为：
max(min) z c1x1 c2 x2 L cn xn
（1-1）
a11x1 a12 x2 L a1n xn (, )b1
a21
x1
a22
x2
L a2n xn LLLLL
(,
)b2
am1
x1
am2 x2
L
amn xn (, )bm
x1, x2 ,L , xn 0
当z取定值时，方程z=2x1+5x2或x2=－ 2/5x1+z/5表示一条斜率为－2/5的直线 l ， 称为 z的等值线，它在x2轴上的截距为z/5。当l向右 上方平行移动且保持与R有共同部分时，z值不
断上升，由于l的斜率为－2/5，因此当l向右上
方平移的过程中，与R最后的公共点是Q3，z在
x
21
x22
x23
40
x11 x21
x12
x22
20 25
x13
x23
18
xij 0 i 1, 2 j 1, 2, 3
上述三个问题属于同一类型的决策优化问题，它 们具有下列共同特点：
（1）每个行动方案可用一组变量（x1，…，xn）的 值表示，这些变量一般取非负值；
（2）变量的变化要受某些限制，这些限制条件用一 些线性等式或不等式表示；
j1
max(min)z CX AX (, )b
x1 ,L , xn 0
X
0
式中：X=（x1，x2，…，xn）T
C=（c1，c2，…，cn）
b=（b1，b2，…，bm）T
A=（aij）m×n
Pj=（a1j，a2j，…，amj）T
二、图解法
当决策变量个数n=2时，LP问题可以通过在 平面上作图的方法求解，称为图解法。
（1-2） （1-3）
变量x1，x2，…，xn称为决策变量，目标函数中变量系数 cj，称为价值系数，bi称为右端常数，约束条件（1-3）称为非负 约束，（1-2）称为技术约束，系数aij称为技术系数。满足全部约 束条件的变量值（x1，…xn）称为可行解，可行解的集合称为可 行域，记为R；使目标函数取得最大（最小）值的可行解
要消耗A、B、C三种原料，已知单位产品的 原料消耗数量等资料如表1-1所示。
产品ห้องสมุดไป่ตู้
P
Q
原料总量/吨
单位消耗
原料
A
1
2
8
B
5
2
20
C
0
4
12
产品单价
2万元
5万元
解：设P、Q的产量分别为x1，x2，则问题的模
型为
m a x z 2 x1 5 x 2
x1 2 x 2 8
5
x1
2 x2 20 4 x2 12
1．已有一定数量的人力、物力、财力资源，研 究如何充分合理地使用才能使完成的任务量最 大。（如：利润、产值等最大。 maximum）
2．当一项任务量确定以后，研究如何统筹安排， 才能使完成任务耗费的资源量为最小。（如： 成本最小。minimum）
第一节 线性规划的基本概念
一、线性规划的数学模型 【例1-1】 某厂生产P、Q两种产品，主
（x1，…xn）称为最优解。
采用求和符号Σ，线性规划的一般形式可以 简写为：
n
max(min)z cj xj j1
n
aij xj
(,)bi
j1
xj 0
i 1,2,L ,m j 1,2,L , n
用向量形式可表示为： 用矩阵和向量形式
max(min)z CX
表示为：
n
Pjx j (, )b
（1）确定问题的可行域R。 x 1 2 x 2 8
x2 5
4 3 Q4
l2 Q3
5
x1
2 x2 4 x2
20 12
l3 x 1 , x 2 0
2
Q2
1 0
123
Q1 456
l1 x1
图1-1
可行域R是凸多角形OQ1Q2Q3Q4
（2）分析目标函数Z的等值线平行移动与 Z值的关系，确定最优解的位置。
x 1 , x 2 0
【例1-2】 某公司打算利用甲、乙、丙3种原料配置一 种新型保健饮料，已知每千克原料中两种主要保健成 分A，B的含量及原料单价如表1-2所示。
含量
原料
甲
乙
丙
成分
A
20
40
0
B
10
0
20
原料单价（元/千克）
2
2
3
产品质量标准规定每千克饮料中，营养成分A，B 的含量不低于10个与8个单位。如何制定饮料配方， 既满足质量标准又使成本最低？
第一章 线性规划与单纯形法
第一节 第二节 第三节 第四节 第五节
线性规划的基本概念 线性规划的标准形式和解的性质 单纯形法 人工变量法 线性规划应用举例
本章学习目的和要求
通过本章的学习，要求学生掌握线性 规划的图解法，深刻理解单纯形法的解题 思路，熟练掌握其运算步骤，并能在实际 问题中加以运用。
主要研究目的
（3）有一个需要优化的目标，它也是变量的线性函 数。
具备以上三个特点的数学模型称为线性规划 （Linear Programming，简记为LP）。
实际问题中线性的含义
一是严格的比例性，如生产某产品 对资源的消耗量和可获取的利润，同其 生产数量严格成比例。
二是可叠加性，如生产多种产品时 对某项资源的消耗量应等于各产品对该 项资源的消耗量之和。
含量
原料
甲
乙
丙
成分
A
20
40
0
B
10
0
20
原料单价（元/千克）
2
2
3
解：设每千克饮料中原料甲，乙，丙的投入量 分为x1，x2，x3千克，则问题的模型为：
min z 2x1 2x2 3x2
20x1 40x2
10
10 x1
20x3 8
x1
,
x2 ,
x3
0
【例1-3】 A1，A2是两个粮库，每月分别可调出粮 食30吨与40吨，三个粮店B1，B2，B3每月的需求量 分别为20吨，25吨与18吨。粮库与粮店之间每吨粮 食的运费如下表1-3所示（单位：元/吨）。
运费 粮库
粮店
A1 A2
B1
B2
B3
2
3
5
4
6
3
要求安排粮食调运方案，在满足需求的前提下， 使总运费最低。
解：设从粮库Ai到粮店Bj的调运量为xij，i=1，2， j=1，2，3，则问题的模型为：
min z 2 x11 3 x12 5 x13 4 x21 6 x22 3 x23
x11 x12 x13 30
图解法求解的目的： 1.判别线性规划问题的求解结局。 2.在存在最优解的条件下，把问题的最优解找出来。
【例1-4】 求下列问题的最优解。
m ax z 2 x1 5 x2
x1 2 x2 8
5
x
1
2 x2 4 x2
20 12
x 1 , x 2 0
m ax z 2 x1 5 x2