第7章 目標規(guī)劃

1、山西大學經濟與管理學院山西大學經濟與管理學院運籌學運籌學主講：范建平主講：范建平 博士博士第7章 目標規(guī)劃第7章 目標規(guī)劃2022年6月5日星期日山西大學經濟與管理學院 范建平2p目標規(guī)劃（目標規(guī)劃（Goal programming，GP）是多目標線性規(guī)劃）是多目標線性規(guī)劃的一種模型與方法，可以解決線性規(guī)劃無法解決的一些的一種模型與方法，可以解決線性規(guī)劃無法解決的一些實際問題。實際問題。p它以線性規(guī)劃為基礎，其模型結構與算法本質上同線性它以線性規(guī)劃為基礎，其模型結構與算法本質上同線性規(guī)劃一致，但也有自己的特點。規(guī)劃一致，但也有自己的特點。7.1 基本模型2022年6月5日星期日山西大學經濟與管

2、理學院 范建平37.1.1 問題的由來2022年6月5日星期日山西大學經濟與管理學院 范建平4p線性規(guī)劃模型在實際應用中主要有以下線性規(guī)劃模型在實際應用中主要有以下2點不足：點不足：n（1）線性規(guī)劃只有一個目標函數，只能使一個目標最優(yōu)化。線性規(guī)劃只有一個目標函數，只能使一個目標最優(yōu)化。n（2）線性規(guī)劃能付諸實施的一個前提是可行域非空集。線性規(guī)劃能付諸實施的一個前提是可行域非空集?！纠?-1】2022年6月5日星期日山西大學經濟與管理學院 范建平5p某化工廠用某種成套設備生產甲、乙兩種產品，單耗分別為每噸某化工廠用某種成套設備生產甲、乙兩種產品，單耗分別為每噸2、3工時，而設備正常生產每天最大運

3、行能力為工時，而設備正常生產每天最大運行能力為18工時，需要增加能工時，需要增加能力可加班運行。甲、乙產品利潤分別為力可加班運行。甲、乙產品利潤分別為500元元/噸、噸、400元元/噸，每周噸，每周需求量分別為需求量分別為30、20噸。該廠希望兩種產品，每天利潤達到噸。該廠希望兩種產品，每天利潤達到4000元元以上，產量符合需求量比例，還希望充分利用設備正常生產能力，以上，產量符合需求量比例，還希望充分利用設備正常生產能力，但盡量避免加班，則應如何安排生產？但盡量避免加班，則應如何安排生產？ 單耗單耗/ /（工時（工時/ /噸）噸）最大生產能力最大生產能力/(/(工時工時/ /天天) )甲乙設

4、備2318利潤/（1100元/件）54需求量（噸/周）3020【例7-1】2022年6月5日星期日山西大學經濟與管理學院 范建平63本例有利潤、產量、產能 項目標，屬于。若只考慮利潤一項目標，而將產量、產能目標轉化為約束條件，就成為一個多目線性標規(guī)劃問解題規(guī)劃問題。 121212121212zmax 54064s.t. 2302+7-1a318,0 xxzxxxxxxxxxx設 每天甲、乙產品的產量為、噸，總利潤為1 100 元，數學模型如下：、式：甲、乙產品的周需求量除以每周工作日5.式：甲、乙產品的需求量比例約束【例7-1】山西大學經濟與管理學院 范建平7CAO(0,0)z法向2x1+3x

5、2=18x1x269BED*129 2/,3/;347-1O0F5Fxxz噸用圖解法求解，見圖，可行域為線段，而點 即給出最優(yōu)解該結果未能使利潤達到目標天噸 天元4值：000元。2x1-3x2=0圖 7-1 1212121211227-1b5447-27-1amax 54064230s.t.2318,0.0 xxzxxxxxxxxxx若給式增加利潤約束：見圖F【例7-1】CAO(0,0)z法向2x1+3x2=18x1x269BED1254407-2xx見圖可行域為空集。線增加性規(guī)一個新約束。：劃無能為力。2x1-3x2=0F圖 7-2 而目標規(guī)劃則不把式、作為硬性約束，而是作為三個目標變通處理

6、。108NGM5x1+4x2=4012D6,2EMNDxx若各目標優(yōu)先滿足的順序為、這樣，雖然利潤、產量目、，則應在線段上標都未滿足，卻是在不選擇離直線加班的前提最近的一點作為問題的下，利潤目解：標最優(yōu)方案。12120 23,80 23BGOADECGxx這樣，利潤、產量目標都得若各目標優(yōu)先滿足的順序為、到滿足，但是每天消耗設備能力約為2，則應在線1工時，超段上選擇離五邊形最近的一點 作過正常生產能力18工時，需加為問題的解：班3工時。 121212121122max 54064230s7-1b.t.2544318,00zxxxxxxxxxxxx7.1.2 基本概念山西大學經濟與管理學院 范建

