線性規(guī)劃與圖解法

1、文理學(xué)院文理學(xué)院 姜華姜華2015-3Page 2辦公室：辦公室：1C2131C213手機(jī)：手機(jī)：1580197759315801977593郵箱：郵箱：（1）運(yùn)籌學(xué)簡(jiǎn)述）運(yùn)籌學(xué)簡(jiǎn)述（2）運(yùn)籌學(xué)的主要內(nèi)容）運(yùn)籌學(xué)的主要內(nèi)容（3）本課程的教材及參考書(shū)）本課程的教材及參考書(shū)本章主要內(nèi)容：本章主要內(nèi)容：Page 4運(yùn)籌學(xué)（運(yùn)籌學(xué)（Operations Research）系統(tǒng)工程的最重要的理論基礎(chǔ)之一，在美國(guó)有人把運(yùn)籌系統(tǒng)工程的最重要的理論基礎(chǔ)之一，在美國(guó)有人把運(yùn)籌學(xué)稱之為管理科學(xué)學(xué)稱之為管理科學(xué)(Management Science)。運(yùn)籌學(xué)所研究的。運(yùn)籌學(xué)所研究的問(wèn)題，可簡(jiǎn)單地歸結(jié)為一句話：?jiǎn)栴}，

2、可簡(jiǎn)單地歸結(jié)為一句話：“依照給定條件和目標(biāo)，從眾多方案中選擇最佳方案依照給定條件和目標(biāo)，從眾多方案中選擇最佳方案”故有人稱之為最優(yōu)化技術(shù)。故有人稱之為最優(yōu)化技術(shù)。Page 5運(yùn)籌學(xué)的歷史運(yùn)籌學(xué)的歷史“運(yùn)作研究運(yùn)作研究(Operational Research)小組小組”:解決復(fù)解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問(wèn)題。例如：雜的戰(zhàn)略和戰(zhàn)術(shù)問(wèn)題。例如：1. 如何合理運(yùn)用雷達(dá)有效地對(duì)付德軍德空襲如何合理運(yùn)用雷達(dá)有效地對(duì)付德軍德空襲2. 對(duì)商船如何進(jìn)行編隊(duì)護(hù)航，使船隊(duì)遭受德國(guó)潛對(duì)商船如何進(jìn)行編隊(duì)護(hù)航，使船隊(duì)遭受德國(guó)潛艇攻擊時(shí)損失最少；艇攻擊時(shí)損失最少；3. 在各種情況下如何調(diào)整反潛深水炸彈的爆炸深在各種情況下如何調(diào)

3、整反潛深水炸彈的爆炸深度，才能增加對(duì)德國(guó)潛艇的殺傷力等。度，才能增加對(duì)德國(guó)潛艇的殺傷力等。Page 6數(shù)學(xué)規(guī)劃（數(shù)學(xué)規(guī)劃（線性規(guī)劃、線性規(guī)劃、目標(biāo)規(guī)劃目標(biāo)規(guī)劃、整數(shù)規(guī)劃、動(dòng)態(tài)、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃等）規(guī)劃等）圖論圖論存儲(chǔ)論存儲(chǔ)論排隊(duì)論排隊(duì)論對(duì)策論對(duì)策論排序與統(tǒng)籌方法排序與統(tǒng)籌方法決策分析決策分析Page 7選用教材選用教材 運(yùn)籌學(xué)運(yùn)籌學(xué)( (本科版本科版) ) 清華大學(xué)出版社清華大學(xué)出版社參考教材參考教材運(yùn)籌學(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é)基礎(chǔ)及應(yīng)用運(yùn)

4、籌學(xué)基礎(chǔ)及應(yīng)用胡運(yùn)權(quán)主編胡運(yùn)權(quán)主編 哈工大出版哈工大出版先修課：先修課：高等數(shù)學(xué)，線性代數(shù)，基礎(chǔ)概率高等數(shù)學(xué)，線性代數(shù)，基礎(chǔ)概率 LP的數(shù)學(xué)模型的數(shù)學(xué)模型 圖解法圖解法 單純形法單純形法 單純形法的進(jìn)一步討論人工變量法單純形法的進(jìn)一步討論人工變量法 LP模型的應(yīng)用模型的應(yīng)用Page 91. 規(guī)劃問(wèn)題規(guī)劃問(wèn)題生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排，使人力、生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問(wèn)題。這就是規(guī)劃問(wèn)題。（1 1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用）當(dāng)任務(wù)或目標(biāo)確定后，如

