《運籌學(xué)教程》胡云權(quán) 第五版 運籌學(xué)復(fù)習(xí)

1、運籌學(xué)復(fù)習(xí),,《運籌學(xué)》課程大綱,課程性質(zhì)：方法技能類 專業(yè)必須課 課時數(shù)：1-14周，3，42學(xué)時 課程框架 考核方案：作業(yè)（50%）+考試（50%）,約束條件、目標(biāo)最大/小化、最優(yōu)方案,線性規(guī)劃,整數(shù)規(guī)劃,動態(tài)規(guī)劃,運輸問題,對策論,決策分析,圖與網(wǎng)絡(luò)分析,《運籌學(xué)》教材內(nèi)容,線性規(guī)劃 第一章 1-5節(jié) 運輸問題 第三章 1-4節(jié) 整數(shù)規(guī)劃 第五章 1-5節(jié) 動態(tài)規(guī)劃 第七章 1-4節(jié) 圖與網(wǎng)絡(luò)分析 第八章

2、 1-3節(jié) 對策論 第十二章 1-3節(jié) 決策論 第十三章 1-3節(jié),第一章 線性規(guī)劃及單純形法,主要內(nèi)容,線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃解的概念、圖解法 單純形法原理線性規(guī)劃應(yīng)用,,每個問題都用一組未知變量 表示目標(biāo)函數(shù)和約束條件。有一個目標(biāo)函數(shù)，且可表示為一組未知量 的線性函數(shù)，目標(biāo)函數(shù)可以是求最大也可以求最小。存在一組約束條件，都可以用一組未知量

3、 的線性等式或不等式表示。,,線性規(guī)劃問題的特征,,線性規(guī)劃模型三要素,決策變量 表示某種重要的可變因素，變量的一組數(shù)據(jù)代表一個解決的方案或措施，用x1, x2, ···, xn表示目標(biāo)函數(shù) 決策變量的函數(shù)，目標(biāo)可以是最大化或最小化約束條件 對決策變量取值的限制條件，由決策變量 x1, x2, ···, xn 的不等式組或方程組構(gòu)成,

4、,線性規(guī)劃模型的標(biāo)準(zhǔn)形式,目標(biāo)函數(shù)：,約束條件：,目標(biāo)最大化 約束為等式 決策變量均非負(fù) 右端項非負(fù),a11 x1 + a12 x2 + … + a1n xn = b1a21 x1 + a22 x2 + … + a2n xn = b2 … … am1 x1 + am2 x2 + … + amn xn = bmx1, x2, …, xn ≥ 0其中bi

5、≥0 ，i = 1, 2, …, m,,max z = c1x1 + c2x2 + … + cnxn,,,,,,解的重要概念,,線性規(guī)劃的求解方法——圖解法,圖解法步驟：1、建立直角坐標(biāo)系；2、圖示約束條件，判斷可行域；3、圖示目標(biāo)函數(shù)和尋找最優(yōu)解；,Max Z= x1 + 2 x2 2 x1 + 2 x2 ≤ 8 0 x1 + 2 x2 ≤ 4 x1 , x2 ≥ 0,,

6、,o,x1,,,,,,,,,,1 2 3 4,4321,,2 x1 + 2 x2 = 8,,2 x2 = 4,,,Z=2,,Z=6,最優(yōu)解：x1=2, x2=2最優(yōu)值：Z=6,,圖解法求解的四種情況,,定理1：線性規(guī)劃問題的可行域為凸集。 定理2：凸集的每個頂點對應(yīng)一個基可行解?；尚薪獾膫€數(shù)是有限的，當(dāng)然凸集的頂點個 數(shù)也是有限的。

7、定理3：若線性規(guī)劃有最優(yōu)解，必在可行域某頂點上達(dá)到。 在有限個基可行解中間存在最優(yōu)解。,基本定理,,從一個初始基可行解出發(fā)，通過對基變量的迭代運算（每次迭代更換一個基變量，相當(dāng)于從一個可行極點移動至與其相鄰的另一個可行極點）而得到下一個基可行解，同時使目標(biāo)函數(shù)值得到改善；經(jīng)過有限次的迭代運算，就能得到LP的最優(yōu)解。,,,,,,,,,單純形法的基本原理,最優(yōu)性條件：判斷是否達(dá)到最優(yōu)解的條件，以及確定下一次應(yīng)調(diào)入哪一個非基

8、變量為基變量，可使目標(biāo)函數(shù)值得到改善；可行性條件：確定應(yīng)調(diào)出哪一個基變量（使其成為非基變量）可確保新的基本解仍然是可行解。,,,,,,,，,,,,由于基可行解數(shù)目有限（≤ ），因此，經(jīng)過有限次迭代即可找到最優(yōu)解。前提：線性規(guī)劃為標(biāo)準(zhǔn)型。,,單純形法基本步驟,求初始基可行解確定換入變量的最優(yōu)性條件確定換出變量的可行性條件運用初等行變換求出新的基 可行解,,單純形法求解——I.求初始基可行解,因為，基

