武漢工程大學(xué) 運(yùn)籌學(xué)02-線性規(guī)劃的圖解法

《武漢工程大學(xué) 運(yùn)籌學(xué)02-線性規(guī)劃的圖解法》由會(huì)員分享，可在線閱讀，更多相關(guān)《武漢工程大學(xué) 運(yùn)籌學(xué)02-線性規(guī)劃的圖解法（30頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、2.1 線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型(1)線性規(guī)劃問(wèn)題建模線性規(guī)劃問(wèn)題建模例例1 1、生產(chǎn)組織與計(jì)劃問(wèn)題、生產(chǎn)組織與計(jì)劃問(wèn)題A,B A,B 各生產(chǎn)多少各生產(chǎn)多少,可獲最大利潤(rùn)可獲最大利潤(rùn)?可用資源可用資源設(shè)備設(shè)備原料原料1原料原料2A B1 22 10 1單位利潤(rùn)單位利潤(rùn)50 100300臺(tái)時(shí)臺(tái)時(shí)400kg250kg建立線性規(guī)劃模型的步驟：1）根據(jù)管理層的要求確定決策目標(biāo)和收集相關(guān)數(shù)據(jù)。2）確定要做出的決策，引入決策變量。3）確定對(duì)這些決策的約束條件和目標(biāo)函數(shù)。例例2 2 合理配料問(wèn)題合理配料問(wèn)題求：求：最低成本的原料混合方案最低成本的原料混合方案 原料原料 A B 每單位

2、成本每單位成本 1 4 1 0 2 2 6 1 2 5 3 1 7 1 6 4 2 5 3 8 每單位添每單位添加劑中維生加劑中維生 12 14 8 素最低含量素最低含量例例3 3、運(yùn)輸問(wèn)題、運(yùn)輸問(wèn)題 工工 廠廠 1 2 3 庫(kù)存庫(kù)存 倉(cāng)倉(cāng) 1 2 1 3 50 2 2 2 4 30 庫(kù)庫(kù) 3 3 4 2 10 需求需求 40 15 35運(yùn)輸運(yùn)輸單價(jià)單價(jià)求：求：運(yùn)輸費(fèi)用最小的運(yùn)輸方案運(yùn)輸費(fèi)用最小的運(yùn)輸方案。(2)線性規(guī)劃問(wèn)題的特征：線性規(guī)劃問(wèn)題的特征：l決策變量：決策變量：每個(gè)問(wèn)題都用一組決策變量每個(gè)問(wèn)題都用一組決策變量(X X1 1 X Xn n)表示，表示，這組決策變量的值都代表一個(gè)具體方

3、案。這組決策變量的值都代表一個(gè)具體方案。l目標(biāo)函數(shù)：衡量決策方案優(yōu)劣的函數(shù)，它是決策變量的目標(biāo)函數(shù)：衡量決策方案優(yōu)劣的函數(shù)，它是決策變量的線性函數(shù)，根據(jù)問(wèn)題不同，目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小線性函數(shù)，根據(jù)問(wèn)題不同，目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化?；?。l約束條件：分為兩類約束條件：分為兩類1 1）函數(shù)約束，一組決策變量的線性）函數(shù)約束，一組決策變量的線性函數(shù)函數(shù)=/=/=/=一個(gè)給定的數(shù)（右端項(xiàng)）。一個(gè)給定的數(shù)（右端項(xiàng)）。2 2）決策變量約）決策變量約束。束。具備以上三個(gè)要素的問(wèn)題就稱為具備以上三個(gè)要素的問(wèn)題就稱為 線性規(guī)劃問(wèn)題線性規(guī)劃問(wèn)題。0,.21221122222121112121112211nm

4、nmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件(3)線性規(guī)劃模型一般形式線性規(guī)劃模型一般形式隱含的假設(shè)隱含的假設(shè)n比例性：決策變量變化引起目標(biāo)的改變量與決策變量改比例性：決策變量變化引起目標(biāo)的改變量與決策變量改變量成正比變量成正比n可加性：每個(gè)決策變量對(duì)目標(biāo)和約束的影響?yīng)毩⒂谄渌杉有裕好總€(gè)決策變量對(duì)目標(biāo)和約束的影響?yīng)毩⒂谄渌兞孔兞縩連續(xù)性：每個(gè)決策變量取連續(xù)值連續(xù)性：每個(gè)決策變量取連續(xù)值n確定性：線性規(guī)劃中的參數(shù)確定性：線性規(guī)劃中的參數(shù)aij,bi,cj為確定值為確定值2.2 線性規(guī)劃問(wèn)題的圖解法線性規(guī)劃

