提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

【运筹学】线性规划数学模型 ( 单纯形法原理 | 单纯形法流程 | 查找初始基可行解 )

流程原理 查找 可行 初始 运筹学 线性规划 单纯形法
2023-06-13 09:17:43 时间

文章目录

一、单纯形法原理

单纯形法的理论基础 :

定理

1

( 可行域是凸集 ) : 如果线性规划的问题 存在可行解 , 其 可行域 必定是 凸集 ;

定理

2

( 基可行解是凸集顶点 ) : 线性规划的 基可行解

X_B

对应了上述 可行域 ( 凸集 ) 的顶点位置 ;

定理

3

( 某个基可行解是最优解 ) : 如果线性规划问题 存在最优解 , 那么 一定存在一个基可行解是最优解 ;

参考上一篇博客 【运筹学】线性规划 图解法 ( 唯一最优解 | 无穷最优解 | 无界解 | 无可行解 ) 进行分析 :

给定线性规划 :

\begin{array}{lcl} max Z = 2x_1 + x_2\\\\ s.t = \begin{cases} x_1 + 1.9x_2 \geq 3.8\\\\ x_1 - 1.9x_2 \leq 3.8\\\\ x_1 + 1.9x_2 \leq 10.2\\\\ x_1 - 1.9x_2 \geq -3.8\\\\ x_1 , x_2 \geq 0 \end{cases} \end{array}

使用图解法进行分析 , 得到如下结果 ;

使用迭代的思想进行求解 :

  • 无限个解中迭代 : 上图中的 可行域
D

中的点是无限的 , 可以在所有的无限个可行域

D

解中进行迭代 , 逐个迭代很难 ;

  • 有限个解中迭代 : 因此选取 可行域 ( 凸集 ) 的顶点 , 也就是 基可行解 进行迭代 , 该线性规划问题的基可行解是有限的 , 只有
4

个 , 即该凸集有

4

个顶点 ;

上图的凸集中的

4

个顶点 , 必然有一个是最优解 , 因此迭代的时候 , 不用从

D

可行域中的无限个点中进行迭代 , 只需要在有限个基可行解中进行迭代 , 即可找到最优解 ;

单纯形法的原理的基础就是源自上述理论 , 在线性规划的有限个基可行解中 , 必定存在一个解释最优解 , 逐个迭代 , 将这个最优解找出即可 ;

从无限个可行解中进行迭代 , 到有限个基可行解中进行迭代 , 简单了很多 ;

但是对于

m \times n

阶的线性规划系数矩阵 , 其基可行解的个数可能有

C_n^m

个 , 如果

n

和

m

很大的话 , 基可行解的数目还是很大 , 这是一个指数级的数 , 因此使用多项式算法 , 完成上述操作 , 计算量还是很大的 ;

这里使用单纯形法 , 进行迭代 , 要比使用多项式法计算量更少 ;

二、单纯形法流程

单纯形法的基本流程 :

① 初始基可行解 : 首先找到初始的基可行解 ;

② 判定是否最优解 : 需要一个准则 , 判定该初始基可行解 , 是否是最优解 ; 这里是单纯形法最核心问题 ;

③ 是最优解 : 如果该基可行解是最优解 , 那么结束迭代 ;

④ 不是最优解 : 如果该基可行解不是最优解 , 那么迭代到下一个基可行解 , 继续判定是否是最优解 ; 如何迭代也需要一个准则 ;

这里涉及到了两个准则 :

  • 判断最优解 : 判断一个 基可行解 是否是最优解 ;
  • 迭代原则 : 如何从一个 基可行解 迭代到下一个基可行解 ;

单纯形法涉及到的问题 :

① 初始解 : 如何找到初始基可行解 ;

② 最优解 : 如何找到一个准则 , 用于判定基可行解是否是最优解 ;

③ 迭代解 : 如果一个基可行解不满足准则 , 如何去选择下一个基可行解进行迭代 ;

解决上述

3

个问题 , 基可行解的算法 , 也就可以得出 ;

三、初始的基可行解查找

如何去找初始的基可行解 , 首先要找到一个 基 , 并且该基是 可行基 ;

对于

m \times n

阶的系数矩阵 :

基 : 从

C(n, m)

个子矩阵中找到基矩阵 , 基矩阵的条件是 该

m

阶方阵是可逆的 ;

参考 【运筹学】线性规划数学模型 ( 求解基矩阵示例 | 矩阵的可逆性 | 线性规划表示为 基矩阵 基向量 非基矩阵 非基向量 形式 ) 一、求解基矩阵示例 博客章节 ,

