運籌學期末復習

1、1,運籌學總復習,2,第八章 排隊論,3,s —— 系統(tǒng)中并聯(lián)服務臺的數(shù)目；? —— 平均到達率（單位時間到達的顧客數(shù)）；1/? —— 平均到達間隔（相繼到達顧客的平均間隔 時間）。? —— 平均服務率（單位時間服務的顧客數(shù)）；1/? —— 平均服務時間（為顧客服務的平均時間）。? —— 服務強度，即每個服務臺單位時間內(nèi)的

2、平均服務時間； 一般有 ? ? ? ? ? s? ? ；,穩(wěn)態(tài)排隊系統(tǒng)的參數(shù),4,Pn=P{N=n}：穩(wěn)態(tài)系統(tǒng)任一時刻狀態(tài)為n（系統(tǒng)中恰好有n個顧客）的概率； 特別當 n = 0 時，Pn即P0，為穩(wěn)態(tài)系統(tǒng)所有服務臺全部空閑的概率。,穩(wěn)態(tài)下系統(tǒng)的基本數(shù)量指標,5,到達的顧客不一定全部進入系統(tǒng)接受服務，設系統(tǒng)中有n個顧客時，每單位時間進入系統(tǒng)的顧客平均數(shù)為?n，每單位時間離開系統(tǒng)的顧客平均數(shù)為?n。我們引

3、入：?e —— 有效平均到達率，即每單位時間實際進入系統(tǒng)的平均顧客數(shù)（期望值）， ?e=∑?npn 對等待制的排隊系統(tǒng)，有 ?e ＝ ?,6,平均有效離去率 : ?e = ∑?n pn 從平穩(wěn)系統(tǒng)中均值的意義看，容易理解應有平均有效離去率等于平均有效到達率，即 ?e = ?e,7,L , Lq, ?e ,W , Wq 之間的關系： L = ?e W, Lq = ?e Wq幾何解釋：穩(wěn)態(tài)時，一個顧客

4、，進入系統(tǒng)后，每單位時間平均到達?e顧客。,隊長L由時間段內(nèi)W個?e組成的,,L=?eW,,5) Little公式,8,同理：Lq= ?eWq又 W=Wq+（1/?）------W與Wq只相差一段平均服務時間1/? L=Lq+(?e /?),5) Little公式,以上公式對一般泊松輸入—指數(shù)排隊模型成立。,9,對于平均隊長和平均隊列長，可用下列公式計算

5、 因此，只要知道 ，則 或 就可由以上兩公式求得，從而再由上面四公式就能求得四項主要工作指標。,,,,,,10,排隊論求解的主要數(shù)量指標,P0 、Pn 、L 、 Lq 、W 、Wq,11,單服務臺無限源系統(tǒng)M/M/1/∞

6、/∞/FCFSM/M/1/N/∞/FCFS,12,M/M/1/?/?/FCFS系統(tǒng): 參數(shù) ?，?問題的一般提法： 泊松輸入/負指數(shù)分布/單服務臺/系統(tǒng)無限制/顧客源無限制求解： (1)系統(tǒng)狀態(tài)P0 、Pn (2)系統(tǒng)運行指標：L 、 Lq 、W 、Wq,13,M/M/1/?/?/FCFS排隊系統(tǒng)模型的主要指標,1、系統(tǒng)中無顧客的概率：P0 =1? ρ2、系統(tǒng)中有n個顧客的概率： Pn =ρ

7、n .(1? ρ)3、系統(tǒng)中的平均顧客數(shù)：L= ρ /(1 ? ρ)4、顧客在系統(tǒng)中的平均逗留時間：W = L /?5、顧客花在排隊上的平均等待時間：Wq = W-1 /u6、平均排隊的顧客數(shù)： Lq= ? Wq,14,1、例子 P216 某醫(yī)院急診室同時只能診治1個病人，診治時間服從指數(shù)分布，每個病人平均需要15分鐘。病人按泊松分布到達，平均每小時到達3人。求該排隊系統(tǒng)的主要數(shù)量指標。,15,由題意知：該題是M/M/1/

