实 验 二 ： MATLAB 编 程单纯形法求解

精品资料

精品资料

仅供学习与交流，如有侵权请联系网站删除 谢谢

仅供学习与交流，如有侵权请联系网站删除 谢谢 PAGE #

精品资料

精品资料

精品资料

精品资料

仅供学习与交流，如有侵权请联系网站删除谢谢

仅供学习与交流，如有侵权请联系网站删除谢谢2

北京联合大学

实验报告

项目名称：运筹学专题实验报告

学

院：

自动化

专

业：

物流工程

班

级：

1201B

学

号:

2012100358081

姓

名：

管水城

成

绩：

2015年 5 月 6 日

实验二：MATLAB编程单纯形法求解

一、实验目的:

使学生在程序设计方面得到进一步的训练；，掌握Matlab (C 或VB)语言进 行程序设计中一些常用方法。

使学生对线性规划的单纯形法有更深的理解.

二、实验用仪器设备、器材或软件环境

计算机，Matlab R2006

三、算法步骤、计算框图、计算程序等

本实验主要编写如下线性规划问题的计算程序：

min ex

Ax b

st.

x 0,b0

其中初始可行基为松弛变量对应的列组成.

对于一般标准线性规划问题：

min ex

Ax b

st.

x 0,b0

1 ?求解上述一般标准线性规划的单纯形算法(修正)步骤如下：

对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始基本可

行解。设初始基为B,然后执行如下步骤：

1

解Bxb b求得Xb B b 令Xn 0,计算目标函数值f CbXb

以b (i 1,2,..., m)记B 1b的第i个分量

1

.计算单纯形乘子w, wB Cb,得到w cbB ,对于非基变量，计算判别

数i乙Ci CbB 1pi Ci ,可直接计算cBB 1A e令

k max{ } ,R为非基变量集合

i R

若判别数k 0 ,则得到一个最优基本可行解，运算结束；否则，转到下一

步

1

.解Byk Pk,得到％ B Pk ；若％ °,即％的每个分量均非正数，

则停止计算，问题不存在有限最优解，否则，进行步骤(4).确定下标r,使

阪吧叫莎,且ytk0XBr为离基变量,

Xk为进基变量,用Pk替换PBr,得到新的基矩阵B,还回步骤(1)；

J

2、计算框图为：

xBr为退基变量，xk进基变量，以

Pk代替pBr,得到新的基矩阵B

3 ?计算程序(Matlab):

A=i nput(

'A=');

b=in put(

'b=');

c=in put(

'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); if (n

D=[E,F];

%创建一个一一映射，为了结果能够标准输出

X=zeros(1, n); if (n

%初始化X

%判断是否为标准型

fprintf('不符合要求需引入松弛变量')

flag=O;

else

flag=1;

B=A(:, n-m+1: n);

%找基矩阵

cB=c( n-m+1: n);

while flag

%基矩阵对应目标值的c

w=cB/B;

%计算单纯形乘子，cB/B=cB*inv(B),用cB/B的

目的是，为了提高运行速度

pan bieshu=w*A-c

后能够显示出来。。

%计算判别数,后面没有加分号，就是为了计算

[z,k]=max(pa nbieshu);

% k作为进基变量下标。。

fprintf('b''./(B\\A(:,%d))为’,k);

b'./(B\A(:,k))

精品资料

精品资料

仅供学习与交流，如有侵权请联系网站删除谢谢

仅供学习与交流，如有侵权请联系网站删除谢谢 PAGE #

精品资料

精品资料

仅供学习与交流，如有侵权请联系网站删除谢谢

仅供学习与交流，如有侵权请联系网站删除谢谢 PAGE #

fprintf( xB=(B\b')'; f=cB*xB';

'已找到最优解!\n');

for

i=1: n

mark=0;

for j=1:m

if (D(j,2)==i)

%所有判别数都小于O时达到最优解

mark=1;

if (zvO.OOOOOOOOl)flag=O;X(i)=xB(D(j,1));%利用D找出xB与X

if (zvO.OOOOOOOOl)

flag=O;

关系。。

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