運(yùn)籌學(xué)第二章-線性規(guī)劃_第1頁(yè)
運(yùn)籌學(xué)第二章-線性規(guī)劃_第2頁(yè)
運(yùn)籌學(xué)第二章-線性規(guī)劃_第3頁(yè)
運(yùn)籌學(xué)第二章-線性規(guī)劃_第4頁(yè)
運(yùn)籌學(xué)第二章-線性規(guī)劃_第5頁(yè)
已閱讀5頁(yè),還剩79頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡(jiǎn)介

1、2020/7/15,.,1,Chapter2 線性規(guī)劃及單純形法 (Linear Programming),LP的數(shù)學(xué)模型 圖解法 單純形法 單純形法的進(jìn)一步討論人工變量法 LP模型的應(yīng)用,本章主要內(nèi)容:,2020/7/15,.,2,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,1. 規(guī)劃問(wèn)題,生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排,使人力、物力等各種資源得到充分利用,獲得最大的效益,這就是規(guī)劃問(wèn)題。,線性規(guī)劃通常解決下列兩類(lèi)問(wèn)題:,(1)當(dāng)任務(wù)或目標(biāo)確定后,如何統(tǒng)籌兼顧,合理安排,用最少的資源 (如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等)去完成確定的任務(wù)或目標(biāo),(2)在一定的資源條件限制下,如何組織安排生產(chǎn)獲得最好的經(jīng)

2、濟(jì)效益(如產(chǎn)品量最多 、利潤(rùn)最大.),2020/7/15,.,3,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,例1.1 如圖所示,如何截取x使鐵皮所圍成的容積最大?,2020/7/15,.,4,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,例1.2 某廠生產(chǎn)兩種產(chǎn)品,下表給出了單位產(chǎn)品所需資源及單位產(chǎn)品利潤(rùn),問(wèn):應(yīng)如何安排生產(chǎn)計(jì)劃,才能使總利潤(rùn)最大?,解:,1.決策變量:設(shè)產(chǎn)品I、II的產(chǎn)量 分別為 x1、x2,2.目標(biāo)函數(shù):設(shè)總利潤(rùn)為z,則有: max z = 2 x1 + x2,3.約束條件:,2020/7/15,.,5,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,例1.3 已知資料如下表所示,問(wèn)如何安排生產(chǎn)才能使利潤(rùn)最大?,解:,1.決策變量:設(shè)產(chǎn)

3、品I、II的產(chǎn)量分別為 x1、x2,2.目標(biāo)函數(shù):設(shè)總利潤(rùn)為z,則有: max z = 2 x1 + 3x2,3.約束條件:,2020/7/15,.,6,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,例1.4 某廠生產(chǎn)三種藥物,這些藥物可以從四種不同的原料中提取。下表給出了單位原料可提取的藥物量,解:,要求:生產(chǎn)A種藥物至少160單位;B種藥物恰好200單位,C種藥物不超過(guò)180單位,且使原料總成本最小。,1.決策變量:設(shè)四種原料的使用 量分別為:x1、x2 、x3 、x4,2.目標(biāo)函數(shù):設(shè)總成本為z min z = 5 x1 + 6 x2 + 7 x3 + 8 x4,3.約束條件:,2020/7/15,.,7,例

4、1.5 某航運(yùn)局現(xiàn)有船只種類(lèi)、數(shù)量以及計(jì)劃期內(nèi)各條航線的貨運(yùn)量、貨運(yùn)成本如下表所示:,問(wèn):應(yīng)如何編隊(duì),才能既完成合同任務(wù),又使總貨運(yùn)成本為最小?,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,2020/7/15,.,8,解:,設(shè):xj為第j號(hào)類(lèi)型船隊(duì)的隊(duì)數(shù)(j = 1,2,3,4), z 為總貨運(yùn)成本,則: min z = 36x1 + 36x2 + 72x3 + 27x4,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,2020/7/15,.,9,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,2. 線性規(guī)劃的數(shù)學(xué)模型由三個(gè)要素構(gòu)成,決策變量 Decision variables 目標(biāo)函數(shù) Objective function 約束條件 Constraints

