運(yùn)籌學(xué)本科整數(shù)規(guī)劃

整數(shù)規(guī)劃IntegerProgramming（IP）第五章整數(shù)規(guī)劃1整數(shù)規(guī)劃IntegerProgramming（IP）整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)整數(shù)規(guī)劃數(shù)學(xué)模型的一般形式（IP）問題Max（min）z=∑cjxj∑aijxj

≤（或=，或≥）bii=1，2，…，mxj

≥0j=1，2，…，nxj中部分或全部取整數(shù)s.t.松弛問題Max（min）z=∑cjxj∑aijxj

≤（或=，或≥）bii=1，2，…，mxj

≥0j=1，2，…，n2整數(shù)規(guī)劃IntegerProgramming（IP）整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)整數(shù)規(guī)劃問題的類型純整數(shù)線性規(guī)劃——pureintegerlinearprogramming：全部決策變量都必須取整數(shù)值?；旌险麛?shù)線性規(guī)劃——mixedintegerlinearprogramming：決策變量中一部分必須取整數(shù)值，另一部分可以不取整數(shù)值。0-1型整數(shù)線性規(guī)劃——zero-oneintegerlinearprogramming：決策變量只能取值0或1

。3整數(shù)規(guī)劃IntegerProgramming（IP）整數(shù)規(guī)劃的例子例1、Page124工作時(shí)間和人員安排問題例2、Page124投資項(xiàng)目選擇問題例3、Page125建廠選址問題4整數(shù)規(guī)劃IntegerProgramming（IP）整數(shù)規(guī)劃問題的求解方法分支定界法branchandboundmethod分支定界法是一種隱枚舉方法（implicitenumeration）或部分枚舉方法，它不是一種有效的算法，是枚舉方法基礎(chǔ)上的改進(jìn)。其關(guān)鍵是分支和定界。例——MaxZ=X1+X214X1+9X2

≤51-6X1+3X2

≤1X1，X2

≥0X1，X2取整數(shù)s.t.5整數(shù)規(guī)劃IntegerProgramming（IP）整數(shù)規(guī)劃問題的求解方法分支定界法圖解整數(shù)規(guī)劃松弛問題MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1，X2≥0該整數(shù)規(guī)劃松弛問題的解為：（X1，X2）=

（3/2，10/3）Z=29/66整數(shù)規(guī)劃IntegerProgramming（IP）整數(shù)規(guī)劃問題的求解方法分支定界法圖解整數(shù)規(guī)劃松弛問題MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1，X2≥0（3/2，10/3）Z=29/6B1MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1

X1≥2X1，X2≥0B2MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1

X1≤1X1，X2≥0B2：解（1，7/3）ZB2=10/3B1：解（2，23/9）ZB1=41/97整數(shù)規(guī)劃IntegerProgramming（IP）整數(shù)規(guī)劃問題的求解方法分支定界法圖解整數(shù)規(guī)劃（3/2，10/3）Z=29/6B1MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2X1，X2≥0B2：解（1，7/3）ZB2=10/3B1：解（2，23/9）ZB1=41/9B11MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2

X2≥3X1，X2≥0B12MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2

X2≤2X1，X2≥0B12：解（33/14，2）ZB12=61/148整數(shù)規(guī)劃IntegerProgramming（IP）整數(shù)規(guī)劃問題的求解方法分支定界法圖解整數(shù)規(guī)劃（3/2，10/3）Z=29/6B2：解（1，7/3）ZB2=10/3B12MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2X2≤2X1，X2≥0B12：解（33/14，2）ZB12=61/14B121MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1

X1≥3X2≤2X1，X2≥0B122MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1

X1≤2X2≤2X1，X2≥0B121：解（3，1）ZB121=4B122：解（2，2）ZB122=4B1：解（2，23/9）ZB1=41/99整數(shù)規(guī)劃IntegerProgramming（IP）整數(shù)規(guī)劃問題的求解方法割平面法cuttingplaneapproach

割平面法求解整數(shù)規(guī)劃問題時(shí)，若其松馳問題的最優(yōu)解X*不滿足整數(shù)要求時(shí)，則從X*的非整分量中選取一個(gè)，用以構(gòu)造一個(gè)線性約束條件（Gomory割平面），將其加入原松馳問題中，形成一個(gè)新的線性規(guī)劃，然后求解之。其關(guān)鍵在于新增加的這個(gè)線性約束條件將切割掉部分非整數(shù)解，至少將當(dāng)前松馳問題的非整數(shù)最優(yōu)解切割掉了，而不會(huì)切割掉問題的任何整數(shù)解。10整數(shù)規(guī)劃IntegerProgramming（IP）整數(shù)規(guī)劃問題的求解方法割平面法cuttingplaneapproach

