運(yùn)籌學(xué) 第四章 整數(shù)規(guī)劃與分配問題

整數(shù)規(guī)劃與分配問題整數(shù)規(guī)劃的特點(diǎn)及作用分支定界法割平面法應(yīng)用舉例分配問題與匈牙利法

例1、合理下料問題設(shè)用某型號(hào)的圓鋼下零件A1,

A2,…,Am

的毛坯。在一根圓鋼上下料的方式有B1,B2,…Bn

種，每種下料方式可以得到各種零件的毛坯數(shù)以及每種零件的需要量，如表所示。問怎樣安排下料方式，使得即滿足需要，所用的原材料又最少？一、整數(shù)規(guī)劃的模型第一節(jié)整數(shù)規(guī)劃的特點(diǎn)及作用零件毛坯數(shù)零件方個(gè)數(shù)式零件設(shè)：xj

表示用Bj

(j=1.2…n)

種方式下料根數(shù)模型：x1xn…例2、某公司計(jì)劃在m個(gè)地點(diǎn)建廠，可供選擇的地點(diǎn)有A1,A2…Am

，他們的生產(chǎn)能力分別是a1,a2,…am（假設(shè)生產(chǎn)同一產(chǎn)品）。第i個(gè)工廠的建設(shè)費(fèi)用為fi

(i=1.2…m),又有n個(gè)地點(diǎn)B1,B2,…Bn

需要銷售這種產(chǎn)品，其銷量分別為b1.b2…bn

。從工廠運(yùn)往銷地的單位運(yùn)費(fèi)為Cij。試決定應(yīng)在哪些地方建廠，即滿足各地需要，又使總建設(shè)費(fèi)用和總運(yùn)輸費(fèi)用最省？單銷地廠址價(jià)生產(chǎn)能力建設(shè)費(fèi)用銷量設(shè)：xij

表示從工廠運(yùn)往銷地的運(yùn)量(i=1.2…m、j=1.2…n),1在Ai建廠又設(shè)Yi＝（i=1.2…m）

0不在Ai建廠設(shè)：

xij

表示從工廠運(yùn)往銷地的運(yùn)量(i=1.2…m、j=1.2…n),1在Ai建廠

又設(shè)Yi＝（i=1.2…m）

0不在Ai建廠模型：

例3、機(jī)床分配問題設(shè)有m臺(tái)同類機(jī)床，要加工n種零件。已知各種零件的加工時(shí)間分別為a1,a2,…an

，問如何分配，使各機(jī)床的總加工任務(wù)相等，或者說盡可能平衡。設(shè)：1分配第i臺(tái)機(jī)床加工第j種零件；

xij＝（i=1.2…m,j=1.2…n）

0相反。又由于一個(gè)零件只能在一臺(tái)機(jī)床上加工，所以有:于是，第i臺(tái)機(jī)床加工各種零件的總時(shí)間為:因此，求xij

，使得問如何分配，使各機(jī)床的總加工時(shí)間相等，或者說盡可能平衡。?在上一章討論的LP問題中,對決策變量只限于不能取負(fù)值的連續(xù)型數(shù)值,即可以是正分?jǐn)?shù)或正小數(shù)。然而在許多實(shí)際問題中，決策變量只有非負(fù)整數(shù)才有實(shí)際意義。對求整數(shù)最優(yōu)解的問題，稱為整數(shù)規(guī)劃(IntegerProgramming)(簡記為IP)。又稱約束條件和函數(shù)均為線性的IP為整數(shù)線性規(guī)劃(IntegerLinearProgramming)(簡記為ILP)。純整數(shù)規(guī)劃：所有決策變量要求取非負(fù)整數(shù)（這時(shí)引進(jìn)的松弛變量和剩余變量可以不要求取整數(shù)）。全整數(shù)規(guī)劃：除了所有決策變量要求取非負(fù)整數(shù)外，系數(shù)aij和常數(shù)bi也要求取整數(shù)（這時(shí)引進(jìn)的松弛變量和剩余變量也必須是整數(shù)）?；旌险麛?shù)規(guī)劃：只有一部分的決策變量要求取非負(fù)整數(shù)，另一部分可以取非負(fù)實(shí)數(shù)。

0－1整數(shù)規(guī)劃：所有決策變量只能取0或1兩個(gè)整數(shù)。整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系