5、,其特征是: (1)問(wèn)題的目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù),通常是求最大值或最小值; (2)問(wèn)題的約束條件是一組多個(gè)決策變量的線性不等式或等式。,怎樣辨別一個(gè)模型是線性規(guī)劃模型?,2020/7/15,.,10,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,3. 建模條件,(1) 優(yōu)化條件:?jiǎn)栴}所要達(dá)到的目標(biāo)能用線型函數(shù)描述,且能夠用極值(max 或 min)來(lái)表示;,(2) 限定條件:達(dá)到目標(biāo)受到一定的限制,且這些限制能夠用決策變量的線性等式或線性不等式表示;,(3) 選擇條件:有多種可選擇的方案供決策者選擇,以便找出最優(yōu)方案。,2020/7/15,.,11,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,4. 建模步驟,(1) 確定決策

6、變量:即需要我們作出決策或選擇的量。一般情況下,題目問(wèn)什么就設(shè)什么為決策變量;,(2) 找出所有限定條件:即決策變量受到的所有的約束;,(3) 寫(xiě)出目標(biāo)函數(shù):即問(wèn)題所要達(dá)到的目標(biāo),并明確是max 還是 min。,2020/7/15,.,12,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,目標(biāo)函數(shù):,約束條件:,5. 線性規(guī)劃數(shù)學(xué)模型的一般形式,簡(jiǎn)寫(xiě)為:,2020/7/15,.,13,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,向量形式:,其中:,2020/7/15,.,14,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,矩陣形式:,其中:,2020/7/15,.,15,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,6. 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式,特點(diǎn): 目標(biāo)函數(shù)求最大值; (2)

7、 約束條件為等式方程,且右端常數(shù)項(xiàng)bi都大于或等于零; (3) 決策變量xj為非負(fù)。,2020/7/15,.,16,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,(2)如何化標(biāo)準(zhǔn)形式,目標(biāo)函數(shù)的轉(zhuǎn)換,如果是求極小值即 ,則可將目標(biāo)函數(shù)乘以 (-1),可化為求極大值問(wèn)題。,也就是:令 ,可得到上式。,即,若存在取值無(wú)約束的變量 ,可令 其中:,變量的變換,2020/7/15,.,17,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,約束方程的轉(zhuǎn)換:由不等式轉(zhuǎn)換為等式。,稱(chēng)為松弛變量,稱(chēng)為剩余變量,常量 bi0 的變換:約束方程兩邊乘以(1),2020/7/15,.,18,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,例1.6 將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式,用

8、替換 ,且,解:()因?yàn)閤3無(wú)符號(hào)要求 ,即x3取正值也可取負(fù)值,標(biāo)準(zhǔn)型中要求變量非負(fù),所以,2020/7/15,.,19,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,(2) 第一個(gè)約束條件是“”號(hào),在“”左端加入松馳變量x4,x40,化為等式; (3) 第二個(gè)約束條件是“”號(hào),在“”左端減去剩余變量x5,x50; (4) 第3個(gè)約束方程右端常數(shù)項(xiàng)為-5,方程兩邊同乘以(-1),將右端常數(shù)項(xiàng)化為正數(shù); (5) 目標(biāo)函數(shù)是最小值,為了化為求最大值,令z=-z,得到max z=-z,即當(dāng)z達(dá)到最小值時(shí)z達(dá)到最大值,反之亦然;,2020/7/15,.,20,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,標(biāo)準(zhǔn)形式如下:,2020/7/15,.

9、,21,例1.7 將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式,為無(wú)約束(無(wú)非負(fù)限制),線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,2020/7/15,.,22,解:,標(biāo)準(zhǔn)形式如下:,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,2020/7/15,.,23,例1.8 將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型,解:,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,無(wú)約束,2020/7/15,.,24,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,7. 線性規(guī)劃問(wèn)題的解,線性規(guī)劃問(wèn)題,求解線性規(guī)劃問(wèn)題,就是從滿足約束條件(2)、(3)的方程組中找出一個(gè)解,使目標(biāo)函數(shù)(1)達(dá)到最大值。,2020/7/15,.,25,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,可行解:滿足約束條件、的解為可行解。所有可行解的集合為可行域。 最優(yōu)解:使

