单纯形法的matlab实现(极小化问题).docVIP

实验报告

实验题目:单纯形法的matlab实现

学生姓名:

学号:

实验时间:2013-4-15

一．实验名称:单纯形法的MATLAB实现

二．实验目的及要求:

1.了解单纯形算法的原理及其matlab实现.

2.运用MATLAB编辑单纯形法程序解决线性规划的极小化问题,求出最优解及目标函数值.

三．实验内容:

单纯形方法原理:

单纯形方法的基本思想,是从一个基本可行解出发,求一个使目标函数值有所改善的基本可行解;通过不断改进基本可行解,力图达到最优基本可行解.

对问题

其中A是一个m×n矩阵,且秩为m,为n维行向量,为n维列向量,为m维非负列向量.符号“”表示右端的表达式是左端的定义式,即目标函数的具体形式就是.

记

令=(B,N),B为基矩阵,N为非基矩阵,设

是基本可行解,在处的目标函数值

,

其中是中与基变量对应的分量组成的m维行向量;是中与非基变量对应的分量组成的n-m维行向量.

现由基本可行解出发求解一个改进的基本可行解.

设是任一可行解,则由得到

,

在点处的目标函数值

,

其中R是非基变量下标集,

.

单纯形方法计算步骤:

首先给定一个初始基本可行解,设初始基为B,然后执行下列主要步骤:

解,求得,令,计算目标函数值.

求单纯形乘子,解,得到.对于所有非基变量,计算判别数.令

.

若,则对于所有非基变量,对应基变量的判别数总是为零,因此停止计算,现行基本可行解是最优解.否则,进行下一步.

解,得到,若,即的每个分量均非正数,则停止计算,问题不存在有限最优解.否则进行步骤（4）.

确定下标r,使

x=,

为离基变量,为进基变量.用替换,得到新的基矩阵B,返回步骤（1）.

单纯形方法表格形式:

右

端

0

1

0

表3.1.2（3.1.1略去左端列后的详表）

假设,由上表得.

若,则现行基本可行解是最优解.

若,则用主元消去法求改进的基本可行解.先根据选择主列,再根据找主行,主元为,然后进行主元消去,得到新单纯形表.表的最后一行是判别数和函数目标值.

四．实验流程图及其MATLAB实现:

1.流程图开始:

开始

初始基本可行解B

初始基本可行解B

解,求得,令

解,求得,令,计算目标函数值

求单纯形乘子,解

求单纯形乘子,解,得到.对于所有非基变量,计算判别数.令

YN

Y

N

解,得到

解,得到

现行基本可行解是最优解

现行基本可行解是最优解

NY

N

Y

确定下标r,使x=赋以正的大值N

确定下标r,使x=

赋以正的大值N

YNmin=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