1、人之為學有難易乎? 學之,則難者亦易矣;不學,則易者亦難矣！,選擇你所喜歡的，喜歡你所選擇的！,第 2 章 線性規(guī)劃與單純形法,基可行解的結構：非零元素的個數(shù)不超過約束矩陣的秩（行數(shù)）,1、各種解的定義（基解、基可行解、最優(yōu)解）,2、單純形法（以最大化目標函數(shù)為例，）(見靈敏度分析例題), 掌握單純表上各個元素的含義(課后題 9題) 檢驗數(shù)的計算； 換入變量的確定：檢驗數(shù)大于零的變量作為換入變量都可以使目標值增加（選最大的，目標增加的最快 ）,換出變量的確定 掌握線性規(guī)劃各種解的判別條件（唯一解、無窮多解、無界解，退化解）（以練習2.10為例說明） B- 的確定 （在靈敏度分析時也要用到）,第

2、 3 章 對偶理論和靈敏度分析,1、線性規(guī)劃對偶性質及應用, 利用對偶性質求線性規(guī)劃的解，（分兩步） 要正確的寫出線性規(guī)劃的對偶規(guī)劃（以對稱形式為基準） 利用互補松弛條件求出線性規(guī)劃的解（例3.7 ，練習2.2,2.3） 原始問題與對偶問題解之間的關系,2、靈敏度分析（與單純形方法、對偶單純形方法接在一起）() (1) bi 的變化: 給出 bi 的變化范圍，使最優(yōu)基不 變 ： B-b0 若最優(yōu)基變了（至少有一個bi0），要用對偶單純形方法求出新的最優(yōu)解,給出 Cj 的變化范圍，使最優(yōu)解不變 -所有檢驗數(shù)不大于零 若最優(yōu)解變了（至少有一個檢驗數(shù)大于零）， 要用單純形方法求出新的最優(yōu)解,(2)

3、Cj 的變化,補充例題：,已知線性規(guī)劃 的最終單純形表格為：,確定x2的系數(shù)c2的變化范圍，使原最優(yōu)解保持最優(yōu)； -2c20 若c2=-4，求新的最優(yōu)計劃。X*=(10,0,0), Z*=20 b3在什么范圍內變化，最優(yōu)基不變？10b325 b3=30時，新的最優(yōu)方案是什么？ X*=(17.5,7.5,0), Z*=27.5,1 寫出下列線性規(guī)劃問題的對偶問題,解：假設對應三個約束的對偶變量分別為y1, y2, y3,寫出對偶問題如下：,解：假設對應三個約束的對偶變量分別為y1, y2, y3,寫出對偶問題如下：,解：假設對應三個約束的對偶變量分別為y1, y2, y3,寫出對偶問題如下：,2

4、 已知線性規(guī)劃問題,其對偶問題的最優(yōu)解為y*1=1.2, y*2=0.2,由對偶理論直接求出原問題的最優(yōu)解。,分析：類似于例3.7利用對偶理論的互補松弛定理求解,解：寫出對偶問題,將 y*1=1.2, y*2=0.2帶入約束條件，得到(3)(4)為嚴格不等式，由互補松弛性可得x*1=x*2=0, 因為y*1， y*2 0, 原問題的兩個約束為等式約束，所以有,求解后得到 x*3= x*4 =4，所以原問題的最優(yōu)解為X*=(0,0,4,4),6(1) 用對偶單純形發(fā)解線性規(guī)劃,解：把線性規(guī)劃轉化為下面的形式,取y4, y5為基變量，得對偶單純形表（1）,表（1）,此時基本解為Y=(0,0,0,-

5、2,-1),不可行，所以轉第二步。因為Min-2,-1=-2, 所以y4為換出變量；又因為min-24/-6, -5/-1=4, 所以y2為換入變量，得到新的單純形表（2）,表（2）,此時基本解為Y=(0,1/3,0,0,-1/3),不可行，所以轉第二步。因為-1/30,所以y5為換出變量；又因為min-15/-5, -1/(-2/3),-4/(-1/3)=3/2, 所以y3為換入變量，得到新的單純形表（3）,表（3）,此時基本解為Y=(0,1/4,1/2,0,0)是可行的，所以滿足最優(yōu)檢驗下的基本可行解，因而是最優(yōu)解。,4 利用三種資源生產兩種產品的最優(yōu)計劃問題歸結為下列線性規(guī)劃,已知最優(yōu)表

6、是2.32。最優(yōu)計劃是兩種產品分別生產35單位和10單位，最大產值Z*=215單位。（1）確定 x2 的系數(shù) c2 的變化范圍，使原最優(yōu)解保持最優(yōu)；（2）若 c2=6，求新的最優(yōu)解。,表（2.32）,解（1）x2為基變量，則當,Maxj/a2j a2j0 c2 Minj/a2ja2j0,最優(yōu)解保持不變。即 -3/2 c2 -1/(-1)=1,（2）若c2=6,單純形表若下,由于x4的檢驗數(shù)大于0，所以當前的基可行解X=(35,10,25,0,0)不是最優(yōu)解。 x4 應為換入變量，計算,所以對應的x3為換出變量，得到新的單純形表如下,此時基本解為X=(45/2,45/2,0,25/2,0) ，由

