用matlab解决运筹学中的LP问题

Question

用matlab编程，使用单纯形法解决LP问题
只需解决max：z=CX,AX≤B，X≥0的情况即可。
我不要那么麻烦的，只需要解决上面那种情况就行

Answer 1

http://www.ilovematlab.cn/viewthread.php?tid=29019
这里有，里面还有 说明 文档。

以下是，采用大M法及字典序规则的 单纯型法 算法 参考程序：
function [x,f]=Lps_Mlex(c,A,b,M,N,pre)
% [x,f]=Lps_Mlex(c,A,b,M,N,pre) 采用单纯型法中的
% 大M法，并给字典序规则解下列线性规划
% min f=ct*x s.t. Ax=b,x 所有分量 >=0
% M是一个充分大的数，N是引进人工变量的个数，N应不超过
% （通常等于）约束等式的个数，pre 是精度
% 返回结果 x 是最优解，f 是最优解处的函数值

[m,n]=size(A);
if nargin<6,pre=0;end;if nargin<5,N=0;end
if N>m,error('N不能超过约束条件的个数m');
else,
A=[A,[zeros(N,m-N);eye(m-N)]];
c=[c(:)',zeros(1,m-N)];
A=[A,eye(m)];c=[c,M*ones(1,m)];
m1=n+m-N+1:n+2*m-N;B=A(:,m1);
x=zeros(n+2*m-N,1);x=x(:);
tb=find(b<0);b(tb)=-b(tb);A(tb,:)=-A(tb,:);
xB=B\b;x(m1)=xB;f=c*x;
criterion=c(m1)*(B\A)-c;[z1,z2]=max(criterion);
while z1>pre
az2=B\A(:,z2);
if z2<=pre,x=nan*ones(length(c));break
else,t1=find(az2>pre);p=[xB,B\eye(size(B))];pp=[];
for kk=1:length(t1);
pp(kk,:)=p(t1(kk),:)./az2(t1(kk));
end
tt1=min(xB(t1)./az2(t1));[tt0,tt2]=lex_min(pp);
t3=t1(tt2);B(:,t3)=A(:,z2);x(m1)=xB-tt1*az2;
m1(t3)=z2;x(z2)=tt1;f=c(m1)*xB;xB=x(m1);
criterion=c(m1)*(B\A)-c;[z1,z2]=max(criterion);
end,end,end;
if sum(x(n+m-N+1:n+2*-N))<=pre*m
x(m1)=xB;f=c(1:n)*x(1:n);x=x(1:n);
else,x=nan*ones(length(c));x=x(:);x=x(1:n);
end

% 例子
% f=[0;0;0;-3/4;20;-0.5;6];
% a=[0.25,-8,-1,9;0.5,-12,-0.5,3;0,0,1,0];
% a=[eye(3),a];b=[0;0;1];vlb=zeros(7,1);
% x=linprog(f,[],[],a,b,vlb); %用来做对比的
% xx=Lps_Mlex(f,a,b,100000,3);[x,xx]

function [y,k]=lex_min(x)
% [y,k]=lex_min(x) 按行求矩阵x 字典序最小行向量
% 返回值 y 是 矩阵 x 字典序最小行向量，k 是 y 在 x 中的行数

[mx,nx]=size(x);k=1;y=x(1,:);
if mx==1,k=1;y=x(1,:);
else,
[t1,t2]=min(x);t3=zeros(mx,nx);
for i=1:nx;t3(:,i)=t1(i)*ones(mx,1);end
t4=sum((t3~=x));tt=find(t4~=0);
k=t2(tt(1));y=x(k,:);
end

分别保存为 Lps_Mlex.m 和 lex_min.m 文件
这已经很简单了

Answer 2

根据题意我用一个例子来说明吧：
max f=10*x1+11*x2
5x1+7x2<=75
6x1+8x2<=100
x1,x2>=0
如题
c=[10;11];
a=[5 7;6 8];
b=[75;100];
[x,fmax]=linprog(-c,a,b,[],[],zeros(2,1))
格式[x,y]=linprog(c,a,b,aeq,beq,LB,UB,X0,OPTIONS)

看楼上的吧，没看清你说的是单纯形法，呵呵