10、目標(biāo)函數(shù)達(dá)到最大值的可行解。 基:設(shè)A為約束條件的mn階系數(shù)矩陣(mn),其秩為m,B是矩陣A中m階滿秩子矩陣(B0),稱(chēng)B是規(guī)劃問(wèn)題的一個(gè)基矩陣,簡(jiǎn)稱(chēng)基。設(shè):,稱(chēng) B中每個(gè)列向量Pj ( j = 1 2 m) 為基向量。與基向量Pj 對(duì)應(yīng)的變量xj 為基變量。除基變量以外的變量為非基變量。,2020/7/15,.,26,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,基解:某一確定的基B,令非基變量等于零,由約束條件方程解出基變量,稱(chēng)這組解為基解。在基解中變量取非0值的個(gè)數(shù)不大于方程數(shù)m,基解的總數(shù)不超過(guò) 基可行解:滿足變量非負(fù)約束條件的基本解,簡(jiǎn)稱(chēng)基可行解。 可行基:對(duì)應(yīng)于基可行解的基稱(chēng)為可行基。,2020/7/

11、15,.,27,線性規(guī)劃問(wèn)題的數(shù)學(xué)模型,例1.10 求線性規(guī)劃問(wèn)題的所有基矩陣。,解: 約束方程的系數(shù)矩陣為25矩陣,r(A)=2,2階子矩陣有10個(gè),其中基矩陣只有9個(gè),即,2020/7/15,.,28,圖解法,線性規(guī)劃問(wèn)題的求解方法,一 般 有 兩種方法,圖 解 法 單純形法,兩個(gè)變量、直角坐標(biāo) 三個(gè)變量、立體坐標(biāo),適用于任意變量、但必需將 一般形式變成標(biāo)準(zhǔn)形式,下面我們分析一下簡(jiǎn)單的情況 只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題,這時(shí)可以通過(guò)圖解的方法來(lái)求解。圖解法具有簡(jiǎn)單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點(diǎn)。,2020/7/15,.,29,解題步驟,4. 確定目標(biāo)函數(shù)值增大(或

12、減?。┓较颍?1. 作出平面直角平面坐標(biāo)系;,2. 根據(jù)約束條件找出可行域;,3. 作出目標(biāo)函數(shù)線;,圖解法,5. 讓目標(biāo)函數(shù)線沿著增大(或減?。┓较蚱叫幸苿?dòng),與 可行域相交且有最大(或最小)目標(biāo)函數(shù)值的頂點(diǎn),即為最優(yōu)值。,2020/7/15,.,30,圖解法,max Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8 s.t. X1 + 1.9X2 10.2 X1 - 1.9X2 -3.8 X1 ,X2 0,例1.11 用圖解法求解線性規(guī)劃問(wèn)題,2020/7/15,.,31,圖解法,x1,x2,o,X1 - 1.9X2 = 3.8(),X1 + 1.9X2

13、= 3.8(),X1 - 1.9X2 = -3.8 (),X1 + 1.9X2 = 10.2(),4 = 2X1 + X2,20 = 2X1 + X2,17.2 = 2X1 + X2,11 = 2X1 + X2,Lo: 0 = 2X1 + X2,(7.6,2),D,max Z,min Z,此點(diǎn)是唯一最優(yōu)解, 且最優(yōu)目標(biāo)函數(shù)值 max Z=17.2,可行域,max Z = 2X1 + X2,2020/7/15,.,32,圖解法,max Z=3X1+5.7X2,x1,x2,o,X1 - 1.9X2 = 3.8 (),X1 + 1.9X2 = 3.8(),X1 - 1.9X2 = -3.8(),X1

14、 + 1.9X2 = 10.2 (),(7.6,2),D,L0: 0=3X1+5.7X2,max Z,(3.8,4),34.2 = 3X1+5.7X2,藍(lán)色線段上的所有點(diǎn)都是最 優(yōu)解這種情形為有無(wú)窮多最 優(yōu)解,但是最優(yōu)目標(biāo)函數(shù)值 max Z=34.2是唯一的。,可行域,2020/7/15,.,33,圖解法,min Z=5X1+4X2,x1,x2,o,X1 - 1.9X2 = 3.8 (),X1 + 1.9X2 = 3.8(),X1 + 1.9X2 = 10.2 (),D,L0: 0=5X1+4X2,max Z,min Z,8=5X1+4X2,43=5X1+4X2,(0,2),可行域,此點(diǎn)是唯一

15、最優(yōu)解,2020/7/15,.,34,圖解法,2,4,6,x1,x2,2,4,6,無(wú)界解(無(wú)最優(yōu)解),max Z=x1+2x2,例1.12,x1+x2=4(),x1+3x2=6(),3x1+x2=6(),max Z,min Z,x1,x2,O,10,20,30,40,10,20,30,40,50,50,無(wú)可行解(即無(wú)最優(yōu)解),max Z=3x1+4x2,例1.13,2020/7/15,.,36,由圖解法得到的啟示,(1) 線性規(guī)劃問(wèn)題解的情況:唯一最優(yōu)解;無(wú)窮多最優(yōu)解;無(wú)界解;無(wú)可行解,(3) 最優(yōu)解或最優(yōu)解之一一定是在凸集的某個(gè)頂點(diǎn),(2) 線性規(guī)劃問(wèn)題的可行域是凸集,(4) 解題思路是,先

16、找出凸集的任一頂點(diǎn),計(jì)算其目標(biāo)函數(shù)值,再與周?chē)旤c(diǎn)的目標(biāo)函數(shù)值比較,如不是最大,繼續(xù)比較,直到找出最大為止。,圖解法,2020/7/15,.,37,圖解法,學(xué)習(xí)要點(diǎn): 1. 通過(guò)圖解法了解線性規(guī)劃有幾種解的形式 (唯一最優(yōu)解;無(wú)窮多最優(yōu)解;無(wú)界解;無(wú)可行解) 2. 作圖的關(guān)鍵有三點(diǎn): (1) 可行解區(qū)域要畫(huà)正確 (2) 目標(biāo)函數(shù)增大(或減小)的方向不能畫(huà)錯(cuò) (3) 目標(biāo)函數(shù)的直線怎樣平行移動(dòng),2020/7/15,.,38,連接幾何形體中任意兩點(diǎn)的線段仍完全在該幾何形體之中。 有限個(gè)凸集的交集仍然是凸集。,單純形法基本原理,2020/7/15,.,39,單純形法基本原理,凸集:如果集合C中任意兩

