研目標(biāo)規(guī)劃課件

目標(biāo)規(guī)劃(Goalprogramming)目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃概述目標(biāo)規(guī)劃目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)導(dǎo)入案例——產(chǎn)品組合問題產(chǎn)品I產(chǎn)品II設(shè)備A設(shè)備B設(shè)備C240205121615單位利潤23現(xiàn)增加如下考慮：（1）力求使利潤指標(biāo)不低于15元；（2）據(jù)市場預(yù)測，I、II兩種產(chǎn)品需求量的比例大致是1:2；（3）A為貴重設(shè)備，嚴(yán)格禁止超時使用；（4）設(shè)備C可以適當(dāng)加班，但要控制；設(shè)備B既要求充分利用，又盡可能不加班，在重要性上設(shè)備B是C的3倍。綜合考慮上述因素，企業(yè)應(yīng)如何決策？這里本章所要討論的問題。最優(yōu)解：x1=3x2=3z=15若僅考慮利潤目標(biāo)，其LP模型為：導(dǎo)入案例——產(chǎn)品組合問題產(chǎn)品I產(chǎn)品II設(shè)備A2212單位利潤

目標(biāo)規(guī)劃通過引入目標(biāo)值和偏差變量，可以將目標(biāo)函數(shù)轉(zhuǎn)化為目標(biāo)約束。目標(biāo)值：是指預(yù)先給定的某個目標(biāo)的一個期望值。實(shí)現(xiàn)值或決策值：是指當(dāng)決策變量xj

選定以后，目標(biāo)函數(shù)的對應(yīng)值。偏差變量（事先無法確定的未知數(shù)）：是指實(shí)現(xiàn)值和目標(biāo)值之間的差異,記為d。正偏差變量：表示實(shí)現(xiàn)值超過目標(biāo)值的部分，記為d＋。負(fù)偏差變量：表示實(shí)現(xiàn)值未達(dá)到目標(biāo)值的部分，記為d－。1、目標(biāo)值和偏差變量1、目標(biāo)值和偏差變量

當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示：d＋≥0,d－＝0當(dāng)未完成規(guī)定的指標(biāo)則表示：d＋＝0,d－≥0當(dāng)恰好完成指標(biāo)時則表示：d＋＝0,d－＝0∴d＋×d－

＝0成立。

引入了目標(biāo)值和正、負(fù)偏差變量后，就對某一問題有了新的限制，既目標(biāo)約束。目標(biāo)約束即可對原目標(biāo)函數(shù)起作用，也可對原約束起作用。目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束。在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未達(dá)到目標(biāo)值，故有d＋×d－

＝0,并規(guī)定d＋≥0,d－≥02、目標(biāo)約束和絕對約束引入了目標(biāo)值和正、負(fù)偏差變量后，就對絕對約束（系統(tǒng)約束）是指必須嚴(yán)格滿足的等式或不等式約束。如線性規(guī)劃中的所有約束條件都是絕對約束，否則無可行解。所以，絕對約束是硬約束。目標(biāo)規(guī)劃處理問題的方法是將多目標(biāo)轉(zhuǎn)化為多個目標(biāo)約束。如目標(biāo)利潤的約束：甲產(chǎn)品單位利潤2元，乙產(chǎn)品單位利潤3元，目標(biāo)要求利潤不小于15元，即有目標(biāo)約束不等式：添加正負(fù)偏差變量，將其變?yōu)榈仁剑寒?dāng)時，表明，達(dá)到了目標(biāo)；當(dāng)時，表明，未達(dá)到目標(biāo)，此種情況一但發(fā)生，希望越小越好，即目標(biāo)要求為：絕對約束（系統(tǒng)約束）是指必須嚴(yán)格滿足的等式或不等式約束。如線同理有其他目標(biāo)約束：產(chǎn)品比例設(shè)備B利用與加班設(shè)備C的加班同理有其他目標(biāo)約束：

達(dá)成函數(shù)是一個使總偏差量為最小的目標(biāo)函數(shù)，記為minZ=f（d＋、d－）。

一般說來，有以下三種情況，但只能出現(xiàn)其中之一：⑴.要求恰好達(dá)到規(guī)定的目標(biāo)值，即正、負(fù)偏差變量要盡可能小，則minZ=f（d＋＋d－）。⑵.要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，也就是正偏差變量盡可能小，則minZ=f（d＋）。⑶.要求超過目標(biāo)值，即超過量不限，但不低于目標(biāo)值，也就是負(fù)偏差變量盡可能小，則minZ=f（d－）。

對于由絕對約束轉(zhuǎn)化而來的目標(biāo)函數(shù)，也照上述處理即可。3、達(dá)成函數(shù)（即目標(biāo)規(guī)劃中的目標(biāo)函數(shù)）達(dá)成函數(shù)是一個使總偏差量為最小的目標(biāo)函數(shù)，記為m優(yōu)先因子Pk

是將決策目標(biāo)按其重要程度排序并表示出來。P1>>P2>>…>>Pk>>Pk+1>>…>>PK，k=1.2…K。權(quán)系數(shù)ωk區(qū)別具有相同優(yōu)先因子的兩個目標(biāo)的差別，決策者可視具體情況而定。對于這種解來說，前面的目標(biāo)可以保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，而后面的目標(biāo)就不一定能保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，有些可能就不能實(shí)現(xiàn)。4、優(yōu)先因子（優(yōu)先等級）與優(yōu)先權(quán)系數(shù)5、滿意解（具有層次意義的解）優(yōu)先因子Pk是將決策目標(biāo)按其重要程度排序并表示導(dǎo)入案例——產(chǎn)品組合問題產(chǎn)品I產(chǎn)品II設(shè)備A設(shè)備B設(shè)備C240205121615單位利潤23現(xiàn)增加如下考慮：（1）力求使利潤指標(biāo)不低于15元；（2）據(jù)市場預(yù)測，I、II兩種產(chǎn)品需求量的比例大致是1:2；（3）A為貴重設(shè)備，嚴(yán)格禁止超時使用；（4）設(shè)備C可以適當(dāng)加班，但要控制；設(shè)備B既要求充分利用，又盡可能不加班，在重要性上設(shè)備B是C的3倍。綜合考慮上述因素，企業(yè)應(yīng)如何決策？這里本章所要討論的問題。最優(yōu)解：x1=3x2=3z=15若僅考慮利潤目標(biāo)，其LP模型為：導(dǎo)入案例——產(chǎn)品組合問題產(chǎn)品I產(chǎn)品II設(shè)備A2212單位利潤將上述目標(biāo)規(guī)劃的目標(biāo)約束、目標(biāo)函數(shù)再加上系統(tǒng)約束和變量非負(fù)約束，即構(gòu)成了引例中的目標(biāo)規(guī)劃數(shù)學(xué)模型如下：將上述目標(biāo)規(guī)劃的目標(biāo)約束、目標(biāo)函數(shù)再加上系統(tǒng)約束和變量非負(fù)約

