第五講-整數(shù)規(guī)劃及指派問題

1、整 數(shù) 規(guī) 劃 與 指派 問 題內(nèi)容提要一、整數(shù)規(guī)劃的應(yīng)用二、整數(shù)規(guī)劃的求解方法概述四、匈牙利解法三、指派問題一、整數(shù)規(guī)劃的案例案例1：集裝箱托運(yùn)問題 公司擬用集裝箱托運(yùn)甲、乙兩種貨物，這兩種貨物每件的體積、重量，可獲利潤以及托運(yùn)所受限制如下表所示: 甲種貨物至多托運(yùn)4件，問兩種貨物各托運(yùn)多少件，可使獲得利潤最大？貨物每件體積/立方英尺每件重量/百千克每件利潤/百元甲19542乙273403托運(yùn)限制1365140 設(shè) 分別為甲、乙兩種貨物托運(yùn)的件數(shù)，其數(shù)學(xué)規(guī)劃模型如下： 一、整數(shù)規(guī)劃的案例（續(xù)）案例2：固定成本問題 高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機(jī)器設(shè)

2、備，制造一個容器所需的各種資源的數(shù)量如下表： 不考慮固定費(fèi)用，每種容器售出一只所得的利潤分別為4萬元，5萬元，6萬元，可使用的金屬板有500，勞動力有300人月，機(jī)器有100臺月。資源小號容器中號容器大號容器金屬板248勞動力234機(jī)器設(shè)備123 此外，不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費(fèi)用：小號為100萬元，中號為150萬元，大號為200萬元。現(xiàn)在要制定生產(chǎn)計劃，使獲得利潤最大。 設(shè) 分別為小號容器、中號容器和大號容器的生產(chǎn)數(shù)量。各種容器的固定費(fèi)用只有在生產(chǎn)該種容器時才投入，故設(shè) 扣除了固定費(fèi)用的最大利潤的目標(biāo)函數(shù)為 約束條件1（資源限制）： 約束條件2（固定費(fèi)用邏輯約束） 約

3、束條件3：可簡化一、整數(shù)規(guī)劃的案例（續(xù)）案例3：分布系統(tǒng)設(shè)計問題 企業(yè)在A1地已有一個工廠，其生產(chǎn)能力為30千箱，為了擴(kuò)大生產(chǎn)，打算在A2，A3，A4，A5地中再選擇幾個地方建廠，建廠的固定成本分別為175千元，300千元，375千元，500千元。其他信息見下表： B1B2B3產(chǎn)量/千箱A184330A252310A343420A497530A5104240銷量302020 （1）應(yīng)該在哪幾個地方建廠，在滿足銷量前提下，使得其總固定成本和總運(yùn)輸費(fèi)用之和最??？ （2）由于政策要求必須在A2，A3 地建一個廠，應(yīng)在哪幾個地方建廠？ 解：設(shè) 為從 運(yùn)往 的運(yùn)輸量， 固定成本及總運(yùn)輸費(fèi)用最小的目標(biāo)為產(chǎn)

4、量限制約束條件： 銷量限制約束條件：（2）增加約束條件二、整數(shù)規(guī)劃的求解方法概述 整數(shù)線性規(guī)劃，是要求整數(shù)解的線性規(guī)劃，包括上班的人數(shù)、設(shè)備的臺數(shù)、材料的件數(shù)等。 問題： 最優(yōu)整數(shù)解是否可以對非整數(shù)解進(jìn)行四舍五入法或者去尾法呢？ * * * * * * * * * * * * * * * * 2x1+3x2=14.662x1+3x2=142x1+3x2=6線性規(guī)劃的最優(yōu)解為：整數(shù)規(guī)劃的最優(yōu)解為： TBA航空公司是一家地區(qū)性公司，從事小型飛機(jī)的短途運(yùn)輸。公司運(yùn)營狀況良好，目前正考慮擴(kuò)展業(yè)務(wù)。 公司管理層面臨的主要問題是要在兩種決策中作出選擇：是購買新一飛機(jī)增加短途航班，還是購買一些大型機(jī)提供跨省

