運(yùn)籌學(xué)第六章整數(shù)線性規(guī)劃

1、運(yùn)籌學(xué)運(yùn)籌學(xué)任課教師：任課教師：郵郵 箱：箱：手手 機(jī)：機(jī)：Q Q：6 整數(shù)線性規(guī)劃p6.1 整數(shù)線性規(guī)劃問題的提出p一般標(biāo)準(zhǔn)線性規(guī)劃問題模型中的決策變量，為非負(fù)的連續(xù)變量。然而在現(xiàn)實(shí)中，如果決策變量代表的是人數(shù)、機(jī)器臺(tái)數(shù)等概念時(shí)，必須取整數(shù)。p全（純）整數(shù)線性規(guī)劃：模型中的決策變量全部要求為整數(shù)。p混合整數(shù)線性規(guī)劃：模型中部分決策變量要求為整數(shù)。6 整數(shù)線性規(guī)劃p6.2 分支定界解法p例1：某廠擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤及托運(yùn)限制如下表所示。問兩種貨物各托運(yùn)多少箱，可使獲利最大？貨物貨物體積體積(m3/箱箱)重量重量(100kg/箱箱)利潤利潤(百元百元/箱箱)甲

2、5220乙4510托運(yùn)限制24 m3136 整數(shù)線性規(guī)劃p6.2 分支定界解法1212121254242513,0,xxxxx xx x為整數(shù)12Max2010zxx此模型為全整數(shù)線性規(guī)劃還是混合整數(shù)線性規(guī)劃？轉(zhuǎn)換為標(biāo)準(zhǔn)模型后呢？原始模型和標(biāo)準(zhǔn)模型均為全整數(shù)線性規(guī)劃。6 整數(shù)線性規(guī)劃p6.2 分支定界解法p本問題對(duì)應(yīng)線性規(guī)劃問題最優(yōu)解為：p本問題的最優(yōu)解為：1212121254242513,0,xxxxx xx x為整數(shù)12Max2010zxx124.8,0,max96xxz124,1,max90 xxz是否可以采用去除小數(shù)或四舍五入的方式得到整數(shù)最優(yōu)解？6 整數(shù)線性規(guī)劃p6.2 分支定界解法

3、p分支定界法求解流程圖求解整數(shù)規(guī)劃問題A求解相應(yīng)線性規(guī)劃問題BB無可行解A無可行解B的最優(yōu)解，滿足整數(shù)約束即為A的最優(yōu)解B的最優(yōu)解，不滿足整數(shù)約束，目標(biāo)函數(shù)值為z0基于非整數(shù)變量增加約束，將B分支為問題B1和B2直到得到A的最優(yōu)解z*0z* z0求解B1和B2，不斷縮小z*下界與上屆的差距6 整數(shù)線性規(guī)劃p6.2 分支定界解法p分支定界法求解例題p練習(xí)題：P152-6.212Max4090zxx12121212975672070,0,xxxxx xx x為整數(shù)1204.811.82356xxz問題B12142.1349xxz問題B112251.57341xxz問題B212342340 xxz問

4、題B31241.423327xxz問題B41255.441308xxz問題B5問題B600,356zzz14x 15x 無可行解22x 23x 21x 22x 10,349zzz2340,341zzz*340z 6 整數(shù)線性規(guī)劃p6.3 割平面法p分支定界法求解例題p將最終單純形表中b列非整數(shù)的方程，將系數(shù)和常數(shù)項(xiàng)都分解為整數(shù)和非負(fù)真分?jǐn)?shù)兩部分之和。12Max zxx12121212-134,0,xxxxx xx x為整數(shù)ci1100CBXBbx1x2x3x40 x31-11100 x443101z011001x13/410-1/41/41x27/4013/41/4z5/200-1/2-1/2

5、6 整數(shù)線性規(guī)劃p6.3 割平面法p分支定界法求解例題p將整數(shù)與分?jǐn)?shù)部分分開1343131 010444xxx ci1100CBXBbx1x2x3x40 x31-11100 x443101z011001x13/410-1/41/41x27/4013/41/4z5/200-1/2-1/22343131444xxx 1334331444xxxx2343311444xxx 343310444xx6 整數(shù)線性規(guī)劃p6.3 割平面法p分支定界法求解例題ci11000CBXBbx1x2x3x4x51x13/410-1/41/401x27/4013/41/400 x5-300-3-11z5/200-1/2-

6、1/20343310444xx3433xx 34533xxx ci11000CBXBbx1x2x3x4x51x111001/31x2101001/40 x310011/3-1/3z-2000-1/3-1/6-1/126 整數(shù)線性規(guī)劃p6.4 0-1整數(shù)規(guī)劃p指決策變量近取0或1二進(jìn)制變量p在現(xiàn)實(shí)中代表是否選擇某個(gè)項(xiàng)目，執(zhí)行某個(gè)任務(wù)等。p0-1整數(shù)規(guī)劃建模練習(xí)P152-6.4，P153-6.66 整數(shù)線性規(guī)劃p6.5 指派問題p求解n項(xiàng)任務(wù)指派給n個(gè)人完成的問題，并且每個(gè)人只完成1項(xiàng)任務(wù)，每個(gè)任務(wù)只給1個(gè)人完成。p例如假設(shè)讓n個(gè)人去完成n項(xiàng)任務(wù)的對(duì)應(yīng)成本表如下：111212122212nnnnn

7、nccccccccc1111Min1,1,2,1,1,2,1or 0nnijijijnijinijjijzc xxjnxinx6 整數(shù)線性規(guī)劃p6.5 指派問題p例題1：讓甲乙丙丁4人去完成英日德俄4種語言翻譯的任務(wù)，4人完成4項(xiàng)任務(wù)的耗時(shí)如下表所示。請(qǐng)問如何指派，使完成的總耗時(shí)最小？人員人員任務(wù)任務(wù)英日德俄甲215134乙1041415丙9141613丁781196 整數(shù)線性規(guī)劃p6.5 指派問題2151341041415914161378119min24970131126010110574014242min01370606905320100人員人員任務(wù)任務(wù)英日德俄甲215134乙10414

8、15丙9141613丁78119甲-俄，乙-日，丙-英，丁-德總耗時(shí)為：4+4+9+11=286 整數(shù)線性規(guī)劃p6.5 指派問題p例題2：讓甲乙丙丁戊5人去完成ABCDE5項(xiàng)任務(wù)，5人完成任務(wù)對(duì)應(yīng)成本如下表。請(qǐng)問如何指派，使完成的總成本最??？人員人員任務(wù)任務(wù)ABCDE甲127979乙89666丙71712149丁15146610戊41071096 整數(shù)線性規(guī)劃p6.5 指派問題1279798966671712149151466104107109min7676450202230000105729800406365甲-B，乙-D，丙-E，丁-C，戊-A總成本為：7+6+9+6+4=3270202430000835011800404143找到未被直線覆蓋的最小元素值2。未被直線覆蓋元素減去，直線交叉處加上該值2。人員人員任務(wù)任務(wù)ABCDE甲1279