運(yùn)籌學(xué)論文

——基于Matlab運(yùn)輸問題求解方法探究摘要：運(yùn)輸行業(yè)的重要性隨著中國經(jīng)濟(jì)的不斷發(fā)展而快速提高，為了降低物流成本，我們有必要研究物流運(yùn)輸中如何組織物資調(diào)運(yùn)才能使總運(yùn)輸成本最少這一重要問題。而傳統(tǒng)的手工解決方式存在著效率低、計(jì)算繁瑣、數(shù)據(jù)易丟失等缺點(diǎn)，因此利用MATLAB軟件來計(jì)算出最佳結(jié)果是很有必要的。本論文以運(yùn)輸問題中一個(gè)典型的案例為例闡述了基于MATLAB的定量分析方法，解決了運(yùn)輸最優(yōu)方案編制中求解這一大難題，可以廣泛應(yīng)用于物流配送領(lǐng)域，對實(shí)踐工作具有較強(qiáng)的指導(dǎo)意義。關(guān)鍵字：Matlab運(yùn)輸問題

產(chǎn)銷不平衡問題一、線性規(guī)劃與運(yùn)輸問題：

線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，它是最優(yōu)化問題領(lǐng)域中最簡單、最基本和使用最廣泛的方法。在交通運(yùn)輸領(lǐng)域中，運(yùn)輸是一個(gè)最基本的功能，也是物流的核心問題。將同一種物資從幾個(gè)不同的發(fā)貨點(diǎn)運(yùn)到另外幾個(gè)不同的收貨點(diǎn)，因?yàn)檫\(yùn)費(fèi)是單位運(yùn)價(jià)和運(yùn)輸量的乘積，所以如何選擇一個(gè)合理的運(yùn)輸方案，使總運(yùn)費(fèi)最省，這是一個(gè)很有應(yīng)用價(jià)值的問題，這類問題就稱為運(yùn)輸問題。研究物資運(yùn)輸過程中最優(yōu)的運(yùn)輸方案，需要在滿足各種資源限制的條件下，找到使運(yùn)輸總成本最少的調(diào)運(yùn)方案。實(shí)踐中如果建立數(shù)學(xué)模型，用線性規(guī)劃的方法來解決這一問題，則可以節(jié)省大量的工作，但由于此類問題所涉及的條件變量較多，一般的數(shù)學(xué)方法運(yùn)算難度較大，結(jié)果不容易求出，而如果能有效的借助MATLAB軟件中強(qiáng)大的運(yùn)算功能則可以得到事半功倍的效果。二、Matlab求解運(yùn)輸問題的原理：在Matlab中構(gòu)建函數(shù)l（x）用來解決線性規(guī)劃問題。眾所周知，運(yùn)輸問題的最優(yōu)解本質(zhì)屬于極值問題，極值有最大和最小兩種，而極大值問題的求解可以轉(zhuǎn)化為極小值問題，因此在Matlab中以求極小值為標(biāo)準(zhǔn)形式，構(gòu)建的函數(shù)l（x）的具體格式如下：[X，v，e，o，l]＝l（F，A，b，m，n，M，N，P，Z）式中：X為問題的解向量；F為由目標(biāo)函數(shù)的系數(shù)構(gòu)成的向量；A為一個(gè)矩陣；b為一個(gè)向量，表示線性規(guī)劃中不等式約束條件，A，b是系數(shù)矩陣和右端向量；m和n為線性規(guī)劃中等式約束條件中的系數(shù)矩陣和右端向量；M和N為約束變量的下界和上界向量；P為給定的變量的初始值；Z為控制規(guī)劃過程的參數(shù)系列；v為優(yōu)化結(jié)束后得到的目標(biāo)函數(shù)值。e＝0表示優(yōu)化結(jié)果已經(jīng)超過了函數(shù)的估計(jì)值或者已聲明的最大迭代次數(shù)，e＞0表示優(yōu)化過程中變量收斂于解X，e＜0表示計(jì)算不收斂。三、具體問題分析：我選擇的是產(chǎn)銷不平衡問題的求解，這里做的是產(chǎn)量大于銷量的問題求解。案例：某食品公司下屬的A1，A2，A3，3個(gè)廠生產(chǎn)方便食品，要運(yùn)輸?shù)紹1，B2，B3，3個(gè)銷售點(diǎn)；公司的初始運(yùn)輸方案如表1所示；3個(gè)廠到各銷售點(diǎn)每噸方便食品的運(yùn)價(jià)如表2所示。問該食品公司在滿足各銷售點(diǎn)銷售量的情況下如何安排運(yùn)輸使得總運(yùn)費(fèi)最小。

表1：初始運(yùn)輸方案(單位：t)

B1

B2

B3產(chǎn)量

A1

8

3

3

15

A2

5

6

5

18

A3

5

3

8

17銷量

18

12

16

