User Tools

Site Tools


keynote:2011-lesson13

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

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>​