运筹学4单纯形法迭代原理课件

运筹学4单纯形法迭代原理
在引入人工变量后，与原先的约束方程不完全等价，为此， 需要在目标函数上做些“修正”——大M法或两阶段法
x1
x2
a1m1xm1 a1nxn b1 a2m1xm1 a2nxn b2
xm amm1xm1 amnxn bm xj 0 ( j 1,2,,n)
非基变量取0，算出基变量，搭配在一起构成 初始基本可行解：
三 单纯形法 迭代原理
运筹学4单纯形法迭代原理
三. 单纯形法的基本思想
1、顶点的逐步转移
• 即从可行域的一个顶点（基本可行解） 开始，转移到另一个顶点（另一个基本可 行解）的迭代过程，转移的条件是使目标 函数值得到改善（逐步变优），当目标函 数达到最优值时，问题也就得到了最优解。
运筹学4单纯形法迭代原理
x2
a2m1xm1 a2nxn b2
xm amm1xm1 amnxn bm xj 0 ( j 1,2,,n)
运筹学4单纯形法迭代原理
➢观察法 ——观察系数矩阵中是否含有现成的单位阵？ ➢LP限制条件中全部是“≤”类型的约束 ——将新增的松弛变量(+)作为初始基变量，对应的 系数列向量构成单位阵； ➢LP限制条件有“≥”类型的约束 ——左端新增剩余变量(-)后，再加上一个非负的新 变量—人工变量。 ➢LP限制条件有“=”类型的约束 ——直接在左端加上人工变量。
n
xi bi' ai'jxj, jm1
n
若BI, xi 运b筹i学4单纯形a法ij迭x代j 原理 jm1
i1,2 ,m
用非基变量表示目标函数的表达式：
n
m
n
m
n
Z c j x j cjxj cjxj cixi cjxj
j 1
m
j1
n
jm1
i1
n
jm1
ci(bi' ai'jxj) cjxj
n
3、进行基变换
Z Z0 jxj
jm1
（1）进基变量的确定——原则：正检验数（或最大正检验
数）所对应的变量进基，目的是使目标函数得到改善。
xmt
（2）离基变量的确定——在保持解的可行性的前提下， 使目标函数较快增大。
X(k)(x1 k,x2 k,.x .m k.,0 ,,.0 .)T .,
n
xi bi' ai'jxj
运筹学4单纯形法迭代原理 是否还是基本解？是
Z(k1) Z0
n
jxj
Z0
xk
mt mt
jm1
Z 0 Z(k)
从而，目标函数得到了改善。
运筹学4单纯形法迭代原理
第四节 单纯形表
初始基本可行解
检验数
进基变量：检验数 运筹离学4基单纯形变法迭量代原：理最小比值准则
1.确定初始基本可行解
LP:
n
maxz cjxj
j1
n
s.t. j1
Pj xj
b
xj 0( j 1,2,3,n)
希望在化LP的标准形 式时，A中都含有一 个m阶单位阵。
？
x1
a1m1xm1 a1nxn b1
i1
jm1
jm1
m
mn
n
cibi'
ciai'jxj cjxj
n
xi bi' ai'jxj
jm1
i1
i1jm1
jm1
m
nm
n
cibi'
ciai'jxj cjxj
i1
jm1i1
jm1
典式
m
n
m
cibi' (cj ciai' j)xj
zj
Z0
i1
jm 1
i1
n
n
n
Z0 (cj zj)xjZ0 jxj
Z
Z0 jxj
jm1
jm1
jm1
运筹学4单j 纯形法检迭代验原数理
n
Z Z0 jxj
m
其中 Z0 cibi',
i 1
jm1
j cj zj,
m
z j ciai'j
i 1
（1）最优性判别定理
j 0,jm1,..n.,
（2）有无穷多个“最优解”的判别定
理
j 0 且mt 0
运筹学4单纯形法迭代原理
a' i,mt
0
k l ' l ,m t
xik1xikai',mtxmt
x k 1 mt
x
k l
a' l ,m t
x ik 1 x ik a i',m tx m k 1 t,i 1 ,.m .,i. ,l
xk1 l
0
x 离基变量： l
X(k)(x1 k,x2 k,.x .m k.,0 ,,.0 .)T ., X ( k 1 ) ( x 1 k 1 ,x .l k 1 1 .,0 , .x l k 1 1 ,0 .0 .,x .m k 1 t,,0 ,wk.baidu.com0 ) T .是 解.可 ！,行
jm1
xj 0; j m 1,...,n
xik bi'
xm t 0
xj0;jm 1,.m .. ,t1,m t1,.n ..,
x ba x x a x k1 ' ' i 运筹学4单i纯形法迭代i,m 原理t mt
k' i i,mt mt
xik1xikai',mtxmt 0
n
Z Z0 jxj
X(0)(b 1,b2,.b .m .,0 ,,.0 .)T .,
运筹学4单纯形法迭代原理
2.建立判别准则
判断：初始基本可行解或经过若干次迭代后得到的新基 本可行解—当前解—是否为最优解？
一般（经过若干次迭代），对于基B，用 非基变量表出基变量的表达式 为：
Axb BB xNN xb
xBB1bB1NN x 典式
jm1
a' i,m t < =
xmt
xik ai',mtxmt
若mt 0且pm' t 0
则该LP无最优解。
>
当
a' i,mt
0 时，为使
xik ai',mtxmt 0，需要
最小比 值原则
xmt
x
k i
a' i,m t
x k 1 mt
从而，x 最大可取到 m t
a x 运筹学m 4单i纯i形n法迭a代ix',原mik理t
转移条件？
转移结果？
使目标函数值得到改善
得到LP最优解，目标函数达到最优值
2．需要解决的问题：
(1)为了使目标函数逐步变优，怎么转移？ (2)目标函数何时达到最优——
判断标准是什么？
运筹学4单纯形法迭代原理
解LP问题单纯形法的基本思路： 初始可行基：设法在约
束矩阵 ARmn 中
构造出一个m阶单位阵
顶点转移的依据？
根据线性规划问题的可行域是凸多边形 或凸多面体，一个线性规划问题有最优解， 就一定可以在可行域的顶点上找到。
于是，若某线性规划只有唯一的一个最 优解，这个最优解所对应的点一定是可行域 的一个顶点；若该线性规划有多个最优解， 那么肯定在可行域的顶点中可以找到至少一 个最优解。
运筹学4单纯形法迭代原理