運(yùn)籌學(xué)--運(yùn)籌學(xué)完整課件_第1頁
運(yùn)籌學(xué)--運(yùn)籌學(xué)完整課件_第2頁
運(yùn)籌學(xué)--運(yùn)籌學(xué)完整課件_第3頁
運(yùn)籌學(xué)--運(yùn)籌學(xué)完整課件_第4頁
運(yùn)籌學(xué)--運(yùn)籌學(xué)完整課件_第5頁
已閱讀5頁,還剩357頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡介

1、3/21/2022精選ppt3/21/2022精選ppt(1)運(yùn)籌學(xué)簡述)運(yùn)籌學(xué)簡述(2)運(yùn)籌學(xué)的主要內(nèi)容)運(yùn)籌學(xué)的主要內(nèi)容(3)本課程的教材及參考書)本課程的教材及參考書(4)本課程的特點(diǎn)和要求)本課程的特點(diǎn)和要求(5)本課程授課方式與考核)本課程授課方式與考核 (6)運(yùn)籌學(xué)在工商管理中的應(yīng)用)運(yùn)籌學(xué)在工商管理中的應(yīng)用本章主要內(nèi)容:本章主要內(nèi)容:Page 33/21/2022精選ppt運(yùn)籌學(xué)(運(yùn)籌學(xué)(Operations Research)系統(tǒng)工程的最重要的理論基礎(chǔ)之一,在美國有人把運(yùn)系統(tǒng)工程的最重要的理論基礎(chǔ)之一,在美國有人把運(yùn)籌學(xué)稱之為管理科學(xué)籌學(xué)稱之為管理科學(xué)(Management S

2、cience)。運(yùn)籌學(xué)所研究。運(yùn)籌學(xué)所研究的問題,可簡單地歸結(jié)為一句話:的問題,可簡單地歸結(jié)為一句話:“依照給定條件和目標(biāo),從眾多方案中選擇最佳方案依照給定條件和目標(biāo),從眾多方案中選擇最佳方案”故有人稱之為最優(yōu)化技術(shù)。故有人稱之為最優(yōu)化技術(shù)。Page 43/21/2022精選ppt運(yùn)籌學(xué)的歷史運(yùn)籌學(xué)的歷史“運(yùn)作研究運(yùn)作研究(Operational Research)小組小組”:解決復(fù)解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問題。例如:雜的戰(zhàn)略和戰(zhàn)術(shù)問題。例如:如何合理運(yùn)用雷達(dá)有效地對付德軍的空襲如何合理運(yùn)用雷達(dá)有效地對付德軍的空襲對商船如何進(jìn)行編隊(duì)護(hù)航,使船隊(duì)遭受德國潛對商船如何進(jìn)行編隊(duì)護(hù)航,使船隊(duì)遭受德國潛艇攻

3、擊時(shí)損失最少;艇攻擊時(shí)損失最少;1. 在各種情況下如何調(diào)整反潛深水炸彈的爆炸深在各種情況下如何調(diào)整反潛深水炸彈的爆炸深度,才能增加對德國潛艇的殺傷力等。度,才能增加對德國潛艇的殺傷力等。Page 53/21/2022精選ppt數(shù)學(xué)規(guī)劃(數(shù)學(xué)規(guī)劃(線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)、動(dòng)態(tài)規(guī)劃等)規(guī)劃等)圖論圖論存儲論存儲論排隊(duì)論排隊(duì)論對策論對策論排序與統(tǒng)籌方法排序與統(tǒng)籌方法決策分析決策分析Page 63/21/2022精選ppt選用教材選用教材 運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用胡運(yùn)權(quán)主編(第胡運(yùn)權(quán)主編(第5 5版)版) 高等教高等教育出版社育出版社參考教材參考教材運(yùn)籌

4、學(xué)教程運(yùn)籌學(xué)教程胡運(yùn)權(quán)主編胡運(yùn)權(quán)主編 (第(第2 2版)清華出版社版)清華出版社管理運(yùn)籌學(xué)管理運(yùn)籌學(xué)韓伯棠主編韓伯棠主編 (第(第2 2版)高等教育出版版)高等教育出版社社運(yùn)籌學(xué)運(yùn)籌學(xué)( (修訂版修訂版) ) 錢頌迪主編錢頌迪主編 清華出版社清華出版社Page 73/21/2022精選ppt先修課:先修課:高等數(shù)學(xué),基礎(chǔ)概率、線性代數(shù)高等數(shù)學(xué),基礎(chǔ)概率、線性代數(shù)特點(diǎn):特點(diǎn):系統(tǒng)整體優(yōu)化;多學(xué)科的配合;模型方法的應(yīng)用系統(tǒng)整體優(yōu)化;多學(xué)科的配合;模型方法的應(yīng)用運(yùn)籌學(xué)的研究的主要步驟:運(yùn)籌學(xué)的研究的主要步驟:真實(shí)系統(tǒng)真實(shí)系統(tǒng)系統(tǒng)分析系統(tǒng)分析問題描述問題描述模型建立模型建立與修改與修改模型求解模型求解

5、與檢驗(yàn)與檢驗(yàn)結(jié)果分析與結(jié)果分析與實(shí)施實(shí)施數(shù)據(jù)準(zhǔn)備數(shù)據(jù)準(zhǔn)備Page 83/21/2022精選ppt學(xué)科總成績學(xué)科總成績平時(shí)成績平時(shí)成績(4040)課堂考勤課堂考勤(5050)平時(shí)作業(yè)平時(shí)作業(yè)(5050)期末成績期末成績(6060)講授為主,結(jié)合習(xí)題作業(yè)講授為主,結(jié)合習(xí)題作業(yè)Page 93/21/2022精選ppt運(yùn)籌學(xué)在工商管理中的應(yīng)用涉及幾個(gè)方面:運(yùn)籌學(xué)在工商管理中的應(yīng)用涉及幾個(gè)方面: 生產(chǎn)計(jì)劃生產(chǎn)計(jì)劃 運(yùn)輸問題運(yùn)輸問題 人事管理人事管理 庫存管理庫存管理 市場營銷市場營銷 財(cái)務(wù)和會計(jì)財(cái)務(wù)和會計(jì)1.另外,還應(yīng)用于設(shè)備維修、更新和可靠性分析,項(xiàng)目的選另外,還應(yīng)用于設(shè)備維修、更新和可靠性分析,項(xiàng)目

