实验一：线性规划单纯形算法
一、实验目的
通过实验熟悉单纯形法的原理，掌握Matlab 循环语句的应用,提高编
程的能力和技巧。

二、算法
对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始
基本可行解。

设初始基为B,然后执行如下步骤：
(1).解B Bx b =,求得1B x B b -=，0,N B B x f c x ==令计算目标函数值
1(1,2,...,)i m B b i -=i 以b 记的第个分量
(2).计算单纯形乘子w , B
wB C =,得到1B w C B -=,对于非基变量，计算判别数1i i i B i i z c c B p c σ-=-=-,令 max{}k i i i R z c σ∈=-,R 为非基变量集合
若判别数0k σ≤ ,则得到一个最优基本可行解，运算结束；否则，转到下一
步
(3).解k k By p =,得到1k k y B p -=；若0k y ≤,即k y 的每个分量均非正数，则停止
计算，问题不存在有限最优解，否则，进行步骤(4).
(4).确定下标r,使{}:0min ,0t r
rk tk tk b b tk y y t y y >=>且r B x 为离基变量。

k x 为进基变量，用k
p 替换r B p ，得到新的基矩阵B ，返回步骤（1）。

对于极大化问题，可以给出完全类似的步骤，只是确定进基变量的准则不同。

对于极大化问题，应令
min{}k k j j z c z c -=-
四、计算框图
五、计算程序
function [x,f]=zuiyouhua(A,b,c)
size(A)=[m,n];
i=n+1:n+m;%基变量集合,后面m个松弛变量为初始基变量; N=1:n;%初始非基变量;
B=eye(m,m);
xb=b';
xn=zeros(m,1);
f1=0;
w=zeros(1,m);
z=-c;%初始判别数;
flag=1;
while(1)
[a,k]=max(z);%x(k)为进基变量;
if a<=0
flag=0;
break
else
y=inv(B)*A(:,k)
if y<=0
flag=0;
fprintf('不存在最优解')
break
end
t=find(y>0);
[a,r1]=min(b1(t)./y(t))
r=t(r1); %基变量中第r 个变量为退基变量;
i(:,r)=k
B(:,r)=A(:,k);%换基，即将原基中第ｒ个变量换成第ｋ个变量;
cb=c(:,i);%新的价值系数;
xb=inv(B)*b;
b0=xb;
x=zeros(1,n+m)
x(:,i)=xb'
f=cb*xb
z=cb*inv(B)*A-c;%可用z=cb*(B\A)-c,判别数.
end
end
六、数值实验及结果分析
求解线性规划问题:
⎪⎪⎩⎪⎪⎨⎧=≥≤-=+-=++--4
,3,2,1,012
216443033..3min 21421
3212
1i x x x x x x x x x t s x x i
在工作区输入:
A=[3,3,1,0;-4,-4,0,1;2,-1,0,0];
b=[30,16,12]';
c=[-3,1,0,0];
[x,f]=zuiyouhua(A,b,c)
x =
7.3333 2.6667 0 0 0 56.0000 0
f =
-19.3333
检验结果正确。