在前面討論的線(xiàn)性規(guī)劃問(wèn)題中，最優(yōu)解可能是整數(shù)，也可能不是整數(shù)，但對(duì)于某些實(shí)際問(wèn)題，要求答案必須是整數(shù)。如所求的解是安排上班的人數(shù)，按某個(gè)方案剪裁鋼材的根數(shù)，生產(chǎn)機(jī)器的臺(tái)數(shù)等。
整數(shù)規(guī)劃是一類(lèi)要求變量取整數(shù)值的數(shù)學(xué)規(guī)劃。

文章目錄

• • 1 整數(shù)規(guī)劃問(wèn)題的提出
  • 2 整數(shù)規(guī)劃與分支定界法
  • 3 整數(shù)規(guī)劃與割平面法
  • 4 指派問(wèn)題

1 整數(shù)規(guī)劃問(wèn)題的提出

所謂整數(shù)規(guī)劃（Integer Programming，簡(jiǎn)稱(chēng)IP）：
決策變量要求取整數(shù)的線(xiàn)性規(guī)劃

數(shù)學(xué)模型：

整數(shù)規(guī)劃問(wèn)題可以分為下列幾種類(lèi)型：
1 . 純（全）整數(shù)線(xiàn)性規(guī)劃（Pure Integer Linear Programming):指全部決策變量都必須取整數(shù)的整數(shù)線(xiàn)性規(guī)劃。
2 . 混合整數(shù)線(xiàn)性規(guī)劃 （Mixed Integer Linear Programming): 指決策變量中有一部分必須取整數(shù)，另一部分可以不取整數(shù)值的整數(shù)線(xiàn)性規(guī)劃。
3 . 0-1整數(shù)規(guī)劃（0-1 Integer Linear Programming）：指決策變量只能取值0、1的整數(shù)線(xiàn)性規(guī)劃。

2 整數(shù)規(guī)劃與分支定界法

分支定界法可用于解純整數(shù)或混合的整數(shù)線(xiàn)性規(guī)劃問(wèn)題
混合整數(shù)規(guī)劃問(wèn)題一般有無(wú)窮多個(gè)可行解。即使是純整數(shù)規(guī)劃問(wèn)題，隨著問(wèn)題規(guī)模的擴(kuò)大，其可行解的數(shù)目也將急劇增加。因此通過(guò)枚舉全部可行解，并從中篩選出最優(yōu)解的算法沒(méi)有實(shí)際應(yīng)用價(jià)值。
分支定界法是一種隱枚舉法（implicit enumeration)或部分枚舉法，是枚舉法基礎(chǔ)上的改進(jìn)。
分支定界法的關(guān)鍵是分支和定界

原問(wèn)題的松馳問(wèn)題：任何整數(shù)規(guī)劃（IP），凡放棄某些約束條件（如整數(shù)要求）后，所得到的問(wèn)題（P） 稱(chēng)為（IP）的松馳問(wèn)題。

分支定界法的步驟：
一般求解對(duì)應(yīng)的松馳問(wèn)題，可能會(huì)出現(xiàn)下面幾種情況：
若所得的最優(yōu)解的各分量恰好是整數(shù)，則這個(gè)解也是原整數(shù)規(guī)劃的最優(yōu)解，計(jì)算結(jié)束。
若松馳問(wèn)題無(wú)可行解，則原整數(shù)規(guī)劃問(wèn)題也無(wú)可行解，計(jì)算結(jié)束
若松馳問(wèn)題有最優(yōu)解，但其各分量不全是整數(shù)，則這個(gè)解不是原整數(shù)規(guī)劃的最優(yōu)解，轉(zhuǎn)下一步。

從不滿(mǎn)足整數(shù)條件的基變量中任選 一個(gè)x_l 進(jìn)行分枝，它必須滿(mǎn)足x_l ≤[x_l ] 或x_l ≥[x_l ] +1中的一個(gè)，把這兩個(gè)約束條件加進(jìn)原問(wèn)題中，形成兩個(gè)互不相容的子問(wèn)題（兩分法）。
定界：把滿(mǎn)足整數(shù)條件各分枝的最優(yōu)目標(biāo)函數(shù)值作為上（下）界，用它來(lái)判斷分枝是保留還是剪枝。
剪枝：把那些子問(wèn)題的最優(yōu)值與界值比較，凡不優(yōu)或不能更優(yōu)的分枝全剪掉，直到每個(gè)分枝都查清為止。

