王誠

（蘭州石化職業(yè)技術(shù)學院，甘肅 蘭州 730060）

0 引言

汽車公司汽車總裝線的配置是一個綜合性排列優(yōu)化組合問題，如何按照所提供的裝配要求進行科學有效的設(shè)計，是降低成本、提高效率產(chǎn)能的關(guān)鍵。

本文針對2018年全國數(shù)學建模競賽D題汽車總裝線的配置問題進行了分析研究?？紤]到汽車總裝線的配置是一個離散模型的網(wǎng)絡(luò)與組合優(yōu)化問題，建立排序與時間表離散優(yōu)化模型。采取啟發(fā)式算法——分支定界法思路：靠下界控制搜索方向，若搜索到某一步比其他分支的下界大，就從下界小的分支繼續(xù)搜索。

建立條件約束的離散優(yōu)化LP模型，用MATLAB編程進行離散優(yōu)化分析，給出了在工藝流程的制約和質(zhì)量控制的需要以及降低成本的考慮下最優(yōu)的裝配方法，利用AHP模型進行滿意度檢驗，對所建模型進行分析和改進[1-3]。

1 基本離散優(yōu)化模型

考慮到汽車總裝線的配置是一個離散模型的網(wǎng)絡(luò)與組合優(yōu)化問題，建立排序與時間表離散優(yōu)化模型。

排序與時間表就是將不同的任務(wù)以一個執(zhí)行的順序和時間來安排，使得預定的目標最優(yōu)化，比如時間最短、費用最省、效率或效益最大等。

針對裝配要求，我們化繁就簡，不考慮前期工件特別要求，在設(shè)置的2條生產(chǎn)線，兩驅(qū)和四驅(qū)的裝配要求及顏色的條件約束，加工時間較短，使得整個生產(chǎn)工藝流程成本較低。根據(jù)SPT（Shortest Processing Time）法則，可得到相應的最優(yōu)加工順序，但SPT不能直接應用于此題目。

采取啟發(fā)式算法——分支定界法思路：靠下界控制搜索方向，若搜索到某一步比其他分支的下界大，就從下界小的分支繼續(xù)搜索。最壞情況下，窮舉所有可能的排列組合，這是一個隱含的窮舉法，但在解決此類復雜的組合優(yōu)化問題比較有效。

建立條件約束的離散優(yōu)化LP模型：

由于約束矩陣是全單位模的，即任何階子式的值為1，-1或0，有研究結(jié)論說，整數(shù)線性規(guī)劃當中的整數(shù)要求可以去掉而化為線性規(guī)則。所以，最優(yōu)化問題可以用LP模型解決[4-8]。

2 實例應用

離散優(yōu)化的LP汽車總裝線的配置模型，按照題目給出的條件約束，運用MATLAB進行編程模擬，抓取主要影響參數(shù)，給出了具有較低成本的裝配順序。

針對題中條件約束，編程時受阻因素較多，程序多次運行失敗。在只滿足硬性要求時，也出現(xiàn)運行不下去的情況，適當調(diào)整了約束條件參數(shù)。同時沒有考慮連續(xù)時間如17日到18日的時間銜接和互相影響因素，只研究每天的排列組合情況，這在實際生產(chǎn)過程中是降低成本的關(guān)鍵點。

3 模型的檢驗

利用AHP（層次分析法）模型進行滿意度檢驗。

引入裝配滿意度對模型編寫的裝配順序進行評價，問題對裝配要求有4個一級指標，14個二級指標。

研究第2個一級指標，如：若間隔數(shù)量無法滿足要求，仍希望間隔數(shù)量越多越好。間隔數(shù)量在5-9輛仍是可以接受的，但代價很高。將代價很高轉(zhuǎn)換為裝配順序滿意度，超過10輛滿意度為100%，5-9輛之間的滿意度設(shè)置如表1：

表1 第2個一級指標車輛間隔數(shù)滿意度

同理可設(shè)置其他二級指標相對應滿意度。

通過查閱資料，4個一級指標權(quán)重見表2。

表2 4個一級指標權(quán)重

經(jīng)分析題目中所給二級指標的重要性，14個二級指標權(quán)重見表3。

表3 14個二級指標權(quán)重

通過MATLAB編程計算分析：

9月18日無論如何分配黑色噴漆，均達不到50-70的條件約束；

9月23日，A1總計367，A2總計93，均為單數(shù)，導致白天和晚上無法平均分配進行裝配。

其他時間滿意度均能達到90%左右，9月18日和9月23日滿意度在80%左右，綜合整體裝配順序，模型滿意度達到了90%以上，結(jié)果是滿意的。

離散優(yōu)化的LP汽車總裝線的配置模型在每次程序搜索生成裝配順序時，可能結(jié)果都不一致，可運用AHP模型進行滿意度檢驗，多次運行程序比較可得到相對最優(yōu)值[9-14]。

4 模型的評價與改進

本文離散優(yōu)化的LP汽車總裝線的配置模型，可以借助LINDO、MATALAB、EXCEL-Solver等，也可將組合優(yōu)化模型優(yōu)化為整數(shù)線性規(guī)劃模型。

采取連續(xù)化方法后模型比較復雜，無法求出問題解，只能退而求其次求出數(shù)值解。即建模時對離散變量做了連續(xù)化處理，而在求解時，對連續(xù)變量作了離散化處理。有時變量事實上只能取自一個有限元集合，如何建立相應模型并設(shè)計高效算法是非常重要的。

建立條件約束的離散優(yōu)化LP模型是典型的NP問題。

經(jīng)查閱相關(guān)資料，NP完全問題已經(jīng)有幾千個，包括最小Steiner樹問題、Hamilton問題、最大點獨立集問題、大多數(shù)的排序問題都屬于NP完全類，這類問題的任意一個到目前為止尚未找到有效算法。

如何解決NP問題是目前求解的一大難點，采用窮舉法不切實際。對題目中品牌分為A1和A2兩種，配置分為B1、B2、B3、B4、B5、B6六種，動力分為汽油和柴油2種，顏色黑、白、藍、黃、紅、銀、棕、匯、金九種，動力分為兩驅(qū)和四驅(qū)2種。只討論顏色和品牌，即為18種不同的產(chǎn)品，在生產(chǎn)線上出現(xiàn)的順序排列方法有：18!/2 =1045094400 ≈ 3.2× 1 015之多。按照當前計算機處理數(shù)據(jù)能力每秒計算100億=1010個排列情況，需要3.2× 1 05≈ 89小時 ≈3.7個日夜。再考慮其他4種因素，需要時間是呈數(shù)量級的增長[15，16]。

找出最優(yōu)組合的排列順序，如按照離散問題的窮舉法思路，需要花費的時間是難以想象的，也不太可能實現(xiàn)。因此，在解決實際問題中，適當摒棄不合理數(shù)據(jù)和過多約束條件，是初步解決此類問題的一個有效途徑。