李立欣　許健開

摘要：目前，在生產(chǎn)過程中，如何用最少的人力、物力、財力和時間去生產(chǎn)更多的產(chǎn)品是生產(chǎn)行業(yè)的熱點(diǎn)研究問題，有重要的研究意義。本文通過建立線性規(guī)劃模型，用Lingo和matlab軟件，實現(xiàn)了對生產(chǎn)時滿足資源消耗限制、加工工序等條件下，生產(chǎn)時間最少、生產(chǎn)成本最低問題的求解。

針對問題一，采用0—1規(guī)劃，設(shè)置25個0—1變量，建立各組件生產(chǎn)時間總和最小的目標(biāo)函數(shù)，根據(jù)題目所給的資源消耗限制及組件生產(chǎn)數(shù)量限制建立約束條件，編寫程序，用Lingo進(jìn)行模型求解。求解完畢后，考慮不同生產(chǎn)線可同時生產(chǎn)，消去計算過程中疊加的時間，計算出最短生產(chǎn)時間，得出計劃安排。

針對問題二，在問題一的基礎(chǔ)上，改變目標(biāo)函數(shù)中各變量系數(shù)的值，使求用時最短變?yōu)樗觅M(fèi)用最少，增加每條生產(chǎn)線只能生產(chǎn)一種組件的約束，刪去生產(chǎn)線B生產(chǎn)組件5對應(yīng)的變量。再編寫程序，用Lingo進(jìn)行模型求解，得到滿足資源消耗條件下，生產(chǎn)線費(fèi)用與資源費(fèi)用之和最小的生產(chǎn)計劃安排。

針對問題三，先選用matlab軟件編寫程序，求出滿足資源消耗限制的所有組件與生產(chǎn)線的組合情況，在此基礎(chǔ)上，再根據(jù)組件與組件間加工的前驅(qū)工序要求及各組件在不同生產(chǎn)線生產(chǎn)的用時情況，固定某個組件在哪條生產(chǎn)線生產(chǎn)，用枚舉法，多次試驗，得出用時最短的生產(chǎn)計劃安排。

最后，對所建模型及求解方法進(jìn)行優(yōu)客觀評價。

關(guān)鍵詞：0—1規(guī)劃；生產(chǎn)優(yōu)化 ；Lingo；MATLAB

中圖分類號：O221文獻(xiàn)標(biāo)識碼：A

1 問題重述

1.1 問題背景

組件生產(chǎn)是生產(chǎn)產(chǎn)品過程中重要的一部分，其生產(chǎn)時間的快慢及消耗成本的多少直接影響著工廠的獲利情況。工業(yè)是國民經(jīng)濟(jì)的主導(dǎo)產(chǎn)業(yè)，隨著經(jīng)濟(jì)的快速發(fā)展，我國工廠的數(shù)量持續(xù)增加，如何減少生產(chǎn)時間、降低生產(chǎn)成本、制定可行的生產(chǎn)方案，對生產(chǎn)行業(yè)具有重大的意義。

1.2 問題描述

某車間有五臺生產(chǎn)線，生產(chǎn)5個組件，不允許兩種組件同時在一個生產(chǎn)線上生產(chǎn)，已知每個組件在不同生產(chǎn)線上的生產(chǎn)時間與資源消耗情況，以及組件和組件間的加工的前驅(qū)工序要求。

試建立數(shù)學(xué)模型解決以下問題：

（1）不考慮組件加工順序，求滿足資源消耗限制的組件生產(chǎn)時間最少的計劃安排；

（2）若假設(shè)每條生產(chǎn)線只能完成一種組件，且因工藝要求，5號組件不能再生產(chǎn)線B上加工，又知5條生產(chǎn)線每小時的運(yùn)行成本及五種資源的單位成本，求在滿足資源消耗限制條件下，組件生產(chǎn)費(fèi)用最小的計劃安排；

（3）考慮組件加工順序，求滿足資源消耗限制的組件生產(chǎn)時間最少的計劃安排，并計算全部組件生產(chǎn)完畢的最短時間。

