運籌學基礎-目標規(guī)劃(2)課件

上節(jié)小結：目標規(guī)劃的基本概念1.目標值和正、負偏差變量

目標值是預先給定的某個目標的一個期望值。實現(xiàn)值是當決策變量x1、x2、…、xn選定以后目標函數(shù)的對應值。偏差變量：實現(xiàn)值和目標值之間的差異值，用d＋和d－表示。

d＋——超出目標的差值，稱正偏差變量；

d－——未達到目標的差值，稱負偏差變量；

2.絕對約束與目標約束

絕對約束又稱系統(tǒng)約束，是指必須嚴格滿足的等式和不等式約束。

目標約束：對那些不嚴格限定的約束，連同原線性規(guī)劃建模時的目標函數(shù)轉化為的約束，稱為目標約束。

由此決策者可根據(jù)自己的要求構造一個使總偏差量為最小的目標函數(shù)，稱為達成函數(shù)，記為

即達成函數(shù)是正、負偏變量的函數(shù)。有三種形式：

3．目標規(guī)劃的目標函數(shù)－－達成函數(shù)實際值恰好等于目標值，即正、負偏變量盡可能地小，這時函數(shù)是：實際值大于目標值，即負偏變量盡可能地小，這時函數(shù)是：實際值小于目標值，即負偏變量盡可能地小，這時函數(shù)是：

在一個目標規(guī)劃的模型中，如果兩個不同目標重要程度相差懸殊，為達到某一目標可犧牲其它一些目標，稱這些目標是屬于不同層次的優(yōu)先級。優(yōu)先級層次的高低可分別通過優(yōu)先因子P1，P2，…表示，并規(guī)定Pk＞＞Pk＋1，符號“＞＞”表示“遠大于”，表示Pk與Pk＋1，不是同一各級別的量，即Pk比Pk＋1有更大的優(yōu)先權。

對屬于同一層次優(yōu)先級的不同目標，按其重要程度可分別乘上不同的權數(shù)。權系數(shù)是一個個具體數(shù)字，乘上的權系數(shù)越大，表明該目標越重要。4.目標的優(yōu)先級與權系數(shù)5.滿意解

目標規(guī)劃問題的求解是在不破壞上一級目標的前提下，實現(xiàn)下一級目標的最優(yōu)。因此，這樣最后求出的解就不是通常意義下的最優(yōu)解，我們稱它為滿意解?！?.2應用舉例[例1]某電子廠生產(chǎn)錄音機和電視機兩種產(chǎn)品，分別經(jīng)由甲、乙兩個車間生產(chǎn)。已知除外購件外，生產(chǎn)一臺錄音機需甲車間加工2h，乙車間裝配1h；生產(chǎn)一臺電視機需甲車間加工1h，乙車間裝配3h；兩種產(chǎn)品需檢驗、銷售環(huán)節(jié)，每臺錄音機檢驗銷售費用需50元，每臺電視機檢驗銷售費用需30元。又甲車間每月可用工時為120h，車間管理為80元/h，乙車間每月可用工時為150h，車間管理為20元/h。估計每臺錄音機利潤100元，每臺電視機利潤75元，又估計下一年度內(nèi)平均每月可銷售錄音機50臺，電視機80臺。該廠的月度目標為

P1：檢驗銷售費用每月不超過4600元；

P2：每月銷售錄音機不少于50臺；

P3：甲、乙車間每月工時要充分利用（權數(shù)按每小時費用比例確定）；P4：甲車間加班不超過20h。P5：每月銷售電視機不少于80臺P6：兩車間加班總時間要控制（權數(shù)按每小時管理費用比例確定）

解設錄音機、電視機的產(chǎn)量分別為x1,x2；甲、乙工時比例為4：1，于是得到目標規(guī)劃模型為檢驗銷售費用每月不超過4600元，P1minZ=P1d1+x1+d2-

–d2+＝50x2+d3-

–d3+＝8050x1+30x2+d1-

–d1+＝

4600+P2d2-

+P5d3-d4++d6-

–d6+＝20每月銷售錄音機不少于50臺，P2；每月銷售電視機不少于80臺，P52x1+x2+d4-

–d4+＝120

x1+3x2+d5-

–d5+＝150x1,x2，di-,di+

≥0

+P3(

4d4-+d5-)甲、乙車間每月工時要充分利用，P3甲車間加班不超過20h，P4

+P4d6+

+P6(4d4+＋d5+)兩車間加班總時間要控制，P6最后得x1=50，x2=40，d1-

=900，

d4+=20，d5+=20，即每月生產(chǎn)錄音機50臺，電視機40臺，利潤額可達到8000元