5、問(wèn)題的圖解法 20,.1XbAXtsCXZMinMax定義定義1 1：滿足約束：滿足約束(2)(2)的的X=(X=(X X1 1 X Xn n)稱為線性規(guī)劃問(wèn)題的稱為線性規(guī)劃問(wèn)題的可行解可行解，全部可行解的集合稱為，全部可行解的集合稱為可行域可行域。定義定義2 2：滿足：滿足(1)(1)的可行解稱為線性規(guī)劃問(wèn)題的的可行解稱為線性規(guī)劃問(wèn)題的最優(yōu)解最優(yōu)解。x1x2z=20000=50 x1+100 x2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE例例1.目標(biāo)函數(shù)：Max z=50 x1+100 x2 約束條件：s.t.x

6、1+x2 300 (A)2 x1+x2 400 (B)x2 250 (C)x1 0 (D)x2 0 (E)得到最優(yōu)解：x1=50，x2 =250 最優(yōu)目標(biāo)值 z =27500直觀結(jié)論直觀結(jié)論n若線性規(guī)劃問(wèn)題有解，則可行域是一個(gè)凸多邊形若線性規(guī)劃問(wèn)題有解，則可行域是一個(gè)凸多邊形（或凸多面體）；（或凸多面體）；n若線性規(guī)劃問(wèn)題有最優(yōu)解，則若線性規(guī)劃問(wèn)題有最優(yōu)解，則q唯一最優(yōu)解對(duì)應(yīng)于可行域的一個(gè)頂點(diǎn)；唯一最優(yōu)解對(duì)應(yīng)于可行域的一個(gè)頂點(diǎn)；q無(wú)窮多個(gè)最優(yōu)解對(duì)應(yīng)于可行域的一條邊；無(wú)窮多個(gè)最優(yōu)解對(duì)應(yīng)于可行域的一條邊；n若線性規(guī)劃問(wèn)題有可行解，但無(wú)有限最優(yōu)解，則若線性規(guī)劃問(wèn)題有可行解，但無(wú)有限最優(yōu)解，則可行域必

7、然是無(wú)界的；可行域必然是無(wú)界的；n若線性規(guī)劃問(wèn)題無(wú)可行解，則可行域必為空集。若線性規(guī)劃問(wèn)題無(wú)可行解，則可行域必為空集。2.3 2.3 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式0,.21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件(1)線性規(guī)劃模型一般形式線性規(guī)劃模型一般形式價(jià)值系數(shù)價(jià)值系數(shù)決策變量決策變量技術(shù)系數(shù)技術(shù)系數(shù)右端常數(shù)右端常數(shù)0,b,bbxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMaxm21nmnmnmmnnnnnn0

8、,.21221122222121112121112211(2)線性規(guī)劃模型標(biāo)準(zhǔn)形式線性規(guī)劃模型標(biāo)準(zhǔn)形式簡(jiǎn)記形式簡(jiǎn)記形式njxmibxatsxcZMaxjinjjijnjjj,2,10,2,1.11(3)線性規(guī)劃模型其它形式線性規(guī)劃模型其它形式矩陣形式矩陣形式0.XbAXtsCXZMaxncccC21mnmmnnaaaaaaaaaA212222111211nxxxX21價(jià)值向量?jī)r(jià)值向量決策向量決策向量系數(shù)矩陣系數(shù)矩陣mbbbb21右端向量右端向量ncccC21nxxxX21價(jià)值向量?jī)r(jià)值向量決策向量決策向量mbbbb21右端向量右端向量向量形式向量形式0.1XbxPtsCXZMaxjnjjnjjj

9、jaaaP21列向量列向量對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題，我們總可對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題，我們總可以通過(guò)以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式以通過(guò)以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式:(4)一般型向標(biāo)準(zhǔn)型的轉(zhuǎn)化一般型向標(biāo)準(zhǔn)型的轉(zhuǎn)化l目標(biāo)函數(shù)目標(biāo)函數(shù)l目標(biāo)函數(shù)為極小化目標(biāo)函數(shù)為極小化l約束條件約束條件l分兩種情況：大于零和小于零分兩種情況：大于零和小于零l決策變量決策變量l可能存在小于零的情況可能存在小于零的情況(4)一般型向標(biāo)準(zhǔn)型的轉(zhuǎn)化一般型向標(biāo)準(zhǔn)型的轉(zhuǎn)化SLPSLP的特點(diǎn)的特點(diǎn)n（1 1）目標(biāo)函數(shù)目標(biāo)函數(shù)取極大取極大n（2 2）所有）所有約束條件約束條件均由等式表示均由等式表示n（3 3）所有）

