我愛學(xué)習(xí)大二下課程運籌學(xué)or03整數(shù)

運籌帷幄之中決勝千里之外運籌學(xué)課件整數(shù)線性規(guī)劃IntegerLinearProgramming整數(shù)線性規(guī)劃

IntegerProgramming整數(shù)線性規(guī)劃問題的提出割平面解法分支定界解法

0-1型整數(shù)線性規(guī)劃指派問題

3.1.1模型及整數(shù)規(guī)劃的實例例1某廠擬用集裝箱托運甲乙兩種貨物，每箱的體積、重量、可獲利潤以及托運所受限制如表所示。問兩種貨物各托運多少箱，可使獲得利潤為最大?3.1整數(shù)規(guī)劃問題

設(shè)x1，x2分別為甲、乙兩種貨物的托運箱數(shù)(當(dāng)然都是非負(fù)整數(shù))。這是一個(純)整數(shù)線性規(guī)劃問題，用數(shù)學(xué)式可表示為：

maxz=20x1+10x2①5x1+4x2≤24②2x1+5x2≤13③x1，x2≥0④x1，x2整數(shù)⑤整數(shù)線性規(guī)劃問題的分類全整數(shù)線性規(guī)劃混合整數(shù)線性規(guī)劃0-1整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃問題的一般形式3.1.2解的特點整數(shù)規(guī)劃問題去掉整數(shù)約束條件后得到的線性規(guī)劃稱為原整數(shù)規(guī)劃的松弛問題。為了滿足整數(shù)解的要求，似乎只要把松弛問題的帶有分?jǐn)?shù)或小數(shù)的解經(jīng)過“舍入化整”就可以了。但這常常是不行的，因為化整后不見得是可行解；或雖是可行解，但不一定是最優(yōu)解。當(dāng)放棄整數(shù)約束時得到的線性規(guī)劃稱為整數(shù)規(guī)劃的松弛問題。整數(shù)規(guī)劃的可行域是松弛問題的可行域，反之不成立。

例1中，對于松弛問題，最優(yōu)解為:x1=4.8，x2=0，maxz=96maxz=20x1+10x2①5x1+4x2≤24②2x1+5x2≤13③x1，x2≥0④

如將(x1=4.8，x2=0)湊整為(x1=5，x2=0)，這樣就破壞了條件②，它不是可行解；如將(x1=4.8，x2=0)舍去尾數(shù)0.8，變?yōu)?x1=4，x2=0)，是可行解，但不是最優(yōu)解，因為此時z=80.

但當(dāng)x1=4，x2=1(這也是可行解)時，z=90。3.2全整數(shù)規(guī)劃的求解

---Gomory割平面方法

割平面解法的思路是：首先不考慮變量是整數(shù)，仍然是用解線性規(guī)劃的方法去解整數(shù)線性規(guī)劃問題，若得到非整數(shù)的最優(yōu)解，然后增加能割去非整數(shù)解的線性約束條件(或稱為割平面)使得由原可行域中切割掉一部分，這部分只包含非整數(shù)解，但沒有切割掉任何整數(shù)可行解。

例3-5用割平面法求解整數(shù)規(guī)劃問題目標(biāo)函數(shù)maxz=x1+x2①

約束條件：

-x1+x2≤1②3x1+x2≤4③(3-5)x1，x2≥0④x1，x2

整數(shù)⑤相應(yīng)的松弛問題的最優(yōu)解：

x1=3/4，x2=7/4，maxz=10/4

它就是圖中域R的極點A，但不合于整數(shù)條件。現(xiàn)設(shè)想，如能找到像CD那樣的直線去切割域R，去掉三角形域ACD，那么具有整數(shù)坐標(biāo)的C點(1，1)就是域R′的一個極點，

