1、單純形算法步驟1：取得一個(gè)初始可行基，寫出初始可行基可行解，以及當(dāng)前的目標(biāo)函數(shù)值，計(jì)算所有檢驗(yàn)數(shù)，。步驟2：考察所有檢驗(yàn)值，若所有檢驗(yàn)值，則當(dāng)前基為最優(yōu)解，停。否則轉(zhuǎn)步驟3.步驟3：令。若，則無最優(yōu)解，停。否則轉(zhuǎn)步驟4.步驟4：令，用代替得新基。步驟5：新基的基可行解及判別數(shù)：轉(zhuǎn)步驟2.單純形表格法MATLAB程序：MATLAB優(yōu)化庫函數(shù)都是以最小化為標(biāo)準(zhǔn)，所以程序也以最小化為標(biāo)準(zhǔn)。的使用方法：先將一般線性規(guī)劃變?yōu)榫€性規(guī)劃的標(biāo)準(zhǔn)形式，再構(gòu)件初始單純形表格，輸入程序。例如：?jiǎn)渭冃伪砀駷椋?.初始輸入表786359945100010001111系數(shù)-1-1-10000（值）注：（值）處顯示標(biāo)準(zhǔn)型（

2、求min）的目標(biāo)函數(shù)值。2.迭代過程表786359945100010001111判別數(shù)-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;%注釋：自由變量個(gè)數(shù)simplexTab(mat,numFreeVar);在MATLAB的command window輸出：初始結(jié)果：ans =the best Pivot is 2 row ang 1 colthe simplex table isans = 7.0000 3.000

3、0 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第一次轉(zhuǎn)換結(jié)果：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.0

4、227 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第二次轉(zhuǎn)換結(jié)果：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.0

5、909 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第三次轉(zhuǎn)換結(jié)果：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.1

6、515 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!（表示程序運(yùn)行完畢）最后得單純形表為：0100011000.16600-0.04350.0632-0.177910.2609-0.07510.04350-0.13040.17390.031610.08700.0356-0.09090.15150.0356判別數(shù)0000.05930.00790.08700.15420X=（0.0316，0.0870,0.0356），g=0.1542, =-0.15

7、42.主程序：function simplexTab(mat,numFreeVar)%Recode by ariszheng%2007 08 09%輸入：%mat 單純形表%numFreeVar 自由變量個(gè)數(shù)format short%檢驗(yàn)和尋找最佳判別數(shù)%maxRow,maxCol單純形表的行數(shù)和列數(shù)maxRow=length(mat(:,1);maxCol=length(mat(1,:);%判別數(shù)objEntryExcludingMaxPayOff=mat(maxRow,1:maxCol-2);%尋找最小判別數(shù)objEnt bestColToPivot=min(objEntryExcludi

8、ngMaxPayOff);%循環(huán)迭代while(objEnt<0) %出基可行解列 lastColExcludingObjEntry=mat(1:(maxRow-1),maxCol); %入基可行解列 ithColExcludingObjEntry=mat(1:(maxRow-1),bestColToPivot); %找出最小正比數(shù)以及其對(duì)應(yīng)的行 a=lastColExcludingObjEntry./ithColExcludingObjEntry; val bestRowToPivot=min(a); sprintf('the best Pivot is %d row ang

9、%d col',bestRowToPivot,bestColToPivot) disp('the simplex table is'); mat,a;0 disp('press any key to continue'); pause; if(val<0) s indices=sort(a); if(max(a)>0) count=1; while(s(count)<0) count=count+1; end bestRowToPivot=indices(count); end end if(length(a)=0) length(a)

10、 return end %旋轉(zhuǎn)變換 mat=pivot(mat,bestRowToPivot,bestColToPivot); %尋找最小判別數(shù) objEntryExcludingMaxPayOff=mat(maxRow,1:maxCol-2); objEnt bestColToPivot=min(objEntryExcludingMaxPayOff); %當(dāng)所有的判別數(shù)都大于零的時(shí)候迭代停止end%sprintf('the best Pivot is %d row and %d col',bestRowToPivot,bestColToPivot)disp('the

11、simplex table is');mat,a;0disp('It is the end!');子程序：由主函數(shù)調(diào)用1. 單純形表的兩行對(duì)調(diào)程序function newMat=interChange(mat,row1,row2)temp=mat(row1,:);mat(row1,:)=mat(row2,:);mat(row2,:)=temp;newMat=mat;2. 行數(shù)據(jù)非主元素消去處理程序function newMat=multiFromRowToRow(mat,fromRow,toRow,multiplier)rG=mat(fromRow,:)*multiplier;mat(toRow,:)=rG+mat(toRow,:);newMat=mat;3. 行乘以mult得新行數(shù)據(jù)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)為軸做旋轉(zhuǎn)function newMat=pivot(mat,row,