線性規(guī)劃圖解法教案課件

1、線性規(guī)劃圖解法 1832和1911年法國數(shù)學(xué)家 J. B. J.傅里葉和 C.瓦萊普森分都分別獨(dú)立地提出線性規(guī)劃的想法，但未引起注意。 1939年，前蘇聯(lián)數(shù)學(xué)家康托洛維奇用線性規(guī)劃模型研究提高組織和生產(chǎn)效率問題 1947年，Dantzig提出求解線性規(guī)劃的單純形法 1950-1956年，主要研究線性規(guī)劃的對偶理論 1951年美國經(jīng)濟(jì)學(xué)家T.C.庫普曼斯把線性規(guī)劃應(yīng)用到經(jīng)濟(jì)領(lǐng)域，為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟(jì)學(xué)獎。 1958年，發(fā)表整數(shù)規(guī)劃的割平面法 1960年，Dantzig和Wolfe研究成功分解算法，奠定了大規(guī)模線性規(guī)劃問題理論和算法的基礎(chǔ)。一、線性規(guī)劃發(fā)展概況第1頁/共44頁

2、線性規(guī)劃的研究成果還直接推動了其他數(shù)學(xué)規(guī)劃問題包括整數(shù)規(guī)劃、隨機(jī)規(guī)劃和非線性規(guī)劃的算法研究。由于數(shù)字電子計算機(jī)的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個變量的線性規(guī)劃問題。 1979年，Khachiyan，1984年，Karmarkaa研究成功線性規(guī)劃的多項(xiàng)式算法。用卡馬卡方法求解線性規(guī)劃問題在變量個數(shù)為5000時只要單純形法所用時間的1/50。 第2頁/共44頁二、線性規(guī)劃研究解決的主要問題 實(shí)際上，上述兩類問題是一個問題的兩個不同的方面，都是求問題的最優(yōu)解（ max 或 min ）。 另一類是當(dāng)一項(xiàng)任務(wù)確定以后，研究如何統(tǒng)籌安排，才能使

3、完成任務(wù)所耗費(fèi)的資源量為最少。一類是已有一定數(shù)量的資源（人力、物質(zhì)、時間等），研究如何充分合理地使用它們，才能使完成的任務(wù)量為最大。線性規(guī)劃在工商管理中應(yīng)用有著廣泛的用處，可以用來解決諸如：人力資源分配問題、生產(chǎn)計劃問題、下料配料、投資問題（見第4章）以及運(yùn)輸問題（第7章）等。實(shí)際上遠(yuǎn)不止這些具體問題。但從一般意義上解決得問題有兩類：第3頁/共44頁三、LP解決問題的一般思路5、模型求解與解的調(diào)適。（獲得最優(yōu)方案一組決策變量的取值）。1、對問題進(jìn)行系統(tǒng)分析,搞清決策什么和決策目標(biāo)是什么？2、明確是哪些因素（人為可控的，決策變量）影響決策目標(biāo)（大小變化），確定決策變量對目標(biāo)（函數(shù)）影響系數(shù)，且與

4、目標(biāo)函數(shù)是否呈線形關(guān)系。3、哪些資源約束（或需求約束）條件制約著目標(biāo)（最大或最?。?。決策變量對這些資源（或需求）的單位消耗（單位產(chǎn)出）是多少？，即要獲得資源總量和投入產(chǎn)出系數(shù)。4、建立線形規(guī)劃數(shù)學(xué)模型。6、方案實(shí)施與調(diào)整。第4頁/共44頁2.1 LP問題的提出及其數(shù)學(xué)模型一、例示問題提出例2.1-1 某廠在計劃期內(nèi)安排生產(chǎn)兩種產(chǎn)品，生產(chǎn)所需資源限制及單位產(chǎn)品原料消耗由下表給給出 利潤 50 100問：應(yīng)如何安排生產(chǎn)計劃才能使 總利潤最大？ 甲乙資源限制設(shè)備11300臺時原料A21400kg原料B01250kg解：確定決策變量：設(shè)產(chǎn)品甲乙的產(chǎn)量分別為 ： x1、x22.建立目標(biāo)函數(shù)：設(shè)總利潤為z

5、，本例是： max z = 50 x1 + 100 x23.考慮約束條件： x1 + x2 300 2x1 + x2 400 x2 250 x1， x20第5頁/共44頁目標(biāo)函數(shù) ：max z = 50 x1 + 100 x2x1 + x2 300 2x1 + x2 400 x2 250 x1， x20滿足 約束條件：4.得到本問題的數(shù)學(xué)模型：第6頁/共44頁例2.1-2 某廠生產(chǎn)兩種產(chǎn)品，下表給出了單位產(chǎn)品所需資源及單位產(chǎn)品利潤 問：應(yīng)如何安排生產(chǎn)計劃，才能使 總利潤最大？ 解：1.決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量分 別為 x1、x22.目標(biāo)函數(shù)：設(shè)利潤為z，則有： max z = 2 x1

