裝配網(wǎng)絡(luò)流最小費(fèi)用問題

由 巧 俐

(遼東學(xué)院 師范學(xué)院, 遼寧 丹東 118000)

?

裝配網(wǎng)絡(luò)流最小費(fèi)用問題

由 巧 俐

(遼東學(xué)院 師范學(xué)院, 遼寧 丹東 118000)

討論裝配網(wǎng)絡(luò)流的最小費(fèi)用問題。分配網(wǎng)絡(luò)流和裝配網(wǎng)絡(luò)流是生產(chǎn)網(wǎng)絡(luò)流的2種特殊簡(jiǎn)化模型,其中裝配網(wǎng)絡(luò)由4種不同的點(diǎn)構(gòu)成:用來(lái)轉(zhuǎn)運(yùn)的普通點(diǎn)O-點(diǎn),用來(lái)提供原料的源點(diǎn)S-點(diǎn),用來(lái)收集成品的終點(diǎn)T-點(diǎn),用來(lái)進(jìn)行裝配或合成操作的裝配點(diǎn)C-點(diǎn)。在研究裝配網(wǎng)絡(luò)流基本結(jié)構(gòu)及其對(duì)偶性質(zhì)的基礎(chǔ)上,定義了一個(gè)唯一確定過程來(lái)計(jì)算原問題的基本可行解和對(duì)偶問題的基本解。最后,給出解決該問題的一個(gè)網(wǎng)絡(luò)單純形法,并對(duì)該算法的步驟3如何確定出基變量以及更新基本可行解加以說(shuō)明。

裝配網(wǎng)絡(luò)流; 最小費(fèi)用; 基本可行解; 網(wǎng)絡(luò)單純形法

Fang[1]提出了一個(gè)稱為生產(chǎn)網(wǎng)絡(luò)流的廣義網(wǎng)絡(luò)流模型,并引入了6種不同的點(diǎn),得到一個(gè)生產(chǎn)網(wǎng)絡(luò)流模型,描述包括多種原材料或產(chǎn)品的生產(chǎn)過程。

本文主要討論簡(jiǎn)化的裝配網(wǎng)絡(luò)流最小費(fèi)用問題,目標(biāo)是在研究其基本結(jié)構(gòu)及其對(duì)偶性質(zhì)的基礎(chǔ)上[1-5],給出該問題的網(wǎng)絡(luò)單純形法。其中裝配網(wǎng)絡(luò)流模型主要由用來(lái)轉(zhuǎn)運(yùn)的普通點(diǎn)O-點(diǎn),用來(lái)提供原料的源點(diǎn)S-點(diǎn),用來(lái)收集成品的終點(diǎn)T-點(diǎn),用來(lái)進(jìn)行裝配或合成操作的裝配點(diǎn)C-點(diǎn)構(gòu)成。

1 原問題基本可行解和對(duì)偶問題基本解

(1)

(2)

令x是基本可行解,GB是對(duì)應(yīng)于x的基本可行圖,如圖2,可以得出GB的一些基本性質(zhì),如GB可以看作G的一棵支撐樹。點(diǎn)s和點(diǎn)t都是活動(dòng)點(diǎn)[2],且GB是連通的;GB的任意一個(gè)圈至少包含一個(gè)C-點(diǎn),對(duì)于每個(gè)C-點(diǎn)。

圖1 轉(zhuǎn)化的裝配網(wǎng)絡(luò)

圖2 一個(gè)基本可行圖

最優(yōu)條件包括3部分:

對(duì)于原問題部分,需要滿足

(3)

(4)

其中L(i)={i*}

(5)

(6)

(7)

對(duì)于對(duì)偶問題的基變量部分,需要滿足

(8)

(9)

(10)

(11)

(12)

對(duì)于對(duì)偶問題的非基變量部分,需要滿足

(13)

(14)

(15)

(16)

下面是計(jì)算原問題基本可行解x的具體步驟。

算法1 令GB是對(duì)應(yīng)于基本可行解x的基本可行圖。

步驟1 判斷GB的葉子[2]。用式(6)計(jì)算與T-點(diǎn)葉子相連的基弧的流值,并置與C-點(diǎn)和O-點(diǎn)葉子相連的基弧的流值為零。

步驟2 判斷GB中未計(jì)算部分的葉子。用式(4),式(5)和式(6)分別計(jì)算C-點(diǎn),O-點(diǎn)和T-點(diǎn)的葉子。重復(fù)該步驟,直到基本可行變量xij全部計(jì)算過。