從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的基礎(chǔ)上，通過舍入取整，尋求滿足整數(shù)要求的解即可。但實(shí)際上兩者卻有很大的不同，通過舍入得到的解（整數(shù)）也不一定就是最優(yōu)解，有時(shí)甚至不能保證所得到的解是整數(shù)可行解。例4、設(shè)整數(shù)規(guī)劃問題如下首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。用圖解法求出最優(yōu)解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)現(xiàn)求整數(shù)解（最優(yōu)解）：如用“舍入取整法”可得到4個(gè)點(diǎn)：(1,3)(2,3)(1,4)(2,4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問題的可行解集是一個(gè)有限集，如圖所示。因此，可將集合內(nèi)的整數(shù)點(diǎn)一一找出，其最大目標(biāo)函數(shù)的值為最優(yōu)解，此法為完全枚舉法。如上例：其中（2，2）（3，1）點(diǎn)為最大值，Z=4。目前，常用的求解整數(shù)規(guī)劃的方法有：

分支定界法和割平面法；對于特別的0－1規(guī)劃問題采用隱枚舉法和匈牙利法。人們對IP感興趣，還因?yàn)橛行┙?jīng)濟(jì)管理中的實(shí)際問題的解必須滿足如邏輯條件和順序要求等一些特殊的約束條件。此時(shí)需引進(jìn)邏輯變量（又稱0-1變量），以“0”表示“非”，以“1”表示“是”。凡決策變量均是0-1變量的IP為0-1規(guī)劃。邏輯變量的應(yīng)用(3)兩組條件滿足其中一組又Ｍ為任意大正數(shù)，則問題表達(dá)為：若，則；否則（即時(shí)）定義(4)在實(shí)際中經(jīng)常會(huì)遇到這樣的問題，有n項(xiàng)不同的任務(wù)，需要n個(gè)人分別完成其中的一項(xiàng)，但由于任務(wù)的性質(zhì)和各人的專長不同，因此各人去完成不同的任務(wù)的效率（或花費(fèi)的時(shí)間或費(fèi)用）也就不同。于是產(chǎn)生了一個(gè)問題，應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成n項(xiàng)任務(wù)的總效率最高（或所需時(shí)間最少），這類問題稱為指派問題或分配問題。第二節(jié)分配問題與匈牙利法（一）、指派問題的數(shù)學(xué)模型設(shè)n個(gè)人被分配去做n件工作，規(guī)定每個(gè)人只做一件工作，每件工作只有一個(gè)人去做。已知第i個(gè)人去做第j件工作的的效率（時(shí)間或費(fèi)用）為aij(i=1.2…n;j=1.2…n)并假設(shè)aij≥0。問應(yīng)如何分配才能使總效率（時(shí)間或費(fèi)用）最高？設(shè)決策變量1分配第i個(gè)人去做第j件工作

xij

=0相反(i,j=1.2.…n)其數(shù)學(xué)模型為：（二）、解題步驟：指派問題是0-1規(guī)劃的特例，也是運(yùn)輸問題的特例，當(dāng)然可用整數(shù)規(guī)劃，0-1規(guī)劃或運(yùn)輸問題的解法去求解，這就如同用單純型法求解運(yùn)輸問題一樣是不合算的。利用指派問題的特點(diǎn)可有更簡便的解法，這就是匈牙利法.匈牙利法是從這樣一個(gè)明顯的事實(shí)出發(fā):如果效率矩陣的所有元素,而其中存在一組位于不同行不同列的零元素，則只要令這些零元素位置的，其余的，則就是問題的最優(yōu)解．最優(yōu)解為如效率矩陣為匈牙利法的基本思想是：對同一項(xiàng)工作（任務(wù)）j來說，同時(shí)提高或降低每人相同的效率（常數(shù)ti），不影響其最優(yōu)指派；同樣，對同一個(gè)人i來說，完成各項(xiàng)工作的效率都提高或降低相同的效率（常數(shù)di），也不影響其最優(yōu)指派;因此可得到新的效率矩陣(bij)nxn，其中bij=aij+ti+dj

（對所有的i,j）則新的目標(biāo)函數(shù)為其中為常數(shù)這說明Z與Z同時(shí)達(dá)到最小值。因而最優(yōu)解相同。故指派問題有以下性質(zhì)：若從效率矩陣(aij)nxn的一行（列）各元素中分別減去該行（列）的最小元素，得到的新效率矩陣(bij)nxn不改變原指派問題的最優(yōu)解。匈牙利法:第一步：變換指派問題的系數(shù)矩陣（aij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即(1)從(aij)的每行元素都減去該行的最小元素；(2)再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。

第二步：進(jìn)行試指派，以尋求最優(yōu)解。在(bij)中找盡可能多的獨(dú)立0元素，若能找出n個(gè)獨(dú)立0元素，就以這n個(gè)獨(dú)立0元素對應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨(dú)立0元素，常用的步驟為：

(1)從只有一個(gè)0元素的行(列)開始，給這個(gè)0元素加圈，記作◎

。然后劃去◎

所在列(行)的其它0元素，記作?

；這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。

(2)給只有一個(gè)0元素的列(行)中的0元素加圈，記作◎；然后劃去◎

