091单纯形法_作业1单纯形法

091单纯形法由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“作业1单纯形法”。

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

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

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

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