“分支”為整數(shù)規(guī)劃最優(yōu)解的出現(xiàn)創(chuàng)造了條件，而“定界”則可以提高搜索的效率。

例1. 用分枝定界法求解：

用單純形法可解得相應(yīng)的松馳問(wèn)題的最優(yōu)解為（6/5，21/10）
Z=111/10為各分枝的上界。

3 整數(shù)規(guī)劃與割平面法

此方法的基礎(chǔ)仍然是用解線(xiàn)性規(guī)劃的方法去解整數(shù)規(guī)劃問(wèn)題。
思路： 先不考慮變量x_i是整數(shù)這一條件，但增加線(xiàn)性約束條件（幾何術(shù)語(yǔ)：割平面）使得由原可行域中切割掉一部分（此部分只包含非整數(shù)解，沒(méi)有切割掉任何整數(shù)可行解），使切割后最終得到這樣的可行域，它的一個(gè)有整數(shù)坐標(biāo)的極點(diǎn)恰好是問(wèn)題的最優(yōu)解。
該方法是1958年R.E.Gormory首先提出的，故又稱(chēng)為Gormory割平面法
割平面法的關(guān)鍵： 如何找到適當(dāng)?shù)母钇矫?#xff1f;
構(gòu)造割平面約束的方法很多，下面只介紹一種（它可以從相應(yīng)線(xiàn)性規(guī)劃的最終單純形表中直接產(chǎn)生）

先通過(guò)舉一簡(jiǎn)單的例子入手，介紹算法的過(guò)程

將上推導(dǎo)對(duì)應(yīng)一般情況，可得：
思路：
用割平面法解整數(shù)規(guī)劃時(shí)，若其松弛問(wèn)題的最優(yōu)解x不滿(mǎn)足整數(shù)條件，則從x的非整分量中選取一個(gè)，用以構(gòu)造一個(gè)線(xiàn)性約束條
件，將其加入原松弛問(wèn)題中，形成一個(gè)新的線(xiàn)性規(guī)劃之后求解。
若新的最優(yōu)解滿(mǎn)足整數(shù)條件，則它就是整數(shù)規(guī)劃的最優(yōu)解，否則重復(fù)上述步驟，直到獲得最優(yōu)解為止。
為獲得整數(shù)最優(yōu)解，每次增加的線(xiàn)性約束條件應(yīng)滿(mǎn)足2個(gè)基本性質(zhì)
（1）已獲得的不符合整數(shù)要求的線(xiàn)性規(guī)劃最優(yōu)解不滿(mǎn)足該線(xiàn)性約束條件，從而不可能在以后的解中再出現(xiàn)。
（2）凡整數(shù)可行解均滿(mǎn)足該線(xiàn)性約束條件，故整數(shù)最優(yōu)解始終被保留在每次形成的線(xiàn)性規(guī)劃可行域中。

4 指派問(wèn)題

一類(lèi)特殊的0-1規(guī)劃問(wèn)題：將m項(xiàng)工作分派給n個(gè)人去做，既發(fā)揮各人特長(zhǎng)又使總效率最高。
又如：某單位需完成n項(xiàng)任務(wù)，恰好有n個(gè)人可承擔(dān)這些任務(wù)。由于各人的專(zhuān)長(zhǎng)不同，故各人完成任務(wù)的效率（如時(shí)間等）不同。問(wèn)題需解決確定指派哪個(gè)人完成哪項(xiàng)任務(wù)，使完成n項(xiàng)任務(wù)的總效率最高等。
上述類(lèi)型問(wèn)題稱(chēng)為指派問(wèn)題（assignment problem)

指派問(wèn)題是0-1規(guī)劃及運(yùn)輸問(wèn)題的特例，可用前已學(xué)方法求解，但不夠方便。
（下介紹一針對(duì)指派問(wèn)題特點(diǎn)的簡(jiǎn)便求解方法。)
指派問(wèn)題的標(biāo)準(zhǔn)形式為：
即：目標(biāo)求最小，且系數(shù)矩陣為方陣（每項(xiàng)工作只能由1個(gè)人做，每個(gè)人只能做一項(xiàng)工作）


從中即可說(shuō)明，系數(shù)矩陣中元素本身的大小不決定最優(yōu)解，而元素之間的差值發(fā)生則可能改變最優(yōu)解
其中k為一個(gè)常數(shù)，故當(dāng)z達(dá)最大值時(shí)，z’也達(dá)到最大值

(完)

總結(jié)

以上是生活随笔為你收集整理的运筹学笔记 整数规划的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。