陳本士

哈爾濱德強商務學院，黑龍江哈爾濱 150025

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

陳本士

哈爾濱德強商務學院，黑龍江哈爾濱 150025

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

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

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

1 一個生產(chǎn)計劃的實際問題

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

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

2 問題的一般化與求解模型

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

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

其中 ，Xki＜Zki;Yki＜Gki

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

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

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

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

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

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

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

具體算法步驟如下：

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

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

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

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

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

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

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

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

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

根據(jù)上面提出的模型，我們對開始提出的問題按以下算法進行求解：

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

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

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

表1

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

表2

第五步：

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

表3

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

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

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

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

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

4 結(jié)論

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

[1]李清，錢頌迪.運籌學[M].北京：清華大學.

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

[T-9]

A

1674-6708（2010）22-0211-02