5、何統(tǒng)籌兼顧，合理安排，用最少的資源最少的資源 （如資金、設(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)品量最多 、利潤(rùn)最大、利潤(rùn)最大. .）Page 10例例1.1 如圖所示，如何截取如圖所示，如何截取x使鐵皮所圍成的容積最使鐵皮所圍成的容積最大？大？ x xa a xxav 220 dxdv0)2()2()2(22 xaxxa6ax Page 11例例1.2 某企業(yè)計(jì)劃生產(chǎn)甲、乙

6、兩種產(chǎn)品。這些產(chǎn)品分某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分別要在別要在A、B、C、D、四種不同的設(shè)備上加工。按工、四種不同的設(shè)備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺(tái)藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺(tái)時(shí)如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使時(shí)如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使企業(yè)總的利潤(rùn)最大？企業(yè)總的利潤(rùn)最大？ 設(shè)設(shè) 備備產(chǎn)產(chǎn) 品品 A B C D利潤(rùn)（元）利潤(rùn)（元） 甲甲 2 1 4 0 2 乙乙 2 2 0 4 3 有有 效效 臺(tái)臺(tái) 時(shí)時(shí) 12 8 16 12Page 12解：設(shè)解：設(shè)x1、x2分別為甲、乙兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為：分別

7、為甲、乙兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為：Page 13Page 1400 )( )( (min) max12211112121112211 nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz)21(j 0 )21(i )( Z (min)max 11nxmbxaxcjnjijijnjjj 簡(jiǎn)寫(xiě)為：簡(jiǎn)寫(xiě)為：Page 15 mnmnaaaaA1111m ax (m in) () b0 ZC XA XX 其中：其中：) (21ncccC nxxX11mbbb Page 164. 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式minjxbxatsxcZjnjijijnjjj, 2 , 1

8、, 2 , 1, 0.max11 特點(diǎn)：特點(diǎn)：(1) 目標(biāo)函數(shù)求最大值目標(biāo)函數(shù)求最大值(2) 約束條件都為等式方程，且右端常數(shù)項(xiàng)約束條件都為等式方程，且右端常數(shù)項(xiàng)bi都大于或等于零都大于或等于零(3) 決策變量決策變量xj為非負(fù)。為非負(fù)。Page 17 目標(biāo)函數(shù)的轉(zhuǎn)換目標(biāo)函數(shù)的轉(zhuǎn)換 如果是求極小值即如果是求極小值即 ，則可將目標(biāo)函數(shù)乘以，則可將目標(biāo)函數(shù)乘以(- (-1)1)，可化為求極大值問(wèn)題。，可化為求極大值問(wèn)題。 jjxczmin也就是：令也就是：令 ，可得到上式。，可得到上式。zz maxjjzzc x 即即 1 1）若存在取值無(wú)約束的變量若存在取值無(wú)約束的變量 ，可令，可令 其中：其中

9、：jxjjjxxx 0, jjxx 變量的變換變量的變換Page 18 約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。 ijijbxa0 iniinjijxbxxa稱為松弛變量稱為松弛變量 ijijbxa0 iniinjijxbxxa稱為剩余變量稱為剩余變量2 2） 變量變量 的變換的變換 可令可令 ，顯然，顯然0 jxjjxx 0 jxPage 19例例1.3 將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式 ,0,52324 7 532min321321321321321無(wú)無(wú)約約束束xxxxxxxxxxxxxxxZ用用 替換替換 ，且，且 解解:（）因

10、為（）因?yàn)閤3無(wú)符號(hào)要求無(wú)符號(hào)要求 ，即，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以型中要求變量非負(fù)，所以33xx 3x0,33 xxPage 20(2) 第一個(gè)約束條件是第一個(gè)約束條件是“”號(hào)，在號(hào)，在“”左端加入松馳變量左端加入松馳變量x4，x40,化為等式；化為等式；(3) 第二個(gè)約束條件是第二個(gè)約束條件是“”號(hào)，在號(hào)，在“”左端減去剩余變量左端減去剩余變量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ù)是最小值，為了化為求最大

