1、運 籌 學(xué)( Operations Research ),任課教師：胡劍峰,海南師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,緒 論,（1）運籌學(xué)簡述 （2）運籌學(xué)的主要內(nèi)容 （3）本課程的特點和要求 （4）運籌學(xué)在工商管理中的應(yīng)用,本章主要內(nèi)容：,運籌學(xué)簡述,運籌學(xué)（Operations Research） 系統(tǒng)工程的最重要的理論基礎(chǔ)之一，在美國有人把運籌學(xué)稱之為管理科學(xué)(Management Science)。運籌學(xué)所研究的問題，可簡單地歸結(jié)為一句話： “依照給定條件和目標，從眾多方案中選擇最佳方案” 故有人稱之為最優(yōu)化技術(shù)。,運籌學(xué)簡述,運籌學(xué)的歷史與產(chǎn)生背景,1、軍事 兩次世界大戰(zhàn)期間的軍事運籌研究 2、管

2、理 生產(chǎn)中的組織與計劃問題 3、經(jīng)濟 魁內(nèi)的經(jīng)濟表,“運作研究(Operational Research)小組”:解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問題。例如： 如何合理運用雷達有效地對付德軍德空襲 對商船如何進行編隊護航，使船隊遭受德國潛艇攻擊時損失最少； 在各種情況下如何調(diào)整反潛深水炸彈的爆炸深度，才能增加對德國潛艇的殺傷力等。,軍事運籌學(xué),1942年麻省Morse教授應(yīng)美國大西洋艦隊反潛戰(zhàn)官員Baker艦長的請求擔任反潛戰(zhàn)運籌組的計劃與監(jiān)督工作，其最出色的工作之一是協(xié)助英國打破了德國對英吉利海峽的海上封鎖，研究所提出的兩條重要建議是： 將反潛攻擊由反潛艦艇投擲水雷改為飛機投擲深水炸彈，起爆深度由100

3、米改為25米左右，即當?shù)路綕撏傁聺摃r攻擊效果最佳； 運送物資的船隊及護航艦艇的編隊由小規(guī)模、多批次改為大規(guī)模、少批次，從而減少了損失率；,大西洋反潛戰(zhàn)Morse小組的重要工作,我國古代運籌學(xué)思想應(yīng)用案例,齊王要與大臣田忌賽馬，雙方各出上、中、下馬各一匹，對局三次，每次勝負1000金。田忌在好友、著名的軍事謀略家孫臏的指導(dǎo)下，以以下安排： 齊王上中下 田忌下上中 最終凈勝一局，贏得1000金。,田忌賽馬,北宋年間，丁謂負責修復(fù)火毀的開封皇宮。他的施工方案是：先將工程皇宮前的一條大街挖成一條大溝，將大溝與汴水相通。使用挖出的土就地制磚，令與汴水相連形成的河道承擔繁重的運輸任務(wù)；修復(fù)工程完成后，實

4、施大溝排水，并將原廢墟物回填，修復(fù)成原來的大街。丁謂將取材、生產(chǎn)、運輸及廢墟物的處理用“一溝三用”巧妙地解決了。,丁 謂 的 皇 宮 修 復(fù) 工 程,“運籌學(xué)”名詞出處,“夫運籌策帷幄之中，決勝于千里之外”,史記高祖本紀,運籌學(xué)的主要內(nèi)容,數(shù)學(xué)規(guī)劃（線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、目標規(guī)劃、動態(tài)規(guī)劃等） 圖論及網(wǎng)絡(luò)分析 存貯論 排隊論 對策論 排序與統(tǒng)籌方法 決策分析,本課程的特點和要求,先修課：數(shù)學(xué)分析（高等數(shù)學(xué)），高等代數(shù)（線性代數(shù)）、 概率論與數(shù)理統(tǒng)計 特點：系統(tǒng)整體優(yōu)化；多學(xué)科的配合；模型方法的應(yīng)用 運籌學(xué)的研究的主要步驟：,運籌學(xué)在工商管理中的應(yīng)用,Interface上發(fā)表的部分獲獎

5、項目,Chapter1 線性規(guī)劃 (Linear Programming),LP的數(shù)學(xué)模型 圖解法 單純形法 單純形法的進一步討論人工變量法 LP模型的應(yīng)用,本章主要內(nèi)容：,線性規(guī)劃問題的數(shù)學(xué)模型,1. 規(guī)劃問題（最優(yōu)化問題）,生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。,線性規(guī)劃通常解決下列兩類問題：,（1）當任務(wù)或目標確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源 （如資金、設(shè)備、原標材料、人工、時間等）去完成確定的任務(wù)或目標,（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟效益（如產(chǎn)品量最多 、利潤最大.）,線性規(guī)劃

6、問題的數(shù)學(xué)模型,例1.1 如圖所示，如何截取x使鐵皮所圍成的容積最大？,線性規(guī)劃問題的數(shù)學(xué)模型,例1.2 某企業(yè)計劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分別要在A、B、C、D、四種不同的設(shè)備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺時如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計劃，使企業(yè)總的利潤最大？,線性規(guī)劃問題的數(shù)學(xué)模型,解：設(shè)x1、x2分別為甲、乙兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為：,線性規(guī)劃問題的數(shù)學(xué)模型,2. 線性規(guī)劃的數(shù)學(xué)模型由三個要素構(gòu)成,決策變量 Decision variables 目標函數(shù) Objective function 約束條件 Constraints,其特征是： （1

7、）問題的目標函數(shù)是多個決策變量的線性函數(shù)，通常是求最大值或最小值； （2）問題的約束條件是一組多個決策變量的線性不等式或等式。 （3）系數(shù)是確定的，決策變量可允許用分數(shù)值,怎樣辨別一個模型是線性規(guī)劃模型？,線性規(guī)劃問題的數(shù)學(xué)模型,目標函數(shù)：,約束條件：,3. 線性規(guī)劃數(shù)學(xué)模型的一般形式,線性規(guī)劃問題的數(shù)學(xué)模型,向量形式：,其中：,線性規(guī)劃問題的數(shù)學(xué)模型,矩陣形式：,其中：,線性規(guī)劃問題的數(shù)學(xué)模型,3. 線性規(guī)劃問題的標準形式,特點： (1) 目標函數(shù)求最大值（本書規(guī)定，有些書規(guī)定求最小值）； (2) 約束條件都為等式方程，且右端常數(shù)項bi0； (3) 決策變量xj為非負。,線性規(guī)劃問題的數(shù)學(xué)模