目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理中多目標(biāo)決策的需要而逐步發(fā)展起來的一個分支。

2、線性規(guī)劃求最優(yōu)解；目標(biāo)規(guī)劃是找到一個滿意解。1、線性規(guī)劃只討論一個線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題；而目標(biāo)規(guī)劃是多個目標(biāo)決策，可求得更切合實(shí)際的解。目標(biāo)規(guī)劃概述（一）、目標(biāo)規(guī)劃與線性規(guī)劃的比較目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理中多4、線性規(guī)劃的最優(yōu)解是絕對意義下的最優(yōu)，但需花去大量的人力、物力、財(cái)力才能得到；實(shí)際過程中，只要求得滿意解，就能滿足需要（或更能滿足需要）。3、線性規(guī)劃中的約束條件是同等重要的，是硬約束；而目標(biāo)規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。目前，已經(jīng)在經(jīng)濟(jì)計(jì)劃、生產(chǎn)管理、經(jīng)營管理、市場分析、財(cái)務(wù)管理等方面得到了廣泛的應(yīng)用。4、線性規(guī)劃的最優(yōu)解是絕對意義下的最優(yōu)，但需花去大量的人目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式：

優(yōu)先因子正偏差權(quán)系數(shù)負(fù)偏差權(quán)系數(shù)目標(biāo)約束系統(tǒng)約束變量非負(fù)目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式：優(yōu)先因子正偏建模的步驟1、根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約束與絕對約束；4、對同一優(yōu)先等級中的各偏差變量，若需要可按其重要程度的不同，賦予相應(yīng)的權(quán)系數(shù)。3、給各目標(biāo)賦予相應(yīng)的優(yōu)先因子Pk（k=1.2…K）。2、可根據(jù)決策者的需要，將某些或全部絕對約束轉(zhuǎn)化為目標(biāo)約束。這時只需要給絕對約束加上負(fù)偏差變量和減去正偏差變量即可。建模的步驟1、根據(jù)要研究的問題所提出的各目標(biāo)與條件，確5、根據(jù)決策者的要求，按下列情況之一構(gòu)造

優(yōu)先因子和權(quán)系數(shù)相對應(yīng)的偏差變量組成的，要求實(shí)現(xiàn)極小化的目標(biāo)函數(shù)，即達(dá)成函數(shù)。⑴.恰好達(dá)到目標(biāo)值，取。⑵.允許超過目標(biāo)值，取。⑶.不允許超過目標(biāo)值，取。5、根據(jù)決策者的要求，按下列情況之一構(gòu)造⑴.恰好達(dá)到目標(biāo)

例、某廠計(jì)劃在下一個生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計(jì)劃，使獲得的利潤最大？同時，根據(jù)市場預(yù)測，甲的銷路不是太好，應(yīng)盡可能少生產(chǎn)；乙的銷路較好，可以擴(kuò)大生產(chǎn)。試建立此問題的數(shù)學(xué)模型。12070單件利潤3000103設(shè)備臺時200054煤炭360049鋼材資源限制乙甲單位產(chǎn)品資源消耗例、某廠計(jì)劃在下一個生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已另外提出下列要求：1、完成或超額完成利潤指標(biāo)50000元；2、產(chǎn)品甲不超過200件，產(chǎn)品乙不低于250件；3、現(xiàn)有鋼材3600噸必須用完。試建立目標(biāo)規(guī)劃模型。分析：題目有三個目標(biāo)層次，包含四個目標(biāo)值。第一目標(biāo)：第二目標(biāo)：有兩個要求即甲，乙，但兩個具有相同的優(yōu)先因子，因此需要確定權(quán)系數(shù)。本題可用單件利潤比作為權(quán)系數(shù)即70:120，化簡為7:12。另外提出下列要求：分析：題目有三個目第三目標(biāo)：目標(biāo)規(guī)劃模型為：第三目標(biāo)：目標(biāo)規(guī)劃模型為：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最大的生產(chǎn)方案？ⅠⅡ擁有量原材料2111設(shè)備(臺時)1210單件利潤810在此基礎(chǔ)上考慮：1、產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量；2、充分利用設(shè)備有效臺時，不加班；3、利潤不小于56元。解:分析第一目標(biāo)：即產(chǎn)品Ⅰ的產(chǎn)量不大于Ⅱ的產(chǎn)量。第二目標(biāo)：例三：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。第三目標(biāo)：規(guī)劃模型：第三目標(biāo)：規(guī)劃模型：（三）、小結(jié)線性規(guī)劃LP目標(biāo)規(guī)劃GP目標(biāo)函數(shù)min,max系數(shù)可正負(fù)min,偏差變量系數(shù)≥0變量xi,xsxa

xixsxad約束條件系統(tǒng)約束（絕對約束）目標(biāo)約束系統(tǒng)約束解最優(yōu)最滿意（三）、小結(jié)線性規(guī)劃LP目標(biāo)規(guī)劃GP目標(biāo)函數(shù)min,圖解法同樣適用兩個變量的目標(biāo)規(guī)劃問題，但其操作簡單，原理一目了然。同時，也有助于理解一般目標(biāo)規(guī)劃的求解原理和過程。圖解法解題步驟如下：1、確定各約束條件的可行域，即將所有約束條件（包括目標(biāo)約束和絕對約束，暫不考慮正負(fù)偏差變量）在坐標(biāo)平面上表示出來；2、在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值增大的方向；三、目標(biāo)規(guī)劃的圖解法圖解法同樣適用兩個變量的目標(biāo)規(guī)劃問題，但其操作簡單3、求滿足最高優(yōu)先等級目標(biāo)的解；4、轉(zhuǎn)到下一個優(yōu)先等級的目標(biāo)，在不破壞所有較高優(yōu)先等級目標(biāo)的前提下，求出該優(yōu)先等級目標(biāo)的解；5、重復(fù)4，直到所有優(yōu)先等級的目標(biāo)都已審查完畢為止；6、確定最優(yōu)解和滿意解。例一、用圖解法求解目標(biāo)規(guī)劃問題3、求滿足最高優(yōu)先等級目標(biāo)的解；例一、用圖解法求解012345678123456⑴⑵⑶Ax2

x1BC

