单纯形法原理以及步骤

《单纯形法原理以及步骤》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、x121100x23312111010x31min,,214241001x42x501101222050111442110011442(0)X(0,0,3,1,2)X(1)(1,0,2,1,0)224、单纯形法迭代原理单纯形法是沿顶点寻找线性规划问题最优解的一种有效方法。该方法主要包括：确定初始基可行解（即起始顶点）；从一个基可行解转移到另一个基可行解；最优性检验三项内容。1

2、.确定初始基可行解对标准形式的线性规划问题nmaxz=∑cx（1-6）j=1jjn∑Px=b（1-7）j=1jjst.xj≥0(j=1,…,n)（1-8）(1)如果线性规划问题的约束条件均为≤符号，则通过加入松弛变量化为标准形式后，系数矩阵中包含有m×m的单位矩阵。(2)标准形式的约束条件中本身存在单位矩阵。(3)如果没有单位矩阵，需要通过人造基的方法获得单位矩阵。（见第五节）注意：单纯形法迭代必须有单位方阵。令单位矩阵列向量对应的变量为基变量，其余变量取零值，就可得到初始基可行解（要求右端常数项b≥0）。目

3、标函数约束=右边常数条件行列式≠0=基矩阵2.从一个基可行解转换到另一个基可行解定义：两个基可行解是相邻的，如果它们之间变换且只变换一个基变量。不失一般性，通常假设初始基可行解中的前m个变量为基变量，即(0)000TX(x,x,,x,0,,0)12m代入约束条件（1-6），得m0Pixib(19)i1（1-9）方程组的增广矩阵为：………P1P2PmPm+1PjPnb10…0a1,m+1…a1j…a1nb101…0a2,m+1…a2ja2nb2…：：：：：：：00…1am,m+1…amjamnbm

4、…显然，P1，P2，…，Pm为基向量，其余向量可以由这个基的线性组合来表示：mPjaijPii1m或PaP0(110)jijii1用大于零的正参数乘式（1-10）两边，与（1-9）式相加，得m0(xiaij)PiPjb(111)i1这里，我们得到了一个新解X（1）：(1)000TX(xa,xa,,xa,0,,,,0)11j22jmmj要使X（1）成为基可行解，必须：（1）可行。通过选择参数可以做到。x0x0ilminaij0(112)

5、iaijalj（2）正分量对应的系数列向量线性无关。按（1-12）选择参数后，X（1）成为不超过m个正分量的可行解。它的系数列向量Pj与原来的（m－1）个系数列向量P1，P2，…，Pl-1，Pl+1…，Pm是线性无关的，可以作为一个新基。把Pj化为单位列向量，即，对下列增广矩阵进行初等行变换，就可得到新的基可行解X（1）。P1P2…Pl-1PjPl+1…Pmb10…0a1j0…0b1……biaijxi010a2j00b2：：：：：：：00…1al—1,j0…0bl-1……b000alj00bll

6、xjalj00…0al+1j1…0bl+1：：：：：：：biminaij＞000…0a0…1baijmjmx121100x23312111010x31min,,214241001x42x501101222050111442110011442(0)X(0,0,3,1,2)X(1)(1,0,2,1,0)223.最优性检验和解的判断将基可行解X（0）和X（

7、1）代入目标函数，得m(1)0zci[xiaij]cjmi1z(0)cx0mmiicx0[cca]i1iijiiji1i1(0)(0)z(cz)zjjj通过比较两个目标函数值可以发现，目标函数值是否改善取决于,j由于规定第一个参数大于零，所以，目标值是否改善完全由后者决定。我们称后者为检验数。判别定理：（1）当所有的检验数都≤0时，新基可行解X（1）的目标函数值小于X（0）的目标函数值，这说明，目前的基可行解（顶点）就是最优解。（2）当所有的检验数都≤0

8、时，又有某一个非基变量的检验数等于零，表明新基可行解与原来的基可行解有相同的目标函数值，则问题具有无穷多最优解。（3）与之相应，如果所有非基变量的检验数都＜0，则线性规划问题具有唯一最优解。（4）如果某个非基变量的检验数＞0，而它所对应的系数列向量Pj≤0，则线性规划问题具有无界解。注意，在X（1）的各个分量中，(1)000TX(xa,xa,,xa,0,,,,0)11j22jm