091单纯形法

发布时间：2020-03-02 11:55:42 来源：范文大全收藏本文下载本文手机版

2013-2014（1）专业课程实践论文

题目：单纯形法求解线性规划

一、算法理论

对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始基本可行解。设初始基为B,然后执行如下步骤：

(1)解BxBb,求得xBB1b，令xN0,计算目标函数值fcBxB以bii1,2,,m记B1b的第i个分量。

(2)计算单纯形乘子w, wBCB,得到wCBB1,对于非基变量，计算判别数izicicBB1pici,令 kmaxzici,R为非基变量集合。若判别数

iRk0,则得到一个最优基本可行解，运算结束；否则，转到下一步。 (3)解Bykpk,得到ykB1pk；若yk0,即yk的每个分量均非正数，则停止计算，问题不存在有限最优解，否则，进行步骤(4)。

btbrmin，且ytk0， xB为离基变量。xk为进基变(4)确定下标r,使yrkt:ytk0ytk量，用Pk替换PBr，得到新的基矩阵B，返回步骤（1）。

对于极大化问题，可以给出完全类似的步骤，只是确定进基变量的准则不同。对于极大化问题，应令

ZkCkminzjcj

二、算法框图

三、算法程序

function [x,fval,it,op]=singl(c,a,b) %求解如下线性规划问题的单纯形法函数

%max cx

其中c=[c1 c2 ...cn] %s.t ax=0) %函数形式 function [x,fval,it,op]=singl(c,a,b) %输出中 x为最优解 %fval为最优值

%it为迭代次数

%无最优解 op=0

%有最优解 op=1 %初始解设为x=[zeros(1,n),ones(1,m)]; [m,n]=size(a); A=[a eye(m) b;c zeros(1,m+1)];

C=[c,zeros(1,m)]; fval=0; op=1; it=0; e=zeros(1,m); cb=zeros(1,m); for j=1:m+n

r(j)=C(j)-cb*A(1:m,j); end d=find(r>0); l=length(d); while l>0

for s=1:l

if d(s)>=n+1 & A(:,d(s))

op=0;

break

end

if op==1

[d1,j]=max(r);

for i=1:m

if A(i,j)>0

e(i)=A(i,end)/A(i,j);

else

e(i)=inf;

end

[g h]=min(e);

for w=1:m+1

if w==h

A(w,:)=A(w,:)/A(h,j);

else

A(w,:)=A(w,:)-A(h,:)*A(w,j)/A(h,j);

end

it=it+1;

cb(h)=C(j);

for j=1:m+n

r(j)=C(j)-cb*A(1:m,j);

end

d=find(r>0);

l=length(d);

end end for i=1:(m+n)

ix=find(A(:,i));

if(length(ix)==1)&(ix

x(i)=A(ix,end);

else

x(i)=0;

end end fval=-A(end,end);

四、算法实现

例1.用单纯形法求解

minz2x13x2,x12x210, 3x1x215,x1,x20.stx1x22,解：(1)在MATLAB界面中依次输入

c=[2 3]; a=[-1 1;1 2; 3 1]; b=[2;10;15]; [x,fval,it,op]=singl(c,a,b) (2)得到下图所示的结果（其中it为迭代次数，无最优解 op0，有最优解op1）。

(3)从图中读出最优解：x14,x23,x33,x4x50，

若把引进的松弛变量略去，则最优解为x*4,3,最优值为

Tz*17。

例2.用单纯形法求解

minstz2x13x2,x12x28,4x116,4x212,x1,x20.

解：(1)在MATLAB界面中依次输入

c=[2 3]; a=[1 2;4 0; 0 4]; b=[8;16;12]; [x,fval,it,op]=singl(c,a,b) (2)得到下图所示的结果（其中it为迭代次数，无最优解 op0，有最优解op1）。

(3)从图中读出最优解：x14,x22,x30,x40,x54，

若把引进的松弛变量略去，则最优解为x*4,2,最优值为

Tz*14。

例3.用单纯形法求解

maxstzx12x2x3,x1x2x312,2x1x2x36, x13x29,x1,x2,x30.解：(1)在MATLAB界面中依次输入

c=[1 -2 1]; a=[1 1 1;2 1 -1;-1 3 0]; b=[12;6;9]; [x,fval,it,op]=singl(c,a,b) (2)得到下图所示的结果（其中it为迭代次数，无最优解 op0，有最优解op1）。

(3)从图中读出最优解：x16,x20,x36,x40,x50,x615，

若把引进的松弛变量略去，则最优解为x*6,0,6,最优值为

Tz*12

例4.用单纯形法求解

minstz2x1x23x35x4,x12x24x3x46,2x13x2x3x412, x1x3x44x1,x2,x3,x40.解：(1)在MATLAB界面中依次输入

c=[2 1 -3 5]; a=[1 2 4 -1;2 3 -1 1; 1 0 1 1]; b=[6;12;4]; [x,fval,it,op]=singl(c,a,b) (2)得到下图所示的结果（其中it为迭代次数，无最优解 op0，有最优解op1）。

(3)从图中读出最优解：

814x10,x2,x30,x44,x5,x60,x70，

338若把引进的松弛变量略去，则最优解为x0,,0,4,最优值为

3*Tz*68。 3

将本文的Word文档下载到电脑，方便编辑。

推荐度：

点击下载文档