基于線性規(guī)劃模型的運輸問題研究

肖滿紅

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

基于線性規(guī)劃模型的運輸問題研究

肖滿紅

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

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

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

一、引言

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

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

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

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

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

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

二、運輸問題的線性規(guī)劃模型

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

1．運輸問題的特征

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

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

2．運輸問題的解決策略

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

三、運輸問題解決示例

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

表1 各分工廠到各經(jīng)銷地的拖拉機(jī)運價（元／臺）

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

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

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

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

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

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

表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

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

設(shè)xij為校車從第i個居民區(qū)將一個學(xué)生送往第j個學(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)行計算，不難得最優(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；此時，接送所花的最低的總費用為1540元。學(xué)生劃分情況具體如表5所示。

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

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

表7 最佳指派方案

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

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

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

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

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

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

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

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

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

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

［4］張家善．線性規(guī)劃在產(chǎ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

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