文档介绍：最优化方法线性规划单纯形法
第一页，共七十六页。
线性规划：目标函数是线性的，约束条件是
线性等式或不等式
线性规划
第二页，共七十六页。
线性规划的历史
渊源要追溯到Euler、Liebnitz、Lagrange等一页，共七十六页。
例2.
K　有2个极点
有3个基本解，2个可行
K 有3个极点
有3个基本解，均可行
例1.
第二十二页，共七十六页。
例3.
Subject to
5个极点
－极点
第二十三页，共七十六页。
线性规划解的
几何特征
唯一解(顶点)！
第二十四页，共七十六页。
线性规划解的几何特征
无界：没有有限最优解
不可行：没有可行解
无解
可行集：多边形(二维)
→多边集(高维空间)
给出有效的代数刻画和严谨的几何描述，从理论上证实上述几何特征，并寻求有效算法
有解：唯一解/多个解(整条边、面、甚至整个可行集)
有顶点解
第二十五页，共七十六页。
顶点
一条边
无(下)界
第二十六页，共七十六页。
线性规划问题解的几种情况
第二十七页，共七十六页。
单纯形法简介
适用形式：标准形(基本可行解=极点)
理论基础：线性规划的基本定理！
基本思想：从约束集的某个极点/BFS开始，依次移动到相邻极点/BFS，直到找出最优解，或判断问题无界.
初始化：如何找到一个BFS？
判断准则：何时最优？何时无界？
迭代规则：如何从一个极点/BFS迭代到相邻极点/BFS？
第二十八页，共七十六页。
1.　转轴(基本解→相邻基本解)
满秩假定：
A是行满秩的
第二十九页，共七十六页。
规范形(canonical form)
基变量
基本解
非基变量
等价变形
不妨设线性无关
一般地：
次序可以打乱！
只要有m个单位列
第三十页，共七十六页。
规范形的转换问题
⊙ 什么时候可以替换？
⊙ 替换后新规范形是什么？
◎ 替换问题
假设在上述规范形中，想用
第三十一页，共七十六页。
转轴(pivot)
◎ 当且仅当　　　　，可以替换
◎ 替换后，新规范形的系数
转轴公式
－转轴元(pivot element)
第三十二页，共七十六页。
转轴
例1. 求下列方程组以　　　　　为基变量的基本解
第三十三页，共七十六页。
转轴
转轴
转轴
x=(0,0,0,4,2,1)
第三十四页，共七十六页。
2.　BFS→相邻BFS(极点→相邻极点)
◎问题：
确定出基变量，使转轴后新规范形对应BFS？
设x是BFS, 且规范形如前，且假设 aq 进基
因为
令
可否选取合适的　　使得　　　是BFS ？
所以
第三十五页，共七十六页。
确定离基变量
至少有一个正元
第三十六页，共七十六页。
例3. 考虑线性方程组
a4进基
转轴
B=(a1,a2,a3)
X=(4,3,1,0,0,0)
x=(0,1,3,2,0,0)
第三十七页，共七十六页。
3. BFS→目标值减小的相邻BFS
⊙ 将Ax=b的任一解用非基变量表示；
设x是BFS，且规范形如前，则有
◎问题：
确定进基变量，转轴后使新BFS的目标值变小？
用非基变量表示. ——选取进基变量的依据
⊙ 将目标函数
第三十八页，共七十六页。
相对/既约费用系数(relative/reduced cost coefficients)
将 Ax=b 的任一解 x 用非基变量表示为
度量变量相对于给定基的费用
第三十九页，共七十六页。
确定进基变量
◎最优性定理
◎定理(BFS的提高)
◎相对费用系数的经济解释！(合成价格、相对价格)
给定目标值为z0的非退化基本可行解，且假定存在 j 使得 rj < 0，则
i) 如果用 aj 替换基中某列得到了新的BFS，则新解处的目标值比 z0 严格小.
ii) 如果任何替换都产生不了新的BFS，则问题无界.
◆ 退化基本可行解：某个或某些基变量取零的基本可行解！
问题：基本可行解与基的对应关系？
第四十页，共七十六页。
4. 计算过程－单纯形法
单纯形表：BFS对应规范形的表格＋
　　　　　既约费用系数和BFS目标值的相反数
第四十一页，共七十六页。
单纯形法的步骤
步0 形成与初始BFS对应的初始表格.
通过行变换求出第一张单纯形表.
步1 若对每个 j 都有，停；当前BFS是最优的.
步2 选取 q 满足
步4 以为转轴元进行转轴，更新单纯形表