整數(shù)規(guī)劃與分配問(wèn)題運(yùn)籌學(xué)第1頁(yè)，共91頁(yè)，2023年，2月20日，星期五第4章整數(shù)規(guī)劃與分配問(wèn)題2023/4/102第2頁(yè)，共91頁(yè)，2023年，2月20日，星期五例4.1某服務(wù)部門(mén)各時(shí)段（每2小時(shí)為一時(shí)段）需要的服務(wù)員人數(shù)如下表，按規(guī)定，服務(wù)員連續(xù)工作8小時(shí)（即4個(gè)時(shí)段）為一班，現(xiàn)要求安排服務(wù)員的工作時(shí)間，使服務(wù)部門(mén)服務(wù)員總數(shù)最小。時(shí)段12345678服務(wù)員最少數(shù)目108911138534.1整數(shù)規(guī)劃問(wèn)題的數(shù)學(xué)模型2023/4/103第3頁(yè)，共91頁(yè)，2023年，2月20日，星期五解：設(shè)在第j時(shí)段開(kāi)始時(shí)上班的服務(wù)員人數(shù)為xj，由于第j時(shí)段開(kāi)始時(shí)上班的服務(wù)員將在第(j+3)時(shí)段結(jié)束時(shí)下班，故決策變量只需考慮x1,x2,x3,x4,x5，此問(wèn)題的數(shù)學(xué)模型為：2023/4/104第4頁(yè)，共91頁(yè)，2023年，2月20日，星期五此類問(wèn)題數(shù)學(xué)模型的一般形式為：求一組變量X1,X2,…,Xn，使2023/4/105第5頁(yè)，共91頁(yè)，2023年，2月20日，星期五例4.2某單位有5個(gè)擬選擇的投資項(xiàng)目，其所需投資額與期望收益如下表。由于各項(xiàng)目之間有一定聯(lián)系，A、C、E之間必須選擇一項(xiàng)且僅需選擇一項(xiàng)；B和D之間需選擇也僅需選擇一項(xiàng)；又由于C和D兩項(xiàng)目密切相關(guān)，C的實(shí)施必須以D的實(shí)施為前提條件，該單位共籌集資金15萬(wàn)元，問(wèn)應(yīng)該選擇哪些項(xiàng)目投資，使期望收益最大？項(xiàng)目所需投資額（萬(wàn)元）期望收益（萬(wàn)元）A610B48C27D46E592023/4/106第6頁(yè)，共91頁(yè)，2023年，2月20日，星期五解：決策變量：設(shè)目標(biāo)函數(shù)：期望收益最大約束條件：投資額限制條件6x1+4x2+2x3+4x4+5x515項(xiàng)目A、C、E之間必須且只需選擇一項(xiàng)：x1+x3+x5=1項(xiàng)目C的實(shí)施要以項(xiàng)目D的實(shí)施為前提條件：x3

