初中 信息和信息技术课件.ppt

初中 信息和信息技术课件.ppt线性规划的单纯形法 The Simplex Method
1
§ 线性规划模型的几种表示

max z = c1 x1 + c2 x2 + …+ cn xn
. a11 x1 + … a1j xj+ …+ a1n xn = b1
a21 x1 + … a2j xj+ …+ a2n xn = b2
……
am1 x1 + … amj xj + …+ amn xn = bm
x1 , …, xj ,…,xn ≥ 0
2

其中,
3

其中,
4
§ 线性规划解的概念
设线性规划为
A为m × n矩阵, n > m, Rank( A) = m (A为行满秩矩阵)
1. 可行解(Feasible solution):满足条件(2)、(3)的X;
2. 最优解(Optimal solution):满足条件(1)的可行解;
5
3. 基( Basis )
取B为A中的m × m子矩阵,Rank (B) = m,则称B为线性
规划问题的一个基。
取
B = (p1 , p2 , ··· , pm )
pj = (a1j , a2j , ··· , amj )T
则称变量x1 , x2 ,···, xm为基变量(basic variable ),其它的变量
为非基变量(non-basic variable)。
6
(Basic solution)
设B =(p1 , p2 , ···, pm )为线性规划问题的一个基,XB为基变
量;N 为非基,XN为非基变量,则
BXB + NXN=b
若令XN=0, 则有

基本解:

基本解的个数
7
(Basic feasible solution )
满足(3)式要求的基本解。
如右图所示,各边交点O,Q1,Q2,Q3,Q4均为基本可行解;而
其延长线的交点Q5为基本解,但不是基本可行解。
O(0,0)
Q1(4,0)
Q2(4,2)
Q4(0,3)
Q3(2,3)
Q5(4,3)
6. 可行基(Feasible basis)
基本可行解对应的基为可行基。
8
可行解
基本可行解
非可行解
基本解
各类解之间的关系图
9
§ 线性规划问题的几何意义
基本概念
1、凸集(convex set):
设K为En(n维欧式空间)的一点集,X(1)∈K,X(2)∈K。若αX(1)+(1-α)X(2)∈K,则称K为凸集。( 0  1 )
2、顶点(vertex):
X∈K,X(1)∈K,X(2)∈K (任意两点)。若X不能
用αX(1)+(1-α)X(2)表示,则称X为K的一个顶点。(0<α<1)
10