单纯形法的matlab实现极小化问题文档格式.doc
《单纯形法的matlab实现极小化问题文档格式.doc》由会员分享，可在线阅读，更多相关《单纯形法的matlab实现极小化问题文档格式.doc（9页珍藏版）》请在冰点文库上搜索。
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
右
端
1
表3.1.2（3.1.1略去左端列后的详表）
假设,由上表得.
若,则现行基本可行解是最优解.
若,则用主元消去法求改进的基本可行解.先根据选择主列,再根据找主行,主元为,然后进行主元消去,得到新单纯形表.表的最后一行是判别数和函数目标值.
四．实验流程图及其MATLAB实现:
1.流程图开始
:
初始基本可行解B
解,求得,令,计算目标函数值
求单纯形乘子,解,得到.对于所有非基变量,计算判别数.令
Y
N
解,得到
现行基本可行解是最优解
确定下标r,使x=
赋以正的大值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
[beta,p]=min（r）;
p;
y（p）=C（q）;
%%==========================%%
B（p,:
）=B（p,:
）/B（p,q）;
fori=1:
ifi~=p
B（i,:
）=B（i,:
）-B（p,:
）*B（i,q）;
ifmax（t）<
break;
B;
end
%++++++++++++++++++++++++++++++++++++++%
Z=B（:
iflength（x（W））~=length（Z）
x=char（'
NONE'
）;
f=char（'
disp（'
不存在有限最优解'
elsex（W）=Z'
;
（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
1.5000001.00000-0.50008.0000
1.500002.000001.00000.500010.0000
-0.50001.0000-2.0000000.50002.0000
2
00300-1
-4
0.750001.000000.50000.25005.0000
1.00001.0000001.00001.000012.0000
3
-2.2500000-1.5000-1.7500
-19
x=
0125
五．总结:
在单纯形法求解过程中,每一个基本可行解x都以某个经过初等行变换的约束方程组中的单位矩阵为可行基.对于极大化的线性规划问题,先标准化,即将极大化问题变换为极小化问题:
然后利用单纯形方法求解.
六．参考文献:
陈宝林编著《最优化理论与算法》清华大学出版社2005年10月第2版
升级会员 