x4項(xiàng)目B、D之間必須且只需選擇一項(xiàng)：x2+x4=1歸納起來(lái)，其數(shù)學(xué)模型為：2023/4/107第7頁(yè)，共91頁(yè)，2023年，2月20日，星期五上面此例表明，利用0-1變量處理一類“可供選擇條件”的問(wèn)題非常簡(jiǎn)明方便。下面再進(jìn)一步分別說(shuō)明對(duì)0-1變量的應(yīng)用。假定現(xiàn)有m種資源對(duì)可供選擇的n個(gè)項(xiàng)目進(jìn)行投資的數(shù)學(xué)模型為：求一組決策變量X1,X2,…,Xn，使 2023/4/108第8頁(yè)，共91頁(yè)，2023年，2月20日，星期五根據(jù)變量取整數(shù)的情況,將整數(shù)規(guī)劃分為：（1）純整數(shù)規(guī)劃，所有變量都取整數(shù).（2）混合整數(shù)規(guī)劃，一部分變量取整數(shù),一部分變量取實(shí)數(shù)（3）0-1整數(shù)規(guī)劃,所有變量均取0或1對(duì)決策變量只限于不能取負(fù)值的連續(xù)型數(shù)值，即可以是正分?jǐn)?shù)或正小數(shù)。然而在許多經(jīng)濟(jì)管理的實(shí)際問(wèn)題中，決策變量只有非負(fù)整數(shù)才有實(shí)際意義。對(duì)求整數(shù)最優(yōu)解的問(wèn)題，稱為整數(shù)規(guī)劃(IntegerProgramming)(簡(jiǎn)記為IP)。又稱約束條件和函數(shù)均為線性的IP為整數(shù)線性規(guī)劃(IntegerLinearProgramming)(簡(jiǎn)記為ILP)。2023/4/109第9頁(yè)，共91頁(yè)，2023年，2月20日，星期五考慮純整數(shù)問(wèn)題：整數(shù)問(wèn)題的松弛問(wèn)題：第10頁(yè)，共91頁(yè)，2023年，2月20日，星期五求解ILP問(wèn)題方法的思考：“舍入取整”法：即先不考慮整數(shù)性約束，而去求解其相應(yīng)的LP問(wèn)題（稱為松馳問(wèn)題），然后將得到的非整數(shù)最優(yōu)解用“舍入取整”的方法。這樣能否得到整數(shù)最優(yōu)解？但在處理個(gè)別實(shí)際問(wèn)題時(shí)，如果允許目標(biāo)函數(shù)值在某一誤差范圍內(nèi)，有時(shí)也可采用“舍入取整”得到的整數(shù)可行解作為原問(wèn)題整數(shù)最優(yōu)解的近似。這樣可節(jié)省求解的人力、物力和財(cái)力。2023/4/1011第11頁(yè)，共91頁(yè)，2023年，2月20日，星期五例4.3設(shè)整數(shù)規(guī)劃問(wèn)題如下首先不考慮整數(shù)約束，得到線性規(guī)劃問(wèn)題（松弛問(wèn)題）。2023/4/1012第12頁(yè)，共91頁(yè)，2023年，2月20日，星期五用圖解法求出最優(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ī)劃問(wèn)題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問(wèn)題的可行解集是一個(gè)有限集，如圖所示。第13頁(yè)，共91頁(yè)，2023年，2月20日，星期五因此，可將集合內(nèi)的整數(shù)點(diǎn)一一找出，其最大目標(biāo)函數(shù)的值為最優(yōu)解，此法為完全枚舉法。如上例：其中（2，2）（3，1）點(diǎn)為最大值，Z=4。目前，常用的求解整數(shù)規(guī)劃的方法有：割平面法和分支定界法，對(duì)于特別的0－1規(guī)劃問(wèn)題采用隱枚舉法和匈牙利法。2023/4/1014第14頁(yè)，共91頁(yè)，2023年，2月20日，星期五在實(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)題。4.2分配問(wèn)題與匈牙利法第15頁(yè)，共91頁(yè)，2023年，2月20日，星期五分配第i個(gè)人去完成第j項(xiàng)任務(wù)不分配第i個(gè)人去完成第j項(xiàng)任務(wù)例4.4有一份說(shuō)明書(shū)，要分別譯成英、日、德、俄四種文字，交甲、乙、丙、丁四個(gè)人去完成。因各人專長(zhǎng)不同，他們完成翻譯不同文字所需的時(shí)間（h）如下表，應(yīng)如何分配，使這四個(gè)人分別完成這四項(xiàng)任務(wù)總的時(shí)間為最?。?023/4/1016第16頁(yè)，共91頁(yè)，2023年，2月20日，星期五2023/4/1017第17頁(yè)，共91頁(yè)，2023年，2月20日，星期五分配問(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)用）最高？設(shè)決策變量1分配第i個(gè)人去做第j件工作

