理學(xué)目標(biāo)規(guī)劃

目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理中多目標(biāo)決策的需要而逐步發(fā)展起來的一個分支。目標(biāo)規(guī)劃是60年代初由美國科學(xué)家A.charnes和W.cooper在《管理模型和線性規(guī)劃的工業(yè)應(yīng)用》中一書提出的。

⑵線性規(guī)劃立足于求滿足所有約束條件的最優(yōu)可行解，而目標(biāo)規(guī)劃可以在相互矛盾的約束條件下找到滿意解，得出決策問題的滿意方案。

⑴線性規(guī)劃只能處理一個目標(biāo)的問題，而目標(biāo)規(guī)劃則能夠統(tǒng)籌兼顧多個目標(biāo)的關(guān)系，更能適用于經(jīng)營管理中的多目標(biāo)決策問題。目標(biāo)規(guī)劃與線性規(guī)劃的比較:

⑶目標(biāo)規(guī)劃找到的最優(yōu)解是指盡可能達(dá)到或接近一個或多個已給定目標(biāo)值的滿意解。

⑷線性規(guī)劃對約束條件是不分主次地同等對待，而目標(biāo)規(guī)劃可以根據(jù)實際需要靈活地給予輕重緩急的考慮。第一節(jié)目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型一、目標(biāo)規(guī)劃問題的提出【例4-1】產(chǎn)品生產(chǎn)問題。某企業(yè)計劃生產(chǎn)I、II兩種型號的產(chǎn)品，具體相關(guān)數(shù)據(jù)如下表所示：108利潤1021設(shè)備工時1112原材料擁有量ⅡⅠ

產(chǎn)品消耗資源

解：若用xi（i＝1,2）分別表示I、II兩種產(chǎn)品的生產(chǎn)量，則問題可以歸結(jié)為如下的線性規(guī)劃問題數(shù)學(xué)模型：

這是一個單目標(biāo)的線性規(guī)劃模型，可求出最優(yōu)解為x1＝4件，x2＝3件，Maxz=62元。企業(yè)生產(chǎn)中可能有下列情況出現(xiàn)：⑴根據(jù)市場對該產(chǎn)品銷售預(yù)測得知，產(chǎn)品I的利潤有下降的趨勢，故應(yīng)考慮產(chǎn)品I的產(chǎn)量不應(yīng)大于產(chǎn)品II的產(chǎn)量。⑵盡可能不超過計劃使用原材料，因為超過計劃后，需要高價采購原材料，導(dǎo)致成本增加。⑶應(yīng)盡量充分利用原有的設(shè)備工時，而不希望加班生產(chǎn)。⑷應(yīng)盡可能達(dá)到或超過原計劃利潤指標(biāo)56。此時，企業(yè)決策者的考慮用數(shù)學(xué)表達(dá)式表述為：二、目標(biāo)規(guī)劃的一般概念1．目標(biāo)值和偏差變量

目標(biāo)值：是指預(yù)先給定的某個目標(biāo)的一個期望值。實現(xiàn)值或決策值：是指當(dāng)決策變量xj

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

在一次決策中，實現(xiàn)值不可能既超過目標(biāo)值又未達(dá)到目標(biāo)值，故有d＋×d－

＝0,并規(guī)定d＋≥0,d－≥0

當(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ī)劃中特有的，是軟約束。2、目標(biāo)約束和絕對約束

絕對約束（系統(tǒng)約束）是指必須嚴(yán)格滿足的等式或不等式約束。如線性規(guī)劃中的所有約束條件都是絕對約束，否則無可行解。所以，絕對約束是硬約束。3、優(yōu)先因子與權(quán)系數(shù)

優(yōu)先因子Pk

是將決策目標(biāo)按其重要程度排序并表示出來。P1>>P2>>…>>Pk>>Pk+1>>…>>PK

，k=1.2…K。權(quán)系數(shù)ωk

區(qū)別具有相同優(yōu)先因子的兩個目標(biāo)的差別，決策者可視具體情況而定。4、目標(biāo)規(guī)劃的目標(biāo)函數(shù)

目標(biāo)函數(shù)是一個使總偏差量為最小的目標(biāo)函數(shù)，記為：

一般說來，有以下三種情況，但只能出現(xiàn)其中之一：⑴要求恰好達(dá)到規(guī)定的目標(biāo)值，即正、負(fù)偏差變量要盡可能小，則：⑶要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，也就是正偏差變量盡可能小，則：⑵要求超過目標(biāo)值，即對目標(biāo)的正偏差要求不限，而負(fù)偏差越小越好，這時的目標(biāo)函數(shù)為：對于由絕對約束轉(zhuǎn)化而來的目標(biāo)函數(shù)，也照上述處理即可。

