实验二:MATLAB编程单纯形法求解Word下载.docx
《实验二:MATLAB编程单纯形法求解Word下载.docx》由会员分享,可在线阅读,更多相关《实验二:MATLAB编程单纯形法求解Word下载.docx(9页珍藏版)》请在冰点文库上搜索。
二、实验用仪器设备、器材或软件环境
计算机,MatlabR2006
三、算法步骤、计算框图、计算程序等
本实验主要编写如下线性规划问题的计算程序:
其中初始可行基为松弛变量对应的列组成.
对于一般标准线性规划问题:
1.求解上述一般标准线性规划的单纯形算法(修正)步骤如下:
对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始基本可行解。
设初始基为B,然后执行如下步骤:
(1).解,求得,
(2).计算单纯形乘子w,,得到,对于非基变量,计算判别数,可直接计算令
R为非基变量集合
若判别数,则得到一个最优基本可行解,运算结束;
否则,转到下一步
(3).解,得到;
若,即的每个分量均非正数,
则停止计算,问题不存在有限最优解,否则,进行步骤(4).确定下标r,使
;
2、计算框图为:
开始
初始可行基B
是
否
得到最优
否
不存在有限
确定下标r,使得
图1
3.计算程序(Matlab):
A=input('
A='
);
b=input('
b='
c=input('
c='
formatrat%可以让结果用分数输出
[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:
%基矩阵对应目标值的c
whileflag
w=cB/B;
%计算单纯形乘子,cB/B=cB*inv(B),用cB/B的目的是,为了提高运行速度。
。
panbieshu=w*A-c%计算判别数,后面没有加分号,就是为了计算后能够显示出来。
[z,k]=max(panbieshu);
%k作为进基变量下标。
fprintf('
b'
'
./(B\\A(:
%d))为'
k);
b'
./(B\A(:
k))
if(z<
0.000000001)
flag=0;
%所有判别数都小于0时达到最优解。
fprintf('
已找到最优解!
\n'
xB=(B\b'
)'
f=cB*xB'
fori=1:
n
mark=0;
forj=1:
m
if(D(j,2)==i)
mark=1;
X(i)=xB(D(j,1));
%利用D找出xB与X之间的关系。
end
end
ifmark==0
X(i)=0;
%如果D中没有X(i),则X(i)为非基变量,所以X(i)=0。
end
fprintf('
基向量为:
X
目标函数值为:
);
f
else
if(B\A(:
k)<
=0)%如果B\A(;
k)中的每一个分量都小于零。
flag=0;
fprintf('
\n此问题不存在最优解!
%若B\A(:
k)的第k列均不大于0,则该问题不存在最优解。
else
b1=B\b'
temp=inf;
fori=1:
if((A(i,k)>
0)&
&
(b1(i)/(A(i,k)+eps))<
temp)
temp=b1(i)/A(i,k);
%找退基变量
r=i;
end
end
x(%d)进基,x(%d)退基\n'
k,D(r,2));
%显示进基变量和退基变量
B(:
r)=A(:
cB(r)=c(k);
%确定进基退基变量后,相应的基矩阵及新基对应的目标值的c也相应改变
D(r,2)=k;
%改变D中的映射关系
end
end
end
程序保存为danchunxin.m 文件
四.数值实验及其结果:
打开matlab软件,点击运行danchunxin.m,出现命令符要求输入相应矩阵命令。
1.求解:
输入数据矩阵如下:
A=[94100;
45010;
310001]
b=[360200300]
c=[-7-12000]
点击运行得如下图:
图2
由实验结果可知,该问题的最优解为:
x1=100,x2=0,x3=540,x4=200,x5=0,最大值为700。
2.求解:
A=[-3-2-1-6-1810;
-1-0.5-0.2-2-0.501;
0.510.220.800]
b=[-700-30200]
c=[2749500]
图3
x1=15200/33,x2=0,x3=0,x4=0,x5=1250/33,x6=0,最小值为:
1235/3。
3.求解:
A=[1-2110;
4-1-201;
-20100]
b=[11-31]
c=[3-1-100]
图4
由实验结果可知,该线性问题不存在最优解。
五.实验总结
通过该实验,加深了对线性规划问题的理解,并加深了将实际问题进行数学建模转化为可利用MATLAB软件处理的线性规划问题,通过使用该软件,能充分的将复杂的线性规划问题通过编写程序实现相应的逻辑求解线性规划问题,在实际操作过程中,大大的减少了线性规划问题的运算的复杂性。
编写函数程序代码是遇到了很多问题,但在老师的帮助下,逐一的解决了,为进行下面的实验奠定了一定的基础。