17、個(gè)點(diǎn)X1、X2,其連線上的所有點(diǎn)也都是集合C中的點(diǎn),稱(chēng)C為凸集。,頂點(diǎn):如果凸集C中不存在任何兩個(gè)不同的點(diǎn)X1,X2,使X成為這兩個(gè)點(diǎn)連線上的一個(gè)點(diǎn),2020/7/15,.,40,單純形法基本原理,定理1:若線性規(guī)劃問(wèn)題存在可行解,則該問(wèn)題的可行域是凸集。 定理2:線性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)可行域(凸集)的頂點(diǎn)。 定理3:若問(wèn)題存在最優(yōu)解,一定存在一個(gè)基可行解是最優(yōu)解。(或在某個(gè)頂點(diǎn)取得),2020/7/15,.,41,單純形法的計(jì)算步驟,單純形法的思路,找出一個(gè)初始基可行解,是否最優(yōu),轉(zhuǎn)移到另一個(gè)基可行解 (找出更大的目標(biāo)函數(shù)值),最優(yōu)解,是,否,循 環(huán),核心是:變量迭代,結(jié)束,單純形舉例

18、.ppt,2020/7/15,.,42,單純形法的計(jì)算步驟,例1.12 用單純形法求下列線性規(guī)劃的最優(yōu)解,解:1)將問(wèn)題化為標(biāo)準(zhǔn)型,加入松馳變量x3、x4則標(biāo)準(zhǔn)型為:,2020/7/15,.,43,單純形法的計(jì)算步驟,2)求出線性規(guī)劃的初始基可行解,列出初始單純形表。,檢驗(yàn)數(shù),2020/7/15,.,44,單純形法的計(jì)算步驟,3)進(jìn)行最優(yōu)性檢驗(yàn),如果表中所有檢驗(yàn)數(shù) ,則表中的基可行解就是問(wèn)題的最優(yōu)解,計(jì)算停止。否則繼續(xù)下一步。,4)從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)值更大的基可行解,列出新的單純形表,確定換入基的變量。 一般選擇最大的一個(gè)檢驗(yàn)數(shù),即: ,其對(duì)應(yīng)的xk作為換入變量。 確定換出變量。根

19、據(jù)下式計(jì)算并選擇 ,選最小的對(duì)應(yīng)基變量作為換出變量。,2020/7/15,.,45,單純形法的計(jì)算步驟,用換入變量xk替換基變量中的換出變量,得到一個(gè)新的基。對(duì)應(yīng)新的基可以找出一個(gè)新的基可行解,并相應(yīng)地可以畫(huà)出一個(gè)新的單純形表。 5)重復(fù)3)、4)步直到計(jì)算結(jié)束為止。,2020/7/15,.,46,單純形法的計(jì)算步驟,入基,bi /ai2,ai20,40,10,出基,將3化為1,5/3,1,18,0,1/3,0,1/3,10,1,1/3,30,30,0,5/3,0,4/3,乘以1/3后得到,1,0,3/5,1/5,18,0,1,1/5,2/5,4,0,0,1,1,2020/7/15,.,47,

