用對(duì)偶單純形算法解裝卸工問題

方潤生,任云霞,王世英

用對(duì)偶單純形算法解裝卸工問題

方潤生1,任云霞1,王世英2

(1.中原工學(xué)院經(jīng)濟(jì)管理學(xué)院,河南鄭州450007;2.山西大學(xué)數(shù)學(xué)科學(xué)學(xué)院,山西太原030006)

文章提出了一些裝卸工問題的數(shù)學(xué)模型.在一些特殊情況下,用對(duì)偶單純形算法,獲得了它們的最優(yōu)解和最優(yōu)值.

運(yùn)籌學(xué);裝卸工問題;最優(yōu)解;最優(yōu)值

設(shè)運(yùn)輸公司有m輛貨車A1,A2,…,Am要向n個(gè)站點(diǎn)B1,B2,…,Bn裝卸貨物.運(yùn)輸公司要在每輛貨車上安排跟車的裝卸工,也可以在每個(gè)站點(diǎn)上雇傭當(dāng)?shù)氐难b卸工.貨車Ai上跟車的裝卸工必須裝卸向所有n個(gè)站點(diǎn)裝卸的貨物,最多可以跟車的裝卸工人數(shù)是ci,支付給每位跟車裝卸工的費(fèi)用是pi;在站點(diǎn)Bj處雇傭的裝卸工必須裝卸所有m輛貨車到這個(gè)站點(diǎn)上裝卸的貨物,最多可以雇傭的裝卸工人數(shù)是dj,支付給每位雇傭裝卸工的費(fèi)用是qj.如果用xi表示在貨車Ai上跟車裝卸工的人數(shù),用yj表示在站點(diǎn)Bj處雇傭當(dāng)?shù)匮b卸工的人數(shù),又已知貨車Ai在站點(diǎn)Bj處執(zhí)行裝卸任務(wù)時(shí)需要裝卸工的最少人數(shù)是eij,那么對(duì)i=1,2,…,m;j= 1,2,…,n必須滿足

其中tj是描述在站點(diǎn)Bj處雇傭的裝卸工在能力和素質(zhì)上與運(yùn)輸公司跟車裝卸工的差別.試求在每輛車Ai上跟車裝卸工的人數(shù)xi和在每個(gè)站點(diǎn)Bj處雇傭裝卸工的人數(shù)yj,使支付總的裝卸費(fèi)用為最小.

上述裝卸工問題的數(shù)學(xué)模型是寫成比較對(duì)稱的形式,這個(gè)裝卸工問題的整數(shù)規(guī)劃模型(記為P1)是問題P1作為整數(shù)規(guī)劃,可以討論參數(shù)ci,dj,si,tj,pi,qj,eij中取值為零或負(fù)數(shù)的情況,但從裝卸工問題的實(shí)際背景出發(fā),我們假設(shè)參數(shù)ci,dj,si,tj,eij(i=1,2,…,m;j=1,2,…,n)都是正整數(shù),參數(shù)pi,qj(i=1,2,…,m;j= 1,2,…,n)都是正數(shù).裝卸工問題是唐國春等2004年4月在全國運(yùn)籌學(xué)研究生講習(xí)班(貴陽)上提出的.這個(gè)問題的雛形是文[1]第105頁的“裝卸工人的調(diào)配問題”令pi=qj=si=tj=1,ci=dj=∞(i=1,2,…,m;j= 1,2,…,n),e1j=e2j=…=emj=ej(j=1,2,…,n)且不妨設(shè)e1≥e2≥…≥en>0,則裝卸工問題的整數(shù)規(guī)劃模型(記為P2)是

其中Z為非負(fù)整數(shù)的集合.文[2]給出了一類解裝卸工問題的求解方法.在文[3]中,在裝卸工問題P1中增加了兩個(gè)限制條件后,Tang等證明了這個(gè)裝卸工問題是NP困難的.在文[4]中,王世英等給出了P2的最優(yōu)解和最優(yōu)值.由于一個(gè)裝卸工費(fèi)用pi(qj)和他的能力si(tj)成正比的,所以我們可討論下面的裝卸工問題(記為P3).

其中k為正整數(shù).設(shè)P4是下面的裝卸工問題.

x＊1,x＊2,…,x＊m,y＊1,y＊2,…y＊n是裝卸工問題P3的一個(gè)最優(yōu)解當(dāng)且僅當(dāng)x＊1,x＊2,…,x＊m,y＊1,y＊2,…y＊n是裝卸工問題P4的一個(gè)最優(yōu)解.因此,我們討論P(yáng)4如下.

定理1 設(shè)裝卸工問題P4的一個(gè)最優(yōu)解是x＊1,x＊2,…,x＊m,y＊1,y＊2,…,y＊n.則s1x＊1=s2x＊2=…=smx＊m= cx＊,其中cx＊=min{s1x＊1,s2x＊2,…,smx＊m}.

證明 設(shè)裝卸工問題P4的一個(gè)最優(yōu)解是x＊1,x＊2,…,x＊m,y＊1,y＊2,…,y＊n.則我們有

和

設(shè)sixi=cx＊(i=1,2,…,m)和tjyj=tjy＊j(j=1,2,…,n).則xi=cx＊/si(i=1,2,…,m)和yj=y＊j(j=1,2,…, n)是P4一個(gè)可行解.所以

由(1)和(2),我們有

因此,

證畢.