6、的選擇與評價(jià),工程優(yōu)化設(shè)計(jì)等。擇與評價(jià),工程優(yōu)化設(shè)計(jì)等。3/21/2022精選ppt LP的數(shù)學(xué)模型的數(shù)學(xué)模型 圖解法圖解法 單純形法單純形法 單純形法的進(jìn)一步討論人工變量法單純形法的進(jìn)一步討論人工變量法 LP模型的應(yīng)用模型的應(yīng)用Page 113/21/2022精選ppt1. 規(guī)劃問題規(guī)劃問題生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排,使人力、生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排,使人力、物力等各種資源得到充分利用,獲得最大的效益,物力等各種資源得到充分利用,獲得最大的效益,這就是規(guī)劃問題。這就是規(guī)劃問題。(1 1)當(dāng)任務(wù)或目標(biāo)確定后,如何統(tǒng)籌兼顧,合理安排,用)當(dāng)任務(wù)或目標(biāo)確定后,如何統(tǒng)籌兼顧,合

7、理安排,用最少的資源最少的資源 (如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等)(如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等)去完成確定的任務(wù)或目標(biāo)去完成確定的任務(wù)或目標(biāo)(2 2)在一定的資源條件限制下,如何組織安排生產(chǎn)獲得最)在一定的資源條件限制下,如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益(如產(chǎn)品量最多好的經(jīng)濟(jì)效益(如產(chǎn)品量最多 、利潤最大、利潤最大. .)Page 123/21/2022精選ppt例例1.1 如圖所示,如何截取如圖所示,如何截取x使鐵皮所圍成的容積最使鐵皮所圍成的容積最大?大? x xa a xxav 220 dxdv0)2()2()2(22 xaxxa6ax Page 133/21/2022

8、精選ppt例例1.2 某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分別要在別要在A、B、C、D、四種不同的設(shè)備上加工。按工、四種不同的設(shè)備上加工。按工藝資料規(guī)定,單件產(chǎn)品在不同設(shè)備上加工所需要的臺藝資料規(guī)定,單件產(chǎn)品在不同設(shè)備上加工所需要的臺時(shí)如下表所示,企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃,使時(shí)如下表所示,企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃,使企業(yè)總的利潤最大?企業(yè)總的利潤最大?Page 143/21/2022精選ppt解:設(shè)解:設(shè)x1、x2分別為甲、乙兩種產(chǎn)品的產(chǎn)量,則數(shù)學(xué)模型為:分別為甲、乙兩種產(chǎn)品的產(chǎn)量,則數(shù)學(xué)模型為:Page 153/21/2022精選pptPag

9、e 163/21/2022精選ppt00 )( )( (min) max12211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz)21(j 0 )21(i )( Z(min)max 11nxmbxaxcjnjijijnjjj簡寫為:簡寫為:Page 173/21/2022精選ppt) (21ncccC nxxX1 mjjjaaP1 mbbB1 0 )( (min) maxXBxpCXzjj其中:其中:Page 183/21/2022精選ppt mnmnaaaaA1111 0 )( (min) maxXBAXCXZ其中:其中:) (21ncccC n

10、xxX1 mbbB1Page 193/21/2022精選ppt3. 線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性規(guī)劃問題的標(biāo)準(zhǔn)形式minjxbxatsxcZjnjijijnjjj, 2 , 1, 2 , 1, 0.max11 特點(diǎn):特點(diǎn):(1) 目標(biāo)函數(shù)求最大值(有時(shí)求最小值)目標(biāo)函數(shù)求最大值(有時(shí)求最小值)(2) 約束條件都為等式方程,且右端常數(shù)項(xiàng)約束條件都為等式方程,且右端常數(shù)項(xiàng)bi都大于或等于零都大于或等于零(3) 決策變量決策變量xj為非負(fù)。為非負(fù)。Page 203/21/2022精選ppt 目標(biāo)函數(shù)的轉(zhuǎn)換目標(biāo)函數(shù)的轉(zhuǎn)換 如果是求極小值即如果是求極小值即 ,則可將目標(biāo)函數(shù)乘以,則可將目標(biāo)函數(shù)乘以(-1)

11、(-1),可化為求極大值問題??苫癁榍髽O大值問題。 jjxczmin也就是:令也就是:令 ,可得到上式。,可得到上式。zz jjxczzmax即即 若存在取值無約束的變量若存在取值無約束的變量 ,可令,可令 其中:其中:jxjjjxxx 0, jjxx 變量的變換變量的變換Page 213/21/2022精選ppt 約束方程的轉(zhuǎn)換:由不等式轉(zhuǎn)換為等式。約束方程的轉(zhuǎn)換:由不等式轉(zhuǎn)換為等式。ijijbxa0iniinjijxbxxa稱為松弛變量稱為松弛變量 ijijbxa0iniinjijxbxxa稱為剩余變量稱為剩余變量 變量變量 的變換的變換 可令可令 ,顯然,顯然0jxjjxx0 jxPag

12、e 223/21/2022精選ppt例例1.3 將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式 ,0,52324 7 532min321321321321321無約束xxxxxxxxxxxxxxxZ用用 替換替換 ,且,且 解解:()因?yàn)椋ǎ┮驗(yàn)閤3無符號要求無符號要求 ,即,即x3取正值也可取負(fù)值,標(biāo)準(zhǔn)取正值也可取負(fù)值,標(biāo)準(zhǔn)型中要求變量非負(fù),所以型中要求變量非負(fù),所以33xx 3x0,33 xxPage 233/21/2022精選ppt(2) 第一個(gè)約束條件是第一個(gè)約束條件是“”號,在號,在“”左端加入松馳變量左端加入松馳變量x4,x40,化為等式;化為等式;(3) 第二個(gè)約束

