1、目標(biāo)規(guī)劃第1頁，共29頁，2022年，5月20日，9點12分，星期五1 目標(biāo)的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型問題的提出：目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理多目標(biāo)決策的需要而由線性規(guī)劃逐步發(fā)展起來的一個分支。由于現(xiàn)代化企業(yè)內(nèi)專業(yè)分工越來越細(xì)，組織機(jī)構(gòu)日益復(fù)雜，為了統(tǒng)一協(xié)調(diào)企業(yè)各部門圍繞一個整體的目標(biāo)工作，產(chǎn)生了目標(biāo)管理這種先進(jìn)的管理技術(shù)。目標(biāo)規(guī)劃是實行目標(biāo)管理的有效工具，它根據(jù)企業(yè)制定的經(jīng)營目標(biāo)以及這些目標(biāo)的輕重緩急次序，考慮現(xiàn)有資源情況，分析如何達(dá)到規(guī)定目標(biāo)或從總體上離規(guī)定目標(biāo)的差距為最小。 1961年，美國學(xué)者A.Charnes和W.Cooper首次在管理模型和線性規(guī)劃的工業(yè)應(yīng)用一書中提

2、出目標(biāo)規(guī)劃的相關(guān)概念，并在1965年以后逐步形成獨(dú)立分支。2022/9/242第2頁，共29頁，2022年，5月20日，9點12分，星期五1 目標(biāo)的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型例1 常山機(jī)器廠生產(chǎn)I、兩種產(chǎn)品。這兩種產(chǎn)品都要分別在A、B、C三種不同設(shè)備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺時和利潤如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計劃，使企業(yè)總的利潤最大？ 設(shè) 備產(chǎn) 品 A B C利潤（元） I 2 4 0 2 2 0 5 3 有 效 臺 時 12 16 152022/9/243第3頁，共29頁，2022年，5月20日，9點12分，星期五1 目標(biāo)的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型ma

3、x Z = 2x1 + 3x2 x1 0 , x2 0s.t. 2x1 + 2x2 12 4x1 16 5x2 15 解：設(shè)x1、x2分別為I、兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為：其最優(yōu)解為x13，x23，z15元2022/9/244第4頁，共29頁，2022年，5月20日，9點12分，星期五1 目標(biāo)的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型但企業(yè)的經(jīng)營目標(biāo)不僅僅是利潤，而且要考慮多個方面，如：力求使利潤指標(biāo)不低于15元；考慮到市場需求，I、II兩種產(chǎn)品的生產(chǎn)量需保持1:2的比例；A為貴重設(shè)備，嚴(yán)格禁止超時使用；設(shè)備C必要時可以加班，但加班時間要控制；設(shè)備B即要求充分利用，又盡可能不加班，而且在重要性上設(shè)備B是設(shè)備

4、C的3倍。要考慮上述多方面的目標(biāo)，需要借助目標(biāo)規(guī)劃的方法。2022/9/245第5頁，共29頁，2022年，5月20日，9點12分，星期五1 目標(biāo)的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型線性規(guī)劃模型存在的局限性：1）要求問題的解必須滿足全部約束條件，實際問題中并非所有約束都需要嚴(yán)格滿足。2）只能處理單目標(biāo)的優(yōu)化問題。實際問題中，目標(biāo)和約束可以相互轉(zhuǎn)化。3）線性規(guī)劃中各個約束條件都處于同等重要地位，但現(xiàn)實問題中，各目標(biāo)的重要性即有層次上的差別，同一層次中又可以有權(quán)重上的區(qū)分。4）線性規(guī)劃尋求最優(yōu)解，但很多實際問題中只需找出滿意解就可以。2022/9/246第6頁，共29頁，2022年，5月20日，9點12分，

5、星期五1 目標(biāo)的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型 目標(biāo)規(guī)劃怎樣解決上述線性規(guī)劃模型建模中的局限性？1. 設(shè)置偏差變量，用來表明實際值同目標(biāo)值之間的差異。偏差變量用下列符號表示：d+超出目標(biāo)的偏差，稱正偏差變量d-未達(dá)到目標(biāo)的偏差，稱負(fù)偏差變量正負(fù)偏差變量兩者必有一個為0。 當(dāng)實際值超出目標(biāo)值時： d+0, d-=0; 當(dāng)實際值未達(dá)到目標(biāo)值時： d+=0, d-0; 當(dāng)實際值同目標(biāo)值恰好一致時： d+=0, d-=0;故恒有d+d-=02022/9/247第7頁，共29頁，2022年，5月20日，9點12分，星期五1 目標(biāo)的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型2. 統(tǒng)一處理目標(biāo)和約束。 對有嚴(yán)格限制的資源使用建立系

