运筹学教学|快速掌握人工变量法（Artificial variable method）（附Java代码及算例）

运筹学教学|快速掌握人工变量法

在之前的推文中，我们学习了单纯形法，顺利解决了约束条件都是“≤”的线性规划问题。同时为了讲解方便，我们都是使用约束方程系数矩阵中带单位矩阵、约束符号为“=”的算例。那肯定有人会问小编：更加常规的线性规划问题如何求解呢？为了响应群众号召，今天，小编就来带大家了解一下人工变量法！学会之后，“≤”“≥”或“＝”型的约束的线性规划问题都顺利解决，妥妥的~

内容提要

1.什么是人工变量法

2.大M法介绍

3.两阶段法介绍

4.人工变量法Java实现

01

人工变量法

在用单纯形法求解线性规划问题时，需要有一个单位矩阵作为初始基。若标准化后找不到单位矩阵，就需要在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。这种人为加的变量称为人工变量，构成的可行基称为人工基，用人工变量作桥梁的求解方法称为人工变量法（Artificial variable method）。

所以，人工变量法是帮助我们寻求原问题的初始可行基的一个方法。

关于线性规划的单纯形法，过去的推文里我们有介绍过，还不懂的同学可以参考这篇推文：

运筹学教学|十分钟快速掌握单纯形法（附C++代码及算例）

易知，当原线性规划问题的系数矩阵中本来就含有单位矩阵（此情况较少见，没有代表性，下文不再考虑）或为如下形式时，不需要加入人工变量即可求解：

其中X_s是松弛变量组成的向量。

可见当所有约束是(≤)时，加入松弛变量化为标准型即可得到一个单位矩阵，取这个单位矩阵为初始基，很容易得到一个初始基可行解，从而建立单纯形表。

但存在(=)和（≥）约束条件的线性规划问题则不是如此。对于（≥）型约束来说，标准化时需添加剩余变量，其系数为-1，而对(=)型约束，则不需添加松弛变量，因此标准化后缺少足够的松弛变量的系数组成十分直观的单位矩阵，也即无法不做变换地找到基可行解。

这时候就可以利用人工变量法进行求解。

由于人工变量是在等式中人为添加的，只有当人工变量等于0时，约束条件才是它本来的意义。

人工变量法包括大M法和两阶段法，两者引入人工变量的目的和原则相同，所不同的时处理人工变量的方法。

下文将分别对两者进行详细介绍

02

大M法

在将原线性规划问题转化为标准型之后，得到如下形式：

假设上述等式约束中均无单位列向量。我们在每个约束中人为的加入一个变量，将约束化为：

由于新约束要与原约束等价当且仅当所有的人工变量取值为零，为确保引入人工变量后新的线性规划问题与原线性规划问题求解一致，我们在新的线性规划目标函数中设人工变量的系数为-M（M>0为一充分大的数,不需要给出具体的数值），其作用为罚因子。当人工变量是基变量且取值大于0时,目标函数就不可能达到最大值，因此原问题只要有可行解，新的线性规划问题的最优解中人工变量的取值一定为0。

如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。这种方法称为大M单纯形法（简称大M法）。

在得到新问题的最优解后，去掉人工变量便得到原问题的最优解，相应的在新问题的最终单纯形表中去掉人工变量那一块即为原问题的最优单纯形表。

下面我们来看一个例子~

已标准化，发现系数矩阵中没有单位矩阵，不符合构造初始可行基的条件，需加入人工变量 。为保证人工变量为0，在目标函数中令其系数为-M。

按大M法构造人造基，引入人工变量x_4 , x_5 的辅助问题如下：

之后，再按照单纯形法的步骤进行求解即可。若基变量中含非零的人工变量，则无可行解；否则，有最优解。

需要注意的是，在加入人工变量时，实际上不一定每个约束都加入人工变量，例如某约束是“≤”型，则在加入松弛变量后，该松弛变量即可作为基变量。当若目标函数是求最小值，则新问题的目标函数中人工变量项应改为＋Mx_{n+1} + … +Mx_{n+m} 。

是不是很简单呢~

03

两阶段法

两阶段法，顾名思义，分为两个阶段进行求解。

第一阶段

求解一个辅助线性规划。目标函数取所有人工变量之和，并取极小化；如果辅助线性规划存在一个基本可行解，使目标函数的最小值等于零，则所有人工变量都已经“离基”。表明原问题已经得了一个初始的基本可行解，可转入第二阶段继续计算；否则说明原问题没有可行解，可停止计算。

第二阶段

去掉人工变量，还原目标函数系数，写出初始单纯形表，再继续用单纯形法求解即可。求得的最优解即为原线性规划问题的最优解。

以上两个过程称为两阶段法。

同样，在加入人工变量时，实际上不一定每个约束都加入人工变量。

下面我们也看一道例题：

构造第一阶段问题并求解：

注意：不需要三个人工变量！

将以上辅助问题运用单纯形法求解后，得到最终单纯形表（第一阶段）：

发现目标函数最小值等于零，可以进入第二阶段。

第二阶段：将第一阶段的最终表中的人工变量删去，填入原问题的目标函数的系数， 计算检验数，写出第二阶段单纯形表。继续求解即可。

04

人工变量法Java实现

代码分为Main、Data、ArtificialVariableMethod三个类。Main为主函数入口，Data实现线性规划问题的输入以及单纯形表和结果的输出，ArtificialVariableMethod实现人工变量法。

具体代码和输入的算例比较长，小编就不放出来啦，感兴趣的小伙伴可在在留言区获得下载方式。

需要注意的是，代码中默认使用大M法，大M法中的M理论上为一充分大的数，代码中以具体数值999.0代替。同学们可根据具体情况更改M的数值。（如当约束系数超过三位数时，此时M取999.0显然不够准确。一般来说M越大，准确度越高）。还有，并不是所有的问题都需要使用人工变量法，但是考虑到代码的简化，小编将两种情况都融合在人工变量法的代码中，当出现需要使用人工变量法的情况时使用人工变量法，不需要时则直接执行单纯形法。

为简化代码，我们这里要求输入最大化问题。

算例输入：

输出单纯形表：

输出最优解：

推荐书籍：

1.Operations Research Applications and Algorithms, Wayne L. Winston（本文内容具体在第四章进行介绍）

2.运筹学 《运筹学》教材编写组，清华大学出版社（本文内容具体在第二章进行介绍）

（我们将在留言区里面把这本书的百度网盘链接给出，是不是很激动！）

- END -

文案&代码：胡心瑶（华中科技大学管理学院本科二年级）

指导老师：秦虎老师（华中科技大学管理学院）

排版：程欣悦（荆楚理工学院本科三年级）

如对文中内容有疑问，欢迎交流。PS：部分资料来自网络。

如有需求，可以联系：

秦虎老师（华中科技大学管理学院：professor.qin@qq.com）

胡心瑶（华中科技大学管理学院本科二年级：1603945923@qq.com）

程欣悦 （荆楚理工学院本科三年级：1293900389@qq.com）