陳本士

哈爾濱德強(qiáng)商務(wù)學(xué)院，黑龍江哈爾濱 150025

基于優(yōu)先補(bǔ)償權(quán)在生產(chǎn)計(jì)劃中的一種規(guī)劃模型算法

陳本士

哈爾濱德強(qiáng)商務(wù)學(xué)院，黑龍江哈爾濱 150025

本文針對(duì)有限生產(chǎn)能力和一定的市場(chǎng)需求量情況下的生產(chǎn)計(jì)劃，建立一種規(guī)劃模型，提出了優(yōu)先補(bǔ)償權(quán)和優(yōu)先生產(chǎn)權(quán)準(zhǔn)則，并在這兩個(gè)準(zhǔn)則下取得最優(yōu)解。這一算法的提出，對(duì)此類實(shí)際問(wèn)題的解決，具有一定的可操作性。

需求量；優(yōu)先補(bǔ)償權(quán)；規(guī)劃模型

生產(chǎn)企業(yè)的生產(chǎn)計(jì)劃必須依據(jù)工廠的生產(chǎn)能力、市場(chǎng)需求量來(lái)制定。在不同時(shí)間內(nèi)生產(chǎn)企業(yè)的生產(chǎn)能力、市場(chǎng)需求不同，同時(shí)不能產(chǎn)生大量庫(kù)存。所以制定計(jì)劃時(shí)必須綜合考慮諸多因素，以最大收益原則來(lái)制定。本文從一個(gè)實(shí)際問(wèn)題出發(fā)，提出一種解決此類問(wèn)題的解決方法。

1 一個(gè)生產(chǎn)計(jì)劃的實(shí)際問(wèn)題

在文獻(xiàn)[1]中給出了如下一個(gè)數(shù)學(xué)建模問(wèn)題：某廠擁有4臺(tái)磨床（1月、5月各停工一臺(tái)）、3臺(tái)臥式鉆床（2月停工維修二臺(tái)，6月維修一臺(tái)）、2臺(tái)立式鉆床（4月、5月各停工維修一臺(tái)）、一臺(tái)鏜床（3月停工維修）和一臺(tái)刨床（6月停工維修一臺(tái)），用以生產(chǎn)7種產(chǎn)品記作p1至p7。工廠收益規(guī)定為產(chǎn)品售價(jià)減去原材料之剩余。每種產(chǎn)品的單價(jià)的收益及所需各機(jī)床的加工工時(shí)（以小時(shí)計(jì)）見(jiàn)文獻(xiàn)，這里不再贅述。

每種產(chǎn)品存貨最多可到100件，存費(fèi)每件每月為0.5?，F(xiàn)在無(wú)存貨，要求到6月底每種產(chǎn)品存貨50件。工廠每周工作6天，可假設(shè)每月僅有24個(gè)工作日，每班8小時(shí)，不需要考慮排列等待加工的問(wèn)題，為使收益最大，工廠應(yīng)如何安排各種產(chǎn)品的產(chǎn)量？

2 問(wèn)題的一般化與求解模型

我們將問(wèn)題一般化如下：某工廠生產(chǎn)n種產(chǎn)品Wi（i=1，2，…n），每種產(chǎn)品的價(jià)格為Pi（i=1，2，…n），而生產(chǎn)每種Wi需要m道加工過(guò)程Gj（j=1,2,…m），加工一件Wi所需Gj工時(shí)為tij（i=1，2，…n；j=1,2,…m）現(xiàn)在已知有r個(gè)時(shí)間段Tk（k=1,2,…r）內(nèi)，各種產(chǎn)品Wi（i=1，2，…n）在各時(shí)間段Tk（k=1,2,…r）的市場(chǎng)容量Zik（i=1，2，…n；k=1,2,…r），并且時(shí)間段Tk（k=1,2,…r）內(nèi)每種產(chǎn)品Wi（i=1，2，…n）的最大存貨量為Cki（k=1,2,…r；i=1，2，…n）。且Tk內(nèi)每件 Wi存貨費(fèi)為 Dki（k=1,2,…r；i=1，2，…n）?，F(xiàn)在無(wú)存貨 ，加工過(guò)程不考慮排隊(duì)問(wèn)題，為使效益最大，工廠如何安排各段時(shí)間的生產(chǎn)計(jì)劃？

