整數(shù)規(guī)劃(整數(shù)規(guī)劃)

想一想：在生產(chǎn)管理和經(jīng)營(yíng)活動(dòng)中若要求解：安排上班的人數(shù)運(yùn)輸車輛臺(tái)數(shù)第八章整數(shù)規(guī)劃（IP）(IntegerProgramming)§1整數(shù)規(guī)劃的模型（掌握）§3整數(shù)規(guī)劃的應(yīng)用（掌握）（補(bǔ)充指派問(wèn)題的匈牙利解法）§2整數(shù)規(guī)劃的計(jì)算機(jī)求解（掌握）主要內(nèi)容：一、整數(shù)規(guī)劃的模型（一）整數(shù)規(guī)劃實(shí)例例1：某公司擬用集裝箱托運(yùn)甲、乙兩種貨物，這兩種貨物每件的體積、重量，可獲利潤(rùn)以及托運(yùn)所受限制如表所示：甲種貨物至多托運(yùn)4件。問(wèn)：兩種貨物各托運(yùn)多少件，可使獲得利潤(rùn)最大？？？貨物每件體積（立方英尺）每件重量（百千克）每件利潤(rùn)（百元）甲乙19527344023托運(yùn)限制1365140規(guī)劃模型：貨物每件體積每件重量每件利潤(rùn)甲乙19527344023托運(yùn)限制1365140（二）整數(shù)規(guī)劃的一般數(shù)學(xué)模型一般形式

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

純整數(shù)規(guī)劃：所有決策變量要求取非負(fù)整數(shù)。

全整數(shù)規(guī)劃：除了所有決策變量要求取非負(fù)整數(shù)外，技術(shù)系數(shù)aij和常數(shù)bi也要求取整數(shù)。

混合整數(shù)規(guī)劃：只有一部分的決策變量要求取非負(fù)整數(shù)，另一部分可以取非負(fù)實(shí)數(shù)。0－1整數(shù)規(guī)劃：所有決策變量只能取0或1兩個(gè)整數(shù)。

對(duì)整數(shù)規(guī)劃問(wèn)題，先按線性規(guī)劃問(wèn)題（不受整數(shù)約束）求解，然后“舍入化整”，就可得到整數(shù)最優(yōu)解，可以嗎？想一想：（三）整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系

從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的基礎(chǔ)上，通過(guò)舍入取整，尋求滿足整數(shù)要求的解即可。但實(shí)際上兩者卻有很大的不同，通過(guò)舍入得到的解（整數(shù)）也不一定就是最優(yōu)解，有時(shí)甚至不能保證所得的解是整數(shù)可行解。舉例說(shuō)明。例：設(shè)整數(shù)規(guī)劃問(wèn)題如下

首先不考慮整數(shù)約束，得到線性規(guī)劃問(wèn)題。用解法求出最優(yōu)解x1＝3/2,x2=10/3且有MaxZ=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ī)劃問(wèn)題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問(wèn)題的可行解集是一個(gè)有限集，如圖所示。圖1.整數(shù)規(guī)劃的解是可數(shù)個(gè)的，最優(yōu)解不一定發(fā)生在頂點(diǎn)。2.整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于其對(duì)應(yīng)線性規(guī)劃問(wèn)題的最優(yōu)解。（定理）重點(diǎn)

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

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

分支定界法和割平面法（不作為課堂授課內(nèi)容）；對(duì)于特別的0－1規(guī)劃問(wèn)題采用隱枚舉法和匈牙利法。

在實(shí)際中經(jīng)常會(huì)遇到這樣的問(wèn)題，有n項(xiàng)不同的任務(wù)，需要n個(gè)人分別完成其中的一項(xiàng)，但由于任務(wù)的性質(zhì)和各人的專長(zhǎng)不同，因此各人去完成不同的任務(wù)的效率（或花費(fèi)的時(shí)間或費(fèi)用）也就不同。于是產(chǎn)生了一個(gè)問(wèn)題，應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成n項(xiàng)任務(wù)的總效率最高（或所需時(shí)間最少），這類問(wèn)題稱為指派問(wèn)題或分派問(wèn)題。二、指派問(wèn)題（匈牙利法）指派問(wèn)題是0—1規(guī)劃的特例。庫(kù)恩（ww.kuhn）于1955年提出了指派問(wèn)題的解法。他引用了匈牙利數(shù)學(xué)家康尼格一個(gè)關(guān)于矩陣中0元素的定理，所以把這解法稱為匈牙利法。以后在方法上雖有不斷改進(jìn)，但仍沿用這名稱。四、整數(shù)規(guī)劃問(wèn)題計(jì)算機(jī)求解(P165)例2：