6、+ 3 x23.約束條件： x1 + 2x2 8 4x1 16 4x2 12 x1， x20第7頁/共44頁例2.1-3 某廠生產(chǎn)三種藥物，這些藥物可從四種不同的原料中提取。下表給出了單位原料可提取藥物的量（有效單位數(shù)）要求：生產(chǎn)A種藥物至少160單位；B種藥物恰好200單位，C種藥物不超過180單位，且使原料總成本最小。解：1.決策變量：設(shè)四種原料的使用 量分別為： x1、x2 、x3 、x42.目標(biāo)函數(shù)：設(shè)總成本為z，則有： min z = 5 x1 + 6 x2 + 7 x3 + 8 x43.約束條件： x1 + 2x2 + x3 + x4 160 2x1 +4 x3 +2 x4 160

7、 3x1 x2 +x3 +2 x4 180 x1、x2 、x3 、x40 藥物原料ABC單位成本（元噸）甲1235乙2016丙1417丁1228第8頁/共44頁二、LP問題一般模型1.決策變量： X = (x1,x2,.,xn)T2.目標(biāo)函數(shù)：max(minz) = c1 x1 + c2 x2 + . + cnxn3.約束條件： a11x1 + a12 x2 +.+ a1n xn (=) b1 a21x1 + a22 x2 +.+ a2n xn (=) b2 am1x1 + am2 x2 +.+ amn xn (=) bm x1,x2,xn0第9頁/共44頁三、LP模型特點(diǎn)1、 都用一組決策變

8、量X = (x1,x2,xn)T表示某一方案，且決策變量 取值非負(fù)； 滿足以上三個條件的數(shù)學(xué)模型稱為線性規(guī)劃數(shù)學(xué)模型或LP模型2 、都有一個要達(dá)到的目標(biāo)，并且目標(biāo)要求可以表示成決策變量的線 性函數(shù)；3、 都有一組約束條件，這些約束條件可以用決策變量的線性等式或 線性不等 式來表示。第10頁/共44頁LP模型的其它表達(dá)形式簡約形式矩陣形式?jīng)Q策變量常數(shù)項(xiàng)系數(shù)矩陣價值系數(shù)其中：第11頁/共44頁四、線性規(guī)劃數(shù)學(xué)模型的建立（一）建模條件1 優(yōu)化條件：問題所要達(dá)到的目標(biāo)能用線型函數(shù)描述，且能夠用極值 （max 或 min）來表示；2 限定條件：達(dá)到目標(biāo)受到一定的限制，且這些限制能夠用決策變量的 線性等式

9、或線性不等式表示；3 選擇條件：有多種可選擇的方案供決策者選擇，以便找出最優(yōu)方案。第12頁/共44頁（二）LP建模步驟1 確定決策變量并收集有關(guān)參數(shù)：即需要我們作出決策或選擇的量。一般情況下題目問什么，就把什么設(shè)置為決策變量。2 找列出所有限定條件：即決策變量受到的所有的資源與需求等約束；3 寫出目標(biāo)函數(shù)：即問題所要達(dá)到的目標(biāo)，并明確是max 還是 min。（三）建模案例例2.1-4 某廠生產(chǎn)A、B兩種產(chǎn)品，有關(guān)參數(shù)資料如下表所示，問如何組 織生產(chǎn)才能使效益最大：設(shè)：總利潤為Z；產(chǎn)品A、B產(chǎn)量為x1、x2，產(chǎn)品C的銷量為x3，報廢量為x4，則： max z = 4 x1 + 10 x2 + 3

10、 x3 2 x4 2 x1 + 3x2 12 3x1 + 4x2 24 4x2 -x3 - x4 = 0 x3 5 x1、x2 、x3 、x4 0第13頁/共44頁2.2 線性規(guī)劃圖解法一、解題步驟4 將最優(yōu)解代入目標(biāo)函數(shù)，求出最優(yōu)值。1 建立坐標(biāo)系并在直角平面坐標(biāo)系中畫出所有的約束等式，然后找出滿足所有約束條件的公共部分，稱為可行域，可行域中的點(diǎn)稱為可行解。2 標(biāo)出目標(biāo)函數(shù)值改善的方向。3 畫出目標(biāo)函數(shù)等值線，若求最大（?。┲担瑒t令目標(biāo)函數(shù)等值線沿目標(biāo)函數(shù)值增加（或減少）的方向平行移動，找與可行域最后相交的點(diǎn)，該點(diǎn)就是最優(yōu)解。第14頁/共44頁用圖解法求解下列線性規(guī)劃問題（例1）x1 + 2