所在行的0元素，記作?

．

(3)反復(fù)進(jìn)行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。

(4)若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個(gè)，則從剩有0元素最少的行(列)開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個(gè)0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。（5）若◎

元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問題的最優(yōu)解已得到。若m<n,則轉(zhuǎn)入下一步。第三步：作最少的直線覆蓋所有0元素。

(1)對沒有◎的行打√號(hào)；

(2)對已打√號(hào)的行中所有含?元素的列打√號(hào)；

(3)再對打有√號(hào)的列中含◎

元素的行打√號(hào)；

(4)重復(fù)(2),(3)直到得不出新的打√號(hào)的行、列為止；

(5)對沒有打√號(hào)的行畫橫線，有打√號(hào)的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù)l。l應(yīng)等于m，若不相等，說明試指派過程有誤，回到第二步(4)，另行試指派；若l＝m<n，須再變換當(dāng)前的系數(shù)矩陣，以找到n個(gè)獨(dú)立的0元素，為此轉(zhuǎn)第四步。第四步：變換矩陣(bij)以增加0元素。在沒有被直線覆蓋的所有元素中找出最小元素，然后打√各行都減去這最小元素；打√各列都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第二步。例1有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時(shí)間如下表所示，問如何分派任務(wù)，可使總時(shí)間最少？

任務(wù)人員ABCD甲67112乙4598丙31104丁5982求解過程如下：第一步，變換系數(shù)矩陣：-5第二步，試指派：◎◎◎??找到3個(gè)獨(dú)立零元素但m=3<n=4。第三步，作最少的直線覆蓋所有0元素：◎◎◎??√√√獨(dú)立零元素的個(gè)數(shù)m等于最少直線數(shù)l，即l＝m=3<n=4；第四步，變換矩陣(bij)以增加0元素：沒有被直線覆蓋的所有元素中的最小元素為1，然后打√各行都減去1；打√各列都加上1，得如下矩陣，并轉(zhuǎn)第二步進(jìn)行試指派：000

0

00得到4個(gè)獨(dú)立零元素，所以最優(yōu)解矩陣為：◎◎◎??√√√◎◎◎??15◎◎◎??◎Lingo求解例2有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時(shí)間如下表所示，問如何分派任務(wù)，可使總時(shí)間最少？

任務(wù)人員ABCD甲21097乙154148丙13141611丁4151392109715414813141611415139行減0875110104235001195082511054230001145列減試指派082511054230001145◎?◎◎?082511054230001145◎?◎◎?√√√調(diào)整0603110542300092306031105423000923指派◎◎?◎?◎0010010000011000Lingo求解例4：求下面問題的最優(yōu)指派115764戊69637丁96458丙9117129乙118957甲EDCBA費(fèi)工作用人員11576469637964589117129118957造“零”520436725042441025340363402317123150240315試指派5032015304310140305242402◎?◎◎◎??打勾√√√5032015304310140305242402◎?◎◎◎??劃線√√√5032015304310140305242402◎?◎◎◎??調(diào)整最小值為11-13133-12400630200000試指派5033004203310240306231301◎?◎?◎?◎?√√√√√◎?列行交替尋找打勾時(shí)√√劃線5033004203310240306231301◎?◎?◎?◎?√√√√√√√5033004203310240306231301◎?◎?◎?◎?√√√√√√√調(diào)整1031326030420133024003305◎?√√√√√◎◎◎???0-120215-12-12-113-106043006√√?31-1023024023◎??◎◎?◎?◎此問題有多個(gè)最優(yōu)解試指派?Lingo求解用匈牙利法求解下列指派問題，已知效率矩陣分別如下：Lingo求解Lingo求解一般指派問題最大化指派問題人數(shù)和工作數(shù)不等的指派問題一個(gè)人可做幾項(xiàng)工作的指派問題某項(xiàng)工作一定不能由某人做的指派問題最大化指派問題最大值最小化指派問題Lingo求解人數(shù)和工作數(shù)不等的指派問題列減√◎?◎◎????◎√√試指派劃線√√√調(diào)整試指派◎◎◎◎◎?????Lingo求解一個(gè)人可做幾項(xiàng)工作的指派問題A1可同時(shí)做三項(xiàng)工作3195231952783298247631952行減2084120841561076025420841列減0074000740360064015300740????????√√√√√√√◎◎◎◎◎?列行交替尋找0074000740360064015300740√√√√√√√0074000740360064015300740調(diào)整0063000630470074004300630-136-1-1240-1350063-136-1-1-136-1-1037000070004400?◎◎◎◎◎???????最優(yōu)指派為A1作B1，B4，B5，A2作B3，A3作B2。Lingo求解某項(xiàng)工作一定不能由某人做的指派問題A1不能做B4;A3不能做B3Lingo求解（一）、基本思路考慮整數(shù)問題：整數(shù)問題的松弛問題：第三節(jié)分枝定界法

