肖滿(mǎn)紅

（天津機(jī)電職業(yè)技術(shù)學(xué)院，天津 300131）

基于線性規(guī)劃模型的運(yùn)輸問(wèn)題研究

肖滿(mǎn)紅

（天津機(jī)電職業(yè)技術(shù)學(xué)院，天津 300131）

運(yùn)輸是物流活動(dòng)核心環(huán)節(jié)，線性規(guī)劃是運(yùn)輸問(wèn)題的常用數(shù)學(xué)模型。本文結(jié)合案例，分析了運(yùn)輸問(wèn)題的特征及策略，揭示了運(yùn)輸問(wèn)題中線性規(guī)劃模型及其變形模型的應(yīng)用，提供了一類(lèi)提高物流效益的重要思想方法。

線性規(guī)劃；運(yùn)輸問(wèn)題；數(shù)學(xué)模型；最優(yōu)化

一、引言

隨著經(jīng)濟(jì)的發(fā)展物流業(yè)蓬勃發(fā)展，國(guó)家之間、地區(qū)之間的貿(mào)易往來(lái)愈發(fā)頻繁?？茖W(xué)地組織貨源進(jìn)行運(yùn)輸和配送，可以提升效益、優(yōu)化資源。

運(yùn)輸是物流活動(dòng)的核心環(huán)節(jié)，線性規(guī)劃是運(yùn)輸問(wèn)題的常用數(shù)學(xué)模型，利用數(shù)學(xué)知識(shí)可以得到優(yōu)化的運(yùn)輸方案。本文從分析線性規(guī)劃模型出發(fā)，研究運(yùn)輸問(wèn)題的最優(yōu)化問(wèn)題，探討提升物流的效益的方法。

線性規(guī)劃主要是研究在某些限定條件（可用線性等式或不等式表示）下，使某一線性目標(biāo)函數(shù)取得最大值（最小值）的問(wèn)題。它是定量分析管理活動(dòng)的重要方法之一。線性規(guī)劃問(wèn)題中包含決策變量、目標(biāo)函數(shù)、約束條件三個(gè)重要因素。

線性規(guī)劃的決策變量可以是多個(gè)，一般記作 x1，x2，x3，…，xn；

線性規(guī)劃的目標(biāo)函數(shù)的一般形式為： Max（Min）z＝c1x1＋c2x2＋…＋cnxn

線性規(guī)劃的約束條件一般用不等式組表示為：

二、運(yùn)輸問(wèn)題的線性規(guī)劃模型

運(yùn)輸問(wèn)題的提出源于如何使物流活動(dòng)中的運(yùn)輸路線或配送方案是最經(jīng)濟(jì)或最低成本的。

1．運(yùn)輸問(wèn)題的特征

運(yùn)輸問(wèn)題解決的是已知產(chǎn)地的供應(yīng)量、銷(xiāo)地的需求量及運(yùn)輸單價(jià)，如何尋找總配送成本最低的方案；運(yùn)輸問(wèn)題包含產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題和產(chǎn)銷(xiāo)不平衡運(yùn)輸問(wèn)題；通常將產(chǎn)銷(xiāo)不平衡問(wèn)題轉(zhuǎn)化為產(chǎn)銷(xiāo)平衡問(wèn)題來(lái)處理；運(yùn)輸問(wèn)題的條件包括需求假設(shè)和成本假設(shè)。

需求假設(shè)指每一個(gè)產(chǎn)地都有一個(gè)固定的供應(yīng)量，所有的供應(yīng)量都必須配送到目的地。與之類(lèi)似，每一個(gè)目的地都有一個(gè)固定的需求量，整個(gè)需求量都必須由出發(fā)地滿(mǎn)足；成本假設(shè)指從任何一個(gè)產(chǎn)地到任何一個(gè)銷(xiāo)地的貨物配送成本和所配送的數(shù)量成線性比例關(guān)系。產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的一般提法是：

2．運(yùn)輸問(wèn)題的解決策略

