x0
(2) (3)
可行解：满足（2）、（3）式的解x ( x1 , x2 , , xn )T 称为 (LP )的可行解。
可行域：D { x| Ax b , x 0}。
定理 线性规划问题的可行域D是凸集。 证明： 任取 x1, x2 D, 0 1。
A( x1 (1 )x2 ) Ax1 (1 )Ax2 b (1 )b
定理3 线性规划问题(LP )如果有最优解，则必有最优 的基本可行解。
定理4 线性规划问题(LP )的解 x 是基本可行解的 充分必要条件是 x 是 可行域 D的顶点。
五. 单纯形算法
1. 算法思路：从一个基本可行解开始，判断其是否为最优解。 是则算法结束。不是，则转换到另一个更好的基本可行解， 直到找到最优解，或者判断出不存在最优解。
2x1 u2 v2 3x3 x4 x5 3
s.t .
x1
3x1 2u2 2v2 2x4 4u2 4v2 3x3 x4
7 x7
6
x1 , x3 , x4 , x5 , x7 , u2 , v2 0
三. 图解法
例 2 求解线性规划 max z 4x1 3x2
s.t .
x2 1
且 x2 1时，x3 0。即x2变为基变量，x3变为非基变量。
x2 x1
1 2
2
3 1
3
x3 x3
1
3 2
3
x4 x4
25 z 11 3 x3 3 x4
令 x3
x4
0,则
x1 x2
2 1
基本可行解 x3 ( 2 ,1, 0 , 0 )T 。目标函数值 z3 11。
问题： (1) 如何得到第一个基本可行解？ (2)最优解的判定法则？
(3) 如何从一个基本可行解变换到另一个基本可行解？
2. 单纯形算法分析
例1 求解线性规划问题 (LP ) min s.t .
解：系数矩阵A 1 2 1 0。 2 1 0 1
Z 4x1 3x2
2x1x12
x2 x2
x3 x4
16
9 14
9
x2 ( 16 ,0,0,14 )T 是基本可行解。
9
9
可行解
基本可行解 基本解
基本解数量 Cnm
是否在基本可行解中一定存在最优解？
退化：称 非 零 分 量 个 数 小 于m的 基 本 解 为 退 化 的 基 本解 ；
否 则 称 非 退 化 的 基 本 解。 如 果( LP)的 所 有 基 本 解 都 是 非 退 化 的 ， 称( LP)是 非 退 化 的 。
4. 数学模型
min S 4 x1 5 x2 7 x3
s.t .
2
x1 x1
1.5x2 2x2 2
3x3 100 x3 150
xi 0, i 1,2,3
线性规划模型：
(1) 一组决策变量； (2)一个线性目标函数； (3)一组线性的约束条件。
线性规划模型( LP )的一般形式：
A
x1 x2 2 C
不存在最大值。
原问题无界。
x1
o
B
x1 x2 2
结果：
在顶点取到唯一最优解
线性规划问题的解
有最优解 无最优解
有无穷多最优解
解无界 可行域为空集
四. 线性规划解的概念和性 质
1. 线性规划解的概念
( LP )
min z cT x (1)
s.t .
Ax b
max 2 x1 3 x2 x3 3 x4
2x1 x2 3x3 x4 3
s.t .
3 x1 x1
2x2 4x2
2x4 3x3
7 x4
6
x1 , x3 , x4 0 , x2无约束
解： 令x2 u2 v2 ,则
min 2 x1 3u2 3v2 x3 3 x4
基本可行解：满足非负条件 的基本解称为基本可行解。
例 给定(LP)问题 min z x1 2x2 x3 2x4
s.t .
2xx1122xx22x23x3
4 x4 x4
8 2
x1 , x2 , x3 , x4 0
求此问题的一个基本解和一个基本可行解。
解： 系数矩阵A 1 2 1 4 。 2 2 2 1
解：分析同例 2。
x2
等值线：x1 2x2 z。
A
B
极大值点为线段AB 上的 任一点。
x1
o
C x1 2 x2 4
2 x1 x2 5
例4 求解线性规划 max s.t .
解：分析同例 2。
z 4 x1 3 x2
x1 x1
x2 x2
2 2
x1 , x2 0
x2
等值线：4x1 3x2 z。
1. 标准型
min
n
ci xi
i 1
a11 x1 a12 x2 a1n xn b1
s.t .
a21 x1
a22 x2
a2n xn
b2
am1 x1 am2 x2 amn xn bm
xi 0,i 1,2, ,n
记 c ( c1 , c2 , , cn )T , b ( b1 , b2 , , bm )T 0, x ( x1 , x2 , , xn )T , A (aij )mn 。则线性规划
x3 x4
0 0
x1 4
x1
5 2
x1
5 2
且
x1
5 2
时
，x
4
0。
即
x1变
为
基
变
量
，x
变
4
为
非
基
变量
。
x3 x4
4 5
x1 2x2 2x1 x2
x3
x1
3
2 5
2
3
2 1
2
x2 x2
1
2 1
2
x4 x4
z 10 x2 2x4
令
x2
x4
0,则
x1
x
3
5
产品
资源
A
B
C
资源总量
原材料 2
1.5
3
100
工时
1
2
2
150
解：1. 确定决策变量
设 A、B、C的产量分别为x1、x2、x3。
2. 确定目标函数
设总利润为S，则
S 4 x1 5 x2 7 x3 3. 确定约束条件
2 x1 1.5 x2 3 x3 100 x1 2x2 2x3 150 xi 0, i 1,2,3
是否为最优解？利用目标函数分析。
z 0 4x1 3x2 目标函数中非基变量x1 和 x2 的系数为负数，因此若x1 和 x2 的 取值可以增大为正数，则目标函数值就可以减小。
固定 x2 不变，考察x1 是否可以增大？
x3 x4
4 5
x1 2x2 2x1 x2
x3 x4
4 x1 5 2x1
标准型可记为
min cT x
s.t .
Ax b
x0
2. 化标准型 (1)目标函数：
原问题目标函数 : max cT x min cT x
(2)约束条件：
(i) 原问题条件： ai1 x1 ai2 x2 ain xn bi
ai1 x1
ai2 x2
ain xn xni 0
因为
Ax b
即
P1 x1 Pm xm Pm1 xm Pn xn b
所以
P1 x1 Pm xm b Pm1 xm Pn xn
令非基变量xm1 xn 0,解得 ( x1 , , xm )T B1b
基本解：取定线性规划问题的基B，令非基变量取零，求得基 变量的取值B1b, 称解(B1b , 0)T 为对应于基B的基本解。
2x1x12
x2 x2
4 5
x1 , x2 0
解 ：(1) 画出可行解的范围。
(2) 利用等值线平移的方法求极值点。 x2
以 z 为参数，则方程4x1 3x2 z
表示一族等值平行线。
A
B
极大值点为顶点 B。
x1
o
C x1 2 x2 4
2 x1 x2 5
例3 将例2中的目标函数改为z x1 2x2 。
b
所以x1 (1 )x2 D。即D是凸集。
顶点：设S为凸集，x S。如果不存在x1 x2 S，及0 1。 使 x x1 (1 )x2 ，则称 x为S的一个顶点。
x
x2
x1
基 : 设 A为m n的系数矩阵,秩为m。若B为A中m m阶的非 退化子阵，则称B为A的(或( LP )问题)一个基。
设基 B ( Pi1 , Pi2 , , Pim ) , 称 Pik (k 1, , m ) 为基向量，称 Pik 对应的变量 xik (k 1, , m )为基变量，不是基变量的变量称为 非基变量。
已知r( Amn ) m，不妨设 A的前m列向量线性无关，则可取 B ( P1 , P2 , , Pm )为基，则x1 , , xm 为基变量。
2. 线性规划解的性质
定理1 设x ( x1, x2 , , xn )T 是Ax b的一个解，则x是基本 解的充要条件是x的非零分量xi1 , xi2 , , xir 对应的A的列向量 pi1 , pi2 , , pir 线 性无 关 。 定理2 线性规划问题(LP )如果有可行解，则必有基本 可行解。
取 B 1 2
2 2
，则令非基变量x3
x4
0,得
2xx1122xx22
8 2
x1 x2
10
3 7
3
x1 ( 10 , 7 ,0,0 )T 是基本解，但不是基本可行解。 33