如在域R′上求解①～④，而得到的最優(yōu)解又恰巧在C點就得到原問題的整數(shù)解，所以解法的關(guān)鍵就是怎樣構(gòu)造一個這樣的“割平面”CD，盡管它可能不是唯一的，也可能不是一步能求到的。對于松弛問題，增加非負(fù)松弛變量x3、x4，使兩式變成等式約束：-x1+x2+x3=1⑥3x1+x2+x4=4⑦最終表中，最優(yōu)解：x1=3/4，x2=7/4，x3=x4=0，maxz=5/2

不能滿足整數(shù)最優(yōu)解的要求。為此考慮將帶有分?jǐn)?shù)的最優(yōu)解的可行域中分?jǐn)?shù)部分割去，再求最優(yōu)解。就可以得到整數(shù)的最優(yōu)解。可從最終計算表中得到非整數(shù)變量對應(yīng)的關(guān)系式：為了得到整數(shù)最優(yōu)解。將上式變量的系數(shù)和常數(shù)項都分解成整數(shù)和非負(fù)真分?jǐn)?shù)兩部分之和(1+0)x1+(-1+3/4)x3+1/4x4=0+3/4x2+(3/4)x3+(1/4)x4=1+3/4然后將整數(shù)部分與分?jǐn)?shù)部分分開，移到等式左右兩邊，得：

得到一個割平面約束，將它作為增加約束條件。

引入松弛變量x5，得到等式即割平面方程-3x3-x4+x5=-3

將這新的約束方程加到最終計算表

這就是(x1，x2)平面內(nèi)形成新的可行域，即包括平行于x1軸的直線x2=1和這直線下的可行區(qū)域，整數(shù)點也在其中，沒有切割掉。求一個切割方程的步驟（1）令xi是相應(yīng)線性規(guī)劃最優(yōu)解中為分?jǐn)?shù)值的一個基變量，由單純形表的最終表得到其中k∈K(K指構(gòu)成非基變量號碼的集合)（2）將bi和αik都分解成整數(shù)部分N與非負(fù)真分?jǐn)?shù)f之和，即

bi=Ni+fi，其中0＜fi＜1αik=Nik+fik，其中0≤fik＜1

而N表示不超過b的最大整數(shù)。（3）代入（3-20）分析，得到割平面約束加上松弛變量化為割平面方程3.3混合整數(shù)規(guī)劃的求解

---分枝定界方法分枝：當(dāng)不符合整數(shù)要求時，構(gòu)造兩個約束條件：加入松弛問題分別形成兩個子問題（分枝）定界：當(dāng)子問題獲得整數(shù)規(guī)劃的一個可行解，則它的目標(biāo)函數(shù)值就構(gòu)成一個界限例132X254X1231S解S得：132X254X1231S2對S分枝：構(gòu)造約束：和形成分枝問題S1和S2，得解B和CS1SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9132X254X1231S2對S1分枝：構(gòu)造約束：和形成分枝問題S11和S12，得解DS12S11無可行解SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11無可行解S12D:x1=33/14,x2=2Z=61/14132X254X1231S2對S12分枝：構(gòu)造約束：和形成分枝問題S121和S122，得解E和FS121S122SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11無可行解S12D:x1=33/14,x2=2Z=61/14S122F:x1=2,x2=2Z=4S121E:x1=3,x2=1Z=4從以上解題過程可得到，用分支定界法求解整數(shù)線性規(guī)劃(最大化)問題的步驟為：ILP稱為問題A，相應(yīng)的松弛問題稱為問題B。(1)解問題B，可能得到以下情況之一。①B沒有可行解，這時A也沒有可行解，則停止。②B有最優(yōu)解，并符合問題A的整數(shù)條件，B的最優(yōu)解即為A的最優(yōu)解，則停止。③B有最優(yōu)解，但不符合問題A的整數(shù)條件，它的目標(biāo)函數(shù)值為z*的上界

