整數(shù)規(guī)劃演示教案

整數(shù)規(guī)劃第1節(jié)整數(shù)規(guī)劃問題的特點及其作用第2節(jié)分支定界方法第3節(jié)割平面方法第4節(jié)0-1規(guī)劃第5節(jié)指派（分配）問題整數(shù)規(guī)劃（1）§1.整數(shù)規(guī)劃問題的提出整數(shù)規(guī)劃:若一個規(guī)劃的最優(yōu)解要求部分或全部決策變量是整數(shù)的問題純整數(shù)規(guī)劃:整數(shù)規(guī)劃中如果所有的變量都為非負(fù)整數(shù),(PureIntegerProgramming)(IntegerProgramming),簡稱IP或稱為全整數(shù)規(guī)劃(AllIntegerProgramming)混合整數(shù)規(guī)劃:若整數(shù)規(guī)劃中僅一部分變量限制為整數(shù),

則稱為混合整數(shù)規(guī)劃(MixedIntegerProgramming)整數(shù)規(guī)劃（2）0--1規(guī)劃：若整數(shù)規(guī)劃中的變量都僅限制為0或1,則稱為0--1規(guī)劃整數(shù)線性規(guī)劃：若整數(shù)規(guī)劃問題的目標(biāo)函數(shù)和約束條件都是線性的，則稱該整數(shù)規(guī)劃是整數(shù)線性規(guī)劃本章中，我們討論的主要對象是整數(shù)線性規(guī)劃，下面的討論中將省略線性二字整數(shù)規(guī)劃（3）問:兩種貨物各托運多少箱,可使獲利最大?則其數(shù)學(xué)模型設(shè)x1,x2分別為托運甲、乙兩種貨物的數(shù)量例1.某廠擬用集裝箱托運甲乙兩種貨物,每箱的體積、重量、可獲利及托運限制如下表:貨物體積重量利潤

(每箱立方米)(每箱百斤)(每箱百元)

甲5220

乙4510托運限制2413

它是一個純整數(shù)規(guī)劃,整數(shù)規(guī)劃（4）它與線性規(guī)劃的區(qū)別僅在于要求x1,x2為整數(shù)的條件則是否可以把所得的非整數(shù)的最優(yōu)解經(jīng)過”化整”來得到整數(shù)規(guī)劃的最優(yōu)解呢?易求出最優(yōu)解為x1=4.8x2=0z*=96若不考慮整數(shù)條件,則變成一個線性規(guī)劃問題但它不是原整數(shù)規(guī)劃的最優(yōu)解.若通過四舍五入的辦法，得解為x1=5x2=0但它不是可行解故這種辦法不可取的若通過取整的辦法，得解為x1=4x2=0,z=80但有解x1=4x2=1,z=90整數(shù)規(guī)劃的常見解法：整數(shù)規(guī)劃（5）二、割平面法：常用于求解純整數(shù)規(guī)劃問題一、分支定界法：可用于求解純整數(shù)或混合整數(shù)規(guī)劃問題；解法的基本思想：(1)通過求解線性規(guī)劃問題來求得整數(shù)線性規(guī)劃問題的最優(yōu)解；(2)在使沒有整數(shù)約束的可行域以“割掉非整數(shù)解，保留需要的所有的整數(shù)可行解”的原則來壓縮可行域?！?.整數(shù)規(guī)劃的解法一通過例子來說明分支定界解法的步驟分支定界解法解:

先不考慮條件(5)例即解相應(yīng)的線性規(guī)劃(1)-----(4)的最優(yōu)解分支定界解法(1)稱為原問題的松馳問題用單純形法解上述問題得x1=4.809,x2=1.817，z=355.89又由于當(dāng)x1=x2=0時，是原規(guī)劃的一個整數(shù)可行解，而此時z＝0。因此，原問題的最優(yōu)值滿足：