Maxz=3x1+x2+3x3

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

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

x1=5x2=2x3=2四、整數(shù)規(guī)劃問(wèn)題計(jì)算機(jī)求解(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變量用《管理運(yùn)籌學(xué)》軟件求解得：

x1=4x2=1.25x3=1z=16.25§8.3整數(shù)規(guī)劃的應(yīng)用投資場(chǎng)所的選擇。例4固定成本問(wèn)題。例5指派問(wèn)題（分配問(wèn)題）。例6分布系統(tǒng)設(shè)計(jì)。例7投資問(wèn)題。例8例4、京成畜產(chǎn)品公司計(jì)劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有10個(gè)位置Aj

(j＝1，2，3，…，10)可供選擇，考慮到各地區(qū)居民的消費(fèi)水平及居民居住密集度，規(guī)定：在東區(qū)由A1

，A2

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

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

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

，A9

，A10

三個(gè)點(diǎn)中至少選兩個(gè)。

Aj

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

=1(Ai點(diǎn)被選用）或0(Ai點(diǎn)沒(méi)被選用）。這樣我們可建立如下的數(shù)學(xué)模型：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例4、京成畜產(chǎn)品公司計(jì)劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有10個(gè)位置Aj

(j＝1，2，3，…，10)可供選擇，考慮到各地區(qū)居民的消費(fèi)水平及居民居住密集度，規(guī)定：在東區(qū)由A1

，A2

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

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

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

，A9

，A10

三個(gè)點(diǎn)中至少選兩個(gè)。

Aj

各點(diǎn)的設(shè)備投資及每年可獲利潤(rùn)由于地點(diǎn)不同都是不一樣的，預(yù)測(cè)情況見(jiàn)表所示(單位：萬(wàn)元)。但投資總額不能超過(guò)720萬(wàn)元，問(wèn)應(yīng)選擇哪幾個(gè)銷售點(diǎn)，可使年利潤(rùn)為最大?在西區(qū)由A4

，A5兩個(gè)點(diǎn)或者都選，或者都不選。五、投資場(chǎng)所的選擇。例4(P166)

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

（一）、指派問(wèn)題的數(shù)學(xué)模型設(shè)n個(gè)人被分配去做n件工作，規(guī)定每個(gè)人只做一件工作，每件工作只有一個(gè)人去做。已知第i個(gè)人去做第j件工作的的效率（時(shí)間或費(fèi)用）為Cij(i=1.2…n;j=1.2…n)并假設(shè)Cij≥0。問(wèn)應(yīng)如何分配才能使總效率（時(shí)間或費(fèi)用）最高？六、指派問(wèn)題指派問(wèn)題是0—1規(guī)劃的特例。庫(kù)恩（ww.kuhn）于1955年提出了指派問(wèn)題的解法。他引用了匈牙利數(shù)學(xué)家康尼格一個(gè)關(guān)于矩陣中0元素的定理，所以把這解法稱為匈牙利法。以后在方法上雖有不斷改進(jìn)，但仍沿用這名稱?！纠肯卤頌槟骋粋€(gè)分配問(wèn)題的效率矩陣，其中aij表示第i個(gè)人完成第j項(xiàng)工作需要的時(shí)間。要求：1.將此分配問(wèn)題的求解轉(zhuǎn)化為一個(gè)網(wǎng)絡(luò)圖中求始點(diǎn)與終點(diǎn)之間的最短路問(wèn)題，畫(huà)出該網(wǎng)絡(luò)圖，注明節(jié)點(diǎn)和邊的含義，并標(biāo)明每一條邊的aij值；

2.以上述網(wǎng)絡(luò)圖為基礎(chǔ)，利用0－1變量建立該最短路問(wèn)題的0－1整數(shù)規(guī)劃模型，列出該模型的數(shù)學(xué)表達(dá)式。

工作人B1B2B3A1A2A3a11a21a31a12a22a32a13a23a33例6．有四個(gè)工人，要分別指派他們完成四項(xiàng)不同的工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表所示，問(wèn)應(yīng)如何指派工作，才能使總的消耗時(shí)間為最少。解：引入0—1變量xij，并令

xij

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

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

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

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

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***求解可用《管理運(yùn)籌學(xué)》軟件中整數(shù)規(guī)劃方法。設(shè)決策變量1分配第i個(gè)人去做第j件工作

xij

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

（二）匈牙利法解題步驟（補(bǔ)充，重點(diǎn)）

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

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

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

(2)再?gòu)乃眯孪禂?shù)矩陣的每列元素中減去該列的最小元素。

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

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

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

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

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

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

(1)對(duì)沒(méi)有◎的行打√號(hào)；

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

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

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

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

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

工件人員ABCD甲149415乙117910丙132105丁1791513例二、指派問(wèn)題是0—1規(guī)劃的特例。庫(kù)恩（ww.kuhn）于1955年提出了指派問(wèn)題的解法。他引用了匈牙利數(shù)學(xué)家康尼格一個(gè)關(guān)于矩陣中0元素的定理，所以把這解法稱為匈牙利法。以后在方法上雖有不斷改進(jìn)，但仍沿用這名稱。復(fù)習(xí)：指派問(wèn)題例2：有一份中文說(shuō)明書(shū)，需譯成英、日、德、俄四種文字。分別記作E、J、G、R。有甲、乙、丙、丁四人。他們將中文說(shuō)明書(shū)譯成不同語(yǔ)種的說(shuō)明書(shū)所需的時(shí)間如表所示。問(wèn)應(yīng)指派何人去完成何工作，使所需總時(shí)間最少？人員任務(wù)EJGR甲乙丙丁2109715414813141611415139例一：

任務(wù)人員EJGR甲215134乙1041415丙9141613丁78119249742第一步：變換指派問(wèn)題的系數(shù)矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即

◎?◎??◎◎

任務(wù)人員EJGR甲215134乙1041415丙9141613丁78119指派方案是：甲翻譯R，乙翻譯J，丙翻譯E，丁翻譯G最少的時(shí)間是：minZ=4+4+9+11=28第二步：進(jìn)行試指派，以尋求最優(yōu)解。

(1)從只有一個(gè)0元素的行開(kāi)始，給這個(gè)0元素加圈，記作◎。然后劃去◎所在列的其它0元素，記作?；這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。一般指派問(wèn)題2、人數(shù)和任務(wù)不等的指派問(wèn)題（1）人少任務(wù)多（2）人多任務(wù)少

3、一個(gè)人可做幾件事的指派問(wèn)題4、某事一定不能由某人做的指派問(wèn)題5、目標(biāo)函數(shù)不是求最小，求最大？6、經(jīng)過(guò)兩步之后，m<n，怎么辦？

思考

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

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

任務(wù)人員ABCD甲25293143乙38372520丙37272840丁44413523E37323223◎?◎??◎?◎?◎由于任務(wù)多，人少，所以增加一個(gè)虛擬的人，該人完成各項(xiàng)任務(wù)的時(shí)間都為零。第一步：增加一種泳姿，各位運(yùn)動(dòng)員的成績(jī)均為零，得方陣：

已知下列五名運(yùn)動(dòng)員各種姿勢(shì)的游泳成績(jī)（各為50米），如表所示，試問(wèn)如何從中選拔一個(gè)參加200米混合泳的接力隊(duì)，使預(yù)期比賽成績(jī)?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第一步：增加一種泳姿，各位運(yùn)動(dòng)員的成績(jī)均為零，得方陣：從甲、乙、丙、丁、戊五人中挑選四人去完成四項(xiàng)任務(wù)。每人完成各項(xiàng)任務(wù)時(shí)間如表所示。規(guī)定每項(xiàng)工作只能由一個(gè)人去單獨(dú)完成，每個(gè)人最多承擔(dān)一項(xiàng)任務(wù)。又假定對(duì)甲必須保證分配一項(xiàng)任務(wù)，丁因?yàn)槟撤N原因決定不同意承擔(dān)第4項(xiàng)任務(wù)。在滿足上述條件下，如何分配工作，使完成四項(xiàng)工作所花費(fèi)時(shí)間為最少。

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

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

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

xij

=1(當(dāng)指派第i人去完成第j項(xiàng)工作時(shí))或0（當(dāng)不指派第i人去完成第j項(xiàng)工作時(shí))．這可以表示為一個(gè)0--1整數(shù)規(guī)劃問(wèn)題：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(甲最多只能干一項(xiàng)工作)

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

x31+x32+x33+x34≤1(丙最多只能干一項(xiàng)工作)

x41+x42+x43+x44≤1(丁最多只能干一項(xiàng)工作)

x51+x52+x53+x54≤1(戊最多只能干一項(xiàng)工作)

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***求解可用《管理運(yùn)籌學(xué)》軟件中整數(shù)規(guī)劃方法。

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