9、可行解是由一個可行基決定，所以，構(gòu)造初始基可行解 ，相當(dāng)于確定一個初始可行基,方法：若A中含I， 則 ； 若A中不含I，則用人工變量法（大M法）構(gòu)造一個I。,問題：若 ，則 例1中的,,單純形法求解——II.最優(yōu)性檢驗,把目標(biāo)函數(shù)用非基變量表示：,檢驗數(shù)向量，記為 。當(dāng) 時，當(dāng)前解為最優(yōu)解。,方法：① 計算每個 的檢驗 數(shù)

10、 ②若所有 ，則當(dāng)前解為最優(yōu)解③否則，有 ，則找到最大的 ，其對應(yīng)的 作為換入變量。,,單純形法求解——III.可行性檢驗,因為，基可行解與基相對應(yīng)，所以，尋找新的可行解，即將初始可行基 轉(zhuǎn)化為 ，稱基變換。,基變換的原則,換入變量： 中最大的 所對 應(yīng)的

11、 換入基；,換出變量：由 決定出基變量。,方法：令 令,檢驗比,,單純形法求解——IV.求解新的基可行解,方法： ① 用入基變量 替換基變量中的換出變量 ，得到一個新的基 ；② 對應(yīng)這個基可以找到一個新的基可行解；③ 重復(fù)步

12、驟II和III，直到結(jié)束，求出最優(yōu)解。,旋轉(zhuǎn)變換的實質(zhì)就是用一系列的初等行變換將主元列變?yōu)閱挝涣邢蛄?，其中主元變?yōu)?，主元列的其余元素都為零。,?,,單純形表：基于單純形法的步驟設(shè)計的計算格式，是單純形法的具體實現(xiàn)。單純形表的主要結(jié)構(gòu),單純形法求解——單純形表,𝐵 ?1 𝑏,𝐵 ?1 A,問題：第一張表的 檢驗數(shù)的公式在哪里？,𝐵 ?1 =？,—— 單位

13、矩陣I,𝐵 ?1 𝑃 𝑗,在哪里？,𝐵 ?1 𝐴,中的第j 列,,,例2 用單純形法求解線性規(guī)劃問題,單純形法求解,解：（1）轉(zhuǎn)化為標(biāo)準(zhǔn)型,,,,[ ],主元素,,,,,,,,,大M法：若給定問題標(biāo)準(zhǔn)化后，系數(shù)矩陣中不存在m個線性無關(guān)的單位列向量，則在某些約束的左端加入非負(fù)變量（人工變量），使得變化后的系數(shù)矩陣中恰有m個線性無關(guān)的單位列向量，并

14、且在目標(biāo)函數(shù)中減去這些人工變量與M的乘積（M是相當(dāng)大的一個正數(shù)）。對于變化后的問題，取這m個單位列向量構(gòu)成的單位矩陣為初始基，該基對應(yīng)的解一定是基可行解。,,,,,,,,,單純形法的進(jìn)一步討論——大M法,,第一階段（目的是求解該問題的一個初始基可行解）：在約束中加入人工變量使系數(shù)矩陣出現(xiàn)單位陣，然后目標(biāo)函數(shù)變?yōu)閙axW＝-∑人工變量，如果所得最優(yōu)解中所有的人工變量都為零則得到原問題的一個基可行解（而非最優(yōu)解），否則原問題無可行解。如果第

15、一階段求解結(jié)果最優(yōu)解的目標(biāo)函數(shù)值不為0，也即最優(yōu)解的基變量中含有非零的人工變量，表明原線性規(guī)劃問題無可行解。,第二階段：將第一階段得到的基可行解作為原問題的初始基可行解，以原目標(biāo)函數(shù)為目標(biāo)函數(shù)進(jìn)行計算，然后按照單純形法求解原問題的最優(yōu)解。,單純形法的進(jìn)一步討論——兩階段法,,線性規(guī)劃最優(yōu)解的幾種情況,,教材P35,單純形法小結(jié),作業(yè)p44,1.1 圖解法1.21.31.6 1.71.101.121.131.14

16、  （1）,,基矩陣（基）：設(shè)A是 階系數(shù)矩陣( )，秩A=m，則A中一定存在m個線性無關(guān)的列向量，稱由m個線性無關(guān)的列向量構(gòu)成的可逆矩陣 為問題L的一個基，L最多有 個基。系數(shù)矩陣A中的m階可逆子陣，記為B。其余為非基矩陣，記為N。基向量：基矩陣B中的列，其余為非基向量?；兞浚号c基矩陣B中列向量所對應(yīng)的變量為基

17、變量，記為 ，其余變量為非基變量，記為 。,,,,,,,,,,,,,,1.3——線性規(guī)劃標(biāo)準(zhǔn)型解的概念,,1.3（2）答案,【解】此線性規(guī)劃問題的系數(shù)矩陣A為,令A(yù)=(P1，P2，P3，P4),①∵ P1，P2線性無關(guān)，∴（P1, P2）為基. x1 , x2為基變量，令非基變量x3 ,

18、x4為0， 得 x1 = -1/3，x2=11/3 則基解為（-1/3 , 11/3 , 0 , 0），非可行解。,②∵ P1，P3線性無關(guān)，∴（P1, P3）為基. x1 , x3為基變量，令非基變量x2 , x4為0， 得 x1 = 5/2，x3=11/5 則基解為（5/2 , 0 , 11/5 , 0），可行解。 （5/2 , 0 , 11/5 , 0）為基可行解，z2=43/5,

