《系統(tǒng)工程》課件第04章 目標(biāo)規(guī)劃

第4章

目標(biāo)規(guī)劃4.1目標(biāo)規(guī)劃的數(shù)學(xué)模型4.2目標(biāo)規(guī)劃的圖解法4.3解目標(biāo)規(guī)劃的單純形法4.4靈敏度分析4.5應(yīng)用舉例14:17

第4章

目標(biāo)規(guī)劃【知識(shí)點(diǎn)聚焦】

本章主要介紹目標(biāo)規(guī)劃的數(shù)學(xué)模型建立，目標(biāo)規(guī)劃問題的圖解法、目標(biāo)規(guī)劃問題的單純形解法；分析約束式右邊值改變時(shí)，目標(biāo)函數(shù)的靈敏度分析問題；并通過應(yīng)用舉例，說明目標(biāo)規(guī)劃問題重要性。4.1目標(biāo)規(guī)劃的數(shù)學(xué)模型4.1.1 多目標(biāo)規(guī)劃簡(jiǎn)介

多目標(biāo)問題最早是Franklin在1772年提出來的，1938年Cournot提出了多目標(biāo)問題的經(jīng)濟(jì)學(xué)模型，1896年P(guān)areto首次從數(shù)學(xué)的角度提出多目標(biāo)最優(yōu)化問題。當(dāng)今，多目標(biāo)規(guī)劃也受到了人們的普遍重視。

在工農(nóng)業(yè)生產(chǎn)中，常常需要考慮某些限制條件下，多個(gè)目標(biāo)的最優(yōu)化問題。下面舉例說明：14:17

第4章

目標(biāo)規(guī)劃

【例4-1】生產(chǎn)計(jì)劃問題。某工廠生產(chǎn)

種產(chǎn)品：1號(hào)產(chǎn)品，2號(hào)產(chǎn)品，…，n號(hào)產(chǎn)品。已知：該廠生產(chǎn)

號(hào)產(chǎn)品的生產(chǎn)能力是

；生產(chǎn)1ti號(hào)產(chǎn)品可獲利潤(rùn)

元；據(jù)市場(chǎng)預(yù)測(cè)，下月i號(hào)產(chǎn)品的最大銷量為

；工廠下月的開工工時(shí)能力為

；下月市場(chǎng)需要盡可能多的1號(hào)產(chǎn)品。問：應(yīng)如何安排下月的生產(chǎn)計(jì)劃，在避免開工不足的條件下，使工人加班的時(shí)間盡量地少；工廠獲得最大利潤(rùn)；滿足市場(chǎng)對(duì)1號(hào)產(chǎn)品的盡可能多的需求。解：為制訂下月的生產(chǎn)計(jì)劃，該廠下月生產(chǎn)i號(hào)產(chǎn)品的時(shí)間為

。根據(jù)已知條件，將問題中希望追求的3個(gè)目標(biāo)用數(shù)量關(guān)系描述如下：（1）因?yàn)橄略掠?/p>

xih時(shí)間生產(chǎn)

i號(hào)產(chǎn)品

，所以工廠生產(chǎn)的總工時(shí)為

，工人的加班時(shí)間為

，按照要求，工人的加班時(shí)間盡可能的短，就使14:17

第4章

目標(biāo)規(guī)劃（2）下月該廠i號(hào)產(chǎn)品的產(chǎn)量為aixit，可獲得的利潤(rùn)為aiaix元

，故工廠的總利潤(rùn)為

元，按照要求工廠獲得最大利潤(rùn)，就使（3）下月1號(hào)產(chǎn)品的產(chǎn)量為，要滿足市場(chǎng)對(duì)1號(hào)產(chǎn)品盡可能多的需求，就使

此外，由預(yù)測(cè)得知下月i號(hào)產(chǎn)品的最大銷售量為

，所以i號(hào)產(chǎn)品的產(chǎn)量aixi不能超過bi，即

為避免工廠開工不足，生產(chǎn)總工時(shí)應(yīng)不低于開工能力T，即

。同時(shí)，考慮到生產(chǎn)時(shí)間不可能為負(fù)值，故，結(jié)合以上討論，所考慮的生產(chǎn)計(jì)劃問題可歸納為以下3個(gè)目標(biāo)的最優(yōu)化問題：14:17

第4章

目標(biāo)規(guī)劃若令則上面的最優(yōu)化問題又可化為(4-1)的形式。這里，x，f(x)皆為向量。14:17

第4章

目標(biāo)規(guī)劃

為了與單目標(biāo)規(guī)劃區(qū)別起見，用

來表示一般多目標(biāo)最優(yōu)化問題。其中，R表示約束集合（或稱可行域）；f(x)表示向量目標(biāo)函數(shù)；稱

是式(4-1)的可行解。

【例4-2】

投資決策問題。某投資開發(fā)公司擁有總資金A萬元，今有

個(gè)項(xiàng)目可供選擇投資。設(shè)投資第