6、統(tǒng)約束，數(shù)學(xué)形式同線性規(guī)劃中的約束條件。如B和C設(shè)備的使用限制。 對不嚴(yán)格限制的約束，連同原線性規(guī)劃建模時的目標(biāo)，均通過目標(biāo)約束來表達(dá)。1）例如要求I、II兩種產(chǎn)品保持1:2的比例，系統(tǒng)約束表達(dá)為：x1/x2 =1/2或2x1=x2 。由于這個比例允許有偏差，當(dāng)2x1x2時，出現(xiàn)正偏差d+，即：2x1-d+ =x2或2x1x2-d+ =02022/9/248第8頁，共29頁，2022年，5月20日，9點12分，星期五1 目標(biāo)的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型正負(fù)偏差不可能同時出現(xiàn)，故總有：2x1x2+d-d+ =0 若希望I的2倍產(chǎn)量不低于II的產(chǎn)量，即不希望d-0,用目標(biāo)約束可表為: 若希望I的2倍

7、產(chǎn)量低于II的產(chǎn)量，即不希望d0,用目標(biāo)約束可表為: 若希望I的產(chǎn)量恰好等于II的產(chǎn)量，即不希望d0,也不希望d-0用目標(biāo)約束可表為:2022/9/249第9頁，共29頁，2022年，5月20日，9點12分，星期五1 目標(biāo)的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型3）設(shè)備C必要時可加班及加班時間要控制，目標(biāo)約束表示為：2）力求使利潤指標(biāo)不低于15元，目標(biāo)約束表示為：4）設(shè)備B既要求充分利用，又盡可能不加班，目標(biāo)約束表示為：2022/9/2410第10頁，共29頁，2022年，5月20日，9點12分，星期五1 目標(biāo)的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型3. 目標(biāo)的優(yōu)先級與權(quán)系數(shù)在一個目標(biāo)規(guī)劃的模型中，為達(dá)到某一目標(biāo)可犧牲其

8、他一些目標(biāo)，稱這些目標(biāo)是屬于不同層次的優(yōu)先級。優(yōu)先級層次的高低可分別通過優(yōu)先因子P1,P2,表示。對于同一層次優(yōu)先級的不同目標(biāo)，按其重要程度可分別乘上不同的權(quán)系數(shù)。權(quán)系數(shù)是一個個具體數(shù)字，乘上的權(quán)系數(shù)越大，表明該目標(biāo)越重要?，F(xiàn)假定： 第1優(yōu)先級P1企業(yè)利潤； 第2優(yōu)先級P2I，II產(chǎn)品的產(chǎn)量保持1:2的比例 第3優(yōu)先級P3設(shè)備C,B盡量不超負(fù)荷工作。其中設(shè)備B的重要性比設(shè)備C大三倍。2022/9/2411第11頁，共29頁，2022年，5月20日，9點12分，星期五1 目標(biāo)的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型上述目標(biāo)規(guī)劃模型可以表示為：系統(tǒng)約束目標(biāo)約束2022/9/2412第12頁，共29頁，2022年

9、，5月20日，9點12分，星期五1 目標(biāo)的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式達(dá)成函數(shù)目標(biāo)約束其中：gk為第k個目標(biāo)約束的預(yù)期目標(biāo)值， 和 為pl 優(yōu)先因子對應(yīng)各目標(biāo)的權(quán)系數(shù)。系統(tǒng)約束2022/9/2413第13頁，共29頁，2022年，5月20日，9點12分，星期五1 目標(biāo)的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型用目標(biāo)規(guī)劃求解問題的過程：明確問題，列出目標(biāo)的優(yōu)先級和權(quán)系數(shù)構(gòu)造目標(biāo)規(guī)劃模型求出滿意解滿意否？分析各項目標(biāo)完成情況據(jù)此制定出決策方案NY2022/9/2414第14頁，共29頁，2022年，5月20日，9點12分，星期五2 目標(biāo)規(guī)劃的圖解分析法目標(biāo)規(guī)劃的圖解法：適用兩個變量的目標(biāo)規(guī)劃

10、問題，但其操作簡單，原理一目了然。同時，也有助于理解一般目標(biāo)規(guī)劃的求解原理和過程。圖解法解題步驟：1. 將所有約束條件（包括目標(biāo)約束和絕對約束，暫不考慮正負(fù)偏差變量）的直線方程分別標(biāo)示于坐標(biāo)平面上。2. 確定系統(tǒng)約束的可行域。3. 在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值增大的方向2022/9/2415第15頁，共29頁，2022年，5月20日，9點12分，星期五2 目標(biāo)規(guī)劃的圖解分析法4. 求滿足最高優(yōu)先等級目標(biāo)的解5. 轉(zhuǎn)到下一個優(yōu)先等級的目標(biāo)，在不破壞所有較高優(yōu)先等級目標(biāo)的前提下，求出該優(yōu)先等級目標(biāo)的解6. 重復(fù)4，直到所有優(yōu)先等級的目標(biāo)都已審查完畢為止7. 確定最優(yōu)解和滿