1、先不考慮整數(shù)約束，解(

IP)的松弛問題(LP)，可能得到以下情況之一：⑴若(LP)沒有可行解,則(IP)也沒有可行解,停止計(jì)算。⑵若(LP)有最優(yōu)解,并符合(IP)的整數(shù)條件,則(LP)的最優(yōu)解即為(IP)的最優(yōu)解,停止計(jì)算。⑶若(LP)有最優(yōu)解,但不符合(IP)的整數(shù)條件,轉(zhuǎn)入下一步。為討論方便，設(shè)(LP)的最優(yōu)解為：

2、定界：記(

IP)的目標(biāo)函數(shù)最優(yōu)值為Z*,以Z(0)

作為Z*

的上界，記為＝Z(0)

。再用觀察法找的一個(gè)整數(shù)可行解X′，并以其相應(yīng)的目標(biāo)函數(shù)值Z′作為Z*

的下界，記為Z＝Z′，也可以令Z＝－∞，則有：

Z≤Z*≤

3、分枝：在(LP)的最優(yōu)解X(0)中，任選一個(gè)不符合整數(shù)條件的變量，例如xr=

（不為整數(shù)），以表示不超過的最大整數(shù)。構(gòu)造兩個(gè)約束條件

xr≤和xr≥＋1如此反復(fù)進(jìn)行，直到得到Z＝Z*＝為止，即得最優(yōu)解X*

。將這兩個(gè)約束條件分別加入問題(

IP)，形成兩個(gè)子問題(

IP1)和(

IP2)，再解這兩個(gè)問題的松弛問題(LP1)和(LP2)。

4、修改上、下界：按照以下兩點(diǎn)規(guī)則進(jìn)行。⑴在各分枝問題中,找出目標(biāo)函數(shù)值最大者作為新的上界;⑵.從已符合整數(shù)條件的分枝中，找出目標(biāo)函數(shù)值最大者作為新的下界。

5、比較與剪枝：各分枝的目標(biāo)函數(shù)值中,若有小于Z者,則剪掉此枝，表明此子問題已經(jīng)探清，不必再分枝了;否則繼續(xù)分枝。3200CB

XB

b

x1x2x3x40x3921109/20x414230114/2-Z032003200CB

XB

b

x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解:用單純形法解對應(yīng)的(LP)問題,獲得最優(yōu)解。初始表最終表例1

、用分枝定界法求解整數(shù)規(guī)劃問題（單純形法）x1=13/4

x2=5/2Z(0)=59/4≈14.75,選x2進(jìn)行分枝，即增加兩個(gè)約束，2≥x2

，x2≥3有下式：分別在(LP1)和(LP2)中引入松弛變量x5和x6

，將新加約束條件加入上表計(jì)算。即x2+x5=2,－x2+x6=－3

得下表:3200CB

XB

b

x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/432000CB

XB

b

x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x5201001-Z-59/400-5/4-1/4032000CB

XB

b

x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x5-1/2001/2-1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010x4100-11-2-Z-29/200-3/20-1/2x1=7/2,x2=2Z(1)=29/2=14.5，LP13200CB

XB

b

x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/432000CB

XB

b

x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/4032000CB

XB

b

x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/40LP2x1=5/2,x2=3Z(2)=27/2=13.5，∵Z(2)<Z(1)∴先不考慮分枝。3x113/4103/4-1/402x25/201-1/21/200x6-1/200-1/21/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10x31001-1-2-Z-27/2000-3/2-5/2接(LP1)繼續(xù)分枝，加入約束4≤x1,

x1≤3,有下式：分別引入松弛變量x7和x8，然后進(jìn)行計(jì)算。32000CB

XB

b

x1x2x3x4x53x17/2101/20-1/22x22010010x4100-11-2-Z-29/200-3/20-1/2CB

XB

b

x1x2x3x4x5x73x17/2101/20-1/202x220100100x4100-11-200x73100001-Z-29/200-3/20-1/20CB

XB

b

x1x2x3x4x5x73x17/2101/20-1/202x220100100x4100-11-200x73100001-Z-29/200-3/20-1/20

x1=3,x2=2Z(3)=13找到整數(shù)解，問題已探明，停止計(jì)算。LP33x17/2101/20-1/202x220100100x4100-11-200x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100x420001-3-20x310010-1-2-Z-130000-2-3CB

XB

b

x1x2x3x4x5x83x17/2101/20-1/202x220100100x4100-11-200x8-4-100001-Z-29/200-3/20-1/20