8、型,（2）如何化標準形式,目標函數(shù)的轉(zhuǎn)換,若存在取值無約束的變量 ，可令 其中：,變量的變換,線性規(guī)劃問題的數(shù)學(xué)模型,約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。,稱為松弛變量,松弛變量,變量 的變換,可令 ，顯然,線性規(guī)劃問題的數(shù)學(xué)模型,例1.3 將下列線性規(guī)劃問題化為標準形式,線性規(guī)劃問題的數(shù)學(xué)模型,(2) 第一個約束條件是“”號，在“”左端加入松馳變量x4，x40,化為等式； (3) 第二個約束條件是“”號，在“”左端減去松弛變量x5，x50； (4) 第3個約束方程右端常數(shù)項為-5，方程兩邊同乘以(-1),將右端常數(shù)項化為正數(shù)； (5) 目標函數(shù)是最小值，為了化為求最大值，令z=-z,得到ma

9、x z=-z，即當z達到最小值時z達到最大值，反之亦然;,線性規(guī)劃問題的數(shù)學(xué)模型,標準形式如下：,線性規(guī)劃問題的數(shù)學(xué)模型,4. 線性規(guī)劃問題的解,考慮標準線性規(guī)劃問題,求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組中找出一個解，使目標函數(shù)(1)達到最大值。,線性規(guī)劃問題的數(shù)學(xué)模型,可行解：滿足約束條件、的解為可行解。所有可行解的集合為可行域。 最優(yōu)解：使目標函數(shù)達到最大值的可行解。 基：設(shè)A為約束條件的mn階系數(shù)矩陣(mn)，其秩為m，B是矩陣A中m階滿秩子矩陣（B0），稱B是規(guī)劃問題的一個基。不妨設(shè)：,稱 B中每個列向量pj ( j = 1 , ,m) 為基向量。與基向量pj 對

10、應(yīng)的變量xj 為基變量。除基變量以外的變量為非基變量。,基本解：某一確定的基B，令非基變量等于零，由約束條件方程解出基變量，稱這組解為對應(yīng)于基B的基本解。 基本可行解：滿足變量非負約束條件的基本解，簡稱基可行解。 可行基：對應(yīng)于基可行解的基稱為可行基。,線性規(guī)劃問題的數(shù)學(xué)模型,基可行解數(shù)基解數(shù),線性規(guī)劃問題的數(shù)學(xué)模型,例1.4 求線性規(guī)劃問題的所有基矩陣。,解: 約束方程的系數(shù)矩陣為25矩陣,r(A)=2，2階子矩陣有10個，其中基矩陣只有9個，即,圖解法,線性規(guī)劃問題的求解方法,一 般 有 兩種方法,圖 解 法 單純形法,兩個變量、直角坐標 三個變量、立體坐標,適用于任意變量、但必需將 一般

11、形式變成標準形式,下面我們分析一下簡單的情況 只有兩個決策變量的線性規(guī)劃問題，這時可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點。,圖解法,max Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8 s.t. X1 + 1.9X2 10.2 X1 - 1.9X2 -3.8 X1 ，X2 0,例1.5 用圖解法求解線性規(guī)劃問題,圖解法,x1,x2,o,X1 - 1.9X2 = 3.8(),X1 + 1.9X2 = 3.8(),X1 - 1.9X2 = -3.8 (),X1 + 1.9X2 = 10.2(),17.2

12、 = 2X1 + X2,Lo： 0 = 2X1 + X2,（7.6，2）,D,max Z,min Z,此點是唯一最優(yōu)解， 且最優(yōu)目標函數(shù)值 max Z=17.2,可行域,max Z = 2X1 + X2,圖解法,max Z=3X1+5.7X2,x1,x2,o,X1 - 1.9X2 = 3.8 (),X1 + 1.9X2 = 3.8(),X1 - 1.9X2 = -3.8(),X1 + 1.9X2 = 10.2 (),（7.6，2）,D,L0： 0=3X1+5.7X2,max Z,（3.8，4）,34.2 = 3X1+5.7X2,藍色線段上的所有點都是最 優(yōu)解這種情形為有無窮多最 優(yōu)解，但是最優(yōu)

13、目標函數(shù)值 max Z=34.2是唯一的。,可行域,圖解法,2,4,6,x1,x2,2,4,6,無界解(無最優(yōu)解),max Z=x1+2x2,例1.6,x1+x2=4(),x1+3x2=6(),3x1+x2=6(),max Z,min Z,x1,x2,O,10,20,30,40,10,20,30,40,50,50,無可行解(即無最優(yōu)解),max Z=3x1+4x2,例1.7,圖解法,學(xué)習(xí)要點： 1. 通過圖解法了解線性規(guī)劃有幾種解的形式 （唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解） 2. 作圖的關(guān)鍵有三點： (1) 可行解區(qū)域要畫正確 (2) 目標函數(shù)增加的方向不能畫錯 (3) 目標函數(shù)的直

14、線怎樣平行移動,單純形法基本原理,凸集：如果集合C中任意兩個點X1、X2，其連線上的所有點也都是集合C中的點，稱C為凸集。, 凸集：設(shè)S是n維歐氏空間的一個點集，若滿足下式：,則稱S為凸集。 極點：設(shè)S為凸集，zS，若z不能表示為S中任意兩點x,yS(xy)的 凸組合，即,則x為S的一個極點。,單純形法基本原理,定理1：若線性規(guī)劃問題存在可行解，則該問題的可行域是凸集。,定理3：若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解。（或在某個頂點取得）,定理2：線性規(guī)劃問題的基可行解x對應(yīng)可行域(凸集)的頂點。,單純形法的計算步驟,單純形法的思路,找一個初始基本可行解,是否最優(yōu),轉(zhuǎn)移到另一個基

15、本可行解 （使目標函數(shù)值增大）,最優(yōu)解,是,否,循 環(huán),核心是：基本可行解的迭代,結(jié)束,單純形法的計算步驟,單純形表,單純形法的計算步驟,例1.8 用單純形法求下列線性規(guī)劃的最優(yōu)解,解：1）引入松馳變量x3、x4，將原問題化為標準形式:,單純形法的計算步驟,2）求出線性規(guī)劃的初始基可行解，列出初始單純形表。,檢驗數(shù),確定進基變量。令 ，選擇對應(yīng)的xk作為進基變量。 （無界解判斷）若進基列向量 ，問題無界，計算停止。 確定出基變量。根據(jù)下式計算 和 r，并把第 r 個基變量換出。,如果表中所有檢驗數(shù) ，則表中的基可行解就是問題的最優(yōu)解，計算停止。否則繼續(xù)下一步。,單純形法的計算步驟,3）進行最優(yōu)