13、條件是第二個(gè)約束條件是“”號,在號,在“”左端減去剩余變量左端減去剩余變量x5,x50;(4) 第第3個(gè)約束方程右端常數(shù)項(xiàng)為個(gè)約束方程右端常數(shù)項(xiàng)為-5,方程兩邊同乘以,方程兩邊同乘以(-1),將右將右端常數(shù)項(xiàng)化為正數(shù);端常數(shù)項(xiàng)化為正數(shù); (5) 目標(biāo)函數(shù)是最小值,為了化為求最大值,令目標(biāo)函數(shù)是最小值,為了化為求最大值,令z=-z,得到得到max z=-z,即當(dāng),即當(dāng)z達(dá)到最小值時(shí)達(dá)到最小值時(shí)z達(dá)到最大值,反之亦然達(dá)到最大值,反之亦然;Page 243/21/2022精選ppt 0,5 )(252 )( 7 )(500)(32max54332133215332143321543321xxxxxx

14、xxxxxxxxxxxxxxxxxxxxZ標(biāo)準(zhǔn)形式如下:標(biāo)準(zhǔn)形式如下:Page 253/21/2022精選ppt4. 4. 線性規(guī)劃問題的解線性規(guī)劃問題的解 )3(, 2 , 1, 0)2(), 2 , 1(.) 1 (max11njxmibxatsxcZjnjijijnjjj線性規(guī)劃問題線性規(guī)劃問題求解線性規(guī)劃問題,就是從滿足約束條件求解線性規(guī)劃問題,就是從滿足約束條件(2)、(3)的方程組的方程組中找出一個(gè)解,使目標(biāo)函數(shù)中找出一個(gè)解,使目標(biāo)函數(shù)(1)達(dá)到最大值。達(dá)到最大值。Page 263/21/2022精選ppt 可行解可行解:滿足約束條件:滿足約束條件、的解為可行解。所有可行解的解為可

15、行解。所有可行解的集合為可行域。的集合為可行域。 最優(yōu)解最優(yōu)解:使目標(biāo)函數(shù)達(dá)到最大值的可行解。:使目標(biāo)函數(shù)達(dá)到最大值的可行解。 基:基:設(shè)設(shè)A為約束條件為約束條件的的mn階系數(shù)矩陣階系數(shù)矩陣(m04010換換出出行行將將3化為化為15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到到103/51/518011/52/540011Page 463/21/2022精選ppt例例1.9 用單純形法求解用單純形法求解 02053115232.2max321321321321xxxxxxxxxtsxxxZ、解:將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式:解:將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式: 5

16、 , 2 , 1, 02053115232.2max53214321321jxxxxxxxxxtsxxxZj不難看出不難看出x4、x5可作為初始基變量,列單純形表計(jì)算??勺鳛槌跏蓟兞浚袉渭冃伪碛?jì)算。Page 473/21/2022精選pptj 201/3150120753017131/30902j 256011017/31/31250128/9-1/92/335/300-98/9 -1/9 -7/3j Page 483/21/2022精選ppt學(xué)習(xí)要點(diǎn):學(xué)習(xí)要點(diǎn):1. 線性規(guī)劃解的概念以及線性規(guī)劃解的概念以及3個(gè)基本定理個(gè)基本定理2. 熟練掌握單純形法的解題思路及求解步驟熟練掌握單純形法的

17、解題思路及求解步驟Page 493/21/2022精選ppt人工變量法:人工變量法:前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣,很容前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣,很容易確定一組基可行解。在實(shí)際問題中有些模型并不含有單易確定一組基可行解。在實(shí)際問題中有些模型并不含有單位矩陣,為了得到一組基向量和初基可行解,在約束條件位矩陣,為了得到一組基向量和初基可行解,在約束條件的等式左端加一組虛擬變量,得到一組基變量。這種人為的等式左端加一組虛擬變量,得到一組基變量。這種人為加的變量稱為人工變量,構(gòu)成的可行基稱為人工基,用大加的變量稱為人工變量,構(gòu)成的可行基稱為人工基,用大MM法或兩階段法求解,這種用

18、人工變量作橋梁的求解方法法或兩階段法求解,這種用人工變量作橋梁的求解方法稱為人工變量法。稱為人工變量法。Page 503/21/2022精選ppt例例1.10 用大用大M法解下列線性規(guī)劃法解下列線性規(guī)劃 012210243423max321321321321321xxxxxxxxxxxxxxxZ、解:首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式解:首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式 5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj系數(shù)矩陣中不存在系數(shù)矩陣中不存在單位矩陣,無法建單位矩陣,無法建立初始單純形表。立初始單純形表。Page 513/21/20

19、22精選ppt故人為添加兩個(gè)單位向量,得到人工變量單純形法數(shù)學(xué)模型:故人為添加兩個(gè)單位向量,得到人工變量單純形法數(shù)學(xué)模型: 7 , 2 , 1, 012210243423max732153216432176321jxxxxxxxxxxxxxxMxMxxxxZj其中:其中:M是一個(gè)很大的抽象的數(shù),不需要給出具體的數(shù)值,是一個(gè)很大的抽象的數(shù),不需要給出具體的數(shù)值,可以理解為它能大于給定的任何一個(gè)確定數(shù)值;再用前面介可以理解為它能大于給定的任何一個(gè)確定數(shù)值;再用前面介紹的單純形法求解該模型,計(jì)算結(jié)果見下表。紹的單純形法求解該模型,計(jì)算結(jié)果見下表。 Page 523/21/2022精選pptj j j

20、 j Page 533/21/2022精選ppt解的判別:解的判別:1)唯一最優(yōu)解判別:最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零)唯一最優(yōu)解判別:最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零,則線則線 規(guī)劃具有唯一最優(yōu)解。規(guī)劃具有唯一最優(yōu)解。2)多重最優(yōu)解判別:最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零)多重最優(yōu)解判別:最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解(或無窮多最優(yōu)解)。則線則性規(guī)劃具有多重最優(yōu)解(或無窮多最優(yōu)解)。3)無界解判別:某個(gè))無界解判別:某個(gè)k0且且aik(i=1,2,m)則線性)則線性規(guī)劃具有無界解。規(guī)劃具有無界解。4)無可行解的判斷:當(dāng)用大)無可行解的判斷:當(dāng)用大M單純形法計(jì)算得