總產(chǎn)量為：15+18+17=50總銷量為：18+12+16=46屬于產(chǎn)>銷問題。

表2：單位運(yùn)價(jià)（單位：元/t）

A1

50

90

20

A2

30

10

70

A3

60

20

80由表1和表2的數(shù)據(jù)可知,在初始運(yùn)送方案下，總的運(yùn)費(fèi)為：S=8*50+3*90+3*20+5*30+6*10+5*10+5*60+3*20+8*80=1990元針對產(chǎn)銷不平衡問題，核心方法是：將產(chǎn)銷不平衡轉(zhuǎn)換為產(chǎn)銷平衡的情形，然后由表上作業(yè)法進(jìn)行求解。（1）對于“產(chǎn)>銷”情形：可虛擬一個(gè)銷售地（庫存），讓多余的產(chǎn)量均運(yùn)抵此銷售地，則其銷售量=“產(chǎn)-銷”，同時(shí)令該虛擬的銷售地的單位運(yùn)價(jià)為0；（虛擬的銷地）（2）對于“銷>產(chǎn)”，可虛擬一個(gè)產(chǎn)地，讓其產(chǎn)量=“銷-產(chǎn)”，同時(shí)令該虛擬的產(chǎn)地的單位運(yùn)價(jià)為0.對于這個(gè)實(shí)際問題，虛設(shè)一銷地，令其銷量為產(chǎn)銷量之差。B4=∑ai-∑bj=(15+18+17)–(18+12+16)=4該列單位運(yùn)價(jià)為0，即可化為產(chǎn)銷平衡問題。如下表所示：

B1B2B3B4產(chǎn)量aiA150

A230

A360

銷量bj18

方案優(yōu)化：針對上述案例，首先構(gòu)建數(shù)學(xué)模型，建立線性方程組。假設(shè)產(chǎn)地A1，A2，A3向銷地B1，B2，B3，B4配送的運(yùn)輸量分別是X1，X2,X12，各變量如下表所示：根據(jù)假設(shè)的運(yùn)輸條件及案例給出的限定條件，設(shè)最小運(yùn)費(fèi)為Smin，構(gòu)建如下線性方程組：Smin＝50*X1＋90*X2＋20*X3＋0*X4＋30*X5＋10*X6＋70*X7＋0*X8＋60*X9＋20*X10＋80*X11＋0*X12約束條件如下：X1＋X2＋X3＋X4＝15；

X5＋X6＋X7＋X8＝18；X9＋X10＋X11＋X12＝17；

X1＋X5＋X9＝18；X2＋X6＋X10＝12；

X3＋X7＋X11＝16；X4＋X8＋X12＝4；

Xi≥0（i＝1，2，?，12）上述方程和約束條件對應(yīng)的Matlab代碼如下：F=[509020030107006020800];

m=[111100000000

000011110000

000000001111

100010001000

010001000100

001000100010

000100010001];n=[1518171812164];M=[000000000000];[v,e]=linprog(F,[],[],m,n,M)x=reshape(v,4,3);x=x'運(yùn)行后的結(jié)果為：Optimizationterminated.v=0.00000.000015.00000.000018.00000.00000.00000.00000.000012.00001.00004.0000e=1.1600e+03x=0.0000

0.0000

15.0000

0.000018.0000

0.0000

0.0000

0.00000.0000

12.0000

1.0000

4.0000由上圖matlab的運(yùn)行結(jié)果可知，優(yōu)化后的運(yùn)輸方案如下表所示：優(yōu)化后的總運(yùn)費(fèi)為：1160元。優(yōu)化后為該工廠節(jié)省運(yùn)費(fèi)：1990-1160=830（元）Linprog函數(shù)介紹：該函數(shù)用于求解線性規(guī)劃問題：其中，f,x,b,beq,lb,ub為向量,A,Aeq為矩陣。x=linprog(f,A,b)功能：求解最小化問題minf*x條件A*x≤b。x=linprog(f,A,b,Aeq,beq)功能：求解最小化問題minf*x條件A*x≤bAeq*x=beq，如果沒有等式就設(shè)置A=[]和b=[]x=linprog(f,A,b,Aeq,beq,lb,ub)功能：求解最小化問題minf*x條件A*x≤bAeq*x=beqlb≤x≤ub，如果沒有等式就設(shè)置A=[]和b=[]x=linprog(f,A,b,Aeq,beq,lb,ub,x0)功能：求解最小化問題minf*x條件A*x≤bAeq*x=beqlb≤x≤ub，如果沒有等式就設(shè)置A=[]和b=[]。設(shè)置初始點(diǎn)x0，這個(gè)選擇項(xiàng)只是對medium-scale算法有效。默認(rèn)的large-scale算法和簡單的算法忽略任何初始點(diǎn)。x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)功能：最小化帶有參數(shù)項(xiàng)的線性規(guī)劃問題。其中options可以使用optimset來設(shè)置。x=linprog(problem)功能：