步驟3 用式(7)計(jì)算出xs。

定義 在基本可行圖GB中,滿足下列條件的路叫做可計(jì)算路:

1) 路結(jié)束于GB的葉子;

2) 同一個(gè)點(diǎn)或弧在路中只出現(xiàn)一次;

3) 如果路經(jīng)過O-點(diǎn)或T-點(diǎn),則與該點(diǎn)相連的其他基弧開始一些可計(jì)算路。

可計(jì)算路的定義只用于分析而不是用于實(shí)際操作。

定理1 令GB是對(duì)應(yīng)于基本可行解x的基本可行圖。則算法1是唯一確定的可計(jì)算過程。特別地有:

1) 對(duì)于一個(gè)非葉子的C-點(diǎn),與之相連的基弧中只有一條開始一些可計(jì)算路;

2) 對(duì)于一個(gè)非葉子的非C-點(diǎn),與之相連的基弧中除了一條外全部開始一些可計(jì)算路。

證明 令B是GB對(duì)應(yīng)的基矩陣。假設(shè)一個(gè)非葉子的C-點(diǎn),與之相連的基弧中有兩條弧開始一些可計(jì)算路,每一種情況取一個(gè)可計(jì)算路。由可計(jì)算路的定義知,從不在這兩條路的每個(gè)基弧開始,可以構(gòu)造另外的可計(jì)算路,它們與這兩條路在一些非C-點(diǎn)處連接。重復(fù)這個(gè)過程,直到?jīng)]有這樣的基弧存在,刪掉重疊部分,可以看到在這些可計(jì)算路中,基矩陣B對(duì)應(yīng)點(diǎn)的那些行是線性相關(guān)的,導(dǎo)致矛盾,(1)得證。同樣可以證明,對(duì)于每個(gè)非葉子的非C-點(diǎn),與之相連的基弧中除一條外全部開始一些可計(jì)算路。這些事實(shí)保證算法1對(duì)應(yīng)同一個(gè)原問題的基變量,不會(huì)因?yàn)檫x擇順序不同而產(chǎn)生不同的值。

在計(jì)算出原問題的基本可行解后,可以用最優(yōu)條件(8)～(12)計(jì)算對(duì)偶問題的基本解。

算法2 令GB是對(duì)應(yīng)于基本可行解x的基本可行圖。

步驟1 ys=0。

步驟2 用式(9)～式(12)計(jì)算剩余的對(duì)偶問題的基變量?？赡苄枰庖恍┮?guī)模小的線性方程組。

定理2 在算法2中遇到的線性方程組的系數(shù)矩陣總是非奇異的。

證明 由線性規(guī)劃的定理可知,在算法2求解過程中,所要解的線性方程組,其系數(shù)矩陣是BT,無(wú)論怎樣把該過程分解成求解較小的線性方程組,只要B是非奇異的,這個(gè)過程中遇到的系數(shù)矩陣總會(huì)是非奇異的。

2 網(wǎng)絡(luò)單純形法

利用算法1,算法2及最優(yōu)條件式(3)～式(16)可以概括一個(gè)求解問題(1)的網(wǎng)絡(luò)單純形法。

算法3 令GB是對(duì)應(yīng)于基本可行解x的基本可行圖。

步驟1 用算法2計(jì)算出對(duì)偶問題的基本解y和μ。

步驟2 檢查對(duì)偶問題可行性條件式(13)～式(16),如果都滿足,則停止(達(dá)到最優(yōu))。否則,選擇一個(gè)破壞對(duì)偶問題可行性條件的非基弧(i,j)作為一個(gè)新的變量加入基中。

步驟3 換基。將新的基變量加入到當(dāng)前的基中,找一個(gè)基變量出基,并更新原問題基本可行解x,返回步驟1,進(jìn)行下一次迭代。

算法3的步驟1和步驟2很容易實(shí)現(xiàn),步驟3需要有效的方法去確定出基變量以及更新x。如果知道如何確定旋轉(zhuǎn)圖,換基過程可以進(jìn)一步改進(jìn)。

如果在步驟2中選擇的進(jìn)基非基弧與一些基弧構(gòu)成一個(gè)不包含任何C-點(diǎn)的圈?？砂匆话憔W(wǎng)絡(luò)旋轉(zhuǎn)過程沿該圈找到一個(gè)基弧出基,并更新x。比如在圖1和圖2中,如果選擇非基弧(1,7)進(jìn)基,則基弧(2,7)將出基。令ω=x2,7,從基中除去(2,7),并給弧(s,1)和(1,7)上的流值增加ω。