21、到最優(yōu)解并單純形法計(jì)算得到最優(yōu)解并且存在且存在Ri0時(shí),則表明原線性規(guī)劃無可行解。時(shí),則表明原線性規(guī)劃無可行解。5)退化解的判別:存在某個(gè)基變量為零的基本可行解。)退化解的判別:存在某個(gè)基變量為零的基本可行解。Page 543/21/2022精選ppt單純性法小結(jié)單純性法小結(jié):Page 553/21/2022精選ppt停止停止A Ajjjzc :求求0 j所所有有kj即即找找出出max)()0(0 jika對對任任一一)0( lklkiiaab 計(jì)計(jì)算算lkxx替替換換基基變變量量用用非非基基變變量量新新單單純純形形表表列列出出下下一一個(gè)個(gè)ax含有含有量中是否量中是否基變基變 0 j非非基基變

22、變量量的的有有某某個(gè)個(gè)最最優(yōu)優(yōu)解解一一唯唯 無無可可行行解解最優(yōu)解最優(yōu)解無窮多無窮多是是否否環(huán)環(huán)循循否否否否否否是是是是是是循環(huán)循環(huán)無無界界解解Page 563/21/2022精選ppt一般而言,一個(gè)經(jīng)濟(jì)、管理問題凡是滿足以一般而言,一個(gè)經(jīng)濟(jì)、管理問題凡是滿足以下條件時(shí),才能建立線性規(guī)劃模型。下條件時(shí),才能建立線性規(guī)劃模型。 要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映,且要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映,且為線性函數(shù)為線性函數(shù) 存在著多種方案存在著多種方案 要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的,這些約要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的,這些約束可用線性等式或不等式描述束可用線性等式或不等式描述

23、Page 573/21/2022精選ppt 人力資源分配問題人力資源分配問題例例1.11 某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員人數(shù)如下表所示:所需司機(jī)和乘務(wù)人員人數(shù)如下表所示:設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段開始時(shí)上班,并連續(xù)工作設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段開始時(shí)上班,并連續(xù)工作8小時(shí),問該公交線路應(yīng)怎樣安排司機(jī)和乘務(wù)人員,即能滿小時(shí),問該公交線路應(yīng)怎樣安排司機(jī)和乘務(wù)人員,即能滿足工作需要,又使配備司機(jī)和乘務(wù)人員的人數(shù)減少足工作需要,又使配備司機(jī)和乘務(wù)人員的人數(shù)減少?Page 583/21/2022精選ppt解:設(shè)解:設(shè)xi表示第表示第i班次時(shí)

24、開始上班的司機(jī)和乘務(wù)人員人數(shù)。班次時(shí)開始上班的司機(jī)和乘務(wù)人員人數(shù)。 0,302050607060.min654321655443322161654321xxxxxxxxxxxxxxxxxxtsxxxxxx此問題最優(yōu)解:此問題最優(yōu)解:x150, x220, x350, x40, x520, x610,一共需要司機(jī)和乘務(wù)員,一共需要司機(jī)和乘務(wù)員150人。人。Page 593/21/2022精選ppt2. 生產(chǎn)計(jì)劃問題生產(chǎn)計(jì)劃問題某廠生產(chǎn)某廠生產(chǎn)、三種產(chǎn)品,都分別經(jīng)三種產(chǎn)品,都分別經(jīng)A、B兩道工序加工。設(shè)兩道工序加工。設(shè)A工序可分別在設(shè)備工序可分別在設(shè)備A1和和A2上完上完成,有成,有B1、B2、B

25、3三種設(shè)備可用于完成三種設(shè)備可用于完成B工序。已工序。已知產(chǎn)品知產(chǎn)品可在可在A、B任何一種設(shè)備上加工;產(chǎn)品任何一種設(shè)備上加工;產(chǎn)品可可在任何規(guī)格的在任何規(guī)格的A設(shè)備上加工,但完成設(shè)備上加工,但完成B工序時(shí),只能工序時(shí),只能在在B1設(shè)備上加工;產(chǎn)品設(shè)備上加工;產(chǎn)品只能在只能在A2與與B2設(shè)備上加工。設(shè)備上加工。加工單位產(chǎn)品所需工序時(shí)間及其他各項(xiàng)數(shù)據(jù)如下表,加工單位產(chǎn)品所需工序時(shí)間及其他各項(xiàng)數(shù)據(jù)如下表,試安排最優(yōu)生產(chǎn)計(jì)劃,使該廠獲利最大。試安排最優(yōu)生產(chǎn)計(jì)劃,使該廠獲利最大。Page 603/21/2022精選pptPage 613/21/2022精選ppt解:設(shè)解:設(shè)xijk表示產(chǎn)品表示產(chǎn)品i在工

26、序在工序j的設(shè)備的設(shè)備k上加工的數(shù)量。約束條上加工的數(shù)量。約束條件有:件有:)(上加工的數(shù)量相等)上加工的數(shù)量相等),在工序在工序(產(chǎn)品(產(chǎn)品上加工的數(shù)量相等)上加工的數(shù)量相等),在工序在工序(產(chǎn)品(產(chǎn)品上加工的數(shù)量相等)上加工的數(shù)量相等),在工序在工序(產(chǎn)品(產(chǎn)品設(shè)備設(shè)備設(shè)備設(shè)備)(設(shè)備(設(shè)備)(設(shè)備(設(shè)備設(shè)備設(shè)備3 , 2 , 1; 2 , 1; 3 , 2 , 10BAIIIBAIIBAI)3B(40007)2B(70001141B4000862A100001297)1A(6000105322312221212211123122121112111123322122221121312212

27、112211111 kjixxxxxxxxxxxxxxxxxxxxxijkPage 623/21/2022精選ppt目標(biāo)是利潤最大化,即利潤的計(jì)算公式如下:目標(biāo)是利潤最大化,即利潤的計(jì)算公式如下: 5131)()(ii該該設(shè)設(shè)備備實(shí)實(shí)際際使使用用臺臺時(shí)時(shí)每每臺臺時(shí)時(shí)的的設(shè)設(shè)備備費(fèi)費(fèi)用用該該產(chǎn)產(chǎn)品品件件數(shù)數(shù)銷銷售售單單價(jià)價(jià)原原料料單單價(jià)價(jià)利利潤潤帶入數(shù)據(jù)整理得到:帶入數(shù)據(jù)整理得到:12332212222112131221221111211135. 023. 1448. 05 . 0375. 0915. 136. 115. 1775. 075. 0maxxxxxxxxxxx Page 633/21

28、/2022精選ppt因此該規(guī)劃問題的模型為:因此該規(guī)劃問題的模型為: )(3,2,1;2,1;3,2,104000770001144000861000012976000105.35.023.1448.05.0375.0915.136.115.1775.075.0max322312221212211123122121112111123322122221121312212112211111123322122221121312212211112111kjixxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxxijkPage 643/21/2022精選ppt3. 套裁下料問題套裁下料問題例

29、:現(xiàn)有一批某種型號的圓鋼長例:現(xiàn)有一批某種型號的圓鋼長8米,需要截取米,需要截取2.5米米長的毛坯長的毛坯100根,長根,長1.3米的毛坯米的毛坯200根。問如何才能根。問如何才能既滿足需要,又能使總的用料最少?既滿足需要,又能使總的用料最少?解:為了找到一個(gè)省料的套裁方案,必須先設(shè)計(jì)出較好的幾解:為了找到一個(gè)省料的套裁方案,必須先設(shè)計(jì)出較好的幾個(gè)下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格個(gè)下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格的圓鋼,以滿足對各種不同規(guī)格圓鋼的需要并達(dá)到省料的目的圓鋼,以滿足對各種不同規(guī)格圓鋼的需要并達(dá)到省料的目的,為此可以設(shè)計(jì)出的,為此可以設(shè)計(jì)出4種下料

30、方案以供套裁用。種下料方案以供套裁用。Page 653/21/2022精選ppt )4.3.2.1(020064210023min4323214321jxxxxxxxxxxxZj設(shè)按方案設(shè)按方案、下料的原材料根數(shù)分別為下料的原材料根數(shù)分別為xj (j=1,2,3,4),可列出下面的數(shù)學(xué)模型:,可列出下面的數(shù)學(xué)模型:Page 663/21/2022精選ppt4. 配料問題配料問題例:某人每天食用甲、乙兩種食物(如豬肉、雞蛋),例:某人每天食用甲、乙兩種食物(如豬肉、雞蛋),其資料如下:問兩種食物各食用多少,才能既滿足需其資料如下:問兩種食物各食用多少,才能既滿足需要、又使總費(fèi)用最???要、又使總費(fèi)

31、用最??? 2 1.5原料單價(jià)原料單價(jià)1.007.5010.00 0.1 0.15 1.7 0.75 1.10 1.30A1A2A3 最最 低低需要量需要量 甲甲 乙乙含量含量 食物食物成分成分Page 673/21/2022精選ppt解:設(shè)解:設(shè)Xj 表示表示Bj 種食物用量種食物用量 0,00.1030.110.150.775.070.100.115.010.05.12min2121212121xxxxxxxxxxZ3/21/2022精選ppt線性規(guī)劃的對偶模型線性規(guī)劃的對偶模型對偶性質(zhì)對偶性質(zhì)對偶問題的經(jīng)濟(jì)解釋影子價(jià)格對偶問題的經(jīng)濟(jì)解釋影子價(jià)格對偶單純形法對偶單純形法 Page 693/2

32、1/2022精選ppt設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙,生產(chǎn)中需設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙,生產(chǎn)中需4種設(shè)備按種設(shè)備按A,B,C,D順序加工,每件產(chǎn)品加工所需的機(jī)時(shí)數(shù)、每件產(chǎn)品的利潤順序加工,每件產(chǎn)品加工所需的機(jī)時(shí)數(shù)、每件產(chǎn)品的利潤值及每種設(shè)備的可利用機(jī)時(shí)數(shù)列于下表值及每種設(shè)備的可利用機(jī)時(shí)數(shù)列于下表 :產(chǎn)品數(shù)據(jù)表產(chǎn)品數(shù)據(jù)表問:充分利用設(shè)備機(jī)時(shí),工廠應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能問:充分利用設(shè)備機(jī)時(shí),工廠應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能獲得最大利潤?獲得最大利潤?1. Page 703/21/2022精選ppt解:設(shè)甲、乙型產(chǎn)品各生產(chǎn)解:設(shè)甲、乙型產(chǎn)品各生產(chǎn)x1及及x2件,則數(shù)學(xué)模型為:件,則數(shù)學(xué)模型為

33、: 0,124164821222.32max2121212121xxxxxxxxtsxxz反過來問:若廠長決定不生產(chǎn)甲和乙型產(chǎn)品,決定出租機(jī)器反過來問:若廠長決定不生產(chǎn)甲和乙型產(chǎn)品,決定出租機(jī)器用于接受外加工,只收加工費(fèi),那么種機(jī)器的機(jī)時(shí)如何定用于接受外加工,只收加工費(fèi),那么種機(jī)器的機(jī)時(shí)如何定價(jià)才是最佳決策?價(jià)才是最佳決策?Page 713/21/2022精選ppt在市場競爭的時(shí)代,廠長的最佳決策顯然應(yīng)符合兩條:在市場競爭的時(shí)代,廠長的最佳決策顯然應(yīng)符合兩條: (1)不吃虧原則。即機(jī)時(shí)定價(jià)所賺利潤不能低于加工甲、乙型)不吃虧原則。即機(jī)時(shí)定價(jià)所賺利潤不能低于加工甲、乙型產(chǎn)品所獲利潤。由此原則,便

34、構(gòu)成了新規(guī)劃的不等式約束條件。產(chǎn)品所獲利潤。由此原則,便構(gòu)成了新規(guī)劃的不等式約束條件。 (2)競爭性原則。即在上述不吃虧原則下,盡量降低機(jī)時(shí)總收)競爭性原則。即在上述不吃虧原則下,盡量降低機(jī)時(shí)總收費(fèi),以便爭取更多用戶。費(fèi),以便爭取更多用戶。設(shè)設(shè)A、B、C、D設(shè)備的機(jī)時(shí)價(jià)分別為設(shè)備的機(jī)時(shí)價(jià)分別為y1、y2、y3、y4,則新的線,則新的線性規(guī)劃數(shù)學(xué)模型為:性規(guī)劃數(shù)學(xué)模型為: 0,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyyPage 723/21/2022精選ppt把同種問題的兩種提法所獲得的數(shù)學(xué)模型用表把同種問題的兩種提法所獲得的數(shù)學(xué)

35、模型用表2表示,將會發(fā)表示,將會發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象。現(xiàn)一個(gè)有趣的現(xiàn)象。原問題與對偶問題對比表原問題與對偶問題對比表Page 733/21/2022精選ppt2. 0,124164821222.32max2121212121xxxxxxxxtsxxz 0,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyy原問題原問題(對偶問題)(對偶問題)對偶問題對偶問題(原問題)(原問題)Page 743/21/2022精選ppt(1)對稱形式)對稱形式特點(diǎn):目標(biāo)函數(shù)求極大值時(shí),所有約束條件為特點(diǎn):目標(biāo)函數(shù)求極大值時(shí),所有約束條件為號,變號,變量非負(fù)量

36、非負(fù);目標(biāo)函數(shù)求極小值時(shí),所有約束條件為目標(biāo)函數(shù)求極小值時(shí),所有約束條件為號,變量非號,變量非負(fù)負(fù). 0XbAX CXmaxZ :P 0YCYA TTbYWDTmin:已知已知P,寫出,寫出DPage 753/21/2022精選ppt例例2.1 寫出線性規(guī)劃問題的對偶問題寫出線性規(guī)劃問題的對偶問題 0,5643 7 32 532432max321321321321321xxxxxxxxxxxxxxxZ解:首先將原問題變形為對稱形式解:首先將原問題變形為對稱形式 0,5 64 3 7 32532432max32132132132321xxxxxxxxxxxxxxxZPage 763/21/202

37、2精選ppt 0,4675343232 532min 321321321321321yyyyyyyyyyyyyyyW對對偶偶問問題題:Page 773/21/2022精選ppt(2) 非對稱型對偶問題非對稱型對偶問題若給出的線性規(guī)劃不是對稱形式,可以先化成對稱形式若給出的線性規(guī)劃不是對稱形式,可以先化成對稱形式再寫對偶問題。也可直接按教材表再寫對偶問題。也可直接按教材表2-2中的對應(yīng)關(guān)系寫出非對中的對應(yīng)關(guān)系寫出非對稱形式的對偶問題。稱形式的對偶問題。Page 783/21/2022精選pptPage 793/21/2022精選ppt例例2.2 寫出下列線性規(guī)劃問題的對偶問題寫出下列線性規(guī)劃問題

38、的對偶問題. 無無約約束束4321432142143214321, 0, 06 43 247 23 523 4 532maxxxxxxxxxxxxxxxxxxxxZ解:原問題的對偶問題為解:原問題的對偶問題為 無無約約束束32132131321321321,0,01 72 54 3332 2234 645minyyyyyyyyyyyyyyyyyWPage 803/21/2022精選ppt例例2.3 分別求解下列分別求解下列2個(gè)互為對偶關(guān)系的線性規(guī)劃問題個(gè)互為對偶關(guān)系的線性規(guī)劃問題 052426155.2max5214213221jxxxxxxxxxtsxxz 012526.52415min53

39、21432321iyyyyyyyytsyyyw分別用單純形法求解上述分別用單純形法求解上述2 2個(gè)規(guī)劃問題,得到最終單純形表如個(gè)規(guī)劃問題,得到最終單純形表如下表:下表:Page 813/21/2022精選pptj j 原問原問題最題最優(yōu)表優(yōu)表對偶對偶問題問題最優(yōu)最優(yōu)表表Page 823/21/2022精選ppt在單純形表中,原問題的松弛變量對應(yīng)在單純形表中,原問題的松弛變量對應(yīng)對偶問題的變量,對偶問題的剩余變量對應(yīng)原對偶問題的變量,對偶問題的剩余變量對應(yīng)原問題的變量。問題的變量。Page 833/21/2022精選ppt性質(zhì)性質(zhì)1 1 對稱性定理對稱性定理:對偶問題的對偶是原問題:對偶問題的對

40、偶是原問題 min W= Y bs.t. YA C Y 0max Z=C Xs.t. AXb X 0Page 843/21/2022精選ppt性質(zhì)性質(zhì)2 2 弱對偶原理弱對偶原理( (弱對偶性弱對偶性) ):設(shè)設(shè) 和和 分別是問題分別是問題(P)(P)和和(D)(D)的可行解,則必有的可行解,則必有0X0Y njmiiijjbyxcbYCX1100即即:推論推論1: 原問題任一可行解的目標(biāo)函數(shù)值是其對偶問題目標(biāo)函數(shù)值原問題任一可行解的目標(biāo)函數(shù)值是其對偶問題目標(biāo)函數(shù)值的下屆;反之,對偶問題任意可行解的目標(biāo)函數(shù)值是其原問題目的下屆;反之,對偶問題任意可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。標(biāo)

41、函數(shù)值的上界。推論推論2: 在一對對偶問題(在一對對偶問題(P)和()和(D)中,若其中一個(gè)問題可行但)中,若其中一個(gè)問題可行但目標(biāo)函數(shù)無界,則另一個(gè)問題無可行解;目標(biāo)函數(shù)無界,則另一個(gè)問題無可行解;反之不成立反之不成立。這也是對這也是對偶問題的無界性。偶問題的無界性。Page 853/21/2022精選ppt推論推論3 3:在一對對偶問題(在一對對偶問題(P)和()和(D)中,若一個(gè)可行(如)中,若一個(gè)可行(如P),而另一個(gè)不可行(如),而另一個(gè)不可行(如D),則該可行的問題目標(biāo)函數(shù)),則該可行的問題目標(biāo)函數(shù)值無界。值無界。性質(zhì)性質(zhì)3 最優(yōu)性定理最優(yōu)性定理:如果如果 是原問題的可行解,是原問

42、題的可行解, 是其對偶是其對偶問題的可行解,并且問題的可行解,并且:0X0Ywz:00即BYCX則則 是原問題的最優(yōu)解,是原問題的最優(yōu)解, 是其對偶問題的最優(yōu)解。是其對偶問題的最優(yōu)解。0X0YPage 863/21/2022精選ppt性質(zhì)性質(zhì)4 強(qiáng)對偶性強(qiáng)對偶性:若原問題及其對偶問題均具有可行解,則若原問題及其對偶問題均具有可行解,則兩者均具有最優(yōu)解,且它們最優(yōu)解的目標(biāo)函數(shù)值相等。兩者均具有最優(yōu)解,且它們最優(yōu)解的目標(biāo)函數(shù)值相等。還可推出另一結(jié)論:若(還可推出另一結(jié)論:若(LP)與()與(DP)都有可行解,則兩者)都有可行解,則兩者都有最優(yōu)解,若一個(gè)問題無最優(yōu)解,則另一問題也無最優(yōu)解。都有最優(yōu)解

43、,若一個(gè)問題無最優(yōu)解,則另一問題也無最優(yōu)解。性質(zhì)性質(zhì)5 互補(bǔ)松弛性互補(bǔ)松弛性:設(shè)設(shè)X0和和Y0分別是分別是P問題問題 和和 D問題問題 的可行的可行解,則它們分別是最優(yōu)解的充要條件是:解,則它們分別是最優(yōu)解的充要條件是: 000ss0XYXY其中:其中:Xs、Ys為松弛變量為松弛變量Page 873/21/2022精選ppt性質(zhì)性質(zhì)5的應(yīng)用:的應(yīng)用:該性質(zhì)給出了已知一個(gè)問題最優(yōu)解求另一個(gè)問題最優(yōu)該性質(zhì)給出了已知一個(gè)問題最優(yōu)解求另一個(gè)問題最優(yōu)解的方法,即已知解的方法,即已知Y求求X或已知或已知X求求Y 00ssXYXY互補(bǔ)松弛條件互補(bǔ)松弛條件由于變量都非負(fù),要使求和式等于零,則必定每一分量為零,

44、由于變量都非負(fù),要使求和式等于零,則必定每一分量為零,因而有下列關(guān)系:因而有下列關(guān)系:若若Y0,則,則Xs必為必為0;若;若X0,則,則Ys必為必為0利用上述關(guān)系,建立對偶問題(或原問題)的約束線性方程組,利用上述關(guān)系,建立對偶問題(或原問題)的約束線性方程組,方程組的解即為最優(yōu)解。方程組的解即為最優(yōu)解。Page 883/21/2022精選ppt例例2.4 已知線性規(guī)劃已知線性規(guī)劃 3 , 2 , 1, 0162210243max321321321jxxxxxxxxxxzj的最優(yōu)解是的最優(yōu)解是X=(6,2,0)T,求其對偶問題的最優(yōu)解求其對偶問題的最優(yōu)解Y。解:寫出原問題的對偶問題,即解:寫出

45、原問題的對偶問題,即 0,1422321610min2121212121yyyyyyyyyyw0,1422321610min5432152142132121yyyyyyyyyyyyyyyyw標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化Page 893/21/2022精選ppt設(shè)對偶問題最優(yōu)解為設(shè)對偶問題最優(yōu)解為Y(y1,y2),由互補(bǔ)松弛性定理可知,由互補(bǔ)松弛性定理可知,X和和 Y滿足:滿足:00 ssXYXY即:即:0),)(,(0),)(,(5421321543 TTxxyyxxxyyy因?yàn)橐驗(yàn)閄10,X20,所以對偶問題的第一、二個(gè)約束的松弛,所以對偶問題的第一、二個(gè)約束的松弛變量等于零,即變量等于零,即y30,y40

46、,帶入方程中:,帶入方程中: 422322121yyyy解此線性方程組得解此線性方程組得y1=1,y2=1,從而對偶問題的最優(yōu)解為:從而對偶問題的最優(yōu)解為:Y=(1,1),最優(yōu)值,最優(yōu)值w=26。Page 903/21/2022精選ppt例例2.5 已知線性規(guī)劃已知線性規(guī)劃 無約束無約束321321321321, 0, 06422minxxxxxxxxxxxxz的對偶問題的最優(yōu)解為的對偶問題的最優(yōu)解為Y=(0,-2),求原問題的最優(yōu)解。,求原問題的最優(yōu)解。解解: 對偶問題是對偶問題是 021264max2121212121yyyyyyyyyyw無約,無約,標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化0, 0,21264max

47、43212142132121yyyyyyyyyyyyyy無約Page 913/21/2022精選ppt設(shè)對偶問題最優(yōu)解為設(shè)對偶問題最優(yōu)解為X(x1,x2 ,x3)T ,由互補(bǔ)松弛性定理由互補(bǔ)松弛性定理可知,可知,X和和 Y滿足:滿足:0),)(,(0),)(,(5421321543 TTxxyyxxxyyy將將Y帶入由方程可知,帶入由方程可知,y3y50,y41。y2=-20 x50又又y4=10 x20將將x2,x5分別帶入原問題約束方程中,得:分別帶入原問題約束方程中,得: 643131xxxx解方程組得:解方程組得:x1=-5,x3=-1, 所以原問題的最優(yōu)解為所以原問題的最優(yōu)解為X=(

48、-5,0,-1),最優(yōu)值,最優(yōu)值z=-12Page 923/21/2022精選ppt原問題與對偶問題解的對應(yīng)關(guān)系小結(jié)原問題與對偶問題解的對應(yīng)關(guān)系小結(jié)Page 933/21/2022精選ppt判斷下列結(jié)論是否正確,如果不正確,應(yīng)該怎樣改正?判斷下列結(jié)論是否正確,如果不正確,應(yīng)該怎樣改正?1 1)任何線性規(guī)劃都存在一個(gè)對應(yīng)的對偶線性規(guī)劃)任何線性規(guī)劃都存在一個(gè)對應(yīng)的對偶線性規(guī)劃. .2 2)原問題第)原問題第ii個(gè)約束是個(gè)約束是“”約束,則對偶變量約束,則對偶變量y yii0.0.3 3)互為對偶問題,或者同時(shí)都有最優(yōu)解,或者同時(shí)都無最優(yōu)解)互為對偶問題,或者同時(shí)都有最優(yōu)解,或者同時(shí)都無最優(yōu)解.