個(gè)項(xiàng)目要用資金ai萬元，預(yù)計(jì)可獲得收益bi萬元，問應(yīng)如何決策投資方案。解：一個(gè)好的投資方案應(yīng)該是投資少、收益大。設(shè)，稱它們?yōu)橥顿Y決策變量。按問題所給的條件，投資第i個(gè)項(xiàng)目的金額應(yīng)為

萬元

，故總投資金額為

萬元。根據(jù)題目要求所使用的資金盡可能地少，應(yīng)使同時(shí)，為獲得最大收益，又應(yīng)滿足以下條件14:17

第4章

目標(biāo)規(guī)劃此外，考慮到該公司總資金額為A萬元，又應(yīng)滿足以下限制條件又因?yàn)?/p>

只能取1或0值，所以還要滿足

綜上所述，所考慮的投資決策問題可歸納為對(duì)兩個(gè)目標(biāo)中的一個(gè)極小化，另一個(gè)極大化。14:17

第4章

目標(biāo)規(guī)劃

多目標(biāo)優(yōu)化問題的例子很多。例如，設(shè)計(jì)貨船，人們通常要考慮選取船舶的航速率最大，年貨運(yùn)量最多，運(yùn)輸成本最低等多個(gè)目標(biāo)都盡可能好的方案；為制訂國家的經(jīng)濟(jì)發(fā)展規(guī)劃，在一定條件下就需要考慮以生產(chǎn)、消費(fèi)、就業(yè)、投資回收率等項(xiàng)目的多個(gè)目標(biāo)的最優(yōu)化問題；為合理使用醫(yī)院的血庫，也會(huì)遇到要考慮血液的庫存量、血液平均壽命以及血液收集費(fèi)用等多個(gè)目標(biāo)的最優(yōu)化問題。在實(shí)際應(yīng)用中，具有多個(gè)目標(biāo)的最優(yōu)化問題舉不勝舉。

在把實(shí)際問題建立成多目標(biāo)規(guī)劃模型時(shí)，應(yīng)注意以下3點(diǎn)：（1）決策變量選擇并確定所考慮問題的供選方案，并把它們用一組變量表示出來。這些變量取不同的一組值對(duì)應(yīng)著問題的一個(gè)不同方案。（2）目標(biāo)函數(shù)按照決策者的意圖，對(duì)問題提出期望要極小化或極大化的若干個(gè)目標(biāo)（指標(biāo)），它們是決策變量的函數(shù)，并且一起組成一個(gè)向量目標(biāo)函數(shù)。（3）約束條件尋找并建立決策變量必須滿足的所有限制條件，并用含有決策變量的不等式或等式表示出來。

基本概念建立多目標(biāo)規(guī)劃的目的，是為了通過求解這一規(guī)劃模型來解決現(xiàn)實(shí)中的問題。要求出多目標(biāo)規(guī)劃的最優(yōu)解，首先應(yīng)知道到底符合什么條件的可行解才是最優(yōu)解？14:17

第4章

目標(biāo)規(guī)劃

在單目標(biāo)規(guī)劃中，其最優(yōu)解可以通過求目標(biāo)函數(shù)的極小值來獲得。很自然地，希望能夠?qū)文繕?biāo)規(guī)劃最優(yōu)解的概念推廣到多目標(biāo)規(guī)劃中去。但是，直接地搬用是不行的，因?yàn)椋也坏竭@樣一個(gè)

，使得向量函數(shù)

在

的某個(gè)鄰域

內(nèi)滿足

，

。

例如，向量函數(shù)

，

。顯然，

的唯一極大值點(diǎn)為0，而

的唯一極大值點(diǎn)為1，

因此，

不可能找出一個(gè)點(diǎn)能滿足：

既是

的極大值點(diǎn)，又是

的極大值點(diǎn)。

因此，單目標(biāo)規(guī)劃中最優(yōu)解的定義在多目標(biāo)規(guī)劃中就不適用了。為克服這一缺點(diǎn)，必須相應(yīng)地引入新的概念，當(dāng)然，我們自然希望當(dāng)多目標(biāo)規(guī)劃變?yōu)閱文繕?biāo)規(guī)劃時(shí)，它們各自的最優(yōu)解的概念應(yīng)是一致的。

首先，為比較向量函數(shù)值的“大”、“小”，引入向量空間中向量間的比較關(guān)系，即“序”的關(guān)系。14:17

第4章

目標(biāo)規(guī)劃【定義4-1】

設(shè)

，

是m維歐氏空間

中的兩個(gè)向量。（1）若

，則稱向量a等于向量b，記作a=b。（2）若

，則稱向量a小于等于向量b，記作

或

。（3）若

，并且其中至少有一個(gè)是嚴(yán)格不等式，則稱向量a小于向量b，記作

或

。（4）若

，則稱向量a嚴(yán)格小于向量b，記作

或

。

一般地，都定義【定義4-1】的序關(guān)系為自然序。特別地，當(dāng)

時(shí)，自然序和實(shí)數(shù)序是一致的。下面利用向量的自然序，來給出一般多目標(biāo)極大化模型的有效解的概念。

【定義4-2】