8、?/?/FCFS排隊系統(tǒng),,(人／小時)，,＝60／15＝4(人／小時),故服務強度為,,其中，p0是急診室空閑的概率，也是病人不必等待立即就能就診的概率。,16,此模型的平均有效到達率，即是到達率 ?,病人在急診室內(nèi)外平均逗留時間：,病人平均等候時間：,(小時)＝45(分鐘),急診室內(nèi)外的病人平均數(shù)：,（人）,（小時）,急診室外排隊等待的病人平均數(shù)：,(人),17,2、 某醫(yī)院手術室只能同時診治一個病人，病人到達服從泊松

9、分布，每小時病人平均到達率為2.1(人/小時)。每次手術平均時間0.4(小時/人)，服從負指數(shù)分布．求：(1) 病房中病人的平均數(shù)(L)；(2) 排隊等待手術病人的平均數(shù)(Lq )；(3) 病人在病房中平均逗留時間(W)(4) 病人排隊等待時間(Wq)。,18,19,3、某醫(yī)院急診室每小時到達一個病人，輸入為最簡單流，急診室僅有一名醫(yī)生，病人接受緊急護理平均需20分鐘，服務時間為負指數(shù)分布，試求： （1） 穩(wěn)態(tài)情

10、況下：a)沒有病人的概率；b)有兩個病人的概率；c)急診室里病人的平均數(shù)；d)排隊中病人的平均數(shù)；e)病人在急診室中的平均時間． （2）為了保證病人急診所花費的平均時間少于25分鐘，那么平均緊急護理時間必須降至多少分鐘?,20,21,22,第七章 動態(tài)規(guī)劃,23,動態(tài)規(guī)劃的基本概念,1) 階段和階段變量 階段是按決策進行的時間或空間上先后順序劃分的。用以描述階段的變量叫作階段變量，一般以k表示階段變量．階段數(shù)等于

11、多階段決策過程從開始到結束所需作出決策的數(shù)目。,24,2）狀態(tài)、狀態(tài)變量和可能狀態(tài)集 描述事物(或系統(tǒng))在某特定的時間與空間域中所處位置及運動特征的量，稱為狀態(tài)。反映狀態(tài)變化的量叫做狀態(tài)變量。,25,每個階段的狀態(tài)可分為初始狀態(tài)和終止狀態(tài)，或稱輸入狀態(tài)和輸出狀態(tài)，階段k的初始狀態(tài)記作sk，終止狀態(tài)記為sk+1。通常定義階段的狀態(tài)即指其初始狀態(tài)。,26,一般狀態(tài)變量的取值有一定的范圍或允許集合，稱為可能狀態(tài)集，可能狀態(tài)集用相應階段

12、狀態(tài)sk的大寫字母Sk表示，sk?Sk，可能狀態(tài)集可以是一離散取值的集合，也可以為一連續(xù)的取值區(qū)間，視具體問題而定．,27,3）決策、決策變量和允許決策集合 決策的實質是關于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對下一階段狀態(tài)作出的選擇。,28,用以描述決策變化的量稱之決策變量。決策變量的值可以用數(shù)，向量、其它量，也可以是狀態(tài)變量的函數(shù). 記uk= uk(sk)，表示于階段 k 狀態(tài)為 sk 時的決策變量。,29,決策變

13、量的取值往往也有一定的允許范圍，稱之允許決策集合。決策變量uk(sk)的允許決策集用Uk(sk)表示, uk(sk)∈ Uk(sk) 允許決策集合實際是決策的約束條件。,30,4）策略和允許策略集合 策略(Policy)也叫決策序列．策略有全過程策略和k部子策略之分，全過程策略是指由依次進行的n個階段決策構成的決策序列，簡稱策略，表示為 p1,n{u1,u

14、2,…,un}。,31,從 k 階段到第 n 階段，依次進行的階段決策構成的決策序列稱為 k 部子策略, 表示為pk,n{ uk, uk+1, …, un } ，顯然當 k = 1 時的 k 部子策略就是全過程策略。,32,在實際問題中，由于在各個階段可供選擇的決策有許多個，因此，它們的不同組合就構成了許多可供選擇的決策序列(策略)，由它們組成的集合，稱之允許策略集合，記作P1,n ，從允許策略集中，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。

