【运筹学】线性规划 人工变量法 ( 单纯形法总结 | 人工变量法引入 | 人工变量法原理分析 | 人工变量法案例 )

一、单纯形法总结

求解线性规划 , 使用的是单纯形法 ;

迭代转化 : 其将 在无穷多个可行解中迭代 , 转化为了 在有限个基可行解中进行迭代 ;

单纯形法理论基础 : 将迭代范围由大集合转为小集合 , 不会漏掉最优解 , 根据线性规划定理 , 只要有最优解 , 该最优解一定是基可行解 ;

单纯形法求解流程 :

• ① 找到单位阵
• ② 最优准则 : 计算检验数
• ③ 迭代准则 : 先根据检验数找到入基变量 , 再根据常量除以入基变量大于 0 0 0 系数 , 选择小的值对应的基变量作为出基变量 ;
• ④ 中心元 : 找到 入基变量 与 出基变量 交叉点元素 , 这是中心元 , 中心元转为 1 1 1 , 同一列另一个系数转为 0 0 0 ; 然后继续根据最优准则计算检验数 , 转到步骤 ② ;

二、人工变量法引入

上述单纯形的解法是 从单位阵出发的 , 所有的前提是有单位阵 , 线性规划中可能不存在单位阵 , 如果线性规划转化为单位阵时 , 没有单位阵 , 就需要使用 人工变量法 , 构造一个单位阵 ;

下面通过一个案例来介绍人工变量法的使用 ;

三、人工变量法案例

求解线性规划 : 使用人工变量法求解线性规划 ;