7、平9 7-121-11.7目標約束剛性約束彈性約束：也稱系統(tǒng)約束，必需滿足的約束。如的約束、式；：也稱目標約束，是盡量【例】【例】目標規(guī)劃往往沒滿足有最的約束；如的式、優(yōu)解，只有滿意解。 121212121122max 54064230s7-1b.t.2544318,00zxxxxxxxxxxxxCAO(0,0)z法向2x1+3x2=18x1x269BED2x1-3x2=0F圖 7-2108NGM5x1+4x2=407.1.2 基本概念+2.dd為了刻畫滿意解對應的每一目標的實際值與目標值的差距，需要引入偏差變量的概念與符號：，表示實際值未達目標值的差距，表示實際值超過目標值的差距正、負偏差變

8、偏差變量負偏差變量正量二者，至少一個取偏差變量值為0.1211-7-1b54+40 xxdd【例7 1】的模型，可為其式同時引入正、負偏差變量，成為：譬如， 111212111211121114025454400;54400;54=40=30;ddxxxxddxxddxxdd當實際值未達到目標值時，即時,則當時,則偏差變量二者當時,，至少一個取值為0，更具體地、0、0、說：則0、7.1.2 基本概念1221,2,3.rkrrPPPP kr由于目標規(guī)劃有不止一個目標，為了區(qū)分其重要性與重要程度，需要引入優(yōu)先級的概念與符號：若有個目標的重要性相差懸殊，則可劃分為 個，并用優(yōu)先因子表示重要性，其中“

9、”表示“遠遠重要于”。優(yōu)先因子是定性因優(yōu)先級與權數素，非優(yōu)先級數量指標。-+dd若有幾個目標的重要性相差不是很懸殊，則可歸于同一優(yōu)先級。又，則為區(qū)別其重要程度的差異，還可以賦予不同的權數；另外，對偏差變量 ，也可賦予不同的權數，而權數是無實際量綱的若其數量綱相同量指標。【例7-1】續(xù)123-PPP假設：該廠提出3個目標并規(guī)定優(yōu)先級如下：甲、乙兩種產品每天利潤達到4000元以上；：甲、乙兩種產品的產量符合需求量比下面例；：充分利以【例7 1】來說明如何建立目標規(guī)劃用設備正常生產能力，并盡量模型避免加班。12111222123354+402 -3+023+1,2,318,kxxddxxddxxdd

10、zk 這樣，式、全都需要改成下述目標約束：利潤：產量：產下面，分別建立每個優(yōu)先級能：的目標函數，記為稱為分目標函數【例7-1】續(xù)2022年6月5日星期日山西大學經濟與管理學院 范建平13 1112115440=1in4000mxxddzd 分目標函數：為使兩種產品每天利潤達到元以上，即，應使；即便達不到這點，也應使最小化，即0 122222222222 -30=0+=0+min2+xxdddddzddd為使兩種產品產量符合需求量比例，即，應使或；即便達不到這點，也應使最小化，即 3233333=min3+20ddddzdd為充分利用設備正常生產能力，并盡量避免加班，應使；即便達不到這點，寧肯加

11、班也不閑置設備能力；若認定前者重要程度是后者2倍，則賦予不同權數1、2，即有：，【例7-1】續(xù)2022年6月5日星期日山西大學經濟與管理學院 范建平14121211112221233121222333-GP6454+40s.t.2 -3+023+18,7-2,0 ,1mi,2,3n 2kkxxxxddxxddxxzPdP ddP dxdddxddk為簡化表示，可將上述3個目標合并為如下形式的1個目標，得【例7 1】的模型：7.1.3 一般模型11173=,1,2,73s.t.,1,2,73,min ,0 ,1,2,73nsjjsjnirkkjjiiijjkkkrmaa xbslba xddez

12、imcx ddjndP z 一般目標規(guī)劃的模型如下：或LLL系統(tǒng)約束目標約束分目標函數7.1.3 一般模型 m1inikiezd若容許不達目標而避免超過目標值 ，如費用、產能、人力等消耗指標，則只引入正偏差變量，即令 -2minikiezd若容許超過目標而避免不達目標值 ，如利潤、收益、品質等產出指標，則只引入負偏差變量，即令 -m3inkkiiiiikzw dew d若既避免超過，又避免不達目標，而希望恰好達到目標值 ，則需同時引入正、負偏差變量，并且分別賦權，即令 -1mi4n0.kimkkiikiiiikwwzw dw d若有幾個目標屬于同一優(yōu)先級，且其量綱相同，則需適當引入正、負偏差變