現(xiàn)實(shí)生產(chǎn)的情況往往比較復(fù)雜，許多實(shí)際問(wèn)題不一定完全符合運(yùn)輸問(wèn)題的假設(shè)，可能一些特征近似但其中的一個(gè)或者幾個(gè)特征卻并不符合運(yùn)輸問(wèn)題條件。一般來(lái)說(shuō)，如果一個(gè)問(wèn)題中涉及兩大類(lèi)對(duì)象之間的聯(lián)系或往來(lái)，且該問(wèn)題能提供運(yùn)輸問(wèn)題所需要的三類(lèi)數(shù)據(jù)：供應(yīng)量、需求量、單位運(yùn)價(jià)，那么這個(gè)問(wèn)題（不管其中是否涉及運(yùn)輸）經(jīng)適當(dāng)約束條件的處理后，基本都可以應(yīng)用運(yùn)輸問(wèn)題模型來(lái)解決。例如：⑴追求的目標(biāo)是效益最大而非成本最低，此時(shí)僅將表達(dá)式（II）中目標(biāo)函數(shù)中的改為即可；⑵部分（或全部）的供應(yīng)量（產(chǎn)量）代表的是從產(chǎn)地提供的最大數(shù)量（而不是一個(gè)固定的數(shù)值），此時(shí)只需將表達(dá)式（II）中的產(chǎn)地約束中部分（或全部）的“”改成“”即可；⑶部分（或全部）的需求量（銷(xiāo)量）代表的是銷(xiāo)地接收的最大數(shù)量（而不是一個(gè)固定的數(shù)值），此時(shí)只需將表達(dá)式（II）中的銷(xiāo)地約束中的“”部分（或全部）改成“”即可；⑷某些目的地的同時(shí)存在最大需求和最小需求，此時(shí)的解決辦法是將表達(dá)式（II）中的相應(yīng)的銷(xiāo)地約束中的“”一個(gè)式子分解成“”最大需求和“”最小需求的兩個(gè)式子即可；⑸某些配送中不能使用的出發(fā)地—目的地組合，此時(shí)的處理方法是添加一個(gè)新的約束條件xij＝0。

三、運(yùn)輸問(wèn)題解決示例

例1（產(chǎn)品運(yùn)輸）甲公司是一拖拉機(jī)生產(chǎn)商，有A1、A2兩個(gè)分廠，將生產(chǎn)的拖拉機(jī)用大卡車(chē)把它們運(yùn)送到三個(gè)經(jīng)銷(xiāo)地B1、B2、B3。表1中給出各分廠的生產(chǎn)能力、各經(jīng)銷(xiāo)地的需求量和每輛拖拉機(jī)從每個(gè)分廠到每個(gè)經(jīng)銷(xiāo)地所需的運(yùn)輸成本（單位：元）。問(wèn)應(yīng)如何調(diào)運(yùn)，才能使得總運(yùn)輸費(fèi)用最小，最小費(fèi)用是多少？

表1 各分工廠到各經(jīng)銷(xiāo)地的拖拉機(jī)運(yùn)價(jià)（元／臺(tái)）

解 由表1知，總產(chǎn)量為3000＋2000＝5000，總銷(xiāo)量為1300＋2200＋1500＝5000。由于總產(chǎn)量等于總銷(xiāo)量，故該問(wèn)題屬于產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題。

設(shè)xij為第i個(gè)分廠運(yùn)往第j個(gè)經(jīng)銷(xiāo)地的拖拉機(jī)臺(tái)數(shù)（i＝1，2；j＝1，2，3）。則

夕照輕陰郭，回車(chē)訪棗花。 山門(mén)分野色，經(jīng)閣帶林霞。 香篆穿簾細(xì)，旛風(fēng)曳柳斜。 摩娑紅杏卷，觴詠想王查。[5]

目標(biāo)函數(shù)為： Min z＝150x11＋200x12＋180x13＋250x21＋140x22＋190x23．

利用Lingo8．0（或Excel）進(jìn)行計(jì)算，不難得最優(yōu)解為：x11＝1300，x12＝200，x13＝1500，x21＝0，x22＝2000，x23＝0； 由此得到最低的總運(yùn)輸費(fèi)用為785000元。

