割平面加速策略的探究與改進

馬春苗 譚希麗

【摘 要】整數(shù)規(guī)劃在數(shù)學規(guī)劃中具有重要的地位。整數(shù)規(guī)劃求解的重要方法之一就是割平面法。在使用割平面法求解整數(shù)規(guī)劃時，尋找Gomory約束是最為關鍵的一步，如何選取較好的Gomory約束，以便加快收斂速度是目前研究的重要課題。

【關鍵詞】整數(shù)規(guī)劃;割平面法;割平面方程;改進方案

【中圖分類號】G642 ?【文獻標識碼】A ?【文章編號】1671-8437（2020）16-0253-02

整數(shù)規(guī)劃是數(shù)學規(guī)劃的一個重要的分支，在工業(yè)、商業(yè)、運輸、經(jīng)濟管理和軍事等領域中都有重要的應用。割平面法是求解整數(shù)規(guī)劃的一種重要方法。目前，多數(shù)運籌學教科書關于割平面法的講解不夠深入、細致，在解題時不能夠靈活應用，經(jīng)常切割很多次仍找不到最優(yōu)解，即遇到向最優(yōu)解收斂很慢的情形，學生普遍認為割平面不如分支界定法有效。然而，實際情況并非如此，靈活運用割平面法可以使得整數(shù)規(guī)劃的求解過程更加容易[1]。最近，仍有許多學者在對割平面法進行研究，并發(fā)現(xiàn)該方法也有很好的效果。本文對割平面法做進一步深入的研究，以讓割平面法能夠更靈活地被運用。

1 ? 割平面法求解問題的思路

綜上所述，本文主要討論了兩種割平面法的改進方案，并對兩種方案進行了對比。一種是用割平面法求解時，利用已知、已得信息，將這些超平面的線性組合生成新的Gomory約束，并取代原來的系統(tǒng)約束，從而較快地得到最優(yōu)解。另一種是在用割平面法求解問題時，選取非整數(shù)解變量中分數(shù)部分最大的一個基變量，取相應行的約束，推導出該行的Gomory約束[4]。當非整數(shù)解變量中分數(shù)部分最大的基變量有兩個或兩個以上時，進行比較，從中選出切割條件較強的Gomory約束，以減少切割次數(shù)和運算量，從而較快地找到最優(yōu)解。

【參考文獻】

[1]胡運權，等.運籌學基礎及應用（第五版）[M].北京：高等教育出版社，2008.

[2]呂一兵，萬仲平.一種求解線性二層規(guī)劃的割平面方法[J].數(shù)學的實踐與認識，2012（21）.

[3]李裕梅，連曉峰，徐美萍，曹顯兵.整數(shù)規(guī)劃中割平面法的研究[J].數(shù)學的實踐與認識，2011（11）.

[4]劉振航，王全文，吳振奎.割平面法的改進[J].天津輕工業(yè)學院學報，2003（S1）.

【作者簡介】

馬春苗（1995～），女，吉林長春人，碩士在讀。研究方向：概率極限理論與應用。

譚希麗（1974～），女，吉林長春人，教授，博士，碩士生導師。研究方向：概率極限理論與應用。