文档介绍：1
线性规划问题解的概念(从标准型式引入)
i =1,2,…,m
xj 0 j =1,2,…,n
max z =CX ()
AX = b ()
X 0 ()
可行解满足约束条件()、()的解
X=( x1,x2,···,xn)T;
最优解使目标函数()达到最大值的可行解;
基 A中的m× m 阶非奇异矩阵B ;
(意味着A的秩为m,|B | ≠ 0,B 的各列线性无关)
2
基 A中的m × m 阶非奇异矩阵B ;
(意味着A的秩为m,|B | ≠ 0,B 的各列线性无关)
· 基向量 B中的列向量;
· 基变量 B中的列向量对应的变量;
· 非基变量非B中的列向量对应的变量;
例如,若A的前m列线性无关,则
a11 … a12 … a1m
a21 … a22 … a2m
……
am1 … am2 …amm
=( P1,P2,…,Pm )
B =
是个基。
P1,P2,…,Pm是基向量;
x1,x2,…,xm 是基变量;
xm+1,…,xn 是非基变量;
若Am×n,m<n,则至多有个基,每个基有m个基变量,n- m 个非基变量。
3
· 基解对应每一个基B,令所有非基变量为零,由() 约束方程组求得的解X ;
约束方程组()中,有m 个方程n 个变量,m<n,有无穷多解,若前m个系数向量线性无关,令xm+1=…=xn =0,则可求出XB =( x1,x2,…,xm)T,则X=( x1,x2,…,xm,0,…,0)T就是一个基解。
至多有个基解,基解的非零分量至多m个,非零分量个数小于m 的基解为退化解。
基可行解满足非负条件()的基解;
同样至多有个基可行解,基可行解至多有m个正分量。
· 可行基对应于基可行解的基;
· 基最优解使目标函数达到最大值的基可行解。
:
4
上述解的概念中基解和基可行解最为重要,各种解的关系粗略地可用下图表示:
非可行解
可行解
基解
基
可
行
解
最优解
5
如例1,max z = 2x1 + 3x2
.
x1 + 2 x2 + x3 = 8
4 x1 + x4 =16
4 x2 +x5 =12
x1,x2,x3,x4,x5 0
以(P3、P4、P5)作为基,令x1 = x2 =0,得到 X=(0,0,8,16,12)T为一个基可行解,对应图中O点;
2 x2 = 8
x4 =16
4 x2 +x5 =12
以(P1、P2、P5)为基,令x3 = x4 =0,可得X=(4,2,0,0,4)T是基最优解,对应图中Q2点。
x1
x2
O
4
Q2(4,2)
Q1
Q3
Q4
3
A
以(P2、P4、P5)作为基,令x1 = x3 =0,由
得X=(0,4,0,16,-4)T是个基解,不是基可行解,对应图中A点;
6
§2 线性规划问题的几何意义
本节重点:
凸组合的概念
凸集的概念
线性规划基本定理
7
基本概念
凸组合
设,若存在,0 1
,且,使
则称X 为的凸组合。
X1
X2
X
2
1
二维空间
两点连线上的任何一点都是这两点的凸组合
8
(a)
(b)
(c)
(d)
(e)
凸集
9
(a)
(b)
(c)
(d)
(e)
图中红粗线和红点是顶点。
10