我們假設(shè)Tk內(nèi)Wi的計(jì)劃生產(chǎn)量為Xki（k=1,2,…r；i=1，2，…n），Tk內(nèi) Wi的計(jì)劃生產(chǎn)存貨量為 Yki（k=1,2,…r；i=1，2，…n），總收益為Q。則可建立如下目標(biāo)函數(shù)：

其中 ，Xki＜Zki;Yki＜Gki

問(wèn)題的求解就是定出各時(shí)間段的計(jì)劃生產(chǎn)量和存貨量，使得目標(biāo)函數(shù)值最大，也就是最優(yōu)解。制定計(jì)劃必須綜合考慮各個(gè)時(shí)間段的生產(chǎn)能力、市場(chǎng)容量和最大庫(kù)存來(lái)確定。我們給出一種基于優(yōu)先補(bǔ)償和優(yōu)先生產(chǎn)原則的規(guī)劃方法：

優(yōu)先補(bǔ)償原則：

在需要補(bǔ)償?shù)那闆r下，優(yōu)先補(bǔ)償單個(gè)產(chǎn)品效益大、耗工時(shí)最小的產(chǎn)品，產(chǎn)品效益優(yōu)先權(quán)值可有如下公式計(jì)算：

補(bǔ)償產(chǎn)品效益優(yōu)先權(quán)值=單個(gè)產(chǎn)品收益÷單個(gè)產(chǎn)品所需該工時(shí)﹣存貨費(fèi)÷單個(gè)產(chǎn)品所需該工時(shí)

優(yōu)先補(bǔ)償原則：

在某種生產(chǎn)能力不足情況下，根據(jù)生產(chǎn)任務(wù)優(yōu)先生產(chǎn)單位工時(shí)效益最大的產(chǎn)品，優(yōu)先生產(chǎn)權(quán)計(jì)算如下：

權(quán)值=單個(gè)產(chǎn)品收益÷單個(gè)產(chǎn)品所需該過(guò)程工時(shí)

具體算法步驟如下：

第一步：計(jì)算出各時(shí)間段各個(gè)加工過(guò)程的最大生產(chǎn)能力Nkj（k=1,2,…r；j=1,2,…m）。

第二步：計(jì)算各時(shí)間段內(nèi)滿足市場(chǎng)容量所需的各個(gè)加工過(guò)程的生產(chǎn)能力 Rkj（k=1,2,…r；j=1,2,…m）。

第三步：計(jì)算各時(shí)間段各個(gè)加工過(guò)程的最大生產(chǎn)能力與所需生產(chǎn)能力之差Skj=Nkj–Rkj。得到一個(gè)反映生產(chǎn)能力滿足市場(chǎng)容量情況的二維數(shù)據(jù)，正者為剩余生產(chǎn)能力，負(fù)者為不足生產(chǎn)能力，可討論所影響的產(chǎn)品能否由上個(gè)時(shí)間段補(bǔ)償。

第四步：考慮到T1和Tm時(shí)間段的特殊性（T1的所缺產(chǎn)品不能由上個(gè)時(shí)間段補(bǔ)償；Tm庫(kù)存需要一定的生產(chǎn)能力），我們先對(duì)這兩個(gè)時(shí)間段進(jìn)行如下處理：如果T1出現(xiàn)某加工過(guò)程生產(chǎn)能力不足，必然導(dǎo)致有些產(chǎn)品不能生產(chǎn)，則依據(jù)優(yōu)先生產(chǎn)權(quán)順序進(jìn)行貪婪生產(chǎn)，得到T1時(shí)段的初次生產(chǎn)計(jì)劃x1i，將此計(jì)劃作為虛擬的市場(chǎng)需求，算出新的生產(chǎn)能力差值，處理后T1時(shí)段的負(fù)值應(yīng)變?yōu)榱慊驍?shù)值較小（不足以生產(chǎn)一件產(chǎn)品）的正值；Tm時(shí)間段的庫(kù)存可加入該時(shí)段市場(chǎng)容量作為一個(gè)虛擬的市場(chǎng)容量，由此市場(chǎng)容量算出所需生產(chǎn)能力并算出新的生產(chǎn)能力差值。經(jīng)過(guò)處理得到一個(gè)新的生產(chǎn)能力情況的二維數(shù)據(jù)R‘kj。R‘kj中未出現(xiàn)負(fù)值的表明該時(shí)間段生產(chǎn)能力過(guò)剩，將市場(chǎng)容量作為生產(chǎn)計(jì)劃量。

