第四章目標(biāo)規(guī)劃(運(yùn)籌學(xué)-重慶大學(xué),熊中楷)ppt課件

1、運(yùn)籌學(xué)目的規(guī)劃1復(fù)習(xí)上節(jié)課內(nèi)容：產(chǎn)銷不平衡運(yùn)輸問題上節(jié)課難點(diǎn)：產(chǎn)銷不平衡運(yùn)輸問題建立模型，造假本節(jié)課內(nèi)容：目的規(guī)劃和圖解法本節(jié)課難點(diǎn)三個(gè)難點(diǎn)1.建立模型中：目的函數(shù)偏向是正或者負(fù)難點(diǎn)2.圖解法中：方向偏向是正或者負(fù) 難點(diǎn)3.圖解法中：判別解第四章：目的規(guī)劃1第四章：目的規(guī)劃1Chapter 4: objective programming(1)example and model of objective programminggraphic method of objective programming第四章：目的規(guī)劃13目的規(guī)劃1 目的規(guī)劃的引例與模型，圖解法目的規(guī)劃2目的規(guī)劃的單純形法，靈

2、敏度分 析目的規(guī)劃3目的規(guī)劃的運(yùn)用線性規(guī)劃-單目的決策： 利潤最大或 本錢最小第四章：目的規(guī)劃及其圖解法1現(xiàn)實(shí)上，企業(yè)面臨的多目的決策 我們?nèi)松媾R的多目的決策一個(gè)國有企業(yè)面臨的多目的決策 1 穩(wěn)定目的完不成第1把手下崗 今年下崗不超越現(xiàn)有人數(shù)的 1 員工參與法能功上北京人數(shù)=253萬3 新產(chǎn)品開發(fā)義務(wù)=2項(xiàng)第四章：目的規(guī)劃及其圖解法1目的函數(shù)：Min多個(gè)目的的正負(fù)偏向 約束條件： 第一目的穩(wěn)定正負(fù)偏向下崗2 第二目的利潤正負(fù)偏向5000萬 第三目的本錢正負(fù)偏向3000萬 第四目的新產(chǎn)品開發(fā)費(fèi)用正負(fù)偏向250萬第四章：目的規(guī)劃及其圖解法1產(chǎn)品A 產(chǎn)品B擁有量原資料公斤2111設(shè)備小時(shí)1212利

3、潤萬元/件810書上引例： 某工廠消費(fèi)A、B兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下, 用線性規(guī)劃求解： 第四章：目的規(guī)劃及其圖解法1求利潤最大的決策是 產(chǎn)品A消費(fèi)4 產(chǎn)品B消費(fèi)3利用線性規(guī)劃求出 ：總利潤為62萬元 這時(shí)原資料用完 設(shè)備剩余2小時(shí)實(shí)踐中，決策時(shí)不只思索利潤最大，還要思索市場等一系列條件，例如 1) 根據(jù)市場信息，產(chǎn)品A的需求有下降的趨勢，因此思索產(chǎn)品A的 產(chǎn)量不大于產(chǎn)品B的產(chǎn)量 2 超越方案供應(yīng)的原資料時(shí)，需求用高價(jià)采購，使本錢添加 3 盡能夠利用設(shè)備，但不希望加班 4 盡能夠到達(dá)并且超越利潤目的56萬元 求：決策方案。 第四章：目的規(guī)劃及其圖解法1例1. 線性規(guī)劃模型 相關(guān)目的規(guī)劃模型 利潤

4、最大 Max Z= 8x1+10 x2 8x1+ 10 x2+ d1- -d1+ =56 決策目的不是利潤最大，而是有多個(gè)，重要性有先后之分： 假設(shè)：第一目的 利潤不小于56元 (利潤小于56-d1-0) 第二目的 充分利用臺時(shí)，不加班 第三目的 產(chǎn)品1產(chǎn)量不大于產(chǎn)品2產(chǎn)量 目的偏向最?。篗inP1 d1- + P2( d2- -d2+ ) + P3d3+ 第四章：目的規(guī)劃及其圖解法1原資料約束 2x1+ x2 =11 2x1+ x2 =11設(shè)備約束 x1+ 2x2 =0 x1 - x2 +d3_d3+ =0 xi =0, di- , d+I=0 難點(diǎn)1.建立模型中：目的函數(shù)偏向是正或者負(fù) 知

