運(yùn)籌學(xué)-目標(biāo)規(guī)劃分析課件

運(yùn)籌學(xué)第四章目標(biāo)規(guī)劃

運(yùn)籌學(xué)第四章目標(biāo)規(guī)劃第四章目標(biāo)規(guī)劃

目標(biāo)規(guī)劃的求解方法本章內(nèi)容目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的靈敏度分析及應(yīng)用舉例目的：掌握目標(biāo)規(guī)劃的數(shù)學(xué)模型及求解理解目標(biāo)規(guī)劃的靈敏度分析第四章目標(biāo)規(guī)劃目標(biāo)規(guī)劃的求解方法本章內(nèi)容目標(biāo)規(guī)劃的數(shù)學(xué)模例1、某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計(jì)劃，使獲得的利潤(rùn)最大，試建立數(shù)學(xué)模型。

引言：12070單件利潤(rùn)3000103設(shè)備臺(tái)時(shí)200054煤炭360049鋼材資源限制乙甲單位產(chǎn)品資源消耗例1、某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料例2、某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計(jì)劃，使獲得的利潤(rùn)最大。試建立數(shù)學(xué)模型。

12070單件利潤(rùn)3000103設(shè)備臺(tái)時(shí)200054煤炭360049鋼材資源限制乙甲單位產(chǎn)品資源消耗要求：1、完成或超額完成利潤(rùn)指標(biāo)50000元；2、產(chǎn)品甲不超過200件，產(chǎn)品乙不低于250件；3、現(xiàn)有鋼材3600噸用完。例2、某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料第一節(jié)目標(biāo)規(guī)劃的數(shù)學(xué)模型第一節(jié)目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)實(shí)際問題中多目標(biāo)決策的需要而逐步發(fā)展起來的一個(gè)分支。

2、線性規(guī)劃要求問題的解必須嚴(yán)格滿足全部約束條件，但實(shí)際問題中并非所有約束都需嚴(yán)格滿足；目標(biāo)規(guī)劃無此要求。

1、線性規(guī)劃只討論一個(gè)線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題；而目標(biāo)規(guī)劃是多個(gè)目標(biāo)決策，可求得更切合實(shí)際的解。一、目標(biāo)規(guī)劃概述（一）目標(biāo)規(guī)劃與線性規(guī)劃的比較目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)實(shí)際問題中多

5、線性規(guī)劃的最優(yōu)解是絕對(duì)意義下的最優(yōu)，但需花去大量的人力、物力、財(cái)力才能得到；實(shí)際過程中，只要求得滿意解，就能滿足需要（或更能滿足需要）。

4、線性規(guī)劃中的約束條件是同等重要的，是硬約束；而目標(biāo)規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。目前，已經(jīng)在經(jīng)濟(jì)計(jì)劃、生產(chǎn)管理、經(jīng)營(yíng)管理、市場(chǎng)分析、財(cái)務(wù)管理等方面得到了廣泛的應(yīng)用。

3、線性規(guī)劃求最優(yōu)解；目標(biāo)規(guī)劃是找到一個(gè)滿意解。5、線性規(guī)劃的最優(yōu)解是絕對(duì)意義下的最優(yōu)，但需花去大量的人目標(biāo)值：是指預(yù)先給定的某個(gè)目標(biāo)的一個(gè)期望值。1、目標(biāo)值和偏差變量（二）目標(biāo)規(guī)劃的基本概念偏差變量（事先無法確定的未知數(shù)）：是指實(shí)現(xiàn)值和目標(biāo)值之間的差異,記為d。正偏差變量：表示實(shí)現(xiàn)值超過目標(biāo)值的部分，記為d＋。負(fù)偏差變量：表示實(shí)現(xiàn)值未達(dá)到目標(biāo)值的部分，記為d－。目標(biāo)值：是指預(yù)先給定的某個(gè)目標(biāo)的一個(gè)期望值。1、目標(biāo)值和偏差

當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示：當(dāng)未完成規(guī)定的指標(biāo)則表示：當(dāng)恰好完成指標(biāo)時(shí)則表示：在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未達(dá)到目標(biāo)值，故有d＋×d－

＝0,并規(guī)定d＋≥0,d－≥0注意：目標(biāo)規(guī)劃中，一般有多個(gè)目標(biāo)值，每個(gè)目標(biāo)值都相應(yīng)有一對(duì)偏差變量。

d＋≥0,d－＝0d＋＝0,d－≥0d＋＝0,d－＝0在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未達(dá)2、絕對(duì)約束和目標(biāo)約束

絕對(duì)約束：是指必須嚴(yán)格滿足的等式約束或不等式約束；如線性規(guī)劃問題的所有約束條件，不能滿足這些條件的解稱為非可行解，所以絕對(duì)約束是硬約束。目標(biāo)約束：是目標(biāo)規(guī)劃所特有的一種約束，它把要追求的目標(biāo)值作為右端常數(shù)項(xiàng)，在追求此目標(biāo)值時(shí)允許發(fā)生正偏差和負(fù)偏差。因此，目標(biāo)約束是由決策變量，正、負(fù)偏差變量和要追求的目標(biāo)值組成的軟約束。2、絕對(duì)約束和目標(biāo)約束絕對(duì)約束：是指必須嚴(yán)格滿足的等式約束優(yōu)先因子Pk

是將決策目標(biāo)按其重要程度排序并表示出來。P1>>P2>>…>>Pk>>Pk+1>>，k=1.2…N。3、優(yōu)先因子（優(yōu)先等級(jí)）與優(yōu)先權(quán)系數(shù)權(quán)系數(shù)ωk

區(qū)別具有相同優(yōu)先因子的兩個(gè)目標(biāo)的差別，決策者可視具體情況而定。解釋：>>表示Pk比Pk+1有更大的優(yōu)先級(jí)。優(yōu)先因子Pk是將決策目標(biāo)按其重要程度排序并表示