16、性檢驗,4）從一個基可行解轉(zhuǎn)換到另一個目標值更大的基可行解，列出新的單純形表,單純形法的計算步驟, 用進基變量xk替換基變量中的出基變量xl，得到一個新的基。對應(yīng)新的基可以找出一個新的基可行解，并相應(yīng)地可以畫出一個新的單純形表。 （以 為主元，亦稱為旋轉(zhuǎn)元，進行行變換，得到新的單純形表） 5）重復(fù)3）、4）步直到計算結(jié)束為止。,單純形法的計算步驟,進基列,bi /ai2，ai20,40,10,出基行,5/3,1,18,0,1/3,0,1/3,10,1,1/3,30,30,0,5/3,0,4/3,將5/3化為 1,1,0,3/5,1/5,18,0,1,1/5,2/5,4,0,0,1,1,將3化為

17、1，進行行變換, , ,單純形法的計算步驟,例1.9 用單純形法求解,解：將數(shù)學(xué)模型化為標準形式：,不難看出x4、x5可作為初始基變量，列單純形表計算。,單純形法的計算步驟,20,x2,2,1/3,1,5,0,1,20,75,3,0,17,1,3,1/3,0,9,0,2,25,60,x1,1,1,0,17/3,1/3,1,25,0,1,28/9,-1/9,2/3,35/3,0,0,-98/9,-1/9,-7/3, , ,單純形法的計算步驟,學(xué)習(xí)要點： 1. 線性規(guī)劃解的概念以及3個基本定理 2. 熟練掌握單純形法的解題思路及求解步驟,單純形法的進一步討論人工變量法,1 人工變量法（大M法）：

18、前面討論了在標準型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，這種用人工變量作橋梁的求解方法稱為人工變量法（大M法） 。,單純形法的進一步討論人工變量法,例1.10 用大M法解下列線性規(guī)劃,解：首先將數(shù)學(xué)模型化為標準形式,系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。,單純形法的進一步討論人工變量法,故人為添加兩個單位向量，得到人工變量單純形法數(shù)學(xué)模型：,其中：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為

19、它能大于給定的任何一個確定數(shù)值；再用前面介紹的單純形法求解該模型，計算結(jié)果見下表。,單純形法的進一步討論人工變量法,2 兩階段法第一階段 求解一個目標函數(shù)僅含人工變量，且為最小化的LP問題，可能兩種結(jié)果： (1)所有人工變量都為0，轉(zhuǎn)第二階段 (2)人工變量不全為0，原問題無可行解第二階段 去掉第一階段中的人工變量，將第一階段得到的最優(yōu)解作為初始可行解，利用單純形法繼續(xù)求解,單純形法的進一步討論人工變量法,單純性法小結(jié):,A,線性規(guī)劃模型的應(yīng)用,一般而言，一個經(jīng)濟、管理問題凡是滿足以下條件時，才能建立線性規(guī)劃模型。,要求解問題的目標函數(shù)能用數(shù)值指標來反映，且為線性函數(shù) 存在著多種方案 要求達到

20、的目標是在一定條件下實現(xiàn)的，這些約束可用線性等式或不等式描述,線性規(guī)劃在管理中的應(yīng)用,人力資源分配問題,例1.11 某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員人數(shù)如下表所示：,設(shè)司機和乘務(wù)人員分別在各時間段開始時上班，并連續(xù)工作8小時，問該公交線路應(yīng)怎樣安排司機和乘務(wù)人員，即能滿足工作需要，又使配備司機和乘務(wù)人員的人數(shù)減少?,線性規(guī)劃在管理中的應(yīng)用,解：設(shè)xi表示第i班次時開始上班的司機和乘務(wù)人員人數(shù)。,此問題最優(yōu)解：x150， x220， x350， x40， x520， x610，一共需要司機和乘務(wù)員150人。,線性規(guī)劃在管理中的應(yīng)用,2. 生產(chǎn)計劃問題,某廠生產(chǎn)、三種產(chǎn)品，都分

21、別經(jīng)A、B兩道工序加工。設(shè)A工序可分別在設(shè)備A1和A2上完成，有B1、B2、B3三種設(shè)備可用于完成B工序。已知產(chǎn)品可在A、B任何一種設(shè)備上加工；產(chǎn)品可在任何規(guī)格的A設(shè)備上加工，但完成B工序時，只能在B1設(shè)備上加工；產(chǎn)品只能在A2與B2設(shè)備上加工。加工單位產(chǎn)品所需工序時間及其他各項數(shù)據(jù)如下表，試安排最優(yōu)生產(chǎn)計劃，使該廠獲利最大。,線性規(guī)劃在管理中的應(yīng)用,線性規(guī)劃在管理中的應(yīng)用,解：設(shè)xijk表示產(chǎn)品i在工序j的設(shè)備k上加工的數(shù)量。約束條件有：,線性規(guī)劃在管理中的應(yīng)用,目標是利潤最大化，即利潤的計算公式如下：,帶入數(shù)據(jù)整理得到：,線性規(guī)劃在管理中的應(yīng)用,因此該規(guī)劃問題的模型為：,線性規(guī)劃在管理中的

22、應(yīng)用,3. 套裁下料問題,例：現(xiàn)有一批某種型號的圓鋼長8米，需要截取2.5米長的毛坯100根，長1.3米的毛坯200根。問如何才能既滿足需要，又能使總的用料最少？,解：為了找到一個省料的套裁方案，必須先設(shè)計出較好的幾個下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格的圓鋼，以滿足對各種不同規(guī)格圓鋼的需要并達到省料的目的，為此可以設(shè)計出4種下料方案以供套裁用。,線性規(guī)劃在管理中的應(yīng)用,設(shè)按方案、下料的原材料根數(shù)分別為xj (j=1，2,3,4)，可列出下面的數(shù)學(xué)模型：,線性規(guī)劃在管理中的應(yīng)用,4. 配料問題,例：某人每天食用甲、乙兩種食物（如豬肉、雞蛋），其資料如下：問兩種食物各食用多少，才能

