单纯形法_单纯形法介绍

单纯形法由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“单纯形法介绍”。

单纯形法（不可以解空集问题，无初始解）

一、单纯形法的基本思想

1、顶点的逐步转移

即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。

2．需要解决的问题：

(1)为了使目标函数逐步变优，怎麽转移？

(2)目标函数何时达到最优——判断标准是什么？

（3）初始解的寻找

二、单纯形法原理（用代数方法求解LP）

第一步：引入非负的松弛变量（x3 x4 x5）和剩余变量（算完后剩余的资源）

x3,x4,x5, 将该LP化为标准型 第二步：寻求初始可行基（单位阵对应的），确定基变量

第三步：写出初始基本可行解（很多之中找一个，必令原x为0）和相应的目标函数值 两个关键的基本表达式：

① 用非基变量表示基变量的表达式 ② 用非基变量表示目标函数的表达式

第四步：分析两个基本表达式，看看目标函数是否可以改善？

①

分析用非基变量表示目标函数的表达式

非基变量前面的系数均为正数（必为负数才可以），所以任何一个非基变量进基都能使Z值增加

通常把非基变量前面的系数叫“检验数” ② 选哪一个非基变量进基？

排在最前面的负检验数对应的非基变量 ③ 确定出基变量

“最小比值原则”（或θ原则）见本 如果x2≤0，会出现什麽问题？

最小比值原则会失效！ 基变换

新的基变量——x2, x3,x4；新的非基变量x1, x5 ； 写出用非基变量表示基变量的表达式： 可得新的基本可行解（）X1=（0,3,2,16,0）T

⑤ 写出用非基变量表示目标函数的表达式: 检验数仍有正的第五步：上述过程何时停止？

当用非基变量表示目标函数的表达式中，非基变量的系数（检验数）全部非正（0时表无穷解，负时表唯一解）时，当前的基本可行解就是最优解!

为什麽？

分析用非基变量表示目标函数的表达式，如果让负检验数所对应的变量进基，目标函数值将下降！

（2）表格设计依据：

将-Z看作不参与基变换的基变量，把目标函数表达式改写成方程的形式，和原有的m个约束方程组成一个具有n+m+1个变量、m+1个方程的方程组：

a11x1a12x2a1nxnxn1b1axaxaxxb2112222nnn22axaxaxxbmnnnmmm11m22Zc1x1c2x2cnxncn1xn1cnmxnm0取出系数写成增广矩阵的形式：

0a11a120a21a220am1am21cc21a1na2namncn100010001cn1cn2cnmb1b2bm0

-Z，Xn+1，…，Xn+m所对应的系数

列向量构成一个基

用矩阵的初等行变换将该基变成单位阵,这时

变成0，相应的增广矩阵变成如下形式：

a22a2n



am2amn

2n

其中，j=1，2，…，n ；

m0z0cnibi

i1 0a110a210am111a12a1n100b1010b2001bm000z0增广矩阵的最后一行就是用非基变量表示目标函数的表达式,(j=1,2,…,n)就是非基变量的检验数。

（3）检验数的两种计算方法：

①利用矩阵的行变换，把目标函数表达式中基变量前面的系数变为0；

②使用计算公式——jcjci1mniijacjCBPjcjzj,j1,2,,n

从最优表可知: 该LP的

最优解是X*=(4,2,0,0,4)T

相应的目标函数最优值是Zmax=14