单纯形表格法：simplexTab.docx

单纯形算法步骤1：取得一个初始可行基，写出初始可行基可行解，以及当前的目标函数值，计算所有检验数，。步骤2：考察所有检验值，若所有检验值，则当前基为最优解，停。否则转步骤3.步骤3：令。若，则无最优解，停。否则转步骤4.步骤4：令，用代替得新基。步骤5：新基的基可行解及判别数：转步骤2.单纯形表格法MATLAB程序：MATLAB优化库函数都是以最小化为标准，所以程序也以最小化为标准。的使用方法：先将一般线性规划变为线性规划的标准形式，再构件初始单纯形表格，输入程序。例如：单纯形表格为：1.初始输入表786359945100010001111系数-1-1-10000（值）注：（值）处显示标准型（求min）的目标函数值。2.迭代过程表786359945100010001111判别数-1-1-10000在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.1429 8.0000 5.0000 4.0000 0 1.0000 0 1.0000 0.1250 6.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.0227 1.0000 0.6250 0.5000 0 0.1250 0 0.1250 0.2500 0 5.2500 2.0000 0 -0.7500 1.0000 0.2500 0.1250 0 -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.0909 1.0000 0.7500 0 -0.0909 0.2045 0 0.1136 0.1515 0 5.7500 0 -0.3636 -0.4318 1.0000 0.2045 0.0356 0 -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.0909 1.0000 0 0 -0.0435 0.2609 -0.1304 0.0870 0.1515 0 1.0000 0 -0.0632 -0.0751 0.1739 0.0356 0.0356 0 0 0 0.0593 0.0079 0.0870 0.1542 0It is the end!（表示程序运行完毕）最后得单纯形表为：0100011000.16600-0.04350.0632-0.177910.2609-0.07510.04350-0.13040.17390.031610.08700.0356-0.09090.15150.0356判别数0000.05930.00790.08700.15420X=（0.0316，0.0870,0.0356），g=0.1542, =-0.1542.主程序：function 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) %出基可行解列 lastColExcludingObjEntry=mat(1:(maxRow-1),maxCol); %入基可行解列 ithColExcludingObjEntry=mat(1:(maxRow-1),bestColToPivot); %找出最小正比数以及其对应的行 a=lastColExcludingObjEntry./ithColExcludingObjEntry; val bestRowToPivot=min(a); sprintf(the best Pivot is %d row ang %d col,bestRowToPivot,bestColToPivot) disp(the simplex table is); mat,a;0 disp(press any key to continue); pause; if(val0) count=1; while(s(count)0) count=count+1; end bestRowToPivot=indices(count); end end if(length(a)=0) length(a) return end %旋转变换 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)%