49、.4 4)對偶問題有可行解,則原問題也有可行解)對偶問題有可行解,則原問題也有可行解. .5 5)原問題有多重解,對偶問題也有多重解)原問題有多重解,對偶問題也有多重解. .6 6)對偶問題有可行解,原問題無可行解,則對偶問題具有無界解)對偶問題有可行解,原問題無可行解,則對偶問題具有無界解. .7 7)原問題無最優(yōu)解,則對偶問題無可行解)原問題無最優(yōu)解,則對偶問題無可行解. .8 8)對偶問題不可行,原問題可能無界解)對偶問題不可行,原問題可能無界解. .9 9)原問題與對偶問題都可行,則都有最優(yōu)解)原問題與對偶問題都可行,則都有最優(yōu)解. .1010)原問題具有無界解,則對偶問題不可行)原問

50、題具有無界解,則對偶問題不可行. .1111)對偶問題具有無界解,則原問題無最優(yōu)解)對偶問題具有無界解,則原問題無最優(yōu)解. .1212)若)若X X* *、Y Y* *是原問題與對偶問題的最優(yōu)解,則是原問題與對偶問題的最優(yōu)解,則X X* *= =Y Y* *. .Page 943/21/2022精選ppt1. 影子價(jià)格的數(shù)學(xué)分析:影子價(jià)格的數(shù)學(xué)分析: 0 D 0 minmax YCYAXbAXPYbW CX Z定義:在一對定義:在一對 P 和和 D 中,若中,若 P 的某個(gè)約束條件的右端項(xiàng)常的某個(gè)約束條件的右端項(xiàng)常數(shù)數(shù)bi (第(第i種資源的擁有量)增加一個(gè)單位時(shí),所引起目標(biāo)種資源的擁有量)增