設(shè)

是式（4-1）的約束集，

是多目標(biāo)優(yōu)化問題式（4-1）的向量目標(biāo)函數(shù)。若

，并且不存在

使得

，則稱

是多目標(biāo)優(yōu)化問題式（4-1）的有效解，也稱做Pareto解、非劣解或滿意解等。14:17

第4章

目標(biāo)規(guī)劃4.1.2以多目標(biāo)規(guī)劃模型建立目標(biāo)規(guī)劃模型

設(shè)有m個(gè)目標(biāo)函數(shù)：

，對(duì)應(yīng)的目標(biāo)值為

。為了使各個(gè)目標(biāo)函數(shù)都盡可能地達(dá)到或接近于它們對(duì)應(yīng)的目標(biāo)值，要考慮記，則上述在約束條件

下考慮各逼近其對(duì)應(yīng)目標(biāo)值

的問題可記作（4-2）

式（4-2）稱為逼近目標(biāo)規(guī)劃模型（式中的記號(hào)

代表向量逼近的意思）。那么，如何來描述向量目標(biāo)函數(shù)

逼近其對(duì)應(yīng)的目標(biāo)值的程度呢？需要引入空間中點(diǎn)

和

之間的某種距離

。由于

逼近于

，可用它們之間的距離

盡可能小來描述，故式(4-2)可歸結(jié)為數(shù)值極小化問題（4-3）14:17

第4章

目標(biāo)規(guī)劃

顯然，當(dāng)賦予距離

以不同的意義時(shí)，式（4-3）就表示在相應(yīng)意義下的

f(x)逼近于

，這時(shí)也就對(duì)應(yīng)了一個(gè)在該意義下求解式（4-2）的方法。本章僅就最常用的距離表示形式

來設(shè)計(jì)一種求解式（4-2）的方法。為此，引入幾個(gè)相應(yīng)的概念:（1）fi(x)關(guān)于

的絕對(duì)偏差變量

；（2）fi(x)關(guān)于

的正偏差變量（3）fi(x)關(guān)于

的負(fù)偏差變量14:17

第4章

目標(biāo)規(guī)劃由以上可以直接得到上述偏差變量之間有以下關(guān)系：R1：R2：R3：R4：由關(guān)系R1可知

，再注意到關(guān)系R2、R3和R4，則在距離意義為

的條件下，可將式（4-3）等價(jià)地化為如下形式：14:17

第4章

目標(biāo)規(guī)劃（4-4）式（4-4）是利用兩組偏差變量

和

，并以這些偏差變量之和作為f(x)和

之間的距離來描述f(x)逼近于

?？梢钥吹剑剑?-4）的目標(biāo)函數(shù)是偏差變量的線性函數(shù)，而式（4-3）的目標(biāo)函數(shù)則帶有絕對(duì)值的形式，就目標(biāo)函數(shù)而言，式（4-4）比式（4-3）要便于計(jì)算，但式（4-4）中含有（偏差）變量相乘的約束條件，這會(huì)給求解帶來極大的不便，那么如何去掉

這一約束條件，將模型變?yōu)榈娜我蛔顑?yōu)解

是式（4-4）的最優(yōu)解，為此有下面的結(jié)論：14:17

第4章

目標(biāo)規(guī)劃【定理4-1】

若

是式（4-5）的最優(yōu)解，則

是式（4-4）的最優(yōu)解。對(duì)于目標(biāo)函數(shù)來說，由于決策者偏愛程度的不同，導(dǎo)致對(duì)不同目標(biāo)函數(shù)逼近于其目標(biāo)值的要求程度也不同。若要在模型中將決策者這一偏愛關(guān)系體現(xiàn)出來，可以利用權(quán)系數(shù)法和優(yōu)先層次法來解決。（1）權(quán)系數(shù)法

即通過式（4-5）的目標(biāo)函數(shù)

中根據(jù)

重要程度的不同，引入相應(yīng)的權(quán)系數(shù)

，

的方式來體現(xiàn)決策者的偏愛程度。帶有權(quán)系數(shù)的目標(biāo)規(guī)劃的一般數(shù)學(xué)模型如下：（4-6）14:17

第4章

目標(biāo)規(guī)劃

其中，

表示正偏差變量

在式（4-6）中的重要程度，當(dāng)

越大時(shí)，表示對(duì)應(yīng)的目標(biāo)函數(shù)

從大于

而接近于

越重要；同樣的，

表示負(fù)偏差量

在式（4-6）中的重要程度，當(dāng)

越大時(shí)，表示對(duì)應(yīng)的目標(biāo)函數(shù)

從小于

而接近于

越重要。（2）優(yōu)先層次法

即根據(jù)決策者對(duì)各目標(biāo)函數(shù)

偏愛程度的不同，將其分別歸屬到若干個(gè)不同的優(yōu)先層次中進(jìn)行求解的方法。即凡要求第一位達(dá)到的目標(biāo)賦予優(yōu)先因子P1，次位的目標(biāo)賦予優(yōu)先因子P2，…，并規(guī)定