目標(biāo)函數(shù)是按各目標(biāo)約束的正、負(fù)偏差變量和賦予相應(yīng)的優(yōu)先因子及權(quán)系數(shù)而構(gòu)造的。4、目標(biāo)函數(shù)⑴要求恰好達(dá)到規(guī)定的目標(biāo)值：⑵要求不超過目標(biāo)值：彈性約束基本形式：⑶要求超過目標(biāo)值：則min(d＋＋d－)則min(d＋)則min(d－)目標(biāo)函數(shù)是按各目標(biāo)約束的正、負(fù)偏差變量和賦予相應(yīng)的對(duì)于這種解來說，前面的目標(biāo)可以保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，而后面的目標(biāo)就不一定能保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，有些可能就不能實(shí)現(xiàn)。

5、滿意解（具有層次意義的解）對(duì)于這種解來說，前面的目標(biāo)可以保證實(shí)現(xiàn)或部分（三）目標(biāo)規(guī)劃的數(shù)學(xué)模型（三）目標(biāo)規(guī)劃的數(shù)學(xué)模型

例2、某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計(jì)劃，使獲得的利潤(rùn)最大？試建立數(shù)學(xué)模型。

12070單件利潤(rùn)3000103設(shè)備臺(tái)時(shí)200054煤炭360049鋼材資源限制乙甲單位產(chǎn)品資源消耗要求：1、完成或超額完成利潤(rùn)指標(biāo)50000元；2、產(chǎn)品甲不超過200件，產(chǎn)品乙不低于250件；3、現(xiàn)有鋼材3600噸用完。例2、某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，目標(biāo)規(guī)劃模型為：分析：目標(biāo)規(guī)劃模型為：分析：例一分析：題目有三個(gè)目標(biāo)層次，包含四個(gè)目標(biāo)值。第一目標(biāo)：第二目標(biāo)：有兩個(gè)要求即甲，乙，但兩個(gè)具有相同的優(yōu)先因子。本題可用單件利潤(rùn)比作為權(quán)系數(shù)即70:120，化簡(jiǎn)為7:12。第三目標(biāo)：例一分析：題目有三個(gè)目標(biāo)層次，包含四個(gè)目標(biāo)值。第目標(biāo)規(guī)劃模型為：目標(biāo)規(guī)劃模型為：例3：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最大的生產(chǎn)方案？ⅠⅡ擁有量原材料2111設(shè)備(臺(tái)時(shí))1210單件利潤(rùn)810在此基礎(chǔ)上考慮：1、產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量；2、充分利用設(shè)備有效臺(tái)時(shí)，不加班；3、利潤(rùn)不小于56元。例3：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最目標(biāo)：1、產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量；2、充分利用設(shè)備有效臺(tái)時(shí)，不加班；3、利潤(rùn)不小于56元。目標(biāo)： 第一目標(biāo)：即產(chǎn)品Ⅰ的產(chǎn)量不大于Ⅱ的產(chǎn)量。第二目標(biāo)：第三目標(biāo)：目標(biāo)：1、產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量；2、充分利用設(shè)備有效臺(tái)時(shí)，不加班；3、利潤(rùn)不小于56元。目標(biāo)函數(shù)：+++=-+--)(min3322211dPddPdPZ 第一目標(biāo)：第二目標(biāo)：第三目標(biāo)：目標(biāo)：目標(biāo)目標(biāo)規(guī)劃模型為：目標(biāo)規(guī)劃模型為：課堂練習(xí)某廠生產(chǎn)A、B、C三種產(chǎn)品，裝配工作在同一生產(chǎn)線上完成，三種產(chǎn)品的工時(shí)消耗分別為6、8、10小時(shí)，生產(chǎn)線每月正常工作時(shí)間為200小時(shí)；三種產(chǎn)品銷售后，每臺(tái)可獲利分別為500、650和800元；每月銷售量預(yù)計(jì)為12、10和6臺(tái)。該廠經(jīng)營(yíng)目標(biāo)如下：1、利潤(rùn)指標(biāo)為每月16000元，爭(zhēng)取超額完成；2、充分利用現(xiàn)有生產(chǎn)能力；3、可以適當(dāng)加班，但加班時(shí)間不超過24小時(shí)；4、產(chǎn)量以預(yù)計(jì)銷售量為準(zhǔn)。試建立目標(biāo)規(guī)劃模型。課堂練習(xí)某廠生產(chǎn)A、B、C三種產(chǎn)品，裝配工作在同一生答案：答案：（四）小結(jié)線性規(guī)劃LP目標(biāo)規(guī)劃GP目標(biāo)函數(shù)min,max系數(shù)可正負(fù)min,偏差變量系數(shù)≥0變量決策變量

決策變量

d約束條件絕對(duì)約束目標(biāo)約束絕對(duì)約束解最優(yōu)最滿意（四）小結(jié)線性規(guī)劃LP目標(biāo)規(guī)劃GP目標(biāo)函數(shù)min,第二節(jié)解目標(biāo)規(guī)劃的圖解法第二節(jié)解目標(biāo)規(guī)劃的圖解法引例：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最大的生產(chǎn)方案？ⅠⅡ擁有量原材料2111設(shè)備(臺(tái)時(shí))1210單件利潤(rùn)810在此基礎(chǔ)上考慮：1、產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量；2、充分利用設(shè)備有效臺(tái)時(shí)，不加班；3、利潤(rùn)不小于56元。引例：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最目標(biāo)規(guī)劃模型為：目標(biāo)規(guī)劃模型為：圖解法解題步驟如下：步驟1建立直角坐標(biāo)系，令各偏差變量為0，作出所有的約束直線。滿足所有絕對(duì)約束條件的區(qū)域，用陰影標(biāo)出。圖解法解題步驟如下：步驟1建立直角坐標(biāo)系，令各偏差變量為步驟2作圖表示偏差變量增減對(duì)約束直線的影響在所有目標(biāo)約束直線旁標(biāo)上

d+，d-，步驟2作圖表示偏差變量增減對(duì)約束直線的影響在所有目標(biāo)約步驟3根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子次序，逐步分析求解。步驟3根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子次序，逐步分析求解。步驟3根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子次序，逐步分析求解。根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子次序，首先考慮具有優(yōu)先因子p1的目標(biāo)的實(shí)現(xiàn)。目標(biāo)函數(shù)要求實(shí)現(xiàn)mind1+，從圖中可見，可以滿足d1+=0，這時(shí)，只能在三角形OBC的區(qū)域上取值；考察具有優(yōu)先因子p2的目標(biāo)，此時(shí)可在線段ED上取值；考察優(yōu)先因子p3的目標(biāo)，這就使取值范圍縮小到線段GD上，該線段上所有點(diǎn)的坐標(biāo)，都是問題的解，G(2,4)D(10/3,10/3)。步驟3根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子次序，逐步分析求解。例1、用圖解法求解目標(biāo)規(guī)劃問題例1、用圖解法求解目標(biāo)規(guī)劃問題012345678123456⑶x2

x1⑴⑵BC

B(0.6250,4.6875)C(0,5.2083)，B、C

線段上的所有點(diǎn)均是該問題的解（無窮多最優(yōu)解）。01234例2、已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型為其中目標(biāo)函數(shù)為總利潤(rùn)，x1，x2

為產(chǎn)品A、B產(chǎn)量。現(xiàn)有下列目標(biāo)：1、要求總利潤(rùn)必須超過2500元；2、考慮產(chǎn)品受市場(chǎng)影響，為避免積壓，A、B的生產(chǎn)量不超過60件和100件；3、由于甲資源供應(yīng)比較緊張，不要超過現(xiàn)有量140。試建立目標(biāo)規(guī)劃模型，并用圖解法求解。例2、已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型為其中目標(biāo)函數(shù)解：以產(chǎn)品A、B的單件利潤(rùn)比2.5：1為權(quán)系數(shù)，模型如下：解：以產(chǎn)品A、B的單件利潤(rùn)比2.5：1為權(quán)系數(shù)0x2

0x11401201008060402020406080100⑵⑴3⑷作圖：0x20x1140204060x2

x1140120100806040202040608010000⑵⑴⑶⑷ABC結(jié)論：C(60,58.3)為所求的滿意解。作圖：x2x11402040608第三節(jié)解目標(biāo)規(guī)劃的單純形法第三節(jié)解目標(biāo)規(guī)劃的單純形法

目標(biāo)規(guī)劃的數(shù)學(xué)模型與線性規(guī)劃的數(shù)學(xué)模型基本相同，因此利用單純形法求解步驟也基本相同，但是需要尤其注意它們之間的區(qū)別。線性規(guī)劃的單純形法求解過程(目標(biāo)函數(shù)極大化情況下)：1.建立初始單純形表，計(jì)算出所有變量的檢驗(yàn)數(shù)；

2.在非基變量檢驗(yàn)數(shù)中找到最大的正數(shù)σj，它所對(duì)應(yīng)的變量xj作為換入基的變量；

3.對(duì)于所有aij>0計(jì)算bi/aij其中最小的元素θ所對(duì)應(yīng)的基變量xi

作為換出基的變量；

4.建立新單純形表，重復(fù)上述步驟2、3，直到所有檢驗(yàn)數(shù)都小于等于零。目標(biāo)規(guī)劃的數(shù)學(xué)模型與線性規(guī)劃的數(shù)學(xué)模型基本相由于目標(biāo)規(guī)劃的目標(biāo)函數(shù)都是求極小化問題，而線性規(guī)劃問題的標(biāo)準(zhǔn)型中目標(biāo)函數(shù)是求極大化問題，因此在用單純形法求解時(shí)要注意一些重要的的差別。例1用單純形法求解下述目標(biāo)規(guī)劃問題：由于目標(biāo)規(guī)劃的目標(biāo)函數(shù)都是求極小化問題，而線性規(guī)劃問第一步：列出初始單純形表，并計(jì)算檢驗(yàn)數(shù)。

將表格中最后一行檢驗(yàn)數(shù)按優(yōu)先級(jí)改寫為：

（這是與線性規(guī)劃單純形法的第一個(gè)差別）第一步：列出初始單純形表，并計(jì)算檢驗(yàn)數(shù)。將表第二步：確定換入基的變量。在負(fù)檢驗(yàn)數(shù)中，選擇最小的一個(gè)σj所對(duì)應(yīng)的變量xj作為換入基的變量(第二個(gè)差別)。第三步：確定換出基的變量（這與線性規(guī)劃相同）。第二步：確定換入基的變量。在負(fù)檢驗(yàn)數(shù)中，選擇最小的一個(gè)

第四步：用換入變量替換換出變量，進(jìn)行單純形法迭代運(yùn)算，直至優(yōu)先級(jí)P1所對(duì)應(yīng)的檢驗(yàn)數(shù)全為非負(fù)。本例中，第一優(yōu)先級(jí)計(jì)算后得：由于優(yōu)先級(jí)P2的檢驗(yàn)數(shù)仍然有負(fù)值，因此可以繼續(xù)優(yōu)化，重復(fù)上述步驟2-4。第四步：用換入變量替換換出變量，進(jìn)行單純形法迭代運(yùn)算，直至確定換入、換出變量：第一點(diǎn)說明：目標(biāo)函數(shù)按優(yōu)先級(jí)順序進(jìn)行優(yōu)化，當(dāng)P1行所有檢驗(yàn)數(shù)非負(fù)時(shí)，說明第一級(jí)已經(jīng)優(yōu)化，可以轉(zhuǎn)入下一級(jí)，考察P2行檢驗(yàn)數(shù)，依此類推。確定換入、換出變量：第一點(diǎn)說明：第二點(diǎn)說明：從考察P2行檢驗(yàn)數(shù)開始，注意應(yīng)把更高級(jí)別的優(yōu)先因子考慮在內(nèi)。如上述問題的進(jìn)一步單純形表如下：對(duì)應(yīng)的檢驗(yàn)數(shù)為P1+(–3/2)P2>0對(duì)應(yīng)的檢驗(yàn)數(shù)為P1–P2>0對(duì)應(yīng)的檢驗(yàn)數(shù)為P1–2P2>0因此上述三種情況都不能選為換入基的變量，這其實(shí)與線性規(guī)劃相同。第二點(diǎn)說明：從考察P2行檢驗(yàn)數(shù)開始，注意應(yīng)把更高

判別迭代計(jì)算停止的準(zhǔn)則：(1)檢驗(yàn)數(shù)P1,P2,…,Pk行的所有值均為非負(fù)；(2)若P1,P2,…,Pi行的所有檢驗(yàn)數(shù)為非負(fù)而Pi+1行存在負(fù)檢驗(yàn)數(shù)，但在負(fù)檢驗(yàn)數(shù)所在列的上面行中有正檢驗(yàn)數(shù)（不一定是相鄰行，只要在其上方即可）。判別迭代計(jì)算停止的準(zhǔn)則：(1)檢驗(yàn)數(shù)P1,P例2：用單純形法求解下列目標(biāo)規(guī)劃問題：

解：

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

cj000

P100

P2

P30

CB

XB

b

x1

x2

x30

x3605101000000

P10[1]-201-10000036440001-100

P34868000001-1

P1-120010000

P2000000100

P3-6-80000001cj000P10

cj000

P100

P2

P30

CB

XB

b

x1

x2

x30

x3605101000000

P10[1]-201-10000036440001-100

P34868000001-1

P1-120010000

P2000000100

P3-6-80000001cj000P10

cj000

P100

P2

P30

CB

XB

b

x1

x2

x30

x3605101000000

P10[1]-201-10000036440001-100

P34868000001-1

P1-120010000

P2000000100

P3-6-800000010

x3600201-5500000

x101-201-100000360120-441-100

P3480[20]0-66001-1

P1000100000

P2000000100

P30-2006-60001cj000P10

cj000

P100

P2

P30

CB

XB

b

x1

x2

x30

x3600201-5500000

x101-201-100000360120-441-100

P3480[20]0-66001-1

P1000100000

P2000000100

P30-2006-600010

x3120011-100-110

x124/51002/5-2/5001/10-1/10036/5000-2/52/51-1-3/53/50

x212/5010-3/103/10001/20-1/20

P1000100000

P2000000100

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

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

Cj00P100002.5P20P2CBXBbx1x2P1250030121－1000000014021001－100000601000001－1000100010000001－1σkjP1

－30－1201000000P2

00000002.501P3

0000010000θ=min｛2500/30,140/2,60/1｝=60,故為換出變量。Cj00P100002.5P20P2CBXBbx1x2P12Cj

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

0－12010030－3000P2

00000002.501P3

0000010000θ=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

030115-150000P2

0-5/400-5/45/45/2001P3

0000010000θ=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

0010000000P2

0-1-1/121/12002/5001P3

01/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

0010000000P2

00000005/201P3

00-1/121/12101/2-1/200滿意解x1*=60，x2*=175/3。Cj00P100P302.5P20P2CBXBbx1x2P目標(biāo)規(guī)劃的靈敏度分析所討論內(nèi)容包括：1、約束條件（目標(biāo)約束和硬約束）右端常數(shù)的變化；2、約束條件中各變量系數(shù)的變化；3、加入新的變量（決策變量和偏差變量）；4、加入新的約束條件；5、目標(biāo)函數(shù)中偏差變量的優(yōu)先等級(jí)及權(quán)系數(shù)的變化；第四節(jié)靈敏度分析目標(biāo)規(guī)劃的靈敏度分析所討論內(nèi)容包括：1、約束條件（目標(biāo)約束和已知目標(biāo)規(guī)劃問題：已知目標(biāo)規(guī)劃問題：XBCjP31P3

1-22-33P2

32P1

σkj-1111-112P2-112-23-318-11141-1-1116x1x2x1bx2CBP23P12P1表1:XBCjP31P31-22-33P232P1-1111目標(biāo)函數(shù)的優(yōu)先等級(jí)變化為：(1)minz=P1(2d1++3d2+)+P2d4++P3d3-(2)minz=P1d3-+P2(2d1++3d2+)+P3d4+試分析原解有什么變化。目標(biāo)函數(shù)的優(yōu)先等級(jí)變化為：XBCjP31P3

1-22-33P2

32P1

σkj-1111-112P2-112-23-318-11141-1-1116x1x2x1bx2CBP23P12P1原：minz=P1(2d1++3d2+)+P2d3-+P3d4+分析(1):XBCjP31P31-22-33P232P1-1111XBCjP21-22-33P3

1P2

32P1

σkj-1111-112P3-112-23-318-11141-1-1116x1x2x1bx2CBP33P12P1新1:

minz=P1(2d1++3d2+)+P2d4++P3d3-將原目標(biāo)函數(shù)中d4+，d3-的優(yōu)先因子對(duì)換了一下。只需對(duì)表1的檢驗(yàn)數(shù)中的P2、P3行和cj行的P2、P3對(duì)換即可。表1:XBCjP21-22-33P31P232P1-1111XBCjP31P3

32P2

1-22-33P1

σkj-1111-12P1-112-23-318-11141-1-1116x1x2x1bx2CBP13P22P2表2:然后繼續(xù)進(jìn)行迭代新2:minz=P1d3-

+P2(2d1++3d2+)

+P3d4+分析(2):XBCjP31P332P21-22-33P1-1111XBCjP31/3-1/3-2/32/3P3

32P2

1P1

σkj-1/31/32/3-2/31-16P31-1-1/31/32/3-2/34-1114-1/31/35/3-5/3112x1x2x1bx2CBP13P22P2表3:從表3中得到新的滿意解x1*=4，x2*=12。XBCjP31/3-1/3-2/32/3P332P21P作業(yè)P1114.2(2)P1124.4(1)、(2)作業(yè)P1114.2(2)例：某公司生產(chǎn)A、B兩種藥品，這兩種藥品每小時(shí)的產(chǎn)量均為1000盒，該公司每天采用兩班制生產(chǎn)，每周最大工作時(shí)間為80小時(shí)，按預(yù)測(cè)每周市場(chǎng)最大銷量分別為70000盒和45000盒．A種藥每盒的利潤(rùn)為2.5元，B種為1.5元．試確定公司每周A、B兩種藥品生產(chǎn)量x1和x2（單位：千盒），使公司的下列目標(biāo)得以實(shí)現(xiàn)：

P1：避免每周80小時(shí)生產(chǎn)能力的過少使用．

P2：加班的時(shí)間盡量限制在10小時(shí)以內(nèi)．

P3：A、B兩種藥品的每周產(chǎn)量盡量分別達(dá)到70000盒和45000盒，但不得超出，其權(quán)系數(shù)依它們每盒的利潤(rùn)為準(zhǔn)．

P4：盡量減少加班時(shí)間．應(yīng)用舉例例：某公司生產(chǎn)A、B兩種藥品，這兩種藥品每小時(shí)的產(chǎn)量均為10解：先建立這個(gè)問題的線性規(guī)劃模型，依題意分別建立各項(xiàng)目標(biāo)約束權(quán)系數(shù)是指它們?cè)谀繕?biāo)函數(shù)中的重要程度，由2.5∶1.5=5∶3，故：目標(biāo)函數(shù)為：建立單純形表運(yùn)算如下：解：先建立這個(gè)問題的線性規(guī)劃模型，依題意分別建立各項(xiàng)目標(biāo)約束