[例2]某制藥公司有甲、乙兩個工廠，現(xiàn)要生產(chǎn)A、B兩種藥品均需在兩個工廠生產(chǎn)．A藥品在甲廠加工2h，然后送到乙廠檢測包裝2.5h才能成品，B藥在甲廠加工4h，再到乙廠檢測包裝1.5h才能成品．A、B藥在公司內(nèi)的每月存貯費分別為8元和15元．甲廠有12臺制造機器，每臺每天工作8h，每月正常工作25天，乙廠有7臺檢測包裝機，每天每臺工作16h，每月正常工作25天，每臺機器每小時運行成本：甲廠為18元，乙廠為15元，單位產(chǎn)品A銷售利潤為20元，B為23元，依市場預測次月A、B銷售量估計分別為1500單位和1000單位．該公司依下列次序為目標的優(yōu)先次序，以實現(xiàn)次月的生產(chǎn)與銷售目標．P1：廠內(nèi)的儲存成本不超過23000元．P2：A銷售量必須完成1500單位．P3：甲、乙兩工廠的設備應全力運轉，避免有空閑時間，兩廠的單位運轉成本當作它們的權系數(shù)．P4：甲廠的超過作業(yè)時間全月份不宜超過30h．P5：B藥的銷量必須完成1000單位．P6：兩個工廠的超時工作時間總和要求限制，其限制的比率依各廠每小時運轉成本為準．試確定A、B藥各生產(chǎn)多少，使目標達到最好，建立目標規(guī)劃模型并化成標準型§5.2目標規(guī)劃的圖解法和線性規(guī)劃問題一樣，圖解法雖然只適用于兩個決策變量的目標規(guī)劃問題，但其操作簡便，原理一目了然，并且有助于理解一般目標規(guī)劃問題的求解原理和過程。

圖解法解題的步驟為：1.確定各約束條件的可行域，即將所有約束條件(包括目標約束和絕對約束，暫不考慮正負偏差變量)在坐標平面上表示出來；

2.在目標約束所代表的邊界線上，用箭頭標出正、負偏差變量值增大的方向；

3.求滿足最高優(yōu)先等級目標的解；4.轉到下一個優(yōu)先等級的目標，在不破壞所有較高優(yōu)先等級目標的前提下，求出該優(yōu)先等級目標的解；5.重復4，直到所有優(yōu)先等級的目標都已審查完畢為止；6.確定最優(yōu)解或滿意解。下面通過例子來說明目標規(guī)劃圖解法的原理和步驟。例1用圖解法求解目標規(guī)劃問題：解

確定各個約束條件的可行域。在x1Ox2坐標平面上，暫不考慮每個約束方程中的正、負偏差變量，將上述每一個約束方程用一條直線表示出來，再用兩個箭頭分別表示上述目標約束方程中的正、負偏差變量。

4x1≤164x2≤122x1+3x2+d1-

–d1+=12x1－x2+d2-–d2+=02x1+2x2+d3-

–d3+=12

x1+2x2+d4-

–d4+=8x1,x2，di-,di+

≥0例1用圖解法求解目標規(guī)劃問題：

4x1≤164x2≤122x1+3x2+d1-

–d1+=123x1－4x2+d2-–d2+=02x1+2x2+d3-

–d3+=12

x1+2x2+d4-

–d4+=8x1,x2，di-,di+

≥01x1x2430215623456ABCd1+d1-d2-d2+d3-d3+d4+d4-EDF3x1-4x2=0x1+2x2=8得x1=3.2，x2=2.4例2用圖解法求解目標規(guī)劃問題：

10x1+12x2+d1-

–d1+＝62.5x1+2x2+d2-

–d2+=102x1+x2

≤8

x1,x2，d1-,d1+,d,2-,d2+

≥01x1x2430215623456d1-d1+d2+d2-D(0.625,4.6875)C(0,5.2083)于是，C,D兩點及CD線段上的所有點(無窮多個)均是該問題的最優(yōu)解。其中：C點對應的解為：x1=0，x2=5.2083；D點對應的解為：x1=0.6250，x2=4.6875；

例3、用圖解法求解線性規(guī)劃模型

30x1+12x2+d1-

–d1+＝25002x1+x2+d2-

–d2+=140

x1,x2，di-,di+

≥0

x1+d3-

–d3+＝60

x2+d4-

–d4+＝100

minZ=P1d1-

+P2(2.5d3++d4+)

+P3d2+于是，確定D點的坐標x1=60，x2=58.3為所求的滿意解。即D(60,58.3)驗算將x1=60，x2=58.3代入約束條件，有

以上驗算表明，若A、B的計劃生產(chǎn)量分別為60件和58.3件，所需甲種原料的數(shù)量超過了現(xiàn)有庫存量。這就意味著，在現(xiàn)有資源條件下，求得的為非可行解。為了使這個解能成為可行解，工廠領導必須采取先進的技術手段和有效管理措施降低A、B產(chǎn)品對甲種原料的消耗量。顯然，A、B產(chǎn)品每件所需甲種原料量應變?yōu)樵邢牧康?8.5%(140/178.3=78.5%)，才能使求得的生產(chǎn)方案(x1=60，x2=58.3)成為可行方案。

30x1+12x2+d1-

–d1+＝25002x1+x2+d2-

–d2+=140