51、加一個(gè)單位時(shí),所引起目標(biāo)函數(shù)最優(yōu)值函數(shù)最優(yōu)值z* 的改變量稱為第的改變量稱為第 i 種資源的影子價(jià)格,其值等種資源的影子價(jià)格,其值等于于D問題中對偶變量問題中對偶變量yi*。由對偶問題得基本性質(zhì)可得:由對偶問題得基本性質(zhì)可得: miiinjjjybxcz11Page 953/21/2022精選ppt2. 影子價(jià)格的經(jīng)濟(jì)意義影子價(jià)格的經(jīng)濟(jì)意義1)影子價(jià)格是一種邊際價(jià)格)影子價(jià)格是一種邊際價(jià)格在其它條件不變的情況下,單位資源數(shù)量的變化所引在其它條件不變的情況下,單位資源數(shù)量的變化所引起的目標(biāo)函數(shù)最優(yōu)值的變化。即對偶變量起的目標(biāo)函數(shù)最優(yōu)值的變化。即對偶變量yi 就是第就是第 i 種資源種資源的影子價(jià)

52、格。即:的影子價(jià)格。即: )2 , 1(*miybZii Page 963/21/2022精選ppt2)影子價(jià)格是一種機(jī)會成本)影子價(jià)格是一種機(jī)會成本影子價(jià)格是在資源最優(yōu)利用條件下對單位資源的估價(jià),影子價(jià)格是在資源最優(yōu)利用條件下對單位資源的估價(jià),這種估價(jià)不是資源實(shí)際的市場價(jià)格。因此,從另一個(gè)角度說,這種估價(jià)不是資源實(shí)際的市場價(jià)格。因此,從另一個(gè)角度說,它是一種機(jī)會成本。它是一種機(jī)會成本。若第若第i 種資源的單位市場價(jià)格為種資源的單位市場價(jià)格為mi ,則有當(dāng),則有當(dāng)yi* mi 時(shí),企業(yè)愿意時(shí),企業(yè)愿意購進(jìn)這種資源,單位純利為購進(jìn)這種資源,單位純利為yi*mi ,則有利可圖;如果,則有利可圖;如