cj00

P1

5P33P3

0

P4

P2

CB

XB

b

x1

x2

P1

80111000-105P370[1]00100003P345010010000100000011-1

P1-1-1000010

P200000001

P3-5-3000000

P400000010

P1

100[1]1-100-100

x170100100003P345010010000100000011-1

P10-1010010

P200000001

P30-3050000

P400000010cj00P15P33P

cj00

P15P33P30

P4

P2

CB

XB

b

x1

x2

P1

100[1]1-100-100

x170100100003P345010010000100000011-1

P10-1010010

P200000001

P30-3050000

P4000000100

x210011-100-100

x170100100003P33500-111010010000001[1]-1

P100100000

P200000001

P3003200-30

P400000010cj00P15P33P

cj00

P1

5P33P30

P4

P2

CB

XB

b

x1

x2

0

x210011-100-100

x170100100003P33500-111010010000001[1]-1

P100100000

P200000001

P3003200-30

P4000000100

x220011-101010

x170100100003P32500-111-101

P4100000011-1

P100100000

P200000001

P30032030-3

P400000-101cj00P15P33P3從而得最優(yōu)解為：x1=70x2=20即生產(chǎn)A種藥品70000盒，B種藥品20000盒，P1，P2，P3級(jí)目標(biāo)可完全實(shí)現(xiàn)．因，故每周需加班10小時(shí)，每周利潤(rùn)為:70000×2.5+20000×1.5=205000（元）．從而得最優(yōu)解為：x1=70x2=20運(yùn)籌學(xué)第四章目標(biāo)規(guī)劃