23、既滿足需要、又使總費用最?。?線性規(guī)劃在管理中的應(yīng)用,解：設(shè)Xj 表示Bj 種食物用量,Chapter2 對偶理論 ( Duality Theory ),線性規(guī)劃的對偶模型 對偶性質(zhì) 對偶問題的經(jīng)濟解釋影子價格 對偶單純形法,本章主要內(nèi)容：,線性規(guī)劃的對偶模型,設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需4種設(shè)備按A，B，C，D順序加工，每件產(chǎn)品加工所需的機時數(shù)、每件產(chǎn)品的利潤值及每種設(shè)備的可利用機時數(shù)列于下表 ：,產(chǎn)品數(shù)據(jù)表,問：充分利用設(shè)備機時，工廠應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能獲得最大利潤？,1. 對偶問題的現(xiàn)實來源,線性規(guī)劃的對偶模型,解：設(shè)甲、乙型產(chǎn)品各生產(chǎn)x1及x2件，則數(shù)學(xué)模型為：,反過

24、來問：若廠長決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機器用于接受外加工，只收加工費，那么種機器的機時如何定價才是最佳決策？,線性規(guī)劃的對偶模型,在市場競爭的時代，廠長的最佳決策顯然應(yīng)符合兩條： （1）不吃虧原則。即機時定價所賺利潤不能低于加工甲、乙型產(chǎn)品所獲利潤。由此原則，便構(gòu)成了新規(guī)劃的不等式約束條件。 （2）競爭性原則。即在上述不吃虧原則下，盡量降低機時總收費，以便爭取更多用戶。,設(shè)A、B、C、D設(shè)備的機時價分別為y1、y2、y3、y4，則新的線性規(guī)劃數(shù)學(xué)模型為：,線性規(guī)劃的對偶模型,把同種問題的兩種提法所獲得的數(shù)學(xué)模型用表2表示，將會發(fā)現(xiàn)一個有趣的現(xiàn)象。,原問題與對偶問題對比表,線性規(guī)劃的對偶模

25、型,2. 原問題與對偶問題的對應(yīng)關(guān)系,原問題 （對偶問題）,對偶問題 （原問題）,線性規(guī)劃的對偶模型,（1）對稱形式,原問題和對偶問題是互為對偶的,特點：目標函數(shù)求極大值時，所有約束條件為號，變量非負;目標函數(shù)求極小值時，所有約束條件為號，變量非負.,定義線性規(guī)劃問題P(原)的對偶問題為D,線性規(guī)劃的對偶模型,例2.1 寫出線性規(guī)劃問題的對偶問題,解：首先將原問題變形為對稱形式,線性規(guī)劃的對偶模型,線性規(guī)劃的對偶模型,(2) 非對稱型對偶問題,若給出的線性規(guī)劃不是對稱形式，可以先化成對稱形式再寫對偶問題。,寫出下面線性規(guī)劃的對偶規(guī)劃：,線性規(guī)劃的對偶模型,線性規(guī)劃的對偶模型,例2.2 寫出下列

26、線性規(guī)劃問題的對偶問題.,解：原問題的對偶問題為,對偶性質(zhì),例2.3 分別求解下列2個互為對偶關(guān)系的線性規(guī)劃問題,分別用單純形法求解上述2個規(guī)劃問題，得到最終單純形表如下表：,對偶性質(zhì),原問題最優(yōu)表,對偶問題最優(yōu)表,對偶性質(zhì),原問題與其對偶問題的變量與解的對應(yīng)關(guān)系： 在單純形表中，原問題的松弛變量對應(yīng)對偶問題的變量，對偶問題的剩余變量對應(yīng)原問題的變量。,對偶性質(zhì),性質(zhì)1 對稱性定理：對偶問題的對偶是原問題,（P）,（D）,對偶性質(zhì),性質(zhì)2 弱對偶原理(弱對偶性)：設(shè) 和 分別是原問題(P)和其對偶問題(D)的可行解，則必有,推論1: 原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下屆；反

27、之，對偶問題任意可行解的目標函數(shù)值是其原問題目標函數(shù)值的上界。,推論2: 在一對對偶問題（P）和（D）中，若其中一個問題可行但目標函數(shù)無界，則另一個問題無可行解；反之不成立。這也是對偶問題的無界性。,對偶性質(zhì),性質(zhì)4 強對偶性：若原問題有最優(yōu)解，則其對偶問題也一定有最優(yōu)解，且它們的最優(yōu)值相等。,推論3：在一對對偶問題（P）和（D）中，若一個可行（如P），而另一個不可行（如D），則該可行的問題目標函數(shù)值無界。,對偶性質(zhì),還可推出另一結(jié)論：若原問題與其對偶問題都有可行解，則兩者都有最優(yōu)解，若一個問題無最優(yōu)解，則另一問題也無最優(yōu)解。,性質(zhì)5 互補松弛性：設(shè) 和 分別是P問題 和 D問題 的可行 解，

28、則它們分別是最優(yōu)解的充要條件是：,對偶性質(zhì),性質(zhì)5（互補松弛性）的應(yīng)用： 該性質(zhì)給出了已知一個問題最優(yōu)解求另一個問題最優(yōu)解的方法，即已知x求y或已知y求x,互補松弛條件,由于變量都非負，要使求和式等于零，則必定每一分量為零，因而有下列關(guān)系： 若 , 則必有 ；若 0，則必有 利用上述關(guān)系，建立對偶問題（或原問題）的約束線性方程組，方程組的解即為最優(yōu)解。,對偶性質(zhì),例2.4 已知線性規(guī)劃,的最優(yōu)解是X=(6,2,0)T,求其對偶問題的最優(yōu)解Y。,解：寫出原問題的對偶問題，即,對偶性質(zhì),設(shè)對偶問題最優(yōu)解為Y(y1，y2),由互補松弛性定理可知，,解此線性方程組得y1=1,y2=1,從而對偶問題的最

29、優(yōu)解為： Y=(1,1)，最優(yōu)值w=26。,對偶性質(zhì),例2.5 已知線性規(guī)劃,的對偶問題的最優(yōu)解為Y=(0,-2)，求原問題的最優(yōu)解。,解: 對偶問題是,對偶性質(zhì),設(shè)對偶問題最優(yōu)解為X(x1，x2 ，x3)T ,由互補松弛性定理可知，X和 Y滿足：,x20,解方程組得：x1=-5,x3=-1, 所以原問題的最優(yōu)解為,X=(-5,0,-1)，最優(yōu)值z=-12,對偶性質(zhì),原問題與對偶問題解的對應(yīng)關(guān)系小結(jié),思考題,判斷下列結(jié)論是否正確，如果不正確，應(yīng)該怎樣改正？,1）任何線性規(guī)劃都存在一個對應(yīng)的對偶線性規(guī)劃. 2）原問題第i個約束是“”約束，則對偶變量yi0. 3）互為對偶問題，或者同時都有最優(yōu)解，

