运筹学线性规划图解法.ppt

例1: max z=2x1+ 3x2
. x1+2x2≤8
4x1≤16
x1,x2≥0
有唯一解
x1
x2
可行域
(4,2)
z=14
目标函数等值线
画图步骤:
1、约束区域的确定
2、目标函数等值线
3、平移目标函数等值线求最优值
有无穷多解
线段Q1Q2上的任意点都是最优解
x2
x1
x1+2x2=8
4x2=12
3x1=12
例2 max z =2x1+4x2
. x1+2x2≤8
4x2 ≤ 12
3x1 ≤12
x1, x2 ≥0
Q1
Q2
约束条件围不成区域
(又称矛盾方程)
无可行解
例3:
x1
x2
max z=4x1+3x2
-3x1+2x2≤6 . -x1+3x2≥18
x1, x2 ≥ 0
无有限最优解(无界解)
x2
例4:
-3x1+2x2=6
线性规划的几何特性:
线性规划问题若有最优解,一定在其可行域的顶点达到;
唯一最优解必在一个顶点达到或无穷多最优解至少在两个顶点达到;
无解(可行域为空集或目标函数无有限极值)。
图解法得出线性规划问题解的几种情况
解的几种情况
约束条件图形特点
方程特点
唯一解
一般围成有限区域,最优值
只在一个顶点达到
无穷多解
在围成的区域边界上,至少
有两个顶点处达到最优值
目标和某一约束
方程成比例
无可行解
(
无
解
)
围不成区域
有矛盾方程
无界解
(
无解
)
围成无界区域
,
且无有限
最优值
缺少一必要条件
的方程
列向量 x=(x1,x2,…,xm)T为m维列向量。xRm
线性相关一组向量v1,…,vn,如果有一组不全为零的系数
α1, …,αn,使得: α1 v1+…+αnvn=0
则称v1,…,vn 是线性相关的.
线性无关一组向量v1,…,vn,如果对于任何数α1,…,αn,
若要满足: α1 v1+…+αnvn=0 ,则必有系数
α1=…=αn=0,(全为零)则称v1,…,vn线性无关(线
性独立).
矩阵A的秩设A为一个m×n阶矩阵(m<n)若矩阵中最大线性
无关列向量个数为k,则称矩阵A的秩数为k,记
为秩(A)=k.
复****线性代数内容:
设线性规划的标准形式:
max z=Σcjxj (1)
=bi i=1,2,…,m (2)
xj≥0 j=1,2,…,n (3)
可行域:由约束条件(2)、(3)所围成的区域;
可行解:满足(2)、(3)条件的解X=(x1,x2,…,xn)T为可行解;
基:设A是约束条件方程组的m×n维系数矩阵,其秩为m,B是A中m×m阶非奇异子矩阵,则称B为线性规划问题的一个基。
设
§ 线性规划问题解的概念
B=
=(p1,p2, …,pm)
a11 a12 … a1m  a21 a22 … a2m  ……… am1 am2 …amm
基向量、非基向量、基变量、非基变量:
称pj(j=1,2,…,m)为基向量,其余称为非基向量;与基向量pj(j=1,2,…,m)对应的xj称为基变量,其全体写成XB=(x1,x2,…,xm)T;否则称为非基变量,其全体经常写成XN。
基解:对给定基B,设XB是对应于这个基的基变量
XB=(x1,x2,…,xm)T; 令非基变量xm+1=xm+2=…=xn=0,
由(2)式得出的解X=(x1,x2,…,xm,0,…,0)T
称为基解。
基可行解:所有决策变量满足非负条件(xj ≥0)的基解,
称作基可行解。
可行基:基可行解所对应的基底称为可行基。
注: m个。基可行解的数目一般小于
基解的数目;
基解中非零分量的个数小于m个时,基解称为退化解。
以后在不声明的情况下,均假设不出现退化情况。
可行解
基解
基可行解
非可行解
解的关系: