線性目標(biāo)規(guī)劃ppt課件.ppt

《線性目標(biāo)規(guī)劃ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、一、目標(biāo)規(guī)劃概述二、目標(biāo)規(guī)劃的數(shù)學(xué)模型三、目標(biāo)規(guī)劃的圖解法四、目標(biāo)規(guī)劃的單純形法第5章線性目標(biāo)規(guī)劃(GoalProgramming)一、目標(biāo)規(guī)劃概述線性規(guī)劃在實踐中得到廣泛應(yīng)用，但有兩個方面不足：一是不能處理多目標(biāo)的優(yōu)化問題；二是其約束條件過于剛性化，不允許約束資源有絲毫超差。目標(biāo)規(guī)劃是為了解決這一不足而創(chuàng)建的一類數(shù)學(xué)模型。線性規(guī)劃是在一組線性約束條件下，尋求某一項目標(biāo)的最優(yōu)值，而實際問題往往要考慮多個目標(biāo)的決策問題。如核電站的設(shè)計問題，傳統(tǒng)的單目標(biāo)規(guī)劃只允許設(shè)定一個目標(biāo)，那么單一目標(biāo)選擇什么？電站建設(shè)費用最低，安全運行的可靠性最

2、高，電能輸出最大，對周圍環(huán)境的影響最小。顯然，上述目標(biāo)都很重要，且又互相矛盾。這是一個多目標(biāo)決策問題，普通的線性規(guī)劃是無能為力的。1、問題的提出例1：工廠生產(chǎn)兩種產(chǎn)品，受到原材料供應(yīng)和設(shè)備工時的限制。在單件利潤等有關(guān)數(shù)據(jù)已知的條件下，要求制訂一個獲利最大的生產(chǎn)計劃，具體數(shù)據(jù)見下表。產(chǎn)品ⅠⅡ限量原材料(kg/件)51060設(shè)備工時(h/件)4440利潤(元/件)68目標(biāo)規(guī)劃問題實例設(shè)產(chǎn)品Ⅰ、Ⅱ的產(chǎn)量分別為，建立線性規(guī)劃模型：解得最優(yōu)生產(chǎn)計劃為件，件，利潤為元。如果工廠作決策時可能還需根據(jù)市場和工廠實際情況，考慮其它問題，如：（1）

3、由于產(chǎn)品Ⅱ銷售疲軟，故希望產(chǎn)品Ⅱ的產(chǎn)量不超過產(chǎn)品Ⅰ的一半；（2）原材料嚴(yán)重短缺，原料數(shù)量只有60；（3）最好能節(jié)約4小時設(shè)備工時；（4）計劃利潤不少于48元。2、目標(biāo)規(guī)劃的基本概念（1）目標(biāo)值和正、負(fù)偏差變量目標(biāo)規(guī)劃通過引入目標(biāo)值和正、負(fù)偏差變量。所謂目標(biāo)值是預(yù)先給定的某個目標(biāo)的一個期望值。實際值（或決策值）是當(dāng)決策變量x1、x2、…、xn選定以后目標(biāo)函數(shù)的對應(yīng)值。顯然，實際值和目標(biāo)值之間會有一定的差異，這種差異稱為偏差變量(事先無法確定的未知量)，用d＋和d－表示。d＋——超出目標(biāo)值的差值，稱正偏差變量；d－——未達(dá)到目標(biāo)

4、值的差值，稱負(fù)偏差變量；當(dāng)實際值超出目標(biāo)值時，有d－＝0，d＋＞0；當(dāng)實際值未達(dá)到目標(biāo)值時，有d＋＝0，d－＞0；當(dāng)實際值同目標(biāo)值恰好一致時，d＋＝d－＝0。（2）絕對約束與目標(biāo)約束絕對約束又稱系統(tǒng)約束，是指必須嚴(yán)格滿足的等式和不等式約束，如線性規(guī)劃問題的所有約束都是絕對約束，不滿足這些約束條件的解稱為非可行解，所以它們是硬約束。目標(biāo)約束是目標(biāo)規(guī)劃特有的，可把約束右端看做要追求的目標(biāo)。在達(dá)到此目標(biāo)值時允許發(fā)生正偏差或負(fù)偏差，因此在這些約束中加入正、負(fù)偏差變量，是軟約束。原材料嚴(yán)重短缺，原料數(shù)量只有60；①目標(biāo)函數(shù)變?yōu)槟繕?biāo)約束線性規(guī)

5、劃問題的目標(biāo)函數(shù)，在給定目標(biāo)值和偏差變量后可變換為目標(biāo)約束。這樣就將目標(biāo)函數(shù)則轉(zhuǎn)化為目標(biāo)約束。比如：計劃利潤不少于48元。②絕對約束變?yōu)槟繕?biāo)約束該約束的右端項看作目標(biāo)值，再引入正、負(fù)偏差變量即可。或此為系統(tǒng)約束在達(dá)到此目標(biāo)值時允許發(fā)生正或負(fù)偏差，因此在這些約束中加入正、負(fù)偏差變量，它們是軟約束，在給定目標(biāo)值和加入正、負(fù)偏差變量之后，可以將絕對約束轉(zhuǎn)化為目標(biāo)約束。（3）優(yōu)先因子（優(yōu)先等級）與權(quán)系數(shù)在一個規(guī)劃問題中，決策者在要求達(dá)到這些目標(biāo)時，是有輕重緩急的，稱這些目標(biāo)是屬于不同層次的優(yōu)先等級。優(yōu)先等級層次的高低可分別通過優(yōu)先因子P1

6、，P2，…表示，并規(guī)定Pk＞＞Pk＋1，符號“＞＞”表示“遠(yuǎn)大于”，表示Pk與Pk＋1，不是同一各級別的量，即Pk與Pk＋1有更大的優(yōu)先權(quán)。對屬于同一層次優(yōu)先等級的不同目標(biāo)，按其重要程度可分別乘上不同的權(quán)系數(shù)。權(quán)系數(shù)是一個個具體數(shù)字，乘上的權(quán)系數(shù)越大，表明該目標(biāo)越重要。（4）目標(biāo)規(guī)劃的目標(biāo)函數(shù)－－準(zhǔn)則函數(shù)從決策者的要求分析：總希望得到的結(jié)果與規(guī)定的目標(biāo)值間的偏差愈小愈好，由此決策者可根據(jù)自己的要求構(gòu)造一個使總偏差量為最小的目標(biāo)函數(shù)，這就是目標(biāo)規(guī)劃的目標(biāo)函數(shù)稱為準(zhǔn)則函數(shù)，記為即目標(biāo)函數(shù)是正、負(fù)偏變量的函數(shù)。一般來說，可能提出的要求只

7、能是以下三種情況之一，對應(yīng)每種要求，可分別構(gòu)造目標(biāo)函數(shù)：構(gòu)造目標(biāo)函數(shù)的方法如希望產(chǎn)品Ⅰ產(chǎn)量恰好等于產(chǎn)品Ⅱ的產(chǎn)量，即正、負(fù)偏變量都要盡可能地小，這時目標(biāo)函數(shù)是：如希望產(chǎn)品Ⅰ產(chǎn)量低于產(chǎn)品Ⅱ的產(chǎn)量，即允許達(dá)不到目標(biāo)值，正偏差變量要盡可能地小,這時目標(biāo)函數(shù)是：如希望產(chǎn)品Ⅰ產(chǎn)量不低于產(chǎn)品Ⅱ的產(chǎn)量，即要求超過目標(biāo)值，不得低于目標(biāo)值，負(fù)偏差變量盡可能地小，這時目標(biāo)函數(shù)是：例1中目標(biāo)函數(shù)的構(gòu)成希望產(chǎn)品Ⅱ產(chǎn)量不超過產(chǎn)品Ⅰ產(chǎn)量的一半，即正偏差變量要盡可能地小，不希望上式中的d＋＞0，這時目標(biāo)函數(shù)是：希望能節(jié)約4小時設(shè)備工時，即正偏差變量要盡可能小，不

8、希望上式中的d＋＞0，這時目標(biāo)函數(shù)是：希望計劃利潤不少于48元，即負(fù)偏差變量盡可能小，不希望上式中的d－＞0，這時目標(biāo)函數(shù)是：（5）滿意解目標(biāo)規(guī)劃問題的求解是分級進(jìn)行的，首先要求滿足P1級目標(biāo)的解；然后再保證P1級目標(biāo)不被破壞的前提下，再要求滿足P