運籌學(xué)第四章目標(biāo)規(guī)劃

管理運籌學(xué)目標(biāo)規(guī)劃運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第1頁!第四章目標(biāo)規(guī)劃

目標(biāo)規(guī)劃（GoodProgramming，簡記為GP）是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟管理中多目標(biāo)決策的需要而逐步發(fā)展起來的一個運籌學(xué)分支，是實行目標(biāo)管理這種現(xiàn)代化管理技術(shù)的一個有效工具。運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第2頁!例4.1某工廠生產(chǎn)兩種產(chǎn)品，受到原材料供應(yīng)和設(shè)備工時的限制.在單件利潤等有關(guān)數(shù)據(jù)已知的條件下，要求制訂一個獲利最大的生產(chǎn)計劃，具體數(shù)據(jù)見下表。一、問題的提出表4-1

產(chǎn)品ⅠⅡ限量原材料(kg/件) 51060設(shè)備工時(h/件) 4440利潤(元/件)684.1目標(biāo)規(guī)劃的數(shù)學(xué)模型運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第3頁!設(shè)產(chǎn)品Ⅰ、Ⅱ的產(chǎn)量分別為從線性規(guī)劃的角度來看，問題似乎已經(jīng)得到圓滿的解，但實際上工廠作決策時可能還需根據(jù)市場和工廠實際情況，考慮其它問題，如：（1）由于產(chǎn)品Ⅱ銷售疲軟，故希望產(chǎn)品Ⅱ的產(chǎn)量不超過產(chǎn)品Ⅰ的一半；（2）原材料嚴(yán)重短缺，生產(chǎn)中應(yīng)避免過量消耗；（3）最好能節(jié)約4小時設(shè)備工時；（4）計劃利潤不少于48元.這時，問題變成一個多目標(biāo)問題，線性規(guī)劃方法就很難處理。St.件，解之得最優(yōu)生產(chǎn)計劃為，建立線性規(guī)劃模型件，利潤為元。運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第4頁!二、目標(biāo)規(guī)劃的基本概念1、目標(biāo)值和偏差變量目標(biāo)規(guī)劃通過引入目標(biāo)值和正、負偏差變量，可以將目標(biāo)函數(shù)轉(zhuǎn)化為目標(biāo)約束。因為在一次決策中，決策值不可能既超過目標(biāo)值，同時又未達到目標(biāo)值，所以有。即中有一個為0。目標(biāo)值是目標(biāo)的期望值（預(yù)先給定）；決策值是目標(biāo)函數(shù)在決策變量確定后的函數(shù)值；偏差變量用于表達二者之間的差異。正偏差變量表示決策值超過目標(biāo)值的數(shù)量，記為；負偏差變量表示決策值未達到目標(biāo)值的數(shù)量，記為。顯然有。運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第5頁!2、目標(biāo)約束和絕對約束目標(biāo)約束（軟約束）是指在目標(biāo)規(guī)劃問題中目標(biāo)值允許發(fā)生正、負偏差，在這些約束中加入正、負偏差變量的約束。絕對約束（硬約束）是指必須嚴(yán)格滿足的等式約束和不等式約束。線性規(guī)劃問題的目標(biāo)函數(shù)在給定目標(biāo)值和加入正、負偏差變量后，可變換為目標(biāo)約束，也可根據(jù)問題的需要將絕對約束變換為目標(biāo)約束。運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第6頁!4、目標(biāo)規(guī)劃的目標(biāo)函數(shù)目標(biāo)規(guī)劃的目標(biāo)函數(shù)（又稱準(zhǔn)則函數(shù)或達成函數(shù)），是由各目標(biāo)約束的偏差變量及相應(yīng)的優(yōu)先因子和權(quán)系數(shù)構(gòu)成，由于目標(biāo)規(guī)劃追求的是盡可能接近各既定目標(biāo)值，也就是各有關(guān)偏差變量盡可能小，所以，其目標(biāo)函數(shù)一定是極小化的。（1）要求恰好達到目標(biāo)值（目標(biāo)：正負偏差為0）最好等于：應(yīng)用時，有三種基本表達式.（2）要求不超過目標(biāo)值（目標(biāo)：正偏差為0）最好不大于：（3）要求不低于目標(biāo)值（目標(biāo)：負偏差為0）最好不小于：運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第7頁!實際問題決策經(jīng)常面臨的問題（多目標(biāo)決策問題）：方案優(yōu)劣并不以單一準(zhǔn)則為目標(biāo)，而是以多重準(zhǔn)則為目標(biāo)。約束條件并不完全符合嚴(yán)格的剛性條件，具有一定的彈性?？赡艿膹椥约s束：

