整數(shù)規(guī)劃與分配問題

整數(shù)規(guī)劃的模型分支定界法割平面法0－1整數(shù)規(guī)劃分配問題第四章整數(shù)規(guī)劃與分配問題一、整數(shù)規(guī)劃的模型及特點(diǎn)一、整數(shù)規(guī)劃的模型及特點(diǎn)一、整數(shù)規(guī)劃的模型及特點(diǎn)

例3設(shè)有4個(gè)教師，他們各有能力去教4門不同課程中的任一門，但因?yàn)樗麄兊慕?jīng)歷和經(jīng)驗(yàn)不同，所以每個(gè)教師同樣準(zhǔn)備教某一課程平均每周所需備課時(shí)間不同，見下表。問應(yīng)分配哪個(gè)教師去擔(dān)任哪門課程，以使所有4門課程總的備課時(shí)間為最少？一、整數(shù)規(guī)劃的模型及特點(diǎn)各位教師對(duì)各門課的準(zhǔn)備時(shí)間一、整數(shù)規(guī)劃的模型及特點(diǎn)

任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119一、整數(shù)規(guī)劃的模型及特點(diǎn)一、整數(shù)規(guī)劃的模型及特點(diǎn)一、整數(shù)規(guī)劃的模型及特點(diǎn)整數(shù)規(guī)劃包括整數(shù)線性規(guī)劃和整數(shù)非線性規(guī)劃。從數(shù)學(xué)模型上看整數(shù)線性規(guī)劃似乎是線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的基礎(chǔ)上，通過舍入取整，尋求滿足整數(shù)要求的解即可。但實(shí)際上兩者卻有很大的不同，通過舍入得到的解（整數(shù)）也不一定就是最優(yōu)解，有時(shí)甚至不能保證所得到的解是整數(shù)可行解。整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系4整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系用圖解法求出最優(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è)有限集，如圖所示。整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系因此，可將集合內(nèi)的整數(shù)點(diǎn)一一找出，其最大目標(biāo)函數(shù)的值為最優(yōu)解，此法為完全枚舉法。如上例：其中（2，2）（3，1）點(diǎn)為最大值，Z=4。目前，常用的求解整數(shù)規(guī)劃的方法有：分支定界法和割平面法；對(duì)于特別的0－1規(guī)劃問題采用隱枚舉法和匈牙利法。整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系

設(shè)n個(gè)人被分配去做n件工作，已知第i個(gè)人去做第j件工作的的效率為Cij(i=1.2…n;j=1.2…n)并假設(shè)Cij≥0。問應(yīng)如何分配才能使總效率（時(shí)間或費(fèi)用）最高？二、分配問題設(shè)決策變量1分配第i個(gè)人去做第j件工作

xij=0相反(i,j=1.2.…n)標(biāo)準(zhǔn)形式二、分配問題二、分配問題二、分配問題二、分配問題方法：可順著閉合回路的方向，對(duì)間隔的0元素打上（）二、分配問題A.從矩陣中未被直線覆蓋的數(shù)字中找出一個(gè)最小的數(shù)kB.對(duì)矩陣中橫豎線交叉點(diǎn)的元素加kC.矩陣中劃線的列不變D.矩陣中未劃線的元素減k

任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119二、分配問題例3二、分配問題42二、分配問題00二、分配問題最優(yōu)分配方案為甲—D，乙—B，丙—A，丁—C此時(shí)最小耗時(shí)成本為28。有一份中文說(shuō)明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說(shuō)明書譯成不同語(yǔ)種的說(shuō)明書所需時(shí)間如下表所示，問如何分派任務(wù)，可使總時(shí)間最少？

任務(wù)人員ABCD甲67112乙4598丙31104丁5982二、分配問題例55

找到3個(gè)獨(dú)立零元素但m=3<n=4二、分配問題所有的零或被劃去,或被圈起二、分配問題A.從矩陣中未被直線覆蓋的數(shù)字中找出一個(gè)最小的數(shù)kB.對(duì)矩陣中橫豎線交叉點(diǎn)的元素加