30、或者同時都無最優(yōu)解. 4）對偶問題有可行解，則原問題也有可行解. 5）原問題有多重解，對偶問題也有多重解. 6）對偶問題有可行解，原問題無可行解，則對偶問題具有無界解. 7）原問題無最優(yōu)解，則對偶問題無可行解. 8）對偶問題不可行，原問題可能無界解. 9）原問題與對偶問題都可行，則都有最優(yōu)解. 10）原問題具有無界解，則對偶問題不可行. 11）對偶問題具有無界解，則原問題無最優(yōu)解. 12）若X*、Y*是原問題與對偶問題的最優(yōu)解，則X*=Y*.,對偶問題的經(jīng)濟解釋影子價格,1. 影子價格的數(shù)學(xué)分析：,定義：在一對 P 和 D 中，若 P 的某個約束條件的右端項常數(shù)bi （第i種資源的擁有量）增加

31、一個單位時，所引起目標函數(shù)最優(yōu)值z* 的改變量稱為第 i 種資源的影子價格，其值等于D問題中對偶變量yi*。,由對偶問題得基本性質(zhì)可得：,對偶問題的經(jīng)濟解釋影子價格,2. 影子價格的經(jīng)濟意義 1）影子價格是一種邊際價格 在其它條件不變的情況下，單位資源數(shù)量的變化所引起的目標函數(shù)最優(yōu)值的變化。即對偶變量yi 就是第 i 種資源的影子價格。即：,對偶問題的經(jīng)濟解釋影子價格,2）影子價格是一種機會成本 影子價格是在資源最優(yōu)利用條件下對單位資源的估價，這種估價不是資源實際的市場價格。因此，從另一個角度說，它是一種機會成本。,若第i 種資源的單位市場價格為mi ，則有當yi* mi 時，企業(yè)愿意購進這種

32、資源，單位純利為yi*mi ，則有利可圖；如果yi* mi ，則企業(yè)有償轉(zhuǎn)讓這種資源，可獲單位純利miyi * ，否則，企業(yè)無利可圖，甚至虧損。,結(jié)論：若yi* mi 則購進資源i，可獲單位純利yi*mi 若yi* mi則轉(zhuǎn)讓資源i ，可獲單位純利miyi,對偶問題的經(jīng)濟解釋影子價格,3）影子價格在資源利用中的應(yīng)用 根據(jù)對偶理論的互補松弛性定理: Y*Xs=0 , YsX*=0 表明生產(chǎn)過程中如果某種資源bi未得到充分利用時，該種資源的影子價格為0；若當資源的影子價格不為0時，表明該種資源在生產(chǎn)中已耗費完。,對偶問題的經(jīng)濟解釋影子價格,4）影子價格對單純形表計算的解釋,單純形表中的檢驗數(shù),其中

33、cj表示第j種產(chǎn)品的價格; 表示生產(chǎn)該種產(chǎn)品所消耗的各項資源的影子價格的總和,即產(chǎn)品的隱含成本。,當產(chǎn)值大于隱含成本時，即 ，表明生產(chǎn)該項產(chǎn)品有利，可在計劃中安排；否則 ，用這些資源生產(chǎn)別的產(chǎn)品更有利，不在生產(chǎn)中安排該產(chǎn)品。,對偶單純形法,對偶單純形法是求解線性規(guī)劃的另一個基本方法。它是根據(jù)對偶原理和單純形法原理而設(shè)計出來的，因此稱為對偶單純形法。不要簡單理解為是求解對偶問題的單純形法。,對偶單純形法原理,對偶單純形法的基本思路： 從原問題的一個基本解出發(fā)，此基本解不一定可行，但它的檢驗數(shù)非正（即對應(yīng)著一個對偶可行解）；然后檢驗當前基本解是否可行，即是否有負的分量，如果有小于零的分量，則進行迭

34、代，求另一個基本解，此基本解對應(yīng)著另一個對偶可行解（檢驗數(shù)仍然非正）。,如果得到的基本解是可行的（分量皆非負），則該基本可行解為最優(yōu)解。也就是說，對偶單純形法在迭代過程中始終保持對偶解的可行性（即檢驗數(shù)非正），使原問題的基本解由不可行逐步變?yōu)榭尚?，當同時得到對偶問題與原問題的可行解時，便得到原規(guī)劃的最優(yōu)解。,Step 1. 建立初始對偶單純形表,對應(yīng)一個基本解,所有檢驗數(shù)均非正( j0)； Step 2. 若右端項 b0,則得到最優(yōu)解,停止；否則,令br =minbi,則選第 r 行的基變量為出基變量； Step 3. 若第r 行所有元素arj0，則原問題無可行解,停止；否則，令 k / ar

35、k =minj / arjarj0，則選擇 xk 為進基變量； Step 4.以 ark 為轉(zhuǎn)軸元，作矩陣行變換使其變?yōu)?,該列其他元變?yōu)?,轉(zhuǎn)Step 2。,對偶單純形法求解線性規(guī)劃問題過程：,對偶單純形法,例2.9 用對偶單純形法求解：,解:（1）將模型轉(zhuǎn)化為求最大化問題，約束方程化為等式求出一組基本解，因為對偶問題可行，即全部檢驗數(shù)0（求max問題）。,對偶單純形法,對偶單純形法,對偶單純形法,原問題的最優(yōu)解為：X*=（2 , 2 , 2 , 0 , 0 , 0），Z* =72,例 用對偶單純形法求解：,對偶單純形法,對偶單純形法應(yīng)注意的問題：,用對偶單純形法求解線性規(guī)劃是一種求解方法，

36、是在原始問題的單純形表格上進行對偶處理，而不是解對偶問題的單純形法！,初始表中一定要滿足對偶問題可行，也就是說檢驗數(shù)非正,對偶單純形法與（原始）單純形法的換基順序不一樣，單純形法是先確定進基變量后確定出基變量，對偶單純形法是先確定出基變量后確定進基變量；,對偶單純形法,普通單純形法的最小比值是 其目的是保證下一個原問題的基本解可行，對偶單純形法的最小比值是,其目的是保證下一個對偶問題的基本解可行,對偶單純形法在確定出基變量時，若不遵循 規(guī)則，任選一個小于零的bi對應(yīng)的基變量出基，不影響計算結(jié)果，只是迭代次數(shù)可能不一樣。,本章小結(jié),學(xué)習(xí)要點： 1. 線性規(guī)劃解的概念以及3個基本定理 2. 熟練掌

