MBA數(shù)據(jù)模型與決策：運(yùn)輸問題

運(yùn)輸問題與指派問題運(yùn)輸問題(TransportationProblem)和指派問題(AssignmentProblem)屬于線性規(guī)劃問題，是線性規(guī)劃的兩類常見問題，并且這兩類問題具有特殊的數(shù)學(xué)性質(zhì)，使得管理科學(xué)家能夠開發(fā)出多種高效獨(dú)特的求解算法，所以我們專門用一章來研究。本章內(nèi)容§6.1案例研究：L食品公司的運(yùn)輸問題§6.2運(yùn)輸問題的模型與性質(zhì)§6.3應(yīng)用EXCEL和LINGO求解運(yùn)輸問題§6.4運(yùn)輸問題變形的一些應(yīng)用§6.5指派問題§6.1

L食品公司的運(yùn)輸問題例1

湖南L食品公司是生產(chǎn)食品罐頭的企業(yè)，有桔子、竹筍、野山菌三個(gè)罐頭廠，三個(gè)工廠的廠址分別在A、B、C三個(gè)靠近不同原料產(chǎn)地的城鎮(zhèn)，每個(gè)工廠都能生產(chǎn)不同品種的罐頭，但每個(gè)工廠生產(chǎn)不同品種罐頭的產(chǎn)能不同，各工廠生產(chǎn)與廠名相同的罐頭的設(shè)計(jì)產(chǎn)能要大一些。2009年6月份來自深圳、武漢、成都和西安的四個(gè)配送中心的野山菌罐頭訂單和各工廠的野山菌罐頭的計(jì)劃產(chǎn)量如表6-1所示。2009年6月每箱野山菌罐頭從各個(gè)工廠到各個(gè)配送中心的具體運(yùn)價(jià)如表6-2所示。廠址（廠名）產(chǎn)量配送中心訂單需求A(桔子)80深圳85B(竹筍)100武漢110C(野山菌)220成都75西安130合計(jì)400合計(jì)400表6-1罐頭的產(chǎn)能和配送中心需求（單位：箱）表6-2各工廠到配送中心的野山菌罐頭運(yùn)價(jià)（單位：元/箱）罐頭廠配送中心深圳武漢成都西安A(桔子)784586110B(竹筍)844179103C(野山菌)805376118表6-1、表6-2可以用下圖表示：小張的運(yùn)輸方案

（單位：箱）小張的運(yùn)輸方案需要運(yùn)費(fèi)成本是：罐頭廠（供應(yīng)）配送中心（需求）合計(jì)深圳武漢成都西安A(桔子)8000080B(竹筍)59500100C(野山菌)01575130220合計(jì)8511075130400小劉的運(yùn)輸方案

（單位：箱）小劉的運(yùn)輸方案需要運(yùn)費(fèi)成本是：罐頭廠（供應(yīng)）配送中心（需求）合計(jì)深圳武漢成都西安A(桔子)70100080B(竹筍)010000100C(野山菌計(jì)8511075130400楊經(jīng)理的思考……小劉的運(yùn)輸方案比小張的節(jié)約了140元，于是，楊經(jīng)理決定用小劉的方案。但是，會(huì)不會(huì)還有更節(jié)約的運(yùn)輸方案呢？楊經(jīng)理開始琢磨這個(gè)問題，或許以后能找到更好的方案吧，不管怎么樣，以后要在運(yùn)輸方案安排上多用點(diǎn)心思了，因?yàn)槊扛魩滋爝\(yùn)輸部都要為公司不同的產(chǎn)品訂單集中安排一次運(yùn)輸，如果每次都能用最好的方案，一年下來也是一筆可觀的費(fèi)用呢?！?.2運(yùn)輸問題的模型與性質(zhì)1運(yùn)輸問題的模型例1中提到的湖南某食品公司的問題就是一個(gè)典型的運(yùn)輸問題。在運(yùn)輸問題中，尋求從產(chǎn)地到銷地的最小的運(yùn)輸成本。運(yùn)輸問題的一般提法是這樣的：某種物資有若干個(gè)產(chǎn)地和銷地，若已知各個(gè)產(chǎn)地的產(chǎn)量、各個(gè)銷地的銷量以及各產(chǎn)地到各銷地的單位運(yùn)價(jià)（或運(yùn)輸距離）。問應(yīng)如何組織運(yùn)輸，才能使總運(yùn)費(fèi)（或總的運(yùn)輸量）最??？假定有m個(gè)產(chǎn)地，n個(gè)銷地，我們定義如下變量：——第產(chǎn)地的供應(yīng)量，i=1，2，…，m

；

——第銷地的需求量，j

=1，2，…，n；

——從產(chǎn)地到銷地的單位運(yùn)費(fèi)，i

=1，2，…，m，j

=1，2，…，n；

——產(chǎn)地到銷地的運(yùn)輸數(shù)量，i

=1，2，…，m，j

=1，2，…，n。

則該問題為求解最佳運(yùn)輸方案，即求解所有的值，使總的運(yùn)輸費(fèi)用達(dá)到最少。決策變量為