運(yùn)籌學(xué)第四章目標(biāo)規(guī)劃第四章目標(biāo)規(guī)劃

目標(biāo)規(guī)劃的求解方法本章內(nèi)容目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的靈敏度分析及應(yīng)用舉例目的：掌握目標(biāo)規(guī)劃的數(shù)學(xué)模型及求解理解目標(biāo)規(guī)劃的靈敏度分析第四章目標(biāo)規(guī)劃目標(biāo)規(guī)劃的求解方法本章內(nèi)容目標(biāo)規(guī)劃的數(shù)學(xué)模例1、某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計(jì)劃，使獲得的利潤(rùn)最大，試建立數(shù)學(xué)模型。

引言：12070單件利潤(rùn)3000103設(shè)備臺(tái)時(shí)200054煤炭360049鋼材資源限制乙甲單位產(chǎn)品資源消耗例1、某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料例2、某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計(jì)劃，使獲得的利潤(rùn)最大。試建立數(shù)學(xué)模型。

12070單件利潤(rùn)3000103設(shè)備臺(tái)時(shí)200054煤炭360049鋼材資源限制乙甲單位產(chǎn)品資源消耗要求：1、完成或超額完成利潤(rùn)指標(biāo)50000元；2、產(chǎn)品甲不超過200件，產(chǎn)品乙不低于250件；3、現(xiàn)有鋼材3600噸用完。例2、某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料第一節(jié)目標(biāo)規(guī)劃的數(shù)學(xué)模型第一節(jié)目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)實(shí)際問題中多目標(biāo)決策的需要而逐步發(fā)展起來的一個(gè)分支。