對于這種解來說，前面的目標(biāo)可以保證實現(xiàn)或部分實現(xiàn)，而后面的目標(biāo)就不一定能保證實現(xiàn)或部分實現(xiàn)，有些可能就不能實現(xiàn)。

5、滿意解（具有層次意義的解）

目標(biāo)規(guī)劃問題的求解是在不破壞上一級目標(biāo)的前提下，實現(xiàn)下一級目標(biāo)的最優(yōu)化。因此，這樣最后求出的解就不是通常意義下的最優(yōu)解，我們稱為它為滿意解。三、目標(biāo)規(guī)劃的一般模型

如例4-1，產(chǎn)品I的產(chǎn)量不應(yīng)大于產(chǎn)品II的產(chǎn)量，其目標(biāo)優(yōu)先級為p1，則第一優(yōu)先級的目標(biāo)函數(shù)為：

第二個目標(biāo)要求是應(yīng)盡量充分利用原有的設(shè)備工時，而不希望加班生產(chǎn)，其目標(biāo)優(yōu)先級為p2，則其目標(biāo)函數(shù)應(yīng)為：

第三個目標(biāo)要求是企業(yè)希望達(dá)到并超過計劃利潤56，其目標(biāo)優(yōu)先級為p3，則其相應(yīng)的目標(biāo)函數(shù)為：則例1對應(yīng)的目標(biāo)規(guī)劃數(shù)學(xué)模型為：

對于任何一個多目標(biāo)決策問題，不妨設(shè)問題有n個決策變量、m個絕對約束、L（≥1）個目標(biāo)約束、K（K≤L）個優(yōu)先等級?？梢越o出多目標(biāo)決策問題的一般目標(biāo)規(guī)劃模型：四、建模步驟1、根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約束與絕對約束；3、給各目標(biāo)賦予相應(yīng)的優(yōu)先因子Pk（k=1.2…K）。2、可根據(jù)決策者的需要，將某些或全部絕對約束轉(zhuǎn)化為目標(biāo)約束。這時只需要給絕對約束加上負(fù)偏差變量和減去正偏差變量即可。5、根據(jù)決策者的要求，按下列情況之一構(gòu)造一個由⑴恰好達(dá)到目標(biāo)值，取。⑵允許超過目標(biāo)值，取。⑶不允許超過目標(biāo)值，取。

優(yōu)先因子和權(quán)系數(shù)相對應(yīng)的偏差變量組成的，要求實現(xiàn)極小化的目標(biāo)函數(shù)，即達(dá)成函數(shù)。4、對同一優(yōu)先等級中的各偏差變量，若需要可按其重要程度的不同，賦予相應(yīng)的權(quán)系數(shù)。第二節(jié)目標(biāo)規(guī)劃的圖解法

圖解法同樣適用兩個變量的目標(biāo)規(guī)劃問題，但其操作簡單，原理一目了然。同時，也有助于理解一般目標(biāo)規(guī)劃的求解原理和過程。

圖解法解題步驟如下：

1、確定各約束條件的可行域，即將所有約束條件（包括目標(biāo)約束和絕對約束，暫不考慮正負(fù)偏差變量）在坐標(biāo)平面上表示出來；

2、在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值增大的方向；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)解和滿意解?！纠坑脠D解法求解例4-1目標(biāo)規(guī)劃問題【例】用圖解法求解目標(biāo)規(guī)劃問題⑴⑵⑶0x2

x1⑷⑸⑹ABCEKMLJ012345678123456⑴⑵⑶Ax2

x1BCB(0.6250,4.6875)、C(0,5.2083)，B、C線段上的所有點均是該問題的解（無窮多最優(yōu)解）。第三節(jié)目標(biāo)規(guī)劃的單純形法σmn+2mσm2σm1αK

PK

σ2n+2mσ22σ21α2P2

σ1n+2mσ12σ11α1P1

σkjemn+2mem2em1bomxjm

cjme2n+2me22e21bo2xj2cj2e1n+2me12e11bo1xj1cj1xn+2m

x2

x1bXBCBcn+2mc2c1Cj

