运输问题用检验数判别最优解的注记

毛圆洁

(无锡科技职业学院文化创意学院,江苏无锡 214028)

运输问题用检验数判别最优解的注记

毛圆洁

(无锡科技职业学院文化创意学院,江苏无锡 214028)

求解运输问题的表上作业法中一般用检验数判别可行解是否为最优解,但此方法并不适用于判别非基本最优解和部分基本最优解.

运输问题;基本最优解;基本可行解;检验数

运输问题是在实际应用中常见的一类线性规划问题,通常可以用表上作业法来求解运输问题的最优解.求解过程中,在求得运输问题的可行解后,通常利用闭回路法或位势法来计算非基变量的检验数,以判别可行解是否为最优解.

运输问题可以用以下数学模型描述

有关于运输问题如何用检验数判别最优解的如下定理.

定理 1若模型 TP的一个可行解满足:对每一非基变量xij(无运量格),都有检验数λij=cij-(ui+vj)≥0,则该可行解为最优解.

定理证明参见文献[1],其中ui和vj分别为行、列位势.由定理 1可知,在运输问题中,如果通过计算得非基变量的检验数均非负,则已求得最优解.那么,用检验数来判别运输问题的可行解是否为最优解的方法一定万无一失吗?

1 检验数不能判别非基本最优解

图 1 例1运输问题的一个可行解

在运输问题中,若某个基本可行解为最优解,则称之为基本最优解,其余的最优解被称为非基本最优解[2].

例 1判断图 1中给出的可行解是否为此运输问题的最优解.

此时,求以上运输问题非基变量的检验数出现了困难,无论是闭回路法或位势法都无法求出所有非基变量的检验数,因为表格中存在非基变量找不到闭回路,或是行列位势无法全部求出,其他求检验数的方法亦然.然而,用表上作业法容易求得此运输问题的最少运费为 45,表 1中给出的可行解的总运费也为 45,说明表 1中给出的可行解确为此运输问题的最优解,而造成无法用检验数判别其是否为最优解的原因是此可行解为非基本最优解[3].

在运输问题中,m+n-1个变量构成基本可行解的基变量的充分必要条件是它们不包含闭回路.而在此例中,(A2,B2)、(A2,B3)、(A3,B2)和(A3,B3)4个变量构成一个闭回路,所以此可行解并非基本可行解,因而也不是基本最优解.

既然检验数不能用来判别非基本最优解,那么,是否所有的基本最优解都能用检验数来判别?

2 检验数不能判别所有的基本最优解

例 2求表 1所示的运输问题的最优解.

用伏格尔法求此运输问题的初始可行解,得到一个退化的基本可行解,为了使基变量个数为m+n-1个,添加一个“0”元,考虑到基本可行解的基变量之间不能形成闭回路,可以将“0”元添加在(A1,B1)处,如图 2[4].

表1 产销平衡运输表

图2 例2运输问题的一个可行解

图3 例2运输问题的另一可行解

此时,通过计算非基变量的检验数,可以得到非基变量(A1,B4)处的检验数为σ14=-1,由定理 1,图 2中的基本可行解并非最优解.考虑用闭回路法对此基本可行解进行改进,在图 2中找到(A1,B4)的闭回路,调整量θ取闭回路偶数顶点上调运量的最小值,即θ=min[0,4]=0,于是基变量为(A1,B1)换出基的变量,然后在闭回路奇数顶点运输量的值均加上调整量θ=0,非基变量(A1,B4)为换入基的变量,于是得改进后的基本可行解,见图 3.

计算图 3中各非基变量的检验数,分别为σ11=1,σ13=1,σ22=5,σ23=4,σ31=3,σ32=6,所有非基变量的检验数均非负,由定理 1,可知图 3中的基本可行解即为此运输问题的最优解,也是基本最优解[5].

观察比较图 2和图 3中的两个基本可行解,除 0基元的位置不同外,两个可行解无其他区别,总运费的取值也应该一致.若图 3中的基本可行解是基本最优解,那么图 2中的基本可行解也应为基本最优解.而检验数判别却给出了不同的结论,可见检验数不适用于所有的基本最优解的判别.

3 结论

在运输问题中,用检验数来判别最优解并非万无一失,面对非基本最优解,检验数判别可能束手无策,而检验数均非负也仅是判别基本最优解的充分而非必要条件,此均为定理 1中未提及的部分.由于运输问题是一类特殊的线性规划问题,以上结论亦可在线性规划中进行推广.

[1] 俞玉森.数学规划的原理和方法[M].武汉:华中理工大学出版社,1985.

[2] 黄桐城.运筹学基础教程[M].上海:上海人民出版社,2007.

[3] 胡运权.运筹学教程[M].北京:清华大学出版社,1998.

[4] 唐文广,吴振奎,王全文,等.运输问题的退化解及表解中 0元的添加[J].数学的实践与认识,2009(1):160-165.

[5] 吴振奎,王全文,刘振航.线性规划问题通解表示的注记[J].运筹与管理,2004,13(1):63-67.

A Note on Using Test Number D istinguishing Opt imal Solution in Transportation Problems

MAO Yuan-jie

(College of Culture and Creativity,W uxi Professional College of Science and Technology,W uxi214028,China)

In the table-working method of transportation problems,test number is generally used to distinguish whether the feasible solution is the optimal solution,but thismethod isn’t suitable for distinguishing non-basic optimal solution and partial basic optimal solution.

transportation problems;basic optimal solution;basic feasible solution;test number

O221.1

A

1007-0834(2010)04-0009-02

10.3969/j.issn.1007-0834.2010.04.004

2010-09-06

毛圆洁(1983—),女,江苏无锡人,无锡科技职业学院文化创意学院教师.