最优化方法
在一组线性的等式或不等式约束下,求一个线性函数的最小值或最大值。
形式化的定义:
LP问题:
D:所有可行点的集合,称为可行区域
D=∅,无解或不可行
D≠∅,但目标函数在D上无上界:无界
D≠∅,且目标函数有限的最优解:有最优解
线性规划在Matlab中的实现方法
Matlab中规定线性规划的标准形式为:
min cTx s.t. Ax≤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是控制参数。
从实际中总结出来的LP形式不完全一样:
标准LP问题形式:
min z=cTx
s.t. Ax=b, x≥0
将LP问题标准化:
目标函数的转换 \max\ z→\min\ (-z)
约束条件的转换(引入松弛变量)
定义: 可行区域是所有满足约束条件的可行点的集合,记为D
D={x| Ax=b, x≥0}
首先讨论集合 K={ x | Ax = b }
一般仿射集的特征:给定 mxn 实矩阵 A 和 b∈Em,则 K={x∈En | Ax=b} 为 En 中的仿射集,并且En中的任一仿射集均可表成此种形式。
集合 K={ x | Ax = b }为 En 仿射集。
可行区域 D={x|Ax=b,x≥0}为凸集。
若dim(D)= n-m, D’为D的界面,且dim(D’)=n-m-k,则|Q|≥k.
如果一个方向d不能表成两个方向的正线性组合,就成d是C的极方向(extreme direction)。
假定rank(A)=m,则A中必有m个线性无关的列向量——构成满秩方阵B,A中其余各列组成子阵N,即A=(B, N)。相应的x=(x_B, x_N),则Ax=b可改写成
B称为基,B中的m个线性无关的列向量称为基向量,x_B的m个分量称为基变量,其余的变量称为非基变量。
基本解不一定满足非负条件,故不一定是可行解。对于非负的基本解,称为基本可行解,此时B称为可行基。
基本可行解x,若它所有的基变量都取正值,则x为非退化的(non-degenerated); 反之,为退化的。
一个可行基对应一个基本可行解;反之,若一个基本可行解是非退化的,则它也对应着唯一的可行基。
若一个基本可行解是退化的,则它可以由不止一个可行基得到。
对应一个LP问题,如果它的所有基本可行解都是非退化,就说该问题是非退化的,否则为退化的。