例2（學(xué)區(qū)學(xué)生入學(xué)的劃分）某學(xué)區(qū)由五個(gè)居民區(qū)和三所學(xué)校組成，學(xué)校設(shè)專(zhuān)門(mén)校車(chē)接送學(xué)生。各學(xué)校的容量如表2所示，各居民區(qū)的學(xué)生人數(shù)如表3所示；各居民區(qū)的學(xué)生到相應(yīng)學(xué)校的校車(chē)費(fèi)用如表4所示。試問(wèn)應(yīng)怎樣給各個(gè)學(xué)校分配兒童，才能實(shí)現(xiàn)學(xué)區(qū)管理者實(shí)現(xiàn)使校車(chē)接送所花費(fèi)用最低的目的？表4 校車(chē)費(fèi)用表（單位：元）

表2 各學(xué)校的學(xué)生容量

表3 各居民區(qū)的學(xué)生人數(shù)

學(xué)校居民區(qū)1 2 3 1 0．8 1 0．6 2 1 1．1 0．8 3 0．6 0．8 0．7 4 0．5 0．6 0．7 5 1．1 0．8 0．9

解 容易計(jì)算出各居民區(qū)里的學(xué)生總?cè)藬?shù)為2350，三所學(xué)校的學(xué)生容量和為2500，二者不相等。根據(jù)問(wèn)題的特點(diǎn)，可將學(xué)?？醋鳟a(chǎn)地，居民區(qū)看作銷(xiāo)地。同時(shí)，可將校車(chē)接送各個(gè)學(xué)生的費(fèi)用看作是運(yùn)輸問(wèn)題的成本，該問(wèn)題就轉(zhuǎn)化為產(chǎn)銷(xiāo)不平衡運(yùn)輸問(wèn)題。

設(shè)xij為校車(chē)從第i個(gè)居民區(qū)將一個(gè)學(xué)生送往第j個(gè)學(xué)校的成本（i＝1，2，…，5；j＝1，2，3）。

目標(biāo)函數(shù)為：Min z＝0．8x11＋x12＋0．6x13＋x21＋1．1x22＋0．8x23＋0．6x31＋0．8x32＋0．7x33＋0．5x41＋0．6x42＋0．7x43＋1．1x51＋0．8x52＋0．9x53

表5 各居民區(qū)學(xué)生分布數(shù)目表

利用Lingo8．0（或Excel）進(jìn)行計(jì)算，不難得最優(yōu)解為：x13＝400，x23＝350，x31＝450，x33＝250，x41＝450，x42＝50，x52＝200， x11＝x12＝x21＝x22＝x32＝x43＝x51＝x53＝0；此時(shí)，接送所花的最低的總費(fèi)用為1540元。學(xué)生劃分情況具體如表5所示。

例3（變形的指派問(wèn)題）一家制藥公司，為了提升企業(yè)的競(jìng)爭(zhēng)力，決定加大科研力度，在參考市場(chǎng)調(diào)查意見(jiàn)后計(jì)劃開(kāi)發(fā)5個(gè)項(xiàng)目，并邀請(qǐng)4位科學(xué)家負(fù)責(zé)開(kāi)發(fā)。為了保證這些科學(xué)家都能夠獲得他們感興趣的項(xiàng)目，公司為此建立了一個(gè)投標(biāo)系統(tǒng)。這四位科學(xué)家都有1000點(diǎn)的投標(biāo)點(diǎn)，他們向每一個(gè)項(xiàng)目投標(biāo)，且把比較多的標(biāo)投向自己最感興趣的項(xiàng)目，具體投標(biāo)結(jié)果如表6所示：

表6 科學(xué)家投標(biāo)結(jié)果表

表7 最佳指派方案

原則上，一個(gè)人僅能負(fù)責(zé)一個(gè)項(xiàng)目，一個(gè)項(xiàng)目也只能由一位科學(xué)家來(lái)領(lǐng)導(dǎo)，但由于人少項(xiàng)目多，公司決定由朱諾博士或者王凱博士同時(shí)負(fù)責(zé)兩個(gè)項(xiàng)目。根據(jù)投標(biāo)情況，公司應(yīng)該怎樣指派，才能使得科學(xué)家的總滿(mǎn)意度最高？