10、所有決策變量決策變量取非負(fù)值取非負(fù)值n（4 4）每一約束的）每一約束的右端常數(shù)右端常數(shù)(資源向量的分資源向量的分量量)均為非負(fù)值均為非負(fù)值線性規(guī)劃問(wèn)題標(biāo)準(zhǔn)形式的特點(diǎn)線性規(guī)劃問(wèn)題標(biāo)準(zhǔn)形式的特點(diǎn)1.1.極小化目標(biāo)函數(shù)的問(wèn)題：極小化目標(biāo)函數(shù)的問(wèn)題：設(shè)目標(biāo)函數(shù)為設(shè)目標(biāo)函數(shù)為 Min f=c1x1+c2x2+cnxn 則可以令則可以令z z -f-f ，該極小化問(wèn)題與下面的，該極小化問(wèn)題與下面的極大化問(wèn)題有相同的最優(yōu)解，即極大化問(wèn)題有相同的最優(yōu)解，即 Max z=-c1x1-c2x2-cnxn 但必須注意，盡管以上兩個(gè)問(wèn)題的最優(yōu)解但必須注意，盡管以上兩個(gè)問(wèn)題的最優(yōu)解相同，但他們最優(yōu)解的目標(biāo)函數(shù)值卻相差一

11、個(gè)相同，但他們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)，即符號(hào)，即 Min f -Max z2 2、約束條件不是等式的問(wèn)題：、約束條件不是等式的問(wèn)題：設(shè)約束條件為設(shè)約束條件為 ai1 x1+ai2 x2+ain xn bi 可以引進(jìn)一個(gè)新的變量可以引進(jìn)一個(gè)新的變量s s ，使它等于約束右，使它等于約束右邊與左邊之差邊與左邊之差 s=bi (ai1 x1+ai2 x2+ain xn)顯然，顯然，s s 也具有非負(fù)約束，即也具有非負(fù)約束，即s s00，這時(shí)新的約束條件成為這時(shí)新的約束條件成為 ai1 x1+ai2 x2+ain xn+s=bi 變量變量 s s 稱為稱為松弛變量松弛變量lMax Z=40X

12、1+50X2 X1+2X2 30 s.t 3X1+2X2 60 引入引入松弛變量松弛變量X3、X4、X5 2X2 24 X1,X2 0 0lMax Z=40X1+50X2+0 X3+0 X4+0 X5 X1+2X2+X3 30 s.t 3X1+2X2+X4 60 2X2+X5 24 X1,X5 0 0當(dāng)約束條件為當(dāng)約束條件為 ai1 x1+ai2 x2+ain xn bi 時(shí)，類似地令時(shí)，類似地令 s=(ai1 x1+ai2 x2+ain xn)-bi 顯然，顯然，s 也具有非負(fù)約束，即也具有非負(fù)約束，即s0，這時(shí)新的約，這時(shí)新的約束條件成為束條件成為 ai1 x1+ai2 x2+ain xn

13、-s=bi變量變量s s稱為稱為剩余變量剩余變量Max Z=2X1+5X2+6X3+8X4 4X1+6X2+X3+2X4 12 s.t X1+X2+7X3+5X4 14 2X2+X3+3X4 8 X1,X4 0 0引入引入剩余變量剩余變量：X5、X6、X7Max Z=2X1+5X2+6X3+8X4 4X1+6X2+X3+2X4-X5 12 s.t X1+X2+7X3+5X4 -X6 14 2X2+X3+3X4 -X7 8 X1,X7 0 03.決策變量決策變量如果某個(gè)變量的約束條件為如果某個(gè)變量的約束條件為jjlx 或者或者jjlx 可令可令jjjlxy或者或者jjjxly代入原問(wèn)題代入原問(wèn)題

14、如果某個(gè)變量為自由變量（無(wú)非負(fù)限如果某個(gè)變量為自由變量（無(wú)非負(fù)限制），則可令制），則可令 0,jjjjjxxxxx0jl且且 X1+X2 5s.t -6 X1 10 X2 0 0令令 X1=X1+6-6+6 X1+6 10+6 0 X1 16 X1+X2 11s.t X1 16 X1,X2 0 0 3X1+2X2 8 s.t X1-4X2 14 X2 0,0,X1 無(wú)限制無(wú)限制 令令X1=X1-X1 3 X1-3 X1 +2X2 8 s.t X1-X1 -4X2 14 X1,X1,X2 0 0例：將線性規(guī)劃模型例：將線性規(guī)劃模型 Min Z=-X1+2X2-3X3 X1+X2+X3 7 s.t