5、市航班，從而將市場擴(kuò)大到整個國家，或同時采取兩種措施。許多因素都影響著管理層的最終決策，但其中最重要的一點(diǎn)是哪種措施可能會帶來最大的利潤。例：TBA航空公司TBA航空公司(無整數(shù)約束)O1221最優(yōu)解(2,1.8)TBA航空公司(整數(shù)約束)O1221最優(yōu)解(0,2)舍入化整法化整后的解可能超出可行域，或者雖是可行解，卻不是最優(yōu)解； 適用情況： 決策變量取值非常大； 決策變量的價值系數(shù)非常??；整數(shù)規(guī)劃的分類： 純整數(shù)規(guī)劃； 混合整數(shù)規(guī)劃； 0-1規(guī)劃整數(shù)規(guī)劃的求解方法：割平面法（cutting plane algorithm） 純整數(shù)規(guī)劃分支定界法（branch and bound method

6、） 混合整數(shù)規(guī)劃隱枚舉法（implicit enumeration method） 0-1規(guī)劃分支定界法（Branch bound method）20世紀(jì)60年代初由蘭德多伊格和戴金等人提出原理分支為整數(shù)規(guī)劃最優(yōu)解的出現(xiàn)創(chuàng)造了條件，縮小了求解范圍，而定界則可以提高求解的效率。首先求出整數(shù)規(guī)劃相應(yīng)的松弛問題的最優(yōu)解，若求得的最優(yōu)解符合整數(shù)要求，則這個解就是原整數(shù)規(guī)劃的最優(yōu)解；若不滿足，則任選一個不滿足整數(shù)條件的變量來構(gòu)造兩個新的約束，使原問題分成兩個問題，在原可行域中剔除部分非整數(shù)解，如此不斷重復(fù)。分支定界法舉例132X254X1 231S解S得：132X254X1 231S2對S分枝：構(gòu)造約束

7、：和形成分枝問題S1和S2，得解B和CS1SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9132X254X1 231S2對S1分枝：構(gòu)造約束：和形成分枝問題S11和S12，得解DS12S11無可行解SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11無可行解S12D:x1=33/14,x2=2Z=61/14132X254X1 231S2對S12分枝：構(gòu)造約束：和形成分枝問題S121和S122，得解E和FS121S122SA:x

8、1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11無可行解S12D:x1=33/14,x2=2Z=61/14S122F:x1=2,x2=2Z=4S121E:x1=3,x2=1Z=4分支定界說明分支定界步驟：線性規(guī)劃問題求解-定界過程-剪枝過程（無可行解或不優(yōu)于現(xiàn)有下界）-分支過程-循環(huán)往復(fù)選擇原則 按目標(biāo)函數(shù)系數(shù) 選系數(shù)絕對值最大的變量先分支； 選與整數(shù)值相差最大的非整數(shù)變量先分支三、指派問題指派問題（Assignment problem） 又稱分配問題，研究如何給n個人（或單位）分配n項(xiàng)工作，使得完成全部工作所消

9、耗的總資源（時間、費(fèi)用）最少。 s.t.例：有一份中文說明書，需譯成英、日、德、俄四種文字。分別記作E、J、G、R?，F(xiàn)有甲、乙、丙、丁四人。他們將中文說明書翻譯成不同語種的說明書所需時間如表所示。問應(yīng)指派何人去完成何工作，使所需總時間最少? 指派問題的解應(yīng)對應(yīng)于成本矩陣的不同行與不同列，且總成本最小。 可行解矩陣的每一行每一列只有一個元素為1，共有n個取1，其余取值為零。同解變化四、匈牙利解法 美國數(shù)學(xué)家W.Knhn于1955年給出的，由于他的解法運(yùn)用了匈牙利數(shù)學(xué)家D.Konig關(guān)于矩陣零元素的一個定理，因此被稱為匈牙利解法。定理：對于指派問題，成本矩陣的任一行(或列)減去(或加上)一個相同的數(shù)得到的新指派問題與原問題同解。定理：覆蓋一個方陣內(nèi)所有0元的最小直線數(shù)等于該陣中位于不同行、列的0元的最多個數(shù)；基本思想（反復(fù)應(yīng)用同解變換） 成本矩陣（效益矩陣）的每一行及每一列減去該行或列的最小數(shù)，使每行每列至少有一個0，假如能夠從中找出n個位于不同行、列的0元，則為最優(yōu)陣，對應(yīng)最優(yōu)解。 如果劃去這些0所需要的直線數(shù)不少于n（等于n），則此時就可以求得最優(yōu)解。四、匈牙利解法（續(xù)）練習(xí)一般指派問題（非標(biāo)準(zhǔn)）：