《线性规划(lp)》由会员分享，可在线阅读，更多相关《线性规划(lp)（18页珍藏版）》请在金锄头文库上搜索。
1、 16.323 讲课讲课 16 线性规划（LP） 二次规划（QP） 混合整数线性规划（MILP） ? Bertsimas，D.，和 Tsitsiklis，J.N.，线性优化导论，雅典娜科学出版社，1997。 ? Floudas， C.A.， 非线性和混合整数优化： 基础和应用， 牛津大学出版社， 1995。 ? 很好的在线资源位于： http:/people.brunel.ac.uk/mastjjb/jeb/or/contents.html 笔记由 Yoshiaki Kuwata 准备 2006 年 5 月 9 日 2006年春季年春季 16.323 16-1 线性规划（线性规划（LP） ?
2、流行的数值优化：线性规划 - 应用范围很宽（调度问题，数据拟合，通信网络，路径规划，等等） - 很多求解器可以用（ “linprog” （MATLAB） ，GLPK（GNU）1，CPLEX，等等） - 求解快速：有数百决策变量和约束的问题不用 1 秒。 - 可以求解巨大问题，有几十万变量和约束的问题2 ? 约束：都是线性（代价，决策变量和约束） xminc xT受约束于 xb,xb ,xeqeqnAA=R? 约束集构成nR上的多面角区域。 - n维多面体中的x，称作可行解可行解 - 代价向量c给出梯度信息 - 最优解在多面体的顶点上 1 http:/plato.asu.edu/topics/p
3、roblems/nlores.html 2 http:/www.maths.ed.ac.uk/or41/talks_v26t/SP.htm 讨论了一个有 1250 万个约束和 2500 万变量的问题求解 2006 年 5 月 9 日 2006年春季年春季 16.323 16-2 图 1：线性规划中的可行区域（2n =） 。虚线显示的是代价的等高线。最优点*x用做了记号。 ? LP 一些特征 - 敏感度分析：一旦得到了优化解，可以有效地获得扰动问题的解 - 网络流量问题的整数公式 2006 年 5 月 9 日 2006年春季年春季 16.323 16-3 例子：生产规划例子：生产规划 ? 问题叙
4、述3 - 可以生产三种不同的计算机系统 - 最大化收入 - 由于调试容量，CPU 的供给最多提供 7,000 单元 - 磁盘驱动的供给范围为 3,000 到 7,000 单元 - 存储器板的供给范围为 8,000 到 16,000 单元 - 按照市场部门，每个系统的最大需求量是 GP-1 为 1,800，GP-3 为 300，总数为 3,800。 ? 线性规划形式 - 决策变量ix：生产的计算机 GP-i的#要1,000 123max 604030xxx+ 12312123131270.31.7342281.80.3xxxxxxxxxxxx+受约束于 33.8x+3 Bertsimas 书的
5、1.2 节 2006 年 5 月 9 日 2006年春季年春季 16.323 16-4 ? Matlab 解： 2006 年 5 月 9 日 2006年春季年春季 16.323 16-5 例子：最优控制问题例子：最优控制问题 ? 给出初始和终端位置，最小化飞行器在操作过程中使用的燃料。 - 用固定的终端时间N，以离散时间设计。 - 飞行器使用的燃料力向量u的绝对值 ? 时间步进为t，离散时间的线性动态为 101min( )unNii kic u k=0s.t. x(1)x( )u( ), 0,1x( )q , 0,u( )q , 0,1x(0)x ,xxuukAkBkkNPkkNPkkN+=+
6、=x()x ,fN =其中 2r( )0.5x( ), , v( )kItIt IkABkOItI=。 ? 转换 1范数表达式到线性形式的技巧是引入一个松弛变量 min( ) min( )s.t. ( )( )( )( )iiiiiis k u ks ku ks ku k ? 然后，得到的 LP 看起来像 xminc x s.t. xb,xbTeqeqAA=? ?其中，问题的变量是 xu (0),u (1),s (0),s (1),x (0),x ()TTTTTTTNNN=? 2006 年 5 月 9 日 2006年春季年春季 16.323 16-6 LP 的形式的形式 ? 在 MATLAB
7、中，可以按照下列形式调用“linprog” ? 使用松弛变量s，转换不等式约束为等式约束 , 0axb axsbs +=? 则，LP 的标准形式为 xminc xs.t. xb,x0TA = 。- n个变量，m个约束 - A矩阵的大小为mn。典型的，mn?（A是个“宽”矩阵） - 多面体是n维 x|xb,x0nRA=P 2006 年 5 月 9 日 2006年春季年春季 16.323 16-7 单纯形法单纯形法 ? 典型求解方法4 - 单纯形法单纯形法：使用智能方法访问每个顶点 事实上最优解在多面体的顶点（G.Dantzig，1947） 。 - 内点法内点法：在多面体中使用椭圆（Karmark
8、ar，1984） ? 解算法的可能结果 - 最优 - 可行，但不是最优 - 不可行 - 无界（最优代价为） ? 单纯形法 - 最基本的求解 LP 的方法 - 利用最优解在多面体的顶点的事实 - 一个接一个的访问多面体的顶点（叫作基本可行解） ，并不断改善目标函数 - 有限次迭代终止 4 Ami Arbel 使用内点线性规划：算法和软件（计算的基础） 2006 年 5 月 9 日 2006年春季年春季 16.323 16-8 图 2：单纯形迭代的图形解释 ? 基本可行解（BFS）x - 点xnRP，其中n个线性独立约束有效。 - xbA =中m个约束，x0中()nm个约束。 在 BFS，至少()
9、nm个x的元素是 0 - 可以看到这实际上是多面体的顶点 ? 如果x是 BFS，可能把x分成两个部分，且有下列性质： - “基本”变量(x)m BR - “非基本”变量()(x,x0)n m NN=R - 不失一般性，可以把问题写为 xx,x.BN ABN= =其中B列是线性独立的 2006 年 5 月 9 日 2006年春季年春季 16.323 16-9 ? 过程 0. 从 BFSx开始。 1. 从xN中选择一个元素jx。注意当前0jx =。 （选择j的方法随后给出。 ） 2. 计算移动的可行方向d，其中 dddBN=- dN的要求：对应于jx的元素，1jd =和0jd =（ij ） 。 -
10、 怎样解Bd？因为d是可行方向， (xd)b,0A+=。 既然x是 BFS，xbA =。比较这两项d0A=。 1d 00d0d1 01BBjABNB A = ?。 其中jA是A的第j列（对应于jx的N列） 。 3. 计算步的大小 移动直到到达约束 *max0|xdmax0|xd0=+=+P （xd+P意味着(xd)bA+=而且xd0+，但是对于我们的选择的d，等式约束自动满足） 。 0id 的行没有约束，这样 *|0max|,(,0)miniii iidiixxi ddd = =2006 年 5 月 9 日 2006年春季年春季 16.323 16-10 4. 更新 *x: xd=+ 可以看到
11、这个新的x是个 BFS。 5. 返回第 1 步。 ? 最后剩下的问题：怎样在第 1 步从xN选取jx - 检查代价的作用。首先，由等式约束 11xbxb xbxxB BN NABNBB N=则，目标函数可以写为 11c xc xc xcb(cc)xTTT BBNNTTT BNBNBB N=+=+如果沿着基本方向移动，项( )i是代价函数的作用。与jx相关的部分是 1c:jjBjccB A?“简化代价” 通过改变jx，对代价有两个作用：第一项jc对应于jx的直接作用；而第二项是满足等式约束xbA =必要性的xB的变化的作用。 - 选择给出最佳改善的jx（0jc且有最大绝对值） 。 - 如果0c，
12、则x是最优的。终止。 2006 年 5 月 9 日 2006 年春季年春季 16.323 16-11 二次规划二次规划 ? 另外一种流行的数值优化方法 - 代价为二次的，约束是线性的 - 许多 MPC 优化使用这种形式 Tx1minxxc x s.t. xb,2x0 THA+=- 凸优化（无局部最小） - 使用对偶&基本单纯形法，内点法，障碍算法，等等，MATLAB“quadprog” 。 ? 更复杂的凸优化 - 二次约束规划：代价和约束都是二次的。 ? 二阶锥规划5 - 半定规划，线性矩阵不等式（LMI）6：决策变量是矩阵形式。 ? 许多鲁棒控制问题可以转化为这种形式。 ? 易处理，但是不容
13、易在线实现。 - 自由求解工具 SeDuMi7和 Matlab 接口 YALMIP8对这种问题都是可用的 5 http:/www.stanford.edu/-boyd/socp.html 6 http:/www.stanford.edu/class/ee363/lmi-s-proc.pef 7 http:/sedumi.mcmaster.ca/ 8 http:/control.ee.ethz.ch/-joloef/yalmip.php 2006 年 5 月 9 日 2006年春季年春季 16.323 16-12 混合整数线性规划混合整数线性规划 ? 线性规划的扩展9 - 一些决策变量只取整数/二进制值；其他取连续值混合线性规划（MILP） - 在问题公式中进行“逻辑”编码，例如 A 或者 B10 - 广泛的应用领域：混合系统11，避免约束12，非凸约束，任务分派，等等。 - 通过分段线性函数逼近也可以处理非线性函数13 - 比 LP 求解更难 - 求解器：GLPK（G
