運(yùn)籌學(xué)期末復(fù)習(xí)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、 = 1 且 s1 取值唯一時(shí)，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ù)學(xué)模型 適于動(dòng)態(tài)規(guī)劃方法求解的一類多階段決策問題，即具有無后效性的多階段決策問題的數(shù)學(xué)模型:,43,常用求最小的加法計(jì)算公式：,（邊界條件）,,階段指標(biāo),44,動(dòng)態(tài)規(guī)劃方法的基本步驟,用函數(shù)基本

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

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

21、sk+1的值也就完全確定，即有 sk+1 = Tk ( sk , uk ),49,動(dòng)態(tài)規(guī)劃建模要點(diǎn),⑤正確地寫出目標(biāo)函數(shù) 目標(biāo)函數(shù)由遞推關(guān)系構(gòu)成，因此，它應(yīng)滿足下列性質(zhì)：函數(shù)可分性：階段指標(biāo)相對(duì)獨(dú)立；要滿足遞推關(guān)系；過程函數(shù)嚴(yán)格單調(diào)。,50,動(dòng)態(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,（二）逆序求解動(dòng)態(tài)規(guī)劃基本方程,常見三種情況：一種是對(duì)于特殊的網(wǎng)絡(luò)求最優(yōu)路徑，可以直接在網(wǎng)絡(luò)圖上，直觀地使用標(biāo)號(hào)法（見下一節(jié)）求解；對(duì)于離散型的動(dòng)態(tài)規(guī)劃問題，常使用列表格（遞推方程）的方法求解。當(dāng)階段指標(biāo)與遞推公式可表示為解析顯函數(shù)時(shí)，對(duì)于規(guī)模較大，特別是連續(xù)型的動(dòng)態(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 個(gè)階段；②狀態(tài)變量sk表示第k階段開始的位置；③決策變量uk定義為到達(dá)下一站所選擇的路徑；④狀態(tài)轉(zhuǎn)移：決策確定了下一階段的狀態(tài)；⑤階段指標(biāo)：圖中線段上所標(biāo)的數(shù)值；,55,⑥ 最優(yōu)指標(biāo)函數(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的最短路徑長(zhǎng)度為21。（三）回溯求最優(yōu)策略： 由 f1(s1) 向 f4(s4) 回溯，得到最短路徑為：S ? A1 ? B1? C1? ES ? A3 ? B1? C1? ES ? A3 ? B2? C1? E,62,2、見以下有向圖，圖中數(shù)字為兩點(diǎn)間距離 要求：用表格（遞推方程）計(jì)算。（1）求出A→D的最短路徑以及最短長(zhǎng)度；（2）用

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

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

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

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

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

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

32、76,76,（5）對(duì)閉回路的各奇標(biāo)號(hào)頂點(diǎn)調(diào)整為：xij + ?，對(duì)各偶標(biāo)號(hào)頂點(diǎn) 調(diào)整為：xij - ?，特別 xpq - ? = 0， xpq變?yōu)榉腔兞俊?重復(fù)(2)、(3)步，直到所有檢驗(yàn)數(shù)均非負(fù)，得到最優(yōu)解。,,77,注意： （1）構(gòu)造閉回路進(jìn)行換基時(shí)，只有一個(gè)基變量出基，一個(gè)非基變量進(jìn)基； （2）如果偶標(biāo)號(hào)格中兩個(gè)變量減去調(diào)整量后都變?yōu)榱?，則取其中一個(gè)為出基變量，另一個(gè)填上運(yùn)量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è)法求解下列運(yùn)輸問題,83,

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

