第2章-線性規(guī)劃圖解法PPT課件

1、 例1.1 某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源?，F(xiàn)將有關(guān)數(shù)據(jù)列表如下： 試擬訂使總收入最大的生產(chǎn)方案。資源單耗 產(chǎn)品資源甲 乙資源限量煤電油9 44 5 3 10360200300單位產(chǎn)品價(jià)格 7 12第1頁/共36頁目標(biāo)函數(shù)：總收入，記為z, ,則 ，為體現(xiàn)對其追求極大化，在z 的前面冠以極大號Max；決策變量：甲、乙產(chǎn)品的計(jì)劃產(chǎn)量，記為 ；約束條件：分別來自資源煤、電、油限量的約束，和產(chǎn) 量非負(fù)的約束，表示為,xx121212129436045200. .310300,0 xxxxstxxx x+12712zxx=+第2頁/共36頁解：解：設(shè)安排甲、乙產(chǎn)量分別為 ,總收入

2、為 ，則模型為：21,xxz121212129436045200. .310300,0 xxxxstxxx x+12712Maxzxx=+第3頁/共36頁線性線性規(guī)劃模型的三要素規(guī)劃模型的三要素3.約束條件：為實(shí)現(xiàn)優(yōu)化目標(biāo)需受到的限制，用 決策變量的等式或不等式表示。1.決策變量：需決策的量，即待求的未知數(shù)；2.目標(biāo)函數(shù)：需優(yōu)化的量，即欲達(dá)的目標(biāo)，用決 策變量的表達(dá)式表示；第4頁/共36頁線性規(guī)劃模型的一般形式：線性規(guī)劃模型的一般形式：（以MAX型、 約束為例）決策變量：目標(biāo)函數(shù)：約束條件：11111111. .,0nnmmnnmna xa xbs taxaxbxx+11nnMaxzc xc

3、x=+nxx,1第5頁/共36頁則模型可表示為模型一般式的矩陣形式模型一般式的矩陣形式記. .0MaxzCXAXbstX=111(,) ,(,),(),(,)TTnnijm nmXxxCccAabbb=第6頁/共36頁回顧例回顧例1.11.1的模型的模型其中 表示決策變量的向量； 表示產(chǎn)品的價(jià)格向量； 表示資源限制向量； 表示產(chǎn)品對資源的單耗系數(shù)矩陣。第7頁/共36頁一般地一般地其中其中 稱為決策變量向量， 稱為價(jià)格系數(shù)向量, , 稱為技術(shù)系數(shù)矩陣, , 稱為資源限制向量。XCAb問題：為什么 A 稱為技術(shù)系數(shù)矩陣？. .0MaxzCXAXbstX=第8頁/共36頁二、線性規(guī)劃模型的圖解法 圖

4、解法是用畫圖的方式求解線性規(guī)劃的一種方法。它雖然只能用于解二維（兩個(gè)變量）的問題，但其主要作用并不在于求解，而是在于能夠直觀地說明線性規(guī)劃解的一些重要性質(zhì)。第9頁/共36頁2021-11-4例例1 用圖解法求解用圖解法求解 線性規(guī)劃問題線性規(guī)劃問題max Z = 50X1 + 100X2 X1 + X2 300 2 X1 + X2 400s.t. X2 250 X1 ，X2 0第10頁/共36頁2021-11-4（1）分別取決策變量 X1，X2 為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里，圖上任意一點(diǎn)的坐標(biāo)代表了決策變量的一組值，例1的每個(gè)約束條件都代表一個(gè)半平面。x2x1X20X2=0 x2x

5、1X10X1=0第11頁/共36頁2021-11-41212（2）對每個(gè)不等式（約束條件），先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。X1+X2300X1+X2=3001001002002X1+X24002X1+X2=400300200300400100200300 x1x1100200300 x2x2第12頁/共36頁2021-11-41313（3）把五個(gè)圖合并成一個(gè)圖，取各約束條件的公共部分，如圖2-1所示。100100X2250X2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400圖圖2-1x1x2第13頁/

6、共36頁2021-11-414（4）目標(biāo)函數(shù)Z=50X1+100X2，當(dāng)Z取某一固定值時(shí)得到一條直線，直線上的每一點(diǎn)都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動(dòng)等值線，當(dāng)移動(dòng)到B點(diǎn)時(shí)，z在可行域內(nèi)實(shí)現(xiàn)了最大化。A，B，C，D，E是可行域的頂點(diǎn)，對有限個(gè)約束條件則其可行域的頂點(diǎn)也是有限的。x1x2z=20000=50 x1+100 x2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE由圖可知：頂點(diǎn)B為最優(yōu)解。X1=50,X2=250Z=50 x50+250 x100=27500第14頁/共36頁（1）做約束的圖形 先