0≤z*≤355這就是分支定界解法中的定界含義。分支定界解法(2)9x1+7x2=567x1+20x2=70x22108642ACB0x1z＝40x1+90x2由于最優(yōu)解是非整數(shù)，首先注意其中一個非整數(shù)變量(可任選),例如x1=4.809，我們可認(rèn)為整數(shù)最優(yōu)解x1是x14或x15,而在4和5之間是不合整數(shù)條件的,于是把原問題分解成兩支,各支都增加了約束條件:即區(qū)域也分成兩塊R1和R2最優(yōu)解：x1=4.809,x2=1.817，z=355.89R2R1這就是分支定界解法中的分支含義分支定界解法(3)9x1+7x2=567x1+20x2=70x22108642ACB0x1z＝40x1+90x2R2R1這就是分支定界解法中的分支含義分支定界解法(4)問題1有x1=4,x2=2.1z1=349.0問題2有x1=5,x2=1.571z2=341.39由于沒有得到整數(shù)最優(yōu)解,繼續(xù)分解問題(1)和問題(2)0≤z*≤349分支定界解法(5)先分解問題(1)問題(3)有x1=4,x2=2z3=340問題(4)有x1=1.428,x2=3z4=327.12問題1有x1=4,x2=2.1z1=349.0340≤z*≤341分支定界解法(6)因為問題（3）的最優(yōu)解是整數(shù)解，最優(yōu)值為340但我們可以肯定,原問題的最優(yōu)解不會在問題(4)中,那么該整數(shù)解是否為原問題的最優(yōu)解？對問題(2)進(jìn)行分解,得問題(5)和問題(6)：所以問題(4)不必去分解了.原問題的最優(yōu)解可能在問題(2)中,因為問題(2)的最優(yōu)值大于340這是因為,問題(4)的最優(yōu)值小于問題(3)的最優(yōu)值分支定界解法(7)

問題(5)有x1=5.44,x2=1,z5=308問題(6)

無可行解原問題的最優(yōu)解不會在問題(5)和(6)中,這是因為問題(5)的最優(yōu)值小于340,(6)沒有可行解原問題的最優(yōu)解:x1=4,x2=2,最優(yōu)值:z*=340原問題的松馳問題：x1=4.809,x2=1.817，z=355.89分支定界解法(8)

因此，原問題的最優(yōu)解:x1=4,x2=2,最優(yōu)值:z*=340問題1

z1=349.0x1=4,x2=2.1問題2

z2=341.39

x1=5,x2=1.571問題3x1=4,x2=2z3=340問題4x1=1.428x2=3z4=327.12問題5x1=5.44x2=1z5=308問題6

無可行解(2)用單純形法解(IPL);分支定界解法的步驟(3)若求得(IPL)的最優(yōu)解,

(1)稱原整數(shù)規(guī)劃問題為(IP)稱相應(yīng)的線性規(guī)劃(即不考慮整數(shù)條件)為松馳問題(IPL)若(IPL)沒有可行解,則(IP)也沒可行解.檢查它是否符合整數(shù)條件,

若符合整數(shù)條件,它就是問題(IP)的最優(yōu)解;否則轉(zhuǎn)(4)(4)在(IPL)的解中,任選一個不符整數(shù)條件的變量xj,(i)xjbj

,(ii)xjbj

+1不考慮整數(shù)條件,分別求解這兩個后繼問題(5)在現(xiàn)有的且還沒有分解后繼問題的各可行問題中,選目標(biāo)函數(shù)為最優(yōu)的問題,重新稱這個問題為(IPL),轉(zhuǎn)(3)重復(fù)進(jìn)行若xj=bj非整;

作兩個后繼問題,它們是對(IPL)分別各增加一個約束條件:

