數學建模中的規劃問題怎麼求解？

12-28

做數模的時候經常遇到各種線性/非線性blabla規劃，規劃好寫但是解很困難。Lingo解一個小時甚至不能得到局部最優解，用遺傳演算法有時候也不能收斂（也可能是因為規劃寫的太爛了）。觀察2014年國賽A題的一獎論文，發現大家規劃都寫的差不多，解法也無非是轉換成非線性離散規劃再用LIngo或者GA，但即使是這些一獎論文，他們得到的最終結果也相差很大。所以我就在懷疑他們是不是沒有解出來全局最優解，而是直接「忽悠」了一個答案上去。
想問下知乎大神們，數學建模競賽中的規劃問題真的是可以求解的嗎？有沒有誰有什麼經驗心得？

曾經用Lingo跑過一題複雜的TSP問題，電腦跑了一個晚上，所以對於優化問題可以簡單說幾點。
1、關於題主的疑問：他們得到的最終結果相差很大。
首先，數學建模是一個重模型輕結果的比賽，特別是美賽，雖然多數評委是中國人，他們看重你的方法或者模型有無創新，寫作如何，結果往往不是特別重要。比較重視結果的國賽A題、深圳杯等往往給出結果的一個範圍，如果在那個範圍內基本能拿好獎。所以不同結果都拿國一不是沒有可能（國賽B題結果更是五花八門，俗話說言之有理即可）。
2、對於優化問題能否真實求解。
首先解釋下Lingo這個軟體吧，LINGO是Linearnteractive and General Optimizer的縮寫，即「互動式的線性和通用優化求解器」，可以用於求解非線性規劃，也可以用於一些線性和非線性方程組的求解等。其特色在於可以允許決策變數是整數(即整數規劃，包括 0-1 整數規劃)，方便靈活，但是耗時往往長，且經常陷入局部最優。
而用Matlab、C寫的優化，跑的速度快，我曾對比過Lingo與C的實現TSP程序，C跑幾秒鐘Lingo需要跑好幾個小時~_~;可以說非常冒汗。但是Lingo也有它的好處，畢竟學起來以及代碼編寫非常簡單，入門級快。個人一直比較認同一點：一個東西一方面的快速勢必會導致另一方面的慢速。像Lingo思考容易，跑起來慢。而Matlab與C你寫個程序可能要半天，跑起來就幾秒鐘。
所以需要提到一個概念：混合編程。充分避免兩者缺點（筆者表示就第一次參加校賽用了Lingo，之後再沒有用過，因為真的慢⌒▽⌒）。
下面講講優化問題，一般在寫作時，優化問題需要一個目標函數，以及用大括弧括起來的一堆限制條件，這樣能給老師很好的印象。至於是否具有最優解或者陷入局部最優解，可以嘗試改變你的約束條件，一般局部最優都是你約束太多造成的。
當然有時候確實不能出結果，那我能咋辦，只能造一個像樣的結果假裝做出來了，而且還要裝的像。只要會講故事，國一不是夢。
ps：筆者往往在隊友沒出結果前就編好了大部分文章，所以很多國一隊伍特別是B題大部分都是沒有真正做出來的。
有想到的我再補充。
以上

本人做關於優化領域的相關研究，沒參加過數學建模競賽，從理論的角度回答一下。

優化領域涉及的問題很多，演算法也格式各樣，很難有個大概的概括。對於求解而言，無非就是用現成求解器解，或者自行設計演算法求解。但無論哪種方式，個人認為都有兩點是需要考慮的，一是問題本身特性，二是求解的目的。

（1）從問題特性來講

規劃問題的求解和問題本身的特性有很大關係。從理論上講，一個問題可解與否，首先要考慮問題的凸性（convexity）。對於一個凸優化問題（比如有限約束、變數的線性規劃問題），當前的優化軟體都能在多項式時間內找到全局最優解。

如果是非凸（non-convex）問題（比如目標函數是非凸函數，或者是整數規劃問題），想要在多項式時間內找到全局最優解在理論上也許根本不可能（NP-hard）。對於非凸問題，一般方法是將問題通過線性化等等手段將非凸問題轉化或簡化為凸問題，再用求解軟體求解。整數規劃問題比較特殊，雖然這個問題很複雜，但是目前很多軟體都集成了很強的工具包或者演算法來求解此類問題（比如cplex），所以規模不大的整數規劃問題可以直接用求解器求解。

（2）從求解目的來講

對於非凸問題而言，如果近似最優解，局部最優解在當前優化問題中也是可以接受的話，那完全可以設計類似的演算法進行求解，比如遺傳演算法。至於遺傳演算法，這種演算法目前在理論上並不完備，演算法的收斂性並未得到證明，所以很多學者（尤其是有數學背景的）都不大喜歡這種演算法。但是這並不妨礙遺傳演算法在解決工程問題中擁有廣闊的市場，因為對於許多非常複雜的問題而言，也許局部最優解，或者是一個不太差的解就已經能夠滿足需要了。

GA，TS之類演算法本身就不太可能會得到全局最優（不排除運氣好）。數學規劃求解方法一般可以分為兩類，精確方法（數學規劃）和啟發式演算法（GA，TS）。很多優化問題都是NP問題，即求解消耗會隨著問題規模指數級增長，所以經常會聽到說"求解一個100客戶的tsp問題要至少幾百萬年的時間"之類的命題。啟發式演算法就是在求解時間和解的質量之間尋求平衡。
然而隨著計算能力（硬體）和演算法的提升，很多以前難以求解的問題規模現在都可以精確求解，比如經典的tsp問題（詳情請參考WILLIAM的著作，中譯本迷茫的旅行商），VRP問題（2000和2014年，Vigo等人的兩本合集）。
但是，如果問題規模真的非常非常大，精確接法就不保證可以在合理時間內得到最優解。
就先寫這麼多吧，淺見。