i) 如果用 aj 替换基中某列得到了新的BFS，则新解 处的目标值比 z0 严格小. ii) 如果任何替换都产生不了新的BFS，则问题无界.
◆ 退化基本可行解：某个或某些基变量取零的基本可行解！
问题：基本可行解与基的对应关系？
◎相对费用系数的经济解释！(合成价格、相对价格)
4. 计算过程－单纯形法
几何解释：连接集合中任两点的线段仍含在该集合中 性质
一些重要的凸集
超平面(hyperplane):
正/负闭半空间： 多面集(polyhedral convex set): 有限个闭半空间的交集
推 广 平面上：多边形
注：任一线性规划的可行集是多面集！
极点
几何上：极点即不能位于连接该集合中其它两点 的开线段上的点
以
为转轴元，转轴后即得新基对应的数据！
例1
a2进基，计算y2. 计算表格如下：
计算
a1进基，计算y1. 得如下表格：
最优值：
最优解：
利用两阶段单纯形过程求解
第七张单纯形表
循环！
注：循环转轴序列中所有BFS都是退化的！是 同一个BFS！
避免循环的方法
美好愿望：构造某种永远不会产生循环的转轴规则！
◎ 摄动法(Charnes，1952年) ◎ 字典序法(Dantzig, Orden和Wolfe，1954年) ◎ Bland法则(Bland, 1977)－最小指标法则
• 1947年, George Dantzig发明了单纯形法
• 1979年，L. Khachain找到了求解线性规划的一 种有效方法(第一个多项式时间算法－椭球内点法)
• 1984年，Narendra Karmarkan发现了另一种求 解线性规划的有效方法，已证明是单纯形法的强 有力的竞争者(投影内点法) • 现在求解大规模、退化问题最有效的是原－对偶 内点法
例1. 食谱问题
◎ 问题：确定食品数量，满足营养需求，花费最小？
n种食品，m种营养成份； －第 j 种食品的单价
－每单位第 j 种食品所含第 i 种营养的数量 －为了健康，每天必须食用第i 种营养的数量
◎ 变量：
－食用第 j 种食品的数量
◎ 模型：
例2. 运输问题
产销平衡/不平衡的运输问题
得辅助问题的一个新最优BFS，且基变量中少1个人工变量！
第 i 个约束冗余； 删除单纯形表的第 i 行数据
例1. 给出下面系统的一个基本可行解，或者说明其无解
引入人工变量 目标：
辅助问题的 初始表格！
BFS
第一张 单纯形表
第二张 单纯形表
注意基变量整列包括末行z在内除了基变量 其他元素都是0
辅助问题的最优值是0. 原问题的BFS：
7. 单纯形法的矩阵形式
给定基 B 及对应BFS (xB, 0), 其中xB=B-1b
用非基变量表示基变量： 用非基变量表示目标函数：
相对费用向量
初始表格－单纯形表
初始表格 通常不是单纯形表！
与基矩阵 B 对应的单纯形表
修正单纯形法的计算步骤
步0 给定BFS及对应的B-1。计算
步1 计算 步2 选取 q 满足 步3 计算 yq=B-1aq；若 停，问题无界；否则，选 p 满足 ， 。如果 停；得最优解.
假设最后得最优解(x, y)、最优值 z* 和最优基 B
得到原问题的基本可行解
◎ z*> 0，无可行解！ ◎ z*= 0，有可行解！
⊙ 基变量中无人工变量→x 是BFS，B 是对应的基 ⊙ 基变量中有人工变量→驱赶人工变量出基 假设第 i 个基变量是人工变量，且当前单纯形表 第 i 行的前n个数据是 以任一非零元为转轴元转轴
◎ 收敛性定理：
对非退化线性规划，从任一基本可行解出发，利用 单纯形法可在有限步内得到最优解或判断问题无界.
5. 两阶段法
如何启动单纯形法－人工变量
◎ 目标 判断 Ax=b, x≥0 是否有界； 有解时找一个基本可行解； ◎ 方法 ⊙ 给有需要的行乘以-1，使得 b≥0 ⊙ 构造辅助问题
人工变量
(x, y)=(0, b)是基本可行解！ 故可以(0,b)为初始BFS，利用单纯形法求解辅助问题
iii) Ax=b对应的约束集K最多有有限个极点.
例1.
K 有3个极点 有3个基本解，均可行
例2.
K
有2个极点
有3个基本解，2个可行
例3.
Subject to
5个极点 －极点
线性规划 解的 几何特征
唯一 解(顶点)！
线性规划解的几何特征
• 有解：唯一解/多个解(整条边、面、甚至 有顶点解 整个可行集) • 无界：没有有限最优解 • 不可行：没有可行解 无解
两阶段法－可求任一线性规划问题
◎ 第I阶段：启动单纯形法 →构造、求解辅助问题
→判断原问题不可行、或可行 → 可行时找到基本可行解及对应规范形
⊙ 第II阶段：利用单纯形法求原问题
→从上述BFS出发，求解所给问题 →原问题无界或者有解
例2. 利用两阶段法求解下面的问题
第I阶段：辅助问题
先构造辅助向量z=x4+x5
实用优化方法
线性规划：单纯形法
线性规划
线性规划：目标函数是线性的，约束条件是 线性等式或不等式
线性规划的历史
• 渊源要追溯到Euler、Liebnitz、Lagrange等
• George Dantzig, Von Neumann(Princeton)和 Leonid Kantorovich在1940’s创建了线性规划
进基变量：最小相对费用系数规则；出基变量：最小指标规则！
例1.
化标准形
得标准形的初始表格/第一张单纯形表
转 轴
0
↓
转 轴
-2 ↓
转 轴
-4 ↓ -27/5
最优解： 最优值：
原问题的极大值：
退化(degenerate)与循环(cycling)
◎退化问题
⊙ 单纯形法可能出现循环！ ⊙ 实际中经常碰到退化问题，但很少出现循环 ⊙ 避免出现循环的措施：摄动法、Bland法则、字典序法
退化基本解：基本解中如果有一个或多个基变量的值为零
基本可行解
约束系统
定义 称 的非负基本解是标准形的基 本可行解(basic feasible solution)；
线性规划的基本定理
考虑线性规划标准形，其中A是秩为m的m×n阶 矩阵，则以下结论成立：
i) 若标准型有可行解，则必有基本可行解；
ii) 若标准型有最优解，则必有最优基本可行解。
⊙如果有多个费用系数是负的，选取下标最小的相对 费用系数对应的变量为进基变量 ⊙如果最小正比值在多个指标处取得，取下标最 小者对应的变量为进基变量
利用Bland法则作为转轴规则求解Beale的例子！ 前四张单纯形表相同！
最后一张单纯形表/最优单纯形表
单纯形法的收敛性
◎ 非退化线性规划：任一基本可行解非退化
可行集：多边形(二维) →多边集(高维空间) 给出有效的代数刻画和严谨的几何描述，从理论上证 实上述几何特征，并寻求有效算法
顶点 一 条 边
无 (下 )界
线性规划问题解的几种情况
单纯形法简介
• 适用形式：标准形(基本可行解=极点) • 理论基础：线性规划的基本定理！ • 基本思想：从约束集的某个极点/BFS开始， 依次移动到相邻极点/BFS，直到找出最优 解，或判断问题无界. • 初始化：如何找到一个BFS？ • 判断准则：何时最优？何时无界？ • 迭代规则：如何从一个极点/BFS迭代到相 邻极点/BFS？
◎ 当且仅当 ，可以替换 ◎ 替换后，新规范形的系数 转轴公式
－转轴元(pivot element)
例1. 求下列方程组以
为基变量的基本解
转轴
转 轴
转 轴
转 轴
x=(0,0,0,4,2,1)
2. BFS→相邻BFS(极点→相邻极点)
设x是BFS, 且规范形如前，且假设 aq 进基 ◎问题： 确定出基变量，使转轴后新规范形对应BFS？ 因为 所以
自由变量 松弛(slack)/盈余(surplus)变量；
例5. 化成标准形
等 价 表 示 为
基本解与基变量
其中 满秩假定： m×n矩阵A满足m<n，且A的行向量线性无关 • 在满秩假定下，方程组Ax=b总有解，且至少有一个基本 解
定义： 给定含有n个变量，m个方程的线性方程组Ax=b， 设B是由A 的列组成的任一非奇异m×m子阵，则如果置x 的所有与B无关的n-m个分量为零后，所得方程组的解是 Ax=b关于基B的基本解(basic solution) ，称x中与基B对应 的分量为基变量(basic variables)
1. 转轴(基本解→相邻基本解)
满秩假定： A是行满秩的
规范形(canonical form)
不妨设 线性无关 等价变形
基变量
基本解
非基变量
一般地： 只要有m个单位列 次序可以打乱！
规范形的转换问题
◎ 替换问题
假设在上述规范形中，想用
⊙ 什么时候可以替换？ ⊙ 替换后新规范形是什么？
转轴(pivot)
例3. 其它应用
• 数据包络分析(data envelope analysis, DEA) • 网络流问题(Network flow) • 博弈论(game theory)等
线性规划的一般形式
线性规划的标准形(分析、算法)
向量表示：
标准形的特征：极小化、等式约束、变量非负
一般形式
转化
标准形
称
令 可否选取合适的 使得 是BFS ？
确定离基变量
至少有一个正元
例3. 考虑线性方程组
B=(a1,a2,a3)
X=(4,3,1,0,0,0)