第五步：從此二維數(shù)據(jù)出發(fā)，依據(jù)優(yōu)先補(bǔ)償準(zhǔn)則從上到下把R‘kj中負(fù)值所影響的未能生產(chǎn)的產(chǎn)品貪婪的由最近的上一時(shí)段該加工過(guò)程剩余生產(chǎn)能力生產(chǎn)產(chǎn)品補(bǔ)償，我們給出如下的處理步驟：

步驟1：搜索所有負(fù)值及負(fù)值影響產(chǎn)品，算出各產(chǎn)品的優(yōu)先生產(chǎn)權(quán)和優(yōu)先補(bǔ)償權(quán)，以優(yōu)先生產(chǎn)權(quán)順序及當(dāng)月市場(chǎng)需求進(jìn)行貪婪的生產(chǎn)，直至無(wú)法得到滿足，得出這幾種產(chǎn)品的計(jì)劃生產(chǎn)量。再搜索該負(fù)值能否由最近的上一時(shí)段進(jìn)行補(bǔ)償，如果能夠補(bǔ)償，則根據(jù)優(yōu)先補(bǔ)償原則進(jìn)行貪婪補(bǔ)償（數(shù)量不能超過(guò)最大庫(kù)存），直至不足以補(bǔ)償或者全部補(bǔ)償，再根據(jù)各產(chǎn)品補(bǔ)償數(shù)量算出新的生產(chǎn)能力差值，如出現(xiàn)新的負(fù)值是由補(bǔ)償造成的，暫不考慮，留作下一輪補(bǔ)償。

步驟2：搜索T1中的數(shù)據(jù)如果出現(xiàn)負(fù)值，則使用該加工過(guò)程的產(chǎn)品必然不能全部生產(chǎn)，根據(jù)效益優(yōu)先原則，優(yōu)先生產(chǎn)效益高、低工時(shí)消耗的產(chǎn)品（參照第四步），并算出新的生產(chǎn)能力差值。

步驟3：重復(fù)步驟1、2處理過(guò)程，直到所有數(shù)據(jù)為正，即可得到各時(shí)間段計(jì)劃生產(chǎn)量，由各月份補(bǔ)償數(shù)量得到庫(kù)存量，問(wèn)題得以求解。

3 算例分析及實(shí)現(xiàn)

根據(jù)上面提出的模型，我們對(duì)開(kāi)始提出的問(wèn)題按以下算法進(jìn)行求解：

第一步：計(jì)算最大生產(chǎn)能力：Nij=第i個(gè)月第j種機(jī)床數(shù)目×工作日×日工作時(shí)間，將所得數(shù)據(jù)填入表一各數(shù)據(jù)單元（含3個(gè)單元格）中左上單元格中。

第二步：計(jì)算各月內(nèi)滿足市場(chǎng)容量所需的各個(gè)加工過(guò)程的生產(chǎn)能力 ：Rij= Zki×tij(k=1,2,…r；j=1,2,…m ； i=1，2，…n)，將所得數(shù)據(jù)填入表一各數(shù)據(jù)單元（含三個(gè)單元格）中左下單元格中。

第三步：計(jì)算各月份最大生產(chǎn)能力和市場(chǎng)容量所需生產(chǎn)能力的差值：Skj=Nkj–Rkj。所得數(shù)據(jù)填入表1各數(shù)據(jù)單元（含3個(gè)單元格）中右側(cè)單元格中。

表1

第四步：一月份磨床為負(fù)，所影響的產(chǎn)品有P1、P2、P5、P6、P7，算出這幾種產(chǎn)品的優(yōu)先生產(chǎn)權(quán)值，優(yōu)先權(quán)順序?yàn)椋篜6、P5、P1、P2、P7，依此順序優(yōu)先安排這幾種產(chǎn)品生產(chǎn)任務(wù)為：X16=200，X15=800，X11=500，X12=888，X17=0，一月份其它產(chǎn)品均能滿足，則一月份初步計(jì)劃為 ：X1i=（500，888，300，300，800，200，0）。作為新的生產(chǎn)需求算出新的生產(chǎn)能力需求及差值，填入表2；六月份除完成生產(chǎn)任務(wù)還要有一定庫(kù)存，將六月份庫(kù)存任務(wù)加入六月份生產(chǎn)計(jì)劃，算出新的生產(chǎn)能力需求及差值填入表2，則六月份生產(chǎn)任務(wù)暫定為X6i=（550，550，150，350，1150，250，110）。二維表中未出現(xiàn)負(fù)值的月份生產(chǎn)能力過(guò)剩，將市場(chǎng)需求直接作為生產(chǎn)計(jì)劃量。

