教學要求1).了解一般線性規劃問題的數學模型。2)．掌握圖解法。3)．理解單純形法原理。4)．掌握單純形法的計算步驟。5)．對單純形法的進一步討論。6)．了解單純形法的矩陣描述。教學重點與難點重點:1、單純形方法中初始可行基的確定方法、基可行解的轉換和最優性檢驗；2、運用單純形表求解線性規劃問題。難點:最優性檢驗、基的變換。第1章線性規劃教學要求第1章線性規劃11、線性規劃問題的數學建模2、LP的數學模型及準型化

3、線性規劃解的概念----基,基解,基可行解,…

4、線性規劃的圖解法5、單純形法原理(1)線性規劃問題的可行解集(即可行域)是凸集.(2)(線性規劃幾何理論基本定理)若X是一可行解,則X是C的一個頂點的充分必要條件是X為線性規劃的基本可行解.(3)若可行域非空有界，則線性規劃問題的目標函數一定可以在可行域的頂點上達到最優值.(即LP有最優解,一定存在一個基可行解是最優解)(4)若目標函數在k個點處達到最優值(k≥2),世隔絕則在這些點的任意凸組合上也達到最優值.第1章線性規劃1、線性規劃問題的數學建模第1章線性規劃26、單純形法①將線性規劃問題化成標準型。②找出或構造一個m階單位矩陣作為初始可行基，建立初始單純形表。③計算各非基變量xj的檢驗數

j=Cj-CBPj，若所有

j≤0，則問題已得到最優解，停止計算，否則轉入下步。④在大于0的檢驗數中，若某個

k所對應的系數列向量Pk≤0,則此問題是無界解，停止計算，否則轉入下步。⑤根據max{

j｜

j＞0}=

k原則，確定xk為換入變量(進基變量)，再按

規則計算：

=min{bi/aik|aik＞0}=bl/aik確定xBl為換出變量。建立新的單純形表，此時基變量中xk取代了xBl的位置。⑥以aik為主元素進行迭代，把xk所對應的列向量變為單位列向量，即aik變為1，同列中其它元素為0，轉第③步。

第1章線性規劃6、單純形法第1章線性規劃37、LP解在單純形中的討論LP無解的條件;LP有無界解的條件;LP有無窮解的條件;LP有惟一解的條件;LP有退化解的條件.第1章線性規劃7、LP解在單純形中的討論第1章線性規劃48、單純形中確定最優基及其逆的方法在初始單純形表中,與最終表里的單位陣對應的矩陣即為最優基B*;在最終表中,與初始單純形表里的單位陣對應的矩陣即為最優基的逆(B*)-1.第1章線性規劃8、單純形中確定最優基及其逆的方法第1章線性規劃5第2章對偶理論教學要求1)．理解原問題與對偶問題。會寫對偶問題。2)．了解對偶問題的基本性質。3)．掌握對偶單純形法。4)．掌握靈敏度分析。5)．了解影子價格。解釋經濟意義。教學重點與難點重點:線性規劃的對偶理論和基本性質；對偶單純形法的計算方法；靈敏度分析。難點:對偶理論及基本性質；對偶單純形法；靈敏度分析第2章對偶理論教學要求61、對稱形式的對偶關系第2章對偶理論（D）（L）

上、下”交換，“左、右”換位，不等式變號，“極大”變“極小一般形式的對偶問題按照原始-對偶表直接寫出1、對稱形式的對偶關系第2章對偶理論（D）（L）上、下72、對偶問題的基本性質（對偶定理）對稱性定理——對偶問題的對偶是原問題。弱對偶定理——若一對對稱形式的對偶線性規劃

注:由該定理可以得到關于“界”的結果無界性定理最優性準則定理強對偶定理若原始問題和對偶問題兩者均可行，則兩者均有最優解，且此時目標函數值相同。互補松弛性定理