7、于所有檢驗數(shù)均小于或等于0，因而此解是最優(yōu)解。即新的最優(yōu)計劃是兩種產品分別生產45/2單位與45/2單位，最大產值Z*=405/2.,5 題4 的線性規(guī)劃作如下分析：（1）b 3 在什么范圍內變化，原最優(yōu)基不變？（2）若b3 =55，求出新的最優(yōu)解。,解（1）,要使得原最優(yōu)基不變，則 b3 的變化范圍為,（2）若b3=55, 即,將其反映到最終單純形表中得到下面的表(1),表(1),因表(1)中原問題為非可行解，故用對偶單純形法繼續(xù)計算。,因為-250，所以x3為換出變量，又因為-3/-5=3/5， 所以x5為換入變量，得到新的單純性表(2),表(2),得到基本解 X=(30,20,0,0,5

8、) 是可行解，所有檢驗數(shù)都小于和等于0， 所以新的最優(yōu)解為 x1=30, x2=20。,第四章 運輸問題,1、運輸問題是特殊的線性規(guī)劃：mn個變量，m+n個約束，獨立約束為m+n-1個， 與一般線性規(guī)劃的區(qū)別：一定有最優(yōu)解（唯一或無窮多解）,2、表上作業(yè)法（實質上是單純形法） 找出初始基可行解（最小元素法、伏格爾方法） 計算非基變量的檢驗數(shù)（閉回路方法、位勢法對偶變量法） 解的調整（閉回路方法）（注：運輸問題是最小化問題，最優(yōu)解的判別是所有檢驗數(shù)都大于等于零時得最優(yōu)解）,以往年考題為例,假設有兩個生產地 A1,A2, A3 和四個銷售地 B1, B2,B3,B4有關數(shù)據(jù)如圖所示如下圖所示，,寫

9、出運輸問題的數(shù)學模型； 用最小元素法找出初始基本可行解; 求出初始基本可行解的檢驗數(shù)，找出閉回路，確定調整量； 求出最優(yōu)運輸方案和最小總運費。最小總運費F=?,假設有兩個生產地 A1, A2和三四個銷售地 B1, B2,B3,B4有關數(shù)據(jù)如下圖所示,寫出運輸問題的數(shù)學模型； 用最小元素法找出初始基本可行解; 求出初始基本可行解的檢驗數(shù)，找出閉回路，確定調整量； 求出最優(yōu)運輸方案和最小總運費。最小總運費F=?,第五章 目標規(guī)劃,1、目標規(guī)劃數(shù)學模型 正、負偏差變量均是非負的 目標規(guī)劃中可以沒有絕對約束，但必須有目標約束,2、目標規(guī)劃的圖解法 每一步要正確分清 d+0,d-=0 和 d+=0,d-

10、0 的區(qū)域 注：在考慮低級別目標時，不能破壞已經滿足的高級別目標，這是目標規(guī)劃的基本原則。但是，也不能因此而以為， 當高級別目標不能滿足時，其后的低級別目標也一定不能被滿足。,第六章 整數(shù)規(guī)劃,1、分支定界法求解整數(shù)規(guī)劃 掌握分支定界法的步驟，特別是繼續(xù)分支的條件及修改上下界的時機,2、匈牙利方法（指派問題） 人數(shù)和任務相等、目標是最小化 步驟 a. 效率矩陣的行、列變化 b. 畫出最少直線覆蓋零元素 c. 零元素的調整 指派問題擴展 a. 人數(shù)和任務不相等（例5.8） b. 目標函數(shù)是最大化（例5.9）,分配4名工人甲、 乙、丙、丁 分別完成4項任務B1, B2, B3, B4, 每人完成各

11、項任務的時間如下表所示，試確定最優(yōu)方案，使完成任務的總時間最小。,第七章 圖與網絡規(guī)劃,1、圖的節(jié)本概念,2、最小支撐樹 的求解 （以練習7.2 為例） 破圈法 避圈法,3、最短路的求法（以練習7.3為例） 指 定點到定點的最短路-狄克斯屈拉(Dijkstra)算法 任意兩點之間的最短路- Floyd(弗洛伊德)矩陣算法。,4、最大流 （看書上例題 ） 增廣鏈 最小截集 增廣鏈和最大流的關系 尋求最大流的標號（Ford,Fulkerson）,練習作業(yè)：求下列網絡的最大流與最小截集,(+vs,2),(+v1,2),(+v3,1),(+v4,1),W=f *s1+f *s2=8+3 =11,(+vs,2),(+v1,1),(-v2,2),標號點集V=vs,v1,v2, v4,;未標