37、握單純形法的解題思路及求解步驟,Chapter3 運輸規(guī)劃( Transportation Problem ),運輸規(guī)劃問題的數(shù)學(xué)模型 表上作業(yè)法 運輸問題的應(yīng)用,本章主要內(nèi)容：,運輸問題網(wǎng)絡(luò)圖,供應(yīng)地,運價,需求地,供應(yīng)量,需求量,總供應(yīng)量60噸,總需求量60噸,供求平衡的運輸問題,運輸問題線性規(guī)劃模型,供應(yīng)地約束,需求地約束,由于前m個供應(yīng)地約束和后n個需求地約束是線性相關(guān)的，因此運輸問題系數(shù)矩陣的秩m+n。可以證明，運輸問題系數(shù)矩陣的秩為m+n-1。即運輸問題有m+n-1個基變量，mn-(m+n-1)個非基變量。例如以上問題m=3，n=4，基變量為3416個，非基變量為1266個。,運輸

38、問題的表格表示,運輸規(guī)劃問題的數(shù)學(xué)模型,例 某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1, B2, B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最??？,運輸規(guī)劃問題的數(shù)學(xué)模型,解：產(chǎn)銷平衡問題：總產(chǎn)量 = 總銷量500 設(shè) xij 為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列運輸量表：,Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13

39、 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3）,運輸規(guī)劃問題的數(shù)學(xué)模型,運輸問題的一般形式：產(chǎn)銷平衡,A1、 A2、 Am 表示某物資的m個產(chǎn)地； B1、B2、Bn 表示某物質(zhì)的n個銷地；ai 表示產(chǎn)地Ai的產(chǎn)量； bj 表示銷地Bj 的銷量； cij 表示把物資從產(chǎn)地Ai運往銷地Bj的單位運價。設(shè) xij 為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列一般運輸量問題的模型：,運輸規(guī)劃問題的數(shù)學(xué)模型,變化： 1）有時目標函數(shù)求最大。如求利潤最大或營業(yè)額最大等； 2）當某些運輸線路上的能力有限制時，在模型中直接加入約束條件（等式或不等式約束)； 3）產(chǎn)銷不平衡時，可加

40、入假想的產(chǎn)地（銷大于產(chǎn)時）或銷地（產(chǎn)大于銷時）。,定理: 設(shè)有m個產(chǎn)地n個銷地且產(chǎn)銷平衡的運輸問題，則基變量數(shù)為m+n-1。,運輸問題基的表示,m個供應(yīng)地、n個需求地的運輸問題，任何一個基要滿足以下三個條件： 基變量的個數(shù)為m+n-1； 同行同列的基變量不能形成回路； 運輸表的每一行和每一列中至少有一個基變量。,基在運輸表中的表示,運輸表中同行同列的變量組成回路,初始基礎(chǔ)可行解西北角法,8,13,13,14,6,6,表上作業(yè)法,表上作業(yè)法是一種求解運輸問題的特殊方法，其實質(zhì)是單純形法。,表上作業(yè)法,例3.2 某運輸資料如下表所示：,問：應(yīng)如何調(diào)運可使總運輸費用最??？,表上作業(yè)法,解：第1步 求

41、初始調(diào)運方案,方法1：最小元素法 基本思想是從運價最小的地方開始供應(yīng)（調(diào)運），然后次小，直到最后供完為止。,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,表上作業(yè)法,總的運輸費(31)+(64) +(43) +(12)+(310)+(35)=86元,最小元素法給定的初始方案只從局部觀點考慮，而未考慮到產(chǎn)地到銷地的最小運價和次小運價之間的差額，可能造成總體運費偏高，不太合理。例如下面兩種運輸方案。,15,5,10,總運費是z=108+52+151=105,最小元素法：,表上作業(yè)法,5,15,10,總運費z=105+152+51=85,若考慮到c11與c21之間的差

42、額是82=6，如果不先調(diào)運x21，到后來就有可能x110，這樣會使總運費增加較大，從而先調(diào)運x21，再是x22，其次是x12,表上作業(yè)法,方法2：Vogel法（元素差額法）,1）從運價表中分別計算出各行和各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行。,3,11,3,10,1,9,2,7,4,10,5,8,表上作業(yè)法,2）再從差值最大的行或列中找出最小運價確定供需關(guān)系和供需數(shù)量。當產(chǎn)地或銷地中有一方數(shù)量供應(yīng)完畢或得到滿足時，劃去運價表中對應(yīng)的行或列。 重復(fù)1)和2)，直到找出初始解為至。,3,11,3,10,1,9,2,7,4,10,5,8,5,表上作業(yè)法,7,1,1,3,5,2

43、,1,5,表上作業(yè)法,7,1,3,5,2,7,5,3,表上作業(yè)法,1,1,3,5,1,5,3,6,3,1,2,該方案的總運費: (13)(46)(35)(210)(18)(35)85元,表上作業(yè)法,第2步 最優(yōu)解的判別（檢驗數(shù)的求法）,求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗數(shù)來判斷，記xij的檢驗數(shù)為ij由第一章知，求最小值的運輸問題的最優(yōu)判別準則是：,所有非基變量的檢驗數(shù)都非負，則運輸方案最優(yōu),求檢驗數(shù)的方法有兩種： 閉回路法 位勢法（）,表上作業(yè)法,用位勢法對初始方案進行最優(yōu)性檢驗：,3,11,3,10,1,9,2,7,4,10,5,8,4,3,6,3,1,3,0,-1,-5,

44、3,10,2,9,（1）,（2）,（1）,（-1）,（10）,（12）,若所有非基變量的檢驗數(shù)ij 0，說明現(xiàn)行方案為最優(yōu)方案，否則目標成本還可以進一步減小。,1）由ij = cij （ui+vj）計算位勢ui ， vj ，因為對基變量 xij 而言有ij = 0，即 cij （ui+vj） = 0，令u1=0,2）再由ij=cij （ui+vj）計算非基變量的檢驗數(shù)ij,表上作業(yè)法,第3步 方案的調(diào)整（閉回路調(diào)整法）,表上作業(yè)法,閉回路的概念,為一個閉回路 ，集合中的變量稱為回路的頂點，相鄰兩個變量的連線為閉回路的邊。如下表,表上作業(yè)法,例下表中閉回路的變量集合是x11,x12,x42,x4

