基于離散優化的LP汽車總裝線的配置模型研究

王誠

（蘭州石化職業技術學院，甘肅 蘭州 730060）

0 引言

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

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

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

1 基本離散優化模型

考慮到汽車總裝線的配置是一個離散模型的網絡與組合優化問題，建立排序與時間表離散優化模型。

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

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

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

建立條件約束的離散優化LP模型：

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

2 實例應用

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

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

3 模型的檢驗

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

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

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

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

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

通過查閱資料，4個一級指標權重見表2。

表2 4個一級指標權重

經分析題目中所給二級指標的重要性，14個二級指標權重見表3。

表3 14個二級指標權重

通過MATLAB編程計算分析：

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

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

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

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

4 模型的評價與改進

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

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

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

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

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

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