運籌學課件整形規(guī)劃問題幻燈片

第八章整數(shù)規(guī)劃（IP）(IntegerProgramming)整數(shù)規(guī)劃的模型整數(shù)規(guī)劃的應(yīng)用（指派問題）整數(shù)規(guī)劃的計算機求解（一）、整數(shù)規(guī)劃問題實例一、整數(shù)規(guī)劃的模型1.1問題的提出例1：某公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨物每件的體積、重量，可獲利潤以及托運所受限制如表1所示：甲種貨物至多托運4件。問：兩種貨物各托運多少件，可使獲得利潤最大？？？貨物每件體積（立方英尺）每件重量（百千克）每件利潤（百元）甲乙19527344023托運限制1365

140

規(guī)劃模型：（二）、整數(shù)規(guī)劃的數(shù)學模型一般形式

依照決策變量取整要求的不同，整數(shù)規(guī)劃可分為純整數(shù)規(guī)劃、全整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、0－1整數(shù)規(guī)劃。

純整數(shù)規(guī)劃：所有決策變量要求取非負整數(shù)（這時引進的松弛變量和剩余變量可以不要求取整數(shù)）。

全整數(shù)規(guī)劃：除了所有決策變量要求取非負整數(shù)外，系數(shù)aij和常數(shù)bi也要求取整數(shù)（這時引進的松弛變量和剩余變量也必須是整數(shù)）。