19、③……④……⑤……⑥……,最優(yōu)解為（5/2 , 0 , 11/5 , 0），最優(yōu)值為43/5。,,1.6（1）答案,【解】大M法,,化為標(biāo)準(zhǔn)型，并加入人工變量得,,[ ],[ ],由此可得，最優(yōu)解X*=(45/7，4/7，0，0，0，0), Z*=102/7， 具有唯一解。,1.6（1）答案,【解】兩階段法,,第一階段的數(shù)學(xué)模型,,[ ],[ ],由此可得，第一階段最優(yōu)解X*=(45/7，4/7，0，

20、0，0，0), 原線性規(guī)劃的基可行解。,原線性規(guī)劃的最優(yōu)解X*=(45/7，4/7，0，0，0), Z*=102/7， 具有唯一解。,1.6（1）答案,,第二階段的目標(biāo)函數(shù),1.12答案,,【解】（1）,為>0的常數(shù)，則 𝜎 𝑗 正負(fù)不變，最優(yōu)解X*= (B-1b, 0)T不變。,（2）,正負(fù)無法判斷，因此最優(yōu)解可能發(fā)生變化。,（3）,1.12答案,,【解】（1）,為>0的常數(shù)，則 

21、0590; 𝑗 正負(fù)不變，最優(yōu)解X*= (B-1b, 0)T不變。,（2）,正負(fù)無法判斷，因此最優(yōu)解可能發(fā)生變化。,（3）,1.14（1）,,教材P122 例1,第二章 運輸問題,主要內(nèi)容,運輸問題模型特征表上作業(yè)法其它運輸問題建模,,運輸問題的數(shù)學(xué)模型,針對單一品種物資運輸調(diào)度問題設(shè)某物資有m個產(chǎn)地A1，A2，…，Am，產(chǎn)量分別是a1，a2，… ，am ， 有n個銷地B1，B2，

22、…，Bn ，銷量分別是b1，b2，… ，bn。從產(chǎn)地Ai (i=1,2, …,m)到銷地Bj (j=1,2, …,n )運輸單位物品的運價是cij 。如何調(diào)運這些物資使得總費用最??？,,運輸問題的數(shù)學(xué)模型,目標(biāo)函數(shù),約束條件,（1）產(chǎn)銷平衡運輸問題,（2）產(chǎn)過于求運輸問題,（3）產(chǎn)不應(yīng)求運輸問題,約束條件的系數(shù)矩陣,產(chǎn)銷平衡運輸問題的數(shù)學(xué)模型特征,元素為0或1；列向量有兩個非0元素，一個變量在前m個方程中出現(xiàn)一次，一個在后n個方程中

23、出現(xiàn)一次矩陣的秩=m+n-1,產(chǎn)銷平衡運輸問題解法——表上作業(yè)法,不需要寫出上述模型，直接在運輸表中進(jìn)行計算,,1、確定初始基可行解 （1）最小元素法：優(yōu)先考慮單位運價最小（或運距最短）的運輸，最大限度滿足其運輸量，然后次小，直至給出初始調(diào)運方案。 找出運輸表中最小元素cij，優(yōu)先賦值對應(yīng)的xij=min{ai,bj}。 若xij=ai，則第 i 個產(chǎn)地全部運出，劃掉運價表中的第i行； 若xi

24、j=bj，則第 j 個銷地全部滿足，劃掉運價表中的第j列；在剩下的運輸表中，取最小運價對應(yīng)的變量賦值并滿足約束，依次下去，直到最后一個，即可得初始基可行解。,產(chǎn)銷平衡運輸問題解法——表上作業(yè)法,,例1 某部門有3個生產(chǎn)同類產(chǎn)品的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由4個銷售點（銷地）出售，各工廠的生產(chǎn)量、各銷售點的銷售量（假定單位均為t），以及各工廠到各銷售點的單位運價（元/t）見下表。請問產(chǎn)品如何調(diào)運才能使費用最?。?產(chǎn)銷平衡運輸問題解法—

25、—表上作業(yè)法,產(chǎn)地,銷地,4,12,11,4,2,10,9,3,8,5,6,11,,產(chǎn)地,銷地,4,12,11,4,2,10,9,3,8,5,6,11,產(chǎn)銷平衡運輸問題解法——表上作業(yè)法,8,2,10,14,8,6,初始基可行解：x13=10, x14=6, x21=8, x23=2, x32=14, x34=8,其余均為0。z=246滿足所有約束條件，非0變量的個數(shù)為 6 = 3+4-1,,1、確定初始基可行解 最

26、小元素法只考慮局部費用最小，可能為節(jié)省一處運費，而增加它處運費，導(dǎo)致總費用非最小。 （2）沃格爾（Vogel）法：考慮產(chǎn)地到銷地的最小運價和次小運價之間的差額，如果差額很大，就選最小運價先調(diào)運，否則會增加總運費。計算各行各列的罰數(shù)，罰數(shù)=次小費用-最小費用找出最大的罰數(shù)行或列所對應(yīng)的最小費用優(yōu)先安排重復(fù)計算步驟①和②,產(chǎn)銷平衡運輸問題解法——表上作業(yè)法,,,,,,,產(chǎn)地,銷地,4,12,11,4,2,10,9,3,8,5,