x1,x2，di-,di+

≥0

x1+d3-

–d3+＝60

x2+d4-

–d4+＝100

minZ=P1d1-

+P2(2.5d3++d4+)+P3d2+分析在上述兩個例子中，前一個例子求得的結果為可行解，后一個例子求得的結果為非可行解。這就表明目標規(guī)劃模型的求解結果可以是非可行解。而這正是目標規(guī)劃模型與線性規(guī)劃模型在求解思想上的差別，即線性規(guī)劃立足于求滿意解。目標規(guī)劃模型的滿意解雖然可能是非可行解，但它卻有助于了解問題的薄弱環(huán)節(jié)以便有的放矢改進工作。練習：用圖解法求解下列目標規(guī)劃問題

(2)(3)(4)(1)CD結論：有無窮多最優(yōu)解。C（2，4），D（10/3，10/3）2、用圖解法解下列目標規(guī)劃模型x1=400,x2=0,Z=80p3x2

1002003004005000x1100200300400最滿意解為x1=400,x2=0§5.4目標有優(yōu)先級的目標規(guī)劃解法--加權法產(chǎn)品A產(chǎn)品B產(chǎn)品C條件利潤（萬元/噸）941總利潤最大化耗用原料（噸/噸）425耗用原料總量不超過38噸排放污染（m3/噸）213排放污染總量不超過26m3銷售價格（萬元/噸）301020銷售總額不低于100萬元總產(chǎn)量（噸）111總產(chǎn)量不低于18噸如果以利潤為目標函數(shù)，線性規(guī)劃模型為：maxz=9x1+4x2+x3s.t.4x1+2x2+5x3≤38 （1）原料總量約束2x1+x2+3x3≤26 （2）排放污染約束30x1+10x2+20x3≥100 （3）銷售總額約束x1+x2+x3≥18 （4）總產(chǎn)量約束x1,x2,x3≥0例：線性規(guī)劃解得：x1=1,x2=17,x3

=0，maxZ=77目標規(guī)劃如果利潤期望值為77，將利潤、耗用原料等五個因素作為目標，確定各目標的理想值以及偏差變量如下：目標產(chǎn)品A產(chǎn)品B產(chǎn)品C目標的理想值正偏差變量負偏差變量利潤（萬元/噸）94177d1+d1-耗用原料（噸/噸）42538d2+d2-排放污染（m3/噸）21326d3+d3-銷售價格（萬元/噸）301020100d4+d4-總產(chǎn)量（噸）11118d5+d5-如果目標大于理想值，正偏差變量大于0，小于理想值，負偏差變量大于0。因此，對第i個目標，有

如果各目標無優(yōu)先級，要使所有的目標總偏差最小，即無優(yōu)先級的目標規(guī)劃模型為：同一個目標的正負偏差變量，不可能兩個同時大于0。這一結果的實際意義也是很清楚的：任何一個目標，不可能既大于理想值，又小于理想值。

用單純形法，得到目標規(guī)劃的最優(yōu)解、各目標的值以及偏差變量的值產(chǎn)品A產(chǎn)品B產(chǎn)品C目標的理想值正偏差變量負偏差變量產(chǎn)量（噸）0100RHSdi+di-達到的目標值利潤（萬元）4077037耗用原料（噸）3038018排放污染（m3）1026016銷售價格（萬元）10010000總產(chǎn)量（噸）101808最優(yōu)解實現(xiàn)值偏差變量目標有優(yōu)先級的目標規(guī)劃產(chǎn)品A產(chǎn)品B產(chǎn)品C目標的理想值正偏差變量負偏差變量產(chǎn)量（噸）0100RHSdi+di-達到的目標值利潤（萬元）4077037耗用原料（噸）3038018排放污染（m3）1026016銷售價格（萬元）10010000總產(chǎn)量（噸）101808在上面的例子中，利潤、耗用原料、排放污染、銷售額、總產(chǎn)量等五個目標是一視同仁的，最優(yōu)解是使偏離五個目標的總偏差之和最小。在實際問題中，這些目標往往是有輕重緩急的。

目標產(chǎn)品A產(chǎn)品B產(chǎn)品C優(yōu)先級Pi目標的理想值正偏差變量負偏差變量利潤（萬元/噸）941177d1+d1-

耗用原料（噸/噸）425438d2+d2-排放污染（m3/噸）213326d3+d3-銷售價格（萬元/噸）3010205100d4+d4-總產(chǎn)量（噸）111218d5+d5-確定五個目標的優(yōu)先級Pi（Pi=1，2，3，4，5），數(shù)字越小優(yōu)先級越高目標規(guī)劃的模型為：優(yōu)先級Pi14352

目標產(chǎn)品A產(chǎn)品B產(chǎn)品C優(yōu)先級權重理想值正偏差負偏差利潤（萬元/噸）941110000077d1+d1-耗用原料（噸/噸）425410038d2+d2-排放污染（m3/噸）2133100026d3+d3-銷售價格（萬元/噸）30102051