運輸問題的對偶模型

吳振華王亞蓓

（1.桂林電子科技大學商學院，廣西 桂林 541004；2.桂林電子科技大學信息科技學院，廣西 桂林 541004）

運輸問題的對偶模型

吳振華1王亞蓓2

（1.桂林電子科技大學商學院，廣西 桂林 541004；2.桂林電子科技大學信息科技學院，廣西 桂林 541004）

線性規(guī)劃原問題與對偶模型之間的轉(zhuǎn)化方法一直是普通高校經(jīng)營類本科生《運籌學》課程的教學重點。運輸問題是線性規(guī)劃中的一類典型問題，其屬于非常規(guī)線性規(guī)劃模型，掌握運輸問題原模型與對偶模型之間的轉(zhuǎn)化過程對于學習后續(xù)相關(guān)內(nèi)容極為重要。文章首先推導出“常規(guī)”與“非常規(guī)”線性規(guī)劃問題模型的對偶形式，然后總結(jié)線性規(guī)劃模型與對偶問題模型的對應關(guān)系，最后舉例說明運輸問題模型的對偶形式。

線性規(guī)劃；運輸問題；對偶模型

《運籌學》是普通高校經(jīng)營類本科生的基礎必修課，對偶規(guī)劃則是線性規(guī)劃問題中的重要內(nèi)容，也是教學難點。對偶模型的提出以及模型轉(zhuǎn)化問題是學習對偶性質(zhì)（定理）的重要基礎，但在已有教材中只是直接給出線性規(guī)劃及對偶模型的對應關(guān)系，較少對偶形式轉(zhuǎn)化的推導過程進行詳細說明，因此學生在自學時往往感覺力不從心。運輸問題模型屬于非常規(guī)線性規(guī)劃問題模型，具有“目標函數(shù)求最小值”、“約束條件為等式”等特點，如果不能熟練掌握原問題與對偶問題模型的轉(zhuǎn)化方法，難以迅速寫出其對偶模型。為此，本文詳細介紹線性規(guī)劃原問題與對偶問題模型的推導過程，總結(jié)兩者的對應關(guān)系，舉例說明運輸問題模型的轉(zhuǎn)化過程，為深刻理解對偶規(guī)劃內(nèi)容以及學習相關(guān)內(nèi)容提供參考。

1 運輸問題及模型

運輸問題是指在某時期內(nèi)將供應地的某類物資，分別運到需要這些物資的地區(qū)，在已知各地供應量和需要量及各地之間的單位運輸費用時，制定總運輸費用最小的調(diào)運方案。例如，有三個產(chǎn)糧區(qū)A1、A2、A3，可供糧食為10、8、5，將糧食運往B1、B2、B3、B4四個地區(qū)，需求量分別為5、7、8、3。產(chǎn)糧地到需求地的單位運價如表1所示，問如何安排才能使總的運輸費用最少[1]？

表1 產(chǎn)糧地到需求地的單位運價

這是一個典型的產(chǎn)銷平衡運輸問題，已知每條運輸路線的單位運價，為獲得總的運輸費用，需要確定每條運輸路線的運輸量，因此可設xij（i =1,2,3；j =1,2,3,4）為i個產(chǎn)糧地運往第j個需求地的運輸量，如表2所示，則該問題的目標函數(shù)為：min S =3x11+ 2x12+ 6x13+ 3x14+ 5x21+ 3x22+8x23+ 2x24+ 4x31+ x32+ 2x33+ 9x34。

表2 產(chǎn)糧地運往需求地的運輸量

根據(jù)題意，每個產(chǎn)地的產(chǎn)量都要運到各個需求地，因此有如下等式成立：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個產(chǎn)糧地運往第j個需求地的運輸量均為非負。綜上，得到該運輸問題的數(shù)學模型（1）：

一般而言，對于產(chǎn)銷平衡運輸問題，通常設xij( i =1, 2, …, m；j=1, 2, …, n)為第i個產(chǎn)地到第j個銷地的運量，則數(shù)學模型為：

模型（2）可簡寫為：

2 原問題與對偶問題模型

2.1 常規(guī)模型

原問題數(shù)學模型可用矩陣形式（4）表達。

若原問題具有最優(yōu)解，其檢驗數(shù)必定小于等于零，即σ ≤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和數(shù)量b的乘積越小越好，即minW =Yb，則對偶問題數(shù)學模型為（5，本文稱模型（4）和（5）為常規(guī)形式。

2.2 非常規(guī)模型

2.2.1 約束條件為等式

原問題模型為：

根據(jù)模型（4）和（5）可轉(zhuǎn)化為對偶形式，過程如下：

最終得到非常規(guī)線性規(guī)劃問題的對偶模型（7）：

2.2.2 決策變量取值無約束

令X = X′-X"，模型（8）可轉(zhuǎn)化為模型（9）。

通過對常規(guī)和非常規(guī)對偶模型的推導，可得出原問題與對偶問題模型的對應關(guān)系，如表3所示。

表3 原問題與對偶問題模型要素對應表[2][3]

3 運輸問題模型的對偶形式

已知某運輸問題模型（10），試求其對偶問題模型[4]？

由于原問題約束條件個數(shù)為6，因此可設對偶變量分別為u1、u2、u3、v1、v2和v3，即Y = (u1, u2, u3, v1, v2, v3)，同時，b = (a1, a2, a3, b1, b2, b3)T，對偶問題目標函數(shù)為：

原問題模型中系數(shù)矩陣為：

因此，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 教學體會

了解“常規(guī)”和“非常規(guī)”線性規(guī)劃問題與對偶問題的模型轉(zhuǎn)化過程，有助于理解模型之間決策變量與約束條件之間的對應關(guān)系，為學習對偶性質(zhì)（定理）及后續(xù)內(nèi)容提供幫助，例如，在掌握運輸問題對偶模型之后，學習表上作業(yè)法中的檢驗方法—位勢變量法時會倍感輕松。然而，在教學過程中發(fā)現(xiàn)，許多學生對表3的記憶和使用仍然存在著一定的困難。為此提出以下建議：首先，選擇兩道典型習題，應含以下信息：目標函數(shù)求max和min，約束條件中不等式符號有“≥”、“≤”和“=”，決策變量取值范圍有“≥0”、“≤0”和“取值無約束”；然后，參照表3將原問題模型轉(zhuǎn)化成對偶形式，再以對偶模型為原問題進行轉(zhuǎn)化，只需重復兩遍就能牢牢記住轉(zhuǎn)化過程，切忌死記硬背。

[1] 吳振華.運籌學[M].北京:北京理工大學出版社,2014.

[2] 謝家平.管理運籌學[M].北京:中國人民大學出版社,2010.

[3] 常大勇.運籌學[M].北京:中國物資出版社,2010.

[4] 熊偉.運籌學[M].北京:機械工業(yè)出版社,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

廣西壯族自治區(qū)教育廳資助“工業(yè)工程特色專業(yè)及課程一體化建設項目”(GXTSZY212)。

吳振華（1972－），男，河北樂亭人，桂林電子科技大學商學院副教授，博士，碩士生導師，研究方向為房地產(chǎn)經(jīng)濟、城市土地增值與收益分配、工業(yè)工程與管理。