5、識要點(diǎn) 1概念1偏向變量：實(shí)踐值與目的值之間差距的變量表示，通常以di-、di+表示， 分別稱為正偏向變量、負(fù)偏向變量、且有di-0,di+0。2優(yōu)先級系數(shù)：又稱優(yōu)先級因子，描畫問題中目的重要性程度的 差別，普通用pi表示。通常，i值越小，代表的優(yōu)先程度越高。 3目的約束與系統(tǒng)約束：描畫問題中兩類不同性質(zhì)的限制條件。 普通目的約束用來描畫允許對給定目的值有一定偏離程度的限制條件。 而系統(tǒng)約束表示的意義同線性規(guī)劃模型的約束條件。 2模型特點(diǎn)1引進(jìn)正負(fù)偏向變量，對一切目的下的正負(fù)偏向變量，均有 di-di+=0；2模型中必順存在目的約束，而系統(tǒng)約束可以不存在；3目的函數(shù)為偏向變量表述式；4以優(yōu)先級

6、系數(shù)描畫目的的重要性程度。目的規(guī)劃問題的稱心解可 是一個(gè) 點(diǎn)， 一條線段或者為一個(gè)區(qū)域。第四章：目的規(guī)劃及其圖解法1d1-d1+X1-X2 +1=0X1X2d1- =1X1 - X2 =0第四章：目的規(guī)劃及其圖解法1難點(diǎn)2.圖解方法中：方向偏向是正或者負(fù)X1 - X2 =02X1-X2 +1=0判別d1-方向判別d1+方向d2+ =1X1+2X2 =10X1X2510X1+2X2 -1=10第四章：目的規(guī)劃及其圖解法1d2+d1-P104 例3 電視消費(fèi)第四章：目的規(guī)劃及其圖解法1Min z= MinP1 d1- + P2 d2+ + P3 ) (2d3- + d4- ) x1+ x2 + d

7、1- -d1+ = 40 x1 + x2 +d2_d2+ =50 x1 +d3_d3+ =24 x2 +d4_d4+ =30 xi =0, di- , d+I=0d3- 03024d4- ？d4+P104 例3 電視消費(fèi)d3d2+ 0d1- 0彩電X1X2黑白5004040第四章：目的規(guī)劃及其圖解法1難點(diǎn)3.圖解方法中：判別解MinP1 d1- + P2 d2+ + P3 ) (2d3- + d4- )d3- 0彩電X1X2黑白3024D4 - ？d4+P104 例3 優(yōu)先權(quán)改動 改為黑白優(yōu)先D3d2+ 0d1- 0第四章：目的規(guī)劃及其圖解法1MinP1 d1- + P2 d2+ + P3 d

8、4- + P4 d3- 靈敏度分析 目的規(guī)劃問題的靈敏度分析，普通只對約束右端項(xiàng)的 變化以及優(yōu)先級系數(shù)的變化進(jìn)展?！纠?】判別下述說法能否正確? (a)線性規(guī)劃模型是目的規(guī)劃模型的一種特殊方式; (b)正偏向變量應(yīng)取正值、負(fù)偏向變量應(yīng)取負(fù)值； (c)目的規(guī)劃模型中，假設(shè)不含系統(tǒng)約束，那么一定有解； (d)目的規(guī)劃的數(shù)學(xué)模型應(yīng)同時(shí)包括系統(tǒng)約束和目的約束。答：a正確。模型構(gòu)造完全一致，可以將線性規(guī)劃模型改寫成單 一目的方式的目的規(guī)劃。 b錯誤。正負(fù)變量都定義取非負(fù)的值。 (c)正確。目的規(guī)劃的解是一種相對稱心的解。 (d)錯誤。可以沒有系統(tǒng)的束。 第四章：目的規(guī)劃及其圖解法1目的規(guī)劃圖解法：例2

9、p103. 第四章：目的規(guī)劃及其圖解法1第2目的約束 MinP2( d2- -d2+ ) d2- =0，d2+ =0第1目的約束 MinP1 d1+ d1+ = 0第3目的約束 MinP3 d3- d3- = 0d1+ = 0例3.p104 不能取0稱心解優(yōu)先彩電黑白黑白彩電彩電稱心解優(yōu)先黑白第四章：目的規(guī)劃及其圖解法1總結(jié)本節(jié)課：目的規(guī)劃難點(diǎn)三個(gè)難點(diǎn)1.建立模型中：目的函數(shù)偏向是正或者負(fù)難點(diǎn)2.圖解方法中：方向偏向是正或者負(fù) 難點(diǎn)3.圖解方法中：判別解第四章：目的規(guī)劃及其圖解法1運(yùn)籌學(xué)目的規(guī)劃2本節(jié)課義務(wù)：目的規(guī)劃單純形法目的規(guī)劃靈敏度第四章：目的規(guī)劃單純形法和靈敏度2復(fù)習(xí)上節(jié)課內(nèi)容：目的規(guī)

