单纯形表格法：simplextab

单纯形算法步骤 1：取得一个初始可行基 ，写出初始可行基可行解 ，以及当前B10BNxb的目标函数值 ，计算所有检验数 ，1TBzcxb,12,.jn。1TN步骤 2：考察所有检验值 ，若所有检验值 ，则当前基为最优解，停。,12,.jn0j否则转步骤 3.步骤 3：令 。若 ，则无最优解，停。否则转步骤 4.max|0kj10kBp步骤 4：令 ，用 代替 得新基。1 11()in|i rki kkibbp kxr步骤 5：新基的基可行解及判别数： ,2.,rjjkrjijijikrkriikrjjjknabaa转步骤 2.单纯形表格法 MATLAB 程序： simplexTabMATLAB 优化库函数都是以最小化为标准，所以 程序t,nuFreVa也以最小化为标准。的使用方法：simplexTab先将一般线性规划变为线性规划的标准形式，再构件初始单纯形表格，输入程序。例如：123123456123123456456maxmin0.79.791854866,0,0fxgxxst st xxxx 单纯形表格为：1.初始输入表 1x23x45x6btheaA786359945100010001111系数 -1 -1 -1 0 0 0 0（ 值）g注：（ 值）处显示标准型（求 min）的目标函数值。g2.迭代过程表 1x23x45x6btheaA786359945100010001111判别数 -1 -1 -1 0 0 0 0在 MATLAB 的 command window 输入：mat=7 3 9 1 0 0 1;8 5 4 0 1 0 1;6 9 5 0 0 1 1;-1 -1 -1 0 0 0 0;numFreeVar=3;%注释：自由变量个数simplexTab(mat,numFreeVar);在 MATLAB 的 command window 输出：初始结果：ans =the best Pivot is 2 row ang 1 colthe simplex table isans =7.0000 3.0000 9.0000 1.0000 0 0 1.0000 0.14298.0000 5.0000 4.0000 0 1.0000 0 1.0000 0.12506.0000 9.0000 5.0000 0 0 1.0000 1.0000 0.1667-1.0000 -1.0000 -1.0000 0 0 0 0 0press any key to continue第一次转换结果：ans =the best Pivot is 1 row ang 3 colthe simplex table isans =0 -1.3750 5.5000 1.0000 -0.8750 0 0.1250 0.02271.0000 0.6250 0.5000 0 0.1250 0 0.1250 0.25000 5.2500 2.0000 0 -0.7500 1.0000 0.2500 0.12500 -0.3750 -0.5000 0 0.1250 0 0.1250 0press any key to continue第二次转换结果：ans =the best Pivot is 1 row ang 2 colthe simplex table isans =0 -0.2500 1.0000 0.1818 -0.1591 0 0.0227 -0.09091.0000 0.7500 0 -0.0909 0.2045 0 0.1136 0.15150 5.7500 0 -0.3636 -0.4318 1.0000 0.2045 0.03560 -0.5000 0 0.0909 0.0455 0 0.1364 0press any key to continue第三次转换结果：ans =the best Pivot is 3 row and 1 colthe simplex table isans =0 0 1.0000 0.1660 -0.1779 0.0435 0.0316 -0.09091.0000 0 0 -0.0435 0.2609 -0.1304 0.0870 0.15150 1.0000 0 -0.0632 -0.0751 0.1739 0.0356 0.03560 0 0 0.0593 0.0079 0.0870 0.1542 0It is the end!（表示程序运行完毕）最后得单纯形表为： 1x23x45x6btheaA0100011000.16600-0.04350.0632-0.177910.2609-0.07510.04350-0.13040.17390.031610.08700.0356-0.09090.15150.0356判别数 0 0 0 0.0593 0.0079 0.0870 0.1542 0X=（0.0316 ，0.0870,0.0356） ，g=0.1542, =-0.1542.123fx主程序：simplexTabfunction simplexTab(mat,numFreeVar)%Recode by ariszheng%2007 08 09%输入：%mat 单纯形表%numFreeVar 自由变量个数format short%检验和寻找最佳判别数%maxRow,maxCol 单纯形表的行数和列数maxRow=length(mat(:,1);maxCol=length(mat(1,:);%判别数objEntryExcludingMaxPayOff=mat(maxRow,1:maxCol-2);%寻找最小判别数objEnt bestColToPivot=min(objEntryExcludingMaxPayOff);%循环迭代while(objEnt0)count=1;while(s(count)0)count=count+1;endbestRowToPivot=indices(count);endendif(length(a)=0)length(a)returnend%旋转变换mat=pivot(mat,bestRowToPivot,bestColToPivot);%寻找最小判别数objEntryExcludingMaxPayOff=mat(maxRow,1:maxCol-2);objEnt bestColToPivot=min(objEntryExcludingMaxPayOff);%当所有的判别数都大于零的时候迭代停止end%sprintf(the best Pivot is %d row and %d col,bestRowToPivot,bestColToPivot)disp(the simplex table is);mat,a;0disp(It is the end!);子程序：由主函数调用1. 单纯形表的两行对调程序function newMat=interChange(mat,row1,row2)temp=mat(row1,:);mat(row1,:)=mat(row2,:);mat(row2,:)=temp;newMat=mat;2. 行数据非主元素消去处理程序function newMat=multiFromRowToRow(mat,fromRow,toRow,multiplier)rG=mat(fromRow,:)*multiplier;mat(toRow,:)=rG+mat(toRow,:);newMat=mat;3. 行乘以 mult 得新行数据function newMat=multMat(mat,row,mult)%multiply a row of a matrix by a nonzero constantmat(row,:)=mat(row,:)*mult;newMat=mat;4. 以 mat(row,col)为轴做旋转function newMat=pivot(mat,row,col)%no