【运筹学】线性规划单纯形法 ( 原理 | 约定符号 | 目标系数矩阵 C | 目标函数变量矩阵 X | 约束方程常数矩阵 b | 系数矩阵 A | 向量 | 向量符号 | 向量 Pj )

韩曙亮

发布于 2023-03-27 17:31:25

1.2K0

发布于 2023-03-27 17:31:25

文章目录

        - [I . 单纯形法 引入](https://cloud.tencent.com/developer)
        - [II . 单纯形法 基本原理](https://cloud.tencent.com/developer)
        - [III . 线性规划 标准形式](https://cloud.tencent.com/developer)
        - [IV . 线性规划 标准形式 普通形式公式](https://cloud.tencent.com/developer)
        - [V . 线性规划 标准形式 展开完整形式公式](https://cloud.tencent.com/developer)
        - [VI . 线性规划 标准形式 矩阵形式公式 ( 矩阵 C | 矩阵 X | 矩阵 b | 矩阵 A )](https://cloud.tencent.com/developer)
        - [VII . 线性规划 标准形式 向量形式公式 ( 向量 Pj )](https://cloud.tencent.com/developer)

I . 单纯形法引入

1. 方程组的解个数 :

① 唯一解 : 如果方程组的方程个数等于变量的个数 , 变量的解是唯一的 ;
② 多个解 : 如果方程组的方程个数大于变量的个数 , 变量的解可能会出现多个 ;

2. 单纯形法引入 : 在线性规划中 , 约束方程个数 , 一般情况下会小于变量个数 , 因此会有多个解 , 单纯形法就是针对这种情况求解的方法 , 可以得到符合要求的线性规划的最优解 ;

II . 单纯形法基本原理

单纯形法原理 :

① 初始单纯形 : 先从线性规划约束方程中找出单纯形 , 每个单纯形可以解出一组变量的解 ;
② 判定趋势 ( 是否最优 ) : 然后判断这个解影响的目标函数的趋势 , 使目标函数增大还是减小 ;
③ 找到更优可行解 : 根据该趋势选择下一个单纯形 , 不断迭代 , 直到找到一个单纯形 , 使目标函数达到最大值或最小值 ;

单纯形法执行方案 :

① 初始可行解 : 先找到一个初始可行解 , 判定其是否是最优解 , 如果是到此为止结束 ;
② 判定 : 是否最优解 , 如果是 , 到此结束 ; 如果不是 , 继续执行 ③ ;
③ 转化更优的可行解 : 那么按照一定法则 , 转换成另一组优化后的可行解 , 跳转到 ② 继续判定 ;

III . 线性规划标准形式

线性规划标准形式 : 使用单纯形法求解线性规划问题 , 这里要求线性规划数学模型必须是标准形式 , 有如下要求 :

① 目标函数 : 变量组成的目标函数 , 求解极大值 ;
② 约束方程 : 所有的约束方程都必须是等式 , 并且右侧的常数都必须大于等于 0 ;
③ 变量约束 : 所有的变量取值都必须大于等于 0 ;

线性规划标准形式转换方式 : 【运筹学】线性规划数学模型标准形式 ( 标准形式 | 目标函数转化 | 决策变量转化 | 约束方程转化 | 固定转化顺序 | 标准形式转化实例 ) , 参考上一篇博客内容 ;

IV . 线性规划标准形式普通形式公式

线性规划标准形式公式 :

个变量 ,

个约束方程 ,

n > m

变量数大于方程数 , 解有多个 ;

\begin{array}{lcl}max Z = \sum_{j = 1}^{n} c_j x_j \\ \\ s.t \begin{cases} \sum_{j = 1}^{n} a_{ij} x_j = b_i & i = 1,2,\cdots,m \\ \\ x_j \geq 0 & j= 1, 2,\cdots,n \\ \\ b_i \geq 0 & i= 1, 2,\cdots,m \end{cases}\end{array}

V . 线性规划标准形式展开完整形式公式

线性规划标准形式展开式 :

个变量 ,

个约束方程 ,

n > m

变量数大于方程数 , 解有多个 ;

\begin{array}{lcl}max Z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n \\ \\ s.t \begin{cases} a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n}x_n = b_1 \\ \\ a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n}x_n = b_2 \\ \\ \cdots\cdots\cdots \\ \\ a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn}x_n = b_m \\ \\ x_1, x_2 , \cdots , x_n \geq 0 \\ \\ b_1 , b_2 , \cdots , b_n \geq 0 \end{cases}\end{array}

VI . 线性规划标准形式矩阵形式公式 ( 矩阵 C | 矩阵 X | 矩阵 b | 矩阵 A )

1. 线性规划标准形式矩阵形式 :

个变量 ,

个约束方程 ,

n > m

变量数大于方程数 , 解有多个 ;

\begin{array}{lcl} maxZ = CX \\\\ AX = b , X \geq 0 \end{array}

2. 矩阵

: 该矩阵是行向量 , 代表了目标函数中的系数 ;

C = \begin{bmatrix} &c_1 , &c_2 , & \cdots , & c_m & \end{bmatrix}

3. 矩阵

: 该矩阵是列向量 , 表示目标函数中的变量 ;

X=\begin{bmatrix}\\\\ x_1\\\\ x_2\\\\ \vdots\\\\ x_m\\\\ \end{bmatrix}

4. 矩阵

: 该矩阵是列向量 , 表示约束方程的右侧常数 ;

b=\begin{bmatrix}\\\\ b_1\\\\ b_2\\\\ \vdots\\\\ b_m\\\\ \end{bmatrix}

5. 矩阵

: 该矩阵是

m \times n

矩阵 , 有

行

列 ,

表示约束方程个数 ,

表示变量个数 ; (

n > m

)

同时也是矩阵

的秩 ; 该矩阵是

个约束方程的每个变量前的系数矩阵 ;

A=\begin{bmatrix}\\\\ & a_{11} & a_{12} & \cdots & a_{1n} &\\\\ & a_{21} & a_{22} & \cdots & a_{2n} &\\\\ & \vdots & \vdots & \ddots & \vdots &\\\\ & a_{m1} & a_{m2} & \cdots & a_{mn} &\\\\ \end{bmatrix}

VII . 线性规划标准形式向量形式公式 ( 向量 Pj )

1. 向量概念 : 向量是特殊的矩阵 ,

行

列的矩阵 , 就是向量 ;

2. 线性规划向量形式 : 其中矩阵

, 矩阵

与上面的矩阵形式内容一致 , 本公式之比上个公式多了一个向量

P_j

;

\begin{array}{lcl}max Z = CX \\ \\ s.t \begin{cases} \sum_{j = 1}^{n} P_j x_j = b \\ \\ X \geq 0 \end{cases}\end{array}

3. 向量

P_j

表示 : 该向量是

行

列的矩阵 , 表示约束方程

中的第

行的列向量 , 其中

j = 1 , 2, \cdots , n

;

P_j=\begin{bmatrix}\\\\ a_{1j}\\\\ a_{2j}\\\\ \vdots\\\\ a_{mj}\\\\ \end{bmatrix}

4. 矩阵

与向量

P_j

关系 :

A = \begin{bmatrix}\\\\ & a_{11} & a_{12} & \cdots & a_{1n} &\\\\ & a_{21} & a_{22} & \cdots & a_{2n} &\\\\ & \vdots & \vdots & \ddots & \vdots &\\\\ & a_{m1} & a_{m2} & \cdots & a_{mn} &\\\\ \end{bmatrix} = \begin{bmatrix} & P_1 & P_2 & \cdots & P_n & \end{bmatrix}

5. 系数替换方案 : 在线性规划普通公式中 , 约束方程系数

a_{ij}

可以使用

P_j

进行替换 ;

\sum_{j = 1}^{n} a_{ij} x_j = b_i \\\\ i = 1,2,\cdots,m \\\\ j= 1, 2,\cdots,n

向量

P_j

代替其中的

a_{ij}

, 替换完毕后为 :

\sum_{j = 1}^{n} P_j x_j = b_i \\\\ j= 1, 2,\cdots,n

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-11-12，如有侵权请联系 cloudcommunity@tencent.com 删除

变量

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度