B(0.6250,4.6875)C(0,5.2083)，B、C線段上的所有點(diǎn)均是該問題的解（無窮多最優(yōu)解）。01234圖解法x1x2o662x1+2x2=122x1+3x2=157.552x1-x2=04x1=165x2=15（1）繪出直角坐標(biāo)（2）圖示系統(tǒng)約束，確定可行域（3）按優(yōu)先級高低，依次圖示目標(biāo)約束，縮小滿意解范圍。圖解法x1x2o662x1+2x2=122x1+3x2=15例二、已知一個生產(chǎn)計(jì)劃的線性規(guī)劃模型為其中目標(biāo)函數(shù)為總利潤，x1,x2為產(chǎn)品A、B產(chǎn)量。現(xiàn)有下列目標(biāo)：1、要求總利潤必須超過2500元；2、考慮產(chǎn)品受市場影響，為避免積壓，A、B的生產(chǎn)量不超過60件和100件；3、由于甲資源供應(yīng)比較緊張，不要超過現(xiàn)有量140。試建立目標(biāo)規(guī)劃模型，并用圖解法求解。例二、已知一個生產(chǎn)計(jì)劃的線性規(guī)劃模型為其中目標(biāo)解：以產(chǎn)品A、B的單件利潤比2.5：1為權(quán)系數(shù)，模型如下：解：以產(chǎn)品A、B的單件利潤比2.5：1為權(quán)系數(shù)0x2

0⑴x11401201008060402020406080100⑵⑶⑷ABCD結(jié)論：C(60,58.3)為所求的滿意解。作圖：0x20⑴x1140204060檢驗(yàn)：將上述結(jié)果帶入模型，因＝＝0；

＝＝0；

＝0，存在；＝0，存在。所以，有下式：minZ=P3

將x1＝60，x2

＝58.3帶入約束條件，得30×60＋12×58.3＝2499.6≈2500；2×60+58.3=178.3>140；1×60＝601×58.3＝58.3<100由上可知：若A、B的計(jì)劃產(chǎn)量為60件和58.3件時，所需甲資源數(shù)量將超過現(xiàn)有庫存。在現(xiàn)有條件下，此解為非可行解。為此，企業(yè)必須采取措施降低A、B產(chǎn)品對甲資源的消耗量，由原來的100％降至78.5％（140÷178.3＝0.785），才能使生產(chǎn)方案（60，58.3）成為可行方案。檢驗(yàn)：將上述結(jié)果帶入模型，因＝＝練習(xí)：用圖解法求解下列目標(biāo)規(guī)劃問題練習(xí)：用圖解法求解下列目標(biāo)規(guī)劃問題⑴⑵⑶⑷CD結(jié)論：有無窮多最優(yōu)解。C（2，4）D（10/3，10/3）⑴⑵⑶⑷CD結(jié)論：有無窮多最優(yōu)解。C（2，4）D（10/3，Cj

c1c2cn+2mCBXBb

x1x2xn+2m

cj1xj1bo1e11e12e1n+2mcj2xj2bo2e21e22e2n+2mcjmxjm

bomem1em2emn+2mσkjP1

α1σ11σ12σ1n+2mP2

α2σ21σ22σ2n+2mPK

αK

σm1σm2σmn+2m四、目標(biāo)規(guī)劃的單純形法（一）、一般形式：Cjc1c2cn+2mCBXBbx1x2xn+2mc1、建立初始單純形表。一般假定初始解在原點(diǎn)，即以約束條件中的所有負(fù)偏差變量或松弛變量為初始基變量，按目標(biāo)優(yōu)先等級從左至右分別計(jì)算出各列的檢驗(yàn)數(shù)，填入表的下半部。2、檢驗(yàn)是否為滿意解。判別準(zhǔn)則如下：⑴.首先檢查αk

(k=1.2…K)是否全部為零？如果全部為零，則表示目標(biāo)均已全部達(dá)到，獲得滿意解，停止計(jì)算轉(zhuǎn)到第6步；否則轉(zhuǎn)入⑵。

（二）、單純形法的計(jì)算步驟1、建立初始單純形表。2、檢驗(yàn)是否為滿意解。判⑵.如果某一個αk

>0。說明第k個優(yōu)先等級的目標(biāo)尚未達(dá)到,必須檢查Pk這一的檢驗(yàn)數(shù)σkj(j=1.2…n+2m).若Pk這一行某些負(fù)檢驗(yàn)數(shù)的同列上面（較高優(yōu)先等級）沒有正檢驗(yàn)數(shù)，說明未得到滿意解，應(yīng)繼續(xù)改進(jìn)，轉(zhuǎn)到第3步；若Pk這一行全部負(fù)檢驗(yàn)數(shù)的同列上面（較高優(yōu)先等級）都有正檢驗(yàn)數(shù)，說明目標(biāo)雖沒達(dá)到，但已不能改進(jìn)，故得滿意解，轉(zhuǎn)到第6步。3、確定進(jìn)基變量。在Pk行，從那些上面沒有正檢驗(yàn)數(shù)的負(fù)檢驗(yàn)數(shù)中，選絕對值最大者，對應(yīng)的變量xs就是進(jìn)基變量。若Pk行中有幾個相同的絕對值最大者，則依次比較它們各列下部的檢驗(yàn)數(shù)，取其絕對值最大的負(fù)檢驗(yàn)數(shù)的所在列的xs為進(jìn)基變量。假如仍無法確定，則選最左邊的變量（變量下標(biāo)小者）為進(jìn)基變量。⑵.如果某一個αk>0。說明第k個優(yōu)先等級的目標(biāo)尚未4、確定出基變量其方法同線性規(guī)劃，即依據(jù)最小比值法則故確定xr為出基變量，ers為主元素。若有幾個相同的行可供選擇時，選最上面那一行所對應(yīng)得變量為xr。5、旋轉(zhuǎn)變換（變量迭代）。以為主元素進(jìn)行變換，得到新的單純形表，獲得一組新解，返回到第2步。6、對求得的解進(jìn)行分析若計(jì)算結(jié)果滿意，停止運(yùn)算；若不滿意，需修改模型，即調(diào)整目標(biāo)優(yōu)先等級和權(quán)系數(shù)，或者改變目標(biāo)值，重新進(jìn)行第1步。4、確定出基變量5、旋轉(zhuǎn)變換（變量迭代）。

單純形法步驟：第1步列出初始單純形表（1）由于目標(biāo)函數(shù)均為負(fù)值，為方便起見，不轉(zhuǎn)換為極大；（2）以系統(tǒng)約束的松馳變量、人工變量、目標(biāo)約束的負(fù)偏差變量為初始基變量；（3）檢驗(yàn)數(shù)行按優(yōu)先因子分別列出。第2步計(jì)算檢驗(yàn)數(shù)，確定換入變量（1）從第一級優(yōu)級開始，若檢驗(yàn)數(shù)存在負(fù)數(shù)，最小檢驗(yàn)數(shù)所對應(yīng)的變量為換入變量。當(dāng)高級優(yōu)先級得到優(yōu)化，轉(zhuǎn)向下一級；（2）在第k優(yōu)先級優(yōu)化過程中，如果破壞了上級優(yōu)化結(jié)果，則迭代停止，k-1以上級目標(biāo)得到優(yōu)化，k級以下未得到優(yōu)化，所得結(jié)果為滿意解；（3）若所有檢驗(yàn)數(shù)均非負(fù)，所有目標(biāo)均得到優(yōu)化，所得結(jié)果可稱為最優(yōu)解。第3步用最小比值原則確定換出變量第4步用換入變量替換換出變量，用行初等變換方法列出新的單純形表，返回第2步。