構(gòu)造切割方程的步驟：1、令xi是相應(yīng)松馳問題的最優(yōu)解中為非整數(shù)值的一個(gè)基變量，由單純形表最終表得：xi+∑aikxk=bi……（1式）其中i∈Q（Q指非基變量下標(biāo)集）k∈K（K指基變量下標(biāo)集）11整數(shù)規(guī)劃IntegerProgramming（IP）整數(shù)規(guī)劃問題的求解方法割平面法cuttingplaneapproach

構(gòu)造切割方程的步驟：2、將bi和aik都分解成整數(shù)部分N（不超過b的最大整數(shù)）與非負(fù)真分?jǐn)?shù)部分f之和，即：bi=Ni+fi，其中0＜fi＜1………（2式）aik=Nik+fik，其中0≤fik＜1例如：若b=2.35，則N=2，f=0.35；若b=-1.45，則N=-2，f=0.5512整數(shù)規(guī)劃IntegerProgramming（IP）整數(shù)規(guī)劃問題的求解方法割平面法cuttingplaneapproach

構(gòu)造切割方程的步驟：2、將（2式）代入（1式）得：xi+∑Nikxk-Ni=fi-∑fikxk……（3式）3、提出變量為整（當(dāng)然含非負(fù)）的條件：由于（3式）中等式左邊需整，而0＜fi＜1，故有

fi-∑fikxk≤0……（4式）此即為所需切割方程。13整數(shù)規(guī)劃IntegerProgramming（IP）整數(shù)規(guī)劃問題的求解方法割平面法cuttingplaneapproach

構(gòu)造切割方程的步驟：（1）切割方程fi-∑fikxk≤0真正進(jìn)行了切割，至少把非整數(shù)最優(yōu)解這一點(diǎn)切割掉了。證明：（反證法）假設(shè)松馳問題的最優(yōu)解X*未被切割掉，則由

fi-∑fikx*k≤0，又因?yàn)閤*k=0，（因x*k為非基變量）有fi≤0，這與fi＞0矛盾。（2）不會(huì)切割掉任何整數(shù)解，因?yàn)榍懈罘匠淌怯勺兞繛檎臈l件提出的。14整數(shù)規(guī)劃IntegerProgramming（IP）整數(shù)規(guī)劃問題的求解方法割平面法cuttingplaneapproach例——求解IPMaxZ=X1+X2-X1+X2≤13X1+X2≤4X1，X2≥0X1，X2整數(shù)LPMaxZ=X1+X2-X1+X2≤13X1+X2≤4X1，X2≥015整數(shù)規(guī)劃IntegerProgramming（IP）求解步驟：1、求解LP得到非整數(shù)最優(yōu)解：

X=（3/4，7/4，0，0），MaxZ=5/2Cj1100I表CBXBB–1

bX1X2X3X40X31-11100X443101j01100B表1X13/410-1/41/41X27/4013/41/4j-5/200-1/2-1/216整數(shù)規(guī)劃IntegerProgramming（IP）求解步驟：2、構(gòu)造切割方程：

由B表中的第2個(gè)方程——X2+3/4X3+1/4X4=7/4有b2=7/4=1+3/4a23=3/4=0+3/4，a24=1/4=0+1/4因此，切割方程為——

3/4–3/4X3–1/4X4≤0增加松弛變量X5，并將如下方程的約束條件添加到B表中。

-3X3-1X4+X5=-3X5≥017整數(shù)規(guī)劃IntegerProgramming（IP）求解步驟：3、求解新的松弛問題

Cj11000B表CBXBB–1

