运输问题的对偶模型

吴振华王亚蓓

（1.桂林电子科技大学商学院，广西 桂林 541004；2.桂林电子科技大学信息科技学院，广西 桂林 541004）

运输问题的对偶模型

吴振华1王亚蓓2

（1.桂林电子科技大学商学院，广西 桂林 541004；2.桂林电子科技大学信息科技学院，广西 桂林 541004）

线性规划原问题与对偶模型之间的转化方法一直是普通高校经营类本科生《运筹学》课程的教学重点。运输问题是线性规划中的一类典型问题，其属于非常规线性规划模型，掌握运输问题原模型与对偶模型之间的转化过程对于学习后续相关内容极为重要。文章首先推导出“常规”与“非常规”线性规划问题模型的对偶形式，然后总结线性规划模型与对偶问题模型的对应关系，最后举例说明运输问题模型的对偶形式。

线性规划；运输问题；对偶模型

《运筹学》是普通高校经营类本科生的基础必修课，对偶规划则是线性规划问题中的重要内容，也是教学难点。对偶模型的提出以及模型转化问题是学习对偶性质（定理）的重要基础，但在已有教材中只是直接给出线性规划及对偶模型的对应关系，较少对偶形式转化的推导过程进行详细说明，因此学生在自学时往往感觉力不从心。运输问题模型属于非常规线性规划问题模型，具有“目标函数求最小值”、“约束条件为等式”等特点，如果不能熟练掌握原问题与对偶问题模型的转化方法，难以迅速写出其对偶模型。为此，本文详细介绍线性规划原问题与对偶问题模型的推导过程，总结两者的对应关系，举例说明运输问题模型的转化过程，为深刻理解对偶规划内容以及学习相关内容提供参考。

1 运输问题及模型

运输问题是指在某时期内将供应地的某类物资，分别运到需要这些物资的地区，在已知各地供应量和需要量及各地之间的单位运输费用时，制定总运输费用最小的调运方案。例如，有三个产粮区A1、A2、A3，可供粮食为10、8、5，将粮食运往B1、B2、B3、B4四个地区，需求量分别为5、7、8、3。产粮地到需求地的单位运价如表1所示，问如何安排才能使总的运输费用最少[1]？

表1 产粮地到需求地的单位运价

这是一个典型的产销平衡运输问题，已知每条运输路线的单位运价，为获得总的运输费用，需要确定每条运输路线的运输量，因此可设xij（i =1,2,3；j =1,2,3,4）为i个产粮地运往第j个需求地的运输量，如表2所示，则该问题的目标函数为：min S =3x11+ 2x12+ 6x13+ 3x14+ 5x21+ 3x22+8x23+ 2x24+ 4x31+ x32+ 2x33+ 9x34。

表2 产粮地运往需求地的运输量

根据题意，每个产地的产量都要运到各个需求地，因此有如下等式成立：x11+ x12+ x13+ x14= 10；x21+ x22+ x23+ x24= 8；x31+ x32+ x33+ x34= 5。同时，每个需求地的需求量均得到满足，因此有如下等式成立：x11+ x21+ x31= 5；x12+ x22+ x32= 7；x13+ x23+ x33= 8；x14+ x24+ x34= 3。另外，从第i个产粮地运往第j个需求地的运输量均为非负。综上，得到该运输问题的数学模型（1）：

一般而言，对于产销平衡运输问题，通常设xij( i =1, 2, …, m；j=1, 2, …, n)为第i个产地到第j个销地的运量，则数学模型为：

模型（2）可简写为：

2 原问题与对偶问题模型

2.1 常规模型

原问题数学模型可用矩阵形式（4）表达。

若原问题具有最优解，其检验数必定小于等于零，即σ ≤0或C - CBB-1A ≤ 0。令Y=CBB-1，则有不等式C -YA≤ 0或YA ≥C成立。由于松驰变量XS对应价格向量CS= 0，则有不等式σS= CS- CBB-1I ≤ 0或CBB-1≥ 0（即Y ≥0）成立。同时，希望资源价格Y和数量b的乘积越小越好，即minW =Yb，则对偶问题数学模型为（5，本文称模型（4）和（5）为常规形式。