20、單純形法的計(jì)算步驟,例1.13 用單純形法求解,解:將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式:,不難看出x4、x5可作為初始基變量,列單純形表計(jì)算。,2020/7/15,.,48,單純形法的計(jì)算步驟,20,x2,2,1/3,1,5,0,1,20,75,3,0,17,1,3,1/3,0,9,0,2,25,60,x1,1,1,0,17/3,1/3,1,25,0,1,28/9,-1/9,2/3,35/3,0,0,-98/9,-1/9,-7/3,2020/7/15,.,49,變成標(biāo)準(zhǔn)型,單純形法的計(jì)算步驟,例1.14 用單純形法求解,2020/7/15,.,50,約束方程的系數(shù)矩陣,為基變量,為非基變量,I 為單位矩陣

21、且線性獨(dú)立,單純形法的計(jì)算步驟,2020/7/15,.,51,2020/7/15,.,52,2020/7/15,.,53,2020/7/15,.,54,單純形法的計(jì)算步驟,學(xué)習(xí)要點(diǎn): 1. 線性規(guī)劃解的概念以及3個(gè)基本定理 2. 熟練掌握線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)化 3.熟練掌握單純形法的解題思路及求解步驟,2020/7/15,.,55,單純形法的進(jìn)一步討論人工變量法,人工變量法: 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣,很容易確定一組基可行解。在實(shí)際問(wèn)題中有些模型并不含有單位矩陣,為了得到一組基向量和初基可行解,在約束條件的等式左端加一組虛擬變量,得到一組基變量。這種人為加的變量稱(chēng)為人工變量,構(gòu)成的

22、可行基稱(chēng)為人工基,用大M法或兩階段法求解,這種用人工變量作橋梁的求解方法稱(chēng)為人工變量法。,2020/7/15,.,56,單純形法的進(jìn)一步討論人工變量法,例1.10 用大M法解下列線性規(guī)劃,解:首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式,系數(shù)矩陣中不存在單位矩陣,無(wú)法建立初始單純形表。,2020/7/15,.,57,單純形法的進(jìn)一步討論人工變量法,故人為添加兩個(gè)單位向量,得到人工變量單純形法數(shù)學(xué)模型:,其中:M是一個(gè)很大的抽象的數(shù),不需要給出具體的數(shù)值,可以理解為它能大于給定的任何一個(gè)確定數(shù)值;再用前面介紹的單純形法求解該模型,計(jì)算結(jié)果見(jiàn)下表。,2020/7/15,.,58,單純形法的進(jìn)一步討論人工變量法,20

23、20/7/15,.,59,單純形法的進(jìn)一步討論人工變量法,例1.11 用大M法解下列線性規(guī)劃,解:首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式,系數(shù)矩陣中不存在單位矩陣,無(wú)法建立初始單純形表。,2020/7/15,.,60,單純形法的進(jìn)一步討論人工變量法,故人為添加兩個(gè)單位向量,得到人工變量單純形法數(shù)學(xué)模型:,其中:M是一個(gè)很大的抽象的數(shù),不需要給出具體的數(shù)值,可以理解為它能大于給定的任何一個(gè)確定數(shù)值;再用前面介紹的單純形法求解該模型,計(jì)算結(jié)果見(jiàn)下表。,2020/7/15,.,61,單純形法的進(jìn)一步討論人工變量法,2020/7/15,.,62,單純形法的進(jìn)一步討論人工變量法,2020/7/15,.,63,單純形

24、法的進(jìn)一步討論,通過(guò)大法或兩階段法求初始的基本可行解。但是如果在大法的最優(yōu)單純形表的基變量中仍含有人工變量,那么該線性規(guī)劃就不存在可行解。,無(wú)可行解,2020/7/15,.,64,C,-3 -2 -1 0 0 0 -M -M,CB,XB,b,x1 x2 x3 x4 x5 x6 x7 x8,0 -M -M,x4 x7 x8,6 4 3,1 1 1 1 0 0 0 0 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1,6/1 - 3/1,Z,-7M,-6-4M,-15-M,-3+M -2+M -1-2M 0 -M -M 0 0,0 -M -2,x4 x7 x2,3 4 3,1

