xin 第5、6章单纯刑法.ppt

《xin 第5、6章单纯刑法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章单纯形法及对偶§1单纯形法的基本思路和原理§2单纯形法的表格形式§3求目标函数值最小的单纯形法§4几种特殊情况§5线性规划的对偶问题目标函数：MAXZ=50x1+100x2约束条件：x1+x2+s1=300，2x1+x2+s2=400，x2+s3=250.xj≥0（j=1，2）,sj≥0（j=1,2,3）约束方程组的系数矩阵§1单纯形法的基本思路和原理一基本概念pj为系数矩阵A第j列的向量。A的秩m为3,小于此方程组的变量个数n。基：B是A中m×m阶非奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基。基向量：基B中的一列即称为一个基

2、向量。基B中共有m个基向量pj。非基向量：在A中除了基B之外的一列则称之为基B的非基向量。§7.3表上作业法§1单纯形法的基本思路和原理基变量（根据约束方程可以确定的变量）：与基向量pj相应的变量xj叫基变量，基变量有m个(s1,s2,s3)。非基变量（根据约束方程无法确定，自由变量）：与非基向量pi相应的变量xi叫非基变量，非基变量有n－m个(x1,x2)。§1单纯形法的基本思路和原理由线性代数知道，如果在约束方程组系数矩阵中找到一个基，令这个方程组的非基变量(自由变量)为零，再求解就可得唯一解了，这个解称为基本解。于是找到B为A的一个基，令非基变量x

3、１，x2为零。§1单纯形法的基本思路和原理这时约束方程就变为基变量的约束方程：s1=300，s2=400，s3=250.求得基本解:x1=0，x2=0，s1=300，s2=400，s3=250.满足非负条件的基本解叫做基本可行解，并把这样的基叫做可行基。第一次找的可行基，称为初始可行基(单位矩阵或者由单位向量构成的矩阵)，其相应的基本可行解叫初始基本可行解。如找不到，将构造初始可行基。§7.3表上作业法§1单纯形法的基本思路和原理通过约束等式移项，用非基变量来表示基变量，因此目标函数中只有非基变量。称目标函数中非基变量的系数为该变量的检验数σj（Z=

4、50x1+100x2,σ2=100)。最优解判别定理：在求最大函数值问题中，对于某个基本可行解，如果其非基变量的检验数σj≤0，则这个解就是最优解。在求最小函数值中，检验数应该σj≥0.§1单纯形法的基本思路和原理二、解的最优性检验三、基变换如不是最优解，那么继续移项，将一个非基变量和一个基变量对换（迭代），得到新的可行基，由此求解得新的基本可行解。为了换基就要确定换入变量（入基变量）与换出变量（出基变量）。1.入基变量（选检验数大于0的非基变量为入基变量）求最大函数值时,只当σj≤0，才是最优解。当σj＞0时，函数值还可以继续增大。故选检验数大于0的非基

5、变量换到基变量中去。若有两个以上，为使目标函数增加更快些，选σj最大者对应的非基变量为入基变量。在上例题中σ2=100比50大，故选x2为入基变量。§1单纯形法的基本思路和原理2.出基变量的确定约束方程中常数项的值除以入基变量在各约束方程中的正的系数，其中最小比值所在的约束方程中的原基变量确定为出基变量（可以证明）。§1单纯形法的基本思路和原理已确定x2为入基变量其中的值最小，于是第三个约束方程的基变量s3为出基变量。可知x2，s1，s2为基变量，x1，s3为非基变量。令非基变量为零，得x2+s1=300,x2+s2=400,x2=250.求得新基本可行

6、解x1=0,x2=250,s1=50,s2=150.此时目标函数值为25000。（初始基本可行解时，目标函数值为0）。接着继续检验其最优性。§1单纯形法的基本思路和原理§2单纯形法的表格形式可行基为m阶单位矩阵的线性规划模型如下（假设其系数矩阵的前m列是单位矩阵）：以下用表示基变量，用表示非基变量。移项，用非基变量表示基变量：把上式代入目标函数，有其中：§2单纯形法的表格形式初始基本可行解为s1=300,s2=400,s3=250,x1=0,x2=0迭代次数基变量cjcix1x2s1s2s3bi比值501000000s1s2s300011100210100

7、10013004002500000050100000§2单纯形法的表格形式最小250，s3为出基变量100>50，X2为入基变量主元接着要将x2和s3对换（迭代），需将x2的系数向量p2变成单位向量。由于主元在第3分量上，故所求单位向量是（0,0,1）T。因此必须进行行初等变换。行初等变换：第3行乘以-1加到第1行，第3行乘以-1加到第2行基本可行解为s1=50,s2=150,x2=250，x1=0,s3=,0迭代次数基变量cjcix1x2s1s2s3bi比值501000001s1s2x2001001010-12001-1010015015025050/1

8、150/2——01000010050000-100§2单纯形法的表