西工大最优控制课程 导论20110407.ppt

* * * * * * * * * * 4、Matlab优化工具箱中 求解线性规划的函数为linprog（） 例题 f=[-7;-9;-8]; A=[4.2,6.1,5.3;0.4,0.7,0.3;1.1,1.9,1.4]; b=[8300;3700;4100]; lb=zeros(3,1); [x,fval]=linprog(f,A,b,[],[],lb); 说明：为应用该函数，需将最大值问题变为最小值求解 不等式约束 等式约束 三、非线性规划 1、目标函数和约束条件至少有一个是非线性。 常见的非线性规划----二次型 最优性条件----局部极小点的一阶必要条件 设函数 在点x处可微，且x为局部极小点，则必有 梯度 可将求极值问题化为求x使满足 一般而言该n维方程组是非线性的，难以用解析法求解，因此一般用数值方法直接求极值。 迭代法基本思想：给出极小点的一个初始估计X0，计算一系列Xk（1，2，…），希望点列Xk的极限X*为f（x）的极小点。 点列获得方法：最速下降法，牛顿法等 2、Matlab优化工具箱中，求解无约束非线性规划的函数为fminsearch（）和fminunc() 例：求 Function f=myfun(x) f=3*x(1)^2+2*x(1)*x(2)+x(2)^2; X0=[1,1];%初始值 [x,fval]=fminunc(@myfun,x0); 3、有约束非线性规划 有约束问题取得的最优解可能是局部最优，并且与初始点有关。一般求解有两类方法： （1）间接解 将约束问题转换为无约束问题，如拉格朗日乘子法，消元法等 （2）直接解 在可行域内选取各点的目标函数，找到最小点，如随机试验法，线性逼近法 拉格朗日乘子法 （1）等式约束 构造拉格朗日函数 2、不等式约束 引入松弛因子，约束函数变为 目标函数为 Matlab优化工具箱中，求解有约束最优化的函数为fminbnd(), fmincon(), fseminf(), quadprog(), fminimax() 例:求取 约束条件 初始位置 Function f=myfun(x) F=-x(1)*x(2)*x(3); X0=[10;10;10]; A=[-1,-2,-2;1,2,2];b=[0;27]; [x,fval]=fmincon(@myfun,x0,A,b) 5、其它最优化问题求解 典型问题：TSP问题，背包问题，作业调度问题 难以抽象出合适数学解析式的优化问题 可采用经验推理、人工智能、专家系统等方法 算法包括禁忌搜索算法、模拟退火算法、遗传算法、蚁群优化算法、神经网络、拉格朗日松弛算法等 TSP问题 问题说明：设有n+1个城市，分别用0，1，2…n来表示，从城市i到城市j的距离为dij，一个推销员从城市0出发，到达其它任一城市一次且仅仅一次，然后回到城市0，如何选择行走路线，使总的路程最短？ 旅行商问题特点： 1、实际很多应用问题可转化为该问题，如物资运输路线，管道铺设等； 2、难于求解，可从事有效求解算法的研究 背包问题 设有n种物品，每一种物品数量无限。第i种物品每件重量为wi公斤，每件价值ci元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。 可以用整数规划模型来描述。设第i种物品取xi件（i=1,2,…,n，xi为非负整数)，背包中物品的价值为z，则 6、算法复杂性 算法的时间复杂性函数是问题输入长度的函数，例冒泡排序法对个数为n的整数排序，最坏情形的时间复杂度为 时间复杂度为 算法的时间复杂性函数很多情况下为下列函数之一： 以上按时间复杂度增大排列 存在某个以输入长度n为变量的多项式函数p(n)，使时间复杂性函数为O（p(n)）,称为多项式时间算法，如 算法的复杂度 是指数函数，是无望求解的 NP问题 例：等周问题 图中曲线y=y(x)如何选取，才能在满足边界弧长为定值的条件下，使该图形的面积实现最大 2 面积 其中 弧长约束 7、泛函最优问题 例：最速降线问题 如图所示，在重力作用下，物体由(0,0)点至(x1,y1)点，路径y=y(x)如何可使所用时间为最短？ (0,0) x y (x,y) (x1,y1) 设t时刻物体速度为v，则 (0,0) x y (x,y) (x1,y1) 该问题即求取 函数关系 四、泛函分析的基本概念---空间 空间实际上就是一个集合，且该集合中的元素之间具有某些特定的联系和性质。 1、线性空间 在非空集合X中规定了元素的加法和数乘线性运算，加法和数乘运算的结果仍包含于X中。 2、距离空间 设X为非空集合，