45、3,x23,x25,x35, x31共有8個頂點，這8個頂點間用水平或垂直線段連接起來，組成一條封閉的回路。,一條回路中的頂點數(shù)一定是偶數(shù)，回路遇到頂點必須轉(zhuǎn)90度與另一頂點連接，表中的變量x 32及x33不是閉回路的頂點，只是連線的交點。,表上作業(yè)法,閉回路,例如變量組 不能構(gòu)成一條閉回路，但A中包含有閉回路,變量組 變量數(shù)是奇數(shù)，顯然不是閉回路，也不含有閉回路；,表上作業(yè)法,3,11,3,10,1,9,2,7,4,10,5,8,4,3,6,3,1,3,(),(),(),(),調(diào)整步驟為：在進基變量的閉回路中標有正號的變量加上調(diào)整量，標有負號的變量減去調(diào)整量，其余變量不變，得到一組新的基可行

46、解。然后求所有非基變量的檢驗數(shù)重新檢驗。,1,2,5,表上作業(yè)法,當所有非基變量的檢驗數(shù)均非負時，則當前調(diào)運方案即為最優(yōu)方案，如表此時最小總運費： Z =(13)(46)(35)(210)(18)(35)85元,3,11,3,10,1,9,2,7,4,10,5,8,5,3,6,3,1,2,0,-2,-5,3,10,3,9,（0）,（2）,（2）,（1）,（12）,（9）,表上作業(yè)法,表上作業(yè)法的計算步驟：,分析實際問題列出產(chǎn)銷平衡表及單位運價表,確定初始調(diào)運方案（最小元素法或Vogel法）,求檢驗數(shù)（位勢法）,所有檢驗數(shù)0?,找出絕對值最大的負檢驗數(shù)，用閉合回路調(diào)整，得到新的調(diào)運方案,得到最優(yōu)

47、方案，算出總運價,Y,N,表上作業(yè)法,表上作業(yè)法計算中的問題：,（1）若運輸問題的某一基可行解有多個非基變量的檢驗數(shù)為負，在繼續(xù)迭代時，取它們中任一變量為換入變量均可使目標函數(shù)值得到改善，但通常取ij0中最小者對應(yīng)的變量為換入變量。 （2）無窮多最優(yōu)解 產(chǎn)銷平衡的運輸問題必定存最優(yōu)解。如果非基變量的ij0，則該問題有無窮多最優(yōu)解。,表上作業(yè)法, 退化解： 因為基變量個數(shù)為(m+n-1)個，因此表格中必須有(m+n-1)個數(shù)字格。若在分配運量時既可劃去一行，又可劃去一列，這時只能選擇要么劃去行，要么劃去列，而不能同時劃去。此情形，會出現(xiàn)數(shù)字0的格子。 利用進基變量的閉回路對解進行調(diào)整時，標有負號

48、的最小運量（超過2個最小值）作為調(diào)整量，選擇任意一個最小運量對應(yīng)的基變量作為出基變量，并打上“”以示作為非基變量。,表上作業(yè)法,12,4,11,4,8,3,10,2,9,5,11,6,(0),(2),(9),(2),(1),(12),8,12,4,2,8,14,如下例中11檢驗數(shù)是 0，經(jīng)過調(diào)整，可得到另一個最優(yōu)解。,表上作業(yè)法,11,4,4,3,1,3,7,7,8,2,10,6,3,4,1,6,0,6,例：用最小元素法求初始可行解,運輸問題的應(yīng)用,求極大值問題 目標函數(shù)求利潤最大或營業(yè)額最大等問題。,運輸問題的應(yīng)用,求解方法： 將極大化問題轉(zhuǎn)化為極小化問題。設(shè)極大化問題的運價表為C ，用一個

49、較大的數(shù)M（Mmaxcij）去減每一個cij得到矩陣C，其中C=（Mcij）0,將C作為極小化問題的運價表，用表上用業(yè)法求出最優(yōu)解。,運輸問題的應(yīng)用,例3.3 下列矩陣C是Ai（I=1，2，3）到Bj的噸公里利潤,運輸部門如何安排運輸方案使總利潤最大.,運輸問題的應(yīng)用,得到新的最小化運輸問題，用表上作業(yè)法求解即可。,運輸問題的應(yīng)用,產(chǎn)銷不平衡的運輸問題 當總產(chǎn)量與總銷量不相等時,稱為不平衡運輸問題.這類運輸問題在實際中常常碰到,它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。,當產(chǎn)大于銷時，即：,數(shù)學(xué)模型為：,運輸問題的應(yīng)用,由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運送完，必須

50、就地庫存，即每個產(chǎn)地設(shè)一個倉庫，假設(shè)該倉庫為一個虛擬銷地Bn+1， bn+1作為一個虛設(shè)銷地Bn+1的銷量(即庫存量)。各產(chǎn)地Ai到Bn+1的運價為零，即Ci,n+1=0,（i=1，m）。則平衡問題的數(shù)學(xué)模型為：,具體求解時,只在運價表右端增加一列Bn+1，運價為零,銷量為bn+1即可,運輸問題的應(yīng)用,當銷大于產(chǎn)時，即：,數(shù)學(xué)模型為：,由于總銷量大于總產(chǎn)量,故一定有些需求地不完全滿足,這時虛設(shè)一個產(chǎn)地Am+1，產(chǎn)量為：,運輸問題的應(yīng)用,銷大于產(chǎn)化為平衡問題的數(shù)學(xué)模型為 ：,具體計算時，在運價表的下方增加一行Am+1，運價為零。產(chǎn)量為am+1即可。,運輸問題的應(yīng)用,例3.4 求下列表中極小化運輸

51、問題的最優(yōu)解。,因為有：,運輸問題的應(yīng)用,所以是一個產(chǎn)大于銷的運輸問題。表中A2不可達B1，用一個很大的正數(shù)M表示運價C21。虛設(shè)一個銷量為b5=180-160=20，Ci5=0，i=1,2,3,4，表的右邊增添一列 ，得到新的運價表。,運輸問題的應(yīng)用,下表為計算結(jié)果。可看出：產(chǎn)地A4還有20個單位沒有運出。,運輸問題的應(yīng)用,3. 生產(chǎn)與儲存問題,例3.5 某廠按合同規(guī)定須于當年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如右表。如果生產(chǎn)出來的柴油機當季不交貨，每臺每積壓一個季度需儲存、維護等費用0.15萬元。試求在完成合同的情況下