2、線性規(guī)劃要求問題的解必須嚴(yán)格滿足全部約束條件，但實(shí)際問題中并非所有約束都需嚴(yán)格滿足；目標(biāo)規(guī)劃無此要求。

1、線性規(guī)劃只討論一個(gè)線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題；而目標(biāo)規(guī)劃是多個(gè)目標(biāo)決策，可求得更切合實(shí)際的解。一、目標(biāo)規(guī)劃概述（一）目標(biāo)規(guī)劃與線性規(guī)劃的比較目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)實(shí)際問題中多

5、線性規(guī)劃的最優(yōu)解是絕對(duì)意義下的最優(yōu)，但需花去大量的人力、物力、財(cái)力才能得到；實(shí)際過程中，只要求得滿意解，就能滿足需要（或更能滿足需要）。

4、線性規(guī)劃中的約束條件是同等重要的，是硬約束；而目標(biāo)規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。目前，已經(jīng)在經(jīng)濟(jì)計(jì)劃、生產(chǎn)管理、經(jīng)營(yíng)管理、市場(chǎng)分析、財(cái)務(wù)管理等方面得到了廣泛的應(yīng)用。

3、線性規(guī)劃求最優(yōu)解；目標(biāo)規(guī)劃是找到一個(gè)滿意解。5、線性規(guī)劃的最優(yōu)解是絕對(duì)意義下的最優(yōu)，但需花去大量的人目標(biāo)值：是指預(yù)先給定的某個(gè)目標(biāo)的一個(gè)期望值。1、目標(biāo)值和偏差變量（二）目標(biāo)規(guī)劃的基本概念偏差變量（事先無法確定的未知數(shù)）：是指實(shí)現(xiàn)值和目標(biāo)值之間的差異,記為d。正偏差變量：表示實(shí)現(xiàn)值超過目標(biāo)值的部分，記為d＋。負(fù)偏差變量：表示實(shí)現(xiàn)值未達(dá)到目標(biāo)值的部分，記為d－。目標(biāo)值：是指預(yù)先給定的某個(gè)目標(biāo)的一個(gè)期望值。1、目標(biāo)值和偏差