x1=4,x2=1Z(4)=14找到整數(shù)解，問題已探明，停止計(jì)算。LP43x17/2101/20-1/202x220100100x4100-11-200x8-1/2001/20-1/21-Z-29/200-3/20-1/203x1410000-12x210110020x4300-310-40x5100-101-2-Z-1400-200-1Lingo求解樹形圖如下：LPx1=13/4,x2=5/2Z(0)

＝59/4=14.75LP2x1=5/2,x2=3Z(2)＝27/2=13.5LP3x1=3,x2=2Z(3)

＝13LP4x1=4,x2=1Z(4)

＝14x2≤2x2≥3x1≤3x1≥4＃＃＃LP1x1=7/2,x2=2Z(1)＝29/2=14.5例2.用分枝定界法求解整數(shù)規(guī)劃問題（用圖解法計(jì)算）記為（IP）解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題記為（LP）用圖解法求（LP）的最優(yōu)解，如圖所示。x1x2⑴⑵33(18/11,40/11)⑶對于x1＝18/11≈1.64，取值x1≤1，x1≥2，先將（LP）劃分為（LP1）和（LP2）,取x1≤1,x1≥2。

x1＝18/11,x2=40/11Z(0)=－218/11≈(－19.8)即Z也是(IP)最小值的下限。有下式：現(xiàn)在只要求出(LP1)和(LP2)的最優(yōu)解即可。x1x2⑴⑵33⑶

先求（LP1）,如圖所示。此時(shí)B

在點(diǎn)取得最優(yōu)解。x1＝1,x2=3,Z(1)=-16找到整數(shù)解，問題已探明，此枝停止計(jì)算。11同理求（LP2）

,如圖所示。在C

點(diǎn)取得最優(yōu)解。即x1＝2,x2=10/3,Z(2)=-56/3≈-18.7∵Z2<Z1＝－16∴原問題有比(-16)更小的最優(yōu)解，但x2不是整數(shù)，故利用4≥10/3≥3加入條件。BAC加入條件：x2≤3,x2≥4有下式：只要求出（LP3）和（LP4）的最優(yōu)解即可。x1x2⑴⑵33⑶11BAC先求（LP3）,如圖所示。此時(shí)D在點(diǎn)取得最優(yōu)解。即x1＝12/5≈2.4,x2=3,Z(3)＝-87/5≈-17.4>Z≈-19.8但x1＝12/5不是整數(shù)，可繼續(xù)分枝。即3≤x1≤2。D求（LP4），如圖所示。無可行解，不再分枝。在(LP3)的基礎(chǔ)上繼續(xù)分枝。加入條件3≤x1,x1≤2。只要求出（LP5）和（LP6）的最優(yōu)解即可。x1x2⑴⑵33⑶11BACD先求（LP5）,如圖所示。此時(shí)E

在點(diǎn)取得最優(yōu)解。即x1＝2,x2=3,Z(5)＝－17找到整數(shù)解，問題已探明，此枝停止計(jì)算。E求（LP6），如圖所示。此時(shí)

F在點(diǎn)取得最優(yōu)解。x1＝3,x2=2.5,Z(6)＝－31/2≈－15.5>Z(5)

F如對Z(6)

繼續(xù)分解，其最小值也不會(huì)低于-15.5，問題探明,剪枝。至此，原問題（IP）的最優(yōu)解為：

x1=2，

x2=3,

Z*=Z(5)

＝-17以上的求解過程可以用一個(gè)樹形圖表示如右：LP1x1=1,x2=3Z(1)

＝－16LPx1=18/11,x2=40/11Z(0)

＝－19.8LP2x1=2,x2=10/3Z(2)

＝－18.5LP3x1=12/5,x2=3Z(3)

＝－17.4LP4無可行解LP5x1=2,x2=3Z(5)

＝－17LP6x1=3,x2=5/2Z(6)

＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃Lingo求解練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問題

（圖解法）

LP1x1=1,x2=7/3Z(1)

＝10/3LPx1=3/2,x2=10/3Z(0)

＝29/6LP2x1=2,x2=23/9Z(2)

＝41/9x1≤1x1≥2LP3x1=33/14,x2=2Z(3)

＝61/14LP4無可行解x2≤2x2≥3＃LP7x1=2,x2=2Z(7)

＝4LP8x1=3,x2=1Z(8)

＝4x1≤2x1≥3＃＃LP1x1=1,x2=7/3Z(1)

＝10/3LPx1=3/2,x2=10/3Z(0)

＝29/6LP2x1=2,x2=23/9Z(2)

＝41/9x1≤1x1≥2LP5x1=1,x2=2Z(5)

＝3LP6無可行解＃＃x2≤2x2≥3LP3x1=33/14,x2=2Z(3)

＝61/14LP4無可行解x2≤2x2≥3＃LP7x1=2,x2=2Z(7)

＝4LP8x1=3,x2=1Z(8)