該問題的數(shù)學(xué)模型形式為：把例1的問題用數(shù)學(xué)模型表達(dá)出來就是：2運(yùn)輸問題的性質(zhì)運(yùn)輸問題中每一個(gè)產(chǎn)地都有一定的供應(yīng)量（supply）配送到銷地，每一個(gè)銷地都有一定的需求量（demand），接收從產(chǎn)地發(fā)出的產(chǎn)品，基本的運(yùn)輸問題有如下性質(zhì)：1）需求假設(shè)（TheRequirementsAssumption）每一個(gè)產(chǎn)地都有一個(gè)固定的供應(yīng)量，所有的供應(yīng)量都必須配送到銷地。與之相類似，每一個(gè)銷地都有一個(gè)固定的需求量，整個(gè)需求量都必須由產(chǎn)地滿足。2）可行解特性（TheFeasibleSolutionsProperty）當(dāng)且僅當(dāng)供應(yīng)量的總和等于需求量的總和，也就是產(chǎn)銷平衡時(shí)，運(yùn)輸問題才有可行解。3）成本假設(shè)（TheCostAssumption）：從任何一個(gè)產(chǎn)地到任何一個(gè)銷地的貨物配送成本和所配送的數(shù)量成線性比例關(guān)系，因此這個(gè)成本就等于配送的單位成本乘以配送的數(shù)量。4）整數(shù)解性質(zhì)（IntegerSolutionsProperty）只要運(yùn)輸問題的供應(yīng)量和需求量都是整數(shù)，任何有可行解的運(yùn)輸問題必然有所有決策變量都是整數(shù)的最優(yōu)解。因此，沒有必要加上所有變量都是整數(shù)的約束條件，這使得求解運(yùn)輸問題避免了整數(shù)約束所導(dǎo)致的計(jì)算復(fù)雜性大幅度增加的麻煩§6.3應(yīng)用EXCEL和LINGO求解運(yùn)輸問題1應(yīng)用EXCEL求解運(yùn)輸問題由于運(yùn)輸問題是線性規(guī)劃問題，我們可以很方便地在電子表格中建模求解。見圖6.2。應(yīng)用“規(guī)劃求解”后，我們得到一個(gè)最優(yōu)解，由圖6.2中表格的陰影部分的數(shù)據(jù)可知，A廠運(yùn)50箱到武漢、運(yùn)30箱到西安；B廠運(yùn)100箱到西安；C廠運(yùn)85箱到深圳、60箱到武漢、75箱到成都，此時(shí)總運(yùn)費(fèi)最低，最優(yōu)值是31530元。采用這個(gè)方案，食品公司6月份這批野山菌罐頭訂單的運(yùn)輸費(fèi)用比小張的方案（32390元）節(jié)約了860元，比小劉的方案（32250元）節(jié)約了720元。2LINGO使用簡(jiǎn)介L(zhǎng)INGO是用來求解線性和非線性優(yōu)化問題的簡(jiǎn)易工具。LINGO內(nèi)置了一種建立最優(yōu)化模型的語言，可以簡(jiǎn)便地表達(dá)大規(guī)模問題，利用LINGO高效的求解器可快速求解并分析結(jié)果。

因?yàn)槠?，本小?jié)只對(duì)LINGO最基本的應(yīng)用和功能結(jié)構(gòu)進(jìn)行介紹，每個(gè)功能詳細(xì)的應(yīng)用技巧請(qǐng)見本書相關(guān)的例子和LINGO的幫助文件。1)LINGO快速入門當(dāng)你在windows下開始運(yùn)行LINGO系統(tǒng)時(shí)，會(huì)得到類似下面的一個(gè)窗口：線性規(guī)劃模型在電子表格中布局的好壞關(guān)系到問題可讀性和求解方便性的高低。本節(jié)以第一章中的例1（資源分配問題）為例來說明一下如何在電子表格中描述線性規(guī)劃模型，讓我們回顧一下第一章中例1的數(shù)學(xué)模型：

Max s.t.

在模型窗口中輸入如下代碼：max=4*x1+3*x2;x1<=6;2*x2<=8;2*x1+3*x2<=18;然后點(diǎn)擊工具條上的按鈕即可。2)LINGO中的集對(duì)實(shí)際問題建模的時(shí)候，總會(huì)遇到一群或多群相聯(lián)系的對(duì)象，比如工廠、消費(fèi)者群體、交通工具和雇工等等。LINGO允許把這些相聯(lián)系的對(duì)象聚合成集（sets）。一旦把對(duì)象聚合成集，就可以利用集來最大限度的發(fā)揮LINGO建模語言的優(yōu)勢(shì)?，F(xiàn)在我們將深入介紹如何創(chuàng)建集，并用數(shù)據(jù)初始化集的屬性。學(xué)完本節(jié)后，你對(duì)基于建模技術(shù)的集如何引入模型會(huì)有一個(gè)基本的理解。（1）為什么使用集集是LINGO建模語言的基礎(chǔ)，是程序設(shè)計(jì)最強(qiáng)有力的基本構(gòu)件。借助于集，能夠用一個(gè)單一的、長(zhǎng)的、簡(jiǎn)明的復(fù)合公式表示一系列相似的約束，從而可以快速方便地表達(dá)規(guī)模較大的模型。（2）什么是集集是一群相聯(lián)系的對(duì)象，這些對(duì)象也稱為集的成員.一個(gè)集可能是一系列產(chǎn)品、卡車或雇員。每個(gè)集成員可能有一個(gè)或多個(gè)與之有關(guān)聯(lián)的特征，我們把這些特征稱為屬性。屬性值可以預(yù)先給定，也可以是未知的，有待于LINGO求解。例如:產(chǎn)品集中的每個(gè)產(chǎn)品可以有一個(gè)價(jià)格屬性；卡車集中的每輛卡車可以有一個(gè)牽引力屬性；雇員集中的每位雇員可以有一個(gè)薪水屬性，也可以有一個(gè)生日屬性等等。LINGO有兩種類型的集：原始集(primitiveset)和派生集(derivedset)。一個(gè)原始集是由一些最基本的對(duì)象組成的。一個(gè)派生集是用一個(gè)或多個(gè)其它集來定義的，也就是說，它的成員來自于其它已存在的集。（3）模型的集部分集部分是LINGO模型的一個(gè)可選部分。在LINGO模型中使用集之前，必須在集部分事先定義。集部分以關(guān)鍵字“sets:”開始，以“endsets”結(jié)束。一個(gè)模型可以沒有集部分，或有一個(gè)簡(jiǎn)單的集部分，或有多個(gè)集部分。一個(gè)集部分可以放置于模型的任何地方，但是一個(gè)集及其屬性在模型約束中被引用之前必須定義了它們。1）定義原始集為了定義一個(gè)原始集，必須詳細(xì)聲明：集的名字可選，集的成員可選，集成員的屬性定義一個(gè)原始集，用下面的語法：setname[/member_list/][:attribute_list];注意：用“[]”表示該部分內(nèi)容可選。下同，不再贅述。Setname是你選擇的來標(biāo)記集的名字，最好具有較強(qiáng)的可讀性。集名字必須嚴(yán)格符合標(biāo)準(zhǔn)命名規(guī)則：以拉丁字母或下劃線（_）為首字符，其后由拉丁字母（A—Z）、下劃線、阿拉伯?dāng)?shù)字（0，1，…，9）組成的總長(zhǎng)度不超過32個(gè)字符的字符串，且不區(qū)分大小寫。注意：該命名規(guī)則同樣適用于集成員名和屬性名等的命名Member_list是集成員列表。如果集成員放在集定義中，那么對(duì)它們可采取顯式羅列和隱式羅列兩種方式。如果集成員不放在集定義中，那么可以在隨后的數(shù)據(jù)部分定義它們①當(dāng)顯式羅列成員時(shí)，必須為每個(gè)成員輸入一個(gè)不同的名字，中間用空格或逗號(hào)擱開，允許混合使用。

