关于运筹学中几个问题的新议

2021-06-11刘满凤徐野温倩

大学教育 2021年5期

刘满凤徐野温倩

[摘要]运筹学是一门研究如何最优安排的学科。笔者提出了运筹学中几个问题的新议。一是用数学的语言来描述幸福就是“收入>付出”，而运筹学就是不断追求幸福的过程;二是二阶段法或大M法中的寻找初始可行基可用更为简便的方法来实现，即对标准型的增广矩阵实施初等行变换可获得线性规划问题的初始可行基，这样做使计算量大大减少;三是在求解平衡运输问题的表上作业法中，可对单位费用矩阵某行或某列减去一个常数，最优解不变，这样可大大减少计算量。

[关键词]运筹学;幸福不等式;二阶段法;运输问题

[中图分类号] O22 [文献标识码] A [文章编号] 2095-3437（2021）05-0092-04

一、运筹学中蕴含的幸福不等式“收入>付出”

幸福是人的一种主观感受，当你问100个人：“幸福是什么？”你将得到100种答案。有的人会说“只要有钱就是幸福”，又有的人说“只要有一份体面又挣钱的工作就是幸福”，还有的人说“只要和爱的人在一起就是幸福”。有的可以从心理学角度去解释幸福，有的可以从哲学角度去解释幸福，还有的可以从生理学角度去解释幸福，等等。那么从数学角度去解释幸福是什么呢？数学似乎与幸福离得太远，数学看起来没有温度，而幸福总是让人感觉暖暖的，但是数学却能归纳出幸福的一般规律，即幸福不等式“收入>付出”，而这正是运筹学的真谛。

运筹学是一门研究如何最优安排的学科，国外把它称作Operations Research，即“运作研究”。而我国把它译作“运筹学”，源于史记“运筹于帷幄之中，决胜于千里之外”，取“运筹”二字，体现运心筹谋、策略取胜。运筹学的真谛就是“收入>付出”，它总是研究如何用最小的成本取得最大的收益。如在企业生产计划问题中，它研究如何运用最小的成本（资源）获得最大的产出（利润、收益等）;或为了获得一定的产出，如何使资源使用最少。在投资问题中，它研究在风险承受范围内如何使投资收益最大;或在一定的投资收益水平之上，如何使投资风险最小。在网络运输问题中，它研究如何用最小的成本满足客户的需求。在分派问题中，它研究如何分配工作可以使效率最高或完成任务的费用最小，等。总之，一句话，运筹学就是研究如何用最少的成本获得最多收入的过程，而只要“收入>付出”，在任何问题中，在任何事情上，人们均能感觉到满足和幸福。如在投资中，投资者如果能够实现“收入>付出”，他就会感觉到满足;哪怕是收入只比付出大一点点，他也会感觉到一点点的满足;而如果“收入>>付出”即收入远远大于付出，则他会感觉到非常的满足。在工作中，如果一个人的“收入>付出”，此时的收入可以是金钱、荣誉、晋升机会、成就感、获得感等，付出可以是时间、劳动、感情等，他也会感觉到满足，由此而觉得幸福。因此，运筹学就是一个不断追求幸福的过程，是如何实现“收入>付出”的过程。

二、用初等行变换确定初始可行基的方法

我们都知道，在运筹学的线性规划问题的求解中，如果某个线性规划问题没有初始可行基，则需要用二阶段法或大M法进行求解。而二阶段法和大M法的计算量相对来说都是比较大的。因此，本文提出一种针对线性规划问题没有初始可行基解，但是计算量又比二阶段法和大M法小得多的一种确定初始可行基解的方法，即用初等行变换确定线性规划问题的初始可行基。本文通过几个典型的例题进行分析，从而可从中略见一斑。

例題1：求解下列线性规划问题

[maxz=-4x1-3x3s.t.12x1-x2-12x3≥2-32x1 +14x3=3x1，x2，x3≥0]

分析：在二阶段法中，其实增加人工变量构造辅助问题只是解决一个问题，即通过辅助问题寻找初始可行基，而这个问题我们认为，完全可以通过对标准型的增广矩阵实施初等行变换得到。在此例中，标准型的增广矩阵为[A=12-1-12-12-3201403]，对增广矩阵施行初等行变换，

[A=12-1-12-12-3201403→015121-310-160-2]，由此看到，已经得到一个单位矩阵[B=[P2，P1]=1001]，但此基是一个不可行基，因为常数列[b]为负。而且得到第一个方程约束为[x2+512x3+x4=-3]，由于[x2，x3，x4≥0]，因此这个等式是不可能成立的，即是一个矛盾的等式，所以得到原线性规划问题无可行解。由此看到，通过对标准型的约束方程增广矩阵施行初等行变换，能够很方便地找到线性规划问题的基，避免了二阶段法或大M法中的复杂计算。我们再来看一个例子。

例题2：求解下列线性规划问题 [maxz=-4x1-3x3s.t.12x1+x2+12x3≥232x1 +34x3=3x1，x2，x3≥0]

