文章目录
一、单纯形法总结
求解线性规划 , 使用的是单纯形法 ;
迭代转化 : 其将 在无穷多个可行解中迭代 , 转化为了 在有限个基可行解中进行迭代 ;
单纯形法理论基础 : 将迭代范围由大集合转为小集合 , 不会漏掉最优解 , 根据线性规划定理 , 只要有最优解 , 该最优解一定是基可行解 ;
单纯形法求解流程 :
- ① 找到单位阵
- ② 最优准则 : 计算检验数
- ③ 迭代准则 : 先根据检验数找到入基变量 , 再根据常量除以入基变量大于
0 系数 , 选择小的值对应的基变量作为出基变量 ;
- ④ 中心元 : 找到 入基变量 与 出基变量 交叉点元素 , 这是中心元 , 中心元转为
1 , 同一列另一个系数转为
0 ; 然后继续根据最优准则计算检验数 , 转到步骤 ② ;
二、人工变量法引入
上述单纯形的解法是 从单位阵出发的 , 所有的前提是有单位阵 , 线性规划中可能不存在单位阵 , 如果线性规划转化为单位阵时 , 没有单位阵 , 就需要使用 人工变量法 , 构造一个单位阵 ;
下面通过一个案例来介绍人工变量法的使用 ;
三、人工变量法案例
求解线性规划 : 使用人工变量法求解线性规划 ;
\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}四、线性规划标准型
参考 【运筹学】线性规划数学模型标准形式 ( 标准形式 | 目标函数转化 | 决策变量转化 | 约束方程转化 | 固定转化顺序 | 标准形式转化实例 ) 线性规划 普通形式 -> 标准形式 转化顺序说明 博客 , 先处理变量约束 , 再将不等式转为等式 , 最后更新目标函数 ;
1 . 处理约束变量 : 所有的约束变量都大于等于
0 , 这里无需处理 ;
2 . 将不等式转为等式 :
① 方程
1 转为等式 : 方程
1 是大于等于不等式 , 需要在方程左侧减去剩余变量
x_4 ;
-4 x_1 + 3x_2 + x_3 - x_4 = 4② 方程
2 转为等式 : 方程
2 是小于等于不等式 , 需要在方程左侧加上松弛变量
x_5 ;
x_1 - x_2 + 2x_3 + x_5 = 103 . 方程
3 转为符合要求的等式 : 方程
3 是等式 , 但是其右侧的常数小于
0 , 这里需要在等式两边都乘以
-1 , 使右侧的常数大于等于
0 ;
2x_1 - 2x_2 + x_3 = 14 . 处理目标函数取最大值 : 目标函数就是取最大值 , 无需处理 ;
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}五、人工变量法
将上述转化完毕的标准型的系数矩阵补全 :
\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}上述约束方程中没有单位阵 , 无法找到初始基可行解 , 创建初始的单纯形表 ;
上述线性规划中 , 需要找到
3 \times 3 的单位阵
\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} , 目前只有
x_5 的系数列向量是
\begin{pmatrix} \quad 0 \quad \\ \quad 1 \quad \\ \quad 0 \quad \\ \end{pmatrix} , 这里需要进行如下操作 ;
人工变量法 : 目的是人为制造单位阵 , 添加
2 个或
3 个人工变量 ;
1 构造变量
x_6 : 该变量只出现在第
1 个方程中 ;
-4 x_1 + 3x_2 + x_3 - x_4 + 0x_5 + x_6 = 42 构造变量
x7 : 该变量只出现在第
3 个方程中 ;
2x_1 - 2x_2 + x_3 + 0x_4 + 0x_5 + x_7 = 1添加了人工变量后 , 变量就变成了
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} , 原来的变量只有
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} ; 如果解出该线性规划的
7 个解 , 去掉后面的
x_6 , x_7 之后 , 该最优解不一定满足
5 个变量的线性规划 ;
如果解出的
7 个解中 ,
x_6 , x_7 都等于
0 , 此时该最优解的前
5 个变量 , 满足最初的线性规划解 ;
引入大
M : 在目标函数中 , 为
x_6 , x_7 加上系数
-M ,
M 是一个抽象数值 , 没有具体的值 , 其大于给定的任何一个值 ;
max Z = 3x_1 + 2x_2 - x_3 + 0x_4 + 0x_5 - M x_6 - Mx_7引入大
M 后最优解
x_6 , x_7 必须为
0 : 如果上述
x_6 , x_7 只要大于
0 , 即使很小 , 但是乘以一个很大的负数值
-M , 也会极大降低目标函数大小 , 因此只有两个变量取值为
0 时 , 才能使该解称为最优解 ;
添加
2 个人工变量后 , 得到 人工变量单纯形法 线性规划模型 :
\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}其中的
M 是一个很大的数值 , 没有具体的值 , 可以理解为正无穷
+\infty , 具体使用单纯形法进行计算时 , 将其理解为大于给出的任意一个确定的数值 ;
六、人工变量法解分析
原来的线性规划称为
LP , 添加了人工变量后的新线性规划为
LPA ;
LP 线性规划 , 可行域不为空集
\varnothing , 那么
LPA 线性规划一定能找到一个解
x , 使得
f(x) 是一个有限的数 , 该有限的数是与 负无穷
-\infty 进行对比区分的 ;
LP 线性规划 有可行解 , 那么
LPA 线性规划中的目标函数一定不是 负无穷
-\infty ;
\begin{pmatrix} \quad x_0 \quad \\ \end{pmatrix} 是线性规划
LP 的可行解 ,
\begin{pmatrix} \quad x_0 \quad \\ \quad 0 \quad \\ \quad 0 \quad \\ \end{pmatrix} 一定是
LPA 线性规划的可行解 , 将该解代入目标函数 , 目标函数一定是一个有限的数 , 不是负无穷
-\infty ;
LPA 线性规划 : 构造的
LPA 辅助线性规划问题有单位阵 , 选取该单位阵为可行解 , 得到基可行解 , 然后开始进行迭代 ;
只要线性规划有初始基可行解 , 那么只可能有以下情况
最优解情况 : 在有最优解的前提下 ;
0 , 将人工变量去掉 , 剩余的解就是原来线性规划
LP 的最优解 ;
0 , 那么说明 原线性规划
LP 没有可行解 ;
没有最优解的情况 :如果
LPA 线性规划没有最优解 , 那么
LP 线性规划也没有最优解 ;