15、,33,5）狀態(tài)轉移方程 系統(tǒng)在階段k處于狀態(tài)sk，執(zhí)行決策uk(sk)的結果是系統(tǒng)狀態(tài)的轉移，即系統(tǒng)由階段k的初始狀態(tài)sk轉移到終止狀態(tài)sk+1 。,34,系統(tǒng)狀態(tài)的這種轉移，用數(shù)學公式描述即有：通常稱上式為多階段決策過程的狀態(tài)轉移方程。有些問題的狀態(tài)轉移方程不一定存在數(shù)學表達式，但是它們的狀態(tài)轉移，還是有一定規(guī)律可循的。,35,6)指標函數(shù) 用來衡量策略或子策略或決策的效果的某種數(shù)量指標，就稱為指標函數(shù)。它是

16、定義在全過程或各子過程或各階段上的確定數(shù)量函數(shù)。對不同問題，指標函數(shù)可以是諸如費用、成本、產(chǎn)值、利潤、產(chǎn)量、耗量、距離、時間、效用等等。,36,階段指標函數(shù)（階段效應） 用gk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為uk(sk)時的指標，則它就是第k段指標函數(shù)，簡記為gk,37,過程指標函數(shù)（目標函數(shù)）,用Rk(sk,uk)表示k子過程的指標函數(shù)。Rk(sk,uk) 不僅跟當前狀態(tài)sk有關，還跟該子過程策略pk(s

17、k)有關，因此它是sk和pk(sk)的函數(shù)，嚴格說來，應表示為:,38,7) 最優(yōu)解 用fk(sk)表示第k子過程指標函數(shù) ，在狀態(tài)sk下的最優(yōu)值,即 稱 fk(sk) 為第 k 子過程上的最優(yōu)指標函數(shù)；,39,相應的子策略稱為sk狀態(tài)下的最優(yōu)子策略，記為pk*(sk) ；而構成該子策賂的各段決策稱為該過程上的最優(yōu)決策，記為有 簡記為,40,特別， 當 k

18、 = 1 且 s1 取值唯一時，f1(s1)就是問題的最優(yōu)值，而p1* 就是最優(yōu)策略。,41,最優(yōu)策略即為s1=s1*狀態(tài)下的最優(yōu)策略： 我們把最優(yōu)策略和最優(yōu)值統(tǒng)稱為問題的最優(yōu)解。,42,8) 多階段決策問題的數(shù)學模型 適于動態(tài)規(guī)劃方法求解的一類多階段決策問題，即具有無后效性的多階段決策問題的數(shù)學模型:,43,常用求最小的加法計算公式：,（邊界條件）,,階段指標,44,動態(tài)規(guī)劃方法的基本步驟,用函數(shù)基本

19、方程逆推求解是常用的方法：首先要有效地建立動態(tài)規(guī)劃模型,然后再遞推求解基本方程,最后回溯求得最優(yōu)策略。合理、有效地建立一個動態(tài)規(guī)劃模型,是解決問題的關鍵。,45,（一）動態(tài)規(guī)劃建模要點,① 將實際問題恰當?shù)胤指畛蒼個子問題(n個階段) 通常是根據(jù)時間或空間而劃分，或者在經(jīng)由靜態(tài)的數(shù)學規(guī)劃模型轉換為動態(tài)規(guī)劃模型時，常取靜態(tài)規(guī)劃中變量的個數(shù)n。,46,動態(tài)規(guī)劃建模要點,② 正確地定義狀態(tài)變量sk，使它既能正確地描述過程的狀態(tài)，

20、又能滿足無后效性。 在動態(tài)規(guī)劃模型中，一般狀態(tài)變量要選取那種可以進行累計的量。,47,動態(tài)規(guī)劃建模要點,③正確地定義決策變量及各階段的允許決策集合Uk(sk)。 一般將問題中待求的量選作動態(tài)規(guī)劃模型中的決策變量。,48,動態(tài)規(guī)劃建模要點,④正確地寫出狀態(tài)轉移方程 要能正確反映狀態(tài)轉移規(guī)律。如果給定第 k 階段狀態(tài)變量 sk 的值，則該段的決策變量 uk 一經(jīng)確定，第k+1段的狀態(tài)變量