＝4x1≤2x1≥3＃＃Lingo求解練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問題

（單純形法）LP1x1=1,x2=3Z(1)

＝－16LPx1=18/11,x2=40/11Z(0)

＝－19.8LP2x1=2,x2=10/3Z(2)

＝－18.5LP3x1=12/5,x2=3Z(3)

＝－17.4LP4無可行解LP5x1=2,x2=3Z(5)

＝－17LP6x1=3,x2=5/2Z(6)

＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃Lingo求解（一）、計(jì)算步驟：1、用單純形法求解(IP)對應(yīng)的松弛問題(LP)：⑴.若(LP)沒有可行解，則(IP)也沒有可行解，停止計(jì)算。

⑵.若(LP)有最優(yōu)解，并符合(IP)的整數(shù)條件，則(LP)的最優(yōu)解即為(IP)的最優(yōu)解，停止計(jì)算。

⑶.若(LP)有最優(yōu)解，但不符合(IP)的整數(shù)條件，轉(zhuǎn)入下一步。第四節(jié)割平面法

2、從(LP)的最優(yōu)解中，任選一個(gè)不為整數(shù)的分量xr,,將最優(yōu)單純形表中該行的系數(shù)和分解為整數(shù)部分和小數(shù)部分之和，并以該行為源行，按下式作割平面方程：

3、將所得的割平面方程作為一個(gè)新的約束條件置于最優(yōu)單純形表中（同時(shí)增加一個(gè)單位列向量），用對偶單純形法求出新的最優(yōu)解，返回1。的小數(shù)部分的小數(shù)部分例1：用割平面法求解整數(shù)規(guī)劃問題解：增加松弛變量x3和x4

，得到(LP)的初始單純形表和最優(yōu)單純形表：Cj0100CBXBbx1x2x3x40x3632100x40-3201－Z00100Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4－Z-3/200-1/4-1/4此題的最優(yōu)解為：X＊=(1,3/2)，Z=3/2，但不是整數(shù)最優(yōu)解，引入割平面。也即：以x2為源行生成割平面，將所需要的數(shù)分解為整數(shù)和分?jǐn)?shù)，由于1/4=0+1/4,3/2=1+1/2,所以有：整數(shù)所以:帶入，得到等價(jià)的割平面條件：x2≤

1見右圖。由x3=6-3x1-2x2

,x4=3x1-2x2得x1x2⑴⑵33第一個(gè)割平面Cj01000CBXBbx1x2x3x4s10x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41－Z-3/200-1/4-1/40將生成的割平面條件加入松弛變量，然后加到表中：CBXBbx1x2x3x4s10x12/3100-1/32/31x21010010x320011-4－Z-10000-1此時(shí)，X1

＝(2/3,1),Z=1,仍不是整數(shù)解。繼續(xù)以x1為源行生成割平面，其條件為：用上表的約束解出x4和s1，將它們帶入上式得到等價(jià)的割平面條件：x1≥x2，見圖：x1x2⑴⑵33第一個(gè)割平面第二個(gè)割平面將生成的割平面條件加入松弛變量，然后加到表中：CBXBbx1x2x3x4s1s20x12/3100-1/32/301x210100100x320011-400s2-2/3000-2/3-2/31－Z-10000-10CBXBbx1x2x3x4s1s20x10100-1011x20010-103/20x3600150-60s1100011-3/2－Z000010-3/2CBXBbx1x2x3x4s1s20x1110001-1/21x210100100x310010-53/20x4100011-3/2－Z-10000-10至此得到最優(yōu)表，其最優(yōu)解為X＊=(1,1),Z=1,這也是原問題的最優(yōu)解。由以上解題過程可見，表中含有分?jǐn)?shù)元素且算法過程中始終保持對偶可行性，因此，這個(gè)算法也稱為分?jǐn)?shù)對偶割平面算法。例2：用割平面法求解數(shù)規(guī)劃問題Cj1100CBXBbx1x2x3x40x3621100x4204501－Z1100初始表最優(yōu)表CBXBbx1x2x3x41

x15/3105/6－1/61x28/301－2/31/3－Z-13/300－1/6－1/6在松弛問題最優(yōu)解中，x1,x2均為非整數(shù)解，由上表有：將系數(shù)和常數(shù)都分解成整數(shù)和非負(fù)真分?jǐn)?shù)之和以上式子只須考慮一個(gè)即可，解題經(jīng)驗(yàn)表明，考慮式子右端最大真分?jǐn)?shù)的式子，往往會(huì)較快地找到所需割平面約束條件。以上兩個(gè)式子右端真分?jǐn)?shù)相等，可任選一個(gè)考慮。現(xiàn)選第二個(gè)式子，并將真分?jǐn)?shù)移到右邊得：引入松弛變量s1后得到下式，將此約束條件加到上表中，繼續(xù)求解。Cj11000CBXBbx1x2x3x4s11