35、，n個(gè)變量，則它的對(duì)偶模型為n個(gè)約束，m個(gè)變量。(3) 從數(shù)據(jù)b、C的位置看：在兩個(gè)規(guī)劃模型中，b和C的位置對(duì)換。(4) 兩個(gè)規(guī)劃模型中的變量皆非負(fù)。,87,對(duì)稱形式： 互為對(duì)偶 (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,非對(duì)稱形式的對(duì)偶規(guī)劃:對(duì)非對(duì)稱形式，可以按照下面的對(duì)應(yīng)關(guān)系直接給出其對(duì)偶規(guī)劃(1) 將模型統(tǒng)一為“max，≤”或“min，≥” 的形式，對(duì)于其中的等式約束按下面(2)

37、、(3)中的方法處理；(2) 若原規(guī)劃的某個(gè)約束條件為等式約束，則在對(duì)偶規(guī)劃中與此約束對(duì)應(yīng)的那個(gè)變量取值沒有非負(fù)限制；(3) 若原規(guī)劃的某個(gè)變量的值沒有非負(fù)限制，則在對(duì)偶問題中與此變量對(duì)應(yīng)的那個(gè)約束為等式。,89,1、例子 P67 寫出下面線性規(guī)劃的對(duì)偶規(guī)劃模型,,90,解 先將約束條件變形為“≤”形式,,91,根據(jù)非對(duì)稱形式的對(duì)應(yīng)關(guān)系，直接寫出對(duì)偶規(guī)劃,,92,2、寫出下面線性規(guī)劃的對(duì)偶規(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,設(shè)最優(yōu)單純形表,其中：,96,96,,靈敏度分析,ci 單個(gè)變化保持最優(yōu)解不變的允許范圍bj 單個(gè)變化對(duì)解的可行性的影響線性規(guī)劃增加一個(gè)變量線性規(guī)劃增加一個(gè)約束,97,97,若ck是非基變量的系數(shù)：設(shè)ck變化為 ck + ?ck ?k’= ?k+ ?ck只要 ?k’≤ 0 ,即 ?ck ≤ -

40、?k ，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗(yàn)數(shù) ?k 用 ?k’取代，繼續(xù)單純形法的表格計(jì)算。,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 時(shí)，原最優(yōu)解不變。,100,100,設(shè) cl 變化為 cl + ?cl ，那么 ?j’=?j - ?cl alj ’ 只要對(duì)所有非基變量?j’≤0，即?j≤?clalj ，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗(yàn)數(shù)?j 用 ?j

42、’取代，繼續(xù)單純形法的表格計(jì)算。,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時(shí)，原最優(yōu)解不變。,103,103,設(shè)分量 br 變化為 br + ?br ，只要保持 B-1

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

45、4, 4+(-2)×4=-4<0, 2+0.5×4=4用對(duì)偶單純形法進(jìn)一步求解，可得：,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, 相應(yīng)有pn+1, cn+1 。 可計(jì)算出 B-1pn+1, ?n+1=cn+1-∑cri ari n+1 填入最優(yōu)單純形表：若 ?n+1 ≤ 0 則 最優(yōu)解不變；否則，進(jìn)一步用單純形法求解。,4、 增加新變量,109,109

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

48、進(jìn)一步用對(duì)偶單純形法求解。,5、增加一個(gè)約束條件,111,111,例 上例增加 3x1+ 2x2?15，原最優(yōu)解不滿足這個(gè)約束。于是,對(duì)表中新的一行利用矩陣初等行變換進(jìn)行處理，可得新的對(duì)偶單純形表：,112,112,經(jīng)對(duì)偶單純形法一步，可得最優(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,標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：Max z = c1x1 + c2x2 + … + cnxn,約束條件：a11x1 + a12x2 + … + a1nxn = b1a21x1 + a22x2 + … + a2nxn = b2 . . .am1x1 + am2x2 + …

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

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

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

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

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

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

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

57、目標(biāo)函數(shù)等值線與可行域的交點(diǎn)即最優(yōu)解（一個(gè)或多個(gè)），此目標(biāo)函數(shù)的值即最優(yōu)值。 否則，目標(biāo)函數(shù)等值線與可行域?qū)⒔挥跓o窮遠(yuǎn)處，此時(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,按照?qǐng)D解法的步驟： （1）以決策變量x1 ，x2 為坐標(biāo)向量作平面直角坐標(biāo)系；,136,136,（2）對(duì)每個(gè)約束（包括非負(fù)約束）條件作出直線（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）任意給定目標(biāo)函數(shù)一個(gè)值（例如37500）作一條目標(biāo)函數(shù)的等值線，并確定該等值線平移后值增加的方向（向上移動(dòng)函數(shù)值增大），平移此目標(biāo)函數(shù)的等值線，使其達(dá)到既與可行域有交點(diǎn)又不可能使值再增加的位置，得到交點(diǎn) (5,25)T ，即最優(yōu)

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

61、),144,單純形法的表格計(jì)算,145,考慮規(guī)范形式的線性規(guī)劃問題, 設(shè) 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 是基本可行解, 對(duì)應(yīng)的基是單位矩陣。,,147,初始單純形表： m m m

65、 m其中 f = -∑ cn+i bi ?j = cj -∑ cn+i aij 為檢驗(yàn)數(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、,標(biāo)準(zhǔn)化后，建立初始單純形表計(jì)算檢驗(yàn)數(shù)選檢驗(yàn)數(shù)>0對(duì)應(yīng)列的變量為進(jìn)基變量 求 （ ） ,選擇 列最小值對(duì)應(yīng)行的基變量為出基變量。5.A中進(jìn)基變量和出基變量交叉的元素aik為主元，在下一步初等行變換中變成1，此列其余分量變成0.上述步驟循環(huán)，直到所有檢驗(yàn)數(shù)≤ 0,停止計(jì)算。,149,注意：?jiǎn)渭冃畏ㄖ校?1.每一步運(yùn)算只能用矩陣初等行變換； 2.表中第3列的數(shù)（右

67、端項(xiàng)）總應(yīng)保持非負(fù)（≥ 0）； 3.當(dāng)所有檢驗(yàn)數(shù)均非正（≤ 0）時(shí)，得到最優(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,引入松弛變量化為標(biāo)準(zhǔn)形式： Max z =1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40