分支定界解法的注釋(1)在用單純形法繼續(xù)求解后繼問題時，可借助上一級終表添加約束條件進(jìn)一步計算，借助單純形法或?qū)ε紗渭冃畏ㄟM(jìn)行計算；(2)對分支中最優(yōu)值較大者先分支，得到整數(shù)解的后繼問題不必繼續(xù)分支；對最優(yōu)值低于目前下界的后繼問題不必繼續(xù)分支；無可行解的后繼問題不必繼續(xù)分支；當(dāng)所有后繼問題都無法繼續(xù)分支時，最優(yōu)解才得到?！?.整數(shù)規(guī)劃的解法二考慮純整數(shù)規(guī)劃問題：設(shè)其中aij(i=1,2,…,m;j=1,2,…,n)和bi(i=1,2,…,m)皆為整數(shù)（若不為整數(shù)，可乘上一個倍數(shù)化為整數(shù)）割平面法：(2)用單純形法解(IPL);§3.整數(shù)規(guī)劃的解法二(3)若求得(IPL)的最優(yōu)解,

1.(1)稱原整數(shù)規(guī)劃問題為(IP)稱相應(yīng)的線性規(guī)劃(即不考慮整數(shù)條件)為松馳問題(IPL)若(IPL)沒有可行解,則(IP)也沒可行解.檢查它是否符合整數(shù)條件,

若符合整數(shù)條件,它就是問題(IP)的最優(yōu)解;否則轉(zhuǎn)2割平面法的步驟：2.(1)令xi是(IPL)的最優(yōu)解中取值為非整的一個基變量，由單純形終表可得：割平面法的步驟（2）(2)將和αij都分解成整數(shù)部分N和非整真分?jǐn)?shù)f之和，即：將(2),(3)代入(1)整理，移項，得(3)考慮整數(shù)約束，(4)式由左邊看是整數(shù)，且0<fi<1,所以有：割平面方程(4)用割平面方程去替代整數(shù)約束求解，具體操作為：將(5)式作為新增加的約束條件，引入松弛變量xn+1,利用對偶單純形法求解；割平面法的步驟（3）(5)若求得整數(shù)最優(yōu)解，停止計算；否則，仍有非整分量，從2.(1)開始重復(fù)，繼續(xù)添加線性約束條件，相當(dāng)于在已經(jīng)割過的可行域上進(jìn)一步再割，直到達(dá)到最優(yōu)。注1：割平面方程真正進(jìn)行了切割，至少把非整數(shù)最優(yōu)解這一點割掉了；注2：割平面方程沒有割掉任何整數(shù)可行解；注3：當(dāng)(IPL)最優(yōu)解中存在多個非整基變量時，選擇分?jǐn)?shù)部分為最大的非整基分量所在行構(gòu)造割平面方程，往往可以減少“切割”次數(shù)。割平面法例子：例：用割平面法求解純整數(shù)規(guī)劃：解：求解原問題的松弛問題,前兩個不等式中引入非負(fù)松弛變量x3、x4，使兩式變成等式約束：-x1+x2+x3=13x1+x2+x4=4用單純形法求解，得：割平面法例子（2）XBbx1x2x3x4

初表x3x414-13111001-z01100終表x1x23/47/41001-1/43/41/41/5-z-5/200-1/2-1/2由單純形終表中第一行產(chǎn)生割平面方程：松弛問題的最優(yōu)解為：x1=3/4,x2=7/4;割平面法例子（3）現(xiàn)考慮整數(shù)約束，得割平面方程為：將它作為新增的約束條件，再解其對應(yīng)的松弛問題，引入松弛變量x5，得到：將原終表中加入一行一列，得：割平面法例子（4）XBbx1x2x3x4x5x1x2x53/47/4-3/4100010-1/43/4-3/41/41/4-1/4001-z-5/200-1/2-1/20XBbx1x2x3x4x5x1x2x31111000100011/301/3-1/121/4-1/3-z-2000-1/3-1/6此時，x*=(1,1,1,0,0)T已滿足整數(shù)要求，故原整數(shù)規(guī)劃問題的最優(yōu)解為：x1=1,x2=1最優(yōu)值為：z*=2割平面法例子（5）下面從幾何角度了解一下本題中可行域的切割過程：割平面方程為：§4.0--1規(guī)劃例1.在高?；@球聯(lián)賽中,我校男子籃球隊要從８名隊員中選擇平均身高最高的出場陣容,隊員的號碼、身高及擅長的位置如下表：0-1變量----若變量只能取值0或1,則稱其為0-1變量.通常作為邏輯變量,常被用來表示系統(tǒng)是否處于某個特定狀態(tài),或決策時是否取某個特定方案.0--1規(guī)劃的數(shù)學(xué)模型(2)同時，要求出場陣容滿足以下條件：