我們給出裝卸工問題P5如下.

定理2 (a).模型P4的最優(yōu)解和模型P5的最優(yōu)解相等.

(b).(i).設(shè)x＊,y＊1,y＊2,…,y＊n是P5的一個(gè)最優(yōu)解.則xi=cx＊/si(i=1,2,…,m)和yj=y＊j(j=1,2,…, n)是P4的一個(gè)最優(yōu)解.

(ii).設(shè)x＊1,x＊2,…,x＊m,y＊1,y＊2,…,y＊n是P4的一個(gè)最優(yōu)解.則x=x＊,yj=y＊j(j=1,2,…,n)是P5的一個(gè)最優(yōu)解,其中cx＊=min{s1x＊1,s2x＊2,…,smx＊m}.

證明(a). 設(shè)x＊,y＊1,y＊2,…,y＊

n是P5的一個(gè)最優(yōu)解.則+tjy＊j≥ej(j=1,2,…,n).設(shè)sixi=cx＊(i=1,2,…,m)和tjyj=tjy＊j(j=1,2,…,n).則xi=cx＊/si(i= 1,2,…,m)和yj=y＊j(j=1,2,…,n)滿足sixi+tjyj≥ej(i=1,2,…,m,j=1,2,…,n).所以xi=cx＊/si(i =1,2,…,m)和yj=y＊j(j=1,2,…,n),是P4一個(gè)可行解.因此

另一方面,設(shè)x＊1,x＊2,…,x＊m,y＊1,y＊2,…,y＊n是P4的一個(gè)最優(yōu)解和設(shè)cx＊=min{s1x＊1,s2x＊2,…,smx＊m}.則由定理1,我們有設(shè)cx=cx＊和tjyj=tjy＊j(j=1,2,…,n).則x= x＊和yj=y＊j(j=1,2,…,n)滿足cx+tjyj≥ej(j=1,2,…,n).因此,x=x＊,yj=y＊j(j=1,2,…,n)P5一個(gè)可行解.所以,我們有

由(3)和(4),我們有P4的最優(yōu)值和P5的最優(yōu)值相等.

(b).在(3)和(4)中的等式成立.由(3),(i)被證明.由(4),(ii)被證明.證畢.

證明 (a).由P5,我們有

它的單純形表如下:

表格1

對(duì)偶單純形算法.

第1步:從第1行到第m行都乘以(-1),得cx+tjyj-pj=ej(j=1,2,…,m).

第2步:0行(z行)分別加上新的第1行到第m行,得表格2.

表格2

第3步:在表格2中,第1行加上第m+1行,第2行加上第m+1行,一直到第m行加上第m+1行,得tjyj-tm+1ym+1-pj+pm+1=ej-em+1(j=1,2,…,m).

第4步:在表格2中,第m+1行乘以(-1),得cx+tm+1ym+1-pm+1=em+1.

第5步:從第m+2行到第n行分別加上新的第m+1行,得tm+1ym+1-tjyj+pj-pm+1=em+1-ej(j=m+ 2,…,n).得到表格3.

表格3

第6步:在表3中,第i行除以ti(i=1,2,…,m)和第m+1行除以c得到表格4.

表格4

(b).它的單純形表如下:

表格5

第1步:i(i=1,2,…,n)行乘以(-1).

第2步:0行分別加上第1行到第n行,得到表格6.

表格6

第3步:在表格6中,i行除以ti(i=1,2,…,n),得到表格7.

表格7

(iv)輸出x,y1,y2,…,yn;z.

b)當(dāng)m≥n時(shí).

(i)排序e1≥e2≥…≥en.

(iv)輸出x,y1,y2,…,yn;z.

由于對(duì)n個(gè)數(shù)進(jìn)行排序有時(shí)間復(fù)雜度為O(nlog2n)的算法(比如堆算法),因此,下面的定理是明顯的.定理5 算法4的時(shí)間復(fù)雜度為O(nlog2n).

[1] 秦明森,王方智.實(shí)用物流技術(shù)[M].北京:中國物資出版社,2001.

[2] 林上為,王世英.一類解裝卸工問題的求解方法[J].山西大學(xué)學(xué)報(bào)(自然科學(xué)版),2004,27(S0):3-5.

[3] TANG G,CHEN F,CHENG TCE,Ng CT,Chen Z-L.The Loader Problem:Formulation,Complexity and Algorithms[J].Journal of the Operational Research Society,2009,61:840-848.

[4] 王世英,唐國春,楊愛民.單純形法解裝卸工問題[J].運(yùn)籌學(xué)學(xué)報(bào),2005,9(3):65-70.

Solving the Loader Problem by Dual Si mplex

FANG Run-sheng1,REN Yun-xia1,WANG Shi-ying2
(1.School of Econom ics and M anagem ent,Zhongyuan University of Technology,Zhengzhou450007,China; 2.School of M athem atical Sciences,Shanxi University,Taiyuan030006,China)

Some mathematicalmodels of the loader problem are introduced and using the dual simplex algorithm we give its optimal solution and optimum in a special case.

operational research;loader problem;optimal solution;optimum

O22

A

0253-2395(2010)04-0519-06

2010-03-02;

2010-04-26

國家自然科學(xué)基金(70671111;61070229)

方潤生(1963-),男,湖北武漢人,博士,教授,主要研究領(lǐng)域?yàn)槠髽I(yè)戰(zhàn)略與運(yùn)籌.