13、量，并且分別賦權，或可為即令目標規(guī)劃的應用案例-加班時間問題17例：某音像店有5名全職售貨員和4名兼職售貨員，全職售貨員每月工作160小時，兼職售貨員每月工作80小時。根據記錄，全職每小時銷售CD25張，平均每小時工資15元，加班工資每小時22.5元。兼職售貨員每小時銷售CD10張，平均工資每小時10元，加班工資每小時10元?，F(xiàn)在預測下月CD銷售量為27500張，商店每周開門營業(yè)6天，所以可能要加班。每出售一張CD盈利1.5元。 商店經理認為，保持穩(wěn)定的就業(yè)水平加上必要的加班，比不加班就業(yè)水平要好，但全職銷售員如果加班過多，就會因為疲勞過度而造成效率下降，因此不允許每月加班超過100小時，建立

14、相應的目標規(guī)劃模型。目標規(guī)劃的應用案例-加班時間問題18首先，確定目標約束的優(yōu)先級。如下：P1：下月的CD銷售量達到27500張；P2：全職售貨員加班時間不超過100小時；P3：保持全體售貨員充分就業(yè)，對全職的要比兼職的加倍加倍優(yōu)先考慮；P4：盡量減少加班時間，對兩種售貨員區(qū)別對待，權重權重由他們對利潤的貢獻而定。其次，建立目標約束函數（1）銷售目標約束，設全體全職售貨員下月的工作時間x1，全體兼職售貨員下月的工作時間 x2；達不到銷售目標的偏差d1-，超過銷售目標的偏差 d1+。 1111211min251027500GPdxxdd 目標規(guī)劃的應用案例-加班時間問題19 （2）正常工作時間約

15、束。設全體全職售貨員下月的停工時間d2-，加班時間d2+ ；全體兼職售貨員下月的停工時間d3-，加班時間d3+。（3）加班時間的限制。設全體全職售貨員下月的加班不足100小時的偏差d4-，加班超過100小時的偏差 d4+ 。兩類售貨員區(qū)別對待，權重比d2+:d3+ =1:3，另一加班目標約束為3323122233min(2)800320GPddxddxdd224144min900GP dxdd4423122233min(3)800320GP ddxddxdd目標規(guī)劃的應用案例-加班時間問題20 第三，按目標的優(yōu)先級，寫出相應的目標規(guī)劃模型：1124323423121112223314412mi

16、n(2)(3)251027500800320s.t.900,0,01,2,3,4llGPdP dPddP ddxxddxddxddxddx xddl運用LINGO軟件求解得 x1=900,x2=500，下月共銷售CD盤27500張，獲利275001.5-80015-10022.5-50010=22000。7.2 基本方法2022年6月5日星期日山西大學經濟與管理學院 范建平212022年6月5日星期日山西大學經濟與管理學院 范建平22pGP的基本方法與的基本方法與LP類同，也是單純形法，稱為目標規(guī)類同，也是單純形法，稱為目標規(guī)劃單純形法。由于劃單純形法。由于GP有有r(r2)個分目標，所以其單

17、純形個分目標，所以其單純形表中的檢驗數也分表中的檢驗數也分r行，各行檢驗數需按不同優(yōu)先級的數行，各行檢驗數需按不同優(yōu)先級的數據分別計算，且據分別計算，且由高到低，逐級優(yōu)化由高到低，逐級優(yōu)化（化為非負）。下（化為非負）。下面以面以【例例7-1】說明該法的基本步驟與運算過程。說明該法的基本步驟與運算過程?！纠?-1】2022年6月5日星期日山西大學經濟與管理學院 范建平231122121211122212332231336454+40s.t.2 -3+023+18,0 ,1,2,3min7-22 kkxxxxddxxzPdP ddP dddxxddx xdddk7.2 基本方法【例7-1】續(xù)132

18、41211122212331122233123346454+40s.t.2 -3+023+18,0 ,1,max ,327-42kkxxxxxxddxxzPdPddPdddxxddx x x x ddkd34-GP7 2-1-jxxx由于【例7 1】等一切問題，其目標函數中一切結構變量的系數恒為0，且目標要求恒為，所以只需將一切偏差變量的權系數全部反號，就可將目標函數標準化。在模型的標準化min、兩式引入松弛變量，便得【例7 1。、】的標準型o34,1,2,37-4kx x dk以為基變量，式已是典式。27-47-1.為式建立初始單純形表，見表建立初始單純形表o1231234112233341