，表示Pk比Pk+1有更大的優(yōu)先權(quán)。也即首先保證P1級(jí)目標(biāo)的實(shí)現(xiàn)，這時(shí)可不考慮次級(jí)目標(biāo)；而P2級(jí)目標(biāo)是在實(shí)現(xiàn)P1級(jí)目標(biāo)的基礎(chǔ)上考慮的；依此類推。

將權(quán)系數(shù)法與優(yōu)先層次法結(jié)合起來，即可得到下面的一般形式的目標(biāo)規(guī)劃模型（4-7）14:17

第4章

目標(biāo)規(guī)劃

其中僅含偏差變量的各層目標(biāo)

叫做偏差目標(biāo)；各層帶有目標(biāo)函數(shù)及其對(duì)應(yīng)目標(biāo)值的約束條件叫做目標(biāo)約束條件

；必須滿足的等式約束和不等式約束（即）稱為絕對(duì)約束條件。另外，由于目標(biāo)規(guī)劃的目標(biāo)函數(shù)是按各目標(biāo)約束的正、負(fù)偏差變量和賦予相應(yīng)的優(yōu)先因子而構(gòu)造的。當(dāng)每一目標(biāo)值確定后，決策者的要求是盡可能縮小偏離目標(biāo)值。因此目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能是

。其基本形式有3種：（1）要求恰好達(dá)到目標(biāo)值，即正、負(fù)偏差都要盡可能地小，這時(shí)（2）要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，就是正偏差變量要盡可能地小，這時(shí)（3）要求超過目標(biāo)值，即超過量不限，但必須是負(fù)偏差變量要盡可能地小，這時(shí)對(duì)每一個(gè)具體的目標(biāo)規(guī)劃，可根據(jù)決策者的要求和賦予各目標(biāo)的優(yōu)先因子來構(gòu)造目標(biāo)函數(shù)。14:17

第4章

目標(biāo)規(guī)劃綜上所述，以多目標(biāo)規(guī)劃數(shù)學(xué)模型為基礎(chǔ)建立目標(biāo)規(guī)劃的基本步驟如下：①確定目標(biāo)值

；②引入偏差變量

，建立目標(biāo)約束條件；③建立目標(biāo)規(guī)劃模型式（4-7）。4.1.3以單目標(biāo)規(guī)劃模型建立目標(biāo)規(guī)劃數(shù)學(xué)模型

在解決實(shí)際問題的過程中，決策者開始時(shí)可能只提出了一個(gè)目標(biāo)要求，并利用單目標(biāo)規(guī)劃模型對(duì)有關(guān)問題進(jìn)行分析討論。但隨著時(shí)間的推移，不斷出現(xiàn)新的問題和要求。在這種情況下，可以充分利用已有的信息來建立目標(biāo)規(guī)劃模型，以單目標(biāo)規(guī)劃模型為基礎(chǔ)來建立目標(biāo)規(guī)劃的數(shù)學(xué)模型。其過程與上面類似，具體步驟如下：1）提出目標(biāo)要求；2）引入偏差變量，建立目標(biāo)約束條件；3）建立目標(biāo)規(guī)劃模型式（4-7）。14:17

第4章

目標(biāo)規(guī)劃下面，通過一個(gè)例子來說明利用單目標(biāo)規(guī)劃模型建立目標(biāo)規(guī)劃模型的過程?！纠?-3】某廠生產(chǎn)I，II兩種產(chǎn)品，已知計(jì)劃期有關(guān)數(shù)據(jù)如下表4-1所示，求獲利最大的生產(chǎn)方案。解：這是一個(gè)單一目標(biāo)規(guī)劃問題，用線性規(guī)劃方法求解設(shè)I，II兩種產(chǎn)品產(chǎn)量分別為x1，x2。線性規(guī)劃模型表述為：可得：元，14:17

第4章

目標(biāo)規(guī)劃

但實(shí)際決策時(shí)，有可能考慮市場(chǎng)等其他方面因素，例如在原材料供應(yīng)受嚴(yán)格限制的基礎(chǔ)上，按重要性排列的下列目標(biāo)：1）據(jù)市場(chǎng)信息，產(chǎn)品I銷售量下降，要求產(chǎn)品I產(chǎn)量低于產(chǎn)品II產(chǎn)量；2）盡可能充分利用現(xiàn)有設(shè)備，但不希望加班；3）達(dá)到并超過計(jì)劃利潤(rùn)指標(biāo)56元。按這些要求，分別賦予三個(gè)目標(biāo)不同的優(yōu)先級(jí)P1，P2，P3。對(duì)要求1），可引入偏差變量

，

，建立目標(biāo)約束方程

，并要求

；對(duì)要求2），可引入偏差變量

，

，建立目標(biāo)約束方程

，并要求

；對(duì)要求3），可引入偏差變量

，

，建立目標(biāo)約束方程

，并要求

。然后建立目標(biāo)規(guī)劃模型如下：14:17

第4章

目標(biāo)規(guī)劃