27、6,11,產(chǎn)銷平衡運輸問題解法——表上作業(yè)法,0,1,1,5,1,3,2,14,0,1,2,1,3,2,8,0,1,2,1,2,8,7,6,1,2,12,0,0,2,2,4,初始基可行解：x13=12, x14=4, x21=8, x24=2, x32=14, x34=8,其余均為0。z=244,當(dāng)最小元素或最大罰數(shù)對應(yīng)的ai和bj相等時，即對應(yīng)的產(chǎn)量和銷量相等時，為保證基變量的個數(shù)為m+n-1個，除了在產(chǎn)銷平衡表填xij=ai外，還應(yīng)

28、在產(chǎn)銷平衡表中的第i行或第j列某空格（相應(yīng)運價未被劃掉）處填一個“0”，然后同時劃去運價表上的第i行和第j列，該“0”看作是數(shù)字格。,產(chǎn)銷平衡運輸問題解法——表上作業(yè)法,1、確定初始基可行解,,2、最優(yōu)性檢驗 檢驗數(shù)：對于空格xij，假定給它一個單位運量，調(diào)整其它有關(guān)數(shù)字格運量，使產(chǎn)銷平衡，則這一系列變化導(dǎo)致的總運費變化值稱為該空格的檢驗數(shù)，記為 。 最優(yōu)方案的判別準(zhǔn)則：如果一個可行方案的所有空

29、格的檢驗數(shù)都大于等于零，則該方案是最優(yōu)方案。,產(chǎn)銷平衡運輸問題解法——表上作業(yè)法,,2、最優(yōu)性檢驗 （1）閉回路法 ①尋找非基變量的閉回路。以空格（非基變量xij）為起點，沿水平或垂直方向前進(jìn)，碰到基變量數(shù)字格后轉(zhuǎn)90°，繼續(xù)前進(jìn)直至回到起始空格為止。 ②非基變量的計算檢驗數(shù)。假定給空格（非基變量xij ）一個單位運量，調(diào)整該閉回路上所有數(shù)字格的運量，使產(chǎn)銷平

30、衡，則閉回路上總運費的變化值就等于 。,產(chǎn)銷平衡運輸問題解法——表上作業(yè)法,,,產(chǎn)地,銷地,4,12,11,4,2,10,9,3,8,5,6,11,產(chǎn)銷平衡運輸問題解法——表上作業(yè)法,2、最優(yōu)性檢驗 （1）閉回路法 缺點：當(dāng)變量個數(shù)較多時，尋找閉回路以及計算檢驗數(shù)的計算 量較大。,產(chǎn)銷平衡運輸問題解法——表上作業(yè)法,,2、最優(yōu)性檢驗

31、 （2）位勢法（對偶變量法） ① 在運輸表中增加位勢行ui和位勢列vj ② 計算行位勢和列位勢 ③ 由公式 ，計算非基變量（空格）的檢驗數(shù),產(chǎn)銷平衡運輸問題解法——表上作業(yè)法,,產(chǎn)地,銷地,4,12,11,4,2,10,9,3,8,5,6,11,產(chǎn)銷平衡運輸問題解法——表上作業(yè)法,設(shè),,,2

32、 1 -110 12,3、解的改進(jìn) 在運輸表中，找出檢驗數(shù)為負(fù)的空格（非基變量xij）對應(yīng)的閉回路 Lij，在滿足所有約束的前提下，盡可能增大xij，并相應(yīng)調(diào)整此閉回路上其它數(shù)字

33、格的運輸量，得到另一個更好的基可行解。 ① 以xij為換入變量，找出它在運輸表中的閉回路 ② 以空格（Ai, Bj）為第一個頂點，沿閉回路的順（或逆）時針方向前進(jìn)，對數(shù)字格依次編號 ③ 在閉回路所有偶數(shù)數(shù)字格中，找出運輸量最小的數(shù)字格，作為換出變量 ④ 以偶數(shù)數(shù)字格最小運輸量為調(diào)整量，將該閉回路中所有奇數(shù)格都增加這一數(shù)值，所有偶數(shù)格都減少這一數(shù)值，從而得出新的運輸方

34、案 重復(fù)第2步最優(yōu)性檢驗和第3步解的改進(jìn)，直至得到最優(yōu)解。,供銷平衡運輸問題解法——表上作業(yè)法,,產(chǎn)地,銷地,4,12,11,4,2,10,9,3,8,5,6,11,產(chǎn)銷平衡運輸問題解法——表上作業(yè)法,2 1

35、-110 12,,①,②,③,④,偶數(shù)數(shù)字格的最小值,故，做出調(diào)整,得到新的基可行解,若運輸問題的某一基可行解有多個非基變量的檢驗數(shù)為負(fù)，選擇 中最小的那個作為換入變量。當(dāng)?shù)竭\輸問題的最優(yōu)解時，若有某非基變量的檢驗數(shù)為0，則該運輸問題有多重最優(yōu)解。當(dāng)某部分產(chǎn)地

36、的產(chǎn)量和，與某部分銷地的銷量和相等時，在迭代過程中可能在某一格填入一個運量時，需同時劃去運輸表中的一行和一列，則出現(xiàn)退化。為了使表上作業(yè)法順利迭代，應(yīng)在同時劃去行或列中的某格填入數(shù)字0，表示該格為基變量，且取值為0，以保證基變量個數(shù)始終為m+n-1個。,產(chǎn)銷平衡運輸問題解法——表上作業(yè)法,,產(chǎn)大于銷 總產(chǎn)量大于總銷量，則多余物資無處運輸，需要考慮多余物資在哪些產(chǎn)地就地存儲的問題。將該地的倉庫設(shè)成一個假想的銷地Bn