11、x2 8 4x1 16 4x2 12 x1， x20 max z = 2 x1 + 3 x2最優(yōu)解：X*= (2,4)T最優(yōu)值：Z* = 14目標(biāo)函數(shù)等值線Z=0 x2x1第15頁/共44頁線性規(guī)劃的圖解（例2）max z=x1+3x2s.t. x1+ x26-x1+2x28x1 0, x20可行域目標(biāo)函數(shù)等值線最優(yōu)解64-860 x1x2第16頁/共44頁目標(biāo)函數(shù)：分別取決策變量為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里，圖上任意一點(diǎn)的坐標(biāo)代表了決策變量的一組值，每個約束條件都代表一個半平面。圖示如下： 用圖解法求解下列線性規(guī)劃問題第17頁/共44頁x2x1X20X2=0 x2x1X10X1=

12、0100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=400300200300400100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400圖2-1第18頁/共44頁x1x2z=20000=50 x1+100 x2圖2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE 綜上得到最優(yōu)解： 最優(yōu)目標(biāo)值: 第19頁/共44頁1、凸集 若連接n維點(diǎn)集P中任意兩點(diǎn)x（1）

13、， x（2），其線段仍在P內(nèi)，則稱P為凸集。即：x|x= x(1)+(1- ) x(2)， 01, x(1)P, x(2)P P,則稱P為凸集）2、 極點(diǎn) 若點(diǎn)x,且x不是P中任何線段的內(nèi)點(diǎn)，則稱點(diǎn)x為凸集P的極點(diǎn)。顯然多邊形的頂點(diǎn)都是極點(diǎn)，四面體的頂點(diǎn)也都是極點(diǎn)，而圓周上、球面上的每一個點(diǎn)都是極點(diǎn)，其它點(diǎn)都不是極點(diǎn)。二、關(guān)于凸集、極點(diǎn)的概念第20頁/共44頁三、線性規(guī)劃解的性質(zhì)定理1 線性規(guī)劃的可行域 R 是一個凸集，且有有限個極點(diǎn)。定理2 X是線性規(guī)劃可行域 R 頂點(diǎn)的充要條件是 X 線性規(guī)劃的基本可行解。定理3 若線性規(guī)劃有最優(yōu)解，則必有基本最優(yōu)解。定理4 若線性規(guī)劃在可行域的兩個頂點(diǎn)上

14、達(dá)到最優(yōu)，則在兩個頂點(diǎn)的連線 上也達(dá)到最優(yōu)。線性規(guī)劃的每一個基本可行解對應(yīng)凸集的每一個頂點(diǎn)。若線性規(guī)劃有最優(yōu)解，則一定在凸集的某個（些）頂點(diǎn)上達(dá)到最優(yōu)。若線性規(guī)劃在兩個頂點(diǎn)以上達(dá)到最優(yōu),則一定有無窮多個最優(yōu)解。最優(yōu)解一定是基本可行解，但基本可行解不一定是最優(yōu)解。第21頁/共44頁四、線性規(guī)劃問題求解可能出現(xiàn)的情況x1x2z=20000=50 x1+100 x2圖2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE則可行域?yàn)榭沼?，不存在滿足約束條件的解，當(dāng)然也就不存在最優(yōu)解了。 4、無可行解。如果例3再增加一個約束條件3

15、、無界解。即可行域延伸到無窮遠(yuǎn)，目標(biāo)函數(shù)值可以無窮大或無窮小。2、如果最優(yōu)解出現(xiàn)在兩個極點(diǎn)上，則會有無窮多個最優(yōu)解。1、如果LP有最優(yōu)解，則一定有一個可行域的極點(diǎn)對應(yīng)這個最優(yōu)解； 第22頁/共44頁五、LP解的有關(guān)概念及其關(guān)系1 可行解（ feasible solution ）：滿足線性規(guī)劃約束條件的解稱為可行解。（一）有關(guān)概念2 最優(yōu)解（optimal solution）：使線性規(guī)劃目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解稱為 最優(yōu)解。3 基本解（basic solution）：以線性規(guī)劃約束等式的系數(shù)矩陣A中任意m行m 列組成的mm滿秩子矩陣為基矩陣，與基矩陣相對應(yīng)的變量稱為基變量（basic varia