21、sk+1的值也就完全確定，即有 sk+1 = Tk ( sk , uk ),49,動態(tài)規(guī)劃建模要點,⑤正確地寫出目標函數(shù) 目標函數(shù)由遞推關系構成，因此，它應滿足下列性質：函數(shù)可分性：階段指標相對獨立；要滿足遞推關系；過程函數(shù)嚴格單調。,50,動態(tài)規(guī)劃基本方程 fn+1(sn+1) = 0 (邊界條件) fk(sk) = opt u{gk ( sk

22、 , uk ) + fk+1(sk+1) } k = n , n-1, … , 1,51,（二）逆序求解動態(tài)規(guī)劃基本方程,常見三種情況：一種是對于特殊的網(wǎng)絡求最優(yōu)路徑，可以直接在網(wǎng)絡圖上，直觀地使用標號法（見下一節(jié)）求解；對于離散型的動態(tài)規(guī)劃問題，常使用列表格（遞推方程）的方法求解。當階段指標與遞推公式可表示為解析顯函數(shù)時，對于規(guī)模較大，特別是連續(xù)型的動態(tài)規(guī)劃問題，常直接使用函數(shù)求優(yōu)的方法。,52,（三）回

23、溯求得最優(yōu)策略,從k=1開始，逐步向后歸納出前一環(huán)節(jié)各步所選擇的決策，得到?jīng)Q策序列，即最優(yōu)策略。,53,1、例子 P176用遞推方程求解最短路徑問題,,54,（一）建模,①如圖劃分成 5 個階段；②狀態(tài)變量sk表示第k階段開始的位置；③決策變量uk定義為到達下一站所選擇的路徑；④狀態(tài)轉移：決策確定了下一階段的狀態(tài)；⑤階段指標：圖中線段上所標的數(shù)值；,55,⑥ 最優(yōu)指標函數(shù) fk(sk) ：表示從目前狀態(tài)到E的最短路徑。

24、終端條件為 f5 ( s5 ) = f5 ( E ) = 0其含義是從E到E的最短路徑為0。,56,（二）逆推求解第4階段的遞推方程為,從 f5 ( s5 ) 到 f4 ( s4 ) 的遞推過程用下表表示,57,第3階段的遞推方程為：,,從 f4(s4) 到f3(s3) 的遞推過程用表格表示如下表：,58,第2階段的遞推方程為,從f3(s3) 到f2(s2) 的遞推過程用表格表示如下,,59,60,第1階段的遞推方程為：,

25、,,61,由此得到 f1(s1) =21 , 即從 A 到 E的最短路徑長度為21。（三）回溯求最優(yōu)策略： 由 f1(s1) 向 f4(s4) 回溯，得到最短路徑為：S ? A1 ? B1? C1? ES ? A3 ? B1? C1? ES ? A3 ? B2? C1? E,62,2、見以下有向圖，圖中數(shù)字為兩點間距離 要求：用表格（遞推方程）計算。（1）求出A→D的最短路徑以及最短長度；（2）用

26、雙箭頭在圖上注明。,63,參考答案,A到D的最短路徑：A→B3 → C1 → D最短長度：21,64,第四章 運輸問題,65,1. 求初始基本可行解 （西北角法、最小元素法）2. 求檢驗數(shù)（位勢法）3. 換基（閉回路）,表上作業(yè)法：,66,1、初始基本可行解的確定 （1）西北角法：從西北角（左上角）格開始，在格內(nèi)的右下角標上允許取得的最大數(shù)。然后按行（列）標下一格的數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的

27、其他格劃去。如此進行下去，直至得到一個基本可行解。,67,（2）最小元素法：從運價最小的格開始，在格內(nèi)的右下角標上允許取得的最大數(shù)。然后按運價從小到大順序填數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進行下去，直至得到一個基本可行解。,68,注:應用西北角法和最小元素法，每次填完數(shù)，都只劃去一行或一列，只有最后一個元例外（同時劃去一行和一列）。當填上一個數(shù)后行、列同時飽和時，也應任意劃去一行（列），在保留的列（

28、行）中沒被劃去的格內(nèi)標一個0。,69,由于目標要求極小，因此，當所有的檢驗數(shù)都大于或等于零時該調運方案就是最優(yōu)方案；否則就不是最優(yōu)，需要進行調整。,2、基本可行解的最優(yōu)性檢驗,70,位勢法 位勢：設對應基變量xij 的 m +n -1 個 ij ，存在ui ,vj 滿足 ui+vj=cij ，i=1,2 … ,m ; j=1,2 … ,n . 稱這些 ui , vj 為該基本可行解對應的位勢。,71

29、,由于有m + n 個變量（ ui , vj ）， m + n - 1 個方程（基變量個數(shù)）， 故有一個自由變量，位勢不唯一。,利用位勢求非基變量xij的檢驗數(shù)： ?ij = cij - ui - vj i = 1, … , m ; j = 1, … , n,72,位勢法求檢驗數(shù)：step 1 從任意基變量對應的 cij 開始,任取 ui 或 vj ，然后利用公式 cij = ui +

