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

2023-03-28 16:26:19 浏览数 (1)

文章目录

  • 一、单纯形法总结
  • 二、人工变量法引入
  • 三、人工变量法案例
  • 四、线性规划标准型
  • 五、人工变量法
  • 六、人工变量法解分析

一、单纯形法总结

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

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

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

单纯形法求解流程 :

  • ① 找到单位阵
  • ② 最优准则 : 计算检验数
  • ③ 迭代准则 : 先根据检验数找到入基变量 , 再根据常量除以入基变量大于
0

系数 , 选择小的值对应的基变量作为出基变量 ;

  • ④ 中心元 : 找到 入基变量 与 出基变量 交叉点元素 , 这是中心元 , 中心元转为
1

, 同一列另一个系数转为

0

; 然后继续根据最优准则计算检验数 , 转到步骤 ② ;

二、人工变量法引入

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

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

三、人工变量法案例

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

begin{array}{lcl} max Z = 3x_1 2x_2 - x_3 \ \ s.tbegin{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 = 10

3 . 方程

3

转为符合要求的等式 : 方程

3

是等式 , 但是其右侧的常数小于

0

, 这里需要在等式两边都乘以

-1

, 使右侧的常数大于等于

0

;

2x_1 - 2x_2 x_3 = 1

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

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

begin{array}{lcl} max Z = 3x_1 2x_2 - x_3 \ \ s.tbegin{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.tbegin{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 = 4
  • 方程
2

构造变量

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.tbegin{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

线性规划也没有最优解 ;

变量 函数 集合 模型 原理

0 人点赞