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

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

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

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

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

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

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

例1中，對(duì)于松弛問(wèn)題，最優(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)解，因?yàn)榇藭r(shí)z=80.

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

---Gomory割平面方法

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

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

約束條件：

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

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

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

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

如在域R′上求解①～④，而得到的最優(yōu)解又恰巧在C點(diǎn)就得到原問(wèn)題的整數(shù)解，所以解法的關(guān)鍵就是怎樣構(gòu)造一個(gè)這樣的“割平面”CD，盡管它可能不是唯一的，也可能不是一步能求到的。對(duì)于松弛問(wèn)題，增加非負(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)解?？蓮淖罱K計(jì)算表中得到非整數(shù)變量對(duì)應(yīng)的關(guān)系式：為了得到整數(shù)最優(yōu)解。將上式變量的系數(shù)和常數(shù)項(xiàng)都分解成整數(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ù)部分分開(kāi)，移到等式左右兩邊，得：

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

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

將這新的約束方程加到最終計(jì)算表

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

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

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

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

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

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

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

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

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

解：這是一個(gè)整數(shù)規(guī)劃的問(wèn)題。設(shè)x1，x2，x3分別為小號(hào)容器、中號(hào)容器和大號(hào)容器的生產(chǎn)數(shù)量。各種容器的固定費(fèi)用只有在生產(chǎn)該種容器時(shí)才投入，為了說(shuō)明固定費(fèi)用的這種性質(zhì)，設(shè)yi=1(當(dāng)生產(chǎn)第i種容器,即xi＞0時(shí))或0（當(dāng)不生產(chǎn)第i種容器即xi=0時(shí)）。引入約束xi≤Myi，i=1，2，3，M充分大，以保證當(dāng)yi=0時(shí)，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個(gè)組合。對(duì)于變量個(gè)數(shù)n較大(例如n＞10)，這幾乎是不可能的。因此常設(shè)計(jì)一些方法，只檢查變量取值的組合的一部分，就能求到問(wèn)題的最優(yōu)解。這樣的方法稱為隱枚舉法(implicitenumeration)，分枝定界法也是一種隱枚舉法。當(dāng)然，對(duì)有些問(wèn)題隱枚舉法并不適用，所以有時(shí)窮舉法還是必要的。3.4.20-1規(guī)劃的解法最優(yōu)解（x1,x2,x3)=(1,0,1)