01運籌學(xué)-靈敏度分析目標規(guī)劃

運籌學(xué)靈敏度分析析價值系數(shù)C發(fā)生變化：：m考慮檢驗數(shù)數(shù)j=cj-∑criarijj=1,2,……,ni=11、若ck是非基變量量的系數(shù)：：設(shè)ck變化為ck+ckk’=ck+ck-∑criarik=k+ck只要k’≤0，即ck≤-k，則最優(yōu)解不不變；否則則，將最優(yōu)優(yōu)單純形表表中的檢驗驗數(shù)k用k’取代，繼續(xù)續(xù)單純形法法的表格計計算。例:MaxZ=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥02、線性規(guī)劃劃問題的進進一步研究究（2.3）進一步理解解最優(yōu)單純純性表中各各元素的含含義考慮問問題Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2...am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥03.靈敏度分分析3、靈敏度度分析無防設(shè)，，xj=0j=m+1,…,n;xi=bi’i=1,…,m是基本可可行解,對應(yīng)的目目標函數(shù)數(shù)典式為為：z=-f+m+1xm+1+…+nxn以下是初初始單純純形表：：mm其中：f=-∑cibi’j=cj-∑ciaij’為檢驗數(shù)數(shù)。向向量b’=B-1bi=1i=1A=[p1,p2,…,pn],pj’=B-1pj,pj’=(a1j’,a2j’,…,amj’)T，j=m+1,……,nci,bj發(fā)生變化化——本段重點增加一約約束或變變量及A中元素發(fā)發(fā)生變化化—通過例題題學(xué)會處處理對于表格格單純形形法，通通過計算算得到最最優(yōu)單純純形表。。應(yīng)能能夠找到到最優(yōu)基基B的逆矩陣陣B-1，B-1b以及B-1N，檢驗數(shù)數(shù)j等。3.靈敏度分分析價值系數(shù)數(shù)c發(fā)生變化化：m考慮檢驗驗數(shù)j=cj-∑criarijj=1,2,………,ni=11.若ck是非基變變量的系系數(shù)：設(shè)ck變化為ck+ckk’=ck+ck-∑criarik=k+ck只要k’≤0,即ck≤-k，則最優(yōu)解不變；；否則，將最最優(yōu)單純形表表中的檢驗數(shù)k用k’取代，繼續(xù)單單純形法的表格格計算。3.靈敏度分析例3.3:Maxz=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥03.靈敏度分析例：最優(yōu)單純純形表從表中看到σ3=c3+Δc3-(c2×a13+c1×a23)可得到Δc3≤9/5時，原最優(yōu)解解不變。3.靈敏度分析2、若cs是基變量的系系數(shù)：設(shè)cs變化為cs+cs，那么j’=cj-∑criarij-(cs+cs)asj=j-csasj，i≠s對所有非基變變量，只要對所有非非基變量j’≤0，即j≤csasj，則最優(yōu)解不變；否則，，將最優(yōu)單純純形表中的檢檢驗數(shù)j用j’取代，繼續(xù)單單純形法的表表格計算。Max{j/asjasj>0}≤cs≤Min{j/asjasj<0}3.靈敏度分析例3.4:Maxz=2x1+3x2+0x3+0x4+0x5s.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,x3,x4,x5≥03.靈敏度分析例:下表為最優(yōu)單單純形表,考慮基變量系數(shù)c2發(fā)生變化從表中看到σj=cj-(c1×a1j+c5×a5j+(c2+Δc2)×a2j)j=3,4可得到-3≤Δc2≤1時，原最優(yōu)解解不變。3.靈敏度分析右端項項b發(fā)生變變化設(shè)分量量br變化為為br+br，根據(jù)據(jù)第1章的討討論，，最優(yōu)優(yōu)解的的基變變量xB=B-1b，那么么只要要保持持B-1(b+b)≥≥0，則最最優(yōu)基基不變變，即即基變變量保保持，，只有有值的的變化化；否否則，，需要要利用用對偶偶單純純形法法繼續(xù)續(xù)計算算。對于問問題(LP)Maxz=cTxs.t.Ax≤bx≥03.靈敏度度分析析最優(yōu)單單純形形表中中含有有B-1=(aij）i=1,…,m;j=n+1,…,n+m那么新的xi=(B-1b)i+brairi=1,…,m。由此可可得，，最優(yōu)優(yōu)基不不變的的條件件是Max{-bi/airair>0}≤br≤Min{-bi/airair<0}3.靈敏度度分析析例3.5:上例最最優(yōu)單單純形形表如如下3.靈敏度度分析析00.250這里B-1=-20.510.5-0.1250各列分分別對對應(yīng)b1、b2、b3的單一一變化化因此，，設(shè)b1增加4，則x1,x5,x2分別變變?yōu)椋海?+0×4=4,4+(-2)×4=-4<0,2+0.5×4=4用對偶單單純形形法進一步步求解解，可可得：：x*=(4,3,2,0,0)Tf*=173.靈敏度度分析析增加一一個變變量增加變變量xn+1則有相相應(yīng)的的pn+1,cn+1。那么計算出出B-1pn+1,n+1=cn+1-∑criarin+1填入最最優(yōu)單單純形形表,若n+1≤0則最優(yōu)解解不變變；否則，，進一步步用單單純形形法求求解。。3.靈敏度度分析析例3.6:例3.4增加x6,p6=(2,6,3)T,c6=5計算得得到用單純純形法法進一一步求求解，，可得得：x*=(1,1.5,0,0,0,2)Tf*=16.53.靈敏度度分析析增加一一個約約束增加約約束一一個之之后，，應(yīng)把把最優(yōu)優(yōu)解帶帶入新的的約束束，若若滿足足則最最優(yōu)解解不變變，否否則填入最最優(yōu)單單純形形表作作為新新的一一行，，引入入一個新的的非負負變量量（原原約束束若是是小于于等于于形式可可引引入入非非負負松松弛弛變變量量，，否否則則引引入入非非負負人人工變變量量）），，并并通通過過矩矩陣陣行行變變換換把把對對應(yīng)應(yīng)基基變變量的的元元素素變變?yōu)闉?，進進一一步步用用單單純純形形法法或或?qū)ε紗螁渭兗冃涡畏ǚㄇ笄蠼饨狻！?.靈敏敏度度分分析析例3.7:例3.4增加加3x1+2x2≤15，原原最最優(yōu)優(yōu)解解不不滿足足這這個個約約束束。。于是是3.靈敏敏度度分分析析經(jīng)對對偶偶單單純純形形法法一一步步，，可可得得最最優(yōu)優(yōu)解解為為（（3.5,2.25,0,0,3,2)T，最最優(yōu)優(yōu)值值為為13.75A中元元素素發(fā)發(fā)生生變變化化(只討討論論N中某某一一列列變化化情情況況））與增增加加變變量量xn+1的情情況況類類似似，，假假設(shè)設(shè)pj變化化。。那么么，，重重新新計計算算出出B-1pjj=cj-∑∑criarij填入入最最優(yōu)優(yōu)單單純純形形表表，，若若j≤0則最最優(yōu)解解不不變變；；否否則則，，進進一一步步用用單單純純形形法法求求解解。。（例例子子從從略略））3.靈敏敏度度分分析析Chapter5目標標規(guī)規(guī)劃劃(Goalprogramming)目標標規(guī)規(guī)劃劃問問題題及及其其數(shù)數(shù)學(xué)學(xué)模模型型目標標規(guī)規(guī)劃劃的的圖圖解解分分析析法法求求解解方方法法目標標規(guī)規(guī)劃劃應(yīng)應(yīng)用用舉舉例例本章主要內(nèi)容：目標標規(guī)規(guī)劃劃問問題題及及其其數(shù)數(shù)學(xué)學(xué)模模型型問題題的的提提出出：：目標標規(guī)規(guī)劃劃是是在在線線性性規(guī)規(guī)劃劃的的基基礎(chǔ)礎(chǔ)上上，，為為適適應(yīng)應(yīng)經(jīng)經(jīng)濟濟管管理理多多目目標標決決策策的的需需要要而而由由線線性性規(guī)規(guī)劃劃逐逐步步發(fā)發(fā)展展起起來來的的一一個個分分支支。。由于于現(xiàn)現(xiàn)代代化化企企業(yè)業(yè)內(nèi)內(nèi)專專業(yè)業(yè)分分工工越越來來越越細細，，組組織織機機構(gòu)構(gòu)日日益益復(fù)復(fù)雜雜，，為為了了統(tǒng)統(tǒng)一一協(xié)協(xié)調(diào)調(diào)企企業(yè)業(yè)各各部部門門圍圍繞繞一一個個整整體體的的目目標標工工作作，，產(chǎn)產(chǎn)生生了了目目標標管管理理這這種種先先進進的的管管理理技技術(shù)術(shù)。。目目標標規(guī)規(guī)劃劃是是實實行行目目標標管管理理的的有有效效工工具具，，它它根根據(jù)據(jù)企企業(yè)業(yè)制制定定的的經(jīng)經(jīng)營營目目標標以以及及這這些些目目標標的的輕輕重重緩緩急急次次序序，，考考慮慮現(xiàn)現(xiàn)有有資資源源情情況況，，分分析析如如何何達達到到規(guī)規(guī)定定目目標標或或從從總總體體上上離離規(guī)規(guī)定定目目標標的的差差距距為為最最小小。。目標標規(guī)規(guī)劃劃問問題題及及其其數(shù)數(shù)學(xué)學(xué)模模型型例5.1某某企企業(yè)業(yè)計計劃劃生生產(chǎn)產(chǎn)甲甲，，乙乙兩兩種種產(chǎn)產(chǎn)品品，，這這些些產(chǎn)產(chǎn)品品分分別別要要在在A,B,C,D四四種種不不同同設(shè)設(shè)備備上上加加工工。。按按工工藝藝文文件件規(guī)規(guī)定定，，如如表表所所示示。。ABCD單件利潤甲11402乙22043最大負荷1281612問該該企企業(yè)業(yè)應(yīng)應(yīng)如如何何安安排排計計劃劃，，使使得得計計劃劃期期內(nèi)內(nèi)的的總總利利潤潤收收入入為為最最大大？？目標標規(guī)規(guī)劃劃問問題題及及其其數(shù)數(shù)學(xué)學(xué)模模型型解：：設(shè)設(shè)甲甲、、乙乙產(chǎn)產(chǎn)品品的的產(chǎn)產(chǎn)量量分分別別為為x1，x2，建建立立線線性性規(guī)規(guī)劃劃模模型型：：其最最優(yōu)優(yōu)解解為為x1＝4，，x2＝2，，z＊＝14元元目標標規(guī)規(guī)劃劃問問題題及及其其數(shù)數(shù)學(xué)學(xué)模模型型但企企業(yè)業(yè)的的經(jīng)經(jīng)營營目目標標不不僅僅僅僅是是利利潤潤，，而而且且要要考考慮慮多多個個方方面面，，如如：：力求求使使利利潤潤指指標標不不低低于于12元；；考慮慮到到市市場場需需求求，，甲甲、、乙乙兩兩種種產(chǎn)產(chǎn)品品的的生生產(chǎn)產(chǎn)量量需需保保持持1:1的比比例例；；C和D為貴貴重重設(shè)設(shè)備備，，嚴嚴格格禁禁止止超超時時使使用用；；設(shè)備備B必要要時時可可以以加加班班，，但但加加班班時時間間要要控控制制；；設(shè)設(shè)備備A即要要求求充充分分利利用用，，又又盡盡可可能能不不加加班班。。要考考慮慮上上述述多多方方面面的的目目標標，，需需要要借借助助目目標標規(guī)規(guī)劃劃的的方方法法。。目標標規(guī)規(guī)劃劃問問題題及及其其數(shù)數(shù)學(xué)學(xué)模模型型線性規(guī)規(guī)劃模模型存存在的的局限限性：：1）要求求問題題的解解必須須滿足足全部部約束束條件件，實實際問問題中中并非非所有有約束束都需需要嚴嚴格滿滿足。。2）只能能處理理單目目標的的優(yōu)化化問題題。實實際問問題中中，目目標和和約束束可以以相互互轉(zhuǎn)化化。3）線性性規(guī)劃劃中各各個約約束條條件都都處于于同等等重要要地位位，但但現(xiàn)實實問題題中，，各目目標的的重要要性即即有層層次上上的差差別，，同一一層次次中又又可以以有權(quán)權(quán)重上上的區(qū)區(qū)分。。4）線性性規(guī)劃劃尋求求最優(yōu)優(yōu)解，，但很很多實實際問問題中中只需需找出出滿意意解就就可以以。目標規(guī)規(guī)劃問問題及及其數(shù)數(shù)學(xué)模模型目標規(guī)規(guī)劃怎怎樣解解決上上述線線性規(guī)規(guī)劃模模型建建模中中的局局限性性？1.設(shè)置偏偏差變變量，，用來來表明明實際際值同同目標標值之之間的的差異異。偏差變變量用用下列列符號號表示示：d+——超出目目標的的偏差差，稱稱正偏偏差變變量d-——未達到到目標標的偏偏差，，稱負負偏差差變量量正負偏偏差變變量兩兩者必必有一一個為為0。當(dāng)實際際值超超出目目標值值時：：d+>0,d-=0;當(dāng)實際際值未未達到到目標標值時時：d+=0,d->0;當(dāng)實際際值同同目標標值恰恰好一一致時時：d+=0,d-=0;故恒有有d+×d-=0目標規(guī)規(guī)劃問問題及及其數(shù)數(shù)學(xué)模模型2.統(tǒng)一處處理目目標和和約束束。對有嚴嚴格限限制的的資源源使用用建立立系統(tǒng)統(tǒng)約束束，數(shù)數(shù)學(xué)形形式同同線性性規(guī)劃劃中的的約束束條件件。如如C和D設(shè)備的的使用用限制制。對不嚴嚴格限限制的的約束束，連連同原原線性性規(guī)劃劃建模模時的的目標標，均均通過過目標標約束束來表表達。。1）例如如要求求甲、、乙兩兩種產(chǎn)產(chǎn)品保保持1:1的比例例，系系統(tǒng)約約束表表達為為：x1=x2。由于于這個個比例例允許許有偏偏差，，當(dāng)x1<x2時，出出現(xiàn)負負偏差差d-，即：：x1+d-=x2或x1－x2+d-=0當(dāng)x1>x2時，出出現(xiàn)正正偏差差d+，即：：x1-d+=x2或x1－x2-d+=0目標規(guī)規(guī)劃問問題及及其數(shù)數(shù)學(xué)模模型∵正負負偏差差不可可能同同時出出現(xiàn)，，故總總有：：x1－x2+d--d+=0若希望望甲的的產(chǎn)量量不低低于乙乙的產(chǎn)產(chǎn)量，，即不不希望望d->0,用目標標約束束可表表為:若希望望甲的的產(chǎn)量量低于于乙的的產(chǎn)量量，即即不希希望d＋>0,用目標標約束束可表表為:若希望望甲的的產(chǎn)量量恰好好等于于乙的的產(chǎn)量量，即即不希希望d＋>0,也不希希望d->0用目標標約束束可表表為:目標規(guī)規(guī)劃問問題及及其數(shù)數(shù)學(xué)模模型3）設(shè)備備B必要時時可加加班及及加班班時間間要控控制，，目標標約束束表示示為：：2）力求求使利利潤指指標不不低于于12元，目目標約約束表表示為為：4）設(shè)備備A既要求求充分分利用用，又又盡可可能不不加班班，目目標約約束表表示為為：目標規(guī)規(guī)劃問問題及及其數(shù)數(shù)學(xué)模模型3.目標的的優(yōu)先先級與與權(quán)系系數(shù)在一個個目標標規(guī)劃劃的模模型中中，為為達到到某一一目標標可犧犧牲其其他一一些目目標，，稱這這些目目標是是屬于于不同同層次次的優(yōu)優(yōu)先級級。優(yōu)優(yōu)先級級層次次的高高低可可分別別通過過優(yōu)先先因子子P1,P2,…表示。。對于于同一一層次次優(yōu)先先級的的不同同目標標，按按其重重要程程度可可分別別乘上上不同同的權(quán)權(quán)系數(shù)數(shù)。權(quán)權(quán)系數(shù)數(shù)是一一個個個具體體數(shù)字字，乘乘上的的權(quán)系系數(shù)越越大，，表明明該目目標越越重要要?，F(xiàn)假定定：第1優(yōu)先級級P1———企業(yè)利利潤；；第2優(yōu)先級級P2———甲乙產(chǎn)產(chǎn)品的的產(chǎn)量量保持持1:1的比例例第3優(yōu)先級級P3———設(shè)備A,B盡量不不超負負荷工工作。。其中中設(shè)備備A的重要要性比比設(shè)備備B大三倍倍。目標規(guī)規(guī)劃問問題及及其數(shù)數(shù)學(xué)模模型上述目目標規(guī)規(guī)劃模模型可可以表表示為為：目標規(guī)規(guī)劃問問題及及其數(shù)數(shù)學(xué)模模型目標規(guī)規(guī)劃數(shù)數(shù)學(xué)模模型的的一般般形式式達成函數(shù)目標約束其中：gk為第k個目標約束束的預(yù)期目目標值，和和為為pl優(yōu)先因子對對應(yīng)各目標標的權(quán)系數(shù)數(shù)。目標規(guī)劃問問題及其數(shù)數(shù)學(xué)模型用目標規(guī)劃劃求解問題題的過程：：明確問題，，列出目標標的優(yōu)先級級和權(quán)系數(shù)數(shù)構(gòu)造目標規(guī)規(guī)劃模型求出滿意解解滿意否？分析各項目目標完成情情況據(jù)此制定出出決策方案案NY目標規(guī)劃的的圖解分析析法目標規(guī)劃的的圖解法：：適用兩個變變量的目標標規(guī)劃問題題，但其操操作簡單，，原理一目目了然。同同時，也有有助于理解解一般目標標規(guī)劃的求求解原理和和過程。圖解法解題題步驟：1.將所有約束束條件（包包括目標約約束和絕對對約束，暫暫不考慮正正負偏差變變量）的直直線方程分分別標示于于坐標平面面上。2.確定系統(tǒng)約約束的可行行域。3.在目標約束束所代表的的邊界線上上，用箭頭頭標出正、、負偏差變變量值增大大的方向目標規(guī)劃的的圖解分析析法3.求滿足最高高