This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
keynote:2011-lesson13 [2011/06/09 09:54] 11021081 [基本可行解] |
keynote:2011-lesson13 [2023/08/19 21:02] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== 第十三课 ====== | ||
+ | **最优化方法** | ||
+ | ====== 内容 ====== | ||
+ | * 线性规划 | ||
+ | * 非线性优化 | ||
+ | ====== 主要参考书: ====== | ||
+ | |||
+ | * 线性规划,张建中,许绍吉,科学出版社 | ||
+ | * 最优化理论与方法,袁亚湘,孙文瑜,科学出版社 | ||
+ | ====== 基本理论 ====== | ||
+ | |||
+ | ===== 问题定义 (Linear Programming,LP)===== | ||
+ | 在一组线性的等式或不等式约束下,求一个线性函数的最小值或最大值。\\ | ||
+ | **形式化的定义:**\\ | ||
+ | <jsmath>\min\ c_1x_1+...+c_nx_n </jsmath> | ||
+ | s.t. | ||
+ | <jsmath>a_{11}x_1+...+a_{1n}x_n\le b_1</jsmath> | ||
+ | <jsmath>...</jsmath> | ||
+ | <jsmath>a_{m1}x_1+...+a_{mn}x_n\le b_m</jsmath> | ||
+ | <jsmath>x_1,...,x_n \ge 0</jsmath> | ||
+ | 即:\\ | ||
+ | min **c<sup>T</sup>x**\\ | ||
+ | s.t. A**x**≤**b**, **x**≥0\\ | ||
+ | 其中,**c:**价值向量,**A:**约束矩阵,**b:**右端向量,**x:**满足约束条件,称为可行解或可行点\\ | ||
+ | |||
+ | **LP问题:**\\ | ||
+ | D:所有可行点的集合,称为可行区域\\ | ||
+ | D=∅,无解或不可行\\ | ||
+ | D≠∅,但目标函数在D上无上界:无界\\ | ||
+ | D≠∅,且目标函数有限的最优解:有最优解\\ | ||
+ | |||
+ | **线性规划在Matlab中的实现方法**\\ | ||
+ | Matlab中规定线性规划的标准形式为:\\ | ||
+ | min **c<sup>T</sup>x** s.t. A**x**≤**b**\\ | ||
+ | 其中,**c**和**x**为n维列向量,**b**为m维列向量,**A**为m*n矩阵\\ | ||
+ | 基本函数形式为:\\ | ||
+ | linprog(c, A, b)\\ | ||
+ | 返回值是向量x的值\\ | ||
+ | 调用举例:\\ | ||
+ | [x,fval]=linprog(c, A, b, Aeq, beq, LB, UB, X0, OPTIONS)\\ | ||
+ | fval返回目标函数的值,\\ | ||
+ | Aeq、beq对应等式约束,AeqX = beq\\ | ||
+ | LB、UB分别是变量X的下界和上界,X0是X的初始值\\ | ||
+ | OPTIONS是控制参数。\\ | ||
+ | |||
+ | |||
+ | <note important> --- //[[1@1|李昌英]] 学号:11021081 2011/06/08//</note> | ||
+ | ===== 标准LP问题 ===== | ||
+ | 从实际中总结出来的LP形式不完全一样:\\ | ||
+ | * 目标函数是最大值或最小值, | ||
+ | * 约束条件是等式约束或不等式约束, | ||
+ | * 变量有上界或下界或无界 | ||
+ | 标准LP问题形式:\\ | ||
+ | min z=**c<sup>T</sup>x**\\ | ||
+ | s.t. A**x**=**b**, **x**≥**0**\\ | ||
+ | 将LP问题标准化: | ||
+ | 目标函数的转换 $\max\ z->\min\ (-z)$\\ | ||
+ | 约束条件的转换(引入松弛变量) | ||
+ | <jsmath>\sum_{j=1}^{n}{a_{ij}x_j\le b_{i}} | ||
+ | <=> | ||
+ | \sum_{j=1}^{n}{a_{ij}x_j+x_{n+i}}=b_i, x_{n+i}\ge 0</jsmath> | ||
+ | 变量的非负约束: | ||
+ | <jsmath>x_j\ge l_j | ||
+ | <=> | ||
+ | y_j\ge0, y_j=x_j-l_j</jsmath> | ||
+ | <jsmath>x_j自由变量 | ||
+ | <=>u_j\ge0, v_j\ge0, x_j=u_j-v_j</jsmath> | ||
+ | |||
+ | |||
+ | <note important> --- //[[1@1|李昌英]] 学号:11021081 2011/06/08//</note> | ||
+ | ====== 可行区域 ====== | ||
+ | |||
+ | **定义:** 可行区域是所有满足约束条件的可行点的集合,记为D | ||
+ | |||
+ | D={x| Ax=b, x≥0}\\ | ||
+ | |||
+ | 首先讨论集合 K={ x | Ax = b }\\ | ||
+ | * **仿射集**:对于集合S⊆E<sup>n</sup>,如果对任意x, y∈S, λ∈E<sup>1</sup>, 都有λx+(1-λ)y∈S,则称S为仿射集。 | ||
+ | 一般仿射集的特征:给定 mxn 实矩阵 A 和 b∈E<sup>m</sup>,则 K={x∈E<sup>n</sup> | Ax=b} 为 E<sup>n</sup> 中的仿射集,并且E<sup>n</sup>中的任一仿射集均可表成此种形式。\\ | ||
+ | 集合 K={ x | Ax = b }为 E<sup>n</sup> 仿射集。\\ | ||
+ | * **凸集**:对任意的x, y∈C,λ∈(0,1),有 λx+(1-λ)y∈C,则C为凸集。 | ||
+ | 可行区域 D={x|Ax=b,x≥0}为凸集。\\ | ||
+ | * **界面**:可行区域D的子集D’为D的一个界面当且仅当存在指标集合Q⊆{1,…,n},使得D’={x|Ax=b,x≥0,且xj=0当j∈Q} | ||
+ | 若dim(D)= n-m, D’为D的界面,且dim(D’)=n-m-k,则|Q|≥k. | ||
+ | * **极点**:凸集C的1维界面称为边(edge), 0维界面称为极点(extreme point)。若两个极点在同一条边上,称它们是相邻的。 | ||
+ | * **极方向**:设C≠Ø为En中的一个凸集,d∈En,d≠0。若对任一x∈C及λ>0,均有x+λd∈C,则称d为C的一个方向。 | ||
+ | 如果一个方向d不能表成两个方向的正线性组合,就成d是C的极方向(extreme direction)。 | ||
+ | |||
+ | |||
+ | <note important> --- //[[1@1|李昌英]] 学号:11021081 2011/06/09//</note> | ||
+ | |||
+ | <note important> --- //[[1@1|桂立业]] 学号:11024012 2011/06/20//</note> | ||
+ | |||
+ | <note important> --- //[[1@1|刘雨]] 学号:10924010 2011/06/21//</note> | ||
+ | |||
+ | ====== 基本可行解 ====== | ||
+ | |||
+ | * **基本解:** | ||
+ | 假定$rank(A)=m$,则A中必有m个线性无关的列向量——构成满秩方阵B,A中其余各列组成子阵N,即$A=(B, N)$。相应的$x=(x_B, x_N)$,则$Ax=b$可改写成 <jsmath>AX=Bx_B+Nx_N=b</jsmath>\\ | ||
+ | 因为B为满秩,则B<sup>-1</sup>存在,那么 <jsmath>x_B=B^{-1}b-B^{-1}Nx_N</jsmath>\\ | ||
+ | 任给一组值$x_N$,则可得到相应的$x_B$,\\ | ||
+ | <jsmath>(x_B, x_N)</jsmath> | ||
+ | 为$Ax=b$的一个解。\\ | ||
+ | 令$x_N=0$, 则$x_B=B^{-1}b$, $x=(B^{-1}b,0)$称为约束方程组的**基本解**。 | ||
+ | |||
+ | * **基本可行解:** | ||
+ | * 设 $rank(A)=m$ | ||
+ | * A中m个线性无关的列向量构成满秩方阵B | ||
+ | * A中其余各列组成子阵N | ||
+ | * A=(B, N) | ||
+ | * $x=(x_B, x_N)$ | ||
+ | * $Ax=b$ 可改写成 $Bx_B + Nx_N =b$ | ||
+ | B称为**基**,B中的m个线性无关的列向量称为**基向量**,$x_B$的m个分量称为**基变量**,其余的变量称为**非基变量**。\\ | ||
+ | 基本解不一定满足非负条件,故不一定是可行解。对于非负的基本解,称为**基本可行解**,此时B称为**可行基**。 | ||
+ | |||
+ | * 退化: | ||
+ | |||
+ | 基本可行解x,若它所有的基变量都取正值,则x为非退化的(non-degenerated); 反之,为退化的。\\ | ||
+ | 一个可行基对应一个基本可行解;反之,若一个基本可行解是非退化的,则它也对应着唯一的可行基。\\ | ||
+ | 若一个基本可行解是退化的,则它可以由不止一个可行基得到。\\ | ||
+ | 对应一个LP问题,如果它的所有基本可行解都是非退化,就说该问题是非退化的,否则为退化的。\\ | ||
+ | |||
+ | |||
+ | |||
+ | <note important> --- //[[1@1|李昌英]] 学号:11021081 2011/06/09//</note> | ||
+ | |||
+ | <note important> --- //[[1@1|郑建靖]] 学号:11024013 2011/06/20//</note> | ||
+ | |||
+ | <note important> --- //[[1@1|桂立业]] 学号:11024012 2011/06/20//</note> |