bX1X2X3X4X51X13/410-1/41/401X27/4013/41/400X5-300-3-11j-5/200-1/2-1/20新B表1X111001/3-1/121X2101001/40X310011/3-1/3j-2000-1/3-1/618整數(shù)規(guī)劃IntegerProgramming（IP）0-1整數(shù)規(guī)劃問題0-1變量及其應(yīng)用0-1變量作為邏輯變量（Logicalvariable），常常被引用來表示系統(tǒng)是否處于某個(gè)特定的狀態(tài)，或者決策變量是否取某個(gè)特定的方案。如xj=1當(dāng)決策取方案Pj時(shí)0當(dāng)決策不取方案Pj時(shí)19整數(shù)規(guī)劃IntegerProgramming（IP）0-1整數(shù)規(guī)劃問題0-1變量及其應(yīng)用例1選址問題某公司在城市的東、西、南三區(qū)建立門市部。擬議中有7個(gè)位置（地點(diǎn)）Ai（i=1，2，…，7）可供選擇。公司規(guī)定在東區(qū)，由A1，A2，A3三個(gè)點(diǎn)中至多選兩個(gè)；在南區(qū)，由A4，A5兩個(gè)點(diǎn)中至少選一個(gè)；在西區(qū)，由A6，A7兩個(gè)點(diǎn)中至少選一個(gè)。如果選用Ai點(diǎn)，設(shè)備投資估計(jì)為bi元，每年可獲利潤估計(jì)為ci元，但投資總額不能超過B元。問公司選擇哪幾個(gè)點(diǎn)可使年總利潤最大？20整數(shù)規(guī)劃IntegerProgramming（IP）0-1整數(shù)規(guī)劃問題0-1變量及其應(yīng)用建立模型引入0-1變量1當(dāng)Ai點(diǎn)被選用0當(dāng)Ai沒點(diǎn)被選用xi=（i=1，2，…，7）maxz=∑cixi∑bixi≤Bx1+x2+x3≤2x4+x5≥1x6+x7≥1xi=0，或121整數(shù)規(guī)劃IntegerProgramming（IP）0-1整數(shù)規(guī)劃問題0-1變量及其應(yīng)用例7應(yīng)用0-1變量解決含互斥約束條件問題設(shè)：工序B有兩種方式完成方式（1）的工時(shí)約束為0.3X1+0.5X2≤150方式（2）的工時(shí)約束為0.2X1+0.4X2≤120問題是完成工序B只能從兩種方式中任選一種，如何將這兩個(gè)互斥的約束條件統(tǒng)一在一個(gè)線性規(guī)劃模型中呢？22整數(shù)規(guī)劃IntegerProgramming（IP）0-1整數(shù)規(guī)劃問題0-1變量及其應(yīng)用例7應(yīng)用0-1變量解決含互斥約束條件問題引入0-1變量y1=0若工序B采用方式（1）完成1若工序B不采用方式（1）完成y2=0若工序B采用方式（2）完成1若工序B不采用方式（2）完成23整數(shù)規(guī)劃IntegerProgramming（IP）0-1整數(shù)規(guī)劃問題0-1變量及其應(yīng)用例7應(yīng)用0-1變量解決含互斥約束條件問題于是前面兩個(gè)互斥的約束條件可以統(tǒng)一為如下三個(gè)約束條件：0.3X1+0.5X2≤150+M1y1

0.2X1+0.4X2≤120+M2y2