分析：我们可以用标准型的增广矩阵施行初等行变换，求出原问题的初始可行基，这样可以大大减少计算量。原问题的标准型的增广矩阵为：

[A=12112-123203403]

对上述增广矩阵施行初等行变换，得到：

[A=12112-123203403→0114-11101202]，同样得到基[B=[P2，P1]]，

这样得到两个约束方程为[ x2+14x3-x4=1x1 +12x3 =2]，

将原目标函数用非基变量表示[maxz=-4x1-3x3=-8-x3]，列出初始单纯形表（见表1）。

因此，可以非常简便地得到原问题的最优解[x1=2，x2=0，x3=0，maxz=-8]。我们再来看一个例子。

例题3：求解下列线性规划问题：[maxz=-4x1-3x3s.t.12x1+x2+12x3-23x4=232x1 -12x3 =33x1-6x2 +4x4=0x1，x2，x3，x4≥0]

分析：我们通过对标准型约束方程的增广矩阵施行初等行变换非常方便地进行求解。该问题的标准型约束方程的增广矩阵为：

[A=12112-232320-12033-6040→ ]

[12112-232-3010-6603012→]

[210-235-3010-610002][→010-2310010010002]

同样得到原问题的初始可行基[B=[P2，P3，P1]]，原约束方程化为：[ x2 -23x4=1 x3 =0x1 =2]

将原问题的目标函数用非基变量表示[maxz=-4x1-3x3=-8]，列出单纯形表（见表2）。

表2已为最优表，最优解为[x1=2，x2=1，x3=0，x4=0，maxz=-8]。

總结：以上三个例题概括了用二阶段法求解无初始可行基的线性规划问题的所有类型，求解辅助问题时，（1）在最优表中人工变量仍然无法出基，且目标函数不等于0，表明原线性规划问题无可行解;（2）在最优表中，人工变量全部出基，得到原问题的一个初始可行基;（3）在最优表中，人工变量没有全部出基，但是辅助问题的目标函数值为0，通过强行选择人工变量出基，也得到原问题的一个初始可行基。后面两种情况均可以继续进入第二阶段，求解原问题。从这三个例题中可以看到，用二阶段法求原问题的初始可行基解一般计算量都较大，而用标准型约束方程的增广矩阵施行初等行变换求原问题基的方法计算量则小得多，因而不失为一种较好的求解方法。

三、求解平衡运输问题的一种简化方法

运输问题的基本模型如下：[minz=i=1mj=1ncijxijs.t.j=1nxij=ai，（i=1，2，...，m）i=1mxij=bj，（j=1，2，...，n）xij≥0]

求解运输问题一般运用表上作业法，计算机求解时也可直接使用单纯形法。无论是运用表上作业法还是单纯形法，当费用矩阵[C=cijm×n]中的单位费用[cij]数值较大时，都不便于计算。为了解决这个难题，我们可以仿照指派问题中的匈牙利法，从费用矩阵[C=cijm×n]中每一行减去其最小值，每一列减去其最小值，得到变换后的费用矩阵[B=bijm×n]，两个费用矩阵[C=cijm×n]和[B=bijm×n]，其对应的运输问题最优解不变。

性质1：对于平衡运输问题，从费用矩阵[C=cijm×n]中某行减去一个常数[t]，某列减去一个常数[d]后得到费用矩阵[B=bijm×n]，那么，这种变化并不会引起最优解的改变。

证明如下：

模型（1）[minz=i=1mj=1ncijxijs.t.j=1nxij=ai，（i=1，2，...，m）i=1mxij=bj，（j=1，2，...，n）xij≥0]

模型（2）[minw=i=1mj=1nbijxijs.t.j=1nxij=ai，（i=1，2，...，m）i=1mxij=bj，（j=1，2，...，n）xij≥0]

设[bij=cij-ti-dj]，即由原运输问题费用矩阵中第[i]行减去一个常数项[ti]，第[j]列减去一个常数项[dj]得到。

[minw=i=1mj=1nbijxij=i=1mj=1n（cij-ti-dj）xij]

[ =i=1mj=1ncijxij-i=1mj=1ntixij-i=1mj=1ndjxij]

[ =i=1mj=1ncijxij-i=1mtij=1nxij-j=1ndji=1mxij][ =minz-i=1mtiai-j=1ndjbj]

由于[i=1mtiai]和[j=1ndjbj]均为常数，所以模型（1）和模型（2）具有相同的最优解。

由此性质，在求解运输问题时，可适当地对费用矩阵进行简化，然后再运用表上作业法进行计算，则可以大大减少计算量。下面以一个例子加以说明。

例题4：用表上作业法求以下运输问题的最优解（见表3）。

解：由于运输问题的单位费用表中的单位费用数值较大，因此，求解起来很不方便，我们先对费用矩阵进行化简，每一行减去该行的最小值，每列再减去该列的最小值，用最小元素法得到初始方案，圆圈内的数字表示运量（见表4）。