19、122331237-17-1-10-1-26000040000-14054001-1000000000-118230000001-1-5-400100000-1-101010000010100-12-3001-1-2300000000000-22kjjPPPPcxxxxddddddxxPdPdPdPPP表【例】的初始單純形表基解 -3000000037.2 基本方法【例7-1】續(xù)B7-13LP2,1,2,7,-4b-5TjBjjjjC acjnCc表中，檢驗數按優(yōu)先級分為 行，每行檢驗數的計算公式同單純形法的：其中即列。L213B27-17-57-1jjjjjkjjkkPPPPPPcacaCP

20、ac但是，各列數據和，以及各行數據和，。如表中行檢驗數的計算結果，及其按公式計算時所用數據， ， ，即為表中紅色的數字；而行其他檢驗數全為0，不必計算只限于同名行檢驗數計算時專用。 、 行的檢驗數也是這樣計算出的。113PP按優(yōu)先級由高到低，依次檢查表中各行檢驗數；現(xiàn)因行有負檢驗最優(yōu)性數，則級。檢驗分目標非優(yōu)o1231234112233341122331237-17-10000-10-1-1-1-2061010000000040101000000-14054001-10000-102-300001-100-118230000001-1-5-400100000-2300000200-2kjjPP

21、PPcxxxxddddddxxPdPdPdPPP表【例】的初始單純形表基解 -300000003211L-45PxPd這一步驟同單純形法一致，在當前存在負檢驗數的行找出最小者 5，確定進基；再按最小比值規(guī)則確定離基變量與主元2；確定主元轉。oo7.2 基本方法【例7-1】續(xù) 53-5-abcj這一步也同單純形方法一致，但需將主列的欄3行檢驗數全都化為0.對表7 1實施該步驟后，得到表7 2，其中空白處數據都為0,。反復運用，得到表換基7 2， 。運算ooo: 123337-2 c,jP PPPP表中欄行檢驗數已全非負，這兩級分目標已獲最優(yōu)； 行還有負檢驗數，但負檢驗數所在列的上面行中都存在正檢

22、驗數，這意味著 級分目標無法獲得最優(yōu)，算法結束。否則，要將 行檢驗數化為非負，其結果必將破壞更高級分目標的優(yōu)化。7.2 基本方法【例7-1】續(xù) 31jkP的如下：若欄各行檢驗數全為非負，則當前解為步驟最優(yōu)性最優(yōu)解，運檢。驗準則算結束o在目標規(guī)劃應用中，如果各分目標的優(yōu)先級發(fā)生變更，其前后求解結果也大相徑庭。而優(yōu)先權的劃分、權數的確定，完全取決于決策者的主觀判斷，對此沒有明確的程序。因此，目標規(guī)劃的應用，與線性規(guī)劃不同，往往不能一次解決問題，需要多次變更優(yōu)先權和權數并多次求解，然后比較權衡，從中選擇一個比較滿意的解作為最終決策。 +12kkPP若行及其上面各行檢驗數全為非負，但行存在負檢驗數，而

23、且該行負檢驗數上面行中都存在正檢驗數，則當前解為滿意解，運算結束。 3kP若行存在一個負檢驗數，而且它所在列的上面行中檢驗數均為0，但該列系數全都非正，則問題無解，停止運算。 44若非上述情形，則轉，繼續(xù)運算。o7.3 實用模型2022年6月5日星期日山西大學經濟與管理學院 范建平307.3.1 營運管理模型-某公司經營的某種商品由其所轄的2個工廠供應3個客戶，每天的供需量 噸以及工廠銷給客戶1噸該商品所獲利潤如表7 3所示，最優(yōu)方案如表7【例7 2】 4所示?？蛻艨蛻艄S工廠利潤利潤/ /（元（元/ /噸）噸）日供量日供量/(/(噸噸) )B1B2B3A1700900700120A26008

24、0050080日需量/(噸)9060100客戶客戶工廠工廠供應量供應量/ /噸噸日供量日供量/(/(噸噸) )B1B2B3A1106050120A28080A3（虛）5050日需量/(噸)9060100250表7-3 利潤表表7-4 最優(yōu)方案【例7-2】 31440 101B270%3900%*最大總利潤：由于所得方案僅考慮總利潤最大，不符合很多實際情況。為此公司決定重新研擬運銷方案，以滿足下述目標。客戶所需量必須全部滿足供應；其他客戶的滿足率不低于；z元運銷總利潤不低于原方案的。試建立其數學模型?？蛻艨蛻艄S工廠供應量供應量/ /噸噸日供量日供量/(/(噸噸) )B1B2B3A1106050