第一步：分支，在B的最優(yōu)解中任選一個不符合整數(shù)條件的變量xj，其值為bj，以［bj］表示小于bj的最大整數(shù)。構(gòu)造兩個約束條件

xj≤［bj］和xj≥［bj］+1

將這兩個約束條件，分別加入問題B，求兩個后繼規(guī)劃問題B1和B2。不考慮整數(shù)條件求解這兩個后繼問題。定界，以每個后繼問題為一分支標(biāo)明求解的結(jié)果，與其他問題的解的結(jié)果中，找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界。從已符合整數(shù)條件的各分支中，找出目標(biāo)函數(shù)值為最大者作為新的下界，若無可行解，

第二步：比較與剪枝各分支的最優(yōu)目標(biāo)函數(shù)中若有小于下界者，則剪掉這支(用打×表示)，即以后不再考慮了。若大于下界，且不符合整數(shù)條件，則重復(fù)第一步驟。一直到最后得到z*為止，得最優(yōu)整數(shù)解xj*，j=1，…，n。

用分支定界法可解純整數(shù)線性規(guī)劃問題和混合整數(shù)線性規(guī)劃問題。它比窮舉法優(yōu)越。因為它僅在一部分可行解的整數(shù)解中尋求最優(yōu)解，計算量比窮舉法小。若變量數(shù)目很大，其計算工作量也是相當(dāng)可觀的。3.40-1整數(shù)規(guī)劃變量只能取0或1的整數(shù)線性規(guī)劃3.4.10-1規(guī)劃的應(yīng)用項目投資預(yù)算變量假設(shè):模型:0-1規(guī)劃的應(yīng)用-工廠-銷售點配置問題生產(chǎn)廠顧客需求銷售點45DCBA7IIIII213I工廠-銷售點配置問題問題:為使經(jīng)營成本最低,應(yīng)開設(shè)那些工廠及銷售點?固定成本問題高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機器設(shè)備，制造一個容器所需的各種資源的數(shù)量如表所示。不考慮固定費用，每種容器售出一只所得的利潤分別為4萬元、5萬元、6萬元，可使用的金屬板有500噸，勞動力有300人/月，機器有100臺/月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費用：小號是l00萬元，中號為150萬元，大號為200萬元?，F(xiàn)在要制定一個生產(chǎn)計劃，使獲得的利潤為最大。

解：這是一個整數(shù)規(guī)劃的問題。設(shè)x1，x2，x3分別為小號容器、中號容器和大號容器的生產(chǎn)數(shù)量。各種容器的固定費用只有在生產(chǎn)該種容器時才投入，為了說明固定費用的這種性質(zhì)，設(shè)yi=1(當(dāng)生產(chǎn)第i種容器,即xi＞0時)或0（當(dāng)不生產(chǎn)第i種容器即xi=0時）。引入約束xi≤Myi，i=1，2，3，M充分大，以保證當(dāng)yi=0時，xi=0。

這樣我們可建立如下的數(shù)學(xué)模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300

x1+2x2+3x3≤100xi≤Myi，i=1，2，3，M充分大

xj≥0yj

為0--1變量，i=1,2,3

解0-1型整數(shù)線性規(guī)劃最容易想到的方法，和一般整數(shù)線性規(guī)劃的情形一樣，就是窮舉法，即檢查變量取值為0或1的每一種組合，比較目標(biāo)函數(shù)值以求得最優(yōu)解，這就需要檢查變量取值的2n個組合。對于變量個數(shù)n較大(例如n＞10)，這幾乎是不可能的。因此常設(shè)計一些方法，只檢查變量取值的組合的一部分，就能求到問題的最優(yōu)解。這樣的方法稱為隱枚舉法(implicitenumeration)，分枝定界法也是一種隱枚舉法。當(dāng)然，對有些問題隱枚舉法并不適用，所以有時窮舉法還是必要的。3.4.20-1規(guī)劃的解法最優(yōu)解（x1,x2,x3)=(1,0,1)