例如，可以定義一個(gè)名為students的原始集，它具有成員John、Jill、Rose和Mike，屬性有sex和age： sets: students/JohnJill,RoseMike/:sex,age;endsets②當(dāng)隱式羅列成員時(shí)，不必羅列出每個(gè)集成員?？刹捎萌缦抡Z法： setname/member1..memberN/[:attribute_list];這里的member1是集的第一個(gè)成員名，memberN是集的最末一個(gè)成員名。LINGO將自動(dòng)產(chǎn)生中間的所有成員名。LINGO也接受一些特定的首成員名和末成員名，用于創(chuàng)建一些特殊的集。列表如下：隱式成員列表格式示例所產(chǎn)生集成員1..n1..51,2,3,4,5StringM..StringNCar2..car14Car2,Car3,Car4,…,Car14DayM..DayNMon..FriMon,Tue,Wed,Thu,FriMonthM..MonthNOct..JanOct,Nov,Dec,JanMonthYearM..MonthYearNOct2001..Jan2002Oct2001,Nov2001,Dec2001,Jan2002③集成員不放在集定義中，而在隨后的數(shù)據(jù)部分來定義 !集部分; sets: students:sex,age; endsets !數(shù)據(jù)部分; data: students,sex,age=John116 Jill014 Rose017 Mike113; enddata注意：開頭用感嘆號(hào)（!），末尾用分號(hào)（;）表示注釋，可跨多行。在集部分只定義了一個(gè)集students，并未指定成員。在數(shù)據(jù)部分羅列了集成員John、Jill、Rose和Mike，并對(duì)屬性sex和age分別給出了值。集成員無論用何種字符標(biāo)記，它的索引都是從1開始連續(xù)計(jì)數(shù)。在attribute_list可以指定一個(gè)或多個(gè)集成員的屬性，屬性之間必須用逗號(hào)隔開。2）定義派生集為了定義一個(gè)派生集，必須詳細(xì)聲明：集的名字父集的名字可選，集成員可選，集成員的屬性可用下面的語法定義一個(gè)派生集：setname(parent_set_list)[/member_list/][:attribute_list];setname是集的名字。parent_set_list是已定義的集的列表，多個(gè)時(shí)必須用逗號(hào)隔開。如果沒有指定成員列表，那么LINGO會(huì)自動(dòng)創(chuàng)建父集成員的所有組合作為派生集的成員。派生集的父集既可以是原始集，也可以是其它的派生集。舉例如下： sets: product/AB/; machine/MN/; week/1..2/; allowed(product,machine,week):x; endsetsLINGO生成了三個(gè)父集的所有組合共八組作為allowed集的成員。列表如下：

編號(hào)

成員 1 (A,M,1) 2

(A,M,2) 3

(A,N,1) 4

(A,N,2) 5

(B,M,1) 6

(B,M,2) 7

(B,N,1) 8