⑶

如果１號隊員和４號隊員都上場，則６號隊員不能出場⑴

中鋒最多只能上場一個⑵

至少有一名后衛(wèi)問應(yīng)當(dāng)選擇哪5名隊員上場,才能使出場隊員平均身高最高?試寫出上述問題的數(shù)學(xué)模型。⑷

２號隊員和６號隊員必須保留一個不出場。0--1規(guī)劃的數(shù)學(xué)模型(3)約束條件:⑶

如果１號隊員和４號隊員都上場，則６號隊員不能出場(1）中鋒最多只能上場一個,即⑵至少有一名后衛(wèi)解:設(shè)Xj=1表示第j號隊員上場,

Xj=0表示第j號隊員不上場

j=1,2,...,8⑷

２號隊員和６號隊員必須保留一個不出場。(5）籃球比賽恰好5人上場0--1規(guī)劃的數(shù)學(xué)模型故該問題的數(shù)學(xué)模型為:其中cj表示第j號隊員的身高(j=1,2,…,8)0--1規(guī)劃的數(shù)學(xué)模型(例2)例2.某公司有機會對B1、B2、B3三個項目進(jìn)行投資。根據(jù)預(yù)算,前兩年每年可投資6(萬元),后兩年每年可投資7(萬元)。三個項目每年所需投資額和純利潤如下表:

問公司應(yīng)對哪幾個項目進(jìn)行投資,才能使獲得的利潤最大?試建立這個問題的整數(shù)規(guī)劃模型.解:設(shè)0--1規(guī)劃的數(shù)學(xué)模型(例2)故數(shù)學(xué)模型為0--1規(guī)劃的數(shù)學(xué)模型(例3)隊員的挑選要滿足下列條件:例3.某?；@球隊準(zhǔn)備從以下六名預(yù)備隊員中選拔三名為正式隊員,并使平均的身高盡可能高。這六名預(yù)備隊員情況如下表所示：⑴

至少補充一名后衛(wèi)隊員;⑵大李或小田中間恰有一名入選;⑶最多補充一名中鋒;⑷無論大李或小趙入選,小周就不能入選.試建立這個問題的整數(shù)規(guī)劃模型.0--1規(guī)劃的數(shù)學(xué)模型(例3)解:

設(shè)j=4,5,...,9約束條件:

⑴至少補充一名后衛(wèi)隊員⑵

大李或小田中間恰有一名入選;(3)最多補充一名中鋒⑷無論大李或小趙入選,小周就不能入選0--1規(guī)劃的數(shù)學(xué)模型(例3)則數(shù)學(xué)模型為例6.求解下面的0-1型整數(shù)規(guī)劃問題：0-1規(guī)劃的解法解：借助隱枚舉法，列表如下：0-1規(guī)劃的解法（2）該問題的最優(yōu)解:x1=1,x2=0,x3=1；最優(yōu)值:z*=8×(1,1,1)T×(1,1,0)T×(0,1,1)T8(1,0,1)T×(1,0,0)T×(0,1,0)T

5(0,0,1)T0(0,0,0)T（4）（3）（2）（1）件條束約z值全體組合2.用0-1變量表示含有互相排斥的約束條件例4．某廠擬用運貨車或船托運甲乙兩種貨物,每箱的體積、重量、可獲利及托運限制如下表:問:兩種貨物各托運多少箱,可使獲利最大?試建立這個問題的整數(shù)規(guī)劃模型.貨物體積重量利潤

(每箱立方米)(每箱百斤)(每箱百元)

甲5(7)220

乙4(3)510托運限制24(45)13

用0-1變量表示含有互相排斥的約束條件解：設(shè)甲乙兩種貨物分別托運x1和x2箱目標(biāo)函數(shù)

z=20x1+10x2約束條件：重量限制

2x1+5x2≤13體積限制：當(dāng)船托運時為7x1+3x2≤45但托運時用汽車或用船的兩種方式中只能選擇一種故引0-1變量yy=0表示采用車運方式；y=1表示采用船運方式體積限制的約束可用以下條件來代替：當(dāng)汽車托運時為5x1+4x2≤245x1+4x2≤24+yM7x1+3x2≤45+(1-y)M（其中M是充分大的數(shù)）用0-1變量表示含有互相排斥的約束條件

則數(shù)學(xué)模型為：用0-1變量表示含有互相排斥的約束條件注：若有m個互相排斥的約束條件（≤型）為了保證這m個約束條件只有一個起作用我們引入m個0-1變量yi(i=1,2,...,m)和一個充分大的常數(shù)M可用下列m+1個約束條件表示：用0-1變量表示含有互相排斥的約束條件例5.利用0-1變量把下列各題分別表示成一般線性約束條件用0-1變量表示含有互相排斥的約束條件解：設(shè)用0-1變量表示含有互相排斥的約束條件§5.指派問題指派問題(或稱分配問題)(AssignmentProblem)有n項任務(wù)要完成，恰好有n個人可以分別去完成其中每一項,但由于任務(wù)性質(zhì)和各人專長不同,因此各人去完成不同的各種任務(wù)的效率(或所費時間)就有差別,則應(yīng)當(dāng)如何指派哪個人去完成哪項任務(wù)使總效率為最高(或所花時間為最小)?

例1:

有一份說明書,要分別譯成英、日、德、俄四種文字（分別稱為任務(wù)Ｅ，Ｊ，Ｇ，Ｒ），要交甲、乙、丙、丁四人去完成，每人完成一種翻譯；因各人專業(yè)不同，他們翻譯成不同文字所需時間如下表，問應(yīng)指派哪個人完成哪項任務(wù)可使總的花費時間為最?。?/p>

指派問題（2）例2.某游泳隊有4名運動員A1,A2,A3,A4,他們的50米自由泳、蛙泳、蝶泳、仰泳的成績?nèi)缦卤硭?現(xiàn)在要將他們組成一個450混合接力隊,問應(yīng)該分配

A1,A2,A3,A4各游什么項目,才能使總成績最好?指派問題（3）類似有：有n項加工任務(wù)，怎么樣指派到n臺機床上分別完成的問題；有n條航線，怎么樣指定N艘船去航行問題....系數(shù)矩陣:對每個指派問題都有類似上述表格中的元素

cij>0，由這些元素構(gòu)成的矩陣為效率矩陣令

則指派問題的數(shù)學(xué)模型

表示指派第i個人去完成第j項任務(wù)

表示不指派第i個人去完成第j項任務(wù)

指派問題（4）指派問題是0-1規(guī)劃的特例，也是運輸問題的特例。指派問題的一個可行解可用一個矩陣表示：稱之為解矩陣若從系數(shù)矩陣（cij）的一行（列）各元素中分別減去該行（列）的最小數(shù)，得到新矩陣（bij），則以（bij）為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)解相同。利用此性質(zhì)，可使原系數(shù)矩陣變換為含有很多0元素的新系數(shù)矩陣，而最優(yōu)解保持不變。我們稱系數(shù)矩陣中位于不同行不同列的0元素為獨立的0元素。指派問題的最優(yōu)解的性質(zhì)：指派問題（5）如下的系數(shù)矩陣中存在4個獨立的0元素若能在系數(shù)矩陣（bij）中能找出n個獨立的0元素，則令解矩陣（xij）中對應(yīng)這n個獨立的0元素的元素取1，其余元素取0，將其代入目標(biāo)函數(shù)中得到zb=0，它一定是最小。這就是以B為系數(shù)矩陣的指派問題的最優(yōu)解，也得到原問題的最優(yōu)解。指派問題（6）1955年庫恩（W.W.Kuhn）提出了指派問題的解法。他引用了匈牙利數(shù)學(xué)家康尼格（D.Konig）一個關(guān)于矩陣中0元素的定理：系數(shù)矩陣中的獨立0元素的最多個數(shù)等于能覆蓋所有0元素的最少的直線數(shù)目。所以稱此解法為匈牙利解法。下面我們介紹匈牙利解法的步驟：匈牙利解法第一步：使系數(shù)矩陣出現(xiàn)0元素