表2

第五步：

1）從表2出發(fā)從上到下找到第一個(gè)負(fù)值為-91，為3月份鏜床不足。所影響的產(chǎn)品為P1、P2、P4、P5、P7，但由于鏜床生產(chǎn)能力為0，即這幾種產(chǎn)品一個(gè)也不能按優(yōu)先生產(chǎn)順序生產(chǎn)，必須全部由上個(gè)月份補(bǔ)償，則算出幾種產(chǎn)品優(yōu)先補(bǔ)償順序?yàn)镻1、P2、P5、P4、P7，依據(jù)此順序和生產(chǎn)任務(wù)及最大庫(kù)存由2月份進(jìn)行貪婪補(bǔ)償，補(bǔ)償數(shù)量分別為：X21補(bǔ)=100，X22補(bǔ)=100，X24補(bǔ)=0，X25補(bǔ)=100，X27補(bǔ)=100。根據(jù)此補(bǔ)償需求算出新的生產(chǎn)能力需求及差值（產(chǎn)生新的生產(chǎn)能力不足暫不考慮），填入表3。則得到此次處理的2、3月份初步生產(chǎn)計(jì)劃：X2i=（700，600，200，0，500，300，250）；X3i=（0，0，0，0，0，400，0）。在向下找到第2個(gè)負(fù)值為-64.5，為6月份刨床不足。和上面做同樣處理，得到5月份補(bǔ)償六月份的產(chǎn)品及數(shù)量為：X53補(bǔ)=100，X55補(bǔ)=100，X57補(bǔ)=100，算出新的需求及差值，得到的數(shù)據(jù)填入表3，得到5、6月份暫時(shí)生產(chǎn)計(jì)劃為：X5i=（0，100，600，100，1100，300，100）；X6i=（550，550，0，350，0，550，0）。

表3

2）考察到1月份沒(méi)有出現(xiàn)負(fù)值，則進(jìn)行第二輪處理。

3）從表3出發(fā)從上到下找到的第一個(gè)負(fù)值為-66，為2月份水平鉆床不足，所影響的產(chǎn)品有P1、P3、P7。算出這幾種產(chǎn)品的優(yōu)先生產(chǎn)權(quán)值，優(yōu)先權(quán)順序?yàn)椋篜1、P3、，依此順序優(yōu)先安排這幾種產(chǎn)品生產(chǎn)任務(wù)為：X21=700，X23=200，X27=140，2月份其它產(chǎn)品均能滿足，則2月份計(jì)劃為：X2i=（700，600，200，0，500，300，150）。在根據(jù)優(yōu)先補(bǔ)償順序進(jìn)行補(bǔ)償，計(jì)算時(shí)因?yàn)镻1、P3已滿足計(jì)劃，則由一月份補(bǔ)償P7不足，X17補(bǔ)=100作為新的生產(chǎn)需求算出新的生產(chǎn)能力需求及差值，填入表四。

4）考察到1月份磨床生產(chǎn)能力又出現(xiàn)負(fù)值，重復(fù)第四步對(duì)1月份的處理辦法，得到結(jié)果為P7無(wú)法由1月份補(bǔ)償。1月份計(jì)劃量仍為 X1i=（500，888，300，300，800，200，0）。

5）經(jīng)過(guò)以上處理的數(shù)據(jù)已經(jīng)沒(méi)有負(fù)值，問(wèn)題得到解決，各月份生產(chǎn)計(jì)劃量為：

其中補(bǔ)償生產(chǎn)產(chǎn)生的庫(kù)存為：

4 結(jié)論

本文在解決此實(shí)際問(wèn)題中，提出了一種基于優(yōu)先補(bǔ)償權(quán)和優(yōu)先生產(chǎn)權(quán)準(zhǔn)則下的規(guī)劃模型，為解決此類實(shí)際問(wèn)題找到了一種較為通用的算法，該算法可以方便的用于程序?qū)崿F(xiàn)，具有一定的實(shí)用價(jià)值。

[1]李清，錢頌迪.運(yùn)籌學(xué)[M].北京：清華大學(xué).

[2]秦宣云.基于優(yōu)先缺貨權(quán)的工廠生產(chǎn)計(jì)劃的動(dòng)態(tài)規(guī)劃模型 [J].長(zhǎng)沙：系統(tǒng)工程，2002.

[T-9]

A

1674-6708（2010）22-0211-02