裝配網絡流最小費用問題

由 巧 俐

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

?

裝配網絡流最小費用問題

由 巧 俐

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

討論裝配網絡流的最小費用問題。分配網絡流和裝配網絡流是生產網絡流的2種特殊簡化模型,其中裝配網絡由4種不同的點構成:用來轉運的普通點O-點,用來提供原料的源點S-點,用來收集成品的終點T-點,用來進行裝配或合成操作的裝配點C-點。在研究裝配網絡流基本結構及其對偶性質的基礎上,定義了一個唯一確定過程來計算原問題的基本可行解和對偶問題的基本解。最后,給出解決該問題的一個網絡單純形法,并對該算法的步驟3如何確定出基變量以及更新基本可行解加以說明。

裝配網絡流; 最小費用; 基本可行解; 網絡單純形法

Fang[1]提出了一個稱為生產網絡流的廣義網絡流模型,并引入了6種不同的點,得到一個生產網絡流模型,描述包括多種原材料或產品的生產過程。

本文主要討論簡化的裝配網絡流最小費用問題,目標是在研究其基本結構及其對偶性質的基礎上[1-5],給出該問題的網絡單純形法。其中裝配網絡流模型主要由用來轉運的普通點O-點,用來提供原料的源點S-點,用來收集成品的終點T-點,用來進行裝配或合成操作的裝配點C-點構成。

1 原問題基本可行解和對偶問題基本解

(1)

(2)

令x是基本可行解,GB是對應于x的基本可行圖,如圖2,可以得出GB的一些基本性質,如GB可以看作G的一棵支撐樹。點s和點t都是活動點[2],且GB是連通的;GB的任意一個圈至少包含一個C-點,對于每個C-點。

圖1 轉化的裝配網絡

圖2 一個基本可行圖

最優條件包括3部分:

對于原問題部分,需要滿足

(3)

(4)

其中L(i)={i*}

(5)

(6)

(7)

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

(8)

(9)

(10)

(11)

(12)

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

(13)

(14)

(15)

(16)

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

算法1 令GB是對應于基本可行解x的基本可行圖。

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

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

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

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

1) 路結束于GB的葉子;

2) 同一個點或弧在路中只出現一次;

3) 如果路經過O-點或T-點,則與該點相連的其他基弧開始一些可計算路。

可計算路的定義只用于分析而不是用于實際操作。

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

1) 對于一個非葉子的C-點,與之相連的基弧中只有一條開始一些可計算路;

2) 對于一個非葉子的非C-點,與之相連的基弧中除了一條外全部開始一些可計算路。

證明 令B是GB對應的基矩陣。假設一個非葉子的C-點,與之相連的基弧中有兩條弧開始一些可計算路,每一種情況取一個可計算路。由可計算路的定義知,從不在這兩條路的每個基弧開始,可以構造另外的可計算路,它們與這兩條路在一些非C-點處連接。重復這個過程,直到沒有這樣的基弧存在,刪掉重疊部分,可以看到在這些可計算路中,基矩陣B對應點的那些行是線性相關的,導致矛盾,(1)得證。同樣可以證明,對于每個非葉子的非C-點,與之相連的基弧中除一條外全部開始一些可計算路。這些事實保證算法1對應同一個原問題的基變量,不會因為選擇順序不同而產生不同的值。

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

算法2 令GB是對應于基本可行解x的基本可行圖。

步驟1 ys=0。

步驟2 用式(9)～式(12)計算剩余的對偶問題的基變量。可能需要解一些規模小的線性方程組。

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

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

2 網絡單純形法

利用算法1,算法2及最優條件式(3)～式(16)可以概括一個求解問題(1)的網絡單純形法。

算法3 令GB是對應于基本可行解x的基本可行圖。

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

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

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

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

如果在步驟2中選擇的進基非基弧與一些基弧構成一個不包含任何C-點的圈。可按一般網絡旋轉過程沿該圈找到一個基弧出基,并更新x。比如在圖1和圖2中,如果選擇非基弧(1,7)進基,則基弧(2,7)將出基。令ω=x2,7,從基中除去(2,7),并給弧(s,1)和(1,7)上的流值增加ω。

圖3 旋轉圖

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

在旋轉圖中,假設進基弧上的流值增加ω,將ω作為一個參數,利用算法1計算旋轉圖中各基弧上流值的改變量。如圖3所示,其中

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

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

3 結 語

本文考慮的是簡化的裝配網絡流最小費用問題,在研究裝配網絡基本結構及其對偶性質的基礎上,給出求解該問題的一個網絡單純形法。

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

[2]胥曉慶,唐恒永. 生產網絡流最小費用問題[J]. 沈陽師范大學學報(自然科學版), 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。

遼寧省教育廳高等學校優秀人才支持計劃(Lr2013062)。

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

1673-5862(2016)02-0170-04

O223

A

10.3969/ j.issn.1673-5862.2016.02.009