修正单纯形法求解约束优化问题_最优化单纯形法解例

修正单纯形法求解约束优化问题由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“最优化单纯形法解例”。

修正单纯形法求解约束优化问题

姓名 王铎 学号 2007021271 班级 机械078 日期 2010/6/23

一．问题分析

求解约束优化问题中，假如目标函数和约束条件都是线性的，像这类约束函数和目标函数都是线性函数的优化问题称作线性规划问题。从实际问题中建立数学模型一般有以下三个步骤：

1.根据影响所要达到目的的因素找到决策变量；

2.由决策变量和所在大道目的之间的函数关系确定目标函数； 3.有决策变量所受的限制条件确定决策变量所要满足的约束条件；

求解线性规划问题的基本方法是单纯形法，而本文研究的是修正单纯形法。1965 年由J.A.Nelder 等提出。是在基本单纯形优化法的基础上，引入了反射、扩展与收缩等操作规则，变固定步长推移单纯形为可变步长推移单纯形，在保证优化精度的条件下，加快了优化速度。是各种单纯形优化法在分析测试中应用最广的一种。二．数学模型

1、线性规划问题的formalization 问题(1.1)称为线性规划问题： x= arg min_x c^T x s.t.Ax=b x>=0(1.1)其中x为n维列向量，A为m*n的矩阵，b和c分别为m,n维的常数向量。

任意一个线性不等式组约束下求解线性函数的最大最小值问题都可以归结到问题(1.1)来。

比如

A(i,:)x A(i,:)x + y(i)= b(i)y(i)>=0(1.2)A(i,:)x >= b(i)A(i,:)xB^-N x_N(1.5)代入c^T x: z=c^Tx =c_B^T B^-bB^-N x_NB^(B^-N)(i,:)=0，此时该问

题无最优解）=> l=min{(B^-b)(j)/(B^-N)(i,j), j=1,2,...,m } 若l=(B^-b)(r)/(B^-N)(i,r)，则x_r=0,x_i=l 把x_i添入x_B，把x_r添入x_N，再用上述过程进行计算

3、有效单纯形法

每次将x_i入基x_r出基时，B要变动，此时导致无论用x_N表示x_B(1.5)还是c^Tx(1.6)都要重新计算一遍B^-，如何利用B变动前后的关系有效计

算(1.5,1.6)就是有效单纯形法所要解决的问题。假设变动后的B为B'，B^-为已知。因为 B' x'_B + N' x'_N= b' 所以

B^-B' x'_B + B^-N' x'_N = B^-b' => x'_B =(B^-B')^-(B^-b'c_B^T B^-N x_N + c_N^T x_N(1.6)x_N的系数全部为正，此时达到最优，则-c_B^T B^-N + c_N^T >=0 => c_N-N^Tw >=0 => A^Tw=[B , N]^T w=[B^Tw;N^Tw]

对偶定理： 原问题和对偶问题中若一方有最优解，则另一方也有最优解，且两个问题的最优值一致。

6、灵敏度分析。

主要一个结论：

在(1.1)中b的微小变化不影响最优基的选择，而b的增加将引起c^Tx的增加，其增加的比例dc^Tx/db_i=w_i，b的减小将引起c^Tx的减小。

下面说明这一点 假设(1.1)变为 x= arg min_x c^T x s.t.Ax=b+db x>=0(1.11)若，此

时

仍

成立

B^-(b+db)>=0，即x'=[x'_B,x'_N]=[B^-(b+db),0]>=0则有c_N^T-c_N^TB^-N>=0，最优条件仍旧满足（就是c^Tx用x_N表出后，所有系数非负仍旧成立），因此B仍为扰动之后的最优基。

7.流程图

三．计算程序

function [y,A]=danchun(A,x,y)[m,n]=size(A);if min(A(1,1:n-1))

f = inline('2x(1).^2+(x(2)-3).^2')[x fval flag] = danchun(f , [0;0])x =

0

1.0000 fval = 8.0064e-027 flag =四．计算结果分析

经检验计算结果符合约束且为优化最优解

单纯形法求解原理过程

单纯形法需要解决的问题：如何确定初始基本可行解；如何由一个基本可行解迭代出另一个基本可行解，同时使目标函数获得较大的下降； 如何判断一个基本可行解是否为最优解。 min f(X)......

无约束优化算法：单纯形法

单纯形法1.算法原理单纯形法的基本思想是：设x,x,...,x(0)(1)(n)是Rn中的n1个点，构成一个当前的单纯形，xmax,xmin定义如下：f(xmax)maxf(x(0)),f(x(1)),...,f(x(n)) f(xmin)minf(x......

单纯形法

单纯形法单纯形法，求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最......

单纯形法

public cla Linear{ public static double[] c={-3,-2,0,0,0,0}; public double W(double x[]) {return c[0]*x[0]+c[1]*x[1]+c[2]*x[2]+c[3]*x[3]+c[4]*x[4]+c[5];} public......

单纯形法

2.2 单纯形法考虑标准最大化线性规划问题的(1.15)maxcxjj1njnaijxjbi s.t.j1xj0i1,2,...,mj1,2,...,n我们首先对它的第i个约束条件引入松弛变量si,i1,2,...,m,并且以表示目......