30、vj 依次找出 m + n 個 ui , vj step 2 計算非基變量的檢驗數(shù) ?ij = cij - ui - vj ；填入圓圈內(nèi),73,當非基變量的檢驗數(shù)出現(xiàn)負值時，則表明當前的基本可行解不是最優(yōu)解。在這種情況下，應該對基本可行解進行調整，即找到一個新的基本可行解使目標函數(shù)值下降，這一過程通常稱為換基(或主元變換)過程（閉回路法）。,3、求新的基本可行解,74,74,（1）選負檢驗數(shù)中最小者 ?rk，那么

31、 xrk 為主元，作為進基變量（上頁圖中 x24 ）; （2）以 xrk 為起點找一條閉回路，除 xrk 外其余頂點必須為基變量格（上頁圖中的回路）;,在運輸問題的表上作業(yè)法中，換基的過程是如下進行：,75,75,（3）為閉回路的每一個頂點標號， xrk 為 1號，沿一個方向（順時針或逆時針）依次給各頂點標號；（4）求? =Min{xij?xij對應閉回路上的偶數(shù)標號格}= xpq 那么確定 xpq為出基變量，?為調整量；,

32、76,76,（5）對閉回路的各奇標號頂點調整為：xij + ?，對各偶標號頂點 調整為：xij - ?，特別 xpq - ? = 0， xpq變?yōu)榉腔兞俊?重復(2)、(3)步，直到所有檢驗數(shù)均非負，得到最優(yōu)解。,,77,注意： （1）構造閉回路進行換基時，只有一個基變量出基，一個非基變量進基； （2）如果偶標號格中兩個變量減去調整量后都變?yōu)榱悖瑒t取其中一個為出基變量，另一個填上運量0。,77,78,1、例子 P

33、99,79,,,,,,,80,,,,,,,,,81,所有?ij ≥ 0，得到最優(yōu)解 x13 = 5,x14 = 2,x21 = 3,x24 = 1, x32 = 6, x34 = 3, 其余 xij = 0 ; 最優(yōu)值： f* = 3×5+10×2+1×3+8×1+4×6+5×3 = 85,,,,,,,82,2、用表上作業(yè)法求解下列運輸問題,83,

34、,,84,第三章 線性規(guī)劃對偶與靈敏度分析,85,對偶規(guī)劃的形式 有對稱形式和非對稱形式。 對稱形式的對偶規(guī)劃之間具有下面的對應關系： (1) 若一個模型為目標求“極大”，約束為“小于等于”的不等式，則它的對偶模型為目標求“極小”，約束是“大于等于”的不等式。即 “max，≤” 和 “min，≥” 相對應。,86,(2) 從約束系數(shù)矩陣看：一個模型中為Ａ，則另一個模型中為AT。一個模型是m個約束

35、，n個變量，則它的對偶模型為n個約束，m個變量。(3) 從數(shù)據(jù)b、C的位置看：在兩個規(guī)劃模型中，b和C的位置對換。(4) 兩個規(guī)劃模型中的變量皆非負。,87,對稱形式： 互為對偶 (LP) Max z = cT x (DP) Min f = bT y s.t. Ax ≤ b s.t. AT y ≥ c

36、 x ≥ 0 y ≥ 0 “Max -- ≤ ” “Min-- ≥”,,,,88,非對稱形式的對偶規(guī)劃:對非對稱形式，可以按照下面的對應關系直接給出其對偶規(guī)劃(1) 將模型統(tǒng)一為“max，≤”或“min，≥” 的形式，對于其中的等式約束按下面(2)

37、、(3)中的方法處理；(2) 若原規(guī)劃的某個約束條件為等式約束，則在對偶規(guī)劃中與此約束對應的那個變量取值沒有非負限制；(3) 若原規(guī)劃的某個變量的值沒有非負限制，則在對偶問題中與此變量對應的那個約束為等式。,89,1、例子 P67 寫出下面線性規(guī)劃的對偶規(guī)劃模型,,90,解 先將約束條件變形為“≤”形式,,91,根據(jù)非對稱形式的對應關系，直接寫出對偶規(guī)劃,,92,2、寫出下面線性規(guī)劃的對偶規(guī)劃模型,,,93,94,94,理解最優(yōu)