xij=0相反(I,j=1.2.…n)其數(shù)學(xué)模型為：第18頁(yè)，共91頁(yè)，2023年，2月20日，星期五4.2.2匈牙利法指派問(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ù)矩陣的每列元素中減去該列的最小元素。2023/4/1019第19頁(yè)，共91頁(yè)，2023年，2月20日，星期五第二步：進(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元素都被圈出和劃掉為止。2023/4/1020第20頁(yè)，共91頁(yè)，2023年，2月20日，星期五（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)；2023/4/1021第21頁(yè)，共91頁(yè)，2023年，2月20日，星期五（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)回第二步。2023/4/1022第22頁(yè)，共91頁(yè)，2023年，2月20日，星期五例4.5任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119第23頁(yè)，共91頁(yè)，2023年，2月20日，星期五24972023/4/1024第24頁(yè)，共91頁(yè)，2023年，2月20日，星期五422023/4/1025第25頁(yè)，共91頁(yè)，2023年，2月20日，星期五◎?◎??◎◎2023/4/1026第26頁(yè)，共91頁(yè)，2023年，2月20日，星期五例4.7有一份中文說(shuō)明書(shū)，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說(shuō)明書(shū)譯成不同語(yǔ)種的說(shuō)明書(shū)所需時(shí)間如下表所示，問(wèn)如何分派任務(wù)，可使總時(shí)間最少？任務(wù)人員ABCD甲67112乙4598丙31104丁5982第27頁(yè)，共91頁(yè)，2023年，2月20日，星期五求解過(guò)程如下：第一步，變換系數(shù)矩陣：－5第二步，試指派：◎◎◎??找到3個(gè)獨(dú)立零元素但m=3<n=42023/4/1028第28頁(yè)，共91頁(yè)，2023年，2月20日，星期五第三步，作最少的直線覆蓋所有0元素：◎◎◎??√√√獨(dú)立零元素的個(gè)數(shù)m等于最少直線數(shù)l，即l＝m=3<n=4；第四步，變換矩陣(bij)以增加0元素：沒(méi)有被直線覆蓋的所有元素中的最小元素為1，然后打√各行都減去1；打√各列都加上1，得如下矩陣，并轉(zhuǎn)第二步進(jìn)行試指派：2023/4/1029第29頁(yè)，共91頁(yè)，2023年，2月20日，星期五000

0

00得到4個(gè)獨(dú)立零元素，所以最優(yōu)解矩陣為：◎◎◎??√√√◎◎◎??15◎◎◎??◎2023/4/1030第30頁(yè)，共91頁(yè)，2023年，2月20日，星期五練習(xí)：115764戊69637丁86458丙9117129乙118957甲EDCBA費(fèi)工作用人員第31頁(yè)，共91頁(yè)，2023年，2月20日，星期五-1-22023/4/1032第32頁(yè)，共91頁(yè)，2023年，2月20日，星期五◎?◎◎◎??2023/4/1033第33頁(yè)，共91頁(yè)，2023年，2月20日，星期五◎?◎◎◎??√√√l=m=4<n=52023/4/1034第34頁(yè)，共91頁(yè)，2023年，2月20日，星期五◎?◎◎◎??2023/4/1035第35頁(yè)，共91頁(yè)，2023年，2月20日，星期五◎?◎?◎?◎?√√√√√√√2023/4/1036第36頁(yè)，共91頁(yè)，2023年，2月20日，星期五◎?◎?◎?◎?√√√√√√√l=m=4<n=52023/4/1037第37頁(yè)，共91頁(yè)，2023年，2月20日，星期五◎?◎?◎?◎?√√√√√√√2023/4/1038第38頁(yè)，共91頁(yè)，2023年，2月20日，星期五◎??◎??◎?◎?◎此問(wèn)題有多個(gè)最優(yōu)解282023/4/1039第39頁(yè)，共91頁(yè)，2023年，2月20日，星期五◎??◎??◎?◎?◎2023/4/1040第40頁(yè)，共91頁(yè)，2023年，2月20日，星期五◎??◎??◎?◎?◎2023/4/1041第41頁(yè)，共91頁(yè)，2023年，2月20日，星期五用匈牙利法求解下列指派問(wèn)題，已知效率矩陣分別如下：2023/4/1042第42頁(yè)，共91頁(yè)，2023年，2月20日，星期五4.2.3兩點(diǎn)說(shuō)明1.分配問(wèn)題中如果人數(shù)和工作任務(wù)數(shù)不相等是的處理方法ⅠⅡⅢⅣ136262714433658464375524365762ⅠⅡⅢⅣⅤⅥ1362600271440033658004643700552430065762002023/4/1043第43頁(yè)，共91頁(yè)，2023年，2月20日，星期五2．如果效率矩陣的數(shù)字是表示每人每天能完成的翻譯成漢字的字?jǐn)?shù)，問(wèn)題就變成如何分配任務(wù)，使每天完成的任務(wù)量為大最，目標(biāo)函數(shù)就變?yōu)椋旱葍r(jià)于：2023/4/1044第44頁(yè)，共91頁(yè)，2023年，2月20日，星期五0－1整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時(shí)的決策變量xi只取兩個(gè)值0或1，一般的解法為隱枚舉法。例4.11求解下列0－1規(guī)劃問(wèn)題0－1整數(shù)規(guī)劃與隱枚舉法第45頁(yè)，共91頁(yè)，2023年，2月20日，星期五解：對(duì)于0－1規(guī)劃問(wèn)題，由于每個(gè)變量只取0，1兩個(gè)值，一般會(huì)用窮舉法來(lái)解，即將所有的0，1組合找出，使目標(biāo)函數(shù)達(dá)到極值要求就可求得最優(yōu)解。但此法太繁瑣，工作量相當(dāng)大。而隱枚舉法就是在此基礎(chǔ)上，通過(guò)加入一定的條件，就能較快的求得最優(yōu)解。x1.x2.x3約束條件滿足條件Z值