最好等于最好不大于最好不小于三、目標(biāo)規(guī)劃的數(shù)學(xué)模型運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第8頁!彈性約束的一般處理方法實際量＋d－－d+=目標(biāo)值負偏差變量正偏差變量最好等于：最好不大于：最好不小于：d－d＋實際值目標(biāo)值實際值運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第9頁!數(shù)學(xué)模型－顧客訪問策略設(shè)、分別為訪問老顧客、新顧客的數(shù)量；（i＝1,2,3,4,5）為按優(yōu)先級排列的管理目標(biāo)（優(yōu)先因子）。建立目標(biāo)規(guī)劃模型如下：訪問時間最好不超過680小時；訪問時間最好不少于600小時；銷售收入盡量不少于70,000；訪問老顧客數(shù)最好不少于200個；訪問新顧客數(shù)最好不少于120個。運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第10頁!目標(biāo)規(guī)劃解的幾何分析X100300200600500400X21002003004005001(1)(2)(3)(4)(5)P1,P2,P3,P4級目標(biāo)均能夠?qū)崿F(xiàn)，但這些目標(biāo)實現(xiàn)后，P5級目標(biāo)無法實現(xiàn)。運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第11頁!級目標(biāo)X100300200600500400X21002003004005001(1)1.訪問時間最好不超過680小時；2.訪問時間最好不少于600小時；3.銷售收入盡量不少于70,000；4.訪問老顧客數(shù)最好不少于200個；5.訪問新顧客數(shù)最好不少于120個。運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第12頁!第三級目標(biāo)X100300200600500400X21002003004005001(1)(2)(3)1.訪問時間最好不超過680小時；2.訪問時間最好不少于600小時；3.銷售收入盡量不少于70,000；4.訪問老顧客數(shù)最好不少于200個；5.訪問新顧客數(shù)最好不少于120個。運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第13頁!X100300200600500400X21002003004005001(1)(2)(3)(4)(5)第五級目標(biāo)（無法實現(xiàn)）1.訪問時間最好不超過680小時；2.訪問時間最好不少于600小時；3.銷售收入盡量不少于70,000；4.訪問老顧客數(shù)最好不少于200個；5.訪問新顧客數(shù)最好不少于120個。運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第14頁!目標(biāo)規(guī)劃單純形法的特點目標(biāo)函數(shù)中只有偏差變量，且求它們的和最小。目標(biāo)函數(shù)中“價值系數(shù)”一般為優(yōu)先級的權(quán)重，因此檢驗數(shù)不是一行，而是m行。在m行檢驗數(shù)中，從上到下，按優(yōu)先級從高到低的順序排列。求解時，首先滿足優(yōu)先級高的變量。運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第15頁!單純形表運算P1行中的檢驗數(shù)不小于0目標(biāo)實現(xiàn)。P2行中的檢驗數(shù)小的對應(yīng)的進基，離基，繼續(xù)計算。d5+d2-運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第16頁!單純形表運算P1、P2行中的檢驗數(shù)不小于0目標(biāo)實現(xiàn)。P3行中的檢驗數(shù)小的對應(yīng)的進基，離基，繼續(xù)計算.d4-d5-運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第17頁!運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第18頁!目標(biāo)規(guī)劃問題的解決思路目標(biāo)規(guī)劃：常用以解決多目標(biāo)決策問題，其目標(biāo)函數(shù)主要是追求偏離目標(biāo)量的最小化。偏離目標(biāo)量一般以偏離變量表示。這些目標(biāo)分主次或輕重緩急，以限制式的方式進行說明，一般采用目標(biāo)依據(jù)級別賦予表示優(yōu)先級的權(quán)重值（優(yōu)先權(quán)因子)來表示。采用目標(biāo)規(guī)劃技術(shù)時，必須了解如何訂定目標(biāo)的優(yōu)先次序與權(quán)數(shù)。有時候可考慮將權(quán)數(shù)與優(yōu)先次序合并使用。運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第19頁!目標(biāo)值實際值d＋d－有：目標(biāo)值＝實際值－d+（此時d－＝0）1.當(dāng)實際值>目標(biāo)值時d－＝02.當(dāng)實際值<目標(biāo)值時d+＝0有：目標(biāo)值＝實際值＋d－（此時d＋＝0）故有：目標(biāo)值＝實際值＋d－－d＋實際值目標(biāo)值運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第20頁!區(qū)別具有相同優(yōu)先因子的兩個目標(biāo)的差別，這時可分別賦予它們不同的權(quán)系數(shù)wj。在實際問題中，決策者要求達到這些目標(biāo)時，是有主次或輕重緩急的不同，凡要求位達到的目標(biāo)賦予優(yōu)先因子P1，次位的目標(biāo)賦予優(yōu)先因子P2，…，并規(guī)定：Pk>>Pk+1

