文章目录

• 一、基矩阵 + 非基矩阵 约束条件
• 二、基矩阵 + 非基矩阵 线性规划
• 三、线性规划 可行解
• 四、目标函数 推导
• 五、$X_N=O$ 目标函数最大 分析
• 六、总结

在上一篇博客 【运筹学】线性规划数学模型 ( 单纯形法原理 | 单纯形法流程 | 查找初始基可行解 ) 中 , 讲解到了使用单纯形法求解线性规划问题 , 需要解决以下三个主要问题 :

• 查找初始基可行解
• 判定是否是最优解
• 如何迭代

该博客中已经讲解了如何查找初始基可行解 , 查找初始基可行解时 , 优先选择单位阵作为基矩阵 , 单位阵 $I$ 对应的基解 , 必定是基可行解 ;
( 如果没有单位阵 $I$ , 那么后续在讨论 )

本博客开始讲解 , 如何 判定最优解 ( 最优解是如何确定出来的 ) , 和 如何迭代到下一个基可行解 ;

一、基矩阵 + 非基矩阵 约束条件

---

目标函数 , 用于判定 $1$ 个基可行解是否是最优解 ;

在 【运筹学】线性规划数学模型 ( 求解基矩阵示例 | 矩阵的可逆性 | 线性规划表示为 基矩阵 基向量 非基矩阵 非基向量 形式 ) 博客中 , 根据推导 , 线性规划的约束条件 , 可以表示为 :

$$B{X}_B+N{X}_N=b$$

二、基矩阵 + 非基矩阵 线性规划

---

将上述约束条件代入线性规划标准形式中

