文章目录
一、单纯形法原理
单纯形法的理论基础 :
定理
( 可行域是凸集 ) : 如果线性规划的问题 存在可行解 , 其 可行域 必定是 凸集 ;
定理
( 基可行解是凸集顶点 ) : 线性规划的 基可行解
对应了上述 可行域 ( 凸集 ) 的顶点位置 ;
定理
( 某个基可行解是最优解 ) : 如果线性规划问题 存在最优解 , 那么 一定存在一个基可行解是最优解 ;
参考上一篇博客 【运筹学】线性规划 图解法 ( 唯一最优解 | 无穷最优解 | 无界解 | 无可行解 ) 进行分析 :
给定线性规划 :
使用图解法进行分析 , 得到如下结果 ;
使用迭代的思想进行求解 :
中的点是无限的 , 可以在所有的无限个可行域
解中进行迭代 , 逐个迭代很难 ;
- 有限个解中迭代 : 因此选取 可行域 ( 凸集 ) 的顶点 , 也就是 基可行解 进行迭代 , 该线性规划问题的基可行解是有限的 , 只有
个 , 即该凸集有
个顶点 ;
上图的凸集中的
个顶点 , 必然有一个是最优解 , 因此迭代的时候 , 不用从
可行域中的无限个点中进行迭代 , 只需要在有限个基可行解中进行迭代 , 即可找到最优解 ;
单纯形法的原理的基础就是源自上述理论 , 在线性规划的有限个基可行解中 , 必定存在一个解释最优解 , 逐个迭代 , 将这个最优解找出即可 ;
从无限个可行解中进行迭代 , 到有限个基可行解中进行迭代 , 简单了很多 ;
但是对于
阶的线性规划系数矩阵 , 其基可行解的个数可能有
个 , 如果
和
很大的话 , 基可行解的数目还是很大 , 这是一个指数级的数 , 因此使用多项式算法 , 完成上述操作 , 计算量还是很大的 ;
这里使用单纯形法 , 进行迭代 , 要比使用多项式法计算量更少 ;
二、单纯形法流程
单纯形法的基本流程 :
① 初始基可行解 : 首先找到初始的基可行解 ;
② 判定是否最优解 : 需要一个准则 , 判定该初始基可行解 , 是否是最优解 ; 这里是单纯形法最核心问题 ;
③ 是最优解 : 如果该基可行解是最优解 , 那么结束迭代 ;
④ 不是最优解 : 如果该基可行解不是最优解 , 那么迭代到下一个基可行解 , 继续判定是否是最优解 ; 如何迭代也需要一个准则 ;
这里涉及到了两个准则 :
- 判断最优解 : 判断一个 基可行解 是否是最优解 ;
- 迭代原则 : 如何从一个 基可行解 迭代到下一个基可行解 ;
单纯形法涉及到的问题 :
① 初始解 : 如何找到初始基可行解 ;
② 最优解 : 如何找到一个准则 , 用于判定基可行解是否是最优解 ;
③ 迭代解 : 如果一个基可行解不满足准则 , 如何去选择下一个基可行解进行迭代 ;
解决上述
个问题 , 基可行解的算法 , 也就可以得出 ;
三、初始的基可行解查找
如何去找初始的基可行解 , 首先要找到一个 基 , 并且该基是 可行基 ;
对于
阶的系数矩阵 :
基 : 从
个子矩阵中找到基矩阵 , 基矩阵的条件是 该
阶方阵是可逆的 ;
参考 【运筹学】线性规划数学模型 ( 求解基矩阵示例 | 矩阵的可逆性 | 线性规划表示为 基矩阵 基向量 非基矩阵 非基向量 形式 ) 一、求解基矩阵示例 博客章节 ,
系数矩阵 , 有
个子矩阵 , 但是只有
个是可逆的 ;
基矩阵如下 :
,
,
,
,
,
,
,
,
;
选择一个基矩阵 , 每个基矩阵都唯一对应一个基解 , 如果该解大于等于
, 说明该解是基可行解 , 那么该选择的基矩阵 , 就是可行基 ;
参考 【运筹学】线性规划数学模型 ( 线性规划求解 | 根据非基变量的解得到基变量解 | 基解 | 基可行解 | 可行基 ) 三、基解 博客章节 , 基解的公式是
使用
矩阵作为基矩阵 , 求出其对应的基可行解 , 代入上述公式 :
如果上述
的两个分量
都大于 0 , 说明该解释基可行解 , 该基矩阵
是可行基 ;
使用算法进行迭代 , 一个个判断太浪费时间 , 选择
作为基矩阵 , 计算很复杂 , 这里选择
作为基矩阵 , 这是个单位阵 , 其逆矩阵还是其单位阵本身 ;
基矩阵对应的基变量是
, 将基矩阵代入
公式 ;
由上述计算过程得到
结果 ,
和
都大于
,
是基可行解 , 该
是可行基 ;
使用
作为基矩阵 , 不好计算 , 还需要求
矩阵的逆矩阵 ,
是单位阵 , 所有的 单位阵
都是可行基 , 初始基可行解选取时 , 优先选择单位阵 ;