38、單純形表的含義考慮問題 Max z = c1 x1 + c2 x2 + … + cn xn s.t. a11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22x2 + … + a2nxn = b2 . . . am1x1 + am2x2 + … + amnxn

39、= bm x1 ，x2 ，… ，xn ≥ 0,靈敏度分析,95,95,設最優(yōu)單純形表,其中：,96,96,,靈敏度分析,ci 單個變化保持最優(yōu)解不變的允許范圍bj 單個變化對解的可行性的影響線性規(guī)劃增加一個變量線性規(guī)劃增加一個約束,97,97,若ck是非基變量的系數(shù)：設ck變化為 ck + ?ck ?k’= ?k+ ?ck只要 ?k’≤ 0 ,即 ?ck ≤ -

40、?k ，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗數(shù) ?k 用 ?k’取代，繼續(xù)單純形法的表格計算。,98,98,例 Max z = -2x1 - 3x2 - 4x3 S.t. -x1 -2x2 - x3 +x4 = - 3 -2x1 + x2 -3x3 +x5 = - 4 x1 ,x2

41、,x3 ,x4 ,x5 ≥0,99,99,例：最優(yōu)單純形表,從表中看到σ3= c3+Δc3-(c2×a13+c1×a23 ) 可得到Δc3 ≤ 9/5 時，原最優(yōu)解不變。,100,100,設 cl 變化為 cl + ?cl ，那么 ?j’=?j - ?cl alj ’ 只要對所有非基變量?j’≤0，即?j≤?clalj ，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗數(shù)?j 用 ?j

42、’取代，繼續(xù)單純形法的表格計算。,2、若 cl 是基變量的系數(shù),101,101,Max z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5 s.t. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2

43、 + x5 = 12 x1 , x2 , x3 , x4 , x5 ≥ 0,,,,例,,b,,增加變量,,增加約束,102,102,下表為最優(yōu)單純形表,考慮基變量系數(shù)c2發(fā)生變化,由σj=cj-(c1×a1j+c5×a5j+(c2+Δc2)×a2j) j=3,4可得到 -3≤Δc2≤1時，原最優(yōu)解不變。,103,103,設分量 br 變化為 br + ?br ，只要保持 B-1

44、(b + ?b)≥0 ，則最優(yōu)基不變，即對偶價格不變；否則，需要利用對偶單純形法繼續(xù)計算。,3、 右端常數(shù)的變化,104,104,上例最優(yōu)單純形表如下,例,105,105,0 0.25 0 這里 B-1 = -2 0.5 1 0.5 -0.125 0,各列分別對應 b1、b2、b3 的單一變化因此，設 b1 增加 4，則 x1 , x5 , x2分別變?yōu)椋?+0×4=

45、4, 4+(-2)×4=-4<0, 2+0.5×4=4用對偶單純形法進一步求解，可得：,106,106,于是，x* = ( 4, 3, 2, 0, 0 )T f* = 17,107,107,討論保持最優(yōu)基不變的前提下，?b2的允許變化范圍 4 + ?b2 ? 0.25 ? 0 ?b2 ? -16 4 + ?b2 ? 0.5 ? 0 ?b2 ? -8

46、 2 + ?b2 ? (- 0.125) ? 0 ?b2 ? 16于是 -8 ? ?b2 ? 16,108,108,增加變量 xn+1, 相應有pn+1, cn+1 。 可計算出 B-1pn+1, ?n+1=cn+1-∑cri ari n+1 填入最優(yōu)單純形表：若 ?n+1 ≤ 0 則 最優(yōu)解不變；否則，進一步用單純形法求解。,4、 增加新變量,109,109

47、,例,對前例，增加x6 , p6=( 2, 6, 3 )T, c6=5,用單純形法進一步求解，可得：x* = ( 1,1.5,0,0,0,2 )T f* = 16.5,110,110,首先，應把最優(yōu)解代入新的約束 若滿足，則最優(yōu)解不變，停止； 否則，引入一個新的非負變量（原約束若是小于等于形式可引入非負松弛變量，否則引入非負人工變量），填入最優(yōu)單純形表作為新的一行，并通過矩陣行變換把對應基中的列向量變?yōu)閱挝幌蛄俊?