m a x Z = 3 x 1 + 2 x 2 − x 3 s . t { − 4 x 1 + 3 x 2 + x 3 ≥ 4 x 1 − x 2 + 2 x 3 ≤ 10 − 2 x 1 + 2 x 2 − x 3 = − 1 x j ≥ 0 ( j = 1 , 2 , 3 ) \begin{array}{lcl} max Z = 3x_1 + 2x_2 - x_3 \\ \\ s.t\begin{cases} -4 x_1 + 3x_2 + x_3 \geq 4 \\\\ x_1 - x_2 + 2x_3 \leq 10 \\\\ -2x_1 + 2x_2 - x_3 = -1 \\\\ x_j \geq 0 & (j = 1 , 2 , 3 ) \end{cases}\end{array} maxZ=3x1​+2x2​−x3​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​−4x1​+3x2​+x3​≥4x1​−x2​+2x3​≤10−2x1​+2x2​−x3​=−1xj​≥0​(j=1,2,3)​​

四、线性规划标准型

参考 【运筹学】线性规划数学模型标准形式 ( 标准形式 | 目标函数转化 | 决策变量转化 | 约束方程转化 | 固定转化顺序 | 标准形式转化实例 ) 线性规划 普通形式 -> 标准形式 转化顺序说明 博客 , 先处理变量约束 , 再将不等式转为等式 , 最后更新目标函数 ;

1 . 处理约束变量 : 所有的约束变量都大于等于 0 0 0 , 这里无需处理 ;

2 . 将不等式转为等式 :

① 方程 1 1 1 转为等式 : 方程 1 1 1 是大于等于不等式 , 需要在方程左侧减去剩余变量 x 4 x_4 x4​ ;

− 4 x 1 + 3 x 2 + x 3 − x 4 = 4 -4 x_1 + 3x_2 + x_3 - x_4 = 4 −4x1​+3x2​+x3​−x4​=4

② 方程 2 2 2 转为等式 : 方程 2 2 2 是小于等于不等式 , 需要在方程左侧加上松弛变量 x 5 x_5 x5​ ;

x 1 − x 2 + 2 x 3 + x 5 = 10 x_1 - x_2 + 2x_3 + x_5 = 10 x1​−x2​+2x3​+x5​=10

3 . 方程 3 3 3 转为符合要求的等式 : 方程 3 3 3 是等式 , 但是其右侧的常数小于 0 0 0 , 这里需要在等式两边都乘以 − 1 -1 −1 , 使右侧的常数大于等于 0 0 0 ;

2 x 1 − 2 x 2 + x 3 = 1 2x_1 - 2x_2 + x_3 = 1 2x1​−2x2​+x3​=1

4 . 处理目标函数取最大值 : 目标函数就是取最大值 , 无需处理 ;

5 . 最终的标准形结果是 :

m a x Z = 3 x 1 + 2 x 2 − x 3 s . t { − 4 x 1 + 3 x 2 + x 3 − x 4 = 4 x 1 − x 2 + 2 x 3 + x 5 = 10 2 x 1 − 2 x 2 + x 3 = 1 x j ≥ 0 ( j = 1 , 2 , 3 , 4 , 5 ) \begin{array}{lcl} max Z = 3x_1 + 2x_2 - x_3 \\ \\ s.t\begin{cases} -4 x_1 + 3x_2 + x_3 - x_4 = 4 \\\\ x_1 - x_2 + 2x_3 + x_5 = 10 \\\\ 2x_1 - 2x_2 + x_3 = 1 \\\\ x_j \geq 0 \quad (j = 1 , 2 , 3, 4, 5 ) \end{cases}\end{array} maxZ=3x1​+2x2​−x3​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​−4x1​+3x2​+x3​−x4​=4x1​−x2​+2x3​+x5​=102x1​−2x2​+x3​=1xj​≥0(j=1,2,3,4,5)​​

五、人工变量法

将上述转化完毕的标准型的系数矩阵补全 :

m a x Z = 3 x 1 + 2 x 2 − x 3 + 0 x 4 + 0 x 5 s . t { − 4 x 1 + 3 x 2 + x 3 − x 4 + 0 x 5 = 4 x 1 − x 2 + 2 x 3 + 0 x 4 + x 5 = 10 2 x 1 − 2 x 2 + x 3 + 0 x 4 + 0 x 5 = 1 x j ≥ 0 ( j = 1 , 2 , 3 , 4 , 5 ) \begin{array}{lcl} max Z = 3x_1 + 2x_2 - x_3 + 0x_4 + 0x_5 \\ \\ s.t\begin{cases} -4 x_1 + 3x_2 + x_3 - x_4 + 0x_5 = 4 \\\\ x_1 - x_2 + 2x_3 + 0x_4 + x_5 = 10 \\\\ 2x_1 - 2x_2 + x_3 + 0x_4 + 0x_5 = 1 \\\\ x_j \geq 0 \quad (j = 1 , 2 , 3, 4, 5 ) \end{cases}\end{array} maxZ=3x1​+2x2​−x3​+0x4​+0x5​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​−4x1​+3x2​+x3​−x4​+0x5​=4x1​−x2​+2x3​+0x4​+x5​=102x1​−2x2​+x3​+0x4​+0x5​=1xj​≥0(j=1,2,3,4,5)​​

上述约束方程中没有单位阵 , 无法找到初始基可行解 , 创建初始的单纯形表 ;

上述线性规划中 , 需要找到 3 × 3 3 \times 3 3×3 的单位阵 ( 1 0 0 0 1 0 0 0 1 ) \begin{pmatrix} \quad 1 \quad 0 \quad 0 \quad \\ \quad 0 \quad 1 \quad 0 \quad \\ \quad 0 \quad 0 \quad 1 \quad \\ \end{pmatrix} ⎝⎛​100010001​⎠⎞​ , 目前只有 x 5 x_5 x5​ 的系数列向量是 ( 0 1 0 ) \begin{pmatrix} \quad 0 \quad \\ \quad 1 \quad \\ \quad 0 \quad \\ \end{pmatrix} ⎝⎛​010​⎠⎞​ , 这里需要进行如下操作 ;

人工变量法 : 目的是人为制造单位阵 , 添加 2 2 2 个或 3 3 3 个人工变量 ;

• 方程 1 1 1 构造变量 x 6 x_6 x6​ : 该变量只出现在第 1 1 1 个方程中 ;

− 4 x 1 + 3 x 2 + x 3 − x 4 + 0 x 5 + x 6 = 4 -4 x_1 + 3x_2 + x_3 - x_4 + 0x_5 + x_6 = 4 −4x1​+3x2​+x3​−x4​+0x5​+x6​=4

• 方程 2 2 2 构造变量 x 7 x7 x7 : 该变量只出现在第 3 3 3 个方程中 ;

2 x 1 − 2 x 2 + x 3 + 0 x 4 + 0 x 5 + x 7 = 1 2x_1 - 2x_2 + x_3 + 0x_4 + 0x_5 + x_7 = 1 2x1​−2x2​+x3​+0x4​+0x5​+x7​=1

添加了人工变量后 , 变量就变成了 7 7 7 个 ( x 1 x 2 x 3 x 4 x 5 x 6 x 7 ) \begin{pmatrix} \quad x_1 \quad \\ \quad x_2 \quad \\ \quad x_3 \quad \\ \quad x_4 \quad \\ \quad x_5 \quad \\ \quad x_6 \quad \\ \quad x_7 \quad \\ \end{pmatrix} ⎝⎜⎜⎜⎜⎜⎜⎜⎜⎛​x1​x2​x3​x4​x5​x6​x7​​⎠⎟⎟⎟⎟⎟⎟⎟⎟⎞​ , 原来的变量只有 5 5 5 个 ( x 1 x 2 x 3 x 4 x 5 ) \begin{pmatrix} \quad x_1 \quad \\ \quad x_2 \quad \\ \quad x_3 \quad \\ \quad x_4 \quad \\ \quad x_5 \quad \\ \end{pmatrix} ⎝⎜⎜⎜⎜⎛​x1​x2​x3​x4​x5​​⎠⎟⎟⎟⎟⎞​ ; 如果解出该线性规划的 7 7 7 个解 , 去掉后面的 x 6 , x 7 x_6 , x_7 x6​,x7​ 之后 , 该最优解不一定满足 5 5 5 个变量的线性规划 ;

如果解出的 7 7 7 个解中 , x 6 , x 7 x_6 , x_7 x6​,x7​ 都等于 0 0 0 , 此时该最优解的前 5 5 5 个变量 , 满足最初的线性规划解 ;

引入大 M M M : 在目标函数中 , 为 x 6 , x 7 x_6 , x_7 x6​,x7​ 加上系数 − M -M −M , M M M 是一个抽象数值 , 没有具体的值 , 其大于给定的任何一个值 ;

m a x Z = 3 x 1 + 2 x 2 − x 3 + 0 x 4 + 0 x 5 − M x 6 − M x 7 max Z = 3x_1 + 2x_2 - x_3 + 0x_4 + 0x_5 - M x_6 - Mx_7 maxZ=3x1​+2x2​−x3​+0x4​+0x5​−Mx6​−Mx7​

引入大 M M M 后最优解 x 6 , x 7 x_6 , x_7 x6​,x7​ 必须为 0 0 0 : 如果上述 x 6 , x 7 x_6 , x_7 x6​,x7​ 只要大于 0 0 0 , 即使很小 , 但是乘以一个很大的负数值 − M -M −M , 也会极大降低目标函数大小 , 因此只有两个变量取值为 0 0 0 时 , 才能使该解称为最优解 ;

添加 2 2 2 个人工变量后 , 得到 人工变量单纯形法 线性规划模型 :

m a x Z = 3 x 1 + 2 x 2 − x 3 + 0 x 4 + 0 x 5 − M x 6 − M x 7 s . t { − 4 x 1 + 3 x 2 + x 3 − x 4 + 0 x 5 + x 6 + 0 x 7 = 4 x 1 − x 2 + 2 x 3 + 0 x 4 + x 5 + 0 x 6 + 0 x 7 = 10 2 x 1 − 2 x 2 + x 3 + 0 x 4 + 0 x 5 + 0 x 6 + x 7 = 1 x j ≥ 0 ( j = 1 , 2 , 3 , 4 , 5 , 6 , 7 ) \begin{array}{lcl} max Z = 3x_1 + 2x_2 - x_3 + 0x_4 + 0x_5 - M x_6 - Mx_7 \\\\ s.t\begin{cases} -4 x_1 + 3x_2 + x_3 - x_4 + 0x_5 + x_6 + 0x_7 = 4 \\\\ x_1 - x_2 + 2x_3 + 0x_4 + x_5 + 0x_6 + 0x_7 = 10 \\\\ 2x_1 - 2x_2 + x_3 + 0x_4 + 0x_5 + 0x_6 + x_7 = 1 \\\\ x_j \geq 0 \quad (j = 1 , 2 , 3, 4, 5 , 6 , 7 ) \end{cases}\end{array} maxZ=3x1​+2x2​−x3​+0x4​+0x5​−Mx6​−Mx7​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​−4x1​+3x2​+x3​−x4​+0x5​+x6​+0x7​=4x1​−x2​+2x3​+0x4​+x5​+0x6​+0x7​=102x1​−2x2​+x3​+0x4​+0x5​+0x6​+x7​=1xj​≥0(j=1,2,3,4,5,6,7)​​

其中的 M M M 是一个很大的数值 , 没有具体的值 , 可以理解为正无穷 + ∞ +\infty +∞ , 具体使用单纯形法进行计算时 , 将其理解为大于给出的任意一个确定的数值 ;

六、人工变量法解分析

原来的线性规划称为 L P LP LP , 添加了人工变量后的新线性规划为 L P A LPA LPA ;

• 目标函数值有限 : 只要 L P LP LP 线性规划 , 可行域不为空集 ∅ \varnothing ∅ , 那么 L P A LPA LPA 线性规划一定能找到一个解 x x x , 使得 f ( x ) f(x) f(x) 是一个有限的数 , 该有限的数是与 负无穷 − ∞ -\infty −∞ 进行对比区分的 ;

• 只要 L P LP LP 线性规划 有可行解 , 那么 L P A LPA LPA 线性规划中的目标函数一定不是 负无穷 − ∞ -\infty −∞ ;

• 两个线性规划解的关系 : ( x 0 ) \begin{pmatrix} \quad x_0 \quad \\ \end{pmatrix} (x0​​) 是线性规划 L P LP LP 的可行解 , ( x 0 0 0 ) \begin{pmatrix} \quad x_0 \quad \\ \quad 0 \quad \\ \quad 0 \quad \\ \end{pmatrix} ⎝⎛​x0​00​⎠⎞​ 一定是 L P A LPA LPA 线性规划的可行解 , 将该解代入目标函数 , 目标函数一定是一个有限的数 , 不是负无穷 − ∞ -\infty −∞ ;

• 解 L P A LPA LPA 线性规划 : 构造的 L P A LPA LPA 辅助线性规划问题有单位阵 , 选取该单位阵为可行解 , 得到基可行解 , 然后开始进行迭代 ;

只要线性规划有初始基可行解 , 那么只可能有以下情况

• ① 有最优解
• ② 没有最优解

最优解情况 : 在有最优解的前提下 ;

• ① 如果人工变量等于 0 0 0 , 将人工变量去掉 , 剩余的解就是原来线性规划 L P LP LP 的最优解 ;
• ② 如果有一个或多个人工变量大于 0 0 0 , 那么说明 原线性规划 L P LP LP 没有可行解 ;

没有最优解的情况 :如果 L P A LPA LPA 线性规划没有最优解 , 那么 L P LP LP 线性规划也没有最优解 ;