馬春苗 譚希麗

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

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

【中圖分類號(hào)】G642 ?【文獻(xiàn)標(biāo)識(shí)碼】A ?【文章編號(hào)】1671-8437（2020）16-0253-02

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

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

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

【參考文獻(xiàn)】

[1]胡運(yùn)權(quán)，等.運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用（第五版）[M].北京：高等教育出版社，2008.

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

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

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

【作者簡(jiǎn)介】

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

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