欢迎来到我的范文网!

r,规划求解

自我介绍 时间:2020-08-04

【www.myl5520.com--自我介绍】

线性规划的求解算法
篇一:r,规划求解

线性规划的求解算法

线性规划(linear programming)是运筹学中的一个重要分支,在现代工业、

农业、商业、交通运输、国防军事及经济管理等诸多领域都有着广泛重要的应用。在数学系的竞赛数学建模中,也多次应用线性规划来建模从而解决实际问题。在这里介绍单纯性法和对偶单纯形法两种求解线性规划的方法。

一、单纯形法算法主体思想 标准线性规划简记如下:

LP-max LP-min s.t {

Ax?bx?0

Ax?bx?0

s.t {

这里只以LP-min为例。

1、算法思想

单纯形法是在已知一个可行基的前提下采用的解决线性规划的算法。步骤

如下:

?a01a02?a11a12?

(1)输入初始矩阵:?

?

?am1am2

(2)求min

a0,n?1?a1,n?1??

?,并化为典则形式。 ?am,n?1?

用R(i)记录单位矩阵I中元素1的位置。

?j|a

0j

?0,1?j?n?t

r,规划求解。

若t不存在,则得到最优解;xR(i)停。否则,转到(3)。

?ai,n?1 (i=1,2,...m).其他xj=0,

ai,n?1

|ait?0,1?i?m}?。 (3)求min{ait

?

不存在,则LP-min无下届,所以无最优解,停;否则,求

ai,n?1??

min?R(i)|??,ait?0,1?i?m?r,规划求解。

ait??

R(s),转到(4)。

asj

(4)asj?(j=1,2....n+1)

ast,

aij

?aij?asjait,(i=0,1,2...m;i?s;j=1,2,....,n+1),

R(s)?t,转到(2).

二、对偶单纯形法

对偶单纯形法是在已知一个正则基的条件下的求解线性规划的方法。步骤如下:

?a01a02

?a11a12?

(1)输入初始矩阵:?

?

?am1am2

(2)求min

a0,n?1?a1,n?1??

?,并化为典则形式。 ?am,n?1?

用R(i)记录单位矩阵I中元素1的位置。

?j|a

0j

?0,1?j?n?s

若s不存在,则得到最优解;xR(i)停。否则,转到(3)。

?ai,n?1 (i=1,2,...m).其他xj=0,

ai,n?1

|ait?0,1?i?m}?。 (3)求min{ait

?

不存在,则LP-min无下届,所以无最优解,停;否则,求

ai,n?1??

min?R(i)|??,ait?0,1?i?m?

ait??

R(s),转到(4)。

asj

(4)asj?(j=1,2....n+1)

ast,

aij

?aij?asjait,(i=0,1,2...m;i?s;j=1,2,....,n+1),

R(s)?t,转到(2).

三、程序代码 1、单纯形法。

% 求解标准型线性规划:max c*x; s.t. A*x=b;x>=0

%A1是标准系数矩阵及最后一列是资源向量,C是目标函数的系数向量 % N是(初始的)基变量的下标 %M=10000 人工变量系数

% 本函数中的A是单纯形表,包括:最后一行是初始的检验数,最后一列是资源向量b %c1是基变量系数

%输出变量sol是最优解

%输出变量val是最优值,k是迭代次数

%flag1的值代表有无最优解,0无界解,1无可行解,2无穷多解,3唯一最优解

function [sol,val,k,flag1]=ssimplex(A1,C,N) M=10000;

[mA1,nA1]=size(A1); C1=[C,0];

val=zeros(1,length(C)); for i=1:length(N) c1(i)=C1(N(i)); end

for i=1:nA1

a(i)=C1(i)-c1*A1(:,i);%计算初始检验数 end

A=[A1;a]; %构造初始单纯形表 [mA,nA]=size(A); k=0; % 迭代次数 flag=1; while flag

for i=1:(nA-1) if A(mA,i)<=0 flag=0; else

flag=1;

break; end end

if flag==0 % 已找到最优解 val1=A(1:(mA-1),nA)'; for i=1:length(N)

if (val1(i)~=0&&abs(C(N(i)))==M)

disp('无可行解'); sol=inf;val=inf; flag3=0; flag1=1; break; else

flag3=1; end end

if flag3

if length(find(A(mA,1:(nA-1))==0))>length(N) disp('存在无穷多最优解'); flag1=2; else

disp('存在最优解'); flag1=3; end

sol=c1*val1'; end

elseif flag==1 for j=1:(mA-1) if A(j,i)<=0 flag2=1; else

flag2=0;break; end

end

if flag==1&&flag2==1

disp('此线性规划问题存在无界解'); sol=inf; val=inf; flag1=0;

flag=0; %跳出while循环 break; end

maxq=max(A(mA,1:(nA-1)));

[m,nb]=find(A(mA,:)==maxq); %确定入基变量的纵坐标

for s=1:(mA-1) if A(s,nb)>0

temp(s)=A(s,nA)/A(s,nb); elser,规划求解。

temp(s)=10000; end end k=k+1;

mino=min(temp);

[n,mb]=find(temp==mino); %确定入基变量的横坐标 if length(mb)>1 mb=mb(1); end

ab=A(mb,nb); A2=A;

for i=1:(mA-1) for j=1:nA if i==mb

A(mb,j)=A2(mb,j)/ab; else

A(i,j)=A2(i,j)-A2(i,nb)*(A2(mb,j)/ab); end end end

for i=1:length(N) if i==mb

N(i)=nb; end end

for i=1:length(N) c1(i)=C(N(i)); end

for i=1:nA

A(mA,i)=C1(i)-c1*A(1:(mA-1),i); end end end

if sol~=inf

for i=1:length(C) for j=1:length(N) if i==N(j)

val(i)=val1(j); end end

无约束非线性规划求解方法及其实现
篇二:r,规划求解

无约束非线性规划求解方法及其实现

作者:杨玲 指导老师:陈素根

摘要:

非线性规划是具有非线性约束条件或目标函数的数学规划,是运筹学的一个重要分支。非线性规划属于最优化方法的一种,是线性规划的延伸。非线性规划研究一个n元实函数在一组灯饰或不等式的约束条件下的极值问题,且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。非线性规划是20世纪50年代才形成的一门新兴学科。1951年H.W库恩和

A.W塔克发表的关于最优性条件的论文是非线性规划正是诞生的一个重要标志。在50年代还得出了可分离规划和二次规划的n种解法,它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解线性规划问题的有效的算法,70年代又得到进一步的发展。非线性规划在工程,管理,经济,科研,军事等发面都有广泛的应用,为最优设计提供了有力的工具。20世纪80年代以来,随着计算机技术的快速发展,非线性规划在信赖域法、稀疏牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果,无约束非线性规划问题是非线性规划的一个重要内容,很多学者对非线性规划问题进行了深入且系统的研究,研究成果丰硕。

关键词 最优化 共轭梯度法 非线性 无约束r,规划求解。

1 引言

1.1 无约束非线性规划问题是最基本的非线性规划问题,在1959~1963年幼三位数学家共同研究成功求解无约束问题的DFP变尺度法,该算法的研究成功是无约束优化算法的一个大飞跃,引起了一系列的理论工作,并陆续出现了许多新的算法。20世纪80年代以来,随着计算机技术的快速发展,非线性规划在信赖域法、稀疏牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果。无约束非线性规划问题是非线性规划的一个重要内容,很多学者对非线性规划问题进行了深入且系统的研究,研究成果丰硕。

1.2 本文主要研究无约束非线性规划问题,将文章分成四个部分,首先会具体介绍无约束非线性规划的相关概念,并在此基础上研究非线性规划的相关理论与基本算法问题,接着详细介绍无约束非线性规划的几种主要的求解方法,最后举例说明他在实际生活中的应用,并编程实现它。

2 正文

2.1主要介绍无约束非线性规划的相关概念

一个非线性规划问题的自变量x没有任何约束,或说可行域即是整个n维向量空间:x?Rn错误!未找到引用源。,则称

这样的非线性规划问题为无约束问题:错误!未找到引用源。或错误!未找到引用源。 。

一般我们研究的无约束非线性规划问题大都可以归结为求无约束最优化问题。

2.2 介绍无约束非线性规划的几种主要的求解方法及其实现

求解无约束非线性规划问题就是求解无约束非线性规划最优化

nminfx,x?R??的问题,可以表述为。它的求解方法有许多种,

大体上可以概括为两大类,一是直接法,二是解析法。解析法又被称为代数法,值得是通过计算f?x?的一阶,二阶偏导数及其函数的解析性质来实现极值的求解方法。相应的,不必计算f?x?的一阶、二阶偏导数及其函数的解析性质,仅用到函数值来实现近似值的求解方法叫直接法。

1. 先介绍直接法中的一维搜索方法,包括Fibonacci法和0.618法。

一维搜索方法就是在用迭代法沿某一已知方向求目标函数极小点的方法,常用的由斐波那契法和黄金分割法。

f?t?,若f?t?是?a,b?区间上的下单考虑一维极小值问题mina?t?b

f?t?峰函数,我们将通过不断的缩短?a,b?的长度,来探索mina?t?b

的近似最优解。在?a,b?中任意取两个关于?a,b?是对称的点t1和t1(不妨设,t2?t1并称它们为搜索点),计算f?t1?与f?t2?并

比较它们的大小。对于单峰函数,若f?t1??f?t2?,则必有t*??a,t1?

则有因而,?a,t1?是缩短了的单峰区间,若f?t2??f?t1?,?t,b?是缩短了的单峰区间,若,故2t*??t2,b?

f?t2??f?t1?,则?a,t1?和?t2,b?都是缩短了的单峰。因而通过两个搜索点处目标函数值大小的比较,总可以获得缩短了的单峰区间。对于新的单峰区间重复上述做法,又可以获得更短的单峰区间。如此下去,在单峰区间缩短到充分小时,可以取最后的

f?t?最优解的近似值,下面介绍斐波那契法搜索点作为mina?t?b

来选取搜索点,使给定的单峰区间的长度能尽快缩短。

Fibonacci法:

若数列?Fn?满足关系:F0?F1?1,Fn?Fn?2?Fn?1,

,则称Fn为Fibonacci数列,Fn称为第n个n?2,3,

Fn?1Fibonacci数,称相邻两个Fibonacci数之比F为Fibonacci分

n

数。当用斐波那契法以n个探索点来缩短某一区间时,区间长度Fn?2Fn?3Fn?1,,的第一次缩短率为,其后各次分别为Fn?1Fn?2Fn

由此,若t1和t2,F1,,F2?t2?t1?单峰区间?a,b?中的第1个和第2

t2?aFn?2t1?aFn?1?个探索点的话,则应有比例关系b?a?F,从b?aFnn,

而t1?a?

的点。 Fn?1Fn?2b?a??t2?a??b?a?,它们关于a,b是对称FnFn,??

如果要求经过一系列探索点搜索之后,使最后的探索点和最优解之间的距离不超过精度??0,这也要求最后区间的长度不超过?b?ab?a????。由此,按照预先给定的精度?,确定使,即FnFn

成立的最小整数n作为搜索次数,直到进行第n次探索点为止。

f?t?的近似用上述不断缩短函数f?x?单峰区间的方法来求mina?t?b

解是Kiefer(1953年)提出的,叫Fibonacci法。具体步骤如下: 1选取初始数据,确定单峰区间?a0,b0?,给出搜索精度??0,由b?a??确定搜索次数n; Fn

2k?1,a?a0,b?b0,计算最初两个搜索点,按

Fn?1Fn?2t1?a?b?a??t2?a??b?a?计算t1t2; ,FnFn,

3while k?n?1

f1?f?t1?f2?f?t2? ,

if f1?f2

Fn?1?kt?a??b?a? a?t2;t2?t1;1Fn?k;

else

本文来源:http://www.myl5520.com/fanwendaquan/116690.html

推荐内容