盧躍奇

(洛陽師范學(xué)院 數(shù)學(xué)科學(xué)學(xué)院,河南 洛陽 471934)

0 引言

針對產(chǎn)銷平衡的標(biāo)準(zhǔn)形式的運(yùn)輸問題,可以使用表上作業(yè)法求最優(yōu)解[1]。對于總產(chǎn)量大于總銷量或總銷量大于總產(chǎn)量形式的產(chǎn)銷不平衡的運(yùn)輸問題,其主約束條件都是“≤”或“=”形式,其中對于主約束條件有上界約束的情況,可以通過添加松弛變量轉(zhuǎn)換為產(chǎn)銷平衡的運(yùn)輸問題,即對于總產(chǎn)量大于總銷量的運(yùn)輸問題,可以添加一個虛擬的銷地,設(shè)置每個產(chǎn)地到虛擬銷地的單位運(yùn)價為零,設(shè)置虛擬銷地的銷量為總產(chǎn)量與原總銷量的差;對于總銷量大于總產(chǎn)量的運(yùn)輸問題,可以添加一個虛擬的產(chǎn)地,設(shè)置虛擬產(chǎn)地到每個銷地的單位運(yùn)價為零,設(shè)置虛擬產(chǎn)地的產(chǎn)量為總銷量與原總產(chǎn)量的差。對于其他形式的運(yùn)輸問題,諸多學(xué)者也進(jìn)行了一系列深入的研究[2-7]。

對于主約束條件既有上界約束又有下界約束的運(yùn)輸問題,如何等價地轉(zhuǎn)化為產(chǎn)銷平衡的標(biāo)準(zhǔn)形式的運(yùn)輸問題呢?針對這類形式的運(yùn)輸問題,也有比較通用的處理方法。下面以銷量約束有上下界要求的運(yùn)輸問題為例來說明。

1 銷量約束有上下界要求的運(yùn)輸問題模型的一般形式

設(shè)第i個產(chǎn)地到第j個銷地的單位運(yùn)價為cij,運(yùn)量為xij,第i個產(chǎn)地的產(chǎn)量為si,第j個銷地的最低需求為aj、最高需求為bj,其中i=1,2,…,m,j=1,2,…,n,則在附加條件

下的運(yùn)輸問題的數(shù)學(xué)模型的一般形式為

2 銷量約束有上下界要求的運(yùn)輸問題模型的標(biāo)準(zhǔn)化方法

注意到上述銷量約束有上下界要求的運(yùn)輸問題模型的附加條件中,總產(chǎn)量既高于最低總需求,又低于最高總需求,即每個銷地的需求中,最低需求部分必須滿足,而介于最低需求和最高需求之間的需求可以全部滿足,也可以部分滿足。因此,可以把每個銷地的需求量分為兩部分:剛性需求,即最低需求;彈性需求,即最高需求與最低需求之差。

令xij=x′ij+x″ij,其中x′ij表示從第i個產(chǎn)地運(yùn)往第j個銷地的運(yùn)量中,滿足第j個銷地需求量中的剛性需求部分,x″ij表示從第i個產(chǎn)地運(yùn)往第j個銷地的運(yùn)量中,滿足第j個銷地需求量中的彈性需求部分,從而把原運(yùn)輸問題等價地轉(zhuǎn)化為總銷量大于總產(chǎn)量形式的運(yùn)輸問題

其中,只需在彈性需求約束

左側(cè)添加非負(fù)松弛變量x″m+1,j化為等式

同時,在約束條件中添加

即可化為產(chǎn)銷平衡的運(yùn)輸問題。

3 應(yīng)用舉例

例1已知從各產(chǎn)地到各銷地的單位運(yùn)價(元/kg)、各產(chǎn)地的產(chǎn)量、各銷地的需求量,如表1。在各產(chǎn)地產(chǎn)量都運(yùn)走的條件下,求總運(yùn)費(fèi)最小的運(yùn)輸方案。其中,“—”表示B4的需求量不能從A3運(yùn)過來。

表1 產(chǎn)銷量與單位運(yùn)價

解注意到總產(chǎn)量有限,合計只有160 kg,故B4的最高需求量實(shí)質(zhì)上不可能不受限制?？紤]到只有當(dāng)給其他每個銷地運(yùn)送最少的量時,B4才會得到最大可能的量,故B4的最高需求量為

