[發(fā)明專利]混合整數(shù)線性規(guī)劃模型的求解方法

在審

• 申請?zhí)枺?/td>: 201410353035.3
• 申請日: 2014-07-23
• 公開（公告）號: CN104156508A
• 公開（公告）日: 2014-11-19
• 發(fā)明（設(shè)計）人: 劉紅超;邱紹明;黃傳安;應(yīng)波濤;李海;張健;顏瑞;陳清水;劉建南
• 申請（專利權(quán)）人: 國家電網(wǎng)公司;北京許繼電氣有限公司;中電投江西電力有限公司
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 北京立成智業(yè)專利代理事務(wù)所(普通合伙) 11310
• 代理人: 李想

技術(shù)領(lǐng)域

本發(fā)明涉及計算機(jī)技術(shù)領(lǐng)域，尤其涉及一種混合整數(shù)線性規(guī)劃模型的求解方法。

背景技術(shù)

與一般采購計劃線性規(guī)劃模型不同，煤炭采購計劃除采購重量、采購資金等基礎(chǔ)約束之外，還包括煤炭熱值、煤炭Vdaf、煤炭Std等煤炭品質(zhì)約束，且對于鐵路運(yùn)輸?shù)拿禾控浽匆话阋蟛少徚繛閱诬噹b煤量的整數(shù)倍。綜合這樣的特點(diǎn)，煤炭采購計劃線性規(guī)劃模型是一個混合整數(shù)線性規(guī)劃模型。

目前，混合整數(shù)線性規(guī)劃模型的求解算法主要包括精確算法和啟發(fā)式算法兩類，其中精確算法包括分支定界法、列生成法等，啟發(fā)式算法包括遺傳算法、蟻群算法、粒子群算法、模擬退火算法等。

其中，精確算法能夠求得模型的精確最優(yōu)解，但其缺點(diǎn)在于在現(xiàn)有計算機(jī)技術(shù)下、在有限的計算時間內(nèi)無法處理決策變量較多的問題。而啟發(fā)式算法雖然能夠處理決策變量較多的問題，但其得到的最優(yōu)解為近似最優(yōu)解，且比較容易陷入局部最優(yōu)解，所求得的近似最優(yōu)解與實(shí)際最優(yōu)解之間的差距無法衡量和估計。

發(fā)明內(nèi)容

本發(fā)明要解決的技術(shù)問題是，針對現(xiàn)有技術(shù)的不足，提供一種混合整數(shù)線性規(guī)劃模型的求解方法，提高計算效率，節(jié)約計算資源。

根據(jù)本發(fā)明一個方面，提供一種混合整數(shù)線性規(guī)劃模型的求解方法，包括：步驟1、采用單純形法求解無整數(shù)約束的線性規(guī)劃模型，得到一組無整數(shù)約束最優(yōu)解；步驟2、將整數(shù)約束決策變量的解從所求得的最優(yōu)解中分離出來，并直接賦以與所求得的最優(yōu)解最接近的整數(shù)值；步驟3、將整數(shù)約束決策變量及其約束從混合整數(shù)線性規(guī)劃模型中整體剔除出去，得到剔除整數(shù)約束決策變量的線性規(guī)劃模型；步驟4、采用單純形法求解無整數(shù)約束的線性規(guī)劃模型，得到一組非整數(shù)解；步驟5、將整數(shù)解與非整數(shù)解合到一起生成混合整數(shù)線性規(guī)劃模型的近似最優(yōu)解。

與現(xiàn)有技術(shù)相比，本發(fā)明實(shí)施例中提出的兩階段求解方法能快速完成對混合整數(shù)線性規(guī)劃模型的求解并輸出結(jié)果，且輸出結(jié)果精確，求解步驟簡單，降低計算時間成本和存儲空間成本，提高計算效率。

附圖說明

圖1是根據(jù)本發(fā)明一個實(shí)施例提供的混合整數(shù)線性規(guī)劃模型的求解方法流程圖。

具體實(shí)施方式

為了使本發(fā)明的目的、技術(shù)方案及優(yōu)點(diǎn)更加清楚明白，以下結(jié)合附圖，對本發(fā)明進(jìn)一步詳細(xì)說明。應(yīng)當(dāng)理解，此處所描述的具體實(shí)施例僅僅用以解釋本發(fā)明，并不用于限定本發(fā)明。

根據(jù)本發(fā)明一個實(shí)施例，如圖1所示，提供一種混合整數(shù)線性規(guī)劃模型的求解方法，包括：

S1、采用單純形法求解無整數(shù)約束的線性規(guī)劃模型，得到一組無整數(shù)約束最優(yōu)解；

S2、將整數(shù)約束決策變量的解從所求得的最優(yōu)解中分離出來，并直接賦以與所求得的最優(yōu)解最接近的整數(shù)值；

S3、將整數(shù)約束決策變量及其約束從混合整數(shù)線性規(guī)劃模型中整體剔除出去，得到剔除整數(shù)約束決策變量的線性規(guī)劃模型；

根據(jù)本發(fā)明一個實(shí)施例，該線性規(guī)劃模型可以用于煤炭采購計劃；

S4、采用單純形法求解無整數(shù)約束的線性規(guī)劃模型，得到一組非整數(shù)解；

S5、將整數(shù)解與非整數(shù)解合到一起生成混合整數(shù)線性規(guī)劃模型的近似最優(yōu)解。

根據(jù)本發(fā)明另一個實(shí)施例，步驟S1和/或S4進(jìn)一步包括：

S11、把線性規(guī)劃問題的約束方程組表達(dá)成典范型方程組，找出基本可行解作為初始基本可行解；

若基本可行解不存在，即約束條件有矛盾，則問題無解；

若基本可行解存在，從初始基本可行解作為起點(diǎn)，根據(jù)最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，找出目標(biāo)函數(shù)值更優(yōu)的另一基本可行解；

S12、按步驟(S11)進(jìn)行迭代，直到對應(yīng)檢驗(yàn)數(shù)滿足最優(yōu)性條件(這時目標(biāo)函數(shù)值不能再改善)，即得到問題的最優(yōu)解；若迭代過程中發(fā)現(xiàn)問題的目標(biāo)函數(shù)值無界，則終止迭代。

根據(jù)本發(fā)明另一個實(shí)施例，步驟S2進(jìn)一步包括：

S21、將步驟S1中計算出的一組決策變量最優(yōu)解進(jìn)行唯一編號；

S22、將整數(shù)約束的決策變量從最優(yōu)解中分離出來；

S23、對于整數(shù)約束的決策變量進(jìn)行取整操作。

根據(jù)本發(fā)明另一個實(shí)施例，步驟S22進(jìn)一步包括：

S221、整數(shù)約束的決策變量可解釋為要求該決策變量取值為整數(shù)，或取值為某個固定常數(shù)的整數(shù)倍。

根據(jù)本發(fā)明另一個實(shí)施例，步驟S23進(jìn)一步包括：

S231、將變量值取為大于等于初始值的最小整數(shù)；

S232、判斷如果某個整數(shù)值大于與之對應(yīng)的決策變量的上限，則將該整數(shù)值減1。