11、值，令目標(biāo)函數(shù)是最小值，為了化為求最大值，令z=-z,得到得到max z=-z，即當(dāng)，即當(dāng)z達(dá)到最小值時(shí)達(dá)到最小值時(shí)z達(dá)到最大值，反之亦然達(dá)到最大值，反之亦然;Page 21 0,5 )(252 )( 7 )(500)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ標(biāo)準(zhǔn)形式如下：標(biāo)準(zhǔn)形式如下：Page 225. 5. 線性規(guī)劃問(wèn)題的解線性規(guī)劃問(wèn)題的解 )3(, 2 , 1, 0)2(), 2 , 1(.) 1 (max11njxmibxatsxcZjnjijijnjjjLP問(wèn)題問(wèn)題求解線性規(guī)劃問(wèn)題，就是從滿足約束條件求解線性

12、規(guī)劃問(wèn)題，就是從滿足約束條件(2)、(3)的方程組的方程組中找出一個(gè)解，使目標(biāo)函數(shù)中找出一個(gè)解，使目標(biāo)函數(shù)(1)達(dá)到最大值。達(dá)到最大值。Page 23 可行解可行解：滿足約束條件、的解為可行解。所有可行解：滿足約束條件、的解為可行解。所有可行解的集合為的集合為可行域可行域。 最優(yōu)解最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。：使目標(biāo)函數(shù)達(dá)到最大值的可行解。Page 24線性規(guī)劃問(wèn)題的求解方法線性規(guī)劃問(wèn)題的求解方法一一 般般 有有兩種方法兩種方法圖圖 解解 法法單純形法單純形法兩個(gè)變量、直角坐標(biāo)兩個(gè)變量、直角坐標(biāo)三個(gè)變量、立體坐標(biāo)三個(gè)變量、立體坐標(biāo)適用于任意變量、但必需將適用于任意變量、但必需將一般形

13、式變成標(biāo)準(zhǔn)形式一般形式變成標(biāo)準(zhǔn)形式下面我們分析一下簡(jiǎn)單的情況下面我們分析一下簡(jiǎn)單的情況 只有兩個(gè)決策只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題，這時(shí)可以通過(guò)圖解的方法變量的線性規(guī)劃問(wèn)題，這時(shí)可以通過(guò)圖解的方法來(lái)求解。圖解法具有簡(jiǎn)單、直觀、便于初學(xué)者窺來(lái)求解。圖解法具有簡(jiǎn)單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點(diǎn)。探線性規(guī)劃基本原理和幾何意義等優(yōu)點(diǎn)。Page 25max Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8s.t. X1 + 1.9X2 10.2 X1 - 1.9X2 -3.8 X1 ，X2 0例例1.5 用圖解法求解線性規(guī)劃問(wèn)題用圖解法求解線性

14、規(guī)劃問(wèn)題Page 26x1x2oX1 - 1.9X2 = 3.8()X1 + 1.9X2 = 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）Dmax Zmin Z此點(diǎn)是唯一最優(yōu)解，此點(diǎn)是唯一最優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值且最優(yōu)目標(biāo)函數(shù)值 max Z=17.2可行域可行域max Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8s.t. X1 + 1.9X2 10.2

15、 X1 - 1.9X2 -3.8 X1 ，X2 0Page 27max Z=3X1+5.7X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()（7.6，2）DL0： 0=3X1+5.7X2 max Z（3.8，4）34.2 = 3X1+5.7X2 藍(lán)色線段上的所有點(diǎn)都是最藍(lán)色線段上的所有點(diǎn)都是最優(yōu)解這種情形為有無(wú)窮多最優(yōu)解這種情形為有無(wú)窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值max Z=34.2是唯一的。是唯一的。可行域可行域Page 28 0063463212121

16、21xxxxxxxx、246x1x2246無(wú)界解無(wú)界解( (無(wú)最優(yōu)解無(wú)最優(yōu)解) )max Z=x1+2x2例例1.6x1+x2=4()x1+3x2=6()3x1+x2=6() max Z min Zx1x2O10203040102030405050無(wú)可行解無(wú)可行解(即無(wú)最優(yōu)解即無(wú)最優(yōu)解)0,050305 .140221212121 xxxxxxxxmax Z=3x1+4x2例例1.7Page 30學(xué)習(xí)要點(diǎn)：學(xué)習(xí)要點(diǎn)：1. 通過(guò)圖解法了解線性規(guī)劃有幾種解的形式通過(guò)圖解法了解線性規(guī)劃有幾種解的形式（唯一最優(yōu)解；無(wú)窮多最優(yōu)解；無(wú)界解；無(wú)可行解）（唯一最優(yōu)解；無(wú)窮多最優(yōu)解；無(wú)界解；無(wú)可行解）2. 作圖的關(guān)鍵有三點(diǎn)：作圖的關(guān)鍵有三點(diǎn)： (1) 可行解區(qū)域要畫(huà)正確可行解區(qū)域要畫(huà)正確 (2) 目標(biāo)函數(shù)增加的方向不能畫(huà)錯(cuò)目標(biāo)函數(shù)增加的方向不能畫(huà)錯(cuò) (3) 目標(biāo)函數(shù)的直線怎樣平行移動(dòng)目標(biāo)函數(shù)的直線怎樣平行移動(dòng)Page 31LP問(wèn)題的解的特點(diǎn)問(wèn)題的解的特點(diǎn)1.若若LP問(wèn)題存在可行域，則其可行域一定為問(wèn)題存在可行域，則其可行域一定為凸集。凸集。凸集：如果集合凸集：如果集合C中任意兩個(gè)點(diǎn)中任意兩個(gè)點(diǎn)X1、X2，其連線上的所有點(diǎn)，其連線上的所有點(diǎn)也