單純形法步驟：用單純形法求目標(biāo)規(guī)劃滿意解

用單純形法求目標(biāo)規(guī)劃滿意解

滿意解滿意解例一、用單純形法求解下列目標(biāo)規(guī)劃問題

例一、用單純形法求解下列目標(biāo)規(guī)劃問題

Cj00P1000000000000002.5P20P200000P30000CBXBbx1x2P1250030121－1000000014021001－100000601000001－1000100010000001－1σkjP1

-2500－30－1201000000P2

000000002.501P3

00000010000θ=min｛2500/30,140/2,60/1｝=60,故為換出變量。00P1000000000000002.5P20P20000Cj

00P100P302.5P20P2CBXBbx1x2P17000121－100－30300002001001－1－22000x1601000001－1000100010000001－1σkjP1

－7000－12010030－3000P2

000000002.501P3

00000010000θ=min｛700/30,20/2,－,－｝=10,故為換出變量。Cj00P100P302.5P20P2CBXBbx1x2PCj

00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000x17011/2001/2-1/200000100010000001-1σkjP1

-400030115-150000P2

-250-5/400-5/45/45/2001P3

00000010000θ=min｛400/15,－,－,－｝=10,故為換出變量。Cj00P100P302.5P20P2CBXBbx1x2PCj

00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000x1250/312/51/30-1/300000000100010000001－1σkjP1

00010000000P2

-175/30-1-1/121/12002/5001P3

-80/301/5-1/151/15100000θ=min｛－,350/6,1250/6,100/1｝=75,故為換出變量。Cj00P100P302.5P20P2CBXBbx1x2PCj

00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000x2175/3011/12-1/1200-5/25/2000x160100000-11000125/300-1/121/12005/2-5/21－1σkjP1

00010000000P2

000000005/201P3

-115/300-1/121/12101/2-1/200表中P3＝115/3≠0，說明P3優(yōu)先等級目標(biāo)沒有實(shí)現(xiàn)，但已無法改進(jìn)，得到滿意解

x1＝60，x2＝175/3，＝115/3，＝125/3。Cj00P100P302.5P20P2CBXBbx1x2P

結(jié)果分析：計(jì)算結(jié)果表明，工廠應(yīng)生產(chǎn)A產(chǎn)品60件，B產(chǎn)品175/3件，2500元的利潤目標(biāo)剛好達(dá)到。＝125/3，表明產(chǎn)品比最高限額少125/3件，滿足要求。＝115/3表明甲資源超過庫存115/3公斤，該目標(biāo)沒有達(dá)到。從表中還可以看到，P3的檢驗(yàn)數(shù)還有負(fù)數(shù)，但其高等級的檢驗(yàn)數(shù)卻是正數(shù)，要保證P1目標(biāo)實(shí)現(xiàn)，P3等級目標(biāo)則無法實(shí)現(xiàn)。所以，按現(xiàn)有消耗水平和資源庫存量，無法實(shí)現(xiàn)2500元的利潤目標(biāo)?？煽紤]如下措施：降低A、B產(chǎn)品對甲資源的消耗量，以滿足現(xiàn)有甲資源庫存量的目標(biāo)；或改變P3等級目標(biāo)的指標(biāo)值，增加甲資源115/3公斤。若很難實(shí)現(xiàn)上述措施，則需改變現(xiàn)有目標(biāo)的優(yōu)先等級，以取得可行的滿意解果。結(jié)果分析：計(jì)算結(jié)果表明，工廠應(yīng)生產(chǎn)A產(chǎn)品60件練習(xí)：用單純形法求解下列目標(biāo)規(guī)劃問題練習(xí)：用單純形法求解下列目標(biāo)規(guī)劃問題Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

001－11－100000P21012001－1000

P3

5681000001－100

x3

11210000001σkjP1

0000100000P2

－10－1－20002000P3

－56－8－100000010θ=min｛－,10/2,56/10,11/1｝=5,故為換出變量。Cj000P1P2P2P300CBXBbx1x2Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

023/201－11/2-1/20000x251/21001/2-1/2000

P3

63000-551－100

x3

63/2000-1/21/2001σkjP1

0000100000P2

0000011000P3

－6－30005-5010θ=min｛10/3,10,6/3,12/3｝=2,故為換出變量。Cj000P1P2P2P300CBXBbx1x2Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

02001－13-3-1/21/200x2401004/3-4/3-1/61/600x121000-5/35/31/3-1/300

x3

300002-2-1/21/21σkjP1

0000100000P2

0000011000P3

0000000100最優(yōu)解為x1＝2，x2＝4。但非基變量的檢驗(yàn)數(shù)為零，故此題有無窮多最優(yōu)解。θ=min｛4,24,－,6｝=4,故為換出變量。Cj000P1P2P2P300CBXBbx1x2Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

04002-26-6-1100x210/301-1/31/31/3-1/30000x110/3102/3-2/31/3-1/30000

x3

100-1－1-11001σkjP1

0000100000P2

0000011000P3

0000000100最優(yōu)解為x1＝10/3,，x2=10/3。Cj000P1P2P2P300CBXBbx1x2

1、某廠生產(chǎn)A、B、C三種產(chǎn)品，裝配工作在同一生產(chǎn)線上完成，三種產(chǎn)品時的工時消耗分別為6、8、10小時，生產(chǎn)線每月正常工作時間為200小時；三種產(chǎn)品銷售后，每臺可獲利分別為500、650和800元；每月銷售量預(yù)計(jì)為12、10和6臺。該廠經(jīng)營目標(biāo)如下：1、利潤指標(biāo)為每月16000元，爭取超額完成；2、充分利用現(xiàn)有生產(chǎn)能力；3、可以適當(dāng)加班，但加班時間不得超過24小時；4、產(chǎn)量以預(yù)計(jì)銷售量為準(zhǔn)。試建立目標(biāo)規(guī)劃模型。作業(yè)：作業(yè)：2、用圖解法求解下列目標(biāo)規(guī)劃問題：滿意解為由x1=（3，3）,x2

=（3.5，1.5）所連線段。2、用圖解法求解下列目標(biāo)規(guī)劃問題：滿意解為由x1=（3，3、用圖解法解下列目標(biāo)規(guī)劃模型。x1=400,x2=0,Z=80p33、用圖解法解下列目標(biāo)規(guī)劃模型。x1=400,x0100200300400500100200300400⑴⑵⑶x2

x1401002004、用單純形法求解下列目標(biāo)規(guī)劃問題：x

=（10，20，10）4、用單純形法求解下列目標(biāo)規(guī)劃問題：x=（10，20，10

5、用目標(biāo)規(guī)劃的單純形方法解以下目標(biāo)規(guī)劃模型。

5、x1=12,x2=10,=14,Z=14p4

