单纯形算法MATLAB编程报告.docx

机械优化设计
课程作业

题 目： 单纯形程序算法
学 院： 机电工程学院
专 业： 机械工程

2016年 4 月 24 日

基于MATLAB的单纯形算法实现
一. 算法简述
为求解下面线性规划问题：

其中初始可行基为松弛变量对应的列组成.
对于一般标准线性规划问题:

１．求解上述一般标准线性规划的单纯形算法步骤如下：
对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始基本可行解。设初始基为B,然后执行如下步骤：
(1).解,求得，

(2).计算单纯形乘子w, ,得到,对于非基变量，计算判别数,可直接计算令
,R为非基变量集合
若判别数 ,则得到一个最优基本可行解，运算结束；否则，转到下一步
(3).解,得到；若,即的每个分量均非正数，
则停止计算，问题不存在有限最优解，否则，进行步骤(4).确定下标r,使

二. 算法框图
初始化

初始可行基B

是

否
输出结果，得到最优解
结束

是

否
不存在有限最优解
确定下标r,使得

高斯迭代

三． 计算程序
Clear %清空工作区
Clc %清空命令输入框
A=input('A=');
b=input('b=');
c=input('c=');
format rat %可以让结果用分数输出
[m,n]=size(A); %取维数
E=1:m;E=E';
F=n-m+1:n;F=F';
D=[E,F]; %创建一个一一映射，为了结果能够标准输出
X=zeros(1,n); %初始化X
if(n<m) %判断是否为标准型
fprintf('不符合标准形式需引入松弛变量')
flag=0;
else
flag=1;
B=A(:,n-m+1:n); %找基矩阵
cB=c(n-m+1:n); %基矩阵对应目标值的c
while flag
w=cB/B %计算单纯形乘子，cB/B=cB*inv(B),左除相当于求逆
panbieshu=w*A-c %计算判别数,后面没有加分号，就是为了计算后能够显示出来
[z,k]=max(panbieshu) % k作为进基变量下标
fprintf('确定下标并选择进基变量和离基变量为\n',k);
b'./(B\A(:,k)) %这个式子是为了确定进基变量和离基变量的下标
if(z<0.00000000001) %为了使判别数尽可能趋近于零
flag=0; %所有判别数都小于0时达到最优解
fprintf(' 已找到最优解!\n');
xB=(B\b')';
f=cB*xB';
for i=1:n
mark=0;
for j=1:m
if (D(j,2)==i)
mark=1;
X(i)=xB(D(j,1)) %利用D找出xB与X之间的关系
end
end
if mark==0
X(i)=0; %如果D中没有X(i),则X(i)为非基变量，所以X(i)＝0
end
end
fprintf('基向量为:'); X
fprintf('目标函数值为:') ; f
else
if(B\A(:,k)<=0) % 如果B\A(;,k)中的每一个分量都小于零
flag=0;
fprintf(' \n 此问题不存在最优解!\n'); %若B\A(:,k)的第k列均不大于0，则该问题不存在最优解
else
b1=B\b';
temp=inf;
for i=1:m
if ((A(i,k)>0) && (b1(i)/(A(i,k)+eps))<temp )
temp=b1(i)/A(i,k); %找离基变量
r=i;
end
end
fprintf('x(%d)进基，x(%d)离基\n',k,D(r,2)); %显示进基变量和离基变量
B(:,r)=A(:,k)
cB(r)=c(k) %确定进基离基变量后，相应的基矩阵及新基对应的目标值的c也相应改变
D(r,2)=k; %改变D中的映射关系

end
end
end
end
【备注：文件名字为danchunxing11zly.m】

四. 使用方法以及运算实例
在命令窗口中输入 run danchunxing11zly，然后依次按照提示完成约束以及目标函数的矩阵。
例1：min
S.t
窗口输入 run danchunxing11zly
A=[1 1 -2 1 0 0;2 -1 4 0 1 0;-1 2 -4 0 0 1];
b=[10 8 4];
c=[1 -2 1 0 0 0]
运行结果为：
w =

0 0 0

panbieshu =

-1 2 -1 0 0 0

z =

2

k =

2

确定下标并选择进基变量和离基变量为

ans =

10
-8
2

x(2)进基，x(6)离基

B =

1 0 1
0 1 -1
0 0 2

cB =

0 0 -2

w =

0 0 -1

panbieshu =

0 0 3 0 0 -1

z =

3

k =

3

确定下标并选择进基变量和离基变量为

ans =

1/0
4
-2

x(3)进基，x(5)离基

B =

1 -2 1
0 4 -1
0 -4 2

cB =

0 1 -2

w =

0 -3/2 -7/4

panbieshu =

-9/4 0 0 0 -3/2 -7/4

z =

0

k =

2

确定下标并选择进基变量和离基变量为

ans =

1/0
1/0
4

已找到最优解!

xB =

8 5 12

f =

-19

X =

0 12 0 0 0 0

X =

0 12 5 0 0 0

X =

0 12 5 8 0 0

基向量为:
X =

0 12 5 8 0 0

目标函数值为:
f =

-19

例2： max
S.t
命令窗口中输入: run danchunxing11zly
A=[1 1 2 1 0;1 4 -1 0 1]
b=[6 4]
c=[-2 -1 1 0 0]
运行结果为：
w =

0 0

panbieshu =

2 1 -1 0 0

z =

2

k =

1

确定下标并选择进基变量和离基变量为

ans =

6
4

x(1)进基，x(5)离基

B =

1 1
0 1

cB =

0 -2

w =

0 -2

panbieshu =

0 -7 1 0 -2

z =

1

k =

3

确定下标并选择进基变量和离基变量为

ans =

2
-4

x(3)进基，x(4)离基

B =

2 1
-1 1

cB =

1 -2

w =

-1/3 -5/3

panbieshu =

0 -6 0 -1/3 -5/3

z =

0

k =

1

确定下标并选择进基变量和离基变量为

ans =

1/0
4

已找到最优解!

X =

14/3 0 0 0 0

X =

14/3 0 2/3 0 0

基向量为:
X =

14/3 0 2/3 0 0

目标函数值为:
f =

-26/3