2 模型假設(shè)

（1）假設(shè)組件交接過程中即上一個組件生產(chǎn)完，下一個組件就開始生產(chǎn)，沒有時間浪費(fèi)；

（2）假設(shè)不同生產(chǎn)線上可以同時生產(chǎn)；

（3）假設(shè)每條生產(chǎn)線同一時間只能生產(chǎn)一個組件；

（4）假設(shè)每種組件生產(chǎn)的數(shù)量為1或0；

（5）假設(shè)工作中機(jī)器不會出現(xiàn)意外，會一直運(yùn)行。

3 符號說明

Xij：生產(chǎn)線i（i=A，B，C，D，E）生產(chǎn)組件j（j=1，2，3，4，5）的數(shù)量；

Cij：生產(chǎn)線i（i=A，B，C，D，E）生產(chǎn)組件j（j=1，2，3，4，5）所需時間；

Fij：生產(chǎn)線i（i=A，B，C，D，E）生產(chǎn)組件j（j=1，2，3，4，5）每小時的運(yùn)行成本；

Wk：Xij消耗資源k（k=1，2，3，4，5）的成本。

4 模型的建立與求解

4.1 問題一的建模與求解

（1）問題分析。

為求滿足資源消耗限制的組件生產(chǎn)時間最少的計劃安排，需利用0—1規(guī)劃，建立求各組件生產(chǎn)時間總和最小的目標(biāo)函數(shù)，再根據(jù)題目所給的資源消耗限制及組件生產(chǎn)數(shù)量限制建立約束條件，用Lingo進(jìn)行模型求解。求解完畢后，再根據(jù)假設(shè)2.2，考慮不同生產(chǎn)線可同時生產(chǎn)，計算出最短生產(chǎn)時間，得出計劃安排。

（2）模型的建立。

①目標(biāo)函數(shù)的建立。

根據(jù)題目所給的信息，建立生產(chǎn)時間總和最少的目標(biāo)函數(shù)：

minz=∑i=E，j=5i=A，j=1Cij*Xij

根據(jù)題目所給的數(shù)據(jù)，目標(biāo)函數(shù)展開為：

z=10XA1+8XA2+20XA3+4XA4+8XA5+4XB1+10XB2+6XB3+12XB4+5XB5+22XC1+13XC2+4XC3+10XC4+8XC5+2XD1+16XD2+25XD3+8XD4+2XD5+6XE1+8XE2+13XE3+11XE4+16XE5

②約束條件的建立。

由題知，要求生產(chǎn)所消耗的各種資源滿足現(xiàn)有的資源提供量，即5種資源消耗約束分別為：

2XA1+XA3+2XB2+XB3+XC1+2XC2+XC5+2XD2+XD3+2XE4+XE5

SymbolcB@ 3XA2+2XA5+2XB1+XB4+2XC2+3XD2+2XD4+3XD5+XE1+3XE5

SymbolcB@ 42XA1+2XA3+XB1+2XB2+2XC3+2XD3+3XE4

SymbolcB@ 3XA1+2XA2+3XA4+2XB3+3XB5+2XC3+XC4+XC5+XD1+3XD4+4XE2+XE4

SymbolcB@ 45XA2+5XA4+2XA5+5XB3+2XB4+4XC4+3XC5+2XD1+6XD5+2XE1+3XE3

SymbolcB@ 6

且5種組件都需生產(chǎn)1個：

XA1+XB1+XC1+XD1+XE1=1；XA2+XB2+XC2+XD2+XE2=1；XA3+XB3+XC3+XD3+XE3=1；XA4+XB4+XC4+XD4+XE4=1；XA5+XB5+XC5+XD5+XE5=1

組件j在生產(chǎn)線i上生產(chǎn)1個或不生產(chǎn)：

Xij=01；i=A，B，C，D，E，j=1，2，3，4，5

（3）模型的求解。

