大连民族学院
数学实验报告
课程：____________________ 最优化方法______________________ 实验题目： ___________ 单纯形法的matlab实现 ___________________ 系别：______________________ 理学院________________________ 专业：__________________ 信息与计算科学____________________ 姓名：__________________________________________________ 班级：_____________________ 信息102班 ____________________ 指导教师：___________________ 葛仁东_______________________ 完成学期：2013 年__9 ___________ 月_2________ 日
实验目的：
实验方法和步骤(包括数值公式、算法步骤、程序) ：
考察标准形式的线性规划问题：
min f(x) C T x
s.t Ax b, x 0
设x(k)F为一个基本可行解，单纯形方法首先检验它的最优性。

如果它不是最优的，确定与该顶点相连的一条使目标函数下降的边；接下来确定沿这个边移
动多远可以到达另一个更优的相邻点，也就是得出一个新的基本可行解
算法步骤：
步骤1给定一个初始基本可行解，记迭代次数 k 1 ；
步骤2 :计算单纯形乘子y k B k T c B k)和简约价值系数向量C N k) c N k) N T y k ； 步骤3 :最优性检验，计算C?k) min{C (k)|j 2}，如果C?k) 0，则x (k)为最优解，
停止迭代；否则有x p 0，选x p 为入基变量；
步骤4:确定出基变量，计算g k) B k 1a p ，如果对所有j B k ，有器)0,则问题
无有界的最优解，停止迭代；否则确定出基变量指标
步骤5:交换B k 的列a q 与N k 的列a p 得到新的基矩阵 盼和山+1，计算新的基本可 行解
x (k1),置k:k 1后转步骤
2；
在上述算法中，当存在不止一个简约价值系数 C j k) 0时，选取最负的©“的 指标为p ，并以X p 作为入基变量。

Matlab 计算程序：
Function] x,f]=zuiyouhua(A,b,c) Size(A)=[m, n]; i=n+1: n+m; N=1: n;
B=eye(m,m); xb=b '; xn=zeros(m,1); f1=0; w=zeros(1,m); z=-c; flag=1; while(1) [a,k]=max(z); If a<=0 flag=0; break else
y=i nv(B)*A(:,k)
b (k)
B k }；
min{ _(k )殆 0, j
if y<=0
flag=O;
fprintf( '不存在最优解’)
break
end
t=fi nd(y>0);
[a,rl]=mi n(bl(t)/y(t)) r=t(rl);
i(:,k)=k
B(:,k)=A(:,k); cb=C(:,i); xb=i nv(B)*b; bO=xb;
x=zeros(1, n+m) x(:,i)=xb '
f=cb*xb z=cb* in v(B)*A-C;
end
end
实验数据和分析：
根据题意，可以列出以下8种可能的切割方案，其目标是使总剩余的废料最小。

设X“X2L x8分别代表采用切割方案1~8的套数，f(x)表示总剩余的废料, 则上述问题的线性规划如下：
min f (x)0.1x10.3X20.9x3 0x4 1.1x50.2X60.8x7 1.4x8
2X1X2 x3x4100
2X2 X33X52X,X7100
st
x1x33X42X63X74X8100
X1,X2,X3,X4,X5,X6,X7,X 0
在matlab的输入区域输入：
A=[2,1,1,1,0,0,0,0;0,2,1,0,3,2,1,0;1,0,1,3,0,2,3,4];
b=[100,100,100 ]';
c=[,,,0,,,,]；
[x,f]=zuiyouhua(A,b,c)
Matlab输出内容：
x=10 50 0 30 0 0 0 0
f=-16
结果分析：
可以看出只需要90根原料，其中，方案1需要10根，方案2需要50根, 方案4需要30根，即可达到要求，此时总剩余废料最小，为16m
附：
万案合计余料
1201
2120
3111
41030
5030
6022
7013
80046
实验的启示：
通过本次实验加深了我对单纯形法的进一步理解，利用matlab程序求解线性规划问题，在生活中有不少问题都是线性规划问题。

例如本次实验中的钢材
下料问题，学习用已学习的知识解决实际问题是我们的最终目标。