160-(30+70+0)=60 kg。

為了使得B4的需求量不能從A3運(yùn)過來,即x34=0,考慮到運(yùn)輸問題的目標(biāo)函數(shù)求最小值,只需令相應(yīng)的單位運(yùn)價c34=M(一個足夠大的正常數(shù))即可。從而,原問題可轉(zhuǎn)化為銷量約束有上下界要求的運(yùn)輸問題。

根據(jù)上一節(jié)的分析,可把銷量約束有上下界要求的運(yùn)輸問題轉(zhuǎn)化為總銷量大于總產(chǎn)量形式的運(yùn)輸問題,見表2,其中,銷地B11、B2、B41為剛性需求,對應(yīng)產(chǎn)量約束為等式約束,其他銷地為彈性需求,對應(yīng)銷量約束為≤形式的不等式約束如表2所示。

表2 包含剛性需求和彈性需求的單位運(yùn)價

為了使表2中總銷量大于總產(chǎn)量形式的運(yùn)輸問題轉(zhuǎn)化為產(chǎn)銷平衡的運(yùn)輸問題,須增加一個虛擬的產(chǎn)地A4,其產(chǎn)量為(30+20+70+30+10+50)-(50+60+50)=50 kg。同時,考慮到每個銷地的剛性需求部分B11、B2、B41不能由虛擬產(chǎn)地運(yùn)過來,即從虛擬產(chǎn)地運(yùn)到剛性需求的運(yùn)量必須為零。為了做到這一點(diǎn),考慮到目標(biāo)函數(shù)求最小值,只需令相應(yīng)的運(yùn)價為M即可;而每個銷地的彈性需求,若是從虛擬產(chǎn)地運(yùn)過來的,因?yàn)閷?shí)際上沒有發(fā)生對應(yīng)的運(yùn)費(fèi),故相應(yīng)的運(yùn)價應(yīng)取零,若是從實(shí)際產(chǎn)地運(yùn)來的,則運(yùn)價取原來相應(yīng)運(yùn)價。從而轉(zhuǎn)化為表3所示產(chǎn)銷平衡的運(yùn)輸問題。

表3 產(chǎn)銷平衡的單位運(yùn)價

利用表上作業(yè)法,求得上述運(yùn)輸問題的最優(yōu)解(表4),其中空格對應(yīng)的運(yùn)量為零。

表4 最優(yōu)解

可以看出,在最優(yōu)調(diào)運(yùn)方案中:B1滿足了最高需求50 kg,都從A3運(yùn)來;B2的需求70 kg也得到滿足,其中從A1運(yùn)過來50 kg,從A2運(yùn)過來20 kg;B3表面上滿足了最高需求30 kg,但都是從虛擬產(chǎn)地A4運(yùn)來的,實(shí)際上沒有得到任何滿足;B4滿足了最低需求10 kg,是從A2運(yùn)過來的,還滿足了部分彈性需求30 kg,也是從A2運(yùn)過來的,而還有部分彈性需求20 kg,是從虛擬產(chǎn)地A4運(yùn)過來的,這部分彈性需求實(shí)際上沒得到滿足,即B4實(shí)際上總共只得到了40 kg的需求。

4 總結(jié)

對于具有上下界主約束條件的運(yùn)輸問題,只需把需求量分為彈性需求和剛性需求、產(chǎn)量分為剛性產(chǎn)量和彈性產(chǎn)量,增加適當(dāng)?shù)奶摂M銷地或虛擬產(chǎn)地;對于不能從虛擬產(chǎn)地運(yùn)過來的剛性需求量,不能把剛性產(chǎn)量運(yùn)到虛擬銷地的產(chǎn)量,只需令相應(yīng)的單位運(yùn)價取M;對于能從虛擬產(chǎn)地運(yùn)過來的彈性需求量、能把彈性產(chǎn)量運(yùn)到虛擬銷地的產(chǎn)量,只需令相應(yīng)的單位運(yùn)價取零,就可以轉(zhuǎn)化為標(biāo)準(zhǔn)形式的產(chǎn)銷平衡運(yùn)輸問題,從而可以利用表上作業(yè)法等經(jīng)典方法快速求出最優(yōu)解。