用Lingo軟件求解得：最短時間為44小時，變量XB1，XB2，XC5，XD4，XE3值為1，其它變量值為0。

因不同生產(chǎn)線可同時生產(chǎn)，故消去計算過程中疊加的時間，取各生產(chǎn)線所用時間的最大值：

max（CB1+CB2，CC5，CD4，CE3）=max（4+10，8，8，13）=14，

因此，實際生產(chǎn)所用最短時間為14小時，生產(chǎn)計劃安排為：

生產(chǎn)線A不生產(chǎn)；

生產(chǎn)線B生產(chǎn)組件1和組件2；

生產(chǎn)線C生產(chǎn)組件5；

生產(chǎn)線D生產(chǎn)組件4；

生產(chǎn)線E生產(chǎn)組件3。

4.2 問題二的建立與求解

（1）問題分析。

題目要求每條生產(chǎn)線只能完成一種組件，且5號組件不能在生產(chǎn)線B上加工，給出了各生產(chǎn)線每小時的運(yùn)行成本及資源的單位成本，求滿足資源消耗限制下，生產(chǎn)費(fèi)用最小的計劃安排。因此，只要在問題一的基礎(chǔ)上，改變以下幾個地方：

①取消變量XB5；

②改變目標(biāo)函數(shù)中各變量系數(shù)的值，使求用時最短變?yōu)橘M(fèi)用最少；

③增加每條生產(chǎn)線只能生產(chǎn)一種組件的約束。

（2）模型的建立。

①目標(biāo)函數(shù)的建立。

根據(jù)題目所給信息，建立生產(chǎn)線運(yùn)行成本與資源消耗成本費(fèi)用之和最少的目標(biāo)函數(shù)：

minz=∑i=E，j=5，k=5i=A，j=1，k=1（Cij*Fij+Wk）*Xij （不取XB5）

代入數(shù)值，展開化簡為：

z=17900XA1+17000XA2+27400XA3+13300XA4+12000XA5+5200XB1+12400XB2+12800XB3+11600XB4+34000XC1+22300XC2+12900XC3+19700XC4+16900XC5+5500XD1+22400XD2+33400XD3+14900XD4+8400XD5+6800XE1+12400XE2+12800XE3+15900XE4+15000XE5

②約束條件的建立。

在問題一建立的對資源消耗和組件生產(chǎn)數(shù)量的約束上刪去變量XB5：

XA1+XB1+XC1+XD1+XE1=1；XA2+XB2+XC2+XD2+XE2=1；XA3+XB3+XC3+XD3+XE3=1；XA4+XB4+XC4+XD4+XE4=1；XA5+XC5+XD5+XE5=1；

2XA1+XA3+2XB2+XB3+XC1+2XC2+XC5+2XD2+XD3+2XE4+XE5

SymbolcB@ 3XA2+2XA5+2XB1+XB4+2XC2+3XD2+2XD4+3XD5+XE1+3XE5

SymbolcB@ 42XA1+2XA3+XB1+2XB2+2XC3+2XD3+3XE4

SymbolcB@ 3XA1+2XA2+3XA4+2XB3+2XC3+XC4+XC5+XD1+3XD4+4XE2+XE4

SymbolcB@ 45XA2+5XA4+2XA5+5XB3+2XB4+4XC4+3XC5+2XD1+6XD5+2XE1+3XE3

SymbolcB@ 6

根據(jù)題目要求，建立每條生產(chǎn)線只能完成一種組件的約束，即各生產(chǎn)線生產(chǎn)的組件數(shù)為1：

XA1+XA2+XA3+XA4+XA5=1；XB1+XB2+XB3+XB4=1；XC1+XC2+XC3+XC4+XC5=1；XD1+XD2+XD3+XD4+XD5=1；XE1+XE2+XE3+XE4+XE5=1；

Xij=01；i=A，B，C，D，E，j=1，2，3，4，5

（3）模型的求解。

編寫算法，用Lingo軟件求解得：滿足資源消耗的生產(chǎn)費(fèi)用最小為86100元。生產(chǎn)計劃安排為：

