吳振華王亞蓓

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

運(yùn)輸問(wèn)題的對(duì)偶模型

吳振華1王亞蓓2

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

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

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

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

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

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

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

這是一個(gè)典型的產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題，已知每條運(yùn)輸路線的單位運(yùn)價(jià)，為獲得總的運(yùn)輸費(fèi)用，需要確定每條運(yùn)輸路線的運(yùn)輸量，因此可設(shè)xij（i =1,2,3；j =1,2,3,4）為i個(gè)產(chǎn)糧地運(yùn)往第j個(gè)需求地的運(yùn)輸量，如表2所示，則該問(wèn)題的目標(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ù)題意，每個(gè)產(chǎn)地的產(chǎn)量都要運(yùn)到各個(gè)需求地，因此有如下等式成立：x11+ x12+ x13+ x14= 10；x21+ x22+ x23+ x24= 8；x31+ x32+ x33+ x34= 5。同時(shí)，每個(gè)需求地的需求量均得到滿足，因此有如下等式成立：x11+ x21+ x31= 5；x12+ x22+ x32= 7；x13+ x23+ x33= 8；x14+ x24+ x34= 3。另外，從第i個(gè)產(chǎn)糧地運(yùn)往第j個(gè)需求地的運(yùn)輸量均為非負(fù)。綜上，得到該運(yùn)輸問(wèn)題的數(shù)學(xué)模型（1）：

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

模型（2）可簡(jiǎn)寫(xiě)為：

2 原問(wèn)題與對(duì)偶問(wèn)題模型

2.1 常規(guī)模型

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

若原問(wèn)題具有最優(yōu)解，其檢驗(yàn)數(shù)必定小于等于零，即σ ≤0或C - CBB-1A ≤ 0。令Y=CBB-1，則有不等式C -YA≤ 0或YA ≥C成立。由于松馳變量XS對(duì)應(yīng)價(jià)格向量CS= 0，則有不等式σS= CS- CBB-1I ≤ 0或CBB-1≥ 0（即Y ≥0）成立。同時(shí)，希望資源價(jià)格Y和數(shù)量b的乘積越小越好，即minW =Yb，則對(duì)偶問(wèn)題數(shù)學(xué)模型為（5，本文稱模型（4）和（5）為常規(guī)形式。

2.2 非常規(guī)模型

2.2.1 約束條件為等式

原問(wèn)題模型為：

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

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

2.2.2 決策變量取值無(wú)約束

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

通過(guò)對(duì)常規(guī)和非常規(guī)對(duì)偶模型的推導(dǎo)，可得出原問(wèn)題與對(duì)偶問(wèn)題模型的對(duì)應(yīng)關(guān)系，如表3所示。

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

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

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

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

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

因此，YA = (u1+ v1, u1+ v2, u1+ v3, u2+ v1, u2+ v2, u2+ v3, u3+ v1, u3+ v2, u3+ v3)T= ui+ vj，簡(jiǎn)寫(xiě)為：YA = ui+ vj(i = 1,2,3; j = 1,2,3)。同時(shí)，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，可簡(jiǎn)寫(xiě)為：ui+ vj≤ cij。綜上，該運(yùn)輸問(wèn)題模型的對(duì)偶形式為：

4 教學(xué)體會(huì)

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

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

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

[3] 常大勇.運(yùn)籌學(xué)[M].北京:中國(guó)物資出版社,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－），男，河北樂(lè)亭人，桂林電子科技大學(xué)商學(xué)院副教授，博士，碩士生導(dǎo)師，研究方向?yàn)榉康禺a(chǎn)經(jīng)濟(jì)、城市土地增值與收益分配、工業(yè)工程與管理。