52、，使該廠全年生產(chǎn)總費用為最小的決策方案。,運輸問題的應(yīng)用,解： 設(shè) xij為第 i 季度生產(chǎn)的第 j 季度交貨的柴油機數(shù)目，那么應(yīng)滿足： 交貨： x11 = 10 生產(chǎn)：x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10,把第 i 季度生產(chǎn)的柴油機數(shù)目看作第 i 個生產(chǎn)廠的產(chǎn)量；把第 j 季度交貨的柴油機數(shù)目看作第 j 個銷售點的銷量；設(shè)cij是第i季度生產(chǎn)的第j季度交貨的每臺柴油機的實際成本，

53、應(yīng)該等于該季度單位成本加上儲存、維護等費用?？蓸?gòu)造下列產(chǎn)銷平衡問題：,運輸問題的應(yīng)用,由于產(chǎn)大于銷，加上一個虛擬的銷地D，化為平衡問題，即可應(yīng)用表上作業(yè)法求解。,運輸問題的應(yīng)用,該問題的數(shù)學(xué)模型： Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44,運輸問題的應(yīng)用,最優(yōu)生產(chǎn)決策如下表，最小費用z773萬元。,Chapter4 整數(shù)規(guī)劃( Integer Programming ),整數(shù)規(guī)劃的特點及應(yīng)用 分支定界法 分配問題與匈

54、牙利法,本章主要內(nèi)容：,整數(shù)規(guī)劃的特點及應(yīng)用,整數(shù)規(guī)劃（簡稱：IP） 要求一部分或全部決策變量取整數(shù)值的規(guī)劃問題稱為整數(shù)規(guī)劃。不考慮整數(shù)條件，由余下的目標函數(shù)和約束條件構(gòu)成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的松弛問題。若該松弛問題是一個線性規(guī)劃，則稱該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃。,整數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式：,整數(shù)規(guī)劃的特點及應(yīng)用,整數(shù)線性規(guī)劃問題的種類：,純整數(shù)線性規(guī)劃：指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃。 混合整數(shù)線性規(guī)劃：決策變量中有一部分必須取整數(shù)值，另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃。 0-1型整數(shù)線性規(guī)劃：決策變量只能取值0或1的整數(shù)線性規(guī)劃。,整數(shù)規(guī)劃的特點及應(yīng)用,整數(shù)規(guī)劃的

55、典型例子,例4.1 工廠A1和A2生產(chǎn)某種物資。由于該種物資供不應(yīng)求，故需要再建一家工廠。相應(yīng)的建廠方案有A3和A4兩個。這種物資的需求地有B1,B2,B3,B4四個。各工廠年生產(chǎn)能力、各地年需求量、各廠至各需求地的單位物資運費cij，見下表：,工廠A3或A4開工后，每年的生產(chǎn)費用估計分別為1200萬或1500萬元。現(xiàn)要決定應(yīng)該建設(shè)工廠A3還是A4，才能使今后每年的總費用最少。,整數(shù)規(guī)劃的特點及應(yīng)用,解：這是一個物資運輸問題，特點是事先不能確定應(yīng)該建A3還是A4中哪一個，因而不知道新廠投產(chǎn)后的實際生產(chǎn)物資。為此，引入0-1變量：,再設(shè)xij為由Ai運往Bj的物資數(shù)量，單位為千噸；z表示總費用，

56、單位萬元。 則該規(guī)劃問題的數(shù)學(xué)模型可以表示為：,整數(shù)規(guī)劃的特點及應(yīng)用,混合整數(shù)規(guī)劃問題,整數(shù)規(guī)劃的特點及應(yīng)用,例4.2 現(xiàn)有資金總額為B?？晒┻x擇的投資項目有n個，項目j所需投資額和預(yù)期收益分別為aj和cj（j1,2,.,n），此外由于種種原因，有三個附加條件： 若選擇項目1，就必須同時選擇項目2。反之不一定 項目3和4中至少選擇一個； 項目5,6,7中恰好選擇2個。 應(yīng)該怎樣選擇投資項目，才能使總預(yù)期收益最大。,整數(shù)規(guī)劃的特點及應(yīng)用,解：對每個投資項目都有被選擇和不被選擇兩種可能，因此分別用0和1表示，令xj表示第j個項目的決策選擇，記為：,投資問題可以表示為：,整數(shù)規(guī)劃的特點及應(yīng)用,例4.

57、3 指派問題或分配問題。人事部門欲安排四人到四個不同崗位工作，每個崗位一個人。經(jīng)考核四人在不同崗位的成績（百分制）如表所示，如何安排他們的工作使總成績最好。,整數(shù)規(guī)劃的特點及應(yīng)用,設(shè),數(shù)學(xué)模型如下：,要求每人做一項工作，約束條件為：,整數(shù)規(guī)劃的特點及應(yīng)用,每項工作只能安排一人，約束條件為：,變量約束：,分配問題與匈牙利法,指派問題的數(shù)學(xué)模型的標準形式：,設(shè)n 個人被分配去做n 件工作，規(guī)定每個人只做一件工作，每件工作只有一個人去做。已知第i個人去做第j 件工作的效率（ 時間或費用）為cij(i=1.2n;j=1.2n)并假設(shè)Cij 0。問應(yīng)如何分配才能使總效率（ 時間或費用）最高？,設(shè)決策變量

58、,分配問題與匈牙利法,指派問題的數(shù)學(xué)模型為：,分配問題與匈牙利法,克尼格定理 : 如果從分配問題效率矩陣cij的每一行元素中分別減去(或加上)一個常數(shù)ui，從每一列中分別減去(或加上)一個常數(shù)vj，得到一個新的效率矩陣bij，則以bij為效率矩陣的分配問題與以cij為效率矩陣的分配問題具有相同的最優(yōu)解。,分配問題與匈牙利法,指派問題的求解步驟：,1) 變換指派問題的系數(shù)矩陣(cij)為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即 從(cij)的每行元素都減去該行的最小元素； 再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。,2) 進行試指派，以尋求最優(yōu)解。 在(bij)中找盡可能多的獨立0元素，若能找出n個獨立0元素(不在同一行，同一列)，就以這n個獨立0元素對應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。,分配問題與匈牙利法,找獨立0元素，