10、劃和圖解法上節(jié)課難點(diǎn)三個(gè)難點(diǎn)1.建立模型中：目的函數(shù)偏向是正或者負(fù)難點(diǎn)2.圖解法中：方向偏向是正或者負(fù) 難點(diǎn)3.圖解法中：判別解本節(jié)課要點(diǎn)三個(gè) 要點(diǎn)1 初試單純形表要點(diǎn)2 檢驗(yàn)數(shù)的計(jì)算要點(diǎn)3 檢驗(yàn)數(shù)正負(fù)的判別P103 例 2 目的規(guī)劃單純形法第四章：目的規(guī)劃單純形法和靈敏度2原資料嚴(yán)厲限制目的1：產(chǎn)品2產(chǎn)量不低于產(chǎn)品1的產(chǎn)量目的2：充分利用設(shè)備臺時(shí)，不加班目的3：利潤不小于56萬元求決策方案Min z=p1d1+p2(d2-+d2+)+ p3d3- 2x1+ x2+ Xs =11 x1 x2 + d1- -d1+ = 0 x1 + 2x2 +d2_d2+ =10 8x1 + 10 x2 +d3

11、_d3+ =56 xi =0, di- , d+I=0P106 例 目的規(guī)劃單純形法第四章：目的規(guī)劃單純形法和靈敏度2要點(diǎn)1 初試單純形表:有一個(gè)單位矩陣 檢驗(yàn)數(shù)第四章：目的規(guī)劃單純形法和靈敏度2解目的規(guī)劃的單純形法(P106)0000P1P2P2P30CBXB X1X2Xsd1-d1+d2-d2+d3-d3+B-1 b0XS2111111/10d1-1-11 -10P2d2-1轉(zhuǎn)21 -11010/2P3d3-8101 - 15656/10檢驗(yàn)數(shù)P11P2122P38101根據(jù)目的函數(shù)C2 - CB B-1 P2 = 0 0 0 P2 P3 (1 1 2 10 )T = - 2P2 - 10

12、P3 單純形法：降本錢，負(fù)中取小相除后正中取小B-1 =I直接找到單位矩陣轉(zhuǎn)元所在列化為單位向量第四章：目的規(guī)劃單純形法和靈敏度20000P1P2P2P30CBXB X1X2Xsd1-d1+d2-d2+d3-d3+B-1 b0XS0d1-0X21/211/2-1/255/1.5P3d3-檢驗(yàn)數(shù)P11P2122P38101把這一行一切數(shù)乘以2P2+10P3加到檢驗(yàn)數(shù)這一行：- P2 - 8P3+ (1/2) 2P2+10P3= - 3P3轉(zhuǎn)元所在列化為單位向量要點(diǎn)2 檢驗(yàn)數(shù)的計(jì)算第四章：目的規(guī)劃單純形法和靈敏度20000P1P2P2P30CBXB X1X2Xsd1-d1+d2-d2+d3-d3+

13、B-1 b0XS0d1-0X21/211/2-1/255/1.5P3d3-檢驗(yàn)數(shù)P1P2P3-3 把這一行一切數(shù)乘以2P2+10P3加到檢驗(yàn)數(shù)這一行：- P2 - 8P3+ (1/2) 2P2+10P3= - 3P3第四章：目的規(guī)劃單純形法和靈敏度2解目的規(guī)劃的單純形法 (P105)0000P1P2P2P30CBXBX1X2Xsd1-d1+d2-d2+d3-d3+B-1 b0XS3/21-1/21/266/1.50d1-3/21 -11/2-1/250X21/211/2-1/255/1.5P3d3-轉(zhuǎn)3-551 - 166/3檢驗(yàn)數(shù)P11P211P335 51C7 CB B-1 P7 = P2