x15/3105/6-1/601x28/301-2/31/300s1-2/300-1/3-1/31－Z-13/300-1/6-1/60得到整數(shù)最優(yōu)解，即為整數(shù)規(guī)劃的最優(yōu)解，而且此整數(shù)規(guī)劃有兩個(gè)最優(yōu)解：X＊=(0,4),Z=4,Cj11000CBXBbx1x2x3x4s11

x10100-101x240101-20x320011-3－Z-40000－1/2練習(xí)：?????íì3￡-￡+￡+-+=且為整數(shù)0,421625421411max2121212121xxxxxxxxxxZCBXBbx1x2x3x4x50x34001-1/34/34x24/30102/9-5/911x18/31001/92/9－Z000-19/9-2/9（2，3）CBXBbx1x2x3x4x5s10x30001-1064x230101/20-5/211x121000010x530001/21-9/2－Z000-20-1計(jì)算軟件整數(shù)變量定義LinGo

一般整數(shù)變量:@GIN(variable_name);0-1整數(shù)變量：@BIN(variable_name);算例

max3x1+5x2+4x3subjectto2x1+3x2<=15002x2+4x3<=8003x1+2x2+5x3<=2000endginx1ginx3

model:max=3*x1+5*x2+4*x3;2*x1+3*x2<=1500;2*x2+4*x3<=800;3*x1+2*x2+5*x3<=2000;@gin(x1);@gin(x3);endGlobaloptimalsolutionfoundatiteration:3Objectivevalue:2675.000VariableValueReducedCostX1375.00000.3333333X2250.00000.000000X375.00000-4.000000

第五節(jié)應(yīng)用案例例l.分配甲、乙、丙、丁四個(gè)人去完成5項(xiàng)工作，每人完成各項(xiàng)工作所需的時(shí)間見表

。由于工作數(shù)多于人數(shù)，故規(guī)定其中有一個(gè)人可兼顧完成兩項(xiàng)工作，其余3人每人完成一項(xiàng)。試確定總的花費(fèi)時(shí)間為最少的指派方案。工作人ABCDE甲2529314237乙3938262033丙3427284032丁3442362345解：此問題為人數(shù)與任務(wù)數(shù)不等的分配問題，由于任務(wù)數(shù)比人數(shù)多1，因此需要有一個(gè)假想的人去完成某一項(xiàng)工作。根據(jù)題中的要求，這個(gè)假想的人就是甲、乙、丙、丁四個(gè)人中的某一個(gè)，因此這時(shí)假想人完成每項(xiàng)工作所用的時(shí)間不能為零。由于要求總的花費(fèi)時(shí)間最少．因此這個(gè)假想人完成各項(xiàng)工作所需要的時(shí)間應(yīng)該取甲、乙、丙、丁中的最小者．假設(shè)第五個(gè)人是戊，則新的效率矩陣見表。工作人ABCDE甲2529314237乙3938262033丙3427284032丁3442362345工作人ABCDE甲2529314237乙3938262033丙3427284032丁3442362345戊2527262032得到如下的新效率表工作人ABCDE甲2529314237乙3938262033丙3427284032丁3442362345戊2527262032利用匈牙利法，可以得到最優(yōu)分配方案為：甲完成A，乙完成C，丙完成B和E，丁完成D，需要133h.Lingo求解例2.要從甲、乙、丙、丁、戊五人中挑選4個(gè)人去完成4項(xiàng)工作。己知每人完成各項(xiàng)工作的時(shí)間見表。規(guī)定每項(xiàng)工作只能由一個(gè)人單獨(dú)去完成，每個(gè)人最多承擔(dān)一項(xiàng)任務(wù)．又假設(shè)對甲必須保證分配一項(xiàng)任務(wù)，丁因某種原因決定不同意承擔(dān)第4項(xiàng)任務(wù)，在滿足上述條件下，如何分配工作使完成4項(xiàng)工作總的花費(fèi)時(shí)間最少。工作人ABCDE甲1051520M乙2105150丙31514130丁152760戊941580M工作人ABCDE甲1051520M乙2105150丙31514130丁1527M0戊941580應(yīng)用匈牙利法可以得到最優(yōu)分配為：甲完成B，乙完成C，丙完成A，戊完成D，需要21h.Lingo求解例3

