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

2.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型(1)線性規(guī)劃問題建模線性規(guī)劃問題建模例例1 1、生產(chǎn)組織與計劃問題、生產(chǎn)組織與計劃問題A,B A,B 各生產(chǎn)多少各生產(chǎn)多少,可獲最大利潤可獲最大利潤?可用資源可用資源設(shè)備設(shè)備原料原料1原料原料2A B1 22 10 1單位利潤單位利潤50 100300臺時臺時400kg250kg建立線性規(guī)劃模型的步驟：1）根據(jù)管理層的要求確定決策目標(biāo)和收集相關(guān)數(shù)據(jù)。2）確定要做出的決策，引入決策變量。3）確定對這些決策的約束條件和目標(biāo)函數(shù)。例例2 2 合理配料問題合理配料問題求：求：最低成本的原料混合方案最低成本的原料混合方案 原料原料 A B 每單位成本每單位成本 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、運輸問題、運輸問題 工工 廠廠 1 2 3 庫存庫存 倉倉 1 2 1 3 50 2 2 2 4 30 庫庫 3 3 4 2 10 需求需求 40 15 35運輸運輸單價單價求：求：運輸費用最小的運輸方案運輸費用最小的運輸方案。(2)線性規(guī)劃問題的特征：線性規(guī)劃問題的特征：l決策變量：決策變量：每個問題都用一組決策變量每個問題都用一組決策變量(X X1 1 X Xn n)表示，表示，這組決策變量的值都代表一個具體方案。這組決策變量的值都代表一個具體方案。l目標(biāo)函數(shù)：衡量決策方案優(yōu)劣的函數(shù)，它是決策變量的目標(biāo)函數(shù)：衡量決策方案優(yōu)劣的函數(shù)，它是決策變量的線性函數(shù)，根據(jù)問題不同，目標(biāo)函數(shù)實現(xiàn)最大化或最小線性函數(shù)，根據(jù)問題不同，目標(biāo)函數(shù)實現(xiàn)最大化或最小化。化。l約束條件：分為兩類約束條件：分為兩類1 1）函數(shù)約束，一組決策變量的線性）函數(shù)約束，一組決策變量的線性函數(shù)函數(shù)=/=/=/=一個給定的數(shù)（右端項）。一個給定的數(shù)（右端項）。2 2）決策變量約）決策變量約束。束。具備以上三個要素的問題就稱為具備以上三個要素的問題就稱為 線性規(guī)劃問題線性規(guī)劃問題。0,.21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件(3)線性規(guī)劃模型一般形式線性規(guī)劃模型一般形式隱含的假設(shè)隱含的假設(shè)n比例性：決策變量變化引起目標(biāo)的改變量與決策變量改比例性：決策變量變化引起目標(biāo)的改變量與決策變量改變量成正比變量成正比n可加性：每個決策變量對目標(biāo)和約束的影響?yīng)毩⒂谄渌杉有裕好總€決策變量對目標(biāo)和約束的影響?yīng)毩⒂谄渌兞孔兞縩連續(xù)性：每個決策變量取連續(xù)值連續(xù)性：每個決策變量取連續(xù)值n確定性：線性規(guī)劃中的參數(shù)確定性：線性規(guī)劃中的參數(shù)aij,bi,cj為確定值為確定值2.2 線性規(guī)劃問題的圖解法線性規(guī)劃問題的圖解法 20,.1XbAXtsCXZMinMax定義定義1 1：滿足約束：滿足約束(2)(2)的的X=(X=(X X1 1 X Xn n)稱為線性規(guī)劃問題的稱為線性規(guī)劃問題的可行解可行解，全部可行解的集合稱為，全部可行解的集合稱為可行域可行域。定義定義2 2：滿足：滿足(1)(1)的可行解稱為線性規(guī)劃問題的的可行解稱為線性規(guī)劃問題的最優(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.x1+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ī)劃問題有解，則可行域是一個凸多邊形若線性規(guī)劃問題有解，則可行域是一個凸多邊形（或凸多面體）；（或凸多面體）；n若線性規(guī)劃問題有最優(yōu)解，則若線性規(guī)劃問題有最優(yōu)解，則q唯一最優(yōu)解對應(yīng)于可行域的一個頂點；唯一最優(yōu)解對應(yīng)于可行域的一個頂點；q無窮多個最優(yōu)解對應(yīng)于可行域的一條邊；無窮多個最優(yōu)解對應(yīng)于可行域的一條邊；n若線性規(guī)劃問題有可行解，但無有限最優(yōu)解，則若線性規(guī)劃問題有可行解，但無有限最優(yōu)解，則可行域必然是無界的；可行域必然是無界的；n若線性規(guī)劃問題無可行解，則可行域必為空集。若線性規(guī)劃問題無可行解，則可行域必為空集。2.3 2.3 線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性規(guī)劃問題的標(biāo)準(zhǔn)形式0,.21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件(1)線性規(guī)劃模型一般形式線性規(guī)劃模型一般形式價值系數(shù)價值系數(shù)決策變量決策變量技術(shù)系數(shù)技術(shù)系數(shù)右端常數(shù)右端常數(shù)0,b,bbxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMaxm21nmnmnmmnnnnnn0,.21221122222121112121112211(2)線性規(guī)劃模型標(biāo)準(zhǔn)形式線性規(guī)劃模型標(biāo)準(zhǔn)形式簡記形式簡記形式njxmibxatsxcZMaxjinjjijnjjj,2,10,2,1.11(3)線性規(guī)劃模型其它形式線性規(guī)劃模型其它形式矩陣形式矩陣形式0.XbAXtsCXZMaxncccC21mnmmnnaaaaaaaaaA212222111211nxxxX21價值向量價值向量決策向量決策向量系數(shù)矩陣系數(shù)矩陣mbbbb21右端向量右端向量ncccC21nxxxX21價值向量價值向量決策向量決策向量mbbbb21右端向量右端向量向量形式向量形式0.1XbxPtsCXZMaxjnjjnjjjjaaaP21列向量列向量對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式以通過以下變換，將其轉(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的特點的特點n（1 1）目標(biāo)函數(shù)目標(biāo)函數(shù)取極大取極大n（2 2）所有）所有約束條件約束條件均由等式表示均由等式表示n（3 3）所有）所有決策變量決策變量取非負(fù)值取非負(fù)值n（4 4）每一約束的）每一約束的右端常數(shù)右端常數(shù)(資源向量的分資源向量的分量量)均為非負(fù)值均為非負(fù)值線性規(guī)劃問題標(biāo)準(zhǔn)形式的特點線性規(guī)劃問題標(biāo)準(zhǔn)形式的特點1.1.極小化目標(biāo)函數(shù)的問題：極小化目標(biāo)函數(shù)的問題：設(shè)目標(biāo)函數(shù)為設(shè)目標(biāo)函數(shù)為 Min f=c1x1+c2x2+cnxn 則可以令則可以令z z -f-f ，該極小化問題與下面的，該極小化問題與下面的極大化問題有相同的最優(yōu)解，即極大化問題有相同的最優(yōu)解，即 Max z=-c1x1-c2x2-cnxn 但必須注意，盡管以上兩個問題的最優(yōu)解但必須注意，盡管以上兩個問題的最優(yōu)解相同，但他們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個相同，但他們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個符號，即符號，即 Min f -Max z2 2、約束條件不是等式的問題：、約束條件不是等式的問題：設(shè)約束條件為設(shè)約束條件為 ai1 x1+ai2 x2+ain xn bi 可以引進一個新的變量可以引進一個新的變量s s ，使它等于約束右，使它等于約束右邊與左邊之差邊與左邊之差 s=bi (ai1 x1+ai2 x2+ain xn)顯然，顯然，s s 也具有非負(fù)約束，即也具有非負(fù)約束，即s s00，這時新的約束條件成為這時新的約束條件成為 ai1 x1+ai2 x2+ain xn+s=bi 變量變量 s s 稱為稱為松弛變量松弛變量lMax Z=40X1+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 時，類似地令時，類似地令 s=(ai1 x1+ai2 x2+ain xn)-bi 顯然，顯然，s 也具有非負(fù)約束，即也具有非負(fù)約束，即s0，這時新的約，這時新的約束條件成為束條件成為 ai1 x1+ai2 x2+ain xn-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.決策變量決策變量如果某個變量的約束條件為如果某個變量的約束條件為jjlx 或者或者jjlx 可令可令jjjlxy或者或者jjjxly代入原問題代入原問題如果某個變量為自由變量（無非負(fù)限如果某個變量為自由變量（無非負(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 無限制無限制 令令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 X1-X2+X3 2 X1，X2 0，X3無限制無限制 化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型四個方面考慮四個方面考慮2.4 2.4 圖解法的靈敏度分析圖解法的靈敏度分析 靈敏度分析：建立數(shù)學(xué)模型和求得最優(yōu)解后，研究線性規(guī)劃的一個或多個參數(shù)（系數(shù)）ci,aij,bj 變化時，對最優(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)之間時，原最優(yōu)解 x1=50，x2=100 仍是最優(yōu)解。n一般情況：z=c1 x1+c2 x2 寫成斜截式 x2=-(c1/c2)x1+z/c2 目標(biāo)函數(shù)等值線的斜率為 -(c1/c2)，當(dāng) -1 -(c1/c2)0 （*）時，原最優(yōu)解仍是最優(yōu)解。n假設(shè)產(chǎn)品的利潤100元不變，即 c2=100，代到式（*）并整理得 0 c1 100 n假設(shè)產(chǎn)品的利潤 50 元不變，即 c1=50，代到式（*）并整理得 50 c2 +n假若產(chǎn)品、的利潤均改變，則可直接用式（*）來判斷。n假設(shè)產(chǎn)品、的利潤分別為60元、55元，則 -2 -(60/55)-1 那么，最優(yōu)解為 z=x1+x2 和 z=2 x1+x2 的交點 x1=100，x2=200。2.4.2 約束條件中右邊系數(shù)約束條件中右邊系數(shù) bj 的靈敏度分析的靈敏度分析 當(dāng)約束條件中右邊系數(shù) bj 變化時，線性規(guī)劃的可行域發(fā)生變化，可能引起最優(yōu)解的變化?？紤]例1的情況：假設(shè)設(shè)備臺時增加10個臺時，即 b1變化為310，這時可行域擴大，最優(yōu)解為 x2=250 和 x1+x2=310 的交點 x1=60，x2=250。變化后的總利潤-變化前的總利潤=增加的利潤 (5060+100250)-(50 50+100 250)=500，500/10=50 元 說明在一定范圍內(nèi)每增加（減少）1個臺時的設(shè)備能力就可增加（減少）50元利潤，稱為該約束條件的對偶價格。假設(shè)原料 A 增加10 千克時，即 b2變化為410，這時可行域擴大，但最優(yōu)解仍為 x2=250 和 x1+x2=300 的交點 x1=50，x2=250。此變化對總利潤無影響，該約束條件的對偶價格為 0。解釋：原最優(yōu)解沒有把原料 A 用盡，有50千克的剩余，因此增加10千克值增加了庫存，而不會增加利潤。在一定范圍內(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ù)值不變。