(1)(2)(3)(4)是∨否×(0.0.0)

0000∨0(0.0.1)－1101∨5(0.1.0)

2414∨－2(1.0.0)

1110∨3(0.1.1)

15 ×(1.0.1)

0211∨8(1.1.0)

3×(1.1.1)

26×2023/4/1046第46頁(yè)，共91頁(yè)，2023年，2月20日，星期五由上表可知，問(wèn)題的最優(yōu)解為X*=(x1=1x2=0x3=1)由上表可知：x1=0x2=0x3=1是一個(gè)可行解，為盡快找到最優(yōu)解，可將3x1－2x2＋5x3≥5作為一個(gè)約束，凡是目標(biāo)函數(shù)值小于5的組合不必討論，如下表。x1.x2.x3約束條件滿足條件Z值(0)(1)(2)(3)(4)是∨否×(0.0.0)

00000∨0(0.0.1)

5－1101∨5(0.1.0)-2×(0.1.1)

3×(1.0.0)

3×(1.0.1)

80211∨8(1.1.0)

1×(1.1.1)

4×2023/4/1047第47頁(yè)，共91頁(yè)，2023年，2月20日，星期五例4.12求解下列0－1規(guī)劃問(wèn)題解：由于目標(biāo)函數(shù)中變量x1,x2,

x4

的系數(shù)均為負(fù)數(shù)，可作如下變換：令x1

＝1－

x1′

,x2=1-x2′,x3=x3′,x4=1-x4′帶入原題中，但需重新調(diào)整變量編號(hào)。令x3′=x1′,x4′=x2′得到下式。2023/4/1048第48頁(yè)，共91頁(yè)，2023年，2月20日，星期五可以從(1.1.1.1)開(kāi)始試算，x′(3)＝(1.1.0.1)最優(yōu)解。∴x(3)＝(1.0.1.0)是原問(wèn)題的最優(yōu)解，Z*=－22023/4/1049第49頁(yè)，共91頁(yè)，2023年，2月20日，星期五例4.13求解下列0－1規(guī)劃問(wèn)題令y1=x5,y2=x4,y3=x2,y4=x3,y5=x1