53、果yi* mi 則購進(jìn)資源則購進(jìn)資源i,可獲單位純利,可獲單位純利yi*mi 若若yi* mi則轉(zhuǎn)讓資源則轉(zhuǎn)讓資源i ,可獲單位純利,可獲單位純利miyiPage 973/21/2022精選ppt3)影子價(jià)格在資源利用中的應(yīng)用)影子價(jià)格在資源利用中的應(yīng)用根據(jù)對偶理論的互補(bǔ)松弛性定理根據(jù)對偶理論的互補(bǔ)松弛性定理:Y*Xs=0 , YsX*=0表明生產(chǎn)過程中如果某種資源表明生產(chǎn)過程中如果某種資源bi未得到充分利用時(shí),該種資未得到充分利用時(shí),該種資源的影子價(jià)格為源的影子價(jià)格為0;若當(dāng)資源資源的影子價(jià)格不為;若當(dāng)資源資源的影子價(jià)格不為0時(shí),表明時(shí),表明該種資源在生產(chǎn)中已耗費(fèi)完。該種資源在生產(chǎn)中已耗費(fèi)完

54、。Page 983/21/2022精選ppt4)影子價(jià)格對單純形表計(jì)算的解釋)影子價(jià)格對單純形表計(jì)算的解釋單純形表中的檢驗(yàn)數(shù)單純形表中的檢驗(yàn)數(shù)miiijjjBjjyacPBCc11其中其中c cj j表示第表示第j j種產(chǎn)品的價(jià)格種產(chǎn)品的價(jià)格; ; 表示生產(chǎn)該種產(chǎn)品所表示生產(chǎn)該種產(chǎn)品所消耗的各項(xiàng)資源的影子價(jià)格的總和消耗的各項(xiàng)資源的影子價(jià)格的總和, ,即產(chǎn)品的隱含成本。即產(chǎn)品的隱含成本。 miiijya1當(dāng)產(chǎn)值大于隱含成本時(shí),即當(dāng)產(chǎn)值大于隱含成本時(shí),即 ,表明生產(chǎn)該項(xiàng)產(chǎn)品有,表明生產(chǎn)該項(xiàng)產(chǎn)品有利,可在計(jì)劃中安排;否則利,可在計(jì)劃中安排;否則 ,用這些資源生產(chǎn)別的,用這些資源生產(chǎn)別的產(chǎn)品更有利,不

