用对偶单纯形算法解装卸工问题

方润生,任云霞,王世英

用对偶单纯形算法解装卸工问题

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

(1.中原工学院经济管理学院,河南郑州450007;2.山西大学数学科学学院,山西太原030006)

文章提出了一些装卸工问题的数学模型.在一些特殊情况下,用对偶单纯形算法,获得了它们的最优解和最优值.

运筹学;装卸工问题;最优解;最优值

设运输公司有m辆货车A1,A2,…,Am要向n个站点B1,B2,…,Bn装卸货物.运输公司要在每辆货车上安排跟车的装卸工,也可以在每个站点上雇佣当地的装卸工.货车Ai上跟车的装卸工必须装卸向所有n个站点装卸的货物,最多可以跟车的装卸工人数是ci,支付给每位跟车装卸工的费用是pi;在站点Bj处雇佣的装卸工必须装卸所有m辆货车到这个站点上装卸的货物,最多可以雇佣的装卸工人数是dj,支付给每位雇佣装卸工的费用是qj.如果用xi表示在货车Ai上跟车装卸工的人数,用yj表示在站点Bj处雇佣当地装卸工的人数,又已知货车Ai在站点Bj处执行装卸任务时需要装卸工的最少人数是eij,那么对i=1,2,…,m;j= 1,2,…,n必须满足

其中tj是描述在站点Bj处雇佣的装卸工在能力和素质上与运输公司跟车装卸工的差别.试求在每辆车Ai上跟车装卸工的人数xi和在每个站点Bj处雇佣装卸工的人数yj,使支付总的装卸费用为最小.

上述装卸工问题的数学模型是写成比较对称的形式,这个装卸工问题的整数规划模型(记为P1)是问题P1作为整数规划,可以讨论参数ci,dj,si,tj,pi,qj,eij中取值为零或负数的情况,但从装卸工问题的实际背景出发,我们假设参数ci,dj,si,tj,eij(i=1,2,…,m;j=1,2,…,n)都是正整数,参数pi,qj(i=1,2,…,m;j= 1,2,…,n)都是正数.装卸工问题是唐国春等2004年4月在全国运筹学研究生讲习班(贵阳)上提出的.这个问题的雏形是文[1]第105页的“装卸工人的调配问题”令pi=qj=si=tj=1,ci=dj=∞(i=1,2,…,m;j= 1,2,…,n),e1j=e2j=…=emj=ej(j=1,2,…,n)且不妨设e1≥e2≥…≥en>0,则装卸工问题的整数规划模型(记为P2)是

其中Z为非负整数的集合.文[2]给出了一类解装卸工问题的求解方法.在文[3]中,在装卸工问题P1中增加了两个限制条件后,Tang等证明了这个装卸工问题是NP困难的.在文[4]中,王世英等给出了P2的最优解和最优值.由于一个装卸工费用pi(qj)和他的能力si(tj)成正比的,所以我们可讨论下面的装卸工问题(记为P3).

其中k为正整数.设P4是下面的装卸工问题.

x＊1,x＊2,…,x＊m,y＊1,y＊2,…y＊n是装卸工问题P3的一个最优解当且仅当x＊1,x＊2,…,x＊m,y＊1,y＊2,…y＊n是装卸工问题P4的一个最优解.因此,我们讨论P4如下.

定理1 设装卸工问题P4的一个最优解是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}.

证明 设装卸工问题P4的一个最优解是x＊1,x＊2,…,x＊m,y＊1,y＊2,…,y＊n.则我们有

和

设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一个可行解.所以

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

因此,

证毕.

我们给出装卸工问题P5如下.

定理2 (a).模型P4的最优解和模型P5的最优解相等.

(b).(i).设x＊,y＊1,y＊2,…,y＊n是P5的一个最优解.则xi=cx＊/si(i=1,2,…,m)和yj=y＊j(j=1,2,…, n)是P4的一个最优解.

(ii).设x＊1,x＊2,…,x＊m,y＊1,y＊2,…,y＊n是P4的一个最优解.则x=x＊,yj=y＊j(j=1,2,…,n)是P5的一个最优解,其中cx＊=min{s1x＊1,s2x＊2,…,smx＊m}.

证明(a). 设x＊,y＊1,y＊2,…,y＊

n是P5的一个最优解.则+tjy＊j≥ej(j=1,2,…,n).设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一个可行解.因此

另一方面,设x＊1,x＊2,…,x＊m,y＊1,y＊2,…,y＊n是P4的一个最优解和设cx＊=min{s1x＊1,s2x＊2,…,smx＊m}.则由定理1,我们有设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一个可行解.所以,我们有

由(3)和(4),我们有P4的最优值和P5的最优值相等.

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

证明 (a).由P5,我们有

它的单纯形表如下:

表格1

对偶单纯形算法.

第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)当m≥n时.

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

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

由于对n个数进行排序有时间复杂度为O(nlog2n)的算法(比如堆算法),因此,下面的定理是明显的.定理5 算法4的时间复杂度为O(nlog2n).

[1] 秦明森,王方智.实用物流技术[M].北京:中国物资出版社,2001.

[2] 林上为,王世英.一类解装卸工问题的求解方法[J].山西大学学报(自然科学版),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].运筹学学报,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

国家自然科学基金(70671111;61070229)

方润生(1963-),男,湖北武汉人,博士,教授,主要研究领域为企业战略与运筹.