得到下式2023/4/1050第50頁(yè)，共91頁(yè)，2023年，2月20日，星期五y1.y2.y3.y4.y5約束條件滿足條件Z值

(1)(2)是∨否×(0，0，0，0，0)

00×(1，0，0，0，0)

1-1×(0，1，0，0，0)

-11×(0，0，1，0，0)

-21×(0，0，0，1，0)

4-4∨8(0，0，0，0，1)

3-2×所以，

Y*=（0.0.0.1.0），原問(wèn)題的最優(yōu)解為：

X*

＝（0.0.1.0.0），Z*=82023/4/1051第51頁(yè)，共91頁(yè)，2023年，2月20日，星期五（0，1，1，0，0）練習(xí)：用隱枚舉法求解0—1規(guī)劃問(wèn)題第52頁(yè)，共91頁(yè)，2023年，2月20日，星期五4.3.1基本思路4.3分枝定界法只解松弛問(wèn)題1、在全部可行性域上解松弛問(wèn)題若松弛問(wèn)題最優(yōu)解為整數(shù)解，則其也是整數(shù)規(guī)劃的最優(yōu)解2、分枝過(guò)程若松弛問(wèn)題最優(yōu)解中某個(gè)xk=bk不是整數(shù)，令bk為bk

的整數(shù)部分構(gòu)造兩個(gè)新的約束條件xkbk和xkbk+1，分別加于原松弛問(wèn)題，形成兩個(gè)新的整數(shù)規(guī)劃3、求解分枝的松弛問(wèn)題—定界過(guò)程設(shè)兩個(gè)分枝的松弛問(wèn)題分別為問(wèn)題1和問(wèn)題2，它們的最優(yōu)解有如下情況2023/4/1053第53頁(yè)，共91頁(yè)，2023年，2月20日，星期五分枝問(wèn)題解可能出現(xiàn)的情況情況2,4,5找到最優(yōu)解情況3在縮減的域上繼續(xù)分枝定界法情況6問(wèn)題1的整數(shù)解作為界被保留，用于以后與問(wèn)題2的后續(xù)分枝所得到的解進(jìn)行比較，結(jié)論如情況4或52023/4/1054第54頁(yè)，共91頁(yè)，2023年，2月20日，星期五例4.8用分枝定界法求解整數(shù)規(guī)劃問(wèn)題（用圖解法計(jì)算）記為（IP）解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問(wèn)題記為（LP）第55頁(yè)，共91頁(yè)，2023年，2月20日，星期五用圖解法求（LP）的最優(yōu)解，如圖所示。x1x2⑴⑵33(18/11,40/11)⑶對(duì)于x1＝18/11≈1.64，取值x1≤1，x1≥2對(duì)于x2=40/11≈3.64，取值x2≤3，x2≥4先將（LP）劃分為（LP1）和（LP2）,取x1≤1,x1≥2x1＝18/11,x2=40/11Z(0)=－218/11≈(－19.8)即Z也是（IP）最小值的下限。2023/4/1056第56頁(yè)，共91頁(yè)，2023年，2月20日，星期五有下式：現(xiàn)在只要求出（LP1）和（LP2）的最優(yōu)解即可。2023/4/1057第57頁(yè)，共91頁(yè)，2023年，2月20日，星期五x1x2⑴⑵33(18/11,40/11)⑶先求（LP1）,如圖所示。此時(shí)B在點(diǎn)取得最優(yōu)解。x1＝1,x2=3,Z(1)＝－16找到整數(shù)解，問(wèn)題已探明，此枝停止計(jì)算。11同理求（LP2）,如圖所示。在C

點(diǎn)取得最優(yōu)解。即x1＝2,x2=10/3,Z(2)