圖3 旋轉(zhuǎn)圖

另一種情況是在步驟2中選擇的進(jìn)基非基弧與其他基弧構(gòu)成一個(gè)或幾個(gè)圈,并且每個(gè)圈都包含至少一個(gè)C-點(diǎn)。死圈在旋轉(zhuǎn)流中無(wú)用,因而在確定出基基弧時(shí)可以忽略。在非死圈形成的生成圖中,如果一些弧是葉子,可以用算法1描述的方法計(jì)算這些弧及相關(guān)弧上的流值。從生成圖中去掉所有錯(cuò)圈和相關(guān)點(diǎn),就可以得到旋轉(zhuǎn)圖。如圖2中,如果選擇弧(14,15)進(jìn)基,則可得到如圖3的旋轉(zhuǎn)圖。

在旋轉(zhuǎn)圖中,假設(shè)進(jìn)基弧上的流值增加ω,將ω作為一個(gè)參數(shù),利用算法1計(jì)算旋轉(zhuǎn)圖中各基弧上流值的改變量。如圖3所示,其中

根據(jù)原流值,可以判斷出哪個(gè)基弧出基。在圖3中,隨著ω增加x8,13,(13,15),(9,13),(5,9),(10,13)同時(shí)到達(dá)零,因此可任選一個(gè)出基。

在非退化情況下,生成圖刪掉死圈和錯(cuò)圈后至少剩余一個(gè)圈包含進(jìn)基弧,如果出現(xiàn)不存在出基弧的情況,為使所有弧上的流值之和最小,必須令ω=0,這意味著不應(yīng)該在步驟2中首先選擇該進(jìn)基弧進(jìn)基。對(duì)于退化情況,可以在GB空閑部分找一個(gè)合適的基弧作為出基弧,但旋轉(zhuǎn)圖中的流值不發(fā)生變化。

3 結(jié) 語(yǔ)

本文考慮的是簡(jiǎn)化的裝配網(wǎng)絡(luò)流最小費(fèi)用問題,在研究裝配網(wǎng)絡(luò)基本結(jié)構(gòu)及其對(duì)偶性質(zhì)的基礎(chǔ)上,給出求解該問題的一個(gè)網(wǎng)絡(luò)單純形法。

[1]FANGShucheng,QILiqun.Manufacturingnetworkflows:ageneralizednetworkflowmodelformanufacturingprocessmodelling[J].OptimMethodSoft, 2003,18(2):142-165.

[2]胥曉慶,唐恒永. 生產(chǎn)網(wǎng)絡(luò)流最小費(fèi)用問題[J]. 沈陽(yáng)師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2007,25(2):140-143.

[3]LU Haiyan, YAO Enyu, ZHANG Binwu. A note on a generalized network flow model for manufacturing process[J]. Acta Math Appl Sin Engl Ser, 2009,25(1):51-60.

[4]VENKATESHAN P, MATHUR K ,BALLOU R H . An efficient generalized network-simplex-based algorithm for manufacturing network flows[J]. J Comb Optim, 2008,15(4):315-341.

[5]MO Jiangtao, QI Liqun,WEI Zengxin. A netwok simplex algorithm for simple manufacturing network model[J]. Ind Manag Optim, 2005,1(2):251-273.

Minimumcost problem of assembly network flows

YOUQiaoli

(Teachers College, Eastern Liaoning University, Dandong 118000, China)

This paper considers the minimum cost problem of assembly network flows. The distribution and assembly network flow problems are two simplified versions. In an assembly network there are four kinds of different nodes: ordinary nodes(O-nodes )for transition, source nodes(S-nodes) for providing raw materials, termination nodes(T-nodes) for collecting final products, combination nodes(C-nodes) for assembly or synthesis operations. The underlying structure and dual properties of it are specially studied to develop well-defined procedures to compute the primal basic feasible solution and dual basic solution. Finally, we outline a network simplex method for solving this problem. More specially, we show that how to identify a basic variable leaving the basis and to update a basic feasible solution of step 3.

assembly network flows; minimum cost; basic feasible solution; network simplex method

2015-03-09。

遼寧省教育廳高等學(xué)校優(yōu)秀人才支持計(jì)劃(Lr2013062)。

由巧俐(1980-),女(滿族),遼寧東港人,遼東學(xué)院講師,碩士。

1673-5862(2016)02-0170-04

O223

A

10.3969/ j.issn.1673-5862.2016.02.009