某部隊(duì)后勤值班室準(zhǔn)備聘用4名兼職值班員(代號(hào)1,2,3,4)和2名兼職帶班員(代號(hào)5,6)。已知每人從周一至周日每天最多可安排的值班時(shí)間及每人每h值班的報(bào)酬如下表所示：該值班室每天值班時(shí)間為上午8:00至晚上22:00,值班時(shí)間內(nèi)須有且僅須一名值班員值班.要求兼職值班員每周值班不少于10h,兼職帶班員每周不少于8h,每名值班員每周值班不超過4次,每次值班不少于2h,每天安排值班員不超過3人,且其中必須有一名兼職帶班員,試為該值班室安排一張人員的值班表，使總支付的報(bào)酬為最少．值班員代號(hào)報(bào)酬元/h每天最多可安排的值班時(shí)間周一周二周三周四周五周六周日110.060607120210.0060600123948305121249556040125153048012061606063012(1)該值班室值班時(shí)間為上午8:00至22:00,值班時(shí)間內(nèi)須有且僅須一名值班員值班.(2)規(guī)定值班員每周值班不少于10h,(3)帶班員每周不少于8h,(4)每名值班員每周值班不超過4次,(5)每次值班不少于2h,(6)每天安排值班的學(xué)生不超過3人,(7)其中必須有帶班員,設(shè)xij為值班員i在周j值班時(shí)間

1,安排值班員i在周j值班yij=

0,否則(1)(2)(3)(4)(5)(6)(7)值班代號(hào)報(bào)酬元/h每天最多可安排的值班時(shí)間周一周二周三周四周五周六周日11060607120210060600123948305121249556040125153048012061606063012aij為值班員i在周j的最多可值班時(shí)間得到數(shù)學(xué)模型為：

1,安排學(xué)生i在周j值班yij=

0,否則設(shè)xij為值班員i在周j值班時(shí)間Lingo求解程序Sets:num_i/1..6/:c; num_j/1..7; link(num_i,num_j):a,x,y;num_k/1..4/; endsetsdata: c=10,10,9,9,15,16;a=6,0,6,0,7,12,0,0,6,0,6,0,0,12,4,8,3,0,5,12,12,5,5,6,0,4,0,12,3,0,4,8,0,12,0,0,6,0,6,3,0,12; enddatamin=@sum(link(i,j):c(i)*x(i,j));@for(num_j(j):@sum(num_i(i):x(i,j))=14;);@for(num_k(k):@sum(num_j(j):x(k,j))>=10;);@sum(num_j(j):x(5,j))>=8;@sum(num_j(j):x(6,j))>=8;@for(num_i(i):@sum(num_j(j):y(i,j))<=4;);@for(num_j(j):@sum(num_i(i):y(i,j))<=3;);@for(num_j(j):y(5,j)+y(6,j)>=1;);@for(link(i,j):2*y(i,j)<=x(i,j)<=a(i,j)*y(i,j););//換成兩個(gè)不等式@for(link(i,j):@gin(y(i,j));y(i,j)>=0;);@for(link(i,j):@gin(x(i,j));x(i,j)>=0;);例4

東方大學(xué)計(jì)算機(jī)實(shí)驗(yàn)室聘用4名大學(xué)生(代號(hào)1,2,3,4)和2名研究生(代號(hào)5,6)值班答疑.已知每人從周一至周五每天最多可安排的值班時(shí)間及每人每h值班的報(bào)酬如下表所示：該實(shí)驗(yàn)室開放時(shí)間為上午8:00至晚上10:00,開放時(shí)間內(nèi)須有且僅須一名學(xué)生值班.規(guī)定大學(xué)生每周值班不少于8h,研究生每周不少于7h,每名學(xué)生每周值班不超過3次,每次值班不少于7h,每天安排值班的學(xué)生不超過3人,且其中必須有一名研究生,試為該實(shí)驗(yàn)室安排一張人員的值班表，使總支付的報(bào)酬為最少．學(xué)生代號(hào)報(bào)酬元/h每天最多可安排的值班時(shí)間周一周二周三周四周五110.060607210.00606039.94830549.855604510.830480611.306063學(xué)生代號(hào)報(bào)酬元/h每天最多可安排的值班時(shí)間周一周二周三周四周五110.060607210.00606039.94830549.855604510.830480611.306063(1)該實(shí)驗(yàn)室開放時(shí)間為上午8:00至晚上10:00,開放時(shí)間內(nèi)須有且僅須一名學(xué)生值班.(2)規(guī)定大學(xué)生每周值班不少于8h,(3)研究生每周不少于7h,(4)每名學(xué)生每周值班不超過3次,(5)每次值班不少于2h,(6)每天安排值班的學(xué)生不超過3人,(7)其中必須有一名研究生,設(shè)xij為學(xué)生i在周j值班時(shí)間

1,安排學(xué)生i在周j值班yij=

0,否則(1)(2)(3)(4)(5)(6)(7)得到數(shù)學(xué)模型為：設(shè)xij為學(xué)生i在周j值班時(shí)間

1,安排學(xué)生i在周j值班yij=

0,否則Lingo