建立目標(biāo)規(guī)劃數(shù)學(xué)模型時(shí)，需要確定目標(biāo)值、優(yōu)先級(jí)、權(quán)系數(shù)等，它都具有一定的主觀性和模糊性，通常采用專家評(píng)定法給予量化。14:17

第4章

目標(biāo)規(guī)劃4.2目標(biāo)規(guī)劃的圖解法對(duì)于只有兩個(gè)決策變量的目標(biāo)規(guī)劃數(shù)學(xué)模型，可采用圖解法分析求解，這對(duì)于了解目標(biāo)規(guī)劃一般問題的解題思路也很有幫助。下面用例子加以說明。類似于線性規(guī)劃，先在平面直角坐標(biāo)系第一象限繪出各約束條件。絕對(duì)約束的作圖與線性規(guī)劃相同，對(duì)于目標(biāo)約束，先繪出

對(duì)應(yīng)的直線，然后在直線旁相應(yīng)側(cè)標(biāo)注

，如圖4-1所示。根據(jù)目標(biāo)函數(shù)中的優(yōu)先級(jí)對(duì)圖4-1進(jìn)行分析，即可找到滿意解（由于目標(biāo)規(guī)劃問題常出現(xiàn)非可行解，因此稱目標(biāo)規(guī)劃問題的最優(yōu)解為滿意解）。14:17

第4章

目標(biāo)規(guī)劃由圖4-1可見，首先考慮絕對(duì)約束：

，解的可行域?yàn)槿切蜲AB；然后按優(yōu)先級(jí)P1，目標(biāo)函數(shù)中要求

，解域縮減至OBC內(nèi)；再按優(yōu)先級(jí)P2，目標(biāo)函數(shù)中要求

，解域縮減至線段ED上；最后按優(yōu)先級(jí)P3，目標(biāo)函數(shù)中要求

，因此最終滿意解域?yàn)榫€段GD?？汕蟮孟鄳?yīng)坐標(biāo)：G（2,4），D（10/3,10/3）。GD的凸線性組合都是該目標(biāo)規(guī)劃的解。目標(biāo)規(guī)劃問題求解時(shí)，把絕對(duì)約束作為最高優(yōu)先級(jí)（但不必賦P1），【例4-3】中能依次滿足

，

，

，因此最優(yōu)函數(shù)值

。但大多數(shù)情況下并非如此，還可能出現(xiàn)矛盾，這可以通過下面的例子加以說明?！纠?-4】某電子設(shè)備廠裝配A，B兩種型號(hào)同類產(chǎn)品，每裝配一臺(tái)需占用裝配線1h。每周裝配線開動(dòng)40h，預(yù)計(jì)每周銷售：A產(chǎn)品24臺(tái)，每臺(tái)可獲利80元；B產(chǎn)品30臺(tái)，每臺(tái)可獲利40元。該廠確定目標(biāo)為：第一目標(biāo)：充分利用裝配線，每周開動(dòng)40h；第二目標(biāo)：允許裝配線加班，但加班時(shí)間每周不超過10h；第三目標(biāo)：裝配數(shù)量盡量滿足市場(chǎng)需求。要求建立上述問題的數(shù)學(xué)模型并求解。14:17

第4章

目標(biāo)規(guī)劃解：設(shè)x1，x2分別為產(chǎn)品A，B的計(jì)劃產(chǎn)量。對(duì)于第三目標(biāo)，由于每臺(tái)A產(chǎn)品利潤(rùn)是B產(chǎn)品的2倍，因此取其權(quán)系數(shù)分別為2，1。建立目標(biāo)規(guī)劃模型：14:17

第4章

目標(biāo)規(guī)劃由圖4-2可見，在考慮了第一目標(biāo)和第二目標(biāo)之后，x1和x2的取值范圍為ABCD。考慮P3的目標(biāo)要求時(shí)，由于

的權(quán)系數(shù)大于

，應(yīng)先滿足

，因此這時(shí)x1和x2的取值范圍是ACEH，而其中只有H點(diǎn)使

取值最小，故取H點(diǎn)為滿意解。其坐標(biāo)為（24，26），即該廠每周應(yīng)裝配A產(chǎn)品24臺(tái)，B產(chǎn)品26臺(tái)。（可與G端點(diǎn)的結(jié)果比較一下利潤(rùn)上的差別。）對(duì)于多于兩個(gè)變量的情況，類似于線性規(guī)劃，可用單純型法求解。14:17

第4章

