【线性最优化】理论篇

定义问题

线性规划（Liner Programing）的标准型（Canonical form）：
minz=∑j=1ncjxjminz=∑j=1ncjxj
s.t.
⎧⎩⎨⎪⎪∑j=1naijxj=bi,xj≥0i=1,2,...mj=1,2,...n{∑j=1naijxj=bi,i=1,2,...mxj≥0j=1,2,...n

把各种形式转化为标准型的方法：

1. 若问题是求目标函数的最大值，maxzmaxz,那么，
   令f=−zf=−z转化为最小值
2. 若不等式约束条件中出现∑j=1naijxj≤bi∑j=1naijxj≤bi,
   引入 松弛变量 x′ixi′，用两个约束式子替代：
   ⎧⎩⎨⎪⎪∑j=1naijxj+x′i=bix′i≥0{∑j=1naijxj+xi′=bixi′≥0
3. 若约束条件中出现∑j=1naijxj≥bi∑j=1naijxj≥bi,
   引入 剩余变量 x′ixi′，用两个约束式子替代：
   ⎧⎩⎨⎪⎪∑j=1naijxj−x′i=bix′i≥0{∑j=1naijxj−xi′=bixi′≥0
4. 如果约束条件中出现xj≥hjxj≥hj,
   引入新变量yj=xj−hjyj=xj−hj,用这个约束式子替代：
   yj≥0yj≥0
5. 如果变量xjxj的范围没有限制，那么
   引入y′j,y′′jyj′,yj″,用xj=y′j−y′j‘xj=yj′−yj′‘替代原式，
   约束条件变为:
   {y′j≥0y′′j≥0{yj′≥0yj″≥0

单纯形法

一种对矩阵做变换的方法
单纯形方法的目标是把原问题变换成 (ACTBO)(ABCTO)

其特征为(1,2,3条用线性变换可以达成)

1. 中心部位有单位子块
2. 右列元素非负
3. 单位子块对应底行元素为0
4. 底行其它元素非负

可以进行这样的变换

1. 底线以上的部分进行行交换
2. 底线以上的部分乘以非零常数
3. 底线以上的行加到另一行
4. 底线以上的行乘以常数后加到底线

大M法

单纯形法的改进

对偶单纯形法

对偶问题

原问题： minz=cTxminz=cTx
s.t. Ax≥bAx≥b
x≥0x≥0

对应的对偶问题时
maxv=bTymaxv=bTy
s.t. ATy≤cATy≤c
y≥0y≥0

对偶的性质

TH1：
对偶问题的对偶问题是原问题

TH2：（弱对偶定理）
x是原问题的可行解，y是对偶问题的可行解，那么
z=cTx≥v=yTbz=cTx≥v=yTb

更一般的对偶问题

minf(x)s.t.⎧⎩⎨⎪⎪gi(x)≥0hj(x)=0x∈Dminf(x)s.t.{gi(x)≥0hj(x)=0x∈D
对应的对偶问题:
maxθ(w,v)s.t.{w≥0θ(w,v)=inf{f(x)−∑wigi−∑vihj}maxθ(w,v)s.t.{w≥0θ(w,v)=inf{f(x)−∑wigi−∑vihj}

参考文献

施光燕：《最优化方法》，高等教育出版社
龚纯：《Matlab最优化计算》，电子工业出版社
David R. Anderson ：《数据、模型与决策–管理科学篇》，机械工业出版社