資源描述：
《生產(chǎn)網(wǎng)絡(luò)流最小費用問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、第25卷第2期沈陽師范大學(xué)學(xué)報(自然科學(xué)版)Vol25,No.22007年4月JournalofShenyangNormalUniversity(NaturalScience)Apr.2007文章編號:1673-5862(2007)02-0140-04生產(chǎn)網(wǎng)絡(luò)流最小費用問題胥曉慶,唐恒永(沈陽師范大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院,遼寧沈陽110034)摘要:生產(chǎn)網(wǎng)絡(luò)流是一種廣義的網(wǎng)絡(luò)流模型,是基于復(fù)雜的生產(chǎn)過程,重新建立的一種新模型本文主要討論了生產(chǎn)網(wǎng)絡(luò)流的最小費用問題,在研究該問題的基本結(jié)構(gòu)及
2、其對偶性質(zhì)的基礎(chǔ)上給出了該問題的網(wǎng)絡(luò)單純形法關(guān)鍵詞:生產(chǎn)網(wǎng)絡(luò)流;最小費用流;網(wǎng)絡(luò)單純形法中圖分類號:O223文獻(xiàn)標(biāo)識碼:A0引言網(wǎng)絡(luò)流模型在實際生產(chǎn)中有及其廣泛的應(yīng)用,但普通的網(wǎng)絡(luò)流模型在描述更加復(fù)雜的生產(chǎn)過程時[1]有其局限性因此,FANGShucheng和QILiqun在中提出了一個稱為生產(chǎn)網(wǎng)絡(luò)流的廣義網(wǎng)絡(luò)流模型在這個模型中,多種原料通過合成或提煉過程可以生產(chǎn)出多種產(chǎn)品為了更恰當(dāng)?shù)孛枋錾a(chǎn)的各種過程,在生產(chǎn)網(wǎng)絡(luò)流模型中引入了六種不同結(jié)點:用來轉(zhuǎn)運的普通點O點,用來提供原
3、料的原點S點,用來收集成品的終點T點,用來存儲加工中的原料或半成品的存貨點C點,用來進(jìn)行分配或提煉操作的[1]分配點D點,用來進(jìn)行裝配或合成操作的裝配點I點由于生產(chǎn)網(wǎng)絡(luò)的復(fù)雜性,在中作者提出了兩種簡化的模型,即分配網(wǎng)絡(luò)流模型和裝配網(wǎng)絡(luò)流模型本文綜合了分配網(wǎng)絡(luò)流和裝配網(wǎng)絡(luò)流模型的特點,給出了生產(chǎn)網(wǎng)絡(luò)流模型我們主要研究生產(chǎn)網(wǎng)絡(luò)[1,2]流的最小費用問題該問題可以類似,在研究該問題的基本結(jié)構(gòu)及其對偶性質(zhì)的基礎(chǔ)上,給出了解決該問題的網(wǎng)絡(luò)單純形法1基本可行圖定義1令x是基本可行解,如果
4、一個點沒有正的流通過,則稱該點為空閑點,否則稱為活動點下面給出基本可行解的一些性質(zhì):定理1令x是基本可行解,GB是對應(yīng)于x的基本可行圖,則1)點s和點t都是活動點;2)GB是連通的;3)GB的任意一個圈都包含一個C點或一個D點;4)對于每個C點,或者所有與之相連的弧都是基弧,或者只有一條不是基弧在后者情況下,該C點是空閑點;5)對于每個D點,或者所有與之相連的弧都是基弧,或者只有一條不是基弧在后者情況下,該D點是空閑點;6)GB可以看作是的一棵支撐樹,根在s,q-t+p-r,有條
5、多余弧t代表松弛變量個數(shù),r代表I點數(shù)證明1)由4)及dj>0,jNT可知t是活動點正流自s流出,故s也是活動點收稿日期:20070109基金項目:國家自然科學(xué)基金資助項目(10471096)作者簡介:胥曉慶(1982-),女,遼寧沈陽人,沈陽師范大學(xué)碩士研究生;唐恒永(1943-),男,山東掖縣人,沈陽師范大學(xué)教授,碩士研究生導(dǎo)師第2期胥曉慶等:生產(chǎn)網(wǎng)絡(luò)流最小費用問題1412)因為正流來自s,故所有活動點在GB中與s連通,假設(shè)某些空閑點在GB中與s不連
6、通,從新排B10列對應(yīng)于x的基矩陣B的行和列,可以寫B(tài)=,其中B1對應(yīng)于與s連通的點和基弧,B2對0B2應(yīng)于與s不連通的點和基弧由(1)可知,B1不包含s點和t點對應(yīng)的行這樣,B2的一些行完全在M中,使得這樣的行和為零這與B是滿秩矛盾因此B2一定為空,則GB中的所有點與s連通3)同樣,令B是對應(yīng)于x的基矩陣,B與MN的共同部分一定是列滿秩的根據(jù)網(wǎng)絡(luò)單純形法的理[24]論任意不含C點、D點的子圖,不含圈4)對于一個C點,必須包含C點連接的所有弧,或者只有一條不包含其中在后者的
7、情況中,與C點相連的一條弧是非基弧,則該弧上的流值為零,該C點連接的所有的弧上流值都是零,即該點是空閑點5)同上6)由2)及基矩陣的維數(shù)即可證明2原問題和對偶問題的基本可行解利用對偶形式和定理1,可以得到該問題的最優(yōu)條件,令B是最優(yōu)基,對于弧(i,j)B,表示變量xij是基變量,對于每個C點和D點,我們從中省略一個等式因此,用E!(i)表示E(i)中剩余的入弧點,用L!(i)表示L(i)中剩余的出弧點此外,令LC=!{(i,j)A;jL(i)};EC=!{(i,j)A;jE!(
8、i)};iNjNCCLD=!{(i,j)A;jL!(i)};ED=!{(i,j)A;jE(i)};iNjNDDAO=A(LC!LD!EC!ED!{xs})最優(yōu)條件包括三部分:對于原問題部分,需要滿足xij=0(i,j)?B(1)ti=0iNT,i?B(2)xij=kijxi*ijL(i),iND(3)*這里E(i)={i}x*ji=hjixiijE(i),iNC(4)*這里L(fēng)(i)={i}#xji=#xijiNO(5)jE(i)(i,j)BjL(i)(
