文档介绍：1/128
第三节 线性规划问题的单纯形法
n
max z=cjxj
j=1
n
. aijxj=bi (i=1,2,……,m)
j=1
xj≥0 (j=1,2,……,n)
(1)可行解:满足所有约束方程和变量符号限制条件的一组变量的取值。
(2)可行域:全部可行解的集合称为可行域。
(3)最优解:使目标函数达到最优值的可行解。
一、LP问题的解的基本概念
设模型
2/128
(4)基:设A为线性规划模型约束条件系数矩阵(m n,m<n),而B为其mm子矩阵,若|B|≠0,则称B为该线性规划模型的一个基。
(5)基变量:基中每个向量所对应的变量称为基变量。
(6)非基变量:模型中基变量之外的变量称为非基变量。
(7)基本解(基解):令模型中所有非基变量X非基=0后,由模型约束方程组 n
aijxj =bi (i=1,2,……,m)得到的一组解。
j=1
(8)基可行解(基本可行解):在基本解中,同时又是可行解(基变量取值非负)的解称为基可行解(基本可行解)。
(9)可行基:对应于基本可行解的基称为可行基。
(10)最优基本可行解:最优解同时又是基本可行解。
(11)最优基:最优基本可行解所对应的基。
3/128
x1 x2 x3 x4
设
,令
,则
| B |=1≠0,
令 x1=x2 =0,
例:
x3 x4
——基本可行解
标准化
x1,x2 为非基变量
得基本解:X=(0,0,6,8)T
则 x3 =6, x4=8,
则B是一个基,
x3 ,x4为基变量,
令
B=
1 1
-1 0
x1 x3
,则
令 x2=x4 =0,则 x1 =-8, x3=14,X=(-8,0,14,0)T
| B |=1≠0,
——非基本可行解
Max z= x1+3x2
st. x1+ x2≤6 -x1+2x2≤8 x1,x2≥0
Max z= x1+3x2 +0x3 +0x4
st. x1+x2+x3 =6 - x1+2x2 +x4=8 x1, x2, x3 , x4≥0
4/128
O
E
C
B
D
A
Max z= x1+3x2 +0x3 +0x4
st. x1+x2+x3 =6 x1+2x2 +x4=8 x1, x2, x3 , x4≥0
5/128
二、单纯形法(SimplexMethod)基本原理 (补充:概念与解的性质)
两个概念:
(1)凸集:对于集合C中任意两点连线上的点,若也在C内,则称 C为凸集。
或者,任给X1C,X2 C,X=X1+ (1-)X2 C (0<<1),则C为凸集。
凸集
非凸集
6/128
(2)顶点:凸集中不成为任意两点连线上的点,称为凸集顶点。
或者,
设C为凸集,对于XC,不存在任何X1C,X2 C, 且X1≠X2,使得X=X1+(1-)X2C, (0<<1),则X为凸集顶点。
X
X
X
X
X
7/128
定理2: LP问题的基本可行解对应其可行域的顶点。
定理3: LP问题若有可行解必有基本可行解;若有最优解必有基本最优解。
定理1: LP问题存在可行解,则可行域为凸集。
三个基本定理:
8/128
解间的关系如下图所示:
基本可行解
基本解
可行解
非可行解
最优解
基本可行解
9/128
二、单纯形法的基本原理
例
(1)初始基可行解的选择:
10
称为典型方程组,简称典式
对于基
方程改写为:
令x1=x2=0 (非基变量为0)
得一基可行解 X(0)=(0,0,0,6,8,3)T,其经济意义:无产品生产,利润为0