y1+y2=1其中M1，M2都是足夠大的正數(shù)。24整數(shù)規(guī)劃IntegerProgramming（IP）指派問題（assignmentproblem）指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型指派問題的標(biāo)準(zhǔn)形式（以人和事為例）是：有n個(gè)人和n件事，已知第i人做第j事的費(fèi)用為Cij（i，j=1，2，…，n），要求確定人和事之間的一一對應(yīng)的指派方案，使完成這件事的總費(fèi)用最少。如任務(wù)人員ABCD甲乙丙丁210971541481314161141513925整數(shù)規(guī)劃IntegerProgramming（IP）指派問題（assignmentproblem）指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型指派問題的標(biāo)準(zhǔn)形式，令1當(dāng)指派第i人完成第j項(xiàng)任務(wù)0當(dāng)不指派第i人完成第j項(xiàng)任務(wù)xij=minz=∑∑cijxij∑xij=1，j=1，2，…，n∑xij=1，i=1，2，…，nxij=1或026整數(shù)規(guī)劃IntegerProgramming（IP）指派問題（assignmentproblem）匈牙利解法標(biāo)準(zhǔn)的指派問題是一類特殊的0-1整數(shù)規(guī)劃問題，可以用多種相應(yīng)的解法來求解。但是，這些方法都沒有充分利用指派問題的特殊性質(zhì)來有效減少計(jì)算量。1955年，庫恩（W.W.Kuhn）利用匈牙利數(shù)學(xué)家康尼格（D.K?nig）的關(guān)于矩陣中獨(dú)立零元素的定理，提出了指派問題的一種解法，由此，習(xí)慣上稱之為匈牙利解法。27整數(shù)規(guī)劃IntegerProgramming（IP）指派問題（assignmentproblem）匈牙利解法匈牙利解法的關(guān)鍵是利用了指派問題最優(yōu)解的如下性質(zhì)：若從指派問題的系數(shù)矩陣C=（cij）n×n的某行（或某列）各元素分別減去（或加上）一個(gè)常數(shù)k，得到一個(gè)新的系數(shù)矩陣C’=（c’ij）則以C和C’為系數(shù)矩陣的兩個(gè)指派問題有相同的最優(yōu)解（兩個(gè)問題的目標(biāo)值不相同）。28整數(shù)規(guī)劃IntegerProgramming（IP）指派問題（assignmentproblem）匈牙利解法的一般步驟步驟一：變換系數(shù)矩陣。使其每行及每列至少有一個(gè)零元素，同時(shí)不出現(xiàn)負(fù)元素。步驟二：進(jìn)行試指派，即確定獨(dú)立零元素（矩陣中不在同一行和同一列）。步驟三：繼續(xù)變換系數(shù)矩陣，然后返回步驟二。29整數(shù)規(guī)劃IntegerProgramming（IP）指派問題（assignmentproblem）匈牙利解法的一般步驟以上例說明步驟2151341041415914161378119013112601011057401422497min（cij）=30整數(shù)規(guī)劃IntegerProgramming（IP）指派問題（assignmentproblem）匈牙利解法的一般步驟以上例說明步驟013112601011047401420042min01370606905320100=（c’ij）31整數(shù)規(guī)劃IntegerProgramming（IP）指派問題（assignmentproblem）匈牙利解法的一般步驟以上例說明步驟01370606905320100此時(shí)加圈0元素的個(gè)數(shù)m=n=4，所以得到最優(yōu)解32整數(shù)規(guī)劃IntegerProgramming（IP）指派問題（assignmentproblem）匈牙利解法的一般步驟以上例說明步驟00010100

10000010（xij）=33整數(shù)規(guī)劃IntegerProgramming（IP）指派問題（assignmentproblem）匈牙利解法的一般步驟例任務(wù)人員ABCDE甲乙丙丁戊128715479171410961267761461096910934整數(shù)規(guī)劃IntegerProgramming（IP）指派問題（assignmentproblem）匈牙利解法的一般步驟1279798966671712149151466104107109767645020223000010572980040636535整數(shù)規(guī)劃IntegerProgramming（IP）指派問題（assignmentproblem）匈牙利解法的一般步驟50202230000105729800406365此時(shí)加圈0元素的個(gè)數(shù)m=4，而n=5，所以解題沒有完成。獨(dú)立零元素（加圈零元素）少于n個(gè)，表示還不能確定最優(yōu)指派方案。此時(shí)需確定能覆蓋所有零元素的最少直線數(shù)目的直線集合。方法如下：36整數(shù)規(guī)劃IntegerProgramming（IP）指派問題（assignmentproblem）匈牙利解法的一般步驟對沒有加圈零元素的所有行打√號；對所有打√號行的所有含零元素的列打√號；再對已打√號的列中含零元素的行打√號；重復(fù)2）和3），直到再也不能找到可以打√號行或列為止；對未打√號的行畫一橫線，對已打√號的列畫一豎線，這樣就得到能覆蓋所有零元素的最少直線數(shù)目的直線集合。37整數(shù)規(guī)劃IntegerProgramming（IP）指派問題（assignmentproblem）匈牙利解法的一般步驟50202230000105729800406365√√√12338整數(shù)規(guī)劃IntegerProgramming（IP）指派問題（assignmentproblem）匈牙利解法的一般步驟繼續(xù)變換系數(shù)矩陣。其方法是在未被直線覆蓋的元素中找出一個(gè)最小元素。然后在打√號行各元素都減去此最小元素，而在打√號列的各元素都加上此最小元素，以保證原來的0元素不變。這樣得到新系數(shù)矩陣（其最優(yōu)解和原問題相同）。若得到n個(gè)獨(dú)立的0元素，則已得最優(yōu)解，否則重復(fù)該步驟繼續(xù)變換系數(shù)矩陣。39整數(shù)規(guī)劃IntegerProgramming（IP）指派問題（assignmentproblem）匈牙利解法的一般步驟50202230000105729800406365√√√最小元素=270