7、做非負(fù)約束的圖形； 再做資源約束的圖形。 以例1.1為例，其約束為01x2x9040501003040 各約束的公共部分即模型的約束，稱可行域。1. 圖解法的步驟121212129436045200.310300,0 xxxxstxxx x+第15頁/共36頁(2)做目標(biāo)的圖形01x2x做出相應(yīng)的二直線，便可看出增大的方向。7121424對于目標(biāo)函數(shù)便可做出相應(yīng)的二任給 Z 二不同的值，直線，用虛線表示。以例1.1為例，其目標(biāo)為分別令12712zxx=+84168zz=和11nnzc xc x=+第16頁/共36頁（3）求出最優(yōu)解 將目標(biāo)直線向使目標(biāo) 優(yōu)化的方向移，直至可行域的邊界為止，這時(shí)其

8、與可行域的“切”點(diǎn) 即最優(yōu)解。 如在例1.1中， 是可行域的一個(gè)角點(diǎn)， 經(jīng)求解交出 的二約束直線聯(lián)立的方程可解得z*X01x2x9040501003040*X*(20,24)TX =*X*X第17頁/共36頁 由圖解法的結(jié)果得到例1.1的最優(yōu)解 還可將其代入目標(biāo)函數(shù)求得相應(yīng)的最優(yōu)目標(biāo)值 。說明當(dāng)甲產(chǎn)量安排 20 個(gè)單位，乙產(chǎn)量安排 24 個(gè)單位時(shí)，可獲得最大的收入 428。*(20,24)TX =*428z =第18頁/共36頁2. 由圖解法得到線性規(guī)劃解的一些特性由圖解法得到線性規(guī)劃解的一些特性（1）線性規(guī)劃的約束集（即可行域）是一個(gè)凸多面體。 凸多面體:把多面體的任何一個(gè)面伸展成平面，如果

9、所有其他各面都在這個(gè)平面的同側(cè)，這樣的多面體就叫做凸多面體。 凸多面體的任何截面都是凸多邊形。第19頁/共36頁（2 2）線性規(guī)劃的最優(yōu)解（若存在的話）必能在可行域的角點(diǎn)（頂點(diǎn)）獲得。 因?yàn)椋蓤D解法可知，只有當(dāng)目標(biāo)直線平移到邊界時(shí)，才能使目標(biāo) z 達(dá)到最大限度的優(yōu)化。問題：本性質(zhì)有何重要意義？第20頁/共36頁本性質(zhì)重要意義：本性質(zhì)重要意義： 這樣，問題就轉(zhuǎn)化為這樣，問題就轉(zhuǎn)化為從有限多個(gè)角點(diǎn)中從有限多個(gè)角點(diǎn)中尋找最優(yōu)點(diǎn)尋找最優(yōu)點(diǎn)，使原來從所有可行解中去，使原來從所有可行解中去尋找最優(yōu)解的工作大大簡化尋找最優(yōu)解的工作大大簡化。線性規(guī)劃。線性規(guī)劃的的單純形解法單純形解法的依據(jù)的依據(jù)就是這兩個(gè)性

10、質(zhì)。就是這兩個(gè)性質(zhì)。第21頁/共36頁（3 3）線性規(guī)劃解的幾種情形 唯一最優(yōu)解 多重最優(yōu)解 無解 無有限最優(yōu)解（無界解）第22頁/共36頁 重要結(jié)論： 如果線性規(guī)劃有最優(yōu)解，則一定有一個(gè)可行域的頂點(diǎn)對應(yīng)一個(gè)最優(yōu)解； 無窮多個(gè)最優(yōu)解。 無界解。即可行域的范圍延伸到無窮遠(yuǎn)，目標(biāo)函數(shù)值可以無窮大或無窮小。一般來說，這說明模型有錯(cuò)，忽略了一些必要的約束條件； 無可行解。則可行域?yàn)榭沼颍淮嬖跐M足約束條件的解，當(dāng)然也就不存在最優(yōu)解了。第23頁/共36頁 小結(jié)線性規(guī)劃LP(linear programming)的定義： LP是在有限資源的條件下，合理分配和利用資源，以期取得最佳的經(jīng)濟(jì)效益的優(yōu)化方法。 L