當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示：當(dāng)未完成規(guī)定的指標(biāo)則表示：當(dāng)恰好完成指標(biāo)時(shí)則表示：在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未達(dá)到目標(biāo)值，故有d＋×d－

＝0,并規(guī)定d＋≥0,d－≥0注意：目標(biāo)規(guī)劃中，一般有多個(gè)目標(biāo)值，每個(gè)目標(biāo)值都相應(yīng)有一對(duì)偏差變量。

d＋≥0,d－＝0d＋＝0,d－≥0d＋＝0,d－＝0在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未達(dá)2、絕對(duì)約束和目標(biāo)約束

絕對(duì)約束：是指必須嚴(yán)格滿足的等式約束或不等式約束；如線性規(guī)劃問題的所有約束條件，不能滿足這些條件的解稱為非可行解，所以絕對(duì)約束是硬約束。目標(biāo)約束：是目標(biāo)規(guī)劃所特有的一種約束，它把要追求的目標(biāo)值作為右端常數(shù)項(xiàng)，在追求此目標(biāo)值時(shí)允許發(fā)生正偏差和負(fù)偏差。因此，目標(biāo)約束是由決策變量，正、負(fù)偏差變量和要追求的目標(biāo)值組成的軟約束。2、絕對(duì)約束和目標(biāo)約束絕對(duì)約束：是指必須嚴(yán)格滿足的等式約束優(yōu)先因子Pk

是將決策目標(biāo)按其重要程度排序并表示出來。P1>>P2>>…>>Pk>>Pk+1>>，k=1.2…N。3、優(yōu)先因子（優(yōu)先等級(jí)）與優(yōu)先權(quán)系數(shù)權(quán)系數(shù)ωk

區(qū)別具有相同優(yōu)先因子的兩個(gè)目標(biāo)的差別，決策者可視具體情況而定。解釋：>>表示Pk比Pk+1有更大的優(yōu)先級(jí)。優(yōu)先因子Pk是將決策目標(biāo)按其重要程度排序并表示

目標(biāo)函數(shù)是按各目標(biāo)約束的正、負(fù)偏差變量和賦予相應(yīng)的優(yōu)先因子及權(quán)系數(shù)而構(gòu)造的。4、目標(biāo)函數(shù)⑴要求恰好達(dá)到規(guī)定的目標(biāo)值：⑵要求不超過目標(biāo)值：彈性約束基本形式：⑶要求超過目標(biāo)值：則min(d＋＋d－)則min(d＋)則min(d－)目標(biāo)函數(shù)是按各目標(biāo)約束的正、負(fù)偏差變量和賦予相應(yīng)的對(duì)于這種解來說，前面的目標(biāo)可以保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，而后面的目標(biāo)就不一定能保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，有些可能就不能實(shí)現(xiàn)。

5、滿意解（具有層次意義的解）對(duì)于這種解來說，前面的目標(biāo)可以保證實(shí)現(xiàn)或部分（三）目標(biāo)規(guī)劃的數(shù)學(xué)模型（三）目標(biāo)規(guī)劃的數(shù)學(xué)模型

例2、某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計(jì)劃，使獲得的利潤(rùn)最大？試建立數(shù)學(xué)模型。

