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

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

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

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

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

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

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

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

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