5、用目標(biāo)規(guī)劃的單純形方法解以下目標(biāo)規(guī)劃模型。答案：答案：習(xí)題1.已知條件如表所示工序型號每周最大加工能力ABⅠ（小時/臺）Ⅱ（小時/臺）436215070利潤（元/臺）300450如果工廠經(jīng)營目標(biāo)的期望值和優(yōu)先等級如下：p1:每周總利潤不得低于10000元；p2:因合同要求，A型機(jī)每周至少生產(chǎn)10臺，B型機(jī)每周至少生產(chǎn)15臺；p3:希望工序Ⅰ的每周生產(chǎn)時間正好為150小時，工序Ⅱ的生產(chǎn)時間最好用足，甚至可適當(dāng)加班。試建立這個問題的目標(biāo)規(guī)劃模型。

習(xí)題型號每周最大ABⅠ（小時/臺）46150利潤（元/臺）研目標(biāo)規(guī)劃2.在上題中，如果工序Ⅱ在加班時間內(nèi)生產(chǎn)出來的產(chǎn)品，每臺A型機(jī)減少利潤10元，每臺B型機(jī)減少利潤25元，并且工序Ⅱ的加班時間每周最多不超過30小時，這是p4級目標(biāo)，試建立這個問題的目標(biāo)規(guī)劃模型。2.在上題中，如果工序Ⅱ在加班時間內(nèi)生產(chǎn)出來的產(chǎn)品設(shè)x1,x2分別為在正常時間和加班時間生產(chǎn)A型機(jī)臺數(shù)，x3,x4分別為在正常時間和加班時間生產(chǎn)B型機(jī)臺數(shù)，目標(biāo)規(guī)劃數(shù)學(xué)模型為：設(shè)x1,x2分別為在正常時間和加班時間生產(chǎn)A3.某紡織廠生產(chǎn)兩種布料，一種用來做服裝，另一種用來做窗簾。該廠實(shí)行兩班生產(chǎn)，每周生產(chǎn)時間定為80小時。這兩種布料每小時都生產(chǎn)1000米。假定每周窗簾布可銷售70000米，每米的利潤為2.5元；衣料布可銷售45000米，每米的利潤為1.5元。該廠在制定生產(chǎn)計(jì)劃時有以下各級目標(biāo)：p1：每周必須用足80小時的生產(chǎn)時間；p2：每周加班時數(shù)不超過10小時；p3：每周銷售窗簾布70000米，衣料布45000米；p4：加班時間盡可能減少。試建立這個問題的目標(biāo)規(guī)劃模型。3.某紡織廠生產(chǎn)兩種布料，一種用來做服裝，另一種用來設(shè)x1,x2分別為每周生產(chǎn)窗簾布和醫(yī)療布的小時數(shù)，目標(biāo)規(guī)劃數(shù)學(xué)模型為：設(shè)x1,x2分別為每周生產(chǎn)窗簾布和醫(yī)療布的小時數(shù)，目標(biāo)規(guī)劃目標(biāo)規(guī)劃(Goalprogramming)目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃概述目標(biāo)規(guī)劃目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)導(dǎo)入案例——產(chǎn)品組合問題產(chǎn)品I產(chǎn)品II設(shè)備A設(shè)備B設(shè)備C240205121615單位利潤23現(xiàn)增加如下考慮：（1）力求使利潤指標(biāo)不低于15元；（2）據(jù)市場預(yù)測，I、II兩種產(chǎn)品需求量的比例大致是1:2；（3）A為貴重設(shè)備，嚴(yán)格禁止超時使用；（4）設(shè)備C可以適當(dāng)加班，但要控制；設(shè)備B既要求充分利用，又盡可能不加班，在重要性上設(shè)備B是C的3倍。綜合考慮上述因素，企業(yè)應(yīng)如何決策？這里本章所要討論的問題。最優(yōu)解：x1=3x2=3z=15若僅考慮利潤目標(biāo)，其LP模型為：導(dǎo)入案例——產(chǎn)品組合問題產(chǎn)品I產(chǎn)品II設(shè)備A2212單位利潤

目標(biāo)規(guī)劃通過引入目標(biāo)值和偏差變量，可以將目標(biāo)函數(shù)轉(zhuǎn)化為目標(biāo)約束。目標(biāo)值：是指預(yù)先給定的某個目標(biāo)的一個期望值。實(shí)現(xiàn)值或決策值：是指當(dāng)決策變量xj

選定以后，目標(biāo)函數(shù)的對應(yīng)值。偏差變量（事先無法確定的未知數(shù)）：是指實(shí)現(xiàn)值和目標(biāo)值之間的差異,記為d。正偏差變量：表示實(shí)現(xiàn)值超過目標(biāo)值的部分，記為d＋。負(fù)偏差變量：表示實(shí)現(xiàn)值未達(dá)到目標(biāo)值的部分，記為d－。1、目標(biāo)值和偏差變量1、目標(biāo)值和偏差變量

當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示：d＋≥0,d－＝0當(dāng)未完成規(guī)定的指標(biāo)則表示：d＋＝0,d－≥0當(dāng)恰好完成指標(biāo)時則表示：d＋＝0,d－＝0∴d＋×d－

＝0成立。

引入了目標(biāo)值和正、負(fù)偏差變量后，就對某一問題有了新的限制，既目標(biāo)約束。目標(biāo)約束即可對原目標(biāo)函數(shù)起作用，也可對原約束起作用。目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束。在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未達(dá)到目標(biāo)值，故有d＋×d－

＝0,并規(guī)定d＋≥0,d－≥02、目標(biāo)約束和絕對約束引入了目標(biāo)值和正、負(fù)偏差變量后，就對絕對約束（系統(tǒng)約束）是指必須嚴(yán)格滿足的等式或不等式約束。如線性規(guī)劃中的所有約束條件都是絕對約束，否則無可行解。所以，絕對約束是硬約束。目標(biāo)規(guī)劃處理問題的方法是將多目標(biāo)轉(zhuǎn)化為多個目標(biāo)約束。如目標(biāo)利潤的約束：甲產(chǎn)品單位利潤2元，乙產(chǎn)品單位利潤3元，目標(biāo)要求利潤不小于15元，即有目標(biāo)約束不等式：添加正負(fù)偏差變量，將其變?yōu)榈仁剑寒?dāng)時，表明，達(dá)到了目標(biāo)；當(dāng)時，表明，未達(dá)到目標(biāo)，此種情況一但發(fā)生，希望越小越好，即目標(biāo)要求為：絕對約束（系統(tǒng)約束）是指必須嚴(yán)格滿足的等式或不等式約束。如線同理有其他目標(biāo)約束：產(chǎn)品比例設(shè)備B利用與加班設(shè)備C的加班同理有其他目標(biāo)約束：

達(dá)成函數(shù)是一個使總偏差量為最小的目標(biāo)函數(shù)，記為minZ=f（d＋、d－）。