11、意解。2022/9/2416第16頁，共29頁，2022年，5月20日，9點12分，星期五2 目標(biāo)規(guī)劃的圖解分析法例2 用圖解法求解目標(biāo)規(guī)劃問題2022/9/2417第17頁，共29頁，2022年，5月20日，9點12分，星期五2 目標(biāo)規(guī)劃的圖解分析法x2x1d1-d1+d2+d2-d3-d3+d4-d4+滿意解(2,4)04683462 252022/9/2418第18頁，共29頁，2022年，5月20日，9點12分，星期五2 目標(biāo)規(guī)劃的圖解分析法x1x2(a)(b)d1+d1-(c)d2-d2+(d)d3-d3+GD滿意解是線段GD上任意點其中G點X(2,4),D點X(10/3,10/3)

12、05.51055.6112,410/3,10/35107例32022/9/2419第19頁，共29頁，2022年，5月20日，9點12分，星期五2 目標(biāo)規(guī)劃的圖解分析法Ox1x22040605020406050abd1-d1+d2-d2+cdd3-d3+d4-d4+(24,26)滿意解X=(24，26)例42022/9/2420第20頁，共29頁，2022年，5月20日，9點12分，星期五2 目標(biāo)規(guī)劃的圖解分析法學(xué)習(xí)要點：1.理解目標(biāo)規(guī)劃概念； 2.能夠運(yùn)用圖解方法求解模型。作業(yè)： （P144） 5.3（圖解法）2022/9/2421第21頁，共29頁，2022年，5月20日，9點12分，星期

13、五3 用單純形法求解目標(biāo)規(guī)劃目標(biāo)規(guī)劃與線性規(guī)劃的數(shù)學(xué)模型的結(jié)構(gòu)相似可用前述單純形算法求解目標(biāo)規(guī)劃模型： 將優(yōu)先等級Pk視為正常數(shù)正負(fù)偏差變量dk+、dk-視為松弛變量以負(fù)偏差變量dk-為初始基變量，建立初始單純形表檢驗數(shù)的計算與LP單純形表檢驗數(shù)的計算完全相同，即j= cj - CBi Pj 最優(yōu)性判別準(zhǔn)則類似于LP的單純形算法：檢驗數(shù)一般是各優(yōu)先等級因子的代數(shù)和判斷檢驗數(shù)的正負(fù)和大小 2022/9/2422第22頁，共29頁，2022年，5月20日，9點12分，星期五3 用單純形法求解目標(biāo)規(guī)劃例5 (課本例2) 用單純形法求解下述目標(biāo)規(guī)劃問題解：劃為標(biāo)準(zhǔn)型2022/9/2423第23頁，共2

14、9頁，2022年，5月20日，9點12分，星期五3 用單純形法求解目標(biāo)規(guī)劃cj00-P100-P1-P20值CBXBbx1x2d1-d1+d2-d2+d3-d3+-P1d1-10101-10000100d2-4021001-10020-P2d3-1003200001-1100/3檢驗數(shù)jP1P2132-1-10 x110101-10000-0d2-2001-221-10010-P2d3-7002-33001-170/3檢驗數(shù)jP1P22-1-33-1-12022/9/2424第24頁，共29頁，2022年，5月20日，9點12分，星期五3 用單純形法求解目標(biāo)規(guī)劃cj00-P100-P1-P20

15、值CBXBbx1x2d1-d1+d2-d2+d3-d3+0 x12011/2001/2-1/200400d1+1001/2-111/2-1/20020-P2d3-4001/200-3/23/21-180檢驗數(shù)jP1P21/2-11-3/2-13/2-10 x110101-100000 x22001-221-100-P2d3-30001-1-221-1檢驗數(shù)jP1P2-11-1-2-12-12022/9/2425第25頁，共29頁，2022年，5月20日，9點12分，星期五5 目標(biāo)規(guī)劃應(yīng)用舉例例6 已知一個生產(chǎn)計劃的線性規(guī)劃模型如下，其中目標(biāo)函數(shù)為總利潤，x1,x2 為產(chǎn)品A、B產(chǎn)量?，F(xiàn)有下列目標(biāo)：1. 要求總利潤必須超過 2500 元；2. 考慮產(chǎn)品受市場影響，為避免積壓，A、B的生產(chǎn)量不超過 60 件和 100 件；3. 由于甲資源供應(yīng)比較緊張，不要超過現(xiàn)有量140。試建立目標(biāo)規(guī)劃模型，并用圖解法求解。2022/9/2426第26頁，共29頁，2022年，5月20日，9點12分，星期五5 目標(biāo)規(guī)劃應(yīng)用舉例解：以產(chǎn)品 A,B 的單件利潤比 2.5 :1 為權(quán)系數(shù)，模型如下：2022/9