37、+1，該銷地總需求量:,產(chǎn)銷不平衡的運輸問題,,產(chǎn)大于銷 若某產(chǎn)地 i 允許物資就地存儲，則ci,n+1=0 。因為物資就地存儲不存在運輸費用問題，運輸單價應(yīng)該是“0”。 若某產(chǎn)地 i 不允許物資就地存儲，則ci,n+1=M 。M 是一個相當(dāng)大的正數(shù)。這樣對于產(chǎn)地i，如果物資就地存儲就付出相當(dāng)大的代價，使得在求解時不得不將產(chǎn)地 I 的物資都運出去。 在最優(yōu)解中，產(chǎn)地Ai

38、到虛擬銷地Bj的運量，就是產(chǎn)地Ai就地存儲的多余物資的數(shù)量。,產(chǎn)銷不平衡的運輸問題,,產(chǎn)小于銷 總銷量大于總產(chǎn)量，則某銷地缺貨，需要考慮確定哪些銷地缺貨多少的問題。設(shè)虛擬產(chǎn)地Am+1，總產(chǎn)量為,產(chǎn)銷不平衡的運輸問題,,產(chǎn)小于銷 若某銷地 j 允許缺貨，則cm+1,j=0，結(jié)果會出現(xiàn)從虛擬產(chǎn)地Am+1向銷地Bj運送貨物，實際上這部分運量不可能存在，是最后分配方案中Bj的缺貨量。由于這個產(chǎn)地不存

39、在，當(dāng)然運價為0。 若某銷地 j 不允許缺貨，則cm+1,j=M，M 是一個相當(dāng)大的正數(shù)。意味著不可能從虛擬產(chǎn)地Am+1向銷地Bj運送貨物，則銷地Bj的銷量bj需要完全從產(chǎn)地A1～Am運來，保證銷地j不缺貨。 在最優(yōu)解中，虛設(shè)產(chǎn)地Am+1到銷地Bj的運量實際上就是最后分配方案中Bj的缺貨量。,P96 例4,產(chǎn)銷不平衡的運輸問題,,作業(yè)p103,3.13.23.73.93.11,,3.1,

40、p82,,3.9,,【解】總產(chǎn)量大于總銷量，增加虛擬食品廠4，需求量=10， 并考慮單位利潤，得到產(chǎn)銷平衡運輸表,3.11,,【解】總需求量=320+250+350=920 > 總供應(yīng)量=400+450=850, 缺少70，增加虛擬電站，能力為70。 將城市1和3的需求量分為兩部分，第一部分為必須供應(yīng)，第二部分為可變供應(yīng)。則得到產(chǎn)銷平衡的運輸表如下,第三章 整數(shù)規(guī)劃,主要內(nèi)容,整數(shù)規(guī)劃數(shù)學(xué)模型分枝定界法 割平面法

41、 0－1規(guī)劃指派問題,,整數(shù)規(guī)劃數(shù)學(xué)模型,部分或全部決策變量是整數(shù)的規(guī)劃，稱為整數(shù)規(guī)劃。若模型是線性的，稱為整數(shù)線性規(guī)劃。本章只討論整數(shù)線性規(guī)劃。,純整數(shù)規(guī)劃：全部決策變量取整數(shù)值，又稱全整數(shù)規(guī)劃；混合整數(shù)規(guī)劃：部分決策變量取整數(shù)值；0-1規(guī)劃：決策變量只能取0或1。,,,,割平面法,純整數(shù)線性規(guī)劃 松弛問題,,設(shè)aij(i=1,2,…m; j=1,2,…，n

42、)和bi (i=1,2,…m)皆為整數(shù)，若不為整數(shù)，可以乘上一個倍數(shù)化的整數(shù)。,,,（3.1a）,（3.1b）,（3.1c）,（3.1d）,（3.1a）,（3.1b）,（3.1c）,,割平面法從X*的非整數(shù)分量中選取一個，用以構(gòu)造一個線性約束條件，將其加入原松弛問題，形成一個新的線性規(guī)劃，再求解。若新的線性規(guī)劃最優(yōu)解滿足整數(shù)要求，即為純整數(shù)規(guī)劃的最優(yōu)解，否則，重復(fù)上述步驟，直到獲得整數(shù)最優(yōu)解為止。新加約束條件基本性質(zhì)已獲得的不符

43、合整數(shù)要求的線性規(guī)劃最優(yōu)解不滿足該線性約束條件，以使原來的非整數(shù)最優(yōu)解不再出現(xiàn)。凡整數(shù)可行解均滿足該線性約束條件，以使整數(shù)最優(yōu)解始終被保留在每次形成的線性規(guī)劃可行域中。,割平面法,,,,,,,,,,,原松弛問題的最優(yōu)解不可行,整數(shù)規(guī)劃的整數(shù)可行解可行,最大整數(shù)與非負(fù)真分?jǐn)?shù)之和,,割平面法,,割平面法計算步驟（1）運用單純形法求松弛問題的最優(yōu)單純形表（2）針對非整數(shù)變量，增加新的約束條件（3）運用對偶單純形法求解加入新約束條件后的