＝－56/3≈－18.7∵Z2<Z1＝－16∴原問(wèn)題有比（－16）更小的最優(yōu)解，但x2不是整數(shù)，故利用3≥10/3≥4加入條件。BAC2023/4/1058第58頁(yè)，共91頁(yè)，2023年，2月20日，星期五加入條件：x2≤3,x2≥4有下式：只要求出（LP3）和（LP4）的最優(yōu)解即可。2023/4/1059第59頁(yè)，共91頁(yè)，2023年，2月20日，星期五x1x2⑴⑵33(18/11,40/11)⑶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），如圖所示。無(wú)可行解，不再分枝。2023/4/1060第60頁(yè)，共91頁(yè)，2023年，2月20日，星期五在（LP3）的基礎(chǔ)上繼續(xù)分枝。加入條件3≤x1≤2有下式：只要求出（LP5）和（LP6）的最優(yōu)解即可。2023/4/1061第61頁(yè)，共91頁(yè)，2023年，2月20日，星期五x1x2⑴⑵33(18/11,40/11)⑶11BACD先求（LP5）,如圖所示。此時(shí)E在點(diǎn)取得最優(yōu)解。即x1＝2,x2=3,Z(5)＝－17找到整數(shù)解，問(wèn)題已探明，此枝停止計(jì)算。E求（LP6），如圖所示。此時(shí)F在點(diǎn)取得最優(yōu)解。x1＝3,x2=2.5,Z(6)＝－31/2≈－15.5>Z(5)

F如對(duì)Z(6)

繼續(xù)分解，其最小值也不會(huì)低于－15.5，問(wèn)題探明,剪枝。2023/4/1062第62頁(yè)，共91頁(yè)，2023年，2月20日，星期五至此，原問(wèn)題（IP）的最優(yōu)解為：x1=2，x2=3,Z*=Z(5)

＝－17以上的求解過(guò)程可以用一個(gè)樹(shù)形圖表示如右：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無(wú)可行解LP5x1=2,x2=3Z(5)

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

＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃2023/4/1063第63頁(yè)，共91頁(yè)，2023年，2月20日，星期五練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題（圖解法）

第64頁(yè)，共91頁(yè)，2023年，2月20日，星期五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無(wú)可行解＃＃x2≤2x2≥3LP3x1=33/14,x2=2Z(3)

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

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

＝4x1≤2x1≥3＃＃2023/4/1065第65頁(yè)，共91頁(yè)，2023年，2月20日，星期五LP1x1=1,x2=7/3Z(1)

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

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

＝41/9LP3x1=33/14,x2=2Z(3)

＝61/14LP4無(wú)可行解LP7x1=2,x2=2Z(7)

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

＝4x1≤1x1≥2x2≤2x2≥3x1≤2x1≥3＃＃＃＃2023/4/1066第66頁(yè)，共91頁(yè)，2023年，2月20日，星期五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解:用單純形法解對(duì)應(yīng)的(LP)問(wèn)題,如表所示,獲得最優(yōu)解。初始表最終表例4.10用分枝定界法求解整數(shù)規(guī)劃問(wèn)題（單純形法）

第67頁(yè)，共91頁(yè)，2023年，2月20日，星期五

x1=13/4x2=5/2Z(0)=59/4≈14.75

選x2進(jìn)行分枝，即增加兩個(gè)約束，2≥x2≥3有下式：分別在(LP1)和(LP2)中引入松弛變量x5和x6

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

得下表:2023/4/1068第68頁(yè)，共91頁(yè)，2023年，2月20日，星期五32000CB

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繼續(xù)分枝，加入約束

3≥x1≥4LP12023/4/1069第69頁(yè)，共91頁(yè)，2023年，2月20日，星期五32000CB

XB

b

x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x6-1/200-1/2

1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2,x2=3Z(2)=27/2=13.5∵Z(2)<Z(1)∴先不考慮分枝2023/4/1070第70頁(yè)，共91頁(yè)，2023年，2月20日，星期五接(LP1)繼續(xù)分枝，加入約束4≤x1≤3，有下式：分別引入松弛變量x7和x8，然后進(jìn)行計(jì)算。2023/4/1071第71頁(yè)，共91頁(yè)，2023年，2月20日，星期五CB

XB

bx1x2x3x4x5x73x17/2101/20-1/202x220100100x4100-11-200x73100001-Z-29/200-3/20-1/203x17/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-3