一般說來，有以下三種情況，但只能出現(xiàn)其中之一：⑴.要求恰好達(dá)到規(guī)定的目標(biāo)值，即正、負(fù)偏差變量要盡可能小，則minZ=f（d＋＋d－）。⑵.要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，也就是正偏差變量盡可能小，則minZ=f（d＋）。⑶.要求超過目標(biāo)值，即超過量不限，但不低于目標(biāo)值，也就是負(fù)偏差變量盡可能小，則minZ=f（d－）。

對于由絕對約束轉(zhuǎn)化而來的目標(biāo)函數(shù)，也照上述處理即可。3、達(dá)成函數(shù)（即目標(biāo)規(guī)劃中的目標(biāo)函數(shù)）達(dá)成函數(shù)是一個使總偏差量為最小的目標(biāo)函數(shù)，記為m優(yōu)先因子Pk

是將決策目標(biāo)按其重要程度排序并表示出來。P1>>P2>>…>>Pk>>Pk+1>>…>>PK，k=1.2…K。權(quán)系數(shù)ωk區(qū)別具有相同優(yōu)先因子的兩個目標(biāo)的差別，決策者可視具體情況而定。對于這種解來說，前面的目標(biāo)可以保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，而后面的目標(biāo)就不一定能保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，有些可能就不能實(shí)現(xiàn)。4、優(yōu)先因子（優(yōu)先等級）與優(yōu)先權(quán)系數(shù)5、滿意解（具有層次意義的解）優(yōu)先因子Pk是將決策目標(biāo)按其重要程度排序并表示導(dǎo)入案例——產(chǎn)品組合問題產(chǎn)品I產(chǎn)品II設(shè)備A設(shè)備B設(shè)備C240205121615單位利潤23現(xiàn)增加如下考慮：（1）力求使利潤指標(biāo)不低于15元；（2）據(jù)市場預(yù)測，I、II兩種產(chǎn)品需求量的比例大致是1:2；（3）A為貴重設(shè)備，嚴(yán)格禁止超時使用；（4）設(shè)備C可以適當(dāng)加班，但要控制；設(shè)備B既要求充分利用，又盡可能不加班，在重要性上設(shè)備B是C的3倍。綜合考慮上述因素，企業(yè)應(yīng)如何決策？這里本章所要討論的問題。最優(yōu)解：x1=3x2=3z=15若僅考慮利潤目標(biāo)，其LP模型為：導(dǎo)入案例——產(chǎn)品組合問題產(chǎn)品I產(chǎn)品II設(shè)備A2212單位利潤將上述目標(biāo)規(guī)劃的目標(biāo)約束、目標(biāo)函數(shù)再加上系統(tǒng)約束和變量非負(fù)約束，即構(gòu)成了引例中的目標(biāo)規(guī)劃數(shù)學(xué)模型如下：將上述目標(biāo)規(guī)劃的目標(biāo)約束、目標(biāo)函數(shù)再加上系統(tǒng)約束和變量非負(fù)約

目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理中多目標(biāo)決策的需要而逐步發(fā)展起來的一個分支。

2、線性規(guī)劃求最優(yōu)解；目標(biāo)規(guī)劃是找到一個滿意解。1、線性規(guī)劃只討論一個線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題；而目標(biāo)規(guī)劃是多個目標(biāo)決策，可求得更切合實(shí)際的解。目標(biāo)規(guī)劃概述（一）、目標(biāo)規(guī)劃與線性規(guī)劃的比較目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理中多4、線性規(guī)劃的最優(yōu)解是絕對意義下的最優(yōu)，但需花去大量的人力、物力、財(cái)力才能得到；實(shí)際過程中，只要求得滿意解，就能滿足需要（或更能滿足需要）。3、線性規(guī)劃中的約束條件是同等重要的，是硬約束；而目標(biāo)規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。目前，已經(jīng)在經(jīng)濟(jì)計(jì)劃、生產(chǎn)管理、經(jīng)營管理、市場分析、財(cái)務(wù)管理等方面得到了廣泛的應(yīng)用。4、線性規(guī)劃的最優(yōu)解是絕對意義下的最優(yōu)，但需花去大量的人目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式：

優(yōu)先因子正偏差權(quán)系數(shù)負(fù)偏差權(quán)系數(shù)目標(biāo)約束系統(tǒng)約束變量非負(fù)目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式：優(yōu)先因子正偏建模的步驟1、根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約束與絕對約束；4、對同一優(yōu)先等級中的各偏差變量，若需要可按其重要程度的不同，賦予相應(yīng)的權(quán)系數(shù)。3、給各目標(biāo)賦予相應(yīng)的優(yōu)先因子Pk（k=1.2…K）。2、可根據(jù)決策者的需要，將某些或全部絕對約束轉(zhuǎn)化為目標(biāo)約束。這時只需要給絕對約束加上負(fù)偏差變量和減去正偏差變量即可。建模的步驟1、根據(jù)要研究的問題所提出的各目標(biāo)與條件，確5、根據(jù)決策者的要求，按下列情況之一構(gòu)造

優(yōu)先因子和權(quán)系數(shù)相對應(yīng)的偏差變量組成的，要求實(shí)現(xiàn)極小化的目標(biāo)函數(shù)，即達(dá)成函數(shù)。⑴.恰好達(dá)到目標(biāo)值，取。⑵.允許超過目標(biāo)值，取。⑶.不允許超過目標(biāo)值，取。5、根據(jù)決策者的要求，按下列情況之一構(gòu)造⑴.恰好達(dá)到目標(biāo)

例、某廠計(jì)劃在下一個生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計(jì)劃，使獲得的利潤最大？同時，根據(jù)市場預(yù)測，甲的銷路不是太好，應(yīng)盡可能少生產(chǎn)；乙的銷路較好，可以擴(kuò)大生產(chǎn)。試建立此問題的數(shù)學(xué)模型。12070單件利潤3000103設(shè)備臺時200054煤炭360049鋼材資源限制乙甲單位產(chǎn)品資源消耗例、某廠計(jì)劃在下一個生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已另外提出下列要求：1、完成或超額完成利潤指標(biāo)50000元；2、產(chǎn)品甲不超過200件，產(chǎn)品乙不低于250件；3、現(xiàn)有鋼材3600噸必須用完。試建立目標(biāo)規(guī)劃模型。分析：題目有三個目標(biāo)層次，包含四個目標(biāo)值。第一目標(biāo)：第二目標(biāo)：有兩個要求即甲，乙，但兩個具有相同的優(yōu)先因子，因此需要確定權(quán)系數(shù)。本題可用單件利潤比作為權(quán)系數(shù)即70:120，化簡為7:12。另外提出下列要求：分析：題目有三個目第三目標(biāo)：目標(biāo)規(guī)劃模型為：第三目標(biāo)：目標(biāo)規(guī)劃模型為：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最大的生產(chǎn)方案？ⅠⅡ擁有量原材料2111設(shè)備(臺時)1210單件利潤810在此基礎(chǔ)上考慮：1、產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量；2、充分利用設(shè)備有效臺時，不加班；3、利潤不小于56元。解:分析第一目標(biāo)：即產(chǎn)品Ⅰ的產(chǎn)量不大于Ⅱ的產(chǎn)量。第二目標(biāo)：例三：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。第三目標(biāo)：規(guī)劃模型：第三目標(biāo)：規(guī)劃模型：（三）、小結(jié)線性規(guī)劃LP目標(biāo)規(guī)劃GP目標(biāo)函數(shù)min,max系數(shù)可正負(fù)min,偏差變量系數(shù)≥0變量xi,xsxa

