最优化方法:三、线性规划
主要参考书目:
- 最优化方法及其应用/郭科,陈聆,魏友华.-北京:高等教育出版社,2007.7(2013.7重印)
1、线性规划的数学模型和基本原理
- 标准形式
任何一个线性规划问题,总可以写为标准形式:
变形方法:取负号,增加人工变量等等。 - 基本定理
若可行域有界,则目标函数一定能在可行域的顶点上取得最优。
2、单纯性法
- 基本思想
从某一个顶点开始,判断其是否是最优点,不是,则转向另一个顶点。 - 基本流程
其中,i为所有非基变量的下标。
但是,这个流程给的太过公式化,其思想如下:
(1)找到一个初始解(怎么着后面会说)
(2)用非基变量表示基变量(线性方程的理论保证这一定可以做到)并带入目标函数,讨论每个非基变量前的系数。因为非基变量取0,如果把系数为负的非基变量变为基变量,则函数值一定下降(即更优),而系数越小,变得更小的可能性就越大(不是一定最大,因为换入后其取值不一定,2*3<1*8)。如果所有系数都是正值,则换无可换,没人比我更优秀,那我就是最优了。
(3)有一个入基则必定有一个出基,这时候就有一个问题,有时候出基变量没选好,会出现某个基变量只能取为负的现象(和标准形式变量全非负矛盾),所以这时候要避免这种情况发生,则需寻找最小的那个变量出基(自己写个方程试一下就清楚为什么是那个形式了,是矩阵初等变化的结果)。
(4)继续判断新的初始解是否最优,重复以上过程。 - 初始解的确定
一般有大M法和两阶段法
大M法:
两阶段法:
将第一阶段计算得到的最终解,除去人工变量,作为第二阶段的初始解。 - 退化问题
在出现退化情况时,会导致迭代循环,可以通过摄动法、Bland法等方法解决。
3、对偶问题
还存在一些问题没有解决:
X与Y有何关系?
为什么原问题和对偶问题同时可行时即得到最优解?
- 对偶问题与原问题
- 对偶理论
(1)max问题的函数值总不大于min问题。
(2)一个有最优,另一个也有,并且目标函数最优值相等;一个*则另一个没有可行解。
(3)互补松弛定理
- 对偶单纯形法
先保证原问题最优+对偶问题可行,然后进行迭代,以达到原问题可行,此时(也就是两个问题都可行的时候)即获得最优解。
不清楚什么理论保证了此时即是最优解。
- 对偶理论
单纯形法灵敏度分析
- 价值系数变化
变化的为非基变量系数时,保证最优解不变的变化限为:
变化的为基变量系数时,保证最优解不变的变化限为: - 资源系数变化
保证最优解不变的变化限为:
内点法
单纯形法虽然很成功,但它毕竟不是一个多项式算法。而内点法则是多项式算法。内点法首先把规划问题化为纯不等式约束的情况,再通过罚函数法将问题变为无约束优化,之后利用解决无约束问题的方法解决(如最速下降等)。
其实内点法不是线性规划的专利,对于任何一种纯不等式约束(或者可化为纯不等式约束)的问题都有效。