第2章對偶理論2、對偶問題的基本性質（對偶定理）第2章對偶理論83、對偶單純形法對偶單純形法思想在保持原始可行的前提下（b列保≥0）通過逐步迭代實現對偶可行（檢驗數行≤0）對偶單純形法步驟第2章對偶理論3、對偶單純形法第2章對偶理論9第2章對偶理論否初始正則解(對偶可行)檢查可行是則停止得最優解選出基變量檢查是否無可行解是則停止否無最優解選入基變量進行旋轉變換第2章對偶理論否初始正則解(對偶可行)檢查可行是則停止得104、靈敏度分析價值系數C發生變化的情況右端常數b發生變化系數陣A的元素發生變化

(1)增加1個新變量;(2)增加1個約束條件.第2章對偶理論4、靈敏度分析第2章對偶理論11第3章運輸問題教學要求1)理解運輸問題的典例和數學模型。2)掌握表上作業法。3)掌握產銷不平衡的運輸問題及其處理方法。教學重點與難點重點:運輸問題的表上作業法；產銷不平衡問題的轉化。難點:表上作業法；產銷不平衡問題的求解方法。第3章運輸問題教學要求12運輸問題的三種類型產銷平衡第3章運輸問題運輸問題的三種類型第3章運輸問題13表上作業法求解步驟：找出初始方案（初始基可行解）：在m

n維產銷平衡表上給出m+n-1個數字。

最優性檢驗：計算各非基變量的檢驗數，當

ij0最優。方案調整與改進：確定進基變量和離基變量，找出新的基可行解。第3章運輸問題表上作業法求解步驟：第3章運輸問題14確定初始方案(1)最小元素法“就近運給”，從單位運價表中最小運價開始確定供銷關系，逐次挑選最小元素，安排運量min{ai,bj}。(2)最大差額法(Vogel法)不能按最小運費就近供應，就考慮次小運費。各行(各列)的最小運費與次小運費之差稱為行差(列差)。差額越大，說明不能按最小運費調運時，運費增加最多。對最大差額處就采用最小運費調運。第3章運輸問題確定初始方案第3章運輸問題15最優性檢驗判別方法是計算非基變量的檢驗數：

ij=cij–CBPij’=cij–CBB-1Pij運輸問題的目標函數要求為最小，即當

ij0視為最優。位勢法計算檢驗數

ij=cij–CBPij’=cij–CBB-1Pij

ij=cij–(ui+vj)ui代表產地Ai的位勢量，vj代表銷地Bj的位勢量。基變量的檢驗數為0，即

ij=cij–ui–vj=0，并令u1=0，計算各行各列的位勢量。第3章運輸問題最優性檢驗第3章運輸問題16方案改進（閉回路調整法）(1)確定進基變量檢查非基變量xij的檢驗數

ij，按min{

ij|

ij<0}=

lk確定xlk進基。(2)確定離基變量非基變量xlk進基之后，要求它的運量增加量按照它所在行和列的運量保持產銷平衡。保持產銷平衡的方法是閉回路法。閉回路法：以進基變量xlk所在格為始點和終點，其余頂點均為基變量的封閉回路。閉回路的畫法：從進基變量xlk所在格開始，用水平或垂直線向前劃，每碰到一個基變量格轉90o，繼續前進，直到返回始點。奇偶點：始點是偶點，依次奇偶相間標注；偶點標“+”，表示運量增加量；奇點標“-”，表示運量減少量。調整量：最大可調整的運量，為奇點運量的最小值。奇點運量的最小值所在格的基變量離基。第3章運輸問題方案改進（閉回路調整法）第3章運輸問題17產銷不平衡的運輸問題產大于銷：虛設一個銷地Bk(多于物資在產地存儲)，其運價為0，銷量(存儲量)為產銷量之差bk=

ai-bj。產小于銷：虛設一個產地Al(不足物資的脫銷量)，其運價為0，產量(脫銷量)為銷產量之差ak=

bj

-

ai

。帶存儲費或缺貨費的產銷不平衡運輸問題第3章運輸問題產銷不平衡的運輸問題第3章運輸問題18第4章整數線性規劃教學要求1)了解整數規劃的特點及應用。會建立整數規劃模型。2)學會分配問題與匈牙利法。3)理解并掌握分枝定界法。4)理解割平面法。了解割平面法求解整數規劃思想與方法。教學重點與難點重點:解整數規劃問題的分枝定界法和割平面法；分配問題的數學模型及其解法。難點:分枝定界法和割平面法；分配問題的解法。第4章整數線性規劃教學要求19整數規劃建模問題經典分配(指派)問題第4章整數線性規劃分配問題的數學模型