14、 0 0 0 P3 (1/2 1/2 1/2 5 )T = P2 5P3單純形法：降本錢，負(fù)中取小 ( 注：d2+ 的檢驗(yàn)數(shù)為正 )相除后正中取小CB轉(zhuǎn)元所在列化為單位向量解目的規(guī)劃的單純形法 (P107)0000P1P2P2P30CBXBX1X2Xsd1-d1+d2-d2+d3-d3+B-1 b0Xs12-2-1/21/230d1-1-13-3-1/21/220X214/3-4/3-1/61/64P3X11-5/35/31/3-1/32檢驗(yàn)數(shù)P11P211P310非基變量檢驗(yàn)數(shù)為零 對應(yīng)無數(shù)最優(yōu)解單純形法：最優(yōu)解： X1 2 ， X24， Xs 3，d1- 2第四章：目的規(guī)劃單純形法和靈敏度

15、2第四章：目的規(guī)劃單純形法和靈敏度2解目的規(guī)劃的單純形法 (P107)0000P1P2P2P30CBX1X2Xsd1-d1+d2-d2+d3-d3+B-1 b0Xs1-1-1110d3+1 26-6-1140X21-1/31/3-1/310/3P3X11-2/31/3-1/3 10/3檢驗(yàn)數(shù)P101P211P31單純形法：最優(yōu)解X1 10/3 ， X210/3，Xs 1，d3+ 4非基變量檢驗(yàn)數(shù)為零 對應(yīng)無數(shù)最優(yōu)解d1-d3+對換解目的規(guī)劃的單純形法(P105)最優(yōu)解特點(diǎn)一特點(diǎn)二檢驗(yàn)數(shù)包含第四章：目的規(guī)劃單純形法和靈敏度2?檢驗(yàn)數(shù) 2P2 -3 P3為正 檢驗(yàn)數(shù) -3P2 + 5 P3為負(fù)檢驗(yàn)

16、數(shù) P1 - 8P2 -9 P3為正要點(diǎn)3 檢驗(yàn)數(shù)正負(fù)的判別檢驗(yàn)數(shù)中優(yōu)先權(quán)大的系數(shù)符號為準(zhǔn) 檢驗(yàn)數(shù) -3P2 + 5 P3為負(fù) 檢驗(yàn)數(shù) 2P2 -3 P3為正 檢驗(yàn)數(shù) P1 - 8P2 -9 P3為正第四章：目的規(guī)劃單純形法和靈敏度2靈敏度分析-優(yōu)先級改動(107)：優(yōu)先彩電 優(yōu)先黑白第四章：目的規(guī)劃單純形法和靈敏度2優(yōu)先級改動 目的函數(shù)改動， C改動 CB改動， 單純形表中 檢驗(yàn)數(shù)CN CB B-1 N改動優(yōu)先級改動單純形表中 檢驗(yàn)數(shù)改動靈敏度分析-優(yōu)先級改動(107)：Min z=p1 (2d1-+3d1+) +p2 d3- + p3d4 優(yōu)先級改動為Min z=p1 d3- + p2 (

17、2d1+3d2+) + p3d4 x1+ x2+ d1- -d1+ =10 x1 + d2- -d2+ = 4 5x1 + 3x2 +d3_d3+ =56 x1 + x2 +d4_d4+ =12 xi =0, di- , d+I=0 系數(shù)矩陣中有一個(gè)矩陣單位優(yōu)先級改動 目的函數(shù)改動 C改動 CB改動， 單純形表中 檢驗(yàn)數(shù)CN CB B-1 N改動第四章：目的規(guī)劃單純形法和靈敏度2第四章：目的規(guī)劃單純形法和靈敏度20002P203P2P100P3CBX1X2d1-d1+d2-d2+d3-d3+d4-d4+0X2111-1160X110 1114P1d3-33-2211180d4-轉(zhuǎn)1 112檢驗(yàn)

18、數(shù)P11322P2231P31C4 CB B-1 P4 = 2P2 0 0 P1 0 (1 0 3 1 )T = 3P1 2P2單純形法：降本錢，負(fù)中取小 ( 注：d1+ 的檢驗(yàn)數(shù)負(fù))相除后正中取小轉(zhuǎn)元所在列化為單位向量0002P203P2P100P3CBX1X2d1-d1+d2-d2+d3-d3+d4-d4+0X211-5/35/31/3-1/3120X11 114P1d4+-2/32/31/3-1/3-140d1+-11-2/32/31/316檢驗(yàn)數(shù)P11P223P3 2/3-2/3-2/31/3單純形法：最優(yōu)解： X1 4 ， X212第四章：目的規(guī)劃單純形法和靈敏度2轉(zhuǎn)元所在列化為單位