(B,N,2)成員列表被忽略時(shí)，派生集成員由父集成員所有的組合構(gòu)成，這樣的派生集成為稠密集。如果限制派生集的成員，使它成為父集成員所有組合構(gòu)成的集合的一個(gè)子集，這樣的派生集成為稀疏集。同原始集一樣，派生集成員的聲明也可以放在數(shù)據(jù)部分。一個(gè)派生集的成員列表有兩種方式生成：①顯式羅列；②設(shè)置成員資格過濾器。當(dāng)采用方式①時(shí)，必須顯式羅列出所有要包含在派生集中的成員，并且羅列的每個(gè)成員必須屬于稠密集。使用前面的例子，顯式羅列派生集的成員： allowed(product,machine,week)/AM1,AN2,BN1/;如果需要生成一個(gè)大的、稀疏的集，那么顯式羅列就很討厭。幸運(yùn)地是許多稀疏集的成員都滿足一些條件以和非成員相區(qū)分。我們可以把這些邏輯條件看作過濾器，在LINGO生成派生集的成員時(shí)把使邏輯條件為假的成員從稠密集中過濾掉。詳細(xì)內(nèi)容請(qǐng)參見LINGO幫助文件。3)模型的數(shù)據(jù)部分?jǐn)?shù)據(jù)部分提供了模型相對(duì)靜止部分和數(shù)據(jù)分離的可能性。顯然，這對(duì)模型的維護(hù)和維數(shù)的縮放非常便利。數(shù)據(jù)部分以關(guān)鍵字“data:”開始，以關(guān)鍵字“enddata”結(jié)束。在這里，可以指定集成員、集的屬性。其語法如下： object_list=value_list;對(duì)象列（object_list）包含要指定值的屬性名、要設(shè)置集成員的集名，用逗號(hào)或空格隔開。一個(gè)對(duì)象列中至多有一個(gè)集名，而屬性名可以有任意多。如果對(duì)象列中有多個(gè)屬性名，那么它們的類型必須一致。如果對(duì)象列中有一個(gè)集名，那么對(duì)象列中所有的屬性的類型就是這個(gè)集。數(shù)值列（value_list）包含要分配給對(duì)象列中的對(duì)象的值，用逗號(hào)或空格隔開。注意屬性值的個(gè)數(shù)必須等于集成員的個(gè)數(shù)?？聪旅娴睦?a)和(b)：(a) sets: set1/A,B,C/:X,Y; endsets data: X=1,2,3; Y=4,5,6; enddata在集set1中定義了兩個(gè)屬性X和Y。X的三個(gè)值是1、2和3，Y的三個(gè)值是4、5和6。也可采用如下例子中的復(fù)合數(shù)據(jù)聲明（datastatement）實(shí)現(xiàn)同樣的功能。(b) sets: set1/A,B,C/:X,Y; endsets data: X,Y=14 25 36; enddata看到這個(gè)例子，可能會(huì)認(rèn)為X被指定了1、4和2三個(gè)值，因?yàn)樗鼈兪菙?shù)值列中前三個(gè)，而正確的答案是1、2和3。假設(shè)對(duì)象列有n個(gè)對(duì)象，LINGO在為對(duì)象指定值時(shí)，首先在n個(gè)對(duì)象的第1個(gè)索引處依次分配數(shù)值列中的前n個(gè)對(duì)象，然后在n個(gè)對(duì)象的第2個(gè)索引處依次分配數(shù)值列中緊接著的n個(gè)對(duì)象，……，以此類推。4)LINGO函數(shù)LINGO有9種類型的函數(shù)：(1）基本運(yùn)算符：包括算術(shù)運(yùn)算符、邏輯運(yùn)算符和關(guān)系運(yùn)算符(2）數(shù)學(xué)函數(shù)：三角函數(shù)和常規(guī)的數(shù)學(xué)函數(shù)(3）金融函數(shù)：LINGO提供的兩種金融函數(shù)(4）概率函數(shù)：LINGO提供了大量概率相關(guān)的函數(shù)(5）變量界定函數(shù)：這類函數(shù)用來定義變量的取值范圍(6）集操作函數(shù)：這類函數(shù)為對(duì)集的操作提供幫助(7）集循環(huán)函數(shù)：遍歷集的元素，執(zhí)行一定的操作的函數(shù)(8）數(shù)據(jù)輸入輸出函數(shù)：這類函數(shù)允許模型和外部數(shù)據(jù)源相聯(lián)系，進(jìn)行數(shù)據(jù)的輸入輸出(9）輔助函數(shù)：各種雜類函數(shù)一

基本運(yùn)算符1）算術(shù)運(yùn)算符算術(shù)運(yùn)算符是針對(duì)數(shù)值進(jìn)行操作的。LINGO提供了5種二元運(yùn)算符：＾乘方﹡乘／除﹢加﹣減LINGO唯一的一元算術(shù)運(yùn)算符是取反函數(shù)“﹣”一

基本運(yùn)算符（續(xù)）這些運(yùn)算符的優(yōu)先級(jí)由高到底為：高﹣（取反）

＾﹡／低﹢﹣運(yùn)算符的運(yùn)算次序?yàn)閺淖蟮接野磧?yōu)先級(jí)高低來執(zhí)行。運(yùn)算的次序可以用圓括號(hào)“（）”來改變。二

邏輯運(yùn)算符LINGO具有９種邏輯運(yùn)算符：#not#否定該操作數(shù)的邏輯值，＃not＃是一個(gè)一元運(yùn)算符#eq#若兩個(gè)運(yùn)算數(shù)相等，則為true；否則為flase#ne#若兩個(gè)運(yùn)算符不相等，則為true；否則為flase#gt#若左邊的運(yùn)算符嚴(yán)格大于右邊的運(yùn)算符，則為true；否則為flase#ge#若左邊的運(yùn)算符大于或等于右邊的運(yùn)算符，則為true；否則為flase#lt#

若左邊的運(yùn)算符嚴(yán)格小于右邊的運(yùn)算符，則為true；否則為flase二

邏輯運(yùn)算符（續(xù)）#le#若左邊的運(yùn)算符小于或等于右邊的運(yùn)算符，則為true；否則為flase#and#僅當(dāng)兩個(gè)參數(shù)都為true時(shí)，結(jié)果為true；否則為flase#or#僅當(dāng)兩個(gè)參數(shù)都為false時(shí)，結(jié)果為false；否則為true這些運(yùn)算符的優(yōu)先級(jí)由高到低為：高#not##eq##ne##gt##ge##lt##le#低#and##or#三

關(guān)系運(yùn)算符關(guān)系運(yùn)算符與邏輯運(yùn)算符#eq#、#le#、#ge#截然不同，前者是模型中該關(guān)系運(yùn)算符所指定關(guān)系的為真描述，而后者僅僅判斷一個(gè)該關(guān)系是否被滿足：滿足為真，不滿足為假。LINGO有三種關(guān)系運(yùn)算符：“=”、“<=”和“>=”。LINGO中還能用“<”表示小于等于關(guān)系，“>”表示大于等于關(guān)系。三

關(guān)系運(yùn)算符（續(xù)）LINGO并不支持嚴(yán)格小于和嚴(yán)格大于關(guān)系運(yùn)算符。然而，如果需要嚴(yán)格小于和嚴(yán)格大于關(guān)系，比如讓A嚴(yán)格小于B：A<B，那么可以把它變成如下的小于等于表達(dá)式：A+ε<=B，這里ε是一個(gè)小的正數(shù)，它的值依賴于模型中A小于B多少才算不等。三類操作符的優(yōu)先級(jí)高 #not#﹣（取反）

＾

﹡／

﹢﹣ #eq##ne##gt##ge##lt##le# #and##or#低 <==>=（2）數(shù)學(xué)函數(shù)@abs(x)返回x的絕對(duì)值@sin(x)返回x的正弦值，x采用弧度制@cos(x)返回x的余弦值@tan(x)返回x的正切值@exp(x)返回常數(shù)e的x次方@log(x)返回x的自然對(duì)數(shù)@lgm(x)返回x的gamma函數(shù)的自然對(duì)數(shù)@sign(x)如果x<0返回-1；否則，返回1@floor(x)返回x的整數(shù)部分。當(dāng)x>=0時(shí)，返回不超過x的最大整數(shù)；當(dāng)x<0時(shí)，返回不低于x的最大整數(shù)。@smax(x1,x2,…,xn)返回x1，x2，…，xn中的最大值@smin(x1,x2,…,xn)返回x1，x2，…，xn中的最小值（3）金融函數(shù)目前LINGO提供了兩個(gè)金融函數(shù)。@fpa(I,n)返回如下情形的凈現(xiàn)值：?jiǎn)挝粫r(shí)段利率為I，連續(xù)n個(gè)時(shí)段支付，每個(gè)時(shí)段支付單位費(fèi)用。@fpl(I,n)返回如下情形的凈現(xiàn)值：?jiǎn)挝粫r(shí)段利率為I，第n個(gè)時(shí)段支付單位費(fèi)用。（4）概率函數(shù)1）@pbn(p,n,x)二項(xiàng)分布的累積分布函數(shù)。當(dāng)n和（或）x不是整數(shù)時(shí)，用線性插值法進(jìn)行計(jì)算。2）@pcx(n,x)自由度為n的χ2分布的累積分布函數(shù)。3）@peb(a,x)當(dāng)?shù)竭_(dá)負(fù)荷為a，服務(wù)系統(tǒng)有x個(gè)服務(wù)器且允許無窮排隊(duì)時(shí)的Erlang繁忙概率。4）@pel(a,x)當(dāng)?shù)竭_(dá)負(fù)荷為a，服務(wù)系統(tǒng)有x個(gè)服務(wù)器且不允許排隊(duì)時(shí)的Erlang繁忙概率。其他概率函數(shù)參考LIGNO幫助(5)變量界定函數(shù)變量界定函數(shù)實(shí)現(xiàn)對(duì)變量取值范圍的附加限制，共4種：@bin(x)限制x為0或1@bnd(L,x,U)限制L≤x≤U@free(x)取消對(duì)變量x的默認(rèn)下界為0的限制，即x可以取任意實(shí)數(shù)@gin(x)限制x為整數(shù)在默認(rèn)情況下，LINGO規(guī)定變量是非負(fù)的，也就是說下界為0，上界為+∞。@free取消了默認(rèn)的下界為0的限制，使變量也可以取負(fù)值。@bnd用于設(shè)定一個(gè)變量的上下界，它也可以取消默認(rèn)下界為0的約束。（6）集操作函數(shù)1）@in(set_name,primitive_index_1[,primitive_index_2,…])如果元素在指定集中，返回1；否則返回0。2）@index([set_name,]primitive_set_element)

該函數(shù)返回在集set_name中原始集成員primitive_set_element的索引。如果set_name被忽略，那么LINGO將返回與primitive_set_element匹配的第一個(gè)原始集成員的索引。如果找不到，則產(chǎn)生一個(gè)錯(cuò)誤。（6）集操作函數(shù)（續(xù)）3）@wrap(index,limit)

該函數(shù)返回j=index-k*limit，其中k是一個(gè)整數(shù)，取適當(dāng)值保證j落在區(qū)間[1，limit]內(nèi)。該函數(shù)相當(dāng)于index模limit再加1。該函數(shù)在循環(huán)、多階段計(jì)劃編制中特別有用。4）@size(set_name)

該函數(shù)返回集set_name的成員個(gè)數(shù)。在模型中明確給出集大小時(shí)最好使用該函數(shù)。它的使用使模型更加數(shù)據(jù)中立，集大小改變時(shí)也更易維護(hù)。（7）集循環(huán)函數(shù)集循環(huán)函數(shù)遍歷整個(gè)集進(jìn)行操作。其語法為 @function(setname[(set_index_list)[|conditional_qualifier]]: expression_list);@function相應(yīng)于下面四個(gè)集循環(huán)函數(shù)之一：1）@for該函數(shù)用來產(chǎn)生對(duì)集成員的約束?；诮ＵZ言的標(biāo)量需要顯式輸入每個(gè)約束，不過@for函數(shù)允許只輸入一個(gè)約束，然后LINGO自動(dòng)產(chǎn)生每個(gè)集成員的約束。2）@sum該函數(shù)返回遍歷指定的集成員的一個(gè)表達(dá)式的和。3）@min和@max返回指定的集成員的一個(gè)表達(dá)式的最小值或最大值。其他函數(shù)及菜單略，請(qǐng)參見教材的相關(guān)部分及LINGO幫助文檔3應(yīng)用LINGO求解運(yùn)輸問題定義工廠Plants、配送中心DCs兩個(gè)原始集和派生集Links原始集Plants有一個(gè)產(chǎn)量屬性product，DCs有一個(gè)需要量屬性demand因?yàn)閮蓚€(gè)原始集的成員很少，所以采用顯示羅列的方法以加強(qiáng)模型的可讀性。派生集有成本cost和運(yùn)量volume兩個(gè)屬性，product、demand、cost、volume四個(gè)屬性中前三個(gè)是已知的，作為輸入?yún)?shù)在數(shù)據(jù)部分給出具體數(shù)值，volume是待求解的未知決策變量。例1的程序代碼及計(jì)算見LINGO文件§6.4運(yùn)輸問題變形的一些應(yīng)用1不平衡運(yùn)輸問題一、不平衡運(yùn)輸問題的模型在例1的食品公司運(yùn)輸問題當(dāng)中，三個(gè)工廠的總產(chǎn)能（供應(yīng)量）是400箱，四個(gè)配送中心的總需求量也是400箱，這類總供應(yīng)量正好與總需求量相等的問題叫做平衡運(yùn)輸問題運(yùn)輸問題的可行解特性、整數(shù)解性質(zhì)等也是以產(chǎn)銷平衡，即為前提的然而，在實(shí)際的生產(chǎn)生活中，總供應(yīng)量超過總需求量或小于總需求量的不平衡運(yùn)輸問題，即更有可能發(fā)生不平衡型運(yùn)輸問題有以下兩種情況1)當(dāng)總供應(yīng)量大于總需求量時(shí)，2)當(dāng)總供應(yīng)量小于總需求量時(shí)，二、不平衡運(yùn)輸問題舉例例2若第一節(jié)中L食品公司的A工廠2009年6月份的野山菌罐頭產(chǎn)量增加到120箱，配送中心的訂單不變，總的產(chǎn)量就增加到了120箱，而配送中心的需求量沒有變化，使得總供應(yīng)量比總需求量多了40箱，于是可以假設(shè)有一個(gè)虛擬配送中心，需求量剛好是40箱，從各罐頭廠到虛擬配送中心的運(yùn)價(jià)都是0元/箱。這個(gè)不平衡運(yùn)輸問題在Excel電子表格中的布局、公式編輯、求解選項(xiàng)設(shè)置及求解結(jié)果見圖6.32轉(zhuǎn)運(yùn)問題前述運(yùn)輸問題產(chǎn)地與銷地的界線非常分明，產(chǎn)地只供給（輸出）貨物，銷地只需求（輸入）貨物，而實(shí)際上，絕對(duì)的輸出與輸入幾乎是不存在的，有時(shí)一地僅作為其他兩地之間輸入輸出的中轉(zhuǎn)站，更多的是有些產(chǎn)地的貨物可以或必需直達(dá)運(yùn)輸，而另外有些必需或可以經(jīng)過中轉(zhuǎn)站轉(zhuǎn)運(yùn)，我們稱這些類型的運(yùn)輸問題為轉(zhuǎn)運(yùn)問題。這里我們只討論產(chǎn)銷平衡的轉(zhuǎn)運(yùn)問題，不平衡的轉(zhuǎn)運(yùn)問題可以按上節(jié)講到的辦法轉(zhuǎn)化成平衡的問題再行研究。一、轉(zhuǎn)運(yùn)問題模型假定有

個(gè)產(chǎn)地，

個(gè)銷地，

個(gè)中轉(zhuǎn)站，我們定義如下變量：—第

i產(chǎn)地

Ai的供應(yīng)量，i=1，2，…，m；—第

j銷地Bj

的需求量，j=1，2，…,n；—產(chǎn)地

i到銷地

j的單位運(yùn)費(fèi)，i=1，2，…，m，j=1，2，…，n；—產(chǎn)地

i到中轉(zhuǎn)站

k的單位運(yùn)費(fèi)，i=1，2，…,m，k=1，2，…,p；—中轉(zhuǎn)站

k到銷地

j的單位運(yùn)費(fèi)，k=1，2，…，p，j=1，2，…，n；—產(chǎn)地

i到銷地

j的運(yùn)輸數(shù)量，i=1，2，…，m，j=1，2，…，n；—產(chǎn)地i到中轉(zhuǎn)站

k的運(yùn)輸數(shù)量，

i=1，2，…,m，k=1，2，…,p；—中轉(zhuǎn)站

k到銷地j的運(yùn)輸數(shù)量，

k=1，2，…，p，j=1，2，…，n；則該問題模型為：如果所有產(chǎn)地的物資都要經(jīng)過中轉(zhuǎn)站運(yùn)到銷地，只需要把的內(nèi)容去掉就可以，具體如下：

二、L食品公司的轉(zhuǎn)運(yùn)問題在EXCEL電子表格中的建模與求解例3湖南L食品公司的運(yùn)輸部楊經(jīng)理在尋找最節(jié)省的運(yùn)費(fèi)過程中發(fā)現(xiàn)了位于長(zhǎng)沙市和鄭州市的兩個(gè)物流中心，由于這兩個(gè)物流中心具有專業(yè)的農(nóng)產(chǎn)品運(yùn)輸設(shè)施、更為完善的運(yùn)輸網(wǎng)絡(luò)和先進(jìn)的管理水平，能以較低的運(yùn)價(jià)為楊經(jīng)理提供從工廠到配送中心的運(yùn)輸服務(wù)。經(jīng)過洽談，這兩個(gè)物流中心為楊經(jīng)理的運(yùn)費(fèi)報(bào)價(jià)如表6-5、6-6所示。由于楊經(jīng)理出色的公關(guān)技能，他仍然可以利用其他運(yùn)輸公司以前為他提供的運(yùn)價(jià)表（表6-2）上規(guī)定的直達(dá)運(yùn)價(jià)從工廠到配送中心進(jìn)行直達(dá)運(yùn)輸。為了使運(yùn)費(fèi)盡可能的節(jié)約，楊經(jīng)理希望在利用物流中心中轉(zhuǎn)的同時(shí)也并不排除從工廠到配送中心的直達(dá)運(yùn)輸方式。楊經(jīng)理應(yīng)該如何決策呢？三、L食品公司的轉(zhuǎn)運(yùn)問題在LINGO中的建模與求解定義工廠Plants、物流中心TCs和配送中心DCs三個(gè)原始集原始集Plants有一個(gè)產(chǎn)量屬性product，DCs有一個(gè)需求量屬性demand，TCs不需要定義屬性。因?yàn)槿齻€(gè)原始集的成員很少，所以都采用顯示羅列的方法以加強(qiáng)模型的可讀性。然后定義工廠直達(dá)配送中心的派生集PDlinks、工廠運(yùn)到物流中心的派生集PTlinks和物流中心轉(zhuǎn)運(yùn)到配送中心的派生集TDlinks。派生集PDlinks有成本PDcost和運(yùn)量PDvolume兩個(gè)屬性；派生集PTlinks有成本PTcost和運(yùn)量PTvolume兩個(gè)屬性；派生集TDlinks有成本TDcost和運(yùn)量TDvolume兩個(gè)屬性。模型在lingo程序中例3運(yùn)輸問題的代碼和求解結(jié)果見lingo文件或教材。四、一般的轉(zhuǎn)運(yùn)問題前文講到的中轉(zhuǎn)運(yùn)輸問題考慮到了以下兩種情況：產(chǎn)地與銷地之間沒有直達(dá)路線，貨物同產(chǎn)地到銷地必須通過某中間站轉(zhuǎn)運(yùn)；產(chǎn)地與銷地之間有直達(dá)路線，但也可以通過中轉(zhuǎn)站轉(zhuǎn)運(yùn)；更一般的運(yùn)輸問題還會(huì)考慮到下面的第三種情況：某些產(chǎn)地既輸出物資，也吸收一部分物資，也就是說相同的物資可以在一些產(chǎn)地之間相互調(diào)配；某銷地既需要物資，又可以輸出部分物資，銷地之間也可以相互調(diào)配運(yùn)輸。即產(chǎn)地或銷地本身也可以起中轉(zhuǎn)站的作用；四、一般的轉(zhuǎn)運(yùn)問題這種轉(zhuǎn)運(yùn)問題的特點(diǎn)是產(chǎn)地、銷地都可能成為中轉(zhuǎn)站，容易造成產(chǎn)量和需求量的混淆，所以解題思路是先將其轉(zhuǎn)化為平衡型運(yùn)輸問題，這一點(diǎn)和不平衡型運(yùn)輸問題是一樣的。首先來看一下轉(zhuǎn)運(yùn)問題在這個(gè)轉(zhuǎn)化中一些假定：求最大可能中轉(zhuǎn)量

Q（Q為大于總產(chǎn)量的一個(gè)數(shù)）純中轉(zhuǎn)站視為輸入量和輸出量均為Q的一個(gè)產(chǎn)地和銷地兼中轉(zhuǎn)站的產(chǎn)地視為輸入量為Q的銷地和輸出量為的產(chǎn)地兼中轉(zhuǎn)站的銷地視為輸出量為Q的產(chǎn)地和輸入量為的銷地在此假設(shè)的基礎(chǔ)上，列出各產(chǎn)地的供應(yīng)量、各銷地的需求量及各產(chǎn)銷地之間的運(yùn)價(jià)表，然后運(yùn)用前文講到的線性規(guī)劃法求解即可。例4已知某物資的有三個(gè)產(chǎn)地A1、A2、A3，四個(gè)銷地B1、B2、B3、B4，該物資各產(chǎn)地、銷地的產(chǎn)量、需求量及運(yùn)價(jià)如下表所示。產(chǎn)地產(chǎn)量銷地需求量A18B15A24B23A37B37B44產(chǎn)量合計(jì)19需求量合計(jì)19

銷地產(chǎn)地B1B2B3B4A11384A23756A34932表6-7某物資的產(chǎn)量、需求量表6-8某物資的運(yùn)價(jià)表

A1A2A3A1012A2104A3240

B1B2B3B4B10143B21021B34202B43120表6-9產(chǎn)地間互相調(diào)運(yùn)的運(yùn)價(jià)表表6-10銷地間互相調(diào)運(yùn)的運(yùn)價(jià)表另外，還假設(shè)這些物資在三個(gè)產(chǎn)地之間可以互相調(diào)運(yùn)，在四個(gè)銷地之間也可以互相調(diào)運(yùn)，其運(yùn)價(jià)表如表6-9、表6-10所示。

A1A2A3T1T2B1B2B3B4T1221033124T2314305212表6-11中轉(zhuǎn)站到產(chǎn)地、銷地及中轉(zhuǎn)站之間互相調(diào)運(yùn)的運(yùn)價(jià)表然后，再假設(shè)還有兩個(gè)純中轉(zhuǎn)站T1、T2，它們到各產(chǎn)地、各銷地及中轉(zhuǎn)站之間的運(yùn)價(jià)表如表6-11所示。在考慮從產(chǎn)地到銷地之間的直接運(yùn)輸、經(jīng)純中轉(zhuǎn)站或產(chǎn)銷地之間非直接轉(zhuǎn)運(yùn)等各種可能方案的情況下，如何將三個(gè)產(chǎn)地所生產(chǎn)的物資運(yùn)往四個(gè)銷地，使總的運(yùn)費(fèi)最省。解：從表6-8可知，從A1

到B3的運(yùn)費(fèi)是8，A3

到B3的運(yùn)費(fèi)是3，表6-9中A1

到A3的運(yùn)費(fèi)是2，這樣，從從A1

到B3的運(yùn)輸如果經(jīng)過A3中轉(zhuǎn)運(yùn)費(fèi)是2+3=5，可見這個(gè)問題中，從每個(gè)產(chǎn)地到各銷地之間的運(yùn)輸方案是很多的。為了把這個(gè)問題仍當(dāng)作一般的運(yùn)輸問題處理，可以按下面的方法做：1）由于問題中的3個(gè)產(chǎn)地、2中轉(zhuǎn)站、4個(gè)銷地都可以既看作產(chǎn)地，又可以看作銷地，因此可以把整個(gè)問題當(dāng)作有3+3+4=9個(gè)產(chǎn)地和9個(gè)銷地的擴(kuò)大運(yùn)輸問題。2）對(duì)擴(kuò)大的運(yùn)輸問題，建立擴(kuò)大的單位運(yùn)價(jià)表，如表6-12所示。

銷地產(chǎn)地

A1A2A3T1T2B1B2B3B4產(chǎn)量A101223138427A210421375623A324014493226T122103312419T231430521219B113435014319B237912102119B385321420219B446242312019銷量191919191924222623表6-12擴(kuò)大的單位運(yùn)價(jià)表3）所有中轉(zhuǎn)站的產(chǎn)量等于銷量。由于運(yùn)費(fèi)最少時(shí)不可能出現(xiàn)一批物資重復(fù)在相同的運(yùn)輸路線上來回倒運(yùn)的現(xiàn)象，所以每個(gè)純中轉(zhuǎn)站的轉(zhuǎn)運(yùn)數(shù)量不會(huì)超過總產(chǎn)量19。因此，可以規(guī)定兩個(gè)純中轉(zhuǎn)站T1、T2的產(chǎn)量和銷量均為19。由于實(shí)際的轉(zhuǎn)運(yùn)量所以，可以在每個(gè)約束條件中增加一個(gè)松馳變量，相當(dāng)于一個(gè)虛擬的轉(zhuǎn)運(yùn)站，意義就是自己運(yùn)給自己，就是每個(gè)純中轉(zhuǎn)站的實(shí)際轉(zhuǎn)運(yùn)量，對(duì)應(yīng)的運(yùn)價(jià)4）擴(kuò)大的運(yùn)輸問題中，原來的產(chǎn)地與銷地也有轉(zhuǎn)運(yùn)站的作用，所以同樣在原來產(chǎn)量與銷量的數(shù)字上加上總產(chǎn)量19，即三個(gè)產(chǎn)地A1、A2、A3的產(chǎn)量分別改成27，23，26，銷量均為19；四個(gè)銷地B1、B2、B3、B4的銷量分別改成24，22，26，23，產(chǎn)量均為19。同時(shí)引入松馳變量

按照上述方法可以重新構(gòu)成產(chǎn)銷平衡的單位運(yùn)價(jià)表，（見表6-12）。由于表6-12是一個(gè)產(chǎn)銷平衡的運(yùn)輸問題，可以用單純形法求解，這里略過求解過程，也不再舉例，具體可參考本章的例1、例3。3運(yùn)輸問題的一些應(yīng)用運(yùn)輸問題并非僅僅用來解決實(shí)際的運(yùn)輸問題，現(xiàn)實(shí)生產(chǎn)和生活中，許多決策問題具有運(yùn)輸問題的特點(diǎn)和性質(zhì)，或者可以轉(zhuǎn)化成為運(yùn)輸問題。因?yàn)檫\(yùn)輸問題的算法在求解某些問題時(shí)具有較好的效果，只要能轉(zhuǎn)化成運(yùn)輸問題，求解會(huì)變得比較簡(jiǎn)單。3運(yùn)輸問題的一些應(yīng)用例5某汽車發(fā)動(dòng)機(jī)制造廠擬計(jì)劃生產(chǎn)一批發(fā)動(dòng)機(jī)來滿足未來四個(gè)月汽車安裝的需要。為了給出最優(yōu)的進(jìn)度安排，使總成本最小，有關(guān)人員已收集數(shù)據(jù)如下表：月份計(jì)劃安裝量（臺(tái)）最大產(chǎn)量單位生產(chǎn)成本（元）單位庫存成本（元）正常時(shí)間加班時(shí)間正常時(shí)間加班時(shí)間11525104800500015022020105100520015031015550005100150425101553005500—表6-13發(fā)動(dòng)機(jī)廠生產(chǎn)數(shù)據(jù)生產(chǎn)（供應(yīng)）安裝（需求）總供應(yīng)量1月份2月份3月份4月份1月份（正常）4800495051005250251月份（加班）5000515053005450102月份（正常）99999510052505400202月份（加班）99999520053505500103月份（正常）999999999950005150153月份（加班）99999999995100525054月份（正常）99999999999999953