15、 X1-X2+X3 2 X1，X2 0，X3無(wú)限制無(wú)限制 化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型四個(gè)方面考慮四個(gè)方面考慮2.4 2.4 圖解法的靈敏度分析圖解法的靈敏度分析 靈敏度分析：建立數(shù)學(xué)模型和求得最優(yōu)解后，研究線性規(guī)劃的一個(gè)或多個(gè)參數(shù)（系數(shù)）ci,aij,bj 變化時(shí)，對(duì)最優(yōu)解產(chǎn)生的影響。2.4.1 目標(biāo)函數(shù)中的系數(shù)目標(biāo)函數(shù)中的系數(shù) ci 的靈敏度分析的靈敏度分析 考慮例1的情況，ci 的變化只影響目標(biāo)函數(shù)等值線的斜率，目標(biāo)函數(shù) z=50 x1+100 x2 在 z=x2(x2=z 斜率為0)到 z=x1+x2 (x2=-x1+z 斜率為-1)之間時(shí)，原最優(yōu)解 x1=50，x2=100 仍是最優(yōu)解。n一

16、般情況：z=c1 x1+c2 x2 寫成斜截式 x2=-(c1/c2)x1+z/c2 目標(biāo)函數(shù)等值線的斜率為 -(c1/c2)，當(dāng) -1 -(c1/c2)0 （*）時(shí)，原最優(yōu)解仍是最優(yōu)解。n假設(shè)產(chǎn)品的利潤(rùn)100元不變，即 c2=100，代到式（*）并整理得 0 c1 100 n假設(shè)產(chǎn)品的利潤(rùn) 50 元不變，即 c1=50，代到式（*）并整理得 50 c2 +n假若產(chǎn)品、的利潤(rùn)均改變，則可直接用式（*）來(lái)判斷。n假設(shè)產(chǎn)品、的利潤(rùn)分別為60元、55元，則 -2 -(60/55)-1 那么，最優(yōu)解為 z=x1+x2 和 z=2 x1+x2 的交點(diǎn) x1=100，x2=200。2.4.2 約束條件中右

17、邊系數(shù)約束條件中右邊系數(shù) bj 的靈敏度分析的靈敏度分析 當(dāng)約束條件中右邊系數(shù) bj 變化時(shí)，線性規(guī)劃的可行域發(fā)生變化，可能引起最優(yōu)解的變化。考慮例1的情況：假設(shè)設(shè)備臺(tái)時(shí)增加10個(gè)臺(tái)時(shí)，即 b1變化為310，這時(shí)可行域擴(kuò)大，最優(yōu)解為 x2=250 和 x1+x2=310 的交點(diǎn) x1=60，x2=250。變化后的總利潤(rùn)-變化前的總利潤(rùn)=增加的利潤(rùn) (5060+100250)-(50 50+100 250)=500，500/10=50 元 說(shuō)明在一定范圍內(nèi)每增加（減少）1個(gè)臺(tái)時(shí)的設(shè)備能力就可增加（減少）50元利潤(rùn)，稱為該約束條件的對(duì)偶價(jià)格。假設(shè)原料 A 增加10 千克時(shí)，即 b2變化為410，這時(shí)可行域擴(kuò)大，但最優(yōu)解仍為 x2=250 和 x1+x2=300 的交點(diǎn) x1=50，x2=250。此變化對(duì)總利潤(rùn)無(wú)影響，該約束條件的對(duì)偶價(jià)格為 0。解釋：原最優(yōu)解沒有把原料 A 用盡，有50千克的剩余，因此增加10千克值增加了庫(kù)存，而不會(huì)增加利潤(rùn)。在一定范圍內(nèi)，當(dāng)約束條件右邊常數(shù)增加1個(gè)單位時(shí) （1）若約束條件的對(duì)偶價(jià)格大于0，則其最優(yōu)目標(biāo)函數(shù)值得到改善（變好）；（2）若約束條件的對(duì)偶價(jià)格小于0，則其最優(yōu)目標(biāo)函數(shù)值受到影響（變壞）；（3）若約束條件的對(duì)偶價(jià)格等于0，則最優(yōu)目標(biāo)函數(shù)值不變。