12070單件利潤(rùn)3000103設(shè)備臺(tái)時(shí)200054煤炭360049鋼材資源限制乙甲單位產(chǎn)品資源消耗要求：1、完成或超額完成利潤(rùn)指標(biāo)50000元；2、產(chǎn)品甲不超過200件，產(chǎn)品乙不低于250件；3、現(xiàn)有鋼材3600噸用完。例2、某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，目標(biāo)規(guī)劃模型為：分析：目標(biāo)規(guī)劃模型為：分析：例一分析：題目有三個(gè)目標(biāo)層次，包含四個(gè)目標(biāo)值。第一目標(biāo)：第二目標(biāo)：有兩個(gè)要求即甲，乙，但兩個(gè)具有相同的優(yōu)先因子。本題可用單件利潤(rùn)比作為權(quán)系數(shù)即70:120，化簡(jiǎn)為7:12。第三目標(biāo)：例一分析：題目有三個(gè)目標(biāo)層次，包含四個(gè)目標(biāo)值。第目標(biāo)規(guī)劃模型為：目標(biāo)規(guī)劃模型為：例3：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最大的生產(chǎn)方案？ⅠⅡ擁有量原材料2111設(shè)備(臺(tái)時(shí))1210單件利潤(rùn)810在此基礎(chǔ)上考慮：1、產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量；2、充分利用設(shè)備有效臺(tái)時(shí)，不加班；3、利潤(rùn)不小于56元。例3：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最目標(biāo)：1、產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量；2、充分利用設(shè)備有效臺(tái)時(shí)，不加班；3、利潤(rùn)不小于56元。目標(biāo)： 第一目標(biāo)：即產(chǎn)品Ⅰ的產(chǎn)量不大于Ⅱ的產(chǎn)量。第二目標(biāo)：第三目標(biāo)：目標(biāo)：1、產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量；2、充分利用設(shè)備有效臺(tái)時(shí)，不加班；3、利潤(rùn)不小于56元。目標(biāo)函數(shù)：+++=-+--)(min3322211dPddPdPZ 第一目標(biāo)：第二目標(biāo)：第三目標(biāo)：目標(biāo)：目標(biāo)目標(biāo)規(guī)劃模型為：目標(biāo)規(guī)劃模型為：課堂練習(xí)某廠生產(chǎn)A、B、C三種產(chǎn)品，裝配工作在同一生產(chǎn)線上完成，三種產(chǎn)品的工時(shí)消耗分別為6、8、10小時(shí)，生產(chǎn)線每月正常工作時(shí)間為200小時(shí)；三種產(chǎn)品銷售后，每臺(tái)可獲利分別為500、650和800元；每月銷售量預(yù)計(jì)為12、10和6臺(tái)。該廠經(jīng)營(yíng)目標(biāo)如下：1、利潤(rùn)指標(biāo)為每月16000元，爭(zhēng)取超額完成；2、充分利用現(xiàn)有生產(chǎn)能力；3、可以適當(dāng)加班，但加班時(shí)間不超過24小時(shí)；4、產(chǎn)量以預(yù)計(jì)銷售量為準(zhǔn)。試建立目標(biāo)規(guī)劃模型。課堂練習(xí)某廠生產(chǎn)A、B、C三種產(chǎn)品，裝配工作在同一生答案：答案：（四）小結(jié)線性規(guī)劃LP目標(biāo)規(guī)劃GP目標(biāo)函數(shù)min,max系數(shù)可正負(fù)min,偏差變量系數(shù)≥0變量決策變量

決策變量

d約束條件絕對(duì)約束目標(biāo)約束絕對(duì)約束解最優(yōu)最滿意（四）小結(jié)線性規(guī)劃LP目標(biāo)規(guī)劃GP目標(biāo)函數(shù)min,第二節(jié)解目標(biāo)規(guī)劃的圖解法第二節(jié)解目標(biāo)規(guī)劃的圖解法引例：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最大的生產(chǎn)方案？ⅠⅡ擁有量原材料2111設(shè)備(臺(tái)時(shí))1210單件利潤(rùn)810在此基礎(chǔ)上考慮：1、產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量；2、充分利用設(shè)備有效臺(tái)時(shí)，不加班；3、利潤(rùn)不小于56元。引例：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最目標(biāo)規(guī)劃模型為：目標(biāo)規(guī)劃模型為：圖解法解題步驟如下：步驟1建立直角坐標(biāo)系，令各偏差變量為0，作出所有的約束直線。滿足所有絕對(duì)約束條件的區(qū)域，用陰影標(biāo)出。圖解法解題步驟如下：步驟1建立直角坐標(biāo)系，令各偏差變量為步驟2作圖表示偏差變量增減對(duì)約束直線的影響在所有目標(biāo)約束直線旁標(biāo)上

d+，d-，步驟2作圖表示偏差變量增減對(duì)約束直線的影響在所有目標(biāo)約步驟3根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子次序，逐步分析求解。步驟3根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子次序，逐步分析求解。步驟3根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子次序，逐步分析求解。根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子次序，首先考慮具有優(yōu)先因子p1的目標(biāo)的實(shí)現(xiàn)。目標(biāo)函數(shù)要求實(shí)現(xiàn)mind1+，從圖中可見，可以滿足d1+=0，這時(shí)，只能在三角形OBC的區(qū)域上取值；考察具有優(yōu)先因子p2的目標(biāo)，此時(shí)可在線段ED上取值；考察優(yōu)先因子p3的目標(biāo)，這就使取值范圍縮小到線段GD上，該線段上所有點(diǎn)的坐標(biāo)，都是問題的解，G(2,4)D(10/3,10/3)。步驟3根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子次序，逐步分析求解。例1、用圖解法求解目標(biāo)規(guī)劃問題例1、用圖解法求解目標(biāo)規(guī)劃問題012345678123456⑶x2

x1⑴⑵BC

B(0.6250,4.6875)C(0,5.2083)，B、C

線段上的所有點(diǎn)均是該問題的解（無窮多最優(yōu)解）。01234例2、已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型為其中目標(biāo)函數(shù)為總利潤(rùn)，x1，x2

為產(chǎn)品A、B產(chǎn)量?，F(xiàn)有下列目標(biāo)：1、要求總利潤(rùn)必須超過2500元；2、考慮產(chǎn)品受市場(chǎng)影響，為避免積壓，A、B的生產(chǎn)量不超過60件和100件；3、由于甲資源供應(yīng)比較緊張，不要超過現(xiàn)有量140。試建立目標(biāo)規(guī)劃模型，并用圖解法求解。例2、已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型為其中目標(biāo)函數(shù)解：以產(chǎn)品A、B的單件利潤(rùn)比2.5：1為權(quán)系數(shù)，模型如下：解：以產(chǎn)品A、B的單件利潤(rùn)比2.5：1為權(quán)系數(shù)0x2

0x11401201008060402020406080100⑵⑴3⑷作圖：0x20x1140204060x2

x1140120100806040202040608010000⑵⑴⑶⑷ABC結(jié)論：C(60,58.3)為所求的滿意解。作圖：x2x11402040608第三節(jié)解目標(biāo)規(guī)劃的單純形法第三節(jié)解目標(biāo)規(guī)劃的單純形法

目標(biāo)規(guī)劃的數(shù)學(xué)模型與線性規(guī)劃的數(shù)學(xué)模型基本相同，因此利用單純形法求解步驟也基本相同，但是需要尤其注意它們之間的區(qū)別。線性規(guī)劃的單純形法求解過程(目標(biāo)函數(shù)極大化情況下)：1.建立初始單純形表，計(jì)算出所有變量的檢驗(yàn)數(shù)；

2.在非基變量檢驗(yàn)數(shù)中找到最大的正數(shù)σj，它所對(duì)應(yīng)的變量xj作為換入基的變量；

3.對(duì)于所有aij>0計(jì)算bi/aij其中最小的元素θ所對(duì)應(yīng)的基變量xi

作為換出基的變量；

4.建立新單純形表，重復(fù)上述步驟2、3，直到所有檢驗(yàn)數(shù)都小于等于零。目標(biāo)規(guī)劃的數(shù)學(xué)模型與線性規(guī)劃的數(shù)學(xué)模型基本相由于目標(biāo)規(guī)劃的目標(biāo)函數(shù)都是求極小化問題，而線性規(guī)劃問題的標(biāo)準(zhǔn)型中目標(biāo)函數(shù)是求極大化問題，因此在用單純形法求解時(shí)要注意一些重要的的差別。例1用單純形法求解下述目標(biāo)規(guī)劃問題：由于目標(biāo)規(guī)劃的目標(biāo)函數(shù)都是求極小化問題，而線性規(guī)劃問第一步：列出初始單純形表，并計(jì)算檢驗(yàn)數(shù)。

將表格中最后一行檢驗(yàn)數(shù)按優(yōu)先級(jí)改寫為：

（這是與線性規(guī)劃單純形法的第一個(gè)差別）第一步：列出初始單純形表，并計(jì)算檢驗(yàn)數(shù)。將表第二步：確定換入基的變量。在負(fù)檢驗(yàn)數(shù)中，選擇最小的一個(gè)σj所對(duì)應(yīng)的變量xj作為換入基的變量(第二個(gè)差別)。第三步：確定換出基的變量（這與線性規(guī)劃相同）。第二步：確定換入基的變量。在負(fù)檢驗(yàn)數(shù)中，選擇最小的一個(gè)

第四步：用換入變量替換換出變量，進(jìn)行單純形法迭代運(yùn)算，直至優(yōu)先級(jí)P1所對(duì)應(yīng)的檢驗(yàn)數(shù)全為非負(fù)。本例中，第一優(yōu)先級(jí)計(jì)算后得：由于優(yōu)先級(jí)P2的檢驗(yàn)數(shù)仍然有負(fù)值，因此可以繼續(xù)優(yōu)化，重復(fù)上述步驟2-4。第四步：用換入變量替換換出變量，進(jìn)行單純形法迭代運(yùn)算，直至確定換入、換出變量：第一點(diǎn)說明：目標(biāo)函數(shù)按優(yōu)先級(jí)順序進(jìn)行優(yōu)化，當(dāng)P1行所有檢驗(yàn)數(shù)非負(fù)時(shí)，說明第一級(jí)已經(jīng)優(yōu)化，可以轉(zhuǎn)入下一級(jí)，考察P2行檢驗(yàn)數(shù)，依此類推。確定換入、換出變量：第一點(diǎn)說明：第二點(diǎn)說明：從考察P2行檢驗(yàn)數(shù)開始，注意應(yīng)把更高級(jí)別的優(yōu)先因子考慮在內(nèi)。如上述問題的進(jìn)一步單純形表如下：對(duì)應(yīng)的檢驗(yàn)數(shù)為P1+(–3/2)P2>0對(duì)應(yīng)的檢驗(yàn)數(shù)為P1–P2>0對(duì)應(yīng)的檢驗(yàn)數(shù)為P1–2P2>0因此上述三種情況都不能選為換入基的變量，這其實(shí)與線性規(guī)劃相同。第二點(diǎn)說明：從考察P2行檢驗(yàn)數(shù)開始，注意應(yīng)把更高

判別迭代計(jì)算停止的準(zhǔn)則：(1)檢驗(yàn)數(shù)P1,P2,…,Pk行的所有值均為非負(fù)；(2)若P1,P2,…,Pi行的所有檢驗(yàn)數(shù)為非負(fù)而Pi+1行存在負(fù)檢驗(yàn)數(shù)，但在負(fù)檢驗(yàn)數(shù)所在列的上面行中有正檢驗(yàn)數(shù)（不一定是相鄰行，只要在其上方即可）。判別迭代計(jì)算停止的準(zhǔn)則：(1)檢驗(yàn)數(shù)P1,P例2：用單純形法求解下列目標(biāo)規(guī)劃問題：

解：

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

cj000

P100

P2

P30

CB

XB

b

x1

x2

x30

x3605101000000

P10[1]-201-10000036440001-100

P34868000001-1

P1-120010000

P2000000100

P3-6-80000001cj000P10

cj000

P100

P2

P30

CB

XB

b

x1

x2

x30

x3605101000000

P10[1]-201-10000036440001-100

P34868000001-1

P1-120010000

P2000000100

P3-6-80000001cj000P10

cj000

P100

P2

P30

CB

XB

b

x1

x2

x30

x3605101000000

P10[1]-201-10000036440001-100

P34868000001-1

P1-120010000

P2000000100

P3-6-800000010

x3600201-5500000

x101-201-100000360120-441-100

P3480[20]0-66001-1

P1000100000

P2000000100

P30-2006-60001cj000P10

cj000

P100

P2

P30

CB

XB

b

x1

x2

x30

x3600201-5500000

x101-201-100000360120-441-100

P3480[20]0-66001-1

P1000100000

P2000000100

P30-2006-600010

x3120011-100-110

x124/51002/5-2/5001/10-1/10036/5000-2/52/51-1-3/53/50

x212/5010-3/103/10001/20-1/20

P1000100000

P2000000100

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

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

Cj00P100002.5P20P2CBXBbx1x2P1250030121－1000000014021001－100000601000001－1000100010000001－1σkjP1

－30－1201000000P2

00000002.501P3

0000010000θ=min｛2500/30,140/2,60/1｝=60,故為換出變量。Cj00P100002.5P20P2CBXBbx1x2P12Cj

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

0－12010030－3000P2

00000002.501P3

0000010000θ=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

030115-150000P2

0-5/400-5/45/45/2001P3

0000010000θ=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

0010000000P2

0-1-1/121/12002/5001P3

01/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

0010000000P2

00000005/201P3

00-1/121/12101/2-1/200滿意解x1*=60，x2*=175/3。Cj00P100P302.5P20P2CBXBbx1x2P目標(biāo)規(guī)劃的靈敏度分析所討論內(nèi)容包括：1、約束條件（目標(biāo)約束和硬約束）右端常數(shù)的變化；2、約束條件中各變量系數(shù)的變化；3、加入新的變量（決策變量和偏差變量）；4、加入新的約束條件；5、目標(biāo)函數(shù)中偏差變量的優(yōu)先等級(jí)及權(quán)系數(shù)的變化；第四節(jié)靈敏度分析目標(biāo)規(guī)劃的靈敏度分析所討論內(nèi)容包括：1、約束條件（目標(biāo)約束和已知目標(biāo)規(guī)劃問題：已知目標(biāo)規(guī)劃問題：XBCjP31P3

1-22-3