解 指派問(wèn)題實(shí)際上是一種特殊的運(yùn)輸問(wèn)題，其中出發(fā)地是人，目的地是工作，而人負(fù)責(zé)完成工作時(shí)所花費(fèi)的成本或獲得的效益可以看成運(yùn)輸問(wèn)題中的單位成本。常見(jiàn)的指派問(wèn)題要求“人數(shù)與項(xiàng)目數(shù)相等”。而本問(wèn)題中人數(shù)少于項(xiàng)目數(shù)，且研究如何使得滿(mǎn)意度最高，這樣，該模型就成了指派問(wèn)題的變形模型。

可以根據(jù)題意作如下處理：科學(xué)家代表運(yùn)輸問(wèn)題中的產(chǎn)地，項(xiàng)目代表銷(xiāo)地，四位科學(xué)家投標(biāo)的標(biāo)點(diǎn)數(shù)看作運(yùn)輸問(wèn)題中的成本。不難看出，各銷(xiāo)地的銷(xiāo)量均為1，李爾博士和劉哲博士的供應(yīng)量都為1，而朱諾博士與王凱博士的供應(yīng)量都為2，總的供應(yīng)量（1＋2＋1＋2＝6）大于總的銷(xiāo)量（1＋1＋1＋1＋1＝5）。

綜上，設(shè)xij為第i個(gè)科學(xué)家負(fù)責(zé)第j個(gè)項(xiàng)目，得到目標(biāo)函數(shù)為：

利用Lingo8．0（或Excel）進(jìn)行計(jì)算，不難得最優(yōu)解為：x12＝x23＝x35＝x41＝x44＝1，其余決策變量均為0。見(jiàn)表7。其中括號(hào)內(nèi)的“是”與“否”代表科學(xué)家是否領(lǐng)導(dǎo)他最感興趣的項(xiàng)目。

總之，以上三個(gè)案例都具有啟發(fā)性，它們揭示了運(yùn)用線性規(guī)劃模型解決運(yùn)輸問(wèn)題的一般思路。在實(shí)際問(wèn)題處理中，要求決策人員準(zhǔn)確把握問(wèn)題中的產(chǎn)銷(xiāo)雙方以及各自的產(chǎn)量與銷(xiāo)量，在此基礎(chǔ)上設(shè)置好約束條件，同時(shí)提煉出運(yùn)輸問(wèn)題需要的所謂單位成本，建立運(yùn)輸問(wèn)題的數(shù)學(xué)模型。

線性規(guī)劃為決策者解決最優(yōu)化問(wèn)題提供了便捷的數(shù)學(xué)模型，對(duì)于企業(yè)或個(gè)人提升經(jīng)濟(jì)效益具有重要的價(jià)值。

［1］葉向．實(shí)用運(yùn)籌學(xué)［M］．北京：中國(guó)人民大學(xué)出版社，2006．

［2］胡運(yùn)權(quán)．運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用［M］．北京：高等教育出版社，2008．

［3］劉茂華．線性規(guī)劃在運(yùn)輸問(wèn)題中的應(yīng)用［J］．大慶師范學(xué)院學(xué)報(bào)，2007，（04）．

［4］張家善．線性規(guī)劃在產(chǎn)銷(xiāo)不平衡運(yùn)輸問(wèn)題中的應(yīng)用［J］．物流管理，2010，（05）．

Research on the Transportation Problems Based on Linear Programming Model

XIAO Man－h(huán)ong
（Tianjin Vocational Technical College of Machinery and Electricity，Tianjin，China 300131）

Transportation is a core part of the logistics while linear programming is a mathematical model commonly used in transport．With examples the paper analyzes the transport characteristics and the strategies solving transport problems，reveals the linear programming model and its deformation model applications and provides a series of important ways to improve the efficiency in logistics．

O151．2

A

1673－582X（2012）07－0110－05

2012－05－25

肖滿(mǎn)紅（1981－），男，湖南省邵陽(yáng)人，天津機(jī)電職業(yè)技術(shù)學(xué)院講師，從某個(gè)事最優(yōu)化方法機(jī)器算法、數(shù)值分析研究。