25、120A28080A3（虛）5050日需量/(噸)9060100250【例7-2】11121321222311211222132313231111+2122122233111213212221112234334+120+80+90+60+100s.t.+-=100+-=63+-=4min 27+9+7+6+85+-xxxxxxxxxxxxxxddxxddxxddxxxxzP ddPxxdddP d解 數學模型如下：4=129601,2,3;1,2,3,4,0 ,1,2,3,4ijkkdxijddk系統(tǒng)約束，是供不應求運輸模型的典型約束P1P2P31233B70%PP90%P 客戶所需量必須全部

26、滿足供應； 其他客戶的滿足率不低于； 運銷總利潤不低于原方案的。7.3.2 晉酬管理模型-3某醫(yī)院現(xiàn)有醫(yī)生28名，定編人數32名，其職稱級別等情況見表【7 】7例5。級別級別職稱職稱津貼（元津貼（元/ /月月/ /人）人）現(xiàn)有人數現(xiàn)有人數定編人數定編人數 主任醫(yī)師280023副主任醫(yī)師210035主治醫(yī)師1500812醫(yī)師10001512表7-5 %14.523、級的人數不低于各級定編人數的30、40、50。 并且規(guī)定，級人員的缺額由招聘增補，其他各級人員的增補從原有次低級現(xiàn)擬進別人員行職稱調整中晉升。另且其目標要求如下：每月津貼總額不超過萬元；知級人員行將退休一人。則應如何確定各級人各級人員

27、都不超過定編人員調整人數？試建立數數；升入學模型?！纠?-3】 34231211234123411110.10 15- +0.15 8-+0.21 3- +0.28 2-1+4.57+6+5+10897+6+5+11,2,3,4+-0=891minjxxxxxxxxxxxxxxxjjddzxd表示第級人員增 每補數：故月津貼解 設總額的目標約束與目標函數化簡：有得【例7-3】 343423242212111512381243522 1322xxxxxxxxxxxxxx 定編人數的目標約束與目標函數34241212232344552345=3=4=2=2+-+-+-+-min+dddddxxxd

28、ddzdxdxxxdd故有：【例7-3】 1233 0.315 0.42132 0.56xxx 各級晉級人數的目標約束與目標函數6677883637812+-+-+-min=1=2=6+xxxddddddzddd故有：【例7-3】12341134222333124415516627+1122345738836787 +6+5+10+-= 89-+-=3-+-=4- +-=2+-=2s.t.+-=1+-=2+-=6min +0ijzPdxxxxddxxddxxddxxddxP ddddPddxddxddxdddxidd綜上，本例數學模型如下，整數，：1,2,3,4,0 ,1,2,8kkddkL7

29、.3.3 庫存管理模型4-某公司以批發(fā)方式經營某種商品，預計該商品今后4個月的購銷價格如表7 6所示。該公司經營這種商品肯定能批發(fā)銷售出去，但最大銷量受倉庫容量限制，正常庫容量為每月初批發(fā)銷售，每月中旬采購進貨，購貨資金完全依賴銷售收8噸，非常需要時也可占用機動庫容量2噸。該公司。已知第一月初有庫存該貨6噸，其采購價格為5.4萬【例】入7元/噸。月份月份1 12 23 34 4購價5.55.45.65.7銷價5.85.66.06.2表7-6 1234該公司預定今后4個月經營目標如下：每月都使用正常庫容，盡量不要超貯；每月下旬都預留1萬元機動資金，以備急用；力求今后 個月的總盈利達到。應如何擬定

30、購銷計劃？試建立最大數學模型?！纠?-4】12113112241122331,2,3,41,2,3,466- +6- + -+6- + -+-+1.jjxjjyjjyyyxyyx yxyyx yx yx表示第月的采購量 噸 ；表示第月的銷售量 噸 ；每月的銷量不能解 銷量約束超過月初庫存量設 111212123123123412346666ysyyxsyyyxxsyyyyxxxs標準化：【例7-4】112112311223411223345.55.85.45.8-5.5 +5.65.65.8-5.5 +5.6-5.4+65.75.8-5.5 +5.6-5.4+6-5.6+ .22.6xyxyxyxyxyxyxyxyxyxy 采購費用約束每月中旬的采購費用不能超過月初的銷售收入1151212612312371234123485.