11、P有一組有待決策的變量， 一個(gè)線性的目標(biāo)函數(shù)， 一組線性的約束條件， 目標(biāo)函數(shù)和約束方程都是線性的。第24頁/共36頁重要性： 要想在工農(nóng)業(yè)生產(chǎn)、交通運(yùn)輸、商業(yè)貿(mào)易等各方面提高效益，有兩種途徑：一是革新技術(shù)， 二是改進(jìn)生產(chǎn)組織與計(jì)劃，即合理安排有限的人力和物力資源，最合理地組織生產(chǎn)過程。 數(shù)學(xué)規(guī)劃能夠?yàn)楦玫嘏渲觅Y源、組織生產(chǎn)提供理論與方法，包括線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、多目標(biāo)規(guī)劃等很多分支。 其中線性規(guī)劃是在現(xiàn)代管理中運(yùn)用最廣、理論比較完善的一個(gè)部分。隨著電子計(jì)算機(jī)的發(fā)展，數(shù)學(xué)規(guī)劃在現(xiàn)代管理中的重要性日益明顯。 第25頁/共36頁線性規(guī)劃的標(biāo)準(zhǔn)化內(nèi)容之一：引入松馳變量（含義是資源的剩余

12、量） 例1.1 中引入 s1， s2， s3 模型化為 目標(biāo)函數(shù)：Max z = 7x1 + 12x2 + 0 s1 + 0 s2 + 0 s3 約束條件： 9 x1 + 4 x2 + s1 = 360 4x1 + 5x2 + s2 = 200 s.t. 3x1 + 10 x2 + s3 = 300 x1 , x2 , s1 , s2 , s3 0 對于最優(yōu)解 x1 =20 x2 = 24 ，s1 = 84 s2 =0 s3 = 0 說明：生產(chǎn)20單位甲產(chǎn)品和24單位乙產(chǎn)品將消耗完所有可能的電和油，但對煤則還剩余84個(gè)單位。第26頁/共36頁線性規(guī)劃的標(biāo)準(zhǔn)化 一般形式目標(biāo)函數(shù)： Max （Mi

13、n） z = c1 x1 + c2 x2 + + cn xn 約束條件： a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 s.t. am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0 標(biāo)準(zhǔn)形式目標(biāo)函數(shù)： Max z = c1 x1 + c2 x2 + + cn xn 約束條件： a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 s.t. am1 x1 + am2 x2 +

14、+ amn xn = bm x1 ，x2 ， ，xn 0，bi 0第27頁/共36頁 可以看出，線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)特點(diǎn)： 目標(biāo)最大化； 約束為等式； 決策變量均非負(fù)； 右端項(xiàng)非負(fù)。 對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式: :第28頁/共36頁1.極小化目標(biāo)函數(shù)的問題： 設(shè)目標(biāo)函數(shù)為 Min f = c1x1 + c2x2 + + cnxn (可以)令 z -f ， 則該極小化問題與下面的極大化問題有相同的最優(yōu)解，即 Max z = - c1x1 - c2x2 - - cnxn 但必須注意，盡管以上兩個(gè)問題的最優(yōu)解相同，但它們最優(yōu)解的目標(biāo)函數(shù)值卻

15、相差一個(gè)符號，即 Min f - Max z第29頁/共36頁2.約束條件不是等式的問題： 設(shè)約束條件為 ai1 x1+ai2 x2+ +ain xn bi 可以引進(jìn)一個(gè)新的變量s ，使它等于約束右邊與左邊之差 s=bi(ai1 x1 + ai2 x2 + + ain xn )顯然，s 也具有非負(fù)約束，即s0， 這時(shí)新的約束條件成為 ai1 x1+ai2 x2+ +ain xn+s = bi第30頁/共36頁 當(dāng)約束條件為 ai1 x1+ai2 x2+ +ain xn bi 時(shí)， 類似地令 s =(ai1 x1+ai2 x2+ +ain xn)- bi 顯然，s 也具有非負(fù)約束，即s0，這時(shí)新

16、的約束條件成為 ai1 x1+ai2 x2+ +ain xn-s = bi第31頁/共36頁 為了使約束由不等式成為等式而引進(jìn)的變量s，當(dāng)不等式為“小于等于”時(shí)稱為“松弛變量”；當(dāng)不等式為“大于等于”時(shí)稱為“剩余變量”。如果原問題中有若干個(gè)非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須對各個(gè)約束引進(jìn)不同的松弛變量。3.右端項(xiàng)有負(fù)值的問題： 在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個(gè)分量非負(fù)。當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí)，如 bi0，則把該等式約束兩端同時(shí)乘以-1，得到：1122.iiinnia xa xa xb-= -第32頁/共36頁例：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式 Min f = 2 x1 -3x2 + 4 x3 3 x1 + 4x2 - 5 x3 6 2 x1 + x3 8 s.t. x1 + x2 + x3 = -9 x1 , x2 , x3 0 解：首先,將目標(biāo)函數(shù)轉(zhuǎn)換成極大化： 令 z= -f = -2x1+3x2-4x3 其次考慮約束，有2個(gè)不等式約束，引進(jìn)松弛變量與剩余變量 x4，x5 0。 第三個(gè)約束條件的右端值為負(fù)，在等式兩邊同時(shí)乘-1。第33頁/共36頁通過以上變換，可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題： Max z = - 2x1 + 3 x2 -