表示Pk

比Pk+1有更大的優(yōu)先權(quán)，即首先保證級P1目標(biāo)的實現(xiàn)，這時可不考慮次級目標(biāo)；而P2級目標(biāo)是在實現(xiàn)P1級目標(biāo)的基礎(chǔ)上考慮的，以此類推。3、優(yōu)先因子（優(yōu)先等級）與權(quán)系數(shù)運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第21頁!目標(biāo)規(guī)劃問題的求解是分級進行的，首先求滿足P1級目標(biāo)的解，然后在保證級目標(biāo)不被破壞的前提下再求滿足P2級目標(biāo)的解，以此類推?？傊?，是在不破壞上一級目標(biāo)的前提下，實現(xiàn)下一級目標(biāo)的最優(yōu)。因此，這樣最后求出的解就不是通常意義下的最優(yōu)解，稱之為滿意解。之所以叫滿意解，是因為對于這種解來說，前面的目標(biāo)是可以保證實現(xiàn)或部分實現(xiàn)的，后面的目標(biāo)就不一定能保證實現(xiàn)或部分實現(xiàn)，有些可能就不能實現(xiàn)。5、滿意解運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第22頁!目標(biāo)值實際值d＋d－有：目標(biāo)值＝實際值－d+（此時d－＝0）1.當(dāng)實際值>目標(biāo)值時d－＝02.當(dāng)實際值<目標(biāo)值時d+＝0有：目標(biāo)值＝實際值＋d－（此時d＋＝0）故有：目標(biāo)值＝實際值＋d－－d＋實際值目標(biāo)值運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第23頁!問題：商家對顧客訪問及銷售策略目標(biāo)：訪問時間最好不超過680小時；訪問時間最好不少于600小時；銷售收入盡量不少于70,000；訪問老顧客數(shù)最好不少于200個；訪問新顧客數(shù)最好不少于120個。運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第24頁!4.2目標(biāo)規(guī)劃的圖解法圖解法只適用于兩個決策變量的目標(biāo)規(guī)劃問題用圖解法解目標(biāo)規(guī)劃時，先在由決策變量x1，x2構(gòu)成的平面直角坐標(biāo)系的象限內(nèi)作各約束條件。絕對約束條件的作圖與線性規(guī)劃相同，作目標(biāo)約束時，先令d＋、

d－=0，作相應(yīng)的直線，然后在這直線旁標(biāo)上d＋，

d－增大的方向，在此基礎(chǔ)上再按照優(yōu)先級從高到低的順序，逐個地考慮各個目標(biāo)約束。運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第25頁!目標(biāo)規(guī)劃的求解---序貫算法4.3目標(biāo)規(guī)劃的單純形法1.訪問時間最好不超過680小時；2.訪問時間最好不少于600小時；3.銷售收入盡量不少于70,000；4.訪問老顧客數(shù)最好不少于200個；5.訪問新顧客數(shù)最好不少于120個。運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第26頁!第二級目標(biāo)X100300200600500400X21002003004005001(1)(2)1.訪問時間最好不超過680小時；2.訪問時間最好不少于600小時；3.銷售收入盡量不少于70,000；4.訪問老顧客數(shù)最好不少于200個；5.訪問新顧客數(shù)最好不少于120個。運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第27頁!X100300200600500400X21002003004005001(1)(2)(3)(4)第四級目標(biāo)1.訪問時間最好不超過680小時；2.訪問時間最好不少于600小時；3.銷售收入盡量不少于70,000；4.訪問老顧客數(shù)最好不少于200個；5.訪問新顧客數(shù)最好不少于120個。運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第28頁!目標(biāo)規(guī)劃的求解---多階段算法1.訪問時間最好不超過680小時；2.訪問時間最好不少于600小時；3.銷售收入盡量不少于70,000；4.訪問老顧客數(shù)最好不少于200個；5.訪問新顧客數(shù)最好不少于120個。運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第29頁!初始單純形表P1行中的檢驗數(shù)不小于0目標(biāo)實現(xiàn)。P2行中的檢驗數(shù)小的對應(yīng)的X2進基，離基，繼續(xù)計算。d5-運籌學(xué)第四章目標(biāo)規(guī)劃共33頁，您現(xiàn)在瀏覽的是第30頁