【正文】 ? 發(fā)揮自己管理實(shí)踐經(jīng)驗(yàn)豐富和理論聯(lián)系實(shí)際的能力 ? 強(qiáng)化結(jié)合實(shí)際問題建立管理優(yōu)化模型的能力 ? 強(qiáng)化解決問題的方案或模型的解的分析與應(yīng)用能力 ? 充分借用管理運(yùn)籌學(xué)教學(xué)軟件 25 OR:SM 第 1 章 線性規(guī)劃 Sub title 內(nèi)容提要 26 OR:SM 一、線性規(guī)劃的三個(gè)要素 第一節(jié) 線性規(guī)劃的一般模型 ? 決策變量 ? 決策問題待定的量值 ? 取值要求非負(fù) ? 約束條件 ? 任何管理決策問題都是限定在一定的條件下求解 ? 把各種限制條件表示為一組等式或不等式稱約束條件 ? 約束條件是決策方案可行的保障 ? 約束條件是決策變量的線性函數(shù) ? 目標(biāo)函數(shù) ? 衡量決策優(yōu)劣的準(zhǔn)則 ， 如時(shí)間最省 、 利潤最大 、 成本最低 ? 目標(biāo)函數(shù)是決策變量的線性函數(shù) ? 有的目標(biāo)要實(shí)現(xiàn)極大 ， 有的則要求極小 27 OR:SM 二、線性規(guī)劃模型的舉例 第一節(jié) 線性規(guī)劃的一般模型 生產(chǎn)計(jì)劃問題 例 . 某廠生產(chǎn)甲乙兩種產(chǎn)品，生產(chǎn)工藝路線為：各自的零部件分別在設(shè)備 A、 B加工，最后都需在設(shè)備 C上裝配。為發(fā)揮集團(tuán)優(yōu)勢，公司要統(tǒng)一籌劃運(yùn)銷問題，求運(yùn)費(fèi)最小的調(diào)運(yùn)方案。 （ 5） 確定性假定 ? 所有參數(shù)都是確定的 ， 不包含隨機(jī)因素 。=Z，轉(zhuǎn)為求 maxZ39。 ? 矩陣 A中任意 m列的線性無關(guān)子矩陣 B ，稱為一個(gè)基。 非 可 行 解 可 行 解 基 解 基 可 行 解 45 OR:SM 二、線性規(guī)劃之解的概念 第二節(jié) 線性規(guī)劃的一般模型 線性規(guī)劃基本原理 定理 1. 若線性規(guī)劃問題存在可行域，則其可行域一定是凸集。 50 OR:SM 第 2 章 線性規(guī)劃討論 Sub title 內(nèi)容提要 51 OR:SM ? 計(jì)件工資體系，目標(biāo)是企業(yè)利潤最大化： 第一節(jié) 目標(biāo)函數(shù)的描述技巧 一、計(jì)件工資 1 2 3m a x 66 89 70Z x x x? ? ?產(chǎn)品甲： 產(chǎn)品乙： 產(chǎn)品丙： 非負(fù)性約束 1 40x ?2 803 40x ?1 2 3, , 0x x x ?? 計(jì)件工資制薪酬體系下，工作時(shí)間不會(huì)完全受每天 8小時(shí)工作時(shí)間約束，但有產(chǎn)品市場需求約束，如下： ? 經(jīng) Lindo軟件求解，得到最優(yōu)解為 Z=12560，產(chǎn)品甲 x1=40，產(chǎn)品乙 x2=80，產(chǎn)品丙 x3=40。選址規(guī)劃在于二者的實(shí)際取值。 ? 在這個(gè)問題上廠長面臨著兩種選擇：自行生產(chǎn)或出租設(shè)備 。 3. 對偶性定理 若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，而且 兩者的目標(biāo)函數(shù)值相等 。 出讓決策的線性規(guī)劃模型： 71 OR:SM 第 4 章 整數(shù)規(guī)劃 Sub title 內(nèi)容提要 72 OR:SM 第一節(jié) 整數(shù)規(guī)劃問題 ? 線性規(guī)劃的決策變量取值可以是任意非負(fù)實(shí)數(shù)，但許多實(shí)際問題中，只有當(dāng)決策變量的取值為整數(shù)時(shí)才有意義 ? 例如，產(chǎn)品的件數(shù)、機(jī)器的臺數(shù)、裝貨的車數(shù)、完成工作的人數(shù)等，分?jǐn)?shù)或小數(shù)解顯然是不合理的。 1 1 111m in1 , 2 , ...,1 , 2 , ..., .00 , 1m m ni i ij iji i jnij i ijmij jiijiZ y F c xx y a i mx b j nxy? ? ????????????????? ?????? ? ???76 OR:SM 第二節(jié) 整數(shù)規(guī)劃求解 一、舍入化整法 ?為了滿足整數(shù)解的要求，自然想到“舍入”或“截尾”處理，以得到與最優(yōu)解相近的整數(shù)解。 ? 定界的含義： ? IP是在相應(yīng)的 LP基礎(chǔ)上增加整數(shù)約束 ? IP的最優(yōu)解不會(huì)優(yōu)于相應(yīng) LP的最優(yōu)解 ? 對 MaxZ，相應(yīng) LP的 Z*是原 IP的上界 79 OR:SM 第二節(jié) 整數(shù)規(guī)劃求解 三、分支定界法 121 623 , 2 , 3277LPx x Z? ? ?：0 1 7 53 , 2 , 329 9 9LPx x Z? ? ?：2 4 , 1 , 29LPx x Z? ? ?：33 , 2 , 28LPx x Z? ? ?：4442 , 3 , 3155LPx Z? ? ?：5462 , 3 , 29LPx x Z? ? ?：6LP ：無 可 行 解1272 , 3 , 27LPx x Z? ? ?：8221 , 4 , 28LPx x Z? ? ?：x1≤3 x1 ≥4 x2≤2 x2 ≥3 x1≤2 x1 ≥3 x2≤3 x2 ≥4 0 9532下界：上界：29 7232下界：上界：29 5431下界：上界：29 7629下界：上界：2929下界：上界：80 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 一、生產(chǎn)基地規(guī)劃 例： 某公司擬建設(shè) A、 B兩種類型的生產(chǎn)基地若干個(gè)，兩種類型的生產(chǎn)基地每個(gè)占地面積，所需經(jīng)費(fèi)，建成后生產(chǎn)能力及現(xiàn)有資源情況如下表所示。 ? 若設(shè)立倉庫 W1，建設(shè)成本為 10萬元，最大庫容為 20萬臺，單位產(chǎn)品的月庫存成本為 2元； ? 若設(shè)立倉庫 W2建造成本為 20萬元，最大庫容為 25萬臺，單位產(chǎn)品的月庫存成本為 3元。 每年可用勞動(dòng)力 8200h，布料 8800m2。 5x1 +7 x2 =35 2x1 + x2 =9 ? (3,3) ? ? ? ? ? ? ? ? ? ? )972,913(78 OR:SM 第二節(jié) 整數(shù)規(guī)劃求解 三、分支定界法 ? 不考慮整數(shù)限制 ， 先求出相應(yīng)線性規(guī)劃 的最優(yōu)解 ， ? 若求得的最優(yōu)解符合整數(shù)要求 ， 則是原 IP的最優(yōu)解； ? 若不滿足整數(shù)條件 ， 則任選一個(gè)不滿足整數(shù)條件的變量來構(gòu)造新的約束 ， 在原可行域中剔除部分非整數(shù)解 。 解：對于每一種物品無非有兩種狀態(tài)，帶或者不帶，不妨設(shè) ???? 帶此種物品不帶此種物品10jx ???????????????????)7,2,1(102542126255104814181520m ax76543217654321?jxxxxxxxxxxxxxxxZj 或序號 1 2 3 4 5 6 7 物品 食品 氧氣 冰鎬 繩索 帳篷 相機(jī) 設(shè)備 重量 5 5 2 6 12 2 4 重要性系數(shù) 20 15 18 14 8 4 10 01規(guī)劃的模型： 75 OR:SM 第一節(jié) 整數(shù)規(guī)劃問題 三、混合整數(shù)規(guī)劃 例：某產(chǎn)品有 n個(gè)區(qū)域市場，各區(qū)域市場的需求量為 bj噸 /月；現(xiàn)擬在 m個(gè)地點(diǎn)中選址建生產(chǎn)廠，一個(gè)地方最多只能建一家工廠；若選 i地建廠，生產(chǎn)能力為 ai噸 /月，其運(yùn)營固定費(fèi)用為 F元 /月；已知址 i至 j區(qū)域市場的運(yùn)價(jià)為 cij元 /噸。 ? 對資源 i總存量的評估： 購進(jìn) or 出讓 對資源 i當(dāng)前分配量的評估： 增加 or 減少 ? 第一，影子利潤說明增加哪種資源對經(jīng)濟(jì)效益最有利 ? 第二，影子價(jià)格告知以怎樣的代價(jià)去取得緊缺資源 ? 第三，影子價(jià)格是機(jī)會(huì)成本，提示資源出租 /轉(zhuǎn)讓的基價(jià) ? 第四，利用影子價(jià)格分析新品的資源效果：定價(jià)決策 ? 第五，利用影子價(jià)格分析現(xiàn)有產(chǎn)品價(jià)格變動(dòng)的資源緊性 ? 第六，可以幫助分析工藝改變后對資源節(jié)約的收益 ? 第七，可以預(yù)知哪些資源是稀缺資源而哪些資源不稀缺 69 OR:SM 第三節(jié) 資源定價(jià)的決策方案 例：某廠生產(chǎn)甲乙產(chǎn)品， （ 1）如何安排每周的利潤為最大 ? （ 2）如果企業(yè)可以不生產(chǎn)，那資源出讓如何定價(jià)？ 甲 乙 資源成本 資源擁有量 原材料 (kg) 設(shè)備 (工時(shí) ) 電力 (度 ) 9 4 3 4 5 10 20 50 1 360 200 300 銷售價(jià)格 (元 ) 390 352 ????????????????0,3001032023436049s. t.127max2121212121xxxxxxxxxxZ*T( 20 , 24 , 84 , 0 , 0)X ?一、最優(yōu)生產(chǎn)決策 70 OR:SM 第三節(jié) 資源定價(jià)的決策方案 二、資源獲利決策 如果決策者考慮自己不生產(chǎn)甲乙兩種產(chǎn)品，而把原擬用于生產(chǎn)這兩種產(chǎn)品的原材料、設(shè)備工時(shí)、電量資源全部出售給外單位，或者做代加工，則應(yīng)如何確定這三種資源的價(jià)格。 根據(jù)對偶規(guī)劃，很容易寫出對偶問題的對偶問題模型。 ***0iir rirbaba? ? ? ? ?***0iir rirba? ? ? ? ? }0|{min}0|{max******??????? iririiriririiaabbaab62 OR:SM 第 3 章 對偶規(guī)劃 Sub title 內(nèi)容提要 63 OR:SM 第一節(jié) 對偶規(guī)劃的數(shù)學(xué)模型 一、對偶問題的提出 ? 若例 1中該廠的產(chǎn)品平銷 ， 現(xiàn)有另一企業(yè)想租賃其設(shè)備 。 在分銷渠道中，擬定在 2個(gè)地點(diǎn)中選址設(shè)立分銷中心，執(zhí)行產(chǎn)品的轉(zhuǎn)運(yùn)任務(wù)。 47 OR:SM 三、單純形法的基本原理 第二節(jié) 線性規(guī)劃的一般模型 maxZ=3x1 +5 x2 +0x3 +0x4+0x5 =0 2x1 + x3 =16 2x2 + x4 =10 3x1 +4 x2 + x5 =32 Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j x1 x2 x3 x4 x5 3 5 0 0 0 16 2 0 1 0 0 10 0 2 0 1 0 32 3 4 0 0 1 x3 x4 x5 0 0 0 0 3 5 0 0 0 10/2=5 32/4=8 ?????miijBjj aCC i139。 最優(yōu)解： 使目標(biāo)函數(shù)最優(yōu)的可行解，稱為最優(yōu)解 。k≥0,xk ≥0) 。 38 OR:SM 五、線性規(guī)劃解的可能性 第一節(jié) 線性規(guī)劃的一般模型 唯一最優(yōu)解：只有一個(gè)最優(yōu)點(diǎn) 多重最優(yōu)解：無窮多個(gè)最優(yōu)解 當(dāng)市場價(jià)格下降到 74元，其數(shù)學(xué)模型變?yōu)? 12121212m a x 3 42 162 10 .3 4 32,0Z x xxxxxxx???????????? ??2x1 =16 2x2 =10 3x1 +4 x2 =32 Z=24 Z=32 Z=12 39 OR:SM 五、線性規(guī)劃解的可能性 第一節(jié) 線性規(guī)劃的一般模型 無界解：可行域無界，目標(biāo)值無限增大 (缺乏必要約束 ) 12112m a x 3 52 16 .,0Z x xxxx???????40 OR:SM 五、線性規(guī)劃解的可能性 第一節(jié) 線性規(guī)劃的一般模型 沒有可行解：線性規(guī)劃問題的可行域是空集 (約束條件相互矛盾 ) 12121212m a x 3 55 . 3 4 24,0Z x xxxxxxx?????????? ?? x 1x 2O2 4 6 8 2 4 6 8目標(biāo)沖突 利害沖突 目標(biāo)強(qiáng)沖突 利害弱沖突 41 OR:SM 一、線性規(guī)劃的標(biāo)準(zhǔn)型式 第二節(jié) 線性規(guī)劃的一般模型