16、ble），其余變量稱為非基變量，若令非基變量為零，則可求得基變量的解（值），這個解稱為基本解。 4 基本可行解（basic feasible solution）： 滿足非負(fù)約束的基本解稱為基本可行解。若約束等式中有n個變量，m個約束，則基本解的個數(shù)第23頁/共44頁令非基變量 x10，x2 0則得：X (0, 0, 3, 1 )T基本解當(dāng)基變量為x2、x3，則非基變量為x1、x4令非基變量 x10，x4 0則得：X (0, 1, 5, 0 )T基本解基本可行解？ 是基本可行解？ x1 2x2 x3 3 2x1 x2 x4 1 x1,x2,x3,x40解：系數(shù)矩陣為：設(shè)基變量為x3、x4，則非基

17、變量為x1、x23）X (1/2, 1/2, 3/2, 1/2)T不是基本解可行解是基本可行解？例 討論下述約束方程的解第24頁/共44頁1 可行解與最優(yōu)解：最優(yōu)解一定是可行解，但可行解不一定是最優(yōu)解。（二）線性規(guī)劃解之間的關(guān)系基本解不一定是可行解，可行解也不一定是基本解。2 可行解與基本解：3 可行解與基本可行解：基本可行解一定是可行解，但可行解不一定是基本解。基本可行解一定是基本解，但基本解不一定是基本可行解。4 基本解與基本可行解：5 最優(yōu)解與基本解：最優(yōu)解不一定是基本解，基本解也不一定是最優(yōu)解。問題：最優(yōu)解與基本可行解？非可行解可行解基本可行解基本解第25頁/共44頁六、線性規(guī)劃模型的

18、標(biāo)準(zhǔn)形式及其標(biāo)準(zhǔn)化（一）線性規(guī)劃模型標(biāo)準(zhǔn)形式特點(diǎn) 1目標(biāo)最大化； 2約束為等式； 3決策變量均非負(fù)； 4右端項(xiàng)非負(fù)。 特點(diǎn)Max z = c1x1 + c2x2 + + cnxna11x1 + a12x2 + + a1nxn = b1a21x1 + a22x2 + + a2nxn = b2 . . .am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0s.t第26頁/共44頁 如果目標(biāo)函數(shù)為 Min該極小化問題與下面的極大化問題有相同的最優(yōu)解， 但必須注意，盡管以上兩個問題的最優(yōu)解相同，但它們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個符號，即： （二）線性規(guī)劃模型標(biāo)準(zhǔn)化問題

19、1、極小化目標(biāo)函數(shù)的問題：則令： z -f ，Min f Max z第27頁/共44頁2、約束條件不是等式的問題： 時，可以引進(jìn)一個新的變量 ，使它等于約束右邊與左邊之差（2）當(dāng)約束條件為類似地令 則有：則有：（1）當(dāng)約束條件為第28頁/共44頁3.右端項(xiàng)有負(fù)值的問題： 則把該等式約束兩端同時乘以-1，得到： 為了使約束方程由不等式成為等式而引進(jìn)的變量,當(dāng)不等式為“小于等于”時稱引進(jìn)的變量為“松弛變量”；當(dāng)不等式為“大于等于”時稱為“剩余變量”。如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時，必須對各個約束引進(jìn)不同的松弛變量或剩余變量。 在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個分量非負(fù)。當(dāng)某

20、一個右端項(xiàng)系數(shù)為負(fù)時，如 第29頁/共44頁4. 變量無符號限制的問題 在標(biāo)準(zhǔn)形式中，必須每一個變量均有非負(fù)約束。當(dāng)某一個變量xj 沒有非負(fù)約束時，可以令 xj = xj- xj” 其中 xj0，xj”0 即用兩個非負(fù)變量之差來表示一個無符號限制的變量，當(dāng)然xj的符號取決于xj和xj”的大小?？傊ㄟ^上述問題的處理，線性規(guī)劃模型的一般形式均可化為標(biāo)準(zhǔn)形式。第30頁/共44頁標(biāo)準(zhǔn)化例題1一般形式標(biāo)準(zhǔn)形式第31頁/共44頁標(biāo)準(zhǔn)化例題2第32頁/共44頁2.3靈敏度分析 靈敏度分析是建立數(shù)學(xué)模型和求得最優(yōu)解后，研究線性規(guī)劃的一個或多個參數(shù) ( )變化時，對最優(yōu)解產(chǎn)生的影響，或者這些參數(shù)在 一個多大范

