淺析整數規劃法求解生產資源分配問題
2008-01-01 00:00:00胡浩云賈艷輝
中國校外教育(下旬) 2008年2期
[摘要]企業生產過程中，生產計劃的原材料分配合理與否直接影響到企業的經濟效益，本文介紹了一種分配生產計劃的整數規劃的數學模型，采用LINGO軟件進行計算，可快速準確的得出計算結果。說明整數規劃法是解決企業生產中資源分配問題的有效方法，具有一定的實用價值。
[關鍵詞]整數規劃 生產計劃 LINGO軟件 資源分配問題
由于計算機軟、硬件技術的發展，各行各業生產計劃的制定逐步由手工八九不離十的傳統經驗型轉變成計算機的科學型和優化型。生產型企業在制定生產計劃時，生產資料（資源）的分配在企業中占有非常重要的地位。有關企業生產計劃模型的研究，國內外已有一些報道。本文作者試圖通過整數規劃模型的建立、求解，闡述整數規劃解決生產型企業資源分配中的有關問題。
一、問題的提出
生產企業制定生產計劃，分配生產資源時，某原材料月分配計劃單位為百噸，日分配計劃的單位為噸，這樣常出現企業各車間總的日計劃分配額不等于各車間日計劃分配額的總合的情況（詳見表1）。
表1為企業按照該種原材料的存儲及運輸能力，各車間的生產情況，以百噸（或其他整數單位）為單位制定的初步分配計劃，按照該月初步計劃，每日以噸（或其他整數單位）為單位向各車間供應該種原材料，表1中，日計劃為按照月計劃分配額，以31天計算（四舍五入取整）的各車間日分配額，各車間日供應合計為8521噸，全月供應總量264151噸，超出了企業供應能力，可能會造成企業生產的不連續性。基于這個問題，就要對各車間的分配計劃進行微量調整，調整方法：（1）保持總計劃不變；（2）車間月計劃要整百的進行調整。
調整后結果見表2。
由表2可以看出，調整后的每日計劃總合與總的每日計劃結果一致。
表1為企業按照該種原材料的存儲及運輸能力，各車間的生產情況，以百噸（或其他整數單位）為單位制定的初步分配計劃，按照該月初步計劃，每日以噸（或其他整數單位）為單位向各車間供應該種原材料，表1中日計劃為按照月計劃分配額，以31天計算（四舍五入取整）的各車間日分配額，各車間日供應合計為8521噸，全月供應總量264151噸，超出了企業供應能力，可能會造成企業生產的不連續性。基于這個問題，就要對各車間的分配計劃進行微量調整，調整方法如下：（1）保持總計劃不變；（2）車間月計劃要整百的進行調整。
調整后結果見表2。由表2可以看出，調整后的每日計劃總合與總的每日計劃結果一致。
二、建立分配生產計劃的整數規劃模型
根據上述問題，設生產計劃向量 ，和10×10的調整矩陣A，
由上面假設，可以得出下面的整數規劃模型：
其中，（1）式為目標函數，式中的為調整總量，即調整總量最小；（2），（3）式為約束條件，（2）式要求調整后的生產計劃滿足每日總計劃與總的每日計劃相等，Int(R)為對R進行向下取整，Int(R+0.5)為對R進行整數位的四舍五入；（3）式要求調整量為非負整數，又由于車間月計劃要整百的調整，所以在（2）式中為。
三、問題的求解
1.證明
證明上述整數規劃問題的可行域不為空。即證明：
使得（2）式成立。
首先把X=（x1，x2，…，xn）T分解為兩項：
X=X1+X2
其中：
X1=(x11，x12，…x1n)，x1i為可被3100整除的最大整數；
X2=(x21，x22，…x2n)，x2i=xi-x1i。
令
這樣前n-1個xi調整后的值可以被31整除，xn調整后的值xnewn與S對31的整除性質相同。所以（2）式為，
左邊
右邊
所以說，上述整數規劃問題的可行域不為空。
2. 求解
本文采用LINGO軟件進行求解，LINGO軟件是Linus Schrage教授于1980年前后開發的一套專門用于求解最優化問題的工具包，后來經過了多年的不斷完善和擴充，并成立了LINDO系統公司進行商業化運作，取得了巨大成就。該軟件操作簡單，求解速度快。以下是求解上述問題的LINGO程序：
未列出的ai，j都為零，既只需x1+200，x5-100，x9-100，其余不變。調整后結果見表2。
因此，企業生產計劃中的原材料分配問題可以歸結為整數規劃問題，建立具體的數學模型，并利用LINGO軟件進行計算，可快速得到準確的結果。說明整數規劃在生產計劃中的實際應用，為分配生產計劃提供科學的方法，具有一定的實用價值。
參考文獻：
［1］Jones CV. Visualization and optimization. ORSA Journal on Computing， 1994， 6（3）： 221-257.［2］何小榮，李初福，陳丙珍等.石化企業生產計劃圖形健模優化系統［J］.計算機與應用化學，2006，23（1）：1-8.
［3］焦克軍，劉長松.應用計算機編制煤礦生產計劃［J］.煤炭技術，2006，25（2）：124-126.
（作者單位：河北工程大學，湖北武漢大學；河北工程大學）
注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