44、單純形表（4）重復(fù)步驟（2）、（3），直至得到整數(shù)解,分枝定界法,求整數(shù)規(guī)劃的松弛問題最優(yōu)解；若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解，否則轉(zhuǎn)下一步；任意選一個非整數(shù)解的變量xi，在松弛問題中加上約束xi≤[xi]及xi≥[xi]+1組成兩個新的松弛問題，稱為分枝。新的松弛問題具有特征：當(dāng)原問題是求最大值時，目標(biāo)值是分枝問題的上界；當(dāng)原問題是求最小值時，目標(biāo)值是分枝問題的下界；檢查所有分枝的解及目標(biāo)函數(shù)值，若某分枝的

45、解是整數(shù)并且目標(biāo)函數(shù)值大于（max）等于其它分枝的目標(biāo)值，則將其它分枝剪去不再計算，若還存在非整數(shù)解并且目標(biāo)值大于（max）整數(shù)解的目標(biāo)值，需要繼續(xù)分枝，再檢查，直到得到最優(yōu)解。,,求解0-1規(guī)劃的隱枚舉法,找出任意一可行解，目標(biāo)函數(shù)值為Z0； 原問題求最大值時，則增加一個約束 當(dāng)原問題求最小值時，上式改為小于等于約束；列出所有可能解，對每個可能解先檢驗式（*），若滿足再檢驗其它約束，若不滿足式（*），則認(rèn)為不可行，

46、若所有約束都滿足，則認(rèn)為此解是可行解，求出目標(biāo)值；目標(biāo)函數(shù)值最大（最?。┑慕饩褪亲顑?yōu)解。,(*),,指派問題,指派問題的標(biāo)準(zhǔn)形式：有n個人和n件事，已知第i個人做第j件事的費用為cij(i,j=1,2,…,n)，要求確定人和事之間的一一對應(yīng)的指派方案，使完成這n件事的總費用最小。引入n2個0-1變量： 數(shù)學(xué)模型,指派第i個人做第j件事,不指派第i個人做第j件事,(i,j=1,2,…,n),,(i,j=1,2,…,n),(j=1,

47、2,…,n),(i=1,2,…,n),,【解】最優(yōu)分配方案是安排四人工作，使完成工作總時間最少，最小值問題。,第一步：找出效率矩陣每行最小元素，每行分別減去其最小元素,Min 3 4 0 8,第二步：找出效率矩陣每列最小元素，每列分別減去其最小元素,,,,Min,,指派問題,,第三步：用最少的直線覆蓋所有“0”，得,,,,第四步：這里直線數(shù)等于3（等于4時停止運算），要進(jìn)行下一輪計算。,（1）從矩陣

48、未被直線覆蓋的數(shù)字中找出一個最小的數(shù)k，表中k＝3。,（2）直線相交處的元素加上k，未被直線覆蓋的元素減去k，被直線覆蓋而沒有相交的元素不變，得到下列矩陣,,指派問題,,回到第三步:用最少的直線覆蓋所有“ 0”，得,,,,未被直線覆蓋元素中最小元素k=2,直線相交處的元素加上2，未被直線覆蓋的元素減去2，被直線覆蓋而沒有相交的元素不變，得到下列矩陣,指派問題,,畫線，,,,,,最少直線數(shù)等于4。,第五步：最優(yōu)分配,,,,,最優(yōu)解：,最

49、優(yōu)值Z＝73＋87＋82＋88 ＝330,×,×,×,指派問題,,作業(yè)p146,5.15.25.35.45.5 5.9,,第四章 動態(tài)規(guī)劃,主要內(nèi)容,多階段決策過程動態(tài)規(guī)劃基本概念動態(tài)規(guī)劃基本思想動態(tài)規(guī)劃求解方法動態(tài)規(guī)劃應(yīng)用,一般的動態(tài)規(guī)劃基本方程可表示為,動態(tài)規(guī)劃的基本方程,,( 4.2a ),( 4.2b ),最優(yōu)化原理：一個過程的最優(yōu)策略具有這樣的性質(zhì)，無論初始狀態(tài)及初始決

50、策如何，對于先前決策所形成的狀態(tài)而言，以后的決策應(yīng)構(gòu)成最優(yōu)策略。,,模型建立步驟確定過程的分段，構(gòu)造狀態(tài)變量；設(shè)置決策變量，寫出狀態(tài)轉(zhuǎn)移；列出階段指標(biāo)和指標(biāo)函數(shù)；寫出基本方程，由此逐段遞推求解。,動態(tài)規(guī)劃模型建立,關(guān)鍵：識別問題的多階段特征，將其分 解為可用遞推關(guān)系聯(lián)系起來的若 干子問題難點：狀態(tài)變量的選擇 可知性：過程演變的各階段狀態(tài)變量的取值，能直接或間接確定 無

51、后效性重點：明確指標(biāo)函數(shù)，得出基本方程 （狀態(tài)轉(zhuǎn)移方程）,,動態(tài)規(guī)劃解法比較,,,作業(yè)p221,7.17.2,,第五章 圖論與網(wǎng)絡(luò)分析,圖的基本概念 最小支撐樹問題 最短路徑問題,主要內(nèi)容,,定義1：由點和邊組成，記作G=(V，E)，其中 V={v1，v2，……，vn}為結(jié)點的集合， E={e1，e2，……，em}為邊的集合。,點表示研究對象,邊表示表示研究對