混合整數(shù)規(guī)劃：只有一部分的決策變量要求取非負整數(shù)，另一部分可以取非負實數(shù)。0－1整數(shù)規(guī)劃：所有決策變量只能取0或1兩個整數(shù)。例：設(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個點即(1，3)(2，3)(1，4)(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。

按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點。故整數(shù)規(guī)劃問題的可行解集是一個有限集，如圖所示。圖整數(shù)規(guī)劃的解是可數(shù)個的，最優(yōu)解不一定發(fā)生在頂點。整數(shù)規(guī)劃的最優(yōu)解不會優(yōu)于其對應(yīng)線性規(guī)劃問題的最優(yōu)解。（定理）

因此，可將集合內(nèi)的整數(shù)點一一找出，其最大目標函數(shù)的值為最優(yōu)解，此法為完全枚舉法。如上例：其中（2，2）（3，1）點為最大值，Z=4。

目前，常用的求解整數(shù)規(guī)劃的方法有：

分支定界法和割平面法（不作為課堂授課內(nèi)容）；對于特別的0－1規(guī)劃問題采用隱枚舉法和匈牙利法。四、整數(shù)規(guī)劃問題計算機求解(P165)例2：

Maxz=3x1+x2+3x3

s.t.-x1+2x2+x3≤44x2-3x3≤2

x1-3x2+2x3≤3x1,x2,x3≥0為整數(shù)用《管理運籌學》軟件求解得：

x1=5x2=2x3=2四、整數(shù)規(guī)劃問題計算機求解(P165)例3：

Maxz=3x1+x2+3x3

s.t.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x3≤1x1,x2,x3≥0x1，x3

為整數(shù)

x3

為0-1變量用《管理運籌學》軟件求解得：

x1=4x2=1.25x3=1z=16.25§8.3整數(shù)規(guī)劃的應(yīng)用投資場所的選擇。例4固定成本問題。例5指派問題（分配問題）。例6分布系統(tǒng)設(shè)計。例7投資問題。例8例4、京成畜產(chǎn)品公司計劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有10個位置Aj(j＝1，2，3，…，10)可供選擇，考慮到各地區(qū)居民的消費水平及居民居住密集度，規(guī)定：在東區(qū)由A1

，A2

，A3三個點至多選擇兩個；在西區(qū)由A4

，A5兩個點中至少選一個；在南區(qū)由A6

，A7兩個點中至少選一個；在北區(qū)由A8

，A9

，A10

三個點中至少選兩個。

Aj

各點的設(shè)備投資及每年可獲利潤由于地點不同都是不一樣的，預(yù)測情況見表所示(單位：萬元)。但投資總額不能超過720萬元，問應(yīng)選擇哪幾個銷售點，可使年利潤為最大?五、投資場所的選擇。例4(P166)解：設(shè)：0--1變量xi

=1(Ai點被選用）或0(Ai點沒被選用）。這樣我們可建立如下的數(shù)學模型：Maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.t.100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤720

x1+x2+x3≤2

x4+x5≥1

x6+x7≥1

x8+x9+x10≥2

xi≥0

且xi

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

在實際中經(jīng)常會遇到這樣的問題，有n項不同的任務(wù)，需要n個人分別完成其中的一項，但由于任務(wù)的性質(zhì)和各人的專長不同，因此各人去完成不同的任務(wù)的效率（或花費的時間或費用）也就不同。于是產(chǎn)生了一個問題，應(yīng)指派哪個人去完成哪項任務(wù)，使完成n項任務(wù)的總效率最高（或所需時間最少），這類問題稱為指派問題或分派問題。

（一）、指派問題的數(shù)學模型設(shè)n個人被分配去做n件工作，規(guī)定每個人只做一件工作，每件工作只有一個人去做。已知第i個人去做第j件工作的的效率（時間或費用）為Cij(i=1.2…n;j=1.2…n)并假設(shè)Cij≥0。問應(yīng)如何分配才能使總效率（時間或費用）最高？六、指派問題指派問題是0—1規(guī)劃的特例。庫恩（ww.kuhn）于1955年提出了指派問題的解法。他引用了匈牙利數(shù)學家康尼格一個關(guān)于矩陣中0元素的定理，所以把這解法稱為匈牙利法。以后在方法上雖有不斷改進，但仍沿用這名稱。例6．有四個工人，要分別指派他們完成四項不同的工作，每人做各項工作所消耗的時間如下表所示，問應(yīng)如何指派工作，才能使總的消耗時間為最少。解：引入0—1變量xij，并令

xij=1(當指派第i人去完成第j項工作時)或0（當不指派第i人去完成第j項工作時)．這可以表示為一個0--1整數(shù)規(guī)劃問題：Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1(甲只能干一項工作)

x21+x22+x23+x24=1(乙只能干一項工作)

x31+x32+x33+x34=1(丙只能干一項工作)

x41+x42+x43+x44=1(丁只能干一項工作)

x11+x21+x31+x41=1(A工作只能一人干)

x12+x22+x32+x42=1(B工作只能一人干)

x13+x23+x33+x43=1(C工作只能一人干)

x14+x24+x34+x44=1(D工作只能一人干)

xij

為0--1變量，i,j=1,2,3,4***求解可用《管理運籌學》軟件中整數(shù)規(guī)劃方法。設(shè)決策變量1分配第i個人去做第j件工作

xij=0相反(I,j=1.2.…n)其數(shù)學模型為：

（二）匈牙利法解題步驟（補充，重點）

指派問題是0-1規(guī)劃的特例，也是運輸問題的特例，當然可用整數(shù)規(guī)劃，0-1規(guī)劃或運輸問題的解法去求解，這就如同用單純型法求解運輸問題一樣是不合算的。利用指派問題的特點可有更簡便的解法，這就是匈牙利法，即系數(shù)矩陣中獨立0元素的最多個數(shù)等于能覆蓋所有0元素的最少直線數(shù)。

第一步：變換指派問題的系數(shù)矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即

(1)從（cij）的每行元素都減去該行的最小元素；

(2)再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。

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

(1)從只有一個0元素的行(列)開始，給這個0元素加圈，記作◎。然后劃去◎所在列(行)的其它0元素，記作?；這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。

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

(3)反復(fù)進行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。(4)若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個，則從剩有0元素最少的行(列)開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素。可反復(fù)進行，直到所有0元素都已圈出和劃掉為止。

（5）若◎元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問題的最優(yōu)解已得到。若m<n,則轉(zhuǎn)入下一步。

第三步：作最少的直線覆蓋所有0元素。

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

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

(3)再對打有√號的列中含◎元素的行打√號；(4)重復(fù)(2)，(3)直到得不出新的打√號的行、列為止；

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

任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119249742◎?◎??◎◎

甲、乙、丙、丁四個人加工A、B、C、D四種工件所需時間（單位：min）如表所示。應(yīng)指派何人加工何種工件，能使總的加工時間最少？

工件人員ABCD甲149415乙117910丙132105丁1791513例二、指派問題是0—1規(guī)劃的特例。庫恩（ww.kuhn）于1955年提出了指派問題的解法。他引用了匈牙利數(shù)學家康尼格一個關(guān)于矩陣中0元素的定理，所以把這解法稱為匈牙利法。以后在方法上雖有不斷改進，但仍沿用這名稱。

有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，問如何分派任務(wù)，可使總時間最少？

任務(wù)人員ABCD甲67112乙4598丙31104丁5982例二、求解過程如下：第一步，變換系數(shù)矩陣：－5第二步，試指派：

找到3個獨立零元素但m=3<n=

4◎◎◎??

第三步，作最少的直線覆蓋所有0元素：

◎◎◎??√√√獨立零元素的個數(shù)m等于最少直線數(shù)l，即l＝m=3<n=4；

第四步，變換矩陣(bij)以增加0元素：沒有被直線覆蓋的所有元素中的最小元素為1，然后打√各行都減去1；打√各列都加上1，得如下矩陣，并轉(zhuǎn)第二步進行試指派：第三步：作最少的直線覆蓋所有0元素。

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

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

(3)再對打有√號的列中含◎元素的行打√號；(4)重復(fù)(2)，(3)直到得不出新的打√號的行、列為止；

(5)對沒有打√號的行畫橫線，有打√號的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù)l

。000000得到4個獨立零元素，所以最優(yōu)解矩陣為：

◎◎◎??√√√◎◎◎??15◎◎◎??◎第四步，變換矩陣(bij)以增加0元素：沒有被直線覆蓋的所有元素中的最小元素為1，然后打√各行都減去1；打√各列都加上1，得如下矩陣，并轉(zhuǎn)第二步進行試指派：

已知下列五名運動員各種姿勢的游泳成績（各為50米），如表所示，試問如何從中選拔一個參加200米混合泳的接力隊，使預(yù)期比賽成績?yōu)樽詈?。單位：?/p>

任務(wù)人員ABCD甲37.743.433.329.2乙32.924.738.926.4丙33.842.228.529.6丁37.033.130.428.5例三、戊35.441.833.631.1第一步：增加一種泳姿，各位運動員的成績均為零，得方陣：

分配甲、乙、丙、丁四個人去完成五項任務(wù)。每人完成各項任務(wù)時間如表所示。由于任務(wù)數(shù)多于人數(shù)，故規(guī)定其中有一個人可兼完成兩項任務(wù)，其余三人每人完成一項，試確定總花費時間為最少的指派方案。

任務(wù)人員ABCD甲25293143乙38372520丙37272840丁44413523例二、E37323223

任務(wù)人員ABCD甲25293143乙38372520丙37272840丁44413523E37323223◎?◎??◎?◎?◎從甲、乙、丙、丁、戊五人中挑選四人去完成四項任務(wù)。每人完成各項任務(wù)時間如表所示。規(guī)定每項工作只能由一個人去單獨完成，每個人最多承擔一項任務(wù)。又假定對甲必須保證分配一項任務(wù)，丁因為某種原因決定不同意承擔第4項任務(wù)。在滿足上述條件下，如何分配工作，使完成四項工作所花費時間為最少。

任務(wù)人員ABCD甲1051520乙210515丙2151413丁15276例三、戊94158-2-5先增加一種假想工作5，再據(jù)題中給的條件列出矩陣：-8

任務(wù)人員ABCD甲20192028乙18242720丙26161518丁17202419例四、P182（6）（2）如果把消耗時間數(shù)據(jù)看成創(chuàng)造效益的數(shù)據(jù)，那么應(yīng)如何指派，可使得總的效益最大？解決辦法：轉(zhuǎn)化成最小化問題，找出最大元素，用最大元素分別減去表中各元素求解。

任務(wù)人員ABCD甲20192028乙18242720丙26161518丁17202419例四、P182（6）（4）如果再增加一個人戊，他完成A，B，C，D的時間分別為16，17，20，21分鐘，這時應(yīng)指派哪四個人去干這四項工作，使得消耗時間最少？要求建立模型：解：引入0—1變量xij，并令

xij=1(當指派第i人去完成第j項工作時)或0（當不指派第i人去完成第j項工作時)．這可以表示為一個0--1整數(shù)規(guī)劃問題：Minz=20x11+19x12+20x13+28x14+18x21+24x22+27x23+20x24+26x31+16x32+15x33+18x34+17x41+20x42+2443+19x44+16x51+17x52+2053+21x54s.t.x11+x12+x13+x14≤1(甲最多只能干一項工作)

x21+x22+x23+x24≤1(乙最多只能干一項工作)