目標(biāo)規(guī)劃4.3解目標(biāo)規(guī)劃的單純形法單純形法（SimplexMethod）是美國學(xué)者丹茨基于1974年提出的。它的基本思路是：根據(jù)問題的標(biāo)準(zhǔn)形式，從可行域中一個(gè)基本可行解（一個(gè)頂點(diǎn)）開始，轉(zhuǎn)換到另一個(gè)基本可行解（頂點(diǎn)），并使目標(biāo)函數(shù)的值逐步增大，當(dāng)目標(biāo)函數(shù)達(dá)到最大值時(shí)，就得到了問題的最優(yōu)解。本節(jié)主要研究“目標(biāo)規(guī)劃”的分層單純形算法。這一方法從根本上解決了線性規(guī)劃的求解問題。1965年，伊杰尼（Y.Ijiri）在目標(biāo)的優(yōu)先等級(jí)和優(yōu)先權(quán)因子概念的基礎(chǔ)上，給出了改進(jìn)的“目標(biāo)規(guī)劃”的分層單純形算法。目標(biāo)規(guī)劃模型的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)沒有本質(zhì)區(qū)別，所以其計(jì)算方法與單純形法類似。但考慮目標(biāo)規(guī)劃數(shù)學(xué)模型的一些特點(diǎn)，作以下規(guī)定：1）因目標(biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求極小值，所以以

，

為最優(yōu)準(zhǔn)則。2）因非基變量的檢驗(yàn)數(shù)中含有不同等級(jí)的優(yōu)先因子，即14:17

第4章

目標(biāo)規(guī)劃

因

；從每個(gè)檢驗(yàn)數(shù)的整體來看：檢驗(yàn)數(shù)的正負(fù)首先決定于P1的系數(shù)

的正負(fù)。若

，這時(shí)，檢驗(yàn)數(shù)的正負(fù)就決定于P2的系數(shù)

的正負(fù)。下面可依此類推。

解目標(biāo)規(guī)劃問題的分層單純形法的計(jì)算步驟為：（1）建立初始單純形表，在表中將檢驗(yàn)數(shù)行按優(yōu)先因子個(gè)數(shù)分別列成k行，令k=1。（2）檢查該行中是否存在負(fù)數(shù)，且對(duì)應(yīng)的前k-1行的系數(shù)是零。若有，取其中最小者對(duì)應(yīng)的變量為換入變量，轉(zhuǎn)3）。若無負(fù)數(shù)，則轉(zhuǎn)5）。（3）按最小比值規(guī)則確定換出變量，當(dāng)存在兩個(gè)或兩個(gè)以上相同的最小比值時(shí)，選取具有較高優(yōu)先層次的變量為換出變量。（4）按單純形法進(jìn)行基變換運(yùn)算，建立新的計(jì)算表，返回2）。（5）當(dāng)k=K時(shí)，計(jì)算結(jié)束。表中的解即為有效解。否則令k=k+1，返回到2）。【例4-5】試用分層單純形法求解例【4-4】。14:17

第4章

目標(biāo)規(guī)劃解:1）取

，

，

，

為初始變量，列初始單純形表，見表4-2.2）取

，檢查檢驗(yàn)數(shù)的P1行，有-1，-1，取變量x1為換入變量，轉(zhuǎn)3）。3）在表4-2上計(jì)算

，將該最小比值對(duì)應(yīng)的變量

作為換出變量，轉(zhuǎn)4）。4）進(jìn)行分層單純形迭代運(yùn)算，得表4-3，返回到2）。依此類推，直至得到最終單純形迭代表為止（見表4-4）。表4-5所示的解

，

為【例4-4】的有效解（滿意解），此解相當(dāng)于圖圖4-2的E點(diǎn)。14:17

第4章

目標(biāo)規(guī)劃14:17

第4章

目標(biāo)規(guī)劃14:17

第4章

目標(biāo)規(guī)劃14:17

第4章

目標(biāo)規(guī)劃14:17

第4章

目標(biāo)規(guī)劃4.4靈敏度分析

最優(yōu)化一詞經(jīng)常被誤解，實(shí)際上即使求得最優(yōu)解，它也只是相對(duì)于該數(shù)學(xué)規(guī)劃模型的最優(yōu)解，只要模型不能完全表達(dá)實(shí)際問題，它就不是針對(duì)實(shí)際問題的最優(yōu)解。模型的不完全性在實(shí)際問題中是不可避免的，因此與其追求模型的完全性，不如選擇具有某種程度的不完全性但卻能滿足決策支持要求的模型。而且在某種程度上，即使很精確地確定了目標(biāo)函數(shù)和約束函數(shù)，但很少有約束的右邊值必須為某個(gè)確定值的情況，往往是少一點(diǎn)、多一點(diǎn)都可以。多多少或少多少是由目標(biāo)函數(shù)的最優(yōu)值的變化來決定的。

攝動(dòng)函數(shù)

揭示了目標(biāo)函數(shù)的最優(yōu)值是怎樣隨約束右邊的值而改變，因此在實(shí)際的決策支持問題中，如能求得

，那么分析將十分方便。通常無法顯式地求出該函數(shù)，很多情況下拉格朗日乘子給出了

的一次近似信息，即拉格朗日乘子給出了約束式右邊值的變化對(duì)目標(biāo)函數(shù)最優(yōu)解的影響的信息。分析該值就可以大體了解約束式右邊值稍稍改變時(shí)目標(biāo)函數(shù)的變化情況，因此稱之為靈敏度分析，見圖4-3。在實(shí)際的決策支持中，有效地進(jìn)行靈敏度分析十分有用。14:17

第4章

目標(biāo)規(guī)劃

【例4-6】

設(shè)約束是第j個(gè)項(xiàng)目給出的預(yù)算約束，右邊值bj是按去年增加10%確定下來的值?？紤]在上述預(yù)算約束下，使預(yù)估利益f(x)最大的問題，并把它形式化為數(shù)學(xué)規(guī)劃問題，然后求解。解：假設(shè)由靈敏度（拉格朗日乘子或單純形乘子）知，與第1個(gè)約束對(duì)應(yīng)的靈敏度v1最大，這說明第1個(gè)項(xiàng)目的預(yù)算只要增加一點(diǎn)，整個(gè)利益就會(huì)增加很多。因此除考慮增加去年10%的預(yù)算方案外，還可給貢獻(xiàn)大的項(xiàng)目增加更多的預(yù)算。14:17