\begin{bmatrix} &5 & 1 & -1 & 1 & 0 & \\\\ & -10 & 6 & 2 & 0 & 1 & \end{bmatrix}

系数矩阵 , 有

C (5 , 2) = 10

个子矩阵 , 但是只有

9

个是可逆的 ;

基矩阵如下 :

B_1 = \begin{bmatrix} &5 & 1 & \\\\ & -10 & 6 & \end{bmatrix}

,

B_2 = \begin{bmatrix} &1 & -1 & \\\\ & 6 & 2 & \end{bmatrix}

,

B_3 = \begin{bmatrix} &5 & 0 & \\\\ & -10 & 1 & \end{bmatrix}

,

B_4 = \begin{bmatrix} &1 & 1 & \\\\ & 6 & 0 & \end{bmatrix}

,

B_5 = \begin{bmatrix} &5 & 1 & \\\\ & -10 & 0 & \end{bmatrix}

,

B_6 = \begin{bmatrix} &-1 & 0 & \\\\ & 2 & 1 & \end{bmatrix}

,

B_7 = \begin{bmatrix} &-1 & 1 & \\\\ & 2 & 0 & \end{bmatrix}

,

B_8 = \begin{bmatrix} &1 & 10 & \\\\ & 6 & 1 & \end{bmatrix}

,

B_9 = \begin{bmatrix} &1 & 0 & \\\\ & 0 & 1 & \end{bmatrix}

;

选择一个基矩阵 , 每个基矩阵都唯一对应一个基解 , 如果该解大于等于

0

, 说明该解是基可行解 , 那么该选择的基矩阵 , 就是可行基 ;

参考 【运筹学】线性规划数学模型 ( 线性规划求解 | 根据非基变量的解得到基变量解 | 基解 | 基可行解 | 可行基 ) 三、基解 博客章节 , 基解的公式是

X_B = B^{-1}b

使用

B_1 = \begin{bmatrix} &5 & 1 & \\\\ & -10 & 6 & \end{bmatrix}

矩阵作为基矩阵 , 求出其对应的基可行解 , 代入上述公式 :

\begin{array}{lcl} X_B = B^{-1}b\\\\ X_B = \begin{bmatrix} &5 & 1 & \\\\ & -10 & 6 & \end{bmatrix}^{-1} \times \begin{bmatrix} &3 & \\\\ & 2 & \end{bmatrix} \end{array}

如果上述

X_B

的两个分量

\begin{pmatrix} x_1\\ x_2 \\ \end{pmatrix}

都大于 0 , 说明该解释基可行解 , 该基矩阵

B_1

是可行基 ;

使用算法进行迭代 , 一个个判断太浪费时间 , 选择

B_1

作为基矩阵 , 计算很复杂 , 这里选择

B_9 = \begin{bmatrix} &1 & 0 & \\\\ & 0 & 1 & \end{bmatrix}

作为基矩阵 , 这是个单位阵 , 其逆矩阵还是其单位阵本身 ;

B_9

基矩阵对应的基变量是

X_B = \begin{pmatrix} x_4\\ x_5 \\ \end{pmatrix}

, 将基矩阵代入

X_B = B^{-1}b

公式 ;

\begin{array}{lcl} X_B = B^{-1}b\\\\ X_B = \begin{bmatrix} &1 & 0 & \\\\ & 0 & 1 & \end{bmatrix}^{-1} \times \begin{bmatrix} &3 & \\\\ & 2 & \end{bmatrix}\\\\ X_B = \begin{bmatrix} &1 & 0 & \\\\ & 0 & 1 & \end{bmatrix}\times \begin{bmatrix} &3 & \\\\ & 2 & \end{bmatrix}\\\\ X_B = \begin{bmatrix} &3 & \\\\ & 2 & \end{bmatrix} \end{array}

由上述计算过程得到

X_B = \begin{pmatrix} x_4\\ x_5 \\ \end{pmatrix} = \begin{pmatrix} 3\\ 2 \\ \end{pmatrix}

结果 ,

x_4

和

x_5

都大于

0

,

\begin{pmatrix} 0\\ 0\\ 0\\ 3\\ 2 \\ \end{pmatrix}

是基可行解 , 该

X_B

是可行基 ;

使用

B_1

作为基矩阵 , 不好计算 , 还需要求

B_1

矩阵的逆矩阵 ,

B_9

是单位阵 , 所有的 单位阵

I

都是可行基 , 初始基可行解选取时 , 优先选择单位阵 ;

相关文章