【正文】 企業(yè)實(shí)際進(jìn)行應(yīng)用 20% 4 OR:SM 管理運(yùn)籌學(xué)的稱謂 ? 管理運(yùn)籌學(xué)是一門(mén)研究如何最優(yōu)安排的學(xué)科。為解決這個(gè)問(wèn)題，成立運(yùn)籌學(xué)小組，稱Operational Research，意為 作戰(zhàn)研究 。 ? 目的：用科學(xué)方法分析管理問(wèn)題，為管理者決策提供依據(jù) ? 目標(biāo)：在企業(yè)經(jīng)營(yíng)內(nèi)外環(huán)境的限制下，實(shí)現(xiàn)資源效用最大 組織中存 在的問(wèn)題 定量分析 定性分析 評(píng)價(jià)與評(píng)估 決策 量化管理是第一步 ,它導(dǎo)致控制 ,并最終實(shí)現(xiàn)改進(jìn) 如果不能量化某些事情，那么就不能理解它 如果不能理解它，那么就不能控制它 如果不能控制它，那么就不能改進(jìn)它 —— H. James Harrington ? 定性到定量分析，數(shù)量界限的重要性：量變引起質(zhì)變 9 OR:SM ? 聽(tīng)一場(chǎng)音樂(lè)會(huì)： 網(wǎng)絡(luò)訂票的票價(jià) 500元，不去可退票 ? 情況 1：在你馬上要出發(fā)的時(shí)候，發(fā)現(xiàn)你把最近的價(jià)值500元的電話卡弄丟了。 ? 乙比較賺錢 , 假如 80個(gè)全部生產(chǎn) ? 需用 E產(chǎn)能 2400分鐘，但是 E只有 2400分鐘可用 ? 因此只能生產(chǎn) 80個(gè)乙 (2400/30)，而丙無(wú)法生產(chǎn) ? 方案： 甲 產(chǎn)品 40個(gè)， 乙 產(chǎn)品 80個(gè)， 丙 產(chǎn)品 0個(gè) ? 總收入 =40 173+80 233+0 170=25560 ? 原料 =40 65+80 95+0 65=10200 ， 營(yíng)運(yùn)費(fèi)用 =11000 ? 利潤(rùn) =255601020011000=4360 ? 方 案 四：計(jì)時(shí)工資，但以占用瓶頸資源大小為決策意識(shí)。 據(jù)市場(chǎng)分析，單位甲乙產(chǎn)品的銷售價(jià)格分別為 73和 75元，試確定獲利最大的產(chǎn)品生產(chǎn)計(jì)劃。已知各廠的產(chǎn)量、各經(jīng)銷商的銷售量及從 Ai 到 Bj 的單位運(yùn)費(fèi)為 Cij。 ? 建模技巧：將非線性的函數(shù)進(jìn)行分段線性化 。 （ 4） 連續(xù)性假定 ? 決策變量取值連續(xù) 。 maxZ= 3x1 +5 x2 2 x1 ≤16 2x2 ≤10 3x1 +4 x2 ≤32 x1 ≥0, x2 ≥0 2x1 =16 2x2 =10 3x1 +4 x2 =32 0 A B C D 36 OR:SM 2x1 =16 2x2 =10 3x1 +4 x2 =32 0 A B C D 四、線性規(guī)劃的圖解方法 第一節(jié) 線性規(guī)劃的一般模型 線性規(guī)劃的最優(yōu)解 目標(biāo)函數(shù) Z= 3x1 +5 x2 代表以 Z 為參數(shù)的一族平行線。 42 OR:SM 一、線性規(guī)劃的標(biāo)準(zhǔn)型式 第二節(jié) 線性規(guī)劃的一般模型 標(biāo)準(zhǔn)型轉(zhuǎn)換方法 (1)如果極小化原問(wèn)題 minZ=CX，則令 Z39。 (4)對(duì)于 ≥型約束，則在左端減去一個(gè)非負(fù)剩余變量，使其為等式。 1 2 3 4 51 2 31 2 41 2 51 2 3 4 5m a x 3 5 0 0 02 0 160 2 10..3 4 32, , , , 0Z x x x x xx x xx x xstx x xx x x x x? ? ? ? ?? ? ???? ? ???? ? ??? ??43 OR:SM 二、線性規(guī)劃之解的概念 第二節(jié) 線性規(guī)劃的一般模型 基矩陣： 一個(gè)非奇異的子矩陣（線性無(wú)關(guān)）。 ???????????100010001B? 基變量是 x3, x4, x5 ? 非基變量是 x1, x2 ? 令非基變量 x1=x2=0，得到一個(gè)基解 x3=16， x4=10， x5=32 44 OR:SM 二、線性規(guī)劃之解的概念 第二節(jié) 線性規(guī)劃的一般模型 線性規(guī)劃解之關(guān)系 可行解 ： 滿足約束條件 AX=b, X≥0 的解。 最優(yōu)基： 最優(yōu)解對(duì)應(yīng)的基矩陣，稱為最優(yōu)基。 定理 4. 線性規(guī)劃如果有可行解，則一定有基可行解；如果有最優(yōu)解，則一定有基可行解是最優(yōu)解。?48 OR:SM 三、單純形法的基本原理 第二節(jié) 線性規(guī)劃的一般模型 16 2 0 1 0 0 5 0 1 0 1/2 0 12 3 0 0 2 1 x3 x2 x5 0 5 0 3 0 0 5/2 0 5 4 Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j x1 x2 x3 x4 x5 3 5 0 0 0 檢驗(yàn)數(shù) ?j 8 0 0 1 4/3 2/3 5 0 1 0 1/2 0 4 1 0 0 2/3 1/3 x3 x2 x1 0 5 3 0 0 0 1/2 1 最優(yōu)解 :X*=(4,5,8,0,0)T， Z*=37 49 OR:SM 三、單純形法的基本原理 第二節(jié) 線性規(guī)劃的一般模型 ? 單純形的管理啟示 2x1=16 2x2 =10 3x1 +4 x2 =32 X0=(0,0,10,10,32)T X1=(0,5,10,0,12)T X1=(4,5,8,0,0)T 企業(yè)管理過(guò)程也是如此，把現(xiàn)有方案作為初始方案，找到最急需要改進(jìn)的某個(gè)問(wèn)題和改進(jìn)方向，一次做好某個(gè)主要問(wèn)題的解決與改進(jìn)；一次只解決和改進(jìn)一個(gè)問(wèn)題的難度最??；解決之后，再尋求可以改進(jìn)的其它地方，再次改進(jìn)，不斷地追求完美。 53 OR:SM 第一節(jié) 目標(biāo)函數(shù)的描述技巧 三、計(jì)時(shí)工資 ? 目標(biāo)函數(shù)為 1 2 3m a x 108 138 105 110 00Z x x x? ? ? ?? 經(jīng) Lindo軟件求解，得到最優(yōu)解為 Z=5800,x1=40,x2=60,x3=40。各地之間的單位運(yùn)輸物流成本（由距離和運(yùn)輸方式?jīng)Q定） 56 OR:SM 第三節(jié) 線性規(guī)劃的典型案例 ? 決策變量：設(shè)從供貨源到分銷中心的運(yùn)輸量為 ，從分銷中心到需求市場(chǎng)的運(yùn)輸量為 。新的基解為 139。 廠方為了在談判時(shí)心中有數(shù) ， 需掌握設(shè)備臺(tái)時(shí)費(fèi)用的最低價(jià)碼 ， 以便衡量對(duì)方出價(jià) ， 對(duì)出租與否做出抉擇 。于是有 2y1+0y2+3y3≥ 3 ? 同理，對(duì)乙產(chǎn)品而言，則有 0y1+2y2+4y3≥ 5 ? 設(shè)備臺(tái)時(shí)出讓的收益（希望出讓的收益最少值） min? 16y1+10y2+32y3 ? 顯然還有 y1， y2， y3≥0 65 OR:SM 第一節(jié) 對(duì)偶規(guī)劃的數(shù)學(xué)模型 一、對(duì)偶問(wèn)題的提出 例 1的對(duì)偶問(wèn)題的數(shù)學(xué)模型 ? 對(duì)偶問(wèn)題的最優(yōu)解： y1=0， y2=1/2， y3=1， W* =37 ? 兩個(gè)問(wèn)題的目標(biāo)函數(shù)值相等并非偶然 ? 前者稱為線性規(guī)劃原問(wèn)題，則后者為對(duì)偶問(wèn)題，反之亦然。 最優(yōu)性定理 設(shè) ， 分別為原問(wèn)題和對(duì)偶問(wèn)題的可行解，且 則 ， 分別為各自的最優(yōu)解。 ? 若原問(wèn)題價(jià)值系數(shù) Cj表示單位產(chǎn)值 ， 則 yi 稱為 影子價(jià)格 。 1 2 31 2 31 2 31 2 3m in 360 200 3009 4 3 7 . 4 5 10 12, , 0w y y yy y yy y yy y y? ? ?? ? ???? ? ??? ??1* 0y ?2* 6y ?3* 2y ?* 428Z ?45**0 , 0yy??設(shè)原材料的單位出讓獲利為 y1，設(shè)備工時(shí)的單位出讓獲利為 y3，電量的單位出讓獲利為 y2 。 解：設(shè) x1為甲產(chǎn)品的臺(tái)數(shù)， x2為乙產(chǎn)品的臺(tái)數(shù)。如何選址和安排調(diào)運(yùn)，可使總費(fèi)用最??？ iF解：選址建廠與否是個(gè) 01型決策變量， 假設(shè) yi =1，選擇第 i 址建廠， yi=0，不選擇第 i 址建廠； 計(jì)劃從 i 址至區(qū)域市場(chǎng) j 的運(yùn)輸 運(yùn)量 xij為實(shí)數(shù)型決策變量。 77 OR:SM 第二節(jié) 整數(shù)規(guī)劃求解 二、窮舉整數(shù)法 對(duì)于決策變量少，可行的整數(shù)解又較少時(shí)，這種窮舉法有時(shí)是可行的，并且也是有效的。 ? 依次在縮小的可行域中求解新構(gòu)造的線性規(guī)劃的最優(yōu)解 ，直到獲得原整數(shù)規(guī)劃的最優(yōu)解 。請(qǐng)安排服務(wù)員的工作時(shí)間，使服務(wù)員總數(shù)最少 . 82 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 三、項(xiàng)目投資選擇 有 600萬(wàn)元投資 5個(gè)項(xiàng)目，收益如表，求利潤(rùn)最大的方案？ 項(xiàng)目 投資額 項(xiàng)目收益 約束條件 I 2 10 1 60 II 3 00 2 10 I II 1 50 60 IV 1 30 80 V 2 60 1 80 項(xiàng)目 I 、 II 、 I II 中選 1 項(xiàng) 項(xiàng)目 I II 、 IV 之中選 1 項(xiàng) 選項(xiàng)目 V 必先選項(xiàng)目 I ???? 個(gè)項(xiàng)目投資選中第不 個(gè)項(xiàng)目投資選中第 jjx j 01 ??????????????????????????10,116002601301503002101808060210160m a x5432115433215432154321或xxxxxxxxxxxxxxxxxxxxxxZ83 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 四、互斥約束問(wèn)題 ? 例如關(guān)于煤資源的限制，其約束條件為： ? 企業(yè)也可以考慮采用天然氣進(jìn)行加熱處理： ? 這兩個(gè)條件是互相排斥的。 T恤 襯衫 褲子 勞動(dòng)力 3 2 6 布料 售價(jià) 250 400 600 可變成本 100 180 300 生產(chǎn)線租金 (萬(wàn) ) 20 15 10 假設(shè)： yj=1，要租用生產(chǎn)線 j yi=0，不租用生產(chǎn)線 j 第 j 種服裝生產(chǎn)量 xj ?????????????????????10,0,8 8 0 8 2 0 0623..1 0 0 0 0 01 5 0 0 0 02 0 0 0 0 03 0 02 2 01 5 0m a x321321321321321321或且取整數(shù)yyyxxxxxxxxxtsyyyxxxZ 111 yMx ? 222 yMx ? 333 yMx ?85 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 六、任務(wù)指派問(wèn)題 甲乙丙丁四個(gè)人， ABCD四項(xiàng)任務(wù)，如何指派總時(shí)間最短？ A B C D 甲 3 5 8 4 乙 6 8 5 4 丙 2 5 8 5 丁 9 2 5 2 任務(wù) 時(shí)間 人員 解： 引入 01變量 xij ， xij =1：任務(wù) j指派人員 i去完成 xij =0：任務(wù) j不派人員 i去完成 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 43 1 3 2 3 3 3 4 4 1 4 2 4 3 4 4m in 3 5 8 4 6 8 5 42 5 8 5 9 2 5 2Z x x x x x x x xx x x x x x x x? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? 一項(xiàng)任務(wù)只由一個(gè)人完成 ? 一人只能完成一項(xiàng)任務(wù) 1 1 2 1 3 1 4 11 2 2 2 3 2 4 21 3 2 3 3 3 4 31 4 2 4 3 4 4 41111x x x xx x x xx x x xx x x x? ? ? ?? ? ? ?? ? ? ?? ? ? ? 1 1 1 2 1 3 1 42 1 2 2 2 3 2 43 1 3 2 3 3 3 44 1 4 2 4 3 4 41111x x x xx x x xx x x xx x x x? ? ? ?? ? ? ?? ? ? ?? ? ? ?86 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 七、設(shè)施選址問(wèn)題 ? 擬定在 2個(gè)地點(diǎn)中選址設(shè)立分銷中心，執(zhí)行產(chǎn)品的倉(cāng)儲(chǔ)和轉(zhuǎn)運(yùn)，一個(gè)分銷中心擬定設(shè)立一個(gè)倉(cāng)庫(kù) W