(A)從系數(shù)矩陣的每行元素減去該行的最小元素;(B)再從所得系數(shù)矩陣的每列元素中減去該列的最小元素;

由0元素最少的行(或列)開始,圈出一個0元素,用表示,然后劃去同行同列的0元素,用表示,這樣依次做完各行各列,已劃去就不能再圈,第二步：試求最優(yōu)解如果能得到n個,這就完成了求最優(yōu)解的過程;第三步：作能覆蓋所有0元素的最少數(shù)目的直線集合如果圈出的不夠n個,則轉(zhuǎn)(3)匈牙利解法

(A)對沒有的行打號;(B)在已打號的行中，對

所在列打號;(C)在已打號的列中，對所在行打號;(D)重復(fù)(B)(C),直到再也找不到可以打號的行或列為止;(E)對沒有打號的行畫橫線,所有打的列畫縱線,這樣就得到了覆蓋所有零元素的最少直線數(shù)目的直線集合.第四步：在沒有被直線覆蓋的部分中找出最小元素,然后對沒畫直線的行的各元素都減去這最小元素,

對畫直線的列的各元素都加上這最小元素,這樣得到新的系數(shù)矩陣;若有n個不同行不同列的0元素,則求解過程完成;若沒有n個不同行不同列的0元素,轉(zhuǎn)第三步執(zhí)行.匈牙利解法(舉例1)例1解:甲譯俄文；乙譯日文；丙譯英文；丁譯德文總的花費時間為28