48、進一步用對偶單純形法求解。,5、增加一個約束條件,111,111,例 上例增加 3x1+ 2x2?15，原最優(yōu)解不滿足這個約束。于是,對表中新的一行利用矩陣初等行變換進行處理，可得新的對偶單純形表：,112,112,經(jīng)對偶單純形法一步，可得最優(yōu)解為（3.5, 2.25, 0, 0, 3, 2 )T，最優(yōu)值為 13. 75,,113,113,靈敏度分析 1,114,114,115,參考答案,115,116,116,靈敏度分析 2,117

49、,118,參考答案,118,119,第二章 單 純 形 法,120,標準形式目標函數(shù)：Max z = c1x1 + c2x2 + … + cnxn,約束條件：a11x1 + a12x2 + … + a1nxn = b1a21x1 + a22x2 + … + a2nxn = b2 . . .am1x1 + am2x2 + …

50、 + amnxn = bm x1 ，x2 ，… ，xn ≥ 0,121,線性規(guī)劃的標準形式有如下四個特點：目標最大化、約束為等式、決策變量均非負、右端項非負。 對于各種非標準形式的線性規(guī)劃問題，轉換成標準形式進行求解。,122,1.極小化目標函數(shù)的問題： 設目標函數(shù)為 Min f = c1x1 + c2x2 + … + cnxn 則可以令z＝-f ，該極小化問題與下面的極大化問題

51、有相同的最優(yōu)解，即 Max z = -c1x1 - c2x2 - … - cnxn 但必須注意，盡管以上兩個問題的最優(yōu)解相同，但他們最優(yōu)解的目標函數(shù)值卻相差一個符號，即 Min f ＝ - Max z,123,2、約束條件不是等式的問題： 設約束條件為 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引進一個新的變量s ，使它等于約束右邊與左邊之差 s =bi–(ai1 x

52、1 + ai2 x2 + … + ain xn ) 顯然，s 也具有非負約束，即s≥0， 這時新的約束條件成為 ai1 x1+ai2 x2+ … +ain xn+s = bi,124,當約束條件為 ai1 x1+ai2 x2+ … +ain xn ≥ bi 時，類似地令 s =(ai1 x1+ai2 x2+ … +ain xn)- bi 顯然，s 也具有非負約束，即s≥0，這時新的約束條件成

53、為 ai1 x1+ai2 x2+ … +ain xn-s = bi,125,為了使約束由不等式成為等式而引進的變量 s 稱為“松弛變量”。如果原問題中有若干個非等式約束，則將其轉化為標準形式時，必須對各個約束引進不同的松弛變量。,126,3.變量無符號限制的問題：在標準形式中，必須每一個變量均有非負約束。當某一個變量xj沒有非負約束時，可以令 xj = xj’- xj”其中 xj’≥0

54、，xj”≥0即用兩個非負變量之差來表示一個無符號限制的變量，當然xj的符號取決于xj’和xj”的大小。,127,4.右端項有負值的問題：在標準形式中，要求右端項必須每一個分量非負。當某一個右端項系數(shù)為負時，如 bi<0，則把該等式約束兩端同時乘以-1，得到： -ai1 x1-ai2 x2- … -ain xn = -bi,128,線性規(guī)劃的圖解法,129,129,2.2.1 線性規(guī)劃的圖解法 對于只有兩個

55、決策變量的線性規(guī)劃問題，可以二維直角坐標平面上作圖表示線性規(guī)劃問題的有關概念，并求解。 圖解法求解線性規(guī)劃問題的步驟如下：,130,130,(1)建立直角坐標系： 分別取決策變量x1 ,x2 為坐標向量。,131,131,（2）繪制可行域： 對每個約束（包括非負約束）條件，作出其約束半平面（不等式）或約束直線（等式）。 各半平面與直線交出來的區(qū)域若存在，其中的點為此線性規(guī)劃的可行解。稱這個區(qū)域

56、為可行集或可行域。然后進行下步。否則若交為空，那么該線性規(guī)劃問題無可行解。,132,132,(3) 繪制目標函數(shù)等值線，并移動求解： 目標函數(shù)隨著取值不同，為一族相互平行的直線。 首先，任意給定目標函數(shù)一個值，可作出一條目標函數(shù)的等值線（直線）； 然后，確定該直線平移使函數(shù)值增加的方向； 最后，依照目標的要求平移此直線。,133,133,結果 若目標函數(shù)等值線能夠移動到既與可行域有交點又達到最優(yōu)的位置，此