19、向量總結(jié)本節(jié)課義務(wù)：目的規(guī)劃單純形法目的規(guī)劃靈敏度第四章：目的規(guī)劃單純形法和靈敏度2總結(jié)本節(jié)課要點(diǎn)三個(gè) 1 初試單純形表2 檢驗(yàn)數(shù)的計(jì)算3 檢驗(yàn)數(shù)正負(fù)的判別第四章：目的規(guī)劃運(yùn)用3目的規(guī)劃運(yùn)用舉例 (P109) 例6.調(diào)工資方案目的1 不超越年工資總額60000元2 每級人數(shù)不超越定編人數(shù)二三級晉級面盡能夠到達(dá)現(xiàn)有人數(shù)的204 三級缺乏人數(shù)可以錄取新工人，一級有10要退休年工資現(xiàn)有人數(shù)定編人數(shù)一級20001012二級15001215三級10001515合計(jì)3742第四章：目的規(guī)劃運(yùn)用3解：設(shè) X1，X2，X3表示提升到一二級和錄取到三級的新 工人人數(shù)第1目的：不超越年工資總額60000元 提問題

20、：同窗闡明下式 Min P1 d1 200010100.1+ X1 1500(12- X1 X2 ) 1000 (15- X2 X3 ) + d1- d1 60000d1- 缺乏工資總額的數(shù)量d1 超越工資總額的數(shù)量第四章：目的規(guī)劃運(yùn)用3第2目的：每級人數(shù)不超越定編人數(shù) 提問題：同窗闡明下式 Min P2 (d2 )+ (d3 )+(d4 )1010.1 X1 + d2- d2 1212 - X1 X2 + d3- d3 15- X2 X3 + d4- d4 15d2 一級超越定編人數(shù) 的數(shù)量D2- 一級缺乏定編人數(shù) 的數(shù)量第四章：目的規(guī)劃運(yùn)用3第3目的：二三級晉級面盡能夠到達(dá)現(xiàn)有人數(shù)的20提

21、問題：同窗闡明下式 Min P3 (d5 )+ (d6 ) X1 + d5- d5 120. 2 X2 + d6- d6 15 0. 2 d5- 二級晉級面缺乏規(guī)定的數(shù)量 d5 二級晉級面超越規(guī)定的數(shù)量答案 P110 留意偏向變量的經(jīng)濟(jì)含意例6.調(diào)工資方案討論：幾種了解知晉級面不超越20%晉級面不超越20%，盡能夠多提晉級面盡能夠正好20%第四章：目的規(guī)劃運(yùn)用31 B4 是重點(diǎn)保證單位，必需滿足全部需求2 A3向B1提供產(chǎn)量不少于1003 每個(gè)銷地的供應(yīng)量不少于需求的804 總運(yùn)費(fèi)不超越最小運(yùn)費(fèi)的1105 由于路問題，A2盡量不運(yùn)到B46 B1， B3的供應(yīng)率要一樣7 總運(yùn)輸費(fèi)用盡量少第四章：

22、目的規(guī)劃運(yùn)用3(p110例7) 目的規(guī)劃運(yùn)用案例 運(yùn)輸問題 一個(gè)物流企業(yè)的老板正在思索如下問題： 有三個(gè)產(chǎn)地A1,A2,A3給四個(gè)銷地B1,B2,B3,B4供應(yīng)某種產(chǎn)品，曾經(jīng)知道需求量和運(yùn)輸價(jià)錢， 要思索以下7個(gè)目的：銷地B1銷地B2銷地B3銷地B4產(chǎn) 量產(chǎn)地A15元/公斤 2元/公斤6元/公斤7元/公斤300產(chǎn)地A23元/公斤5元/公斤4元/公斤6元/公斤200產(chǎn)地A34元/公斤5元/公斤2元/公斤3元/公斤400銷 量200100450250第四章：目的規(guī)劃運(yùn)用3知銷地B1銷地B2銷地B3銷地B4產(chǎn) 量產(chǎn)地A1200100300產(chǎn)地A20200200產(chǎn)地A3虛產(chǎn)地400100銷 量200100450250第四章：目的規(guī)劃運(yùn)用3首先把 產(chǎn)銷不平衡化為產(chǎn)銷平衡， 求解如下：250150100 .目的規(guī)劃運(yùn)用 運(yùn)輸問題P110 例7 本例中 供需 供 + 虛產(chǎn)地 = 需 七個(gè)要求目的規(guī)劃表達(dá)如下：第1目的：B4是重點(diǎn)單位，必需滿足 提問題：同窗闡明下式第2目的：A3向B1提供產(chǎn)量不少于100 提問題：同窗