設決策變量為：s.t.整數規劃建模問題第4章整數線性規劃分配問題的數學模型設20匈牙利方法步驟第一步：成本矩陣的每一行及每一列減去該行或列的最小數，使每行每列至少有一個0；第二步：畫直線覆蓋全部0元素。覆蓋原則如果直線條數=n（此時矩陣每行都有一個打（）的0，并且所有打（）的0必在不同行不同列）,只要令對應打（）0元素的xij=1即為最優解，算法結束。如果直線條數<n（此時打（）的0個數<n），轉下一步；第三步：進行成本矩陣變換。變換原則得到一個新的成本矩陣，轉第二步。直到矩陣的每一行都有一個打（）的0元素為止第4章整數線性規劃匈牙利方法步驟第4章整數線性規劃21匈牙利方法步驟覆蓋原則1、從第一行開始，若該行只有一個0元素，就對這個0打上（），對打（）的0元素所在列畫一條直線；若該行沒有或有兩個以上0（已劃去的不計在內），則轉下一行，依次進行到最后一行；2、從第一列開始，與行做法類似，依次進行到最后一列；3、重復以上兩個步驟。若還有未被劃去的0,且未被劃去的0之間存在閉回路。這時可沿著閉回路的走向，對每個間隔的0打（），然后對打（）的0，或所在的行，或所在的列，畫一條直線。變換原則1、從矩陣未被直線覆蓋的數字中找出一個最小的數k；2、對矩陣的每行，當該行有直線覆蓋時，令ui=0，無直線覆蓋的令ui=k；3、對矩陣有直線覆蓋的列，令vj=-k，對無直線覆蓋的令vj=0；4、從原矩陣的每個元素cij中分別減去ui和vj，得到一個新矩陣。第4章整數線性規劃匈牙利方法步驟第4章整數線性規劃22第4章整數線性規劃一般指派問題的轉化(1)最大化分配問題(2)人數和工作數不等的分配問題(3)一個人可做幾項工作的分配問題(4)某項工作一定不能由某人做的分配問題第4章整數線性規劃一般指派問題的轉化(1)最大化分配問題23第4章整數線性規劃分枝定界法步驟(1)不考慮整數約束，解相應LP問題(即松弛問題)(2)檢查是否符合整數要求，是，則得最優解，算法結束。否則，轉下步(3)分枝:任取一個非整數變量xi=bi，構造兩個新的約束條件：xi

≤[bi],xi

≥[bi]+1,分別加入到上一個LP問題，形成兩個新的分枝問題。(4)定界:不考慮整數要求，解分枝問題。若整數解的Z值>所有分枝末梢的Z值，則得最優解。否則，取Z值最大的非整數解，繼續分解，Goto3第4章整數線性規劃分枝定界法步驟24第4章整數線性規劃割平面方法(Gomory)

