单纯形法的matlab实现极小化问题.doc
- 文档编号:2504374
- 上传时间:2023-05-03
- 格式:DOC
- 页数:9
- 大小:338.50KB
单纯形法的matlab实现极小化问题.doc
《单纯形法的matlab实现极小化问题.doc》由会员分享,可在线阅读,更多相关《单纯形法的matlab实现极小化问题.doc(9页珍藏版)》请在冰点文库上搜索。
实验报告
实验题目:
单纯形法的matlab实现
学生姓名:
学号:
实验时间:
2013-4-15
一.实验名称:
单纯形法的MATLAB实现
二.实验目的及要求:
1.了解单纯形算法的原理及其matlab实现.
2.运用MATLAB编辑单纯形法程序解决线性规划的极小化问题,求出最优解及目标函数值.
三.实验内容:
1.单纯形方法原理:
单纯形方法的基本思想,是从一个基本可行解出发,求一个使目标函数值有所改善的基本可行解;通过不断改进基本可行解,力图达到最优基本可行解.
对问题
其中A是一个m×n矩阵,且秩为m,为n维行向量,为n维列向量,为m维非负列向量.符号“”表示右端的表达式是左端的定义式,即目标函数的具体形式就是.
记
令=(B,N),B为基矩阵,N为非基矩阵,设
是基本可行解,在处的目标函数值
其中是中与基变量对应的分量组成的m维行向量;是中与非基变量对应的分量组成的n-m维行向量.
现由基本可行解出发求解一个改进的基本可行解.
设是任一可行解,则由得到
在点处的目标函数值
其中R是非基变量下标集,
.
2.单纯形方法计算步骤:
首先给定一个初始基本可行解,设初始基为B,然后执行下列主要步骤:
(1)解,求得,令,计算目标函数值.
(2)求单纯形乘子,解,得到.对于所有非基变量,计算判别数.令
.
若,则对于所有非基变量,对应基变量的判别数总是为零,因此停止计算,现行基本可行解是最优解.否则,进行下一步.
(3)解,得到,若,即的每个分量均非正数,则停止计算,问题不存在有限最优解.否则进行步骤(4).
(4)确定下标r,使
x=,
为离基变量,为进基变量.用替换,得到新的基矩阵B,返回步骤
(1).
3.单纯形方法表格形式:
表3.1.1
右
端
0
1
0
表3.1.2(3.1.1略去左端列后的详表)
假设,由上表得.
若,则现行基本可行解是最优解.
若,则用主元消去法求改进的基本可行解.先根据选择主列,再根据找主行,主元为,然后进行主元消去,得到新单纯形表.表的最后一行是判别数和函数目标值.
四.实验流程图及其MATLAB实现:
1.流程图开始
:
初始基本可行解B
解,求得,令,计算目标函数值
求单纯形乘子,解,得到.对于所有非基变量,计算判别数.令
Y
N
解,得到
现行基本可行解是最优解
N
Y
确定下标r,使x=
赋以正的大值N
Y
N
min=N
问题不存在有限最优解
为离基变量,为进基变量.用替换,得到新的基矩阵B
2.代码及数值算例:
(1)程序源代码:
function[x,f]=DCmin(c,A,b,AR,y0,d)
%x:
最优解
%f:
目标函数最优值
%c:
目标函数系数向量
%A:
系数矩阵
%b:
m维列向量
%AR:
松弛变量系数矩阵
%y0:
基矩阵初始向量
%d:
补充向量(非目标系数向量,为一零向量)
N=10000;
B=[A,AR,b];
[m,n]=size(B);
C=[c,d];
y=y0;
x=zeros(1,length(c));
fork=1:
N
k;
z=B(:
end);%右端
forj=1:
n-1
t(j)=y*B(:
j)-C(j);%检验数
end
t;
f=y*z;
%%========选取主元==========%%
%---------选取主列---------%
[alpha,q]=max(t);
q;
W(k)=q;%x下标矩阵
%-------------------------%
%--------选取主元----------%
forp=1:
m
ifB(p,q)<=0
r(p)=N;
elser(p)=z(p)/B(p,q);
end
end
[beta,p]=min(r);
p;
y(p)=C(q);
%-------------------------%
%%==========================%%
B(p,:
)=B(p,:
)/B(p,q);
fori=1:
m
ifi~=p
B(i,:
)=B(i,:
)-B(p,:
)*B(i,q);
end
end
ifmax(t)<=0
break;
end
B;
end
%++++++++++++++++++++++++++++++++++++++%
Z=B(:
end);
iflength(x(W))~=length(Z)
x=char('NONE');
f=char('NONE');
disp('不存在有限最优解');
elsex(W)=Z';
end
(2)数值算例:
例3.1.2用单纯形方法解下列问题
引进松弛变量x,x,问题标准化:
(i)输出命令:
>>c=[1-21];A=[11-21;2-140;-12-40];b=[10;8;4];AR=[00;10;01];y0=[000];d=[000];
>>[x,f]=DCmin(c,A,b,AR,y0,d)
(ii)运行结果:
B=
11-210010
2-140108
-12-40014
k=
1
t=
-12-1000
f=
0
B=
1.5000001.00000-0.50008.0000
1.500002.000001.00000.500010.0000
-0.50001.0000-2.0000000.50002.0000
k=
2
t=
00300-1
f=
-4
B=
1.5000001.00000-0.50008.0000
0.750001.000000.50000.25005.0000
1.00001.0000001.00001.000012.0000
k=
3
t=
-2.2500000-1.5000-1.7500
f=
-19
x=
0125
f=
-19
五.总结:
在单纯形法求解过程中,每一个基本可行解x都以某个经过初等行变换的约束方程组中的单位矩阵为可行基.对于极大化的线性规划问题,先标准化,即将极大化问题变换为极小化问题:
然后利用单纯形方法求解.
六.参考文献:
陈宝林编著《最优化理论与算法》清华大学出版社2005年10月第2版
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 单纯 matlab 实现 极小 问题