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

在審

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

1.一種混合整數線性規(guī)劃模型的求解方法，包括：

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

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

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

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

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

2.根據權利要求1所述的混合整數線性規(guī)劃模型的求解方法，其中，步驟1進一步包括：

步驟1.1、把線性規(guī)劃問題的約束方程組表達成典范方程組，求解基本可行解作為初始基本可行解；

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

若基本可行解存在，從初始基本可行解作為起點，根據最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，求解目標函數值更優(yōu)的另一基本可行解；

步驟1.2、按步驟1.1進行迭代，直到對應檢驗數滿足最優(yōu)性條件，即得到問題的最優(yōu)解；若迭代過程中發(fā)現問題的目標函數值無界，則終止迭代。

3.根據權利要求1所述的混合整數線性規(guī)劃模型的求解方法，其中，步驟4進一步包括：

步驟4.1、把線性規(guī)劃問題的約束方程組表達成典范方程組，求解基本可行解作為初始基本可行解；

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

若基本可行解存在，從初始基本可行解作為起點，根據最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，求解目標函數值更優(yōu)的另一基本可行解；

步驟4.2、按步驟4.1進行迭代，直到對應檢驗數滿足最優(yōu)性條件，即得到問題的最優(yōu)解；若迭代過程中發(fā)現問題的目標函數值無界，則終止迭代。

4.根據權利要求1所述的混合整數線性規(guī)劃模型的求解方法，其中，步驟2進一步包括：

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

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

步驟2.3、對于整數約束的決策變量進行取整操作。

5.根據權利要求4所述的混合整數線性規(guī)劃模型的求解方法，其中，步驟2.3進一步包括：

將變量值取為大于等于初始值的最小整數；

判斷如果某個整數值大于與之對應的決策變量的上限，則將該整數值減1。

6.根據權利要求1所述的混合整數線性規(guī)劃模型的求解方法，其中，步驟3進一步包括：

步驟3.1、從目標函數中減去整數約束決策變量的目標值；

步驟3.2、從約束條件中減去整數約束決策變量的約束；

步驟3.3、整理去掉整數約束決策變量之后的模型，得到剔除整數約束決策變量的線性規(guī)劃模型。

7.根據權利要求6所述的混合整數線性規(guī)劃模型的求解方法，其中，步驟3.2進一步包括：

從采購量約束條件中減去整數約束決策變量的采購量；

從煤炭熱值約束條件中減去整數約束決策變量的總熱值；

從煤炭Vdaf約束條件中減去整數約束決策變量的總Vdaf；

從煤炭Std約束條件中減去整數約束決策變量的總Std；

從采購資金約束條件中減去整數約束決策變量的總采購資金；

從供應量約束條件中減去整數約束決策變量的總供應量。

8.根據權利要求1所述的混合整數線性規(guī)劃模型的求解方法，其中，步驟5進一步包括：

按照步驟2.1給出的決策變量編號將整數解和非整數解進行排序；

排序后的解即為混合線性規(guī)劃模型的完整解。