運用單純形表求解線性規(guī)劃問題難點課件

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

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

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

j=Cj-CBPj，若所有

j≤0，則問題已得到最優(yōu)解，停止計算，否則轉(zhuǎn)入下步。④在大于0的檢驗數(shù)中，若某個

k所對應(yīng)的系數(shù)列向量Pk≤0,則此問題是無界解，停止計算，否則轉(zhuǎn)入下步。⑤根據(jù)max{

j｜

j＞0}=

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

規(guī)則計算：

=min{bi/aik|aik＞0}=bl/aik確定xBl為換出變量。建立新的單純形表，此時基變量中xk取代了xBl的位置。⑥以aik為主元素進行迭代，把xk所對應(yīng)的列向量變?yōu)閱挝涣邢蛄浚碼ik變?yōu)?，同列中其它元素為0，轉(zhuǎn)第③步。

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

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

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

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

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

n維產(chǎn)銷平衡表上給出m+n-1個數(shù)字。

最優(yōu)性檢驗：計算各非基變量的檢驗數(shù)，當

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

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

ij0視為最優(yōu)。位勢法計算檢驗數(shù)

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

ij=cij–(ui+vj)ui代表產(chǎn)地Ai的位勢量，vj代表銷地Bj的位勢量?；兞康臋z驗數(shù)為0，即

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

ij，按min{

ij|

ij<0}=

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

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

bj

-

ai

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

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

≤[bi],xi

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

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

可行流定義第6章網(wǎng)絡(luò)分析網(wǎng)絡(luò)最大流問題第6章網(wǎng)絡(luò)分析31網(wǎng)絡(luò)最大流問題2.割的定義

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

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

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

難點:最優(yōu)化原理與動態(tài)規(guī)劃的思想方法。

第8章動態(tài)規(guī)劃教學要求371.動態(tài)規(guī)劃最優(yōu)性原理

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

(1)最優(yōu)策略的任何一部分子策略，也是相應(yīng)初始狀態(tài)的最優(yōu)