55、在生產(chǎn)中安排該產(chǎn)品。產(chǎn)品更有利,不在生產(chǎn)中安排該產(chǎn)品。0 j 0 j Page 993/21/2022精選ppt 對偶單純形法是求解線性規(guī)劃的另一個(gè)基本方法。它對偶單純形法是求解線性規(guī)劃的另一個(gè)基本方法。它是根據(jù)對偶原理和單純形法原理而設(shè)計(jì)出來的,因此稱為是根據(jù)對偶原理和單純形法原理而設(shè)計(jì)出來的,因此稱為對偶單純形法。不要簡單理解為是求解對偶問題的單純形對偶單純形法。不要簡單理解為是求解對偶問題的單純形法。法。 找出一個(gè)對偶問題的可行基,保持對偶問題為可行解的找出一個(gè)對偶問題的可行基,保持對偶問題為可行解的條件下,判斷條件下,判斷XB是否可行(是否可行(XB為非負(fù)),若否,通過變換基為非負(fù)),

56、若否,通過變換基解,直到找到原問題基可行解(即解,直到找到原問題基可行解(即XB為非負(fù)),這時(shí)原問題為非負(fù)),這時(shí)原問題與對偶問題同時(shí)達(dá)到可行解,由定理與對偶問題同時(shí)達(dá)到可行解,由定理4可得最優(yōu)解。可得最優(yōu)解。Page 1003/21/2022精選ppt找出一個(gè)找出一個(gè)DP的可行基的可行基LP是否可行是否可行(XB 0)保持保持DP為可行解情況下轉(zhuǎn)移到為可行解情況下轉(zhuǎn)移到LP的另一個(gè)基本解的另一個(gè)基本解最優(yōu)解最優(yōu)解是是否否循循環(huán)環(huán)結(jié)束結(jié)束Page 1013/21/2022精選ppt例例2.9 用對偶單純形法求解:用對偶單純形法求解: )3.2.1(0145 1232102215129min32

57、1321321321jxxxxxxxxxxxxxZj解解:(1)將模型轉(zhuǎn)化為求最大化問題,約束方程化為等式求將模型轉(zhuǎn)化為求最大化問題,約束方程化為等式求出一組基本解,因?yàn)閷ε紗栴}可行,即全部檢驗(yàn)數(shù)出一組基本解,因?yàn)閷ε紗栴}可行,即全部檢驗(yàn)數(shù)0(求(求max問題)。問題)。Page 1023/21/2022精選ppt 014 5 12 3210 2215129max61632153214321321xxxxxxxxxxxxxxxxZiPage 1033/21/2022精選pptiij j Page 1043/21/2022精選pptj 原問題的最優(yōu)解為:原問題的最優(yōu)解為:X*=(2 , 2 ,

58、2 , 0 , 0 , 0),),Z* =72 其對偶問題的最優(yōu)解為:其對偶問題的最優(yōu)解為:Y*= (1/3 , 3 , 7/3),),W*= 72Page 1053/21/2022精選ppt 對偶單純形法應(yīng)注意的問題:對偶單純形法應(yīng)注意的問題: 用對偶單純形法求解線性規(guī)劃是一種求解方法,而不是去求對偶用對偶單純形法求解線性規(guī)劃是一種求解方法,而不是去求對偶問題的最優(yōu)解問題的最優(yōu)解 初始表中一定要滿足對偶問題可行,也就是說檢驗(yàn)數(shù)滿足最優(yōu)判初始表中一定要滿足對偶問題可行,也就是說檢驗(yàn)數(shù)滿足最優(yōu)判別準(zhǔn)則別準(zhǔn)則 最小比值中最小比值中 的絕對值是使得比值非負(fù),在極小化問題的絕對值是使得比值非負(fù),在極小

59、化問題 j j00,分母分母a aij ij0 0 這時(shí)必須取絕對值。在極大化問題中,這時(shí)必須取絕對值。在極大化問題中, j j00,分母,分母a aij ij00, 總滿足非負(fù),這時(shí)絕對值符號不起作用,可以去掉。如總滿足非負(fù),這時(shí)絕對值符號不起作用,可以去掉。如在本例中將目標(biāo)函數(shù)寫成在本例中將目標(biāo)函數(shù)寫成ijja這里這里 j j 0 0在求在求 k k時(shí)就可以不帶絕對值符號。時(shí)就可以不帶絕對值符號。32134maxxxxz ijja Page 1063/21/2022精選ppt 對偶單純形法與普通單純形法的換基順序不一樣,普通單純形法對偶單純形法與普通單純形法的換基順序不一樣,普通單純形法是

60、先確定進(jìn)基變量后確定出基變量,對偶單純形法是先確定出基變是先確定進(jìn)基變量后確定出基變量,對偶單純形法是先確定出基變量后確定進(jìn)基變量;量后確定進(jìn)基變量; 普通單純形法的最小比值是普通單純形法的最小比值是 其目的是保證下一其目的是保證下一個(gè)原問題的基本解可行,對偶單純形法的最小比值是個(gè)原問題的基本解可行,對偶單純形法的最小比值是 0minikikiiaab其目的是保證下一個(gè)對偶問題的基本解可行其目的是保證下一個(gè)對偶問題的基本解可行 0|minljljjjaa 對偶單純形法在確定出基變量時(shí),若不遵循對偶單純形法在確定出基變量時(shí),若不遵循 規(guī)則,任選一個(gè)小于零的規(guī)則,任選一個(gè)小于零的b bii對應(yīng)的基

溫馨提示

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

評論

0/150

提交評論