- 一、基矩阵 + 非基矩阵 约束条件
- 二、基矩阵 + 非基矩阵 线性规划
- 三、线性规划 可行解
- 四、目标函数 推导
- 五、 X N = O X_N = O XN=O 目标函数最大 分析
- 六、总结
在上一篇博客 【运筹学】线性规划数学模型 ( 单纯形法原理 | 单纯形法流程 | 查找初始基可行解 ) 中 , 讲解到了使用单纯形法求解线性规划问题 , 需要解决以下三个主要问题 :
- 查找初始基可行解
- 判定是否是最优解
- 如何迭代
该博客中已经讲解了如何查找初始基可行解 , 查找初始基可行解时 , 优先选择单位阵作为基矩阵 , 单位阵 I I I 对应的基解 , 必定是基可行解 ; ( 如果没有单位阵 I I I , 那么后续在讨论 )
本博客开始讲解 , 如何 判定最优解 ( 最优解是如何确定出来的 ) , 和 如何迭代到下一个基可行解 ;
一、基矩阵 + 非基矩阵 约束条件目标函数 , 用于判定 1 1 1 个基可行解是否是最优解 ;
在 【运筹学】线性规划数学模型 ( 求解基矩阵示例 | 矩阵的可逆性 | 线性规划表示为 基矩阵 基向量 非基矩阵 非基向量 形式 ) 博客中 , 根据推导 , 线性规划的约束条件 , 可以表示为 :
B X B + N X N = b BX_B + NX_N = b BXB+NXN=b
二、基矩阵 + 非基矩阵 线性规划将上述约束条件代入线性规划标准形式中
m a x Z = ∑ j = 1 n c j x j { ∑ j = 1 n a i j x j = b i ( i = 1 , 2 ⋯ m ) x j ≥ 0 ( i = 1 , 2 ⋯ n ) \begin{array}{lcl}max Z = \sum_{j=1}^{n}c_j x_j\\ \\ \begin{cases} \sum_{j=1}^{n} a_{ij}x_j = b_i & (i = 1 , 2 \cdots m) \\ \\x_j \geq 0 & (i = 1 , 2 \cdots n) \end{cases}\end{array} maxZ=∑j=1ncjxj⎩⎪⎨⎪⎧∑j=1naijxj=bixj≥0(i=1,2⋯m)(i=1,2⋯n)
得到如下形式 :m a x Z = C B T X B + C N T X N { B X B + N X N = b x j ≥ 0 ( i = 1 , 2 ⋯ n ) \begin{array}{lcl}max Z = C_B^TX_B + C_N^TX_N \\ \\ \begin{cases} BX_B + NX_N = b \\ \\x_j \geq 0 & (i = 1 , 2 \cdots n) \end{cases}\end{array} maxZ=CBTXB+CNTXN⎩⎪⎨⎪⎧BXB+NXN=bxj≥0(i=1,2⋯n)
假设得到基解 { X B = B − 1 b X N = O \begin{cases} X_B = B^{-1}b \\ \\X_N = O \end{cases} ⎩⎪⎨⎪⎧XB=B−1bXN=O , 其中 O O O 表示零矩阵 , 矩阵张红每个元素的值都是 0 0 0 ;
判断该基解 ( X B X N ) \begin{pmatrix} X_B \\ X_N \\ \end{pmatrix} (XBXN) 是否是最优解 , 需要从目标函数 m a x Z = C B T X B + C N T X N max Z = C_B^TX_B + C_N^TX_N maxZ=CBTXB+CNTXN 开始分析 ;
三、线性规划 可行解从现在开始不再讨论基解了 , 回到之前 , 讨论可行解 , X N X_N XN 可以取值任意合法值 , 而不是取 O O O 矩阵值 , 查看取值其它值的时候 , 目标函数是否有最大值 , 这里 重新进行解的推导 :
在 【运筹学】线性规划数学模型 ( 线性规划求解 | 根据非基变量的解得到基变量解 | 基解 | 基可行解 | 可行基 ) 二、根据非基变量的解得到可行解 博客章节 , 在 B X B + N X N = b BX_B + NX_N = b BXB+NXN=b 两端都乘以 B − 1 B^{-1} B−1 , 然后移项得到了 :
X B = B − 1 b − B − 1 N X N X_B = B^{-1}b - B^{-1}NX_N XB=B−1b−B−1NXN
将上述可行解 , 列举出来 :
{ X B = B − 1 b − B − 1 N X N X N \begin{cases} X_B = B^{-1}b - B^{-1}NX_N \\ \\X_N \end{cases} ⎩⎪⎨⎪⎧XB=B−1b−B−1NXNXN
四、目标函数 推导此时进行判定线性规划可行解 { X B = B − 1 b − B − 1 N X N X N \begin{cases} X_B = B^{-1}b - B^{-1}NX_N \\ \\X_N \end{cases} ⎩⎪⎨⎪⎧XB=B−1b−B−1NXNXN 中 , X N X_N XN 取值 O O O 矩阵 , 是否是最好的情况 , 即目标函数达到最大值 , 目标函数如下 :
m a x Z = C B T X B + C N T X N max Z = C_B^TX_B + C_N^TX_N maxZ=CBTXB+CNTXN
将 X B = B − 1 b − B − 1 N X N X_B = B^{-1}b - B^{-1}NX_N XB=B−1b−B−1NXN 代入上述目标函数 :
m a x Z = 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 \begin{array}{lcl} max Z &=& C_B^T ( B^{-1}b - B^{-1}NX_N ) + C_N^TX_N \\\\ &=& C_B^T B^{-1}b - C_B^T B^{-1}NX_N + C_N^TX_N \end{array} maxZ==CBT(B−1b−B−1NXN)+CNTXNCBTB−1b−CBTB−1NXN+CNTXN
C B T B − 1 b C_B^T B^{-1}b CBTB−1b 计算结果是一个数值常量 , 可以写成 b 0 b_0 b0 , 与 X X X ( n n n 个决策变量 ) 无关 ;
= b 0 + ( C N T − C B T B − 1 N ) X N \begin{array}{lcl} &=& b_0 + ( C_N^T - C_B^T B^{-1}N )X_N \\\\ \end{array} =b0+(CNT−CBTB−1N)XN
之前的基解的策略是 , 将 X N X_N XN 取值为 O O O 零矩阵 , 现在讨论 , 要使上述目标函数 m a x Z maxZ maxZ 最大 , 分析 X N = O X_N = O XN=O 是否是最好的选择 , 即分析 X N = O X_N = O XN=O 是否是使 m a x Z maxZ maxZ 目标函数最大的值 ;
假设 X N X_N XN 矩阵中的变量值为 ( x m + 1 x m + 2 ⋮ x n ) \begin{pmatrix} x_{m+1} \\ x_{m+2} \\ \vdots\\ x_n \end{pmatrix} ⎝⎜⎜⎜⎛xm+1xm+2⋮xn⎠⎟⎟⎟⎞ , ( C N T − C B T B − 1 N ) ( C_N^T - C_B^T B^{-1}N ) (CNT−CBTB−1N) 的计算结果是 ( σ m + 1 , σ m + 2 , ⋯ , σ n ) \begin{pmatrix} \sigma_{m+1} , \sigma_{m+2} , \cdots , \sigma_n \end{pmatrix} (σm+1,σm+2,⋯,σn) , ( C N T − C B T B − 1 N ) X N ( C_N^T - C_B^T B^{-1}N )X_N (CNT−CBTB−1N)XN 结果是 σ m + 1 x m + 1 + σ m + 2 x m + 2 + ⋯ + σ n x n \sigma_{m+1} x_{m+1} + \sigma_{m+2} x_{m+2} + \cdots + \sigma_{n} x_{n} σm+1xm+1+σm+2xm+2+⋯+σnxn
= b 0 + ( C N T − C B T B − 1 N ) X N = b 0 + σ m + 1 x m + 1 + σ m + 2 x m + 2 + ⋯ + σ 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} ==b0+(CNT−CBTB−1N)XNb0+σm+1xm+1+σm+2xm+2+⋯+σnxn
五、 X N = O X_N = O XN=O 目标函数最大 分析当上述 X N X_N XN 矩阵中的变量值 ( x m + 1 x m + 2 ⋮ x n ) \begin{pmatrix} x_{m+1} \\ x_{m+2} \\ \vdots\\ x_n \end{pmatrix} ⎝⎜⎜⎜⎛xm+1xm+2⋮xn⎠⎟⎟⎟⎞ 都为 0 0 0 时 , 假如上述公式取值最大值 , 即
b 0 + σ m + 1 x m + 1 + σ m + 2 x m + 2 + ⋯ + σ n x n b_0 + \sigma_{m+1} x_{m+1} + \sigma_{m+2} x_{m+2} + \cdots + \sigma_{n} x_{n} b0+σm+1xm+1+σm+2xm+2+⋯+σnxn
取值最大值 ;
在线性规划约束条件中 , 所有的变量都是大于等于 0 0 0 的 , 每个 x j x_j xj 约束变量取值都可以大于等于 0 0 0 , 目前是查看当所有的 x j x_j xj 变量都取值 0 0 0 时 , 目标函数达到最大值的情况 ;
当 X N X_N XN 取值等于 O O O 零矩阵时 , 目标函数值等于 b 0 b_0 b0 , 当 X N X_N XN 中有元素取值大于 0 0 0 时 , 就会在 b 0 b_0 b0 基础上加上一个值 , 如果这个值是 小于等于 0 0 0 的 , 那么对应的 x j x_j xj 取值越大 , 目标函数值越小 ;
因此这里得到 , 在 X N = ( x m + 1 x m + 2 ⋮ x n ) X_N=\begin{pmatrix} x_{m+1} \\ x_{m+2} \\ \vdots\\ x_n \end{pmatrix} XN=⎝⎜⎜⎜⎛xm+1xm+2⋮xn⎠⎟⎟⎟⎞ 非基变量前的系数是小于等于 0 0 0 时 , 才能满足当 X N X_N XN 中的元素取值等于 0 0 0 时 , 目标函数是最大值 ;
因此 b 0 + σ m + 1 x m + 1 + σ m + 2 x m + 2 + ⋯ + σ n x n b_0 + \sigma_{m+1} x_{m+1} + \sigma_{m+2} x_{m+2} + \cdots + \sigma_{n} x_{n} b0+σm+1xm+1+σm+2xm+2+⋯+σnxn
中的 σ m + 1 , σ m + 2 , ⋯ , σ n \sigma_{m+1} , \sigma_{m+2} , \cdots , \sigma_{n} σm+1,σm+2,⋯,σn 系数值小于等于 0 0 0 , 其中每个系数对应的变量 x j x_{j} xj 必定是大于等于 0 0 0 的值 , 那么系数 σ m + 1 \sigma_{m+1} σm+1 小于等于 0 0 0 时 , 每个变量取值 x j = 0 x_j = 0 xj=0 , 目标函数达到最小值 ;
六、总结将线性规划约束条件表示为 B X B + N X N = b BX_B + NX_N = b BXB+NXN=b
进行变换后得到 X B = B − 1 b − B − 1 N X N X_B = B^{-1}b - B^{-1}NX_N XB=B−1b−B−1NXN
这里可以写出如下可行解 { X B = B − 1 b − B − 1 N X N X N \begin{cases} X_B = B^{-1}b - B^{-1}NX_N \\ \\X_N \end{cases} ⎩⎪⎨⎪⎧XB=B−1b−B−1NXNXN
将上述可行解代入目标函数 m a x Z = C B T X B + C N T X N max Z = C_B^TX_B + C_N^TX_N maxZ=CBTXB+CNTXN 中
得到 m a x Z = b 0 + ( C N T − C B T B − 1 N ) X N maxZ = b_0 + ( C_N^T - C_B^T B^{-1}N )X_N maxZ=b0+(CNT−CBTB−1N)XN
在该情况下 , 如果 ( C N T − C B T B − 1 N ) ( C_N^T - C_B^T B^{-1}N ) (CNT−CBTB−1N) 系数小于等于 0 0 0 , 当 X N X_N XN 取值为 0 0 0 时 , 目标函数得到最大值 ;
