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

1、運籌學(xué)目的規(guī)劃1復(fù)習(xí)上節(jié)課內(nèi)容：產(chǎn)銷不平衡運輸問題上節(jié)課難點：產(chǎn)銷不平衡運輸問題建立模型，造假本節(jié)課內(nèi)容：目的規(guī)劃和圖解法本節(jié)課難點三個難點1.建立模型中：目的函數(shù)偏向是正或者負難點2.圖解法中：方向偏向是正或者負 難點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ī)劃的運用線性規(guī)劃-單目的決策： 利潤最大或 本錢最小第四章：目的規(guī)劃及其圖解法1現(xiàn)實上，企業(yè)面臨的多目的決策 我們?nèi)松媾R的多目的決策一個國有企業(yè)面臨的多目的決策 1 穩(wěn)定目的完不成第1把手下崗 今年下崗不超越現(xiàn)有人數(shù)的 1 員工參與法能功上北京人數(shù)=253萬3 新產(chǎn)品開發(fā)義務(wù)=2項第四章：目的規(guī)劃及其圖解法1目的函數(shù)：Min多個目的的正負偏向 約束條件： 第一目的穩(wěn)定正負偏向下崗2 第二目的利潤正負偏向5000萬 第三目的本錢正負偏向3000萬 第四目的新產(chǎn)品開發(fā)費用正負偏向250萬第四章：目的規(guī)劃及其圖解法1產(chǎn)品A 產(chǎn)品B擁有量原資料公斤2111設(shè)備小時1212利

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