x1=3,x2=2Z(3)=13找到整數(shù)解，問(wèn)題已探明，停止計(jì)算。LP32023/4/1072第72頁(yè)，共91頁(yè)，2023年，2月20日，星期五CB

XB

bx1x2x3x4x5x83x17/2101/20-1/202x220100100x4100-11-200x8-4-100001-Z-29/200-3/20-1/203x17/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-1

x1=4,x2=1Z(4)=14找到整數(shù)解，問(wèn)題已探明，停止計(jì)算。LP42023/4/1073第73頁(yè)，共91頁(yè)，2023年，2月20日，星期五樹(shù)形圖如下：LP1x1=7/2,x2=2Z(1)＝29/2=14.5LPx1=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＃＃＃2023/4/1074第74頁(yè)，共91頁(yè)，2023年，2月20日，星期五練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題（單純形法）第75頁(yè)，共91頁(yè)，2023年，2月20日，星期五cj-1-5000cBxBbx1x2x3x4x50x32-111000x4

30560100x5410001-Z-1-5000cj-1-5000cBxBbx1x2x3x4x5-5x240/11011/115/110-1x1

18/11101/11-6/1100x526/1100-1/116/111-Z218/11006/1119/1102023/4/1076第76頁(yè)，共91頁(yè)，2023年，2月20日，星期五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無(wú)可行解LP5x1=2,x2=3Z(5)

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

＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃2023/4/1077第77頁(yè)，共91頁(yè)，2023年，2月20日，星期五4.4割平面法的基本思想費(fèi)用減小方向若的分量不全是整數(shù)，則對(duì)增加一個(gè)割平面條件，將的可行區(qū)域割掉一塊，恰好在被割掉的區(qū)域內(nèi)，而原ILP問(wèn)題的任何一個(gè)可行解（格點(diǎn)）都沒(méi)有被割去.2023/4/1078第78頁(yè)，共91頁(yè)，2023年，2月20日，星期五把增添了割平面條件的問(wèn)題記為，用對(duì)偶單純形法求解LP問(wèn)題.若的最優(yōu)解是整數(shù)向量，則是原ILP問(wèn)題的最優(yōu)解，計(jì)算結(jié)束；否則對(duì)問(wèn)題在增加一個(gè)割平面條件，形成問(wèn)題，…，如此繼續(xù)下去，通過(guò)求解不斷改進(jìn)的松弛LP問(wèn)題，知道得到最優(yōu)整數(shù)解為止。2023/4/1079第79頁(yè)，共91頁(yè)，2023年，2月20日，星期五例4.7用割平面法求解整數(shù)規(guī)劃問(wèn)題解：增加松弛變量x3和x4

，得到(LP)的初始單純形表和最優(yōu)單純形表：Cj0100CBXBbx1x2x3x40x3632100x40-3201－Z00100Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4－Z-3/200-1/4-1/42023/4/1080第80頁(yè)，共91頁(yè)，2023年，2月20日，星期五此題的最優(yōu)解為：X＊

(1,3/2)Z=3/2但不是整數(shù)最優(yōu)解，引入割平面。以x2為源行生成割平面，由于1/4=0+1/4,3/2=1+1/2,我們已將所需要的數(shù)分解為整數(shù)和分?jǐn)?shù)，所以，生成割平面的條件為:也即：2023/4/1081第81頁(yè)，共91頁(yè)，2023年，2月20日，星期五將x3=6-3x1-2x2,x4=3x1-2x2,帶入中，得到等價(jià)的割平面條件：x2≤1見(jiàn)下圖。x1x2⑴⑵33第一個(gè)割平面2023/4/1082第82頁(yè)，共91頁(yè)，2023年，2月20日，星期五Cj01000CBXBbx1x2x3x4s10x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41－Z-3/200-1/4-1/40現(xiàn)將生成的割平面條件加入松弛變量，然后加到表中：CBXBbx1x2x3x4s10x12/3100-1/32/31x2101