xixsxad約束條件系統(tǒng)約束（絕對約束）目標(biāo)約束系統(tǒng)約束解最優(yōu)最滿意（三）、小結(jié)線性規(guī)劃LP目標(biāo)規(guī)劃GP目標(biāo)函數(shù)min,圖解法同樣適用兩個變量的目標(biāo)規(guī)劃問題，但其操作簡單，原理一目了然。同時，也有助于理解一般目標(biāo)規(guī)劃的求解原理和過程。圖解法解題步驟如下：1、確定各約束條件的可行域，即將所有約束條件（包括目標(biāo)約束和絕對約束，暫不考慮正負(fù)偏差變量）在坐標(biāo)平面上表示出來；2、在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值增大的方向；三、目標(biāo)規(guī)劃的圖解法圖解法同樣適用兩個變量的目標(biāo)規(guī)劃問題，但其操作簡單3、求滿足最高優(yōu)先等級目標(biāo)的解；4、轉(zhuǎn)到下一個優(yōu)先等級的目標(biāo)，在不破壞所有較高優(yōu)先等級目標(biāo)的前提下，求出該優(yōu)先等級目標(biāo)的解；5、重復(fù)4，直到所有優(yōu)先等級的目標(biāo)都已審查完畢為止；6、確定最優(yōu)解和滿意解。例一、用圖解法求解目標(biāo)規(guī)劃問題3、求滿足最高優(yōu)先等級目標(biāo)的解；例一、用圖解法求解012345678123456⑴⑵⑶Ax2

x1BC

B(0.6250,4.6875)C(0,5.2083)，B、C線段上的所有點(diǎn)均是該問題的解（無窮多最優(yōu)解）。01234圖解法x1x2o662x1+2x2=122x1+3x2=157.552x1-x2=04x1=165x2=15（1）繪出直角坐標(biāo)（2）圖示系統(tǒng)約束，確定可行域（3）按優(yōu)先級高低，依次圖示目標(biāo)約束，縮小滿意解范圍。圖解法x1x2o662x1+2x2=122x1+3x2=15例二、已知一個生產(chǎn)計(jì)劃的線性規(guī)劃模型為其中目標(biāo)函數(shù)為總利潤，x1,x2為產(chǎn)品A、B產(chǎn)量?，F(xiàn)有下列目標(biāo)：1、要求總利潤必須超過2500元；2、考慮產(chǎn)品受市場影響，為避免積壓，A、B的生產(chǎn)量不超過60件和100件；3、由于甲資源供應(yīng)比較緊張，不要超過現(xiàn)有量140。試建立目標(biāo)規(guī)劃模型，并用圖解法求解。例二、已知一個生產(chǎn)計(jì)劃的線性規(guī)劃模型為其中目標(biāo)解：以產(chǎn)品A、B的單件利潤比2.5：1為權(quán)系數(shù)，模型如下：解：以產(chǎn)品A、B的單件利潤比2.5：1為權(quán)系數(shù)0x2

0⑴x11401201008060402020406080100⑵⑶⑷ABCD結(jié)論：C(60,58.3)為所求的滿意解。作圖：0x20⑴x1140204060檢驗(yàn)：將上述結(jié)果帶入模型，因＝＝0；

＝＝0；

＝0，存在；＝0，存在。所以，有下式：minZ=P3

將x1＝60，x2

＝58.3帶入約束條件，得30×60＋12×58.3＝2499.6≈2500；2×60+58.3=178.3>140；1×60＝601×58.3＝58.3<100由上可知：若A、B的計(jì)劃產(chǎn)量為60件和58.3件時，所需甲資源數(shù)量將超過現(xiàn)有庫存。在現(xiàn)有條件下，此解為非可行解。為此，企業(yè)必須采取措施降低A、B產(chǎn)品對甲資源的消耗量，由原來的100％降至78.5％（140÷178.3＝0.785），才能使生產(chǎn)方案（60，58.3）成為可行方案。檢驗(yàn)：將上述結(jié)果帶入模型，因＝＝練習(xí)：用圖解法求解下列目標(biāo)規(guī)劃問題練習(xí)：用圖解法求解下列目標(biāo)規(guī)劃問題⑴⑵⑶⑷CD結(jié)論：有無窮多最優(yōu)解。C（2，4）D（10/3，10/3）⑴⑵⑶⑷CD結(jié)論：有無窮多最優(yōu)解。C（2，4）D（10/3，Cj

c1c2cn+2mCBXBb

x1x2xn+2m

cj1xj1bo1e11e12e1n+2mcj2xj2bo2e21e22e2n+2mcjmxjm

bomem1em2emn+2mσkjP1

α1σ11σ12σ1n+2mP2

α2σ21σ22σ2n+2mPK

αK

σm1σm2σmn+2m四、目標(biāo)規(guī)劃的單純形法（一）、一般形式：Cjc1c2cn+2mCBXBbx1x2xn+2mc1、建立初始單純形表。一般假定初始解在原點(diǎn)，即以約束條件中的所有負(fù)偏差變量或松弛變量為初始基變量，按目標(biāo)優(yōu)先等級從左至右分別計(jì)算出各列的檢驗(yàn)數(shù)，填入表的下半部。2、檢驗(yàn)是否為滿意解。判別準(zhǔn)則如下：⑴.首先檢查αk

(k=1.2…K)是否全部為零？如果全部為零，則表示目標(biāo)均已全部達(dá)到，獲得滿意解，停止計(jì)算轉(zhuǎn)到第6步；否則轉(zhuǎn)入⑵。

（二）、單純形法的計(jì)算步驟1、建立初始單純形表。2、檢驗(yàn)是否為滿意解。判⑵.如果某一個αk