21、圍內(nèi)變化時，原LP問題的最優(yōu)解不變的問題。 目標(biāo)函數(shù)中的系數(shù)的變化只影響目標(biāo)函數(shù)等值線的斜率，不影響可行域。所謂C的靈敏度分析是指，研究在目標(biāo)函數(shù)中其他的系數(shù)不變，只有一個系數(shù)在保持最優(yōu)解不變時該系數(shù)的取值范圍。 1目標(biāo)函數(shù)中的系數(shù) “C” 的靈敏度分析第33頁/共44頁一般情況：可將其寫成：目標(biāo)函數(shù)等值線的斜率為： 有：可使原最優(yōu)解仍是最優(yōu)解。 先假設(shè)產(chǎn)品乙的利潤100元不變，即：代入（*）并整理得： 考慮例1目標(biāo)函數(shù)為：x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400圖2-1要使最優(yōu)解不變，其變化必然在構(gòu)成極點(diǎn)的相交直線的斜率之間。對C1進(jìn)行靈敏度分析max

22、 z = 50 x1 + 100 x2x1 + x2 300 2x1 + x2 400 x2 250 x1， x20滿足第34頁/共44頁同樣：假設(shè)C1=50不變時，代入：有：-1 -（50/C2）0整理后得：50 C2 +即當(dāng)50 C2 +時原最優(yōu)解不變。第35頁/共44頁2 約束條件中右邊系數(shù)的靈敏度分析 當(dāng)約束條件中右邊系數(shù)變化時，線性規(guī)劃的可行域發(fā)生變化，可能引起的最優(yōu)解的變化，進(jìn)而了解當(dāng)其他約束不變時，某一約束條件的右端項(xiàng)每變化一個單位，使目標(biāo)函數(shù)值的改變量。由講義例1可知： （1）假設(shè)設(shè)備臺時增加10個臺時，即變?yōu)?10臺時，這時可行域擴(kuò)大，但最優(yōu)解所在的基點(diǎn)不變，得最優(yōu)解為：X1

23、=60， X2=250 x1x2x2=0 x1=0 x2=250 x1+x2=3102x1+x2=400圖2-1第36頁/共44頁（2）假設(shè)原料 A 增加10 千克時，即 變化為410，這時可行域擴(kuò)大，但最優(yōu)解仍為 和 約束方程的交點(diǎn) 。此變化對總利潤無影響，因此該約束條件的對偶價格為 0 。由于原最優(yōu)解沒有把原料 A 用盡，有50千克的剩余，因此增加10千克值增加了庫存，而不會增加利潤。 這時，即 變化后的總利潤 變化前的總利潤 = 增加的利潤 (5060+ 100250) (50 50+100 250) = 500 元， 即：每增加一個臺時的利潤為：500 / 10 = 50 元 說明在一

24、定范圍內(nèi)每增加（減少）1個臺時的設(shè)備能力就可增加（減少）50元利潤，稱為該約束條件的對偶價格。圖2-1x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=410第37頁/共44頁 在一定范圍內(nèi)，當(dāng)約束條件右邊常數(shù)增加1個單位時 （1）若約束條件的對偶價格大于0，則其最優(yōu)目標(biāo)函數(shù)值得到改善（變好）； （2）若約束條件的對偶價格小于0，則其最優(yōu)目標(biāo)函數(shù)值受到影響（變壞）； （3）若約束條件的對偶價格等于0，則最優(yōu)目標(biāo)函數(shù)值不變。作業(yè)布置： 1、P24 第3（2，3），第4題2、P25 第6、7題第38頁/共44頁原問題LP模型：Max z = 50 x1 + 100 x2 s

25、.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 02.4線性規(guī)劃的對偶問題最優(yōu)解為：x1=50 x2=250 ；max Z=27500對偶問題：不妨提出這樣的問題，如果該廠把設(shè)備（工時）和A、B原料租賃和轉(zhuǎn)讓出去，又要不比自己生產(chǎn)賺的少，該廠如何收取租金和轉(zhuǎn)讓費(fèi)？或者說設(shè)備租賃至少多少錢一個工時，原料A、B應(yīng)收多少錢一公斤？原問題：例2.1 某廠在計劃期內(nèi)安排生產(chǎn)兩種產(chǎn)品，生產(chǎn)所需資源限制及單位產(chǎn)品原料消耗由下表給給出甲乙資源限制設(shè)備11300臺時原料A21400kg原料B01250kg利潤50100第39頁/共44頁定價的原則是：既要能夠轉(zhuǎn)讓出去，又不比自己生產(chǎn)賺的總利潤少。不妨設(shè)： y1 ，y2 ，y3 分別為每個設(shè)備工時