第一篇：線性規(guī)劃單純形法matlab解法

線性規(guī)劃單純形法matlab解法

%單純形法matlab程序-ssimplex % 求解標(biāo)準(zhǔn)型線性規(guī)劃:max c*x;s.t.A*x=b;x>=0 % 本函數(shù)中的A是單純初始表，包括:最后一行是初始的檢驗(yàn)數(shù)，最后一列是資源向量b % N是初始的基變量的下標(biāo)

% 輸出變量sol是最優(yōu)解, 其中松弛變量（或剩余變量）可能不為0 % 輸出變量val是最優(yōu)目標(biāo)值，kk是迭代次數(shù) % 例：max 2*x1+3*x2 % s.t.x1+2*x2<=8 % 4*x1<=16 % 4*x2<=12 % x1,x2>=0 % 加入松馳變量，化為標(biāo)準(zhǔn)型，得到 % 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 % 問(wèn)題有無(wú)界解 disp('have infinite solution!');flag=0;break;end end if flag % 還不是最優(yōu)表，進(jìn)行轉(zhuǎn)軸運(yùn)算 temp=0;for i=1:nA-1 if A(mA,i)>temp temp=A(mA,i);inb=i;% 進(jìn)基變量的下標(biāo) 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

第二篇：?jiǎn)渭冃畏╩atlab程序

算法實(shí)現(xiàn)與分析

算法1．單純形法 具體算例：

minz=?3x1+x2+2x3 3x1+2x2?3x3=6 x1?2x2+x3+x5=4

x1,x2,x3≥0標(biāo)準(zhǔn)化后：

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];%價(jià)值矩陣 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))

第三篇：改進(jìn)單純形法matlab程序

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

第四篇：運(yùn)籌學(xué)單純形法matlab程序

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;

第五篇：習(xí)題答案選01_線性規(guī)劃和單純形法

運(yùn)籌學(xué)教程（胡運(yùn)權(quán)主編，清華版）部分習(xí)題答案（第一章）

1.5 記可行集4個(gè)頂點(diǎn)分別為O:(0,0)，A:(1.6,0)，B:(1,1.5)，C:(0,2.25)當(dāng)c=0，d=0時(shí)，四邊形OABC中的點(diǎn)都是最優(yōu)解 當(dāng)c=0，d>0時(shí)，頂點(diǎn)C是最優(yōu)解

當(dāng)c=0，d<0時(shí)，線段OA上的點(diǎn)都是最優(yōu)解 當(dāng)c>0，d/c<2/5時(shí)，頂點(diǎn)A是最優(yōu)解

當(dāng)c>0，d/c=2/5時(shí)，線段AB上的點(diǎn)都是最優(yōu)解 當(dāng)c>0，2/50，d/c=4/3時(shí)，線段BC上的點(diǎn)都是最優(yōu)解 當(dāng)c>0，d/c>4/3時(shí)，頂點(diǎn)C是最優(yōu)解 當(dāng)c<0，d<0時(shí)，頂點(diǎn)O是最優(yōu)解

當(dāng)c<0，d=0時(shí)，線段OC上的點(diǎn)都是最優(yōu)解 當(dāng)c<0，d>0時(shí)，頂點(diǎn)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周正常工作時(shí)間內(nèi)用于生產(chǎn)食品Ⅰ和Ⅱ的工人數(shù)； 設(shè)si和ti分別為第i周加班時(shí)間內(nèi)為食品Ⅰ和Ⅱ加工的工時(shí)； 設(shè)wi為從第i周開始抽出來(lái)培訓(xùn)新工人的熟練工人數(shù)； 設(shè)ni為從第i周開始接受培訓(xùn)的新工人數(shù)；

設(shè)ui和vi分別為第i周于生產(chǎn)食品Ⅰ和Ⅱ的新工人數(shù)； 設(shè)fi和gi分別為第i周末未能按期交貨的食品Ⅰ和Ⅱ的數(shù)量； 設(shè)ki和li分別為第i周末剩余的食品Ⅰ和Ⅱ的數(shù)量；

設(shè)qi和ri分別為第i周內(nèi)對(duì)食品Ⅰ和Ⅱ的需求量（如表，已知）。

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個(gè)月公司雇傭的人數(shù)(i =1,2,…,6)； s.t.zi：第i個(gè)月末的庫(kù)存量(i =1,2,…,6)； si：第i個(gè)月的短缺量(i =1,2,…,6)；

ti：第i個(gè)月因新增和解雇工人所產(chǎn)生的費(fèi)用(i =1,2,…,6)； qi：第i個(gè)月的需求量（如表，已知）；

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?（該條件原題中沒(méi)給）0?0??，6);?xi,zi,si,ti?0,(i ?1,2 1.18 假設(shè)：每月的現(xiàn)金流發(fā)生在月底。x：上一年末的借款數(shù)；

yi：第i個(gè)月底貸款,(i =1,2,…,11)； zi：第i個(gè)月底存款,(i =1,2,…,12)； ci：第i個(gè)月的現(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