第4章

目標(biāo)規(guī)劃

反之，設(shè)第p個(gè)項(xiàng)目的靈敏度vp最小。這時(shí)即使消減一點(diǎn)點(diǎn)第p個(gè)項(xiàng)目的預(yù)算，整體利益也不會(huì)減少，所以需要把第p個(gè)項(xiàng)目的預(yù)算削減到比預(yù)算方案的還要小。在更極端的情況，即設(shè)vp=0，那么給予第p個(gè)項(xiàng)目的預(yù)算對(duì)整體利益毫無貢獻(xiàn)，這時(shí)可以考慮削減其全部預(yù)算。

值得注意的是，靈敏度信息是局部的，只在最優(yōu)解附近有效。當(dāng)vp=0時(shí)，如果全部削減或大幅削減第p個(gè)項(xiàng)目的預(yù)算，那么有時(shí)會(huì)出現(xiàn)數(shù)學(xué)規(guī)劃模型遠(yuǎn)遠(yuǎn)偏離最初設(shè)計(jì)的情況，最優(yōu)解與設(shè)想解偏差很大。由于線性規(guī)劃中當(dāng)前的靈敏度有效，所以它可以研究約束式的右邊值能改變到何種程度（范圍分析）。這樣，在線性規(guī)劃中把靈敏度分析和范圍分析結(jié)合使用可以更有效地進(jìn)行決策支持。

在線性規(guī)劃中目標(biāo)函數(shù)一約束函數(shù)空間上攝動(dòng)函數(shù)的圖形是分段線性的。特別是，若使右邊值像tb那樣包含參數(shù)t，那么通過改變t研究目標(biāo)函數(shù)最優(yōu)解的變化，攝動(dòng)函數(shù)圖形就是分段的折線圖。這樣，研究目標(biāo)函數(shù)最優(yōu)解隨t的變化的情況就稱為參數(shù)分析。14:17

第4章

目標(biāo)規(guī)劃4.5應(yīng)用舉例

由于目標(biāo)規(guī)劃模型比較符合現(xiàn)代化管理決策的實(shí)際，有能力處理各種沒有統(tǒng)一度量單位和互相矛盾的多目標(biāo)，而且便于利用電子計(jì)算機(jī)技術(shù)，所以已經(jīng)成為解決現(xiàn)代化管理中多目標(biāo)決策問題的有效工具。近年來，世界各國科學(xué)家都非常重視目標(biāo)規(guī)劃，如在工程系統(tǒng)（金屬切削加工、軸承系統(tǒng)、儲(chǔ)水系統(tǒng)、高速公路、太陽能系統(tǒng)等）的優(yōu)化設(shè)計(jì)中，引入目標(biāo)規(guī)劃，在外貿(mào)、保險(xiǎn)、金融、服務(wù)業(yè)等行業(yè)目標(biāo)規(guī)劃也得到了廣泛的應(yīng)用。

【例4-7】某單位領(lǐng)導(dǎo)在考慮本單位職工的升級(jí)調(diào)資方案時(shí)，依次遵循以下規(guī)定：1）不超過年工資總額600000元；2）每級(jí)的人數(shù)不超過定編規(guī)定的人數(shù)；3）II、III級(jí)的升級(jí)面盡可能達(dá)到現(xiàn)有人數(shù)的20%；4）III級(jí)不足編制的人數(shù)可錄用新職工，又I級(jí)的職工中有10%要退休。有關(guān)資料匯總于表4-6中：14:17

第4章

目標(biāo)規(guī)劃問單位領(lǐng)導(dǎo)應(yīng)該如何擬定一個(gè)滿意的方案？解：設(shè)x1，x2，x3分別表示提升到I、II級(jí)和錄用到III級(jí)的新職工人數(shù)。對(duì)各目標(biāo)確定的優(yōu)先因子為P1

不超過年工資總額600000元；P2

每級(jí)的人數(shù)不超過定編規(guī)定的人數(shù)；P3

II、III級(jí)的升級(jí)面盡可能達(dá)到現(xiàn)有人數(shù)的20%。先分別建立各目標(biāo)約束年工資總額不超過600000元：每級(jí)的人數(shù)不超過定編規(guī)定的人數(shù)：14:17