4、最大 Max Z= 8x1+10 x2 8x1+ 10 x2+ d1- -d1+ =56 決策目的不是利潤最大，而是有多個，重要性有先后之分： 假設(shè)：第一目的 利潤不小于56元 (利潤小于56-d1-0) 第二目的 充分利用臺時，不加班 第三目的 產(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 難點1.建立模型中：目的函數(shù)偏向是正或者負 知

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

6、系數(shù)描畫目的的重要性程度。目的規(guī)劃問題的稱心解可 是一個 點， 一條線段或者為一個區(qū)域。第四章：目的規(guī)劃及其圖解法1d1-d1+X1-X2 +1=0X1X2d1- =1X1 - X2 =0第四章：目的規(guī)劃及其圖解法1難點2.圖解方法中：方向偏向是正或者負X1 - X2 =02X1-X2 +1=0判別d1-方向判別d1+方向d2+ =1X1+2X2 =10X1X2510X1+2X2 -1=10第四章：目的規(guī)劃及其圖解法1d2+d1-P104 例3 電視消費第四章：目的規(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 電視消費d3d2+ 0d1- 0彩電X1X2黑白5004040第四章：目的規(guī)劃及其圖解法1難點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ī)劃問題的靈敏度分析，普通只對約束右端項的 變化以及優(yōu)先級系數(shù)的變化進展?！纠?】判別下述說法能否正確? (a)線性規(guī)劃模型是目的規(guī)劃模型的一種特殊方式; (b)正偏向變量應(yīng)取正值、負偏向變量應(yīng)取負值； (c)目的規(guī)劃模型中，假設(shè)不含系統(tǒng)約束，那么一定有解； (d)目的規(guī)劃的數(shù)學(xué)模型應(yīng)同時包括系統(tǒng)約束和目的約束。答：a正確。模型構(gòu)造完全一致，可以將線性規(guī)劃模型改寫成單 一目的方式的目的規(guī)劃。 b錯誤。正負變量都定義取非負的值。 (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ī)劃難點三個難點1.建立模型中：目的函數(shù)偏向是正或者負難點2.圖解方法中：方向偏向是正或者負 難點3.圖解方法中：判別解第四章：目的規(guī)劃及其圖解法1運籌學(xué)目的規(guī)劃2本節(jié)課義務(wù)：目的規(guī)劃單純形法目的規(guī)劃靈敏度第四章：目的規(guī)劃單純形法和靈敏度2復(fù)習(xí)上節(jié)課內(nèi)容：目的規(guī)

10、劃和圖解法上節(jié)課難點三個難點1.建立模型中：目的函數(shù)偏向是正或者負難點2.圖解法中：方向偏向是正或者負 難點3.圖解法中：判別解本節(jié)課要點三個 要點1 初試單純形表要點2 檢驗數(shù)的計算要點3 檢驗數(shù)正負的判別P103 例 2 目的規(guī)劃單純形法第四章：目的規(guī)劃單純形法和靈敏度2原資料嚴(yán)厲限制目的1：產(chǎn)品2產(chǎn)量不低于產(chǎn)品1的產(chǎn)量目的2：充分利用設(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要點1 初試單純形表:有一個單位矩陣 檢驗數(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檢驗數(shù)P11P2122P38101根據(jù)目的函數(shù)C2 - CB B-1 P2 = 0 0 0 P2 P3 (1 1 2 10 )T = - 2P2 - 10

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

13、B-1 b0XS0d1-0X21/211/2-1/255/1.5P3d3-檢驗數(shù)P1P2P3-3 把這一行一切數(shù)乘以2P2+10P3加到檢驗數(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檢驗數(shù)P11P211P335 51C7 CB B-1 P7 = P2

14、 0 0 0 P3 (1/2 1/2 1/2 5 )T = P2 5P3單純形法：降本錢，負中取小 ( 注：d2+ 的檢驗數(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檢驗數(shù)P11P211P310非基變量檢驗數(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檢驗數(shù)P101P211P31單純形法：最優(yōu)解X1 10/3 ， X210/3，Xs 1，d3+ 4非基變量檢驗數(shù)為零 對應(yīng)無數(shù)最優(yōu)解d1-d3+對換解目的規(guī)劃的單純形法(P105)最優(yōu)解特點一特點二檢驗數(shù)包含第四章：目的規(guī)劃單純形法和靈敏度2?檢驗數(shù) 2P2 -3 P3為正 檢驗數(shù) -3P2 + 5 P3為負檢驗

16、數(shù) P1 - 8P2 -9 P3為正要點3 檢驗數(shù)正負的判別檢驗數(shù)中優(yōu)先權(quán)大的系數(shù)符號為準(zhǔn) 檢驗數(shù) -3P2 + 5 P3為負 檢驗數(shù) 2P2 -3 P3為正 檢驗數(shù) P1 - 8P2 -9 P3為正第四章：目的規(guī)劃單純形法和靈敏度2靈敏度分析-優(yōu)先級改動(107)：優(yōu)先彩電 優(yōu)先黑白第四章：目的規(guī)劃單純形法和靈敏度2優(yōu)先級改動 目的函數(shù)改動， C改動 CB改動， 單純形表中 檢驗數(shù)CN CB B-1 N改動優(yōu)先級改動單純形表中 檢驗數(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ù)矩陣中有一個矩陣單位優(yōu)先級改動 目的函數(shù)改動 C改動 CB改動， 單純形表中 檢驗數(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檢驗

18、數(shù)P11322P2231P31C4 CB B-1 P4 = 2P2 0 0 P1 0 (1 0 3 1 )T = 3P1 2P2單純形法：降本錢，負中取小 ( 注：d1+ 的檢驗數(shù)負)相除后正中取小轉(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檢驗數(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é)課要點三個 1 初試單純形表2 檢驗數(shù)的計算3 檢驗數(shù)正負的判別第四章：目的規(guī)劃運用3目的規(guī)劃運用舉例 (P109) 例6.調(diào)工資方案目的1 不超越年工資總額60000元2 每級人數(shù)不超越定編人數(shù)二三級晉級面盡能夠到達現(xiàn)有人數(shù)的204 三級缺乏人數(shù)可以錄取新工人，一級有10要退休年工資現(xiàn)有人數(shù)定編人數(shù)一級20001012二級15001215三級10001515合計3742第四章：目的規(guī)劃運用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ī)劃運用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ī)劃運用3第3目的：二三級晉級面盡能夠到達現(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)濟含意例6.調(diào)工資方案討論：幾種了解知晉級面不超越20%晉級面不超越20%，盡能夠多提晉級面盡能夠正好20%第四章：目的規(guī)劃運用31 B4 是重點保證單位，必需滿足全部需求2 A3向B1提供產(chǎn)量不少于1003 每個銷地的供應(yīng)量不少于需求的804 總運費不超越最小運費的1105 由于路問題，A2盡量不運到B46 B1， B3的供應(yīng)率要一樣7 總運輸費用盡量少第四章：

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