$$\begin{array}{l}maxZ={\sum }_{j=1}^n{c}_j{x}_j\\ \\ \{\begin{array}{ll}{\sum }_{j=1}^n{a}_{ij}{x}_j=b_i& (i=1,2\cdots m)\\ & \\ x_j\ge 0& (i=1,2\cdots n)\end{array}\end{array}$$

得到如下形式 :

$$\begin{array}{l}maxZ=C_B^T{X}_B+C_N^T{X}_N\\ \\ \{\begin{array}{ll}B{X}_B+N{X}_N=b& \\ & \\ x_j\ge 0& (i=1,2\cdots n)\end{array}\end{array}$$

假设得到基解 $\{\begin{array}{l}{X}_B=B^{-1}b\\ \\ X_N=O\end{array}$ , 其中 $O$ 表示零矩阵 , 矩阵张红每个元素的值都是 $0$ ;

判断该基解 $\left(\begin{array}{c}{X}_B\\ X_N\end{array}\right)$ 是否是最优解 , 需要从目标函数 $maxZ=C_B^T{X}_B+C_N^T{X}_N$ 开始分析 ;

三、线性规划 可行解

---

从现在开始不再讨论基解了 , 回到之前 , 讨论可行解 , $X_N$ 可以取值任意合法值 , 而不是取 $O$ 矩阵值 , 查看取值其它值的时候 , 目标函数是否有最大值 , 这里 重新进行解的推导 :

在 【运筹学】线性规划数学模型 ( 线性规划求解 | 根据非基变量的解得到基变量解 | 基解 | 基可行解 | 可行基 ) 二、根据非基变量的解得到可行解 博客章节 , 在 $B{X}_B+N{X}_N=b$ 两端都乘以 $B^{-1}$ , 然后移项得到了 :

$$X_B=B^{-1}b-B^{-1}N{X}_N$$

将上述可行解 , 列举出来 :

$\{\begin{array}{l}{X}_B=B^{-1}b-B^{-1}N{X}_N\\ \\ X_N\end{array}$

四、目标函数 推导

---

此时进行判定线性规划可行解 $\{\begin{array}{l}{X}_B=B^{-1}b-B^{-1}N{X}_N\\ \\ X_N\end{array}$ 中 , $X_N$ 取值 $O$ 矩阵 , 是否是最好的情况 , 即目标函数达到最大值 , 目标函数如下 :

$$maxZ=C_B^T{X}_B+C_N^T{X}_N$$

将 $X_B=B^{-1}b-B^{-1}N{X}_N$ 代入上述目标函数 :

$$\begin{array}{lcl}maxZ& =& C_B^T(B^{-1}b-B^{-1}N{X}_N)+C_N^T{X}_N\\ & & \\ & =& C_B^T{B}^{-1}b-C_B^T{B}^{-1}N{X}_N+C_N^T{X}_N\end{array}$$

$C_B^T{B}^{-1}b$ 计算结果是一个数值常量 , 可以写成 $b_0$ , 与 $X$ ( $n$ 个决策变量 ) 无关 ;

$$\begin{array}{lcl}& =& b_0+(C_N^T-C_B^T{B}^{-1}N)X_N\\ & & \end{array}$$

之前的基解的策略是 , 将 $X_N$ 取值为 $O$ 零矩阵 , 现在讨论 , 要使上述目标函数 $maxZ$ 最大 , 分析 $X_N=O$ 是否是最好的选择 , 即分析 $X_N=O$ 是否是使 $maxZ$ 目标函数最大的值 ;

假设 $X_N$ 矩阵中的变量值为 $\left(\begin{array}{c}{x}_{m+1}\\ x_{m+2}\\ ⋮\\ x_n\end{array}\right)$ , $(C_N^T-C_B^T{B}^{-1}N)$ 的计算结果是 $\left(\begin{array}{c}{\sigma }_{m+1},{\sigma }_{m+2},\cdots ,{\sigma }_n\end{array}\right)$ , $(C_N^T-C_B^T{B}^{-1}N)X_N$ 结果是 ${\sigma }_{m+1}{x}_{m+1}+{\sigma }_{m+2}{x}_{m+2}+\cdots +{\sigma }_n{x}_n$

$$\begin{array}{lcl}& =& b_0+(C_N^T-C_B^T{B}^{-1}N)X_N\\ & & \\ & =& b_0+{\sigma }_{m+1}{x}_{m+1}+{\sigma }_{m+2}{x}_{m+2}+\cdots +{\sigma }_n{x}_n\\ & & \end{array}$$

五、$X_N=O$ 目标函数最大 分析

---

当上述 $X_N$ 矩阵中的变量值 $\left(\begin{array}{c}{x}_{m+1}\\ x_{m+2}\\ ⋮\\ x_n\end{array}\right)$ 都为 $0$ 时 , 假如上述公式取值最大值 , 即

$$b_0+{\sigma }_{m+1}{x}_{m+1}+{\sigma }_{m+2}{x}_{m+2}+\cdots +{\sigma }_n{x}_n$$

取值最大值 ;

在线性规划约束条件中 , 所有的变量都是大于等于 $0$ 的 , 每个 $x_j$ 约束变量取值都可以大于等于 $0$ , 目前是查看当所有的 $x_j$ 变量都取值 $0$ 时 , 目标函数达到最大值的情况 ;

当 $X_N$ 取值等于 $O$ 零矩阵时 , 目标函数值等于 $b_0$ , 当 $X_N$ 中有元素取值大于 $0$ 时 , 就会在 $b_0$ 基础上加上一个值 , 如果这个值是 小于等于 $0$ 的 , 那么对应的 $x_j$ 取值越大 , 目标函数值越小 ;

因此这里得到 , 在 $X_N=\left(\begin{array}{c}{x}_{m+1}\\ x_{m+2}\\ ⋮\\ x_n\end{array}\right)$ 非基变量前的系数是小于等于 $0$ 时 , 才能满足当 $X_N$ 中的元素取值等于 $0$ 时 , 目标函数是最大值 ;

因此
$$b_0+{\sigma }_{m+1}{x}_{m+1}+{\sigma }_{m+2}{x}_{m+2}+\cdots +{\sigma }_n{x}_n$$

中的 ${\sigma }_{m+1},{\sigma }_{m+2},\cdots ,{\sigma }_n$ 系数值小于等于 $0$ , 其中每个系数对应的变量 $x_j$ 必定是大于等于 $0$ 的值 , 那么系数 ${\sigma }_{m+1}$ 小于等于 $0$ 时 , 每个变量取值 $x_j=0$ , 目标函数达到最小值 ;

六、总结

---

将线性规划约束条件表示为 $B{X}_B+N{X}_N=b$

进行变换后得到 $X_B=B^{-1}b-B^{-1}N{X}_N$

这里可以写出如下可行解 $\{\begin{array}{l}{X}_B=B^{-1}b-B^{-1}N{X}_N\\ \\ X_N\end{array}$

将上述可行解代入目标函数 $maxZ=C_B^T{X}_B+C_N^T{X}_N$ 中

得到 $maxZ=b_0+(C_N^T-C_B^T{B}^{-1}N)X_N$

在该情况下 , 如果 $(C_N^T-C_B^T{B}^{-1}N)$ 系数小于等于 $0$ , 当 $X_N$ 取值为 $0$ 时 , 目标函数得到最大值 ;

总结

以上是生活随笔为你收集整理的【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 可行解表示 | 目标函数推导 | 目标函数最大值分析 )的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。