第4章

目標(biāo)規(guī)劃對(duì)I級(jí)有對(duì)II級(jí)有對(duì)III級(jí)有II、III級(jí)的升級(jí)面盡可能達(dá)到現(xiàn)有人數(shù)的20%：對(duì)II級(jí)有對(duì)III級(jí)有目標(biāo)函數(shù)

以上目標(biāo)規(guī)劃模型可用分層單純形法求解，得到多重解。現(xiàn)將這些解匯總于表4-7，這個(gè)單位負(fù)責(zé)人再按具體情況，從表4-7中選出一個(gè)執(zhí)行方案。14:17

第4章

目標(biāo)規(guī)劃14:17

第4章

目標(biāo)規(guī)劃

【例4-8】某電子廠生產(chǎn)錄音機(jī)和電視機(jī)兩種產(chǎn)品，分別經(jīng)由甲、乙兩個(gè)車間生產(chǎn)。已知除外購件外，生產(chǎn)一臺(tái)錄音機(jī)需甲車間加工2h，乙車間裝配1h；生產(chǎn)一臺(tái)電視機(jī)需甲車間加工1h，乙車間裝配3h。這兩種產(chǎn)品生產(chǎn)出來后均需經(jīng)檢驗(yàn)、銷售等環(huán)節(jié)。已知每臺(tái)錄音機(jī)檢驗(yàn)銷售費(fèi)用需50元，每臺(tái)電視機(jī)檢驗(yàn)銷售費(fèi)用需30元。又甲車間每月可用的生產(chǎn)工時(shí)為120h，車間管理費(fèi)用為80元/h；乙車間每月可用的生產(chǎn)工時(shí)為150h，車間管理費(fèi)用為20元/h。估計(jì)每臺(tái)錄音機(jī)的利潤(rùn)為100元，每臺(tái)電視機(jī)的利潤(rùn)為75元，又估計(jì)下一年度內(nèi)平均每月可銷售錄音機(jī)50臺(tái)，電視機(jī)80臺(tái)。工廠確定制訂月度計(jì)劃的目標(biāo)如下。

第一優(yōu)先級(jí)：檢驗(yàn)和銷售費(fèi)每月不超過4600元；

第二優(yōu)先級(jí)：每月售出錄音機(jī)不少于50臺(tái)；

第三優(yōu)先級(jí)：甲、乙兩車間的生產(chǎn)工時(shí)得到充分利用（重要性權(quán)系數(shù)按兩個(gè)車間每小時(shí)費(fèi)用的比例確定）；第四優(yōu)先級(jí)：甲車間加班不超過20h；第五優(yōu)先級(jí)：每月銷售電視機(jī)不少于80臺(tái)。試確定該廠為達(dá)到以上目標(biāo)的最優(yōu)月度計(jì)劃生產(chǎn)數(shù)字。14:17

第4章

目標(biāo)規(guī)劃解：設(shè)x1為每月生產(chǎn)錄音機(jī)的臺(tái)數(shù)，x2為每月生產(chǎn)電視機(jī)的臺(tái)數(shù)，根據(jù)題中給出的條件，約束情況如下。1）檢驗(yàn)和銷售費(fèi)用約束，每月不超過4600元

（其中要求

）2）出售錄音機(jī)數(shù)量約束，每月售出錄音機(jī)不少于50臺(tái)，即要求最好大于50臺(tái)

（其中要求

）3）甲、乙車間可用工時(shí)的約束，充分利用即要求最好不要有剩余工時(shí)：

（甲車間）（其中要求

）（乙車間）（其中要求

）

4）對(duì)甲車間加班限制，20h以內(nèi)

（其中要求

）5）銷售電視機(jī)數(shù)量約束，不少于80臺(tái)

（其中要求

）因甲、乙車間管理費(fèi)用分別為80元/h和20元/h，其權(quán)重比為4:1，故得目標(biāo)規(guī)劃模型為：

14:17

第4章

目標(biāo)規(guī)劃【知識(shí)點(diǎn)串聯(lián)】多目標(biāo)規(guī)劃的數(shù)學(xué)模型：建立多目標(biāo)規(guī)劃的目的，就是為了通過求解這一規(guī)劃模型來解決現(xiàn)實(shí)中的問題。要求出多目標(biāo)規(guī)劃的最優(yōu)解，首先應(yīng)知道到底符合什么條件的可行解才是最優(yōu)解？在建立多目標(biāo)規(guī)劃模型時(shí)，應(yīng)注意決策變量、目標(biāo)函數(shù)、約束條件各自的含義及關(guān)系方程。單目標(biāo)規(guī)劃的數(shù)學(xué)模型：最優(yōu)解可以通過求目標(biāo)函數(shù)的極小值來獲得。對(duì)于目標(biāo)函數(shù)來說，由于決策者偏愛程度的不同，導(dǎo)致對(duì)不同目標(biāo)函數(shù)逼近于其目標(biāo)值的要求程度也不同。若要在模型中將決策者這一偏愛關(guān)系體現(xiàn)出來，有