【正文】 意義 ?目標(biāo)規(guī)劃的單純形方法 問題的提出 ? 線性規(guī)劃的局限性 ? 線性規(guī)劃只研究在滿足一定條件下 ， 單一目標(biāo)函數(shù)取得最優(yōu)解 ， 而在企業(yè)管理中 ， 經(jīng)常遇到多目標(biāo)決策問題 ， 如擬訂生產(chǎn)計劃時 ， 不僅考慮總產(chǎn)值 ， 同時要考慮利潤 ， 產(chǎn)品質(zhì)量和設(shè)備利用率等 。 ? 線性規(guī)劃求最優(yōu)解；目標(biāo)規(guī)劃是找到一個滿意解 。 10 二、多目標(biāo)規(guī)劃的提出 11 12 13 14 上述 15 16 17 18 19 20 21 22 第一節(jié) 多目標(biāo)規(guī)劃問題 三、多目標(biāo)的處理方法 ? 加權(quán)系數(shù)法： ? 為每一目標(biāo)賦一權(quán)數(shù) ， 把多目標(biāo)轉(zhuǎn)化成單目標(biāo) 。 一 、 目標(biāo)值和偏差變量 目標(biāo)規(guī)劃通過引入目標(biāo)值和偏差變量 ， 可以將目標(biāo)函數(shù)轉(zhuǎn)化為目標(biāo)約束 。 目標(biāo)規(guī)劃的數(shù)學(xué)模型 在一次決策中 ， 實現(xiàn)值不可能既超過目標(biāo)值又未達(dá)到目標(biāo)值 ， 故有 d＋ d－ ＝ 0,并規(guī)定 d＋ ≥0, d－ ≥0 當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示： d＋ ≥0, d－ ＝ 0 當(dāng)未完成規(guī)定的指標(biāo)則表示： d＋ ＝ 0, d－ ≥0 當(dāng)恰好完成指標(biāo)時則表示： d＋ ＝ 0, d－ ＝ 0 目標(biāo)規(guī)劃的數(shù)學(xué)模型 二 .目標(biāo)約束和絕對約束 引入了目標(biāo)值和正 、 負(fù)偏差變量后 ， 就對某一問題有了新的限制 ， 既目標(biāo)約束 。 ? 又增加二個目標(biāo)： maxZ1=3x1+5x2 maxZ2=x1 minZ3=x2 2x1 ≤16 2x2 ≤10 3x1+4x2 ≤32 x1， x2 ≥0 30 第二節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型 要求： ? 目標(biāo)一是利潤最大 ， 擬定利潤目標(biāo)是 30； ? 目標(biāo)二是減少乙產(chǎn)品產(chǎn)量但希望不低于 4件； ? 目標(biāo)三是甲產(chǎn)品產(chǎn)量希望不少于 6件 ； ? 對各目標(biāo)引入正 、 負(fù)偏差變量： 3x1+5x2 +d1 d1+ = 30 x2 +d2 d2+ =4 x1 +d3– d3+ = 6 目標(biāo)規(guī)劃的數(shù)學(xué)模型 三 .優(yōu)先因子 (優(yōu)先等級 )與優(yōu)先權(quán)系數(shù) 目標(biāo)等級化 :將目標(biāo)按重要性程度不同依次分成一級目標(biāo) 、 二級目標(biāo) … ..。 因此 ， 同一級別的目標(biāo)的其中一個的損失 ， 可有其余目標(biāo)的適當(dāng)收獲來彌補(bǔ) 。因此目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能是 minZ = f(d＋ 、 d－ )。 (4)前面的目標(biāo)可以保證實現(xiàn)或部分實現(xiàn) ， 而后面的目標(biāo)就不一定能保證實現(xiàn)或部分實現(xiàn) ， 有些可能就不能實現(xiàn) ， 就稱該解為多目標(biāo)規(guī)劃的 滿意解 (具有層次意義的解 ) 單目標(biāo)規(guī)劃 例 52:某工廠生產(chǎn) A， B兩種產(chǎn)品 ， 有關(guān)數(shù)據(jù)如下 。 這時只需要給絕對約束加上負(fù)偏差變量和減去正偏差變量即可 。 78 第四節(jié) 目標(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單純形法相同，即 ?j= cj CBi Pj ? 最優(yōu)性判別準(zhǔn)則類似于 LP的單純形算法： ? 檢驗數(shù)一般是各優(yōu)先等級因子的代數(shù)和 ? 判斷檢驗數(shù)的正負(fù)和大小 目標(biāo)規(guī)劃的單純形法 目標(biāo)規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)形式上沒有本質(zhì)的區(qū)別 ， 所以可用單純形法求解 。 105 2 A 2 4 B D x2 6 8 10 x1 第五節(jié) 目標(biāo)規(guī)劃的應(yīng)用案例 一、無窮多滿意解 由于材料供應(yīng)限量為 8單位，所以有系統(tǒng)約束條件，如下 82 21 ?? xx該問題的目標(biāo)規(guī)劃模型如下，圖解法求解如圖 1 1 1 2 21 2 1 11 2 2 2121 2 1 1 2 2m in ( )10 12 66 ( 1 )( 2)10 20 100 .( 3 )28, 0 , , , , 0G P d d P dx x d dx x d dxxx x d d d d ? ?? ? ?? ? ?? ? ? ??? ? ??????? ???C G 1d1?2d?106 第五節(jié) 目標(biāo)規(guī)劃的應(yīng)用案例 二、加班時間問題 例： 某音像店有 5名全職售貨員和 4名兼職售貨員，全職售貨員每月工作 160小時，兼職售貨員每月工作 80小時。 其次，建立目標(biāo)約束函數(shù) （ 1） 銷售目標(biāo)約束 ，設(shè)全體全職售貨員下月的工作時間 x1，全體兼職售貨員下月的工作時間 x2；達(dá)不到銷售目標(biāo)的偏差 d1，超過銷售目標(biāo)的偏差 d1+。 問應(yīng)如何制定產(chǎn)品甲、乙的產(chǎn)量，試建立其目標(biāo)規(guī)劃的數(shù)學(xué)模型。 1月 y1 ≤2 2月 y2 ≤2 – y1 + x1 → y1 + y2 – x1 ≤2 3月 y3 ≤2 – y1 + x1 – y2 + x2 → y1+y2+ y3 – x1 – x2 ≤2 4月 y4≤2 – y1 +x1 –y2+x2–y3+x3→ y1+y2+y3+y4 – x1 –x2–x3≤2 ?各月采購量約束 :每月采購量依賴月初的售貨收入。 總利潤： 40 單位甲： 單位乙： 生產(chǎn)部目標(biāo) 甲產(chǎn)品的產(chǎn)量： 6， 成本： 乙產(chǎn)品的產(chǎn)量： 2， 成本： 技術(shù)部目標(biāo) 甲產(chǎn)品的設(shè)備單耗： 20 乙產(chǎn)品的設(shè)備單耗： 10 銷售部目標(biāo) 甲產(chǎn)品的銷量： 6， 單價： 10 乙產(chǎn)品的銷量： 2， 單價： 8 第五節(jié) 目標(biāo)規(guī)劃的應(yīng)用 例： 某副食品批發(fā)店預(yù)測某商品今后 4月的購進(jìn)與售出價格如表 。 設(shè)全體全職售貨員下月的加班不足 100小時的偏差 d4，加班超過 100小時的偏差 d4+ 。每出售一張 CD盈利 。 若 α1j=0， 這時此檢驗數(shù)的正 、 負(fù)就決定于 P2的系數(shù) α2j的正 、 負(fù) 。按優(yōu)先級別和權(quán)重依次分析各級目標(biāo)。 第一目標(biāo)： P1(d1＋ +d1) 第二目標(biāo)： P2d2＋ 第二目標(biāo)： P3d3 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0 , , , 48 4 2 130 6 8 4 60 2 4 ) ( 2 1 2 1 3 3 2 1 2 2 2 1 1 2 1 3 3 2 2 1 1 1 i i d d x x x x d d x x d d x d d x x st d P d P d d P MinZ 具有優(yōu)先級別的多目標(biāo)規(guī)劃 例 55：某廠計劃下一個生產(chǎn)周期內(nèi)生產(chǎn)甲 、 乙兩種產(chǎn)品 ，已知資料如表所示 。 對由絕對約束轉(zhuǎn)化而來的目標(biāo)函數(shù) ， 也照上述處理即可 。 即首先保證 P1級目標(biāo)的實現(xiàn) ， 這時可不考慮次級目標(biāo)；而 P2級目標(biāo)是在實現(xiàn) P1級目標(biāo)的基礎(chǔ)上考慮的；依此類推 。 即較高級別的目標(biāo)沒有達(dá)到的損失 ， 任何較低級別目標(biāo)上的收獲不可彌補(bǔ) 。 如線性規(guī)劃中的所有約束條件都是絕對約束 ， 否則無可行解 。 偏差變量 (事先無法確定的未知數(shù) )：是指實現(xiàn)值和目標(biāo)值之間的差異 ,記為 d 。 ? 但可行域大時難以列出所有有效解的組合 。 試制定生產(chǎn)計劃 ， 使獲得的利潤最大 ？ 同時 ， 根據(jù)市場預(yù)測 ， 甲的銷路不是太好 ， 應(yīng)盡可能少生產(chǎn)；乙的銷路較好 ， 可以擴(kuò)大生產(chǎn) 。 ? 線性規(guī)劃把各個約束條件的重要性都不分主次地等同看待 ，這也不符合實際情況 。 ? 求解線性規(guī)劃問題 ， 首先要求約束條件必須相容 ， 如果約束條件中 ， 由于人力 ， 設(shè)備等資源條件的限制 ， 使約束條件之間出現(xiàn)了矛盾 ， 就得不到問題的可行解 ， 但生產(chǎn)還得繼續(xù)進(jìn)行 ， 這將給人們進(jìn)一步應(yīng)用線性規(guī)劃方法帶來困難 。 試建立此問題的數(shù)學(xué)模型 。 ? 目標(biāo)規(guī)劃法： ? 對每一個目標(biāo)函數(shù)引入正的或負(fù)的偏差變量； ? 引入目標(biāo)的優(yōu)先等級和加權(quán)系數(shù) 。 偏差可能存在正的或負(fù)的 。 所以 ， 絕對約束是硬約束 。 故在判斷最優(yōu)方案時 ， 首先從較高級別的目標(biāo)達(dá)到的程度來決策 ， 然后再其次級目標(biāo)的判斷 。 若要區(qū)別具有相同優(yōu)先因子的兩個目標(biāo)的差別 ， 這時可分別賦予它們不同的權(quán)系數(shù) ωj,這些都由決策者按具體情況而定 。 34 例： 甲乙產(chǎn)品的最優(yōu)生產(chǎn)計劃。 制定生產(chǎn)計劃 ， 滿足下列目標(biāo)： P1級目標(biāo)：完成或超額完成利潤指標(biāo) 50000元； P2級目標(biāo)：產(chǎn)品甲不超過 200件 ， 產(chǎn)品乙不低于 250件； P3級目標(biāo)：現(xiàn)有鋼材 3600噸必須用完 120 70 單件利潤 3000 10 3 設(shè)備臺時 2023 5 4 煤炭 3600 4 9 鋼材 資源限制 乙 甲 單位 產(chǎn)品 資源 消耗 具有優(yōu)先級別的多目標(biāo)規(guī)劃 分析：題目有三個目標(biāo)層次 ， 包含四個目標(biāo)值 。 1 1 2 2 31 2 1 12 2 21 3 3121212m in ( 2 )3 5 30 ( 1 )4 ( 2)( 3 )6( 4)2 16 .( 5 )2 10( 6)3 4 32( 7 ),0, 0( 1 , 2 , 3 )llG P d P d dx x d dx d dx d dxxxxxxd d l ????? ? ?? ? ? ??? ???? ?