第一篇：線性規(guī)劃單純形法matlab解法
線性規(guī)劃單純形法matlab解法
%單純形法matlab程序-ssimplex % 求解標準型線性規(guī)劃:max c*x;s.t.A*x=b;x>=0 % 本函數(shù)中的A是單純初始表，包括:最后一行是初始的檢驗數(shù)，最后一列是資源向量b % N是初始的基變量的下標
% 輸出變量sol是最優(yōu)解, 其中松弛變量（或剩余變量）可能不為0 % 輸出變量val是最優(yōu)目標值，kk是迭代次數(shù) % 例：max 2*x1+3*x2 % s.t.x1+2*x2<=8 % 4*x1<=16 % 4*x2<=12 % x1,x2>=0 % 加入松馳變量，化為標準型，得到 % A=[1 2 1 0 0 8;% 4 0 0 1 0 16;% 0 4 0 0 1 12;% 2 3 0 0 0 0];% N=[3 4 5];% [sol,val,kk]=ssimplex(A,N)% 然后執(zhí)行 [sol,val,kk]=ssimplex(A,N)就可以了。function [sol,val,kk]=ssimplex(A,N)[mA,nA]=size(A);kk=0;% 迭代次數(shù) flag=1;while flag kk=kk+1;if A(mA,:)<=0 % 已找到最優(yōu)解 flag=0;sol=zeros(1,nA-1);for i=1:mA-1 sol(N(i))=A(i,nA);end val=-A(mA,nA);else for i=1:nA-1 if A(mA,i)>0&A(1:mA-1,i)<=0 % 問題有無界解 disp('have infinite solution!');flag=0;break;end end if flag % 還不是最優(yōu)表，進行轉(zhuǎn)軸運算 temp=0;for i=1:nA-1 if A(mA,i)>temp temp=A(mA,i);inb=i;% 進基變量的下標 end end sita=zeros(1,mA-1);for i=1:mA-1 if A(i,inb)>0 sita(i)=A(i,nA)/A(i,inb);end end temp=inf;for i=1:mA-1 if sita(i)>0&sita(i) A(outb,:)=A(outb,:)/A(outb,inb);for i=1:mA if i~=outb A(i,:)=A(i,:)-A(outb,:)*A(i,inb);End End End End end 算法實現(xiàn)與分析 算法1．單純形法 具體算例： minz=?3x1+x2+2x3 3x1+2x2?3x3=6 x1?2x2+x3+x5=4 x1,x2,x3≥0標準化后： min z=?3x1+x2+2x3+Mx4+Mx5 3x1+2x2?3x3+x4=6 x1?2x2+x3+x5=4 x1,x2,x3,x4,x5≥0用單純形法求解，程序如下： clear clc M=1000000; A=[3,2,-3,1,0;1,-2,1,0,1];%系數(shù)矩陣 C=[-3,1,2,M,M,0];%價值矩陣 B=[6;4];Xt=[4 5]; for i=1:length(C)-1 D=0; for j=1:length(Xt) D=D+A(j,i)*C(Xt(j)); end xi(i)=C(i)-D;end s=[]; for i=1:length(xi) if xi(i)<0 s=[s,i]; end end f=length(s);h=1; while(f) for k=1:length(s)j=1;A x=[]; for i=1:length(Xt) if A(i,s(k))>0 x(j)=i;j=j+1; end end x if(length(x)+1==1)break;end y=1 x for i=1:length(x) if B(x(i))/A(x(i),s(k)) end end y=x(y);end y1=Xt(y);%??3?±?á? s k aa=A(y,s(k))%s(k)?a??è?±?á? A(y,:)=A(y,:)./aa;B(y,:)=B(y,:)./aa;z=[]; for i=1:length(Xt)z=[z,i];end z z(y)=[];z Xt for i=1:length(z);yz=-A(z(i),s(k)) A(z(i),:)=A(z(i),:)+A(y,:).*yz B(z(i))B(y)yz B(z(i))=B(z(i))+B(y).*yz end for i=1:length(Xt) if Xt(i)==y1 Xt(i)=s(k);break end end Xt disp('×a??oó')A=A B=B AB=[A,B]; for i=1:length(C)D=0; for j=1:length(Xt)D=D+AB(j,i)*C(Xt(j)); end xi(i)=C(i)-D; end xi s=[]; for i=1:length(xi)-1 if xi(i)<0 s=[s,i]; end end s vpa([A,B;C]);f=length(s);h=h+1; if h==5 break end end -xi(length(xi)) clear clc X=[1 2 3 4 5];A=[ 1 2 1 0 0;4 0 0 1 0;0 4 0 0 1];C=[2 3 0 0 0 ];b=[8;16;12];t=[3 4 5];B0=A(:,t);while 1 CB0=C(:,t);XN01=X; for i=1:length(t); for j=1:length(X); if XN01(j)==t(i) XN01(j)=0; end end end j=1; for i=1:length(X); if XN01(i)~=0 XN0(j)=XN01(i); j=j+1; end end for j=1:length(XN0); CN0(j)=C(XN0(j)); end N0=[]; for i=1:length(XN0); N0=[N0,A(:,XN0(i))]; end xiN0=CN0-CB0*B0*N0;j=1;z=[]; for i=1:length(xiN0) if xiN0(i)>0 z(j)=i; j=j+1; end end if length(z)+1==1; break; end n=1; for i=1:length(z) if z(i)>z(n) n=i; end end k=XN0(z(n));%換入變量 B=B0*b; P=B0*A(:,k);j=1; for i=1:length(P) if P(i)>0 x(j)=i; j=j+1; end end y=1; for i=1:length(x) if B(x(y))/P(x(y))>B(x(i))/P(x(i)) y=i; end end y1=x(y); y=t(y1);%換出變量 for i=1:length(t) if t(i)==y m=i; break; end end t(m)=k; P2=B0*A(:,k);q=P2(y1);P2(y1)=-1;P2=-P2./q; E=[1 0 0;0 1 0;0 0 1];E(:,m)=P2;B0=E*B0;end CB0*B0*b function [xx,fm]=myprgmh(m,n,A,b,c)B0=A(:,1:m);cb=c(:,1:m);xx=1:n;sgm=c-cb*B0^-1*A;h=-1;sta=ones(m,1);for i=m+1:n if sgm(i)>0 h=1; end end while h>0 [msg,mk]=max(sgm); for i=1:m sta(i)=b(i)/A(i,mk); end [mst,mr]=min(sta); zy=A(mr,mk); for i=1:m if i==mr for j=1:n A(i,j)=A(i,j)/zy; end b(i)=b(i)/zy; end end for i=1:m if i~=mr for j=1:n A(i,j)=A(i,j)-A(i,mk)*A(mr,j); end b(i)=b(i)-A(i,mk)*b(mr); end end B1=A(:,1:m); cb(mr)=c(mk); xx(mr)=mk; sgm=c-cb*B1*A; for i=m+1:n if sgm(i)>0 h=1; end end end fm=c*xx; 運籌學教程（胡運權(quán)主編，清華版）部分習題答案（第一章） 1.5 記可行集4個頂點分別為O:(0,0)，A:(1.6,0)，B:(1,1.5)，C:(0,2.25)當c=0，d=0時，四邊形OABC中的點都是最優(yōu)解 當c=0，d>0時，頂點C是最優(yōu)解 當c=0，d<0時，線段OA上的點都是最優(yōu)解 當c>0，d/c<2/5時，頂點A是最優(yōu)解 當c>0，d/c=2/5時，線段AB上的點都是最優(yōu)解 當c>0，2/5 當c<0，d=0時，線段OC上的點都是最優(yōu)解 當c<0，d>0時，頂點C是最優(yōu)解 1.8 a=3，b=2，c=4，d=-2，e=2，f=3，g=1，h=0，i=5，j=5，k=-3/2，l=0 1.15 設(shè)i=1,2,3分別表示前、中、后三艙，j=1,2,3分別表示A、B、C三種商品 設(shè)第i艙裝載第j中商品的件數(shù)為xij max s.t.z = 100(x11+x21+x31)+ 700(x12+x22+x32)+ 600(x13+x23+x33)8x11+6x12+5x13 ? 2000 8x21+6x22+5x23 ? 3000 8x31+6x32+5x33 ? 1500 10x11+5x12+7x13 ? 4000 10x21+5x22+7x23 ? 5400 10x31+5x32+7x33 ? 1500 x11+x21+x31 ? 600 x12+x22+x32 ? 1000 x13+x23+x33 ? 800 8x11+6x12+5x13 ? 1.15(8x21+6x22+5x23)8x21+6x22+5x23 ? 1.15(8x11+6x12+5x13)8x31+6x32+5x33 ? 1.15(8x21+6x22+5x23)8x21+6x22+5x23 ? 1.15(8x31+6x32+5x33)8x11+6x12+5x13 ? 1.1(8x31+6x32+5x33)8x31+6x32+5x33 ? 1.1(8x11+6x12+5x13)xij ? 0, i=1,2,3, j=1,2,3 1.16 設(shè)xi和yi分別為第i周正常工作時間內(nèi)用于生產(chǎn)食品Ⅰ和Ⅱ的工人數(shù)； 設(shè)si和ti分別為第i周加班時間內(nèi)為食品Ⅰ和Ⅱ加工的工時； 設(shè)wi為從第i周開始抽出來培訓新工人的熟練工人數(shù)； 設(shè)ni為從第i周開始接受培訓的新工人數(shù)； 設(shè)ui和vi分別為第i周于生產(chǎn)食品Ⅰ和Ⅱ的新工人數(shù)； 設(shè)fi和gi分別為第i周末未能按期交貨的食品Ⅰ和Ⅱ的數(shù)量； 設(shè)ki和li分別為第i周末剩余的食品Ⅰ和Ⅱ的數(shù)量； 設(shè)qi和ri分別為第i周內(nèi)對食品Ⅰ和Ⅱ的需求量（如表，已知）。 min z = 360[(x1 + y1 + w1)+(x2 + y2 + w1 + w2)+...+(x7 + y7 + w6 + w7)+(x8 + y8 + w7)] + 120[(n1)+(n1 + n2)+...+(n6 + n7)] + 240[(u3 + v3)+(u4 + v4)+...+(u8 + v8)] + 12[(s1 + t1)+(s2 + t2)+...+(s8 + t8)] + 0.5(f1 + f2 +...+ f8)+ 0.8(g1 + g2 +...+ g8)x1 + y1 + w1 = 50 x2 + y2 + w1 + w2 = 50 … … x7 + y7 + w6 + w7 = 50 x8 + y8 + w7 = 50 ni ? 3 wi，i=1,2,…,7 ui + vi = n3 +...+ni-2，i=3,4,…,8 n1 + n2 +...+ n7 = 50 400xi + 10si + fi = qi + ki，i=1,2 400xi + 400ui + 10si + fi = qi + ki，i=3,4,…,8 240yi + 6ti + gi = ri + li，i=1,2 240yi + 240vi + 6ti + gi = ri + li，i=3,4,…,8 xi，yi，si，ti，fi，gi，ki，li ? 0，i=1,2,…,8 wi，ni ? 0，i=1,2,…,7 ui，vi ? 0，i=3,4,…,8 1.17 設(shè)： xi：第i個月公司雇傭的人數(shù)(i =1,2,…,6)； s.t.zi：第i個月末的庫存量(i =1,2,…,6)； si：第i個月的短缺量(i =1,2,…,6)； ti：第i個月因新增和解雇工人所產(chǎn)生的費用(i =1,2,…,6)； qi：第i個月的需求量（如表，已知）； Max Z = 30?(qi?16i?si)–2000 ?xi?16i–5 ?z–?tii?1i?166i ?zi-1?100xi?si?zi?qi,(i ?1,2,?,6)?t?1500(x-x),(i ?1,2,?,6)ii-1?i??ti?1000(xi-1-xi),(i ?1,2,?,6)s.t ? ?x0?4?z?（該條件原題中沒給）0?0??，6);?xi,zi,si,ti?0,(i ?1,2 1.18 假設(shè)：每月的現(xiàn)金流發(fā)生在月底。x：上一年末的借款數(shù)； yi：第i個月底貸款,(i =1,2,…,11)； zi：第i個月底存款,(i =1,2,…,12)； ci：第i個月的現(xiàn)金需求量（如表，已知）； max Z = z12 s.t.z1 – x – y1 + 0.01x = c1 zi – 1.004zi-1 – yi + 0.01x + 1.015yi-1 = ci,(i =2,3,…,11)z12 – 1.004z11 + 0.01x + x + 1.015yi-1 = c12 x ? 0 yi ? 0，i=1,2,…,11 zi ? 0，i=1,2,…,12第二篇：單純形法matlab程序
第三篇：改進單純形法matlab程序
第四篇：運籌學單純形法matlab程序
第五篇：習題答案選01_線性規(guī)劃和單純形法
點擊咨詢 