由于已有4個獨立0元素，故最優(yōu)解為：匈牙利解法(舉例2)

例2

求下表所示效率矩陣的指派問題的最小解。解：匈牙利解法(舉例2)

最后一個矩陣中，已得到5個獨立0元素，則得最優(yōu)解為：匈牙利解法(舉例2)最優(yōu)方案為：

甲→B

乙→D

丙→E

丁→C

戊→A

或甲→B

乙→C

丙→E

丁→D

戊→A總的耗費時間為32個單位。匈牙利解法(舉例2)

解2：

(A)對沒有的行打號;(B)在已打號的行中，對

所在列打號;(C)在已打號的列中，對所在行打號;(D)重復(fù)(B)(C),直到再也找不到可以打號的行或列為止;(E)對沒有打號的行畫橫線,所有打的列畫縱線,這樣就得到了覆蓋所有零元素的最少直線數(shù)目的直線集合.匈牙利解法(舉例2)(4)在沒有被直線覆蓋的部分中找出最小元素,然后,對沒畫直線的行的各元素都減去這最小元素,對畫直線的列的各元素都加上這最小元素,這樣得到新的系數(shù)矩陣;第3,5行各元素減去2第1列各元素加上2匈牙利解法(舉例2)最優(yōu)方案為：甲→B

乙→D

丙→E丁→D

戊→A

或甲→B

乙→C

丙→E

丁→C

戊→A最后一個矩陣中，已得到5個獨立0元素，則得最優(yōu)解為：總的耗費時間為32個單位。二．極大化的指派問題極大化指派問題的數(shù)學(xué)模型

需把它化為極小化問題但不能象線性規(guī)劃問題那樣，令目標(biāo)函數(shù)的相反數(shù)此時令bij=M-cij

其中M是足夠大的常數(shù)則系數(shù)