2.2 非常规模型

2.2.1 约束条件为等式

原问题模型为：

根据模型（4）和（5）可转化为对偶形式，过程如下：

最终得到非常规线性规划问题的对偶模型（7）：

2.2.2 决策变量取值无约束

令X = X´-X"，模型（8）可转化为模型（9）。

通过对常规和非常规对偶模型的推导，可得出原问题与对偶问题模型的对应关系，如表3所示。

表3 原问题与对偶问题模型要素对应表[2][3]

3 运输问题模型的对偶形式

已知某运输问题模型（10），试求其对偶问题模型[4]？

由于原问题约束条件个数为6，因此可设对偶变量分别为u1、u2、u3、v1、v2和v3，即Y = (u1, u2, u3, v1, v2, v3)，同时，b = (a1, a2, a3, b1, b2, b3)T，对偶问题目标函数为：

原问题模型中系数矩阵为：

因此，YA = (u1+ v1, u1+ v2, u1+ v3, u2+ v1, u2+ v2, u2+ v3, u3+ v1, u3+ v2, u3+ v3)T= ui+ vj，简写为：YA = ui+ vj(i = 1,2,3; j = 1,2,3)。同时，YA ≤ C，具体为：u1+ v1≤ c11，u1+ v2≤ c12，u1+ v3≤ c13，u2+ v1≤ c21，u2+ v2≤ c22，u2+ v3≤ c23，u3+ v1≤ c31，u3+ v2≤ c32和u3+ v3≤c33，可简写为：ui+ vj≤ cij。综上，该运输问题模型的对偶形式为：

4 教学体会

了解“常规”和“非常规”线性规划问题与对偶问题的模型转化过程，有助于理解模型之间决策变量与约束条件之间的对应关系，为学习对偶性质（定理）及后续内容提供帮助，例如，在掌握运输问题对偶模型之后，学习表上作业法中的检验方法—位势变量法时会倍感轻松。然而，在教学过程中发现，许多学生对表3的记忆和使用仍然存在着一定的困难。为此提出以下建议：首先，选择两道典型习题，应含以下信息：目标函数求max和min，约束条件中不等式符号有“≥”、“≤”和“=”，决策变量取值范围有“≥0”、“≤0”和“取值无约束”；然后，参照表3将原问题模型转化成对偶形式，再以对偶模型为原问题进行转化，只需重复两遍就能牢牢记住转化过程，切忌死记硬背。

[1] 吴振华.运筹学[M].北京:北京理工大学出版社,2014.

[2] 谢家平.管理运筹学[M].北京:中国人民大学出版社,2010.

[3] 常大勇.运筹学[M].北京:中国物资出版社,2010.

[4] 熊伟.运筹学[M].北京:机械工业出版社,2005.

Dual model transport problem

The problem with the original linear programming method for converting between the dual model has been the focus of ordinary business class teaching undergraduate colleges "Operations Research" course. Transportation is a linear programming problem in a class of typical problems, their unconventional linear programming model, master transportation problem with the original model of the transformation process between the dual model is extremely important for the study follow-up related content. This paper deduced the "General" and "unconventional" linear programming problem model dual form, and then summarize the correspondence between linear programming model with the dual problem of the model, and finally illustrate the dual form of transportation problem model.

linear programming; transportation issues; dual model

E83

A

1008-1151(2015)03-0150-03

2015-02-12

广西壮族自治区教育厅资助“工业工程特色专业及课程一体化建设项目”(GXTSZY212)。

吴振华（1972－），男，河北乐亭人，桂林电子科技大学商学院副教授，博士，硕士生导师，研究方向为房地产经济、城市土地增值与收益分配、工业工程与管理。