一、目標(biāo)規(guī)劃單純形法的一般形式目標(biāo)規(guī)劃求解時，其單純形表的一般結(jié)構(gòu)如下表：2、建立初始單純形表。一般假定初始解在原點，即以約束條件中的所有負(fù)偏差變量或松弛變量為初始基變量，按目標(biāo)優(yōu)先等級從左至右分別計算出各列的檢驗數(shù)，填入表的下半部。3、檢驗是否為滿意解。判別準(zhǔn)則如下：⑴首先檢查σk

(k=1.2…K)是否全部大于零？如果全部大于零，則表示目標(biāo)均已全部達(dá)到，獲得最優(yōu)解，停止計算轉(zhuǎn)到第7步；否則轉(zhuǎn)入⑵。二、單純形法的計算步驟⑵如果某一個σ

k

<0。說明第k個優(yōu)先等級的目標(biāo)尚未達(dá)到,必須檢查Pk這一的檢驗數(shù)σkj(j=1.2…n+2m).若Pk這一行某些負(fù)檢驗數(shù)的同列上面（較高優(yōu)先等級）沒有正檢驗數(shù)，說明未得到滿意解，應(yīng)繼續(xù)改進(jìn)，轉(zhuǎn)到第3步；若Pk這一行全部負(fù)檢驗數(shù)的同列上面（較高優(yōu)先等級）都有正檢驗數(shù)，說明目標(biāo)雖沒達(dá)到，但已不能改進(jìn)，故得滿意解，轉(zhuǎn)到第7步。1、將目標(biāo)規(guī)劃問題的數(shù)學(xué)模型化為標(biāo)準(zhǔn)形。4、確定進(jìn)基變量。在Pk行，從那些上面沒有正檢驗數(shù)的負(fù)檢驗數(shù)中，選絕對值最大者，對應(yīng)的變量xs就是進(jìn)基變量。若Pk行中有幾個相同的絕對值最大者，則依次比較它們各列下部的檢驗數(shù)，取其絕對值最大的負(fù)檢驗數(shù)的所在列的xs為進(jìn)基變量。假如仍無法確定，則選最左邊的變量（變量下標(biāo)小者）為進(jìn)基變量。5、確定出基變量其方法同線性規(guī)劃，即依據(jù)最小比值法則：故確定xr為出基變量，ers為主元素。若有幾個相同的行可供選擇時，選最上面那一行所對應(yīng)得變量為xr

。6、旋轉(zhuǎn)變換（變量迭代）以主元素為中心進(jìn)行變換，得到新的單純形表，獲得一組新解，返回到第3步。7、對求得的解進(jìn)行分析若計算結(jié)果滿意，停止運算；若不滿意，需修改模型，即調(diào)整目標(biāo)優(yōu)先等級和權(quán)系數(shù)，或者改變目標(biāo)值，重新進(jìn)行第2步?！纠?-2】用單純形法求解下列目標(biāo)規(guī)劃問題

解：⑴本例中由于各目標(biāo)約束中均存在負(fù)偏差變量，取為初始基變量，計算檢驗數(shù)，并將有關(guān)數(shù)據(jù)填入單純形表中，如下表：-1110856-112110-11-110011211000000-8-1-2-10121表中第一列檢驗數(shù)計算方法為：即x2進(jìn)基變量11—55.6即離基變量-115-536-1/21/211/250-1/21/2-113/2501/2-1/213/26000000表中第一列檢驗數(shù)計算方法為：即x1進(jìn)基變量1-3即離基變量151-51410/3102即為離基變量1111因表中全部檢驗數(shù)均大于0，所以得到滿意解：又因表中列的檢驗數(shù)等于0，則該問題存在多重解。則為進(jìn)基變量-1/31/3-5-5/3121/6-1/6-4/34/31401/2-1/2-33-11201/2-1/2-2213000000因表中全部檢驗數(shù)均大于0，所以得到另一個滿意解：1-1/31/3-2/32/3110/3-1/31/31/3-1/3110/301-1-66-2240-1-11-111000000111第五節(jié)WinQSB軟件應(yīng)用一、目標(biāo)規(guī)劃求解

目標(biāo)規(guī)劃求解的運算程序是GoalProgramming(GP)，該程序可以求解線性目標(biāo)規(guī)劃、整數(shù)目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃問題。【例4-5】用WinQSB軟件求解下述目標(biāo)規(guī)劃問題。⑴啟動。開始→程序→WinQSB→GoalProgramming(GP)。⑵建立新的數(shù)據(jù)文件或打開已有的數(shù)據(jù)文件。在上圖中點File出現(xiàn)下拉菜單New