>0。說明第k個優(yōu)先等級的目標(biāo)尚未達(dá)到,必須檢查Pk這一的檢驗(yàn)數(shù)σkj(j=1.2…n+2m).若Pk這一行某些負(fù)檢驗(yàn)數(shù)的同列上面（較高優(yōu)先等級）沒有正檢驗(yàn)數(shù)，說明未得到滿意解，應(yīng)繼續(xù)改進(jìn)，轉(zhuǎn)到第3步；若Pk這一行全部負(fù)檢驗(yàn)數(shù)的同列上面（較高優(yōu)先等級）都有正檢驗(yàn)數(shù)，說明目標(biāo)雖沒達(dá)到，但已不能改進(jìn)，故得滿意解，轉(zhuǎn)到第6步。3、確定進(jìn)基變量。在Pk行，從那些上面沒有正檢驗(yàn)數(shù)的負(fù)檢驗(yàn)數(shù)中，選絕對值最大者，對應(yīng)的變量xs就是進(jìn)基變量。若Pk行中有幾個相同的絕對值最大者，則依次比較它們各列下部的檢驗(yàn)數(shù)，取其絕對值最大的負(fù)檢驗(yàn)數(shù)的所在列的xs為進(jìn)基變量。假如仍無法確定，則選最左邊的變量（變量下標(biāo)小者）為進(jìn)基變量。⑵.如果某一個αk>0。說明第k個優(yōu)先等級的目標(biāo)尚未4、確定出基變量其方法同線性規(guī)劃，即依據(jù)最小比值法則故確定xr為出基變量，ers為主元素。若有幾個相同的行可供選擇時，選最上面那一行所對應(yīng)得變量為xr。5、旋轉(zhuǎn)變換（變量迭代）。以為主元素進(jìn)行變換，得到新的單純形表，獲得一組新解，返回到第2步。6、對求得的解進(jìn)行分析若計(jì)算結(jié)果滿意，停止運(yùn)算；若不滿意，需修改模型，即調(diào)整目標(biāo)優(yōu)先等級和權(quán)系數(shù)，或者改變目標(biāo)值，重新進(jìn)行第1步。4、確定出基變量5、旋轉(zhuǎn)變換（變量迭代）。

單純形法步驟：第1步列出初始單純形表（1）由于目標(biāo)函數(shù)均為負(fù)值，為方便起見，不轉(zhuǎn)換為極大；（2）以系統(tǒng)約束的松馳變量、人工變量、目標(biāo)約束的負(fù)偏差變量為初始基變量；（3）檢驗(yàn)數(shù)行按優(yōu)先因子分別列出。第2步計(jì)算檢驗(yàn)數(shù)，確定換入變量（1）從第一級優(yōu)級開始，若檢驗(yàn)數(shù)存在負(fù)數(shù)，最小檢驗(yàn)數(shù)所對應(yīng)的變量為換入變量。當(dāng)高級優(yōu)先級得到優(yōu)化，轉(zhuǎn)向下一級；（2）在第k優(yōu)先級優(yōu)化過程中，如果破壞了上級優(yōu)化結(jié)果，則迭代停止，k-1以上級目標(biāo)得到優(yōu)化，k級以下未得到優(yōu)化，所得結(jié)果為滿意解；（3）若所有檢驗(yàn)數(shù)均非負(fù)，所有目標(biāo)均得到優(yōu)化，所得結(jié)果可稱為最優(yōu)解。第3步用最小比值原則確定換出變量第4步用換入變量替換換出變量，用行初等變換方法列出新的單純形表，返回第2步。

單純形法步驟：用單純形法求目標(biāo)規(guī)劃滿意解

用單純形法求目標(biāo)規(guī)劃滿意解

滿意解滿意解例一、用單純形法求解下列目標(biāo)規(guī)劃問題

例一、用單純形法求解下列目標(biāo)規(guī)劃問題

Cj00P1000000000000002.5P20P200000P30000CBXBbx1x2P1250030121－1000000014021001－100000601000001－1000100010000001－1σkjP1

-2500－30－1201000000P2

000000002.501P3

00000010000θ=min｛2500/30,140/2,60/1｝=60,故為換出變量。00P1000000000000002.5P20P20000Cj

00P100P302.5P20P2CBXBbx1x2P17000121－100－30300002001001－1－22000x1601000001－1000100010000001－1σkjP1

－7000－12010030－3000P2

000000002.501P3

00000010000θ=min｛700/30,20/2,－,－｝=10,故為換出變量。Cj00P100P302.5P20P2CBXBbx1x2PCj

00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000x17011/2001/2-1/200000100010000001-1σkjP1

-400030115-150000P2

-250-5/400-5/45/45/2001P3

00000010000θ=min｛400/15,－,－,－｝=10,故為換出變量。Cj00P100P302.5P20P2CBXBbx1x2PCj

00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000x1250/312/51/30-1/300000000100010000001－1σkjP1

00010000000P2

-175/30-1-1/121/12002/5001P3

-80/301/5-1/151/15100000θ=min｛－,350/6,1250/6,100/1｝=75,故為換出變量。Cj00P100P302.5P20P2CBXBbx1x2PCj

00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000x2175/3011/12-1/1200-5/25/2000x160100000-11000125/300-1/121/12005/2-5/21－1σkjP1

00010000000P2

000000005/201P3

-115/300-1/121/12101/2-1/200表中P3＝115/3≠0，說明P3優(yōu)先等級目標(biāo)沒有實(shí)現(xiàn)，但已無法改進(jìn)，得到滿意解

x1＝60，x2＝175/3，＝115/3，＝125/3。Cj00P100P302.5P20P2CBXBbx1x2P

結(jié)果分析：計(jì)算結(jié)果表明，工廠應(yīng)生產(chǎn)A產(chǎn)品60件，B產(chǎn)品175/3件，2500元的利潤目標(biāo)剛好達(dá)到。＝125/3，表明產(chǎn)品比最高限額少125/3件，滿足要求。＝115/3表明甲資源超過庫存115/3公斤，該目標(biāo)沒有達(dá)到。從表中還可以看到，P3的檢驗(yàn)數(shù)還有負(fù)數(shù)，但其高等級的檢驗(yàn)數(shù)卻是正數(shù)，要保證P1目標(biāo)實(shí)現(xiàn)，P3等級目標(biāo)則無法實(shí)現(xiàn)。所以，按現(xiàn)有消耗水平和資源庫存量，無法實(shí)現(xiàn)2500元的利潤目標(biāo)。可考慮如下措施：降低A、B產(chǎn)品對甲資源的消耗量，以滿足現(xiàn)有甲資源庫存量的目標(biāo)；或改變P3等級目標(biāo)的指標(biāo)值，增加甲資源115/3公斤。若很難實(shí)現(xiàn)上述措施，則需改變現(xiàn)有目標(biāo)的優(yōu)先等級，以取得可行的滿意解果。結(jié)果分析：計(jì)算結(jié)果表明，工廠應(yīng)生產(chǎn)A產(chǎn)品60件練習(xí)：用單純形法求解下列目標(biāo)規(guī)劃問題練習(xí)：用單純形法求解下列目標(biāo)規(guī)劃問題Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

001－11－100000P21012001－1000

P3

5681000001－100

x3

11210000001σkjP1

0000100000P2

－10－1－20002000P3

－56－8－100000010θ=min｛－,10/2,56/10,11/1｝=5,故為換出變量。Cj000P1P2P2P300CBXBbx1x2Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

023/201－11/2-1/20000x251/21001/2-1/2000

P3

63000-551－100