2023年全國(guó)碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩158頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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)基變量(上頁圖中 x24 ); (2)以 xrk 為起點(diǎn)找一條閉回路,除 xrk 外其余頂點(diǎn)必須為基變量格(上頁圖中的回路);,在運(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è)模型中為A,則另一個(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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論