生產(chǎn)線A生產(chǎn)組件5；

生產(chǎn)線B生產(chǎn)組件2；

生產(chǎn)線C生產(chǎn)組件1；

生產(chǎn)線D生產(chǎn)組件5；

生產(chǎn)線E生產(chǎn)組件4。

4.3 問題三的建立與求解

（1）問題分析。

題目給出各生產(chǎn)線上生產(chǎn)5種組件對應(yīng)的前驅(qū)組件生產(chǎn)情況，要求考慮組件生產(chǎn)情況，重新求解第一問，計算全部組件生產(chǎn)完畢的最短時間。因每條生產(chǎn)線對各種組件的前驅(qū)組件生產(chǎn)要求不同，要綜合考慮以下幾種情況：

①生產(chǎn)計劃要滿足資源消耗要求。

②不同生產(chǎn)線可同時生產(chǎn)。

③有前驅(qū)組件的要等前驅(qū)組件生產(chǎn)完才可以開始生產(chǎn)。

④若多個組件在同一條生產(chǎn)線上生產(chǎn)，需等上一個生產(chǎn)完才能生產(chǎn)下一個。因此，情況比較復(fù)雜，無法建立用時最短的目標(biāo)函數(shù)，不能采用線性規(guī)劃方法。

若用多階段決策，人為進(jìn)行判斷，每次選取用時較少的組合方案，不確定性大，很難得到最優(yōu)結(jié)果，且不一定滿足資源消耗限制。

綜上所述，選用matlab軟件編寫程序，求出滿足資源消耗限制的所有組合情況，在此基礎(chǔ)上，再根據(jù)組件與組件間加工的前驅(qū)工序要求及各組件在不同生產(chǎn)線生產(chǎn)的用時情況，固定某個組件在哪條生產(chǎn)線生產(chǎn)，用枚舉法，多次試驗，得出用時最短的生產(chǎn)計劃安排。

（2）模型的建立與求解。

根據(jù)題目所給資源限制、各組件在不同生產(chǎn)線生產(chǎn)所需生產(chǎn)時間、5種資源消耗情況、和前驅(qū)工序要求，用matlab編寫相關(guān)算法，運(yùn)用for循環(huán)語句，算出滿足資源消耗限制的所有組件與生產(chǎn)線安排情況。在此基礎(chǔ)上，運(yùn)用枚舉法，每次給定不同的組件與生產(chǎn)線組合約束，計算生產(chǎn)完畢所用時間。經(jīng)過多次試驗，得出在組合約束為R1==2 & R5==2，即組件1在生產(chǎn)線B生產(chǎn)，組件5也在生產(chǎn)線B上生產(chǎn)為時，能求得用時最短方案：

5 模型評價

問題一與問題二所建模型運(yùn)用0—1規(guī)劃，思路清晰，模型嚴(yán)謹(jǐn)，簡明易懂，且求解方法簡單，結(jié)果準(zhǔn)確，說服力強(qiáng)，具有很好的實用性。

問題三所建模型及求解方法具有可行性，但求解過程較復(fù)雜，耗時較長，計算結(jié)果容易出現(xiàn)偏差。

參考文獻(xiàn)：

[1]陳皆妤，鄒晶娜，胡瑜琳，陳俊璇.零件加工優(yōu)化排序問題，職業(yè)教育，14：172，2015.

[2]陳忠實，蔣昱辰.0—1整數(shù)規(guī)劃求解法，北京化工大學(xué)學(xué)報自然科學(xué)版，5965，1989.3.

[3]刁在筠.運(yùn)籌學(xué)，北京：高等教育出版社，2016.7.

[4]謝金星.優(yōu)化建模與LINGO.北京：清華大學(xué)出版社，2005.7.

作者簡介：第一作者：李立欣（1998），女，漢族，本科。

*通訊作者：許健開（1978），男，漢族，博士研究生，副教授，主要研究微分方程與調(diào)和分析。