吳振華王亞蓓

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

運(yùn)輸問題的對偶模型

吳振華1王亞蓓2

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

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

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

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

1 運(yùn)輸問題及模型

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

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

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

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

根據(jù)題意，每個產(chǎn)地的產(chǎn)量都要運(yù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)糧地運(yùn)往第j個需求地的運(yùn)輸量均為非負(fù)。綜上，得到該運(yùn)輸問題的數(shù)學(xué)模型（1）：

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

模型（2）可簡寫為：

2 原問題與對偶問題模型

2.1 常規(guī)模型

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

若原問題具有最優(yōu)解，其檢驗(yàn)數(shù)必定小于等于零，即σ ≤0或C - CBB-1A ≤ 0。令Y=CBB-1，則有不等式C -YA≤ 0或YA ≥C成立。由于松馳變量XS對應(yīng)價格向量CS= 0，則有不等式σS= CS- CBB-1I ≤ 0或CBB-1≥ 0（即Y ≥0）成立。同時，希望資源價格Y和數(shù)量b的乘積越小越好，即minW =Yb，則對偶問題數(shù)學(xué)模型為（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ī)對偶模型的推導(dǎo)，可得出原問題與對偶問題模型的對應(yīng)關(guān)系，如表3所示。

表3 原問題與對偶問題模型要素對應(yīng)表[2][3]

3 運(yùn)輸問題模型的對偶形式

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

由于原問題約束條件個數(shù)為6，因此可設(shè)對偶變量分別為u1、u2、u3、v1、v2和v3，即Y = (u1, u2, u3, v1, v2, v3)，同時，b = (a1, a2, a3, b1, b2, b3)T，對偶問題目標(biāo)函數(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。綜上，該運(yùn)輸問題模型的對偶形式為：

4 教學(xué)體會

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

[1] 吳振華.運(yùn)籌學(xué)[M].北京:北京理工大學(xué)出版社,2014.

[2] 謝家平.管理運(yùn)籌學(xué)[M].北京:中國人民大學(xué)出版社,2010.

[3] 常大勇.運(yùn)籌學(xué)[M].北京:中國物資出版社,2010.

[4] 熊偉.運(yùn)籌學(xué)[M].北京:機(jī)械工業(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è)及課程一體化建設(shè)項(xiàng)目”(GXTSZY212)。

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