掌握確定Gomory約束的方法通常取非整數解變量中分數部分最大的一個基變量所在的方程來求G-約束選：拆：取:變:移：第4章整數線性規劃割平面方法(Gomory)通常取非整數解25第6章網絡分析教學要求1)．理解圖的基本概念與模型。會建立圖的模型。2)．了解樹圖和圖的最小部分樹。掌握樹圖的性質。3)．掌握最短路問題。4)．掌握網絡的最大流。5)．掌握最小費用最大流問題。教學重點與難點重點:最小支撐樹問題；最短路問題最大流問題。難點:最短路與最大流問題的求解方法。第6章網絡分析教學要求26第6章網絡分析樹圖定義與性質(1)定義:一個連通的無圈圖則稱為樹，一個林的每個連通子圖都是一個樹。(2)定理以下關于樹的六種不同描述是等價的：①無圈連通圖。②無圈，q=p-1(p點數;q邊數)。③連通，q=p-1。④無圈，但若任意增加一條邊，則可得到一個且僅一個圈。⑤連通，但若任意舍棄一條邊，圖便不連通。⑥每一對頂點之間有一條且僅有一條鏈。第6章網絡分析樹圖定義與性質27網絡最小部分樹問題(1)破圈法(2)生長法(避圈法)第6章網絡分析網絡最小部分樹問題第6章網絡分析28網絡最短路問題----表格實現第6章網絡分析v1139538362v6v5v3v4v22058910網絡最短路問題----表格實現第6章網絡分析v11329第6章網絡分析vjv1v2v3v4v5v6初始值T(vj

)0∞∞∞∞∞第一次P()+lij0+20+60+∞0+∞0+∞T()26∞∞∞第二次P()+lij2+32+82+92+∞T()51011∞第三次P()+lij5+55+35+∞T()108∞第四次P()+lij8+∞8+1T()109第6章網絡分析vjv1v2v3v4v5v6初始值T(vj30網絡最大流問題最大流問題的數學模型：

可行流定義第6章網絡分析網絡最大流問題第6章網絡分析31網絡最大流問題2.割的定義

割是指將容量網絡中的發點和收點分割開,并使和流中斷的一組弧的集合.第6章網絡分析},),({S(S,)jiji?=uuuu網絡割的容量最小割

所有割集中容量最小的一個割集.網絡最大流問題第6章網絡分析},),({S(S,)32網絡最大流問題3.增廣鏈定義第6章網絡分析是指滿足以下條件的s→t的一條鏈:在這條鏈上所有指向為s→t的弧為非飽合弧(f<c);所有指向為t→s的弧有非零流弧(f>0).增廣鏈的作用可調整可行流的流量,使流量增大.調整原則若在一個有可行流的網絡圖中不存在增廣鏈,則說明流量不能再調整,于是當前流為最大流.即是否存在增廣鏈是判斷最大流的標志網絡最大流問題第6章網絡分析是指滿足以下條件的s→t的一條33網絡最大流問題3.Ford－Fulkerson算法步驟

第6章網絡分析①為網絡分配初始流fij標在圖中弧旁的()內或為已知；②尋求增廣鏈（標號原則）。若不存在，則已最優,算法結束；否則轉下步；③在增廣鏈上調整流量（調整原則），產生新的可行流，轉步②。網絡最大流問題第6章網絡分析①為網絡分配初始流fij標在圖34網絡最小費用流問題算法一般步驟第一步從零流開始.f0為可行流,也是相應的流量為0時費用最小的;第二步對可行流構造加權網絡W(fk).構造原則.第三步在加權網絡W(fk)中尋找費用最小的增廣鏈,也即求從s到t的最短路,并將該增廣鏈上流量調整至允許的最大值,得到一個新的流量更大的可行流,轉第二步;若在此網絡圖中不存在這樣的增廣鏈,則當前流即為要尋找的最小費用最大流,算法結束.第6章網絡分析網絡最小費用流問題第6章網絡分析35網絡最小費用流問題構造加權網絡W(fk)構造原則.對0<fij<cij的弧,當其為正向弧時,通過單位流量的費用為bij,為反向弧時,相應的費用為-bij.即在i和j點間分別畫出弧(i,j)和(j,i),其權數分別為bij和-bij;對fij=cij的弧(i,j),因該弧流量已飽和,在增廣鏈中只能作為反向弧,故在W(fk)中只畫出弧(j,i),其權數為-bij;對fij=0的弧(i,j),在增廣鏈中只能為正向弧,故在W(fk)中只畫出弧(i,j),其權數為bij.第6章網絡分析網絡最小費用流問題第6章網絡分析36第8章動態規劃教學要求1)理解多階段的決策問題。2)掌握最優化原理與動態規劃的數學模型。3)掌握確定性動態規劃模型的求解。4)了解一般數學規劃模型的動態規劃解法。教學重點與難點重點:最優化原理與動態規劃的數學模型；離散確定性動態規劃模型的求解。

難點:最優化原理與動態規劃的思想方法。

第8章動態規劃教學要求371.動態規劃最優性原理

“最優策略具有的基本性質是：無論初始狀態和初始決策如何，對于前面決策所造成的某一狀態而言，下余的決策序列必構成最優策略”。最優性原理的含意

(1)最優策略的任何一部分子策略，也是相應初始狀態的最優