25、 0 2 1 0 1 0 -1 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1,3/1 4/1 -,Z,Z,-3+M 0 -3-M 0 -M -2 0 2-M,-3 -M -2,x1 x7 x2,3 1 3,1 0 2 1 0 1 0 -1 0 0 -3 -1 -1 -1 1 1 0 1 -1 0 0 -1 0 1,0 0 3-3M 3-M -M 1-M 0 -1,例,單純形法的進(jìn)一步討論,運(yùn)算到檢驗(yàn)數(shù)全負(fù)為止,仍含有人工變量,無(wú)可行解。,2020/7/15,.,65,單純形法的進(jìn)一步討論,無(wú)可行解是指原規(guī)劃不存在可行解,從幾何的角度解釋是指 線性規(guī)劃問(wèn)題的可行域?yàn)榭占?/p>

26、; 無(wú)界解則是指線性規(guī)劃問(wèn)題存在可行解,但是可行解的目 標(biāo)函數(shù)達(dá)不到最優(yōu)值,即目標(biāo)函數(shù)在可行域內(nèi)趨于無(wú)窮大。 判別方法:無(wú)界解判定定理 在求解極大化的線性規(guī)劃問(wèn)題過(guò)程中,若某單純形表的檢驗(yàn) 行存在某個(gè)大于零的檢驗(yàn)數(shù),但是該檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量 的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零,則該線性規(guī)劃問(wèn)題 無(wú)界解,無(wú)界解,2020/7/15,.,66,因 但 所以原問(wèn)題無(wú)界解,單純形法的進(jìn)一步討論,2020/7/15,.,67,退化,即計(jì)算出的 (用于確定換出變量)存在有兩個(gè)以上相同的最小比值,會(huì)造成下一次迭代中由一個(gè)或幾個(gè)基變量等于零,這就是退化(會(huì)產(chǎn)生退化解)。 為避免出現(xiàn)計(jì)算的循環(huán),勃蘭特(Bl

27、and)提出一個(gè)簡(jiǎn)便有效的規(guī)則(攝動(dòng)法原理): 當(dāng)存在多個(gè) 時(shí),選下標(biāo)最小的非基變量為換入變量; (2) 當(dāng)值出現(xiàn)兩個(gè)以上相同的最小值時(shí),選下標(biāo)最小的基變量為換出變量。,單純形法的進(jìn)一步討論,2020/7/15,.,68,無(wú)窮多最優(yōu)解,若線性規(guī)劃問(wèn)題某個(gè)基本可行解所有的非基變量檢驗(yàn)數(shù)都小于等于零,但其中存在一個(gè)檢驗(yàn)數(shù)等于零,那么該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。 例:最優(yōu)表: 非基變量檢驗(yàn) 數(shù),所以有無(wú)窮多 最優(yōu)解。,單純形法的進(jìn)一步討論,2020/7/15,.,69,單純形法的進(jìn)一步討論,單純性法小結(jié):,2020/7/15,.,70,線性規(guī)劃模型的應(yīng)用,一般而言,一個(gè)經(jīng)濟(jì)、管理問(wèn)題凡是滿足以下條

28、件時(shí),才能建立線性規(guī)劃模型。,要求解問(wèn)題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來(lái)反映,且為線性函數(shù) 存在著多種方案 要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的,這些約束可用線性等式或不等式描述,2020/7/15,.,71,線性規(guī)劃模型的應(yīng)用,常見(jiàn)問(wèn)題,合理利用線材問(wèn)題:如何下料使用材最少。 配料問(wèn)題:在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)。 投資問(wèn)題:從投資項(xiàng)目中選取方案,使投資回報(bào)最大。 產(chǎn)品生產(chǎn)計(jì)劃:合理利用人力、物力、財(cái)力等,使獲利最大。 勞動(dòng)力安排:用最少的勞動(dòng)力來(lái)滿足工作的需要。 運(yùn)輸問(wèn)題:如何制定調(diào)運(yùn)方案,使總運(yùn)費(fèi)最小。,2020/7/15,.,72,線性規(guī)劃模型的應(yīng)用,(1)設(shè)立決策變量; (2)明確約束條件并用決策變量的線性等式或不等式表示; (3)用決策變量的線性函數(shù)表示目標(biāo),并確定是求極大(Max)還是極?。∕in); (4)根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性。,建立線性規(guī)劃模型的過(guò)程可以分為四個(gè)步驟:,20

溫馨提示

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

最新文檔

評(píng)論

0/150

提交評(píng)論