52、象之間的特定關(guān)系,1. 圖,圖的基本概念,注意：上面定義的圖Ｇ區(qū)別于幾何學(xué)中的圖。幾何學(xué)中，圖中點的位置、線的長度和斜率等都十分重要，而這里只關(guān)心圖中有多少點以及哪些點之間有線相連。,V、E為有限集合，則為有限圖，反之無限圖。,,問題：求網(wǎng)絡(luò)的支撐樹，使其權(quán)和最小。,3、最小支撐樹問題,算法1（避圈法）：把邊按權(quán)從小到大依次添入圖中，若出現(xiàn)圈，則刪去其中最大邊，直至填滿n-1條邊為止（n為結(jié)點數(shù)） 。,【例】 求上例中的最小支撐樹,

53、【解】,4,,最小支撐樹問題,,算法2（破圈法）：在圖中找圈，并刪除其中權(quán)數(shù)最大的邊。如此進(jìn)行下去，直至圖中不存在圈。,3、最小支撐樹問題,最小支撐樹問題,,5,5.5,,,,,,v2,v3,v4,v5,3.5,4,2,3,算法2（破圈法）：在圖中找圈，并刪除其中權(quán)數(shù)最大的邊。如此進(jìn)行下去，直至圖中不存在圈。,3、最小支撐樹問題,最小支撐樹問題,,5,,,,,,v1,v2,v3,v4,v5,3.5,4,2,3,算法2（破圈法）：在圖中找

54、圈，并刪除其中權(quán)數(shù)最大的邊。如此進(jìn)行下去，直至圖中不存在圈。,3、最小支撐樹問題,最小支撐樹問題,,5,,,,,,v1,v2,v3,v4,v5,3.5,2,3,算法2（破圈法）：在圖中找圈，并刪除其中權(quán)數(shù)最大的邊。如此進(jìn)行下去，直至圖中不存在圈。,3、最小支撐樹問題,最小支撐樹問題,,解法1：Dijkstra（狄克斯拉）標(biāo)號法,基本思想：從起點vs開始，逐步給每個結(jié)點vj標(biāo)號[dj，vi]，其中dj為起點vs到vj的最短距離，vi為該最

55、短路線上的前一節(jié)點。,,最短路問題,,[0, v1],[1, v1],(1) 給起點v1標(biāo)號[0, v1],(3) 考慮所有這樣的邊[vi , vj]，其中vi∈VA， vj∈VB，挑選其中與起點v1距離最短（min{di+cij}）的vj，對vj進(jìn)行標(biāo)號,(4) 重復(fù)(2)、(3)，直至終點vn標(biāo)上號[dn, vi]，則dn即為v1→ vn的最短距離，反向追蹤可求出最短路。,步驟：,,[0, v1],[1, v1],[3, v1],

56、,[0, v1],[1, v1],[3, v1],[5, v3],,[0, v1],[1, v1],[3, v1],[5, v3],[6, v2],,[0, v1],[1, v1],[3, v1],[5, v3],[6, v2],[9, v5],,,[0, v1],[1, v1],[3, v1],[5, v3],[6, v2],[9, v5],[10, v5],,,[0, v1],[1, v1],[3, v1],[5, v3],[6,

57、v2],[9, v5],[10, v5],[12, v5],此時終點v9已標(biāo)號[12, v5]，則12即為v1→ vn的最短距離，反向追蹤可求出最短路,[0, v1],[1, v1],[3, v1],[5, v3],[6, v2],[9, v5],[10, v5],[12, v5],v1到v9的最短路為：v1→ v3→ v2→ v5→ v9，最短距離為12,解法2：Floyd（弗洛伊德）算法,基本思想：從圖的權(quán)矩陣D=(dij)n

58、15;n開始，遞歸地進(jìn)行n次更新，即由矩陣D(0)=D，按一個公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；……；最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j(luò)號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點矩陣path來記錄兩點間的最短路徑。,,最短路問題,解法2：Floyd（弗洛伊德）算法,步驟：（1）輸入權(quán)重矩陣D(0)=D（2）計算D

59、(k) = (dij(k) )n×n (k=1,2,…,n) 其中，dij(k)=min[dij(k-1) ，dik(k-1) + dkj(k-1)]（3）D(n) = (dij(n) )n×n中元素dij(n) 就是vi到vj的最短路長。,,最短路問題,【例】求圖G中任意兩點的最短路,【解】圖G的權(quán)矩陣,表示從vi點到vj點或直接有邊，或經(jīng)v1為中間點時的最短路長,……,,最短路問題,表示從v

60、i點到vj點或直接有邊，或最多經(jīng)v1 v2為中間點時的最短路長,,,,,,,,,,,,,,,,,,,,,,,,,,最短路問題,作業(yè)p256,8.18.6,,第六章 對策論,主要內(nèi)容,對策/博弈論概念及要素三個重要結(jié)論矩陣對策構(gòu)建和求解方法,,基本概念,對策論又稱博弈論，研究沖突對抗條件下最優(yōu)決策問題的理論。策略形勢：不完全競爭條件下的對抗行為，各方收益由自身行為和其他方行為共同決定。,基本要素局中人（I ）：有權(quán)決定自己行動方

61、案的對策參加者，理性人策略集（S ）：供局中人選擇的實際可行完整行動方案的集合， 一局對策中，各局中人選定策略的集合，稱局勢贏得函數(shù)（ H(s) ）:對于任一局勢，局中人的贏得值。支付函數(shù),,嚴(yán)格占優(yōu)策略/嚴(yán)格劣勢策略上策均衡/納什均衡,典型案例和重要結(jié)論,結(jié)論1：不要選擇嚴(yán)格劣勢策略。結(jié)論2：個人理性選擇導(dǎo)致非最優(yōu)。結(jié)論3：學(xué)會換位思考。,,,囚徒困境 智豬博弈,求解方法：刪除嚴(yán)格劣勢策略

62、,,矩陣對策的策略,純策略：確定的選擇某策略 混合策略：以某一概率分布選擇各策略。,,矩陣對策的純策略,矩陣對策的一般表達(dá),,矩陣對策的純策略,理智行為：從各自最不利情形中選擇最有利 I：最大最小原則 II：最小最大原則,平衡局勢：雙方均可接受，且對雙方都是最穩(wěn)妥的結(jié)果。 （α2 ，β2），局中人I和II的最優(yōu)純策略。,,

63、矩陣對策的最優(yōu)純策略,1231,3 7 4 6,,矩陣對策的純策略,,34,5 6,無鞍點,矩陣對策的混合策略,,1、混合策略,矩陣對策的混合策略,,2、混合局勢,3、贏得期望,4、混合策略對策模型,矩陣對策的混合策略,,5、最優(yōu)混合策略,矩陣對策的混合策略,,定理2：矩陣對策G在混合策略意義下有解的充要條件是：存在 ，使得對于任意

64、 ，有,例：求解矩陣對策G= ,其中,解：（1）不存在鞍點，為混合策略求解問題。 （2）圖解法求解設(shè)局中人I的混合策略為（x, 1-x）T， 。,0,1,I,I,II,II,① 數(shù)軸上坐標(biāo)為0和1的兩點分別做兩條垂線I-I和II-II。,② 畫出局中人II的不同策略下局中人I的贏得線段。,2,5,7,2,3,11,β1=2x+7(1-x),β2=3x+5(1-x),β3=

65、11x+2(1-x),圖解法,僅適用于贏得矩陣為2×n或m×2階的矩陣對策問題。,β1: v11 = 2x+7(1-x)β2 : v12 = 3x+5(1-x)β3 : v13 = 11x+2(1-x),③由于局中人II理性，局中人I從最少可能收入中選擇最大的一個，為局中人I的最優(yōu)對策。B2,④ 求解方程組可得最優(yōu)混合策略和矩陣對策的值。,0,1,I,I,II,II,2,5,7,2,3,11,β1=2x+7(1-

66、x),β2=3x+5(1-x),β3=11x+2(1-x),B1,B2,B3,B4,聯(lián)立過B2點兩條直線的方程組為,可解得,則，局中人I 的最優(yōu)策略為,由圖可見局中人II的混合策略只有β2和β3組成。,圖解法,設(shè)局中人II的最優(yōu)混合策略為 ，且,⑤ 求局中人II的最優(yōu)混合策略。,同理，可得局中人II的贏得，,α1: v21 = 3y2+11y3α2 : v22 = 5y2+2y3,

67、畫出贏得線段，見右圖,局中人I理性，局中人II取最大損失的最小值,聯(lián)立方程組可得,解得,圖解法,方程組法,定理：設(shè) ，則 為G的解的充要條件是： 存在數(shù)v，使得x*,y*分別是下列不等式組的解，且v = VG。,若xi*,yj*均不為0，則上述不等式的求解即可轉(zhuǎn)化為下列兩個方程組的求解問題。,注：若上述兩個方程組存在非負(fù)解x*,y* ，即矩陣對策的解。若不存在非負(fù)解，

68、則將上述方程組中的某些等式轉(zhuǎn)化為不等式，繼續(xù)求解。 由于事先假設(shè)xi*,yj*均不為0，故，當(dāng)最優(yōu)策略的某些分量為0時，方程組可能無解，因此該方法具有一定的局限性。,方程組法,例：求解矩陣對策G= ,其中A為,解：（1）刪除劣勢策略，得到,無鞍點,和,（2）構(gòu)造方程組,線性規(guī)劃法,注：適用于所有aij＞0 若存在aij＜0，可取一充分大的M＞0，使得M+aij＞0,線性規(guī)

69、劃法,例：兩人“石頭、剪刀、布”矩陣對策求解解：,(X*，Y*)為矩陣對策的解,12.212.312.412.512.612.7（不考）,作業(yè)p386,,第七章 決策分析,決策分析概述 不確定型決策分析 風(fēng)險型決策分析,主要內(nèi)容,,決策分析概述,,,【例】某公司管理層需要決策是否生產(chǎn)一種新產(chǎn)品。可以確定的是，該產(chǎn)品上市后一定供不應(yīng)求。經(jīng)數(shù)據(jù)分析，該產(chǎn)品的預(yù)期單價為900元，單件可變成本400元，生產(chǎn)所需固定成本為500