57、目標函數(shù)等值線與可行域的交點即最優(yōu)解（一個或多個），此目標函數(shù)的值即最優(yōu)值。 否則，目標函數(shù)等值線與可行域將交于無窮遠處，此時稱無有限最優(yōu)解。,134,134,Max z = 1500 x1 + 2500 x2 s.t. 3x1+ 2x2 ≤ 65 (A) 2x1+ x2 ≤ 40 (B) 3x2 ≤ 75

58、 (C) x1 , x2 ≥ 0 (D, E),135,135,按照圖解法的步驟： （1）以決策變量x1 ，x2 為坐標向量作平面直角坐標系；,136,136,（2）對每個約束（包括非負約束）條件作出直線（A、B、C、D、E），并通過判斷確定不等式所決定的半平面。 各約束半平面交出來的區(qū)域即可行集或可行域如下圖陰影所示。,137,137,第2步圖示(1)

59、 分別作出各約束半平面,x2 ≥ 0,x1 ≥ 0,3x1+ 2x2 ≤ 65,2x1+ x2 ≤ 40,3x2 ≤ 75,138,138,第2步圖示(2) 各約束半平面的交－可行域,139,139,（3）任意給定目標函數(shù)一個值（例如37500）作一條目標函數(shù)的等值線，并確定該等值線平移后值增加的方向（向上移動函數(shù)值增大），平移此目標函數(shù)的等值線，使其達到既與可行域有交點又不可能使值再增加的位置，得到交點 (5,25)T ，即最優(yōu)

60、解。此目標函數(shù)的值為70000。,140,140,第3步圖示 作出目標函數(shù)等值線,,函數(shù)值增大,,,,,,,,,,,141,141,第3步圖示(2) 求出最優(yōu)解,1,,,142,142,根據(jù)上面的過程 我們得到這個線性規(guī)劃的 最優(yōu)解 x1=5、x2=25， 最優(yōu)值 z = 70000即最優(yōu)方案為生產(chǎn)甲產(chǎn)品5件、乙產(chǎn)品25件，可獲得最大利潤為70000元。,143,練習：P19例子 作業(yè)：P58—2(1)(4

61、),144,單純形法的表格計算,145,考慮規(guī)范形式的線性規(guī)劃問題, 設 bi > 0 i = 1 , … , m Max z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn ≤ b1 a21 x1 + a22 x2 + … + a2n xn

62、 ≤ b2 . . am1 x1 + am2 x2 + … + amn xn ≤ bm x1 ，x2 ，… ，xn ≥ 0,,146,加入松弛變量： Max z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1

63、+ a12 x2 + … + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2 . . am1 x1 + am2 x2 + … + amn xn+ xn+m = bm x1 ，x2 ，… ，xn ，xn+1 ，… ，xn+m ≥ 0

64、 顯然，xj = 0 j = 1, … , n ; xn+i = bi i = 1 , … , m 是基本可行解, 對應的基是單位矩陣。,,147,初始單純形表： m m m

65、 m其中 f = -∑ cn+i bi ?j = cj -∑ cn+i aij 為檢驗數(shù) i =1 i =1 cn+i = 0 i= 1,…,m an+i,i = 1 , an+i,j = 0 ( j≠i ) i , j = 1, … , m,148

66、,標準化后，建立初始單純形表計算檢驗數(shù)選檢驗數(shù)>0對應列的變量為進基變量 求 （ ） ,選擇 列最小值對應行的基變量為出基變量。5.A中進基變量和出基變量交叉的元素aik為主元，在下一步初等行變換中變成1，此列其余分量變成0.上述步驟循環(huán)，直到所有檢驗數(shù)≤ 0,停止計算。,149,注意：單純形法中， 1.每一步運算只能用矩陣初等行變換； 2.表中第3列的數(shù)（右

67、端項）總應保持非負（≥ 0）； 3.當所有檢驗數(shù)均非正（≤ 0）時，得到最優(yōu)單純形表。,150,Max z =1500x1+2500x2  s.t. 3x1 + 2x2 ? 65 2x1 + x2 ? 40 3x2 ? 75 x1 ,x2 ? 0,1、例子 P39用單純形法求解下面線

68、性規(guī)劃問題,151,引入松弛變量化為標準形式： Max z =1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40