【正文】 3 1/3 檢驗(yàn)數(shù) ?j 0 0 0 2C1/35/2 C1/3 415001 ???? cj?61 OR:SM 第四節(jié) 線性規(guī)劃靈敏度分析 二、右端常量的變動(dòng)分析 ? 參數(shù) bi的變化范圍 第 r個(gè)約束的右端項(xiàng)為 br，增量 ?br，其它數(shù)據(jù)不變。 ***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è)備 。 64 OR:SM 第一節(jié) 對偶規(guī)劃的數(shù)學(xué)模型 一、對偶問題的提出 出讓定價(jià) ? 假設(shè)出讓 A、 B、 C設(shè)備所得利潤分別為 y y y3 ? 原本用于生產(chǎn)甲產(chǎn)品的設(shè)備臺時(shí)，如若出讓，不應(yīng)低于自行生產(chǎn)帶來的利潤，否則寧愿自己生產(chǎn)。 根據(jù)對偶規(guī)劃，很容易寫出對偶問題的對偶問題模型。 ? 對偶變量的值 yi*表示第 i種資源的邊際價(jià)值 ， 稱為 影子價(jià)值 。 ? 對資源 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à)格。 ? 全部決策變量的取值都為整數(shù)，則稱為全整數(shù)規(guī)劃 (All IP) ? 僅要求部分決策變量的取值為整數(shù)，則稱為混合整數(shù)規(guī)劃(Mixed IP) ? 要求決策變量只取 0或 1值，則稱 01規(guī)劃 (01 Programming) 73 OR:SM 第一節(jié) 整數(shù)規(guī)劃問題 一、純整數(shù)規(guī)劃 產(chǎn)品 資源 甲 乙 現(xiàn)有量 A 2 1 9 B 5 7 35 單臺利潤 6 5 例：某企業(yè)利用材料和設(shè)備生產(chǎn)甲乙產(chǎn)品，其工藝消耗系數(shù)和單臺產(chǎn)品的獲利能力如下表所示： 問如何安排甲、乙兩產(chǎn)品的產(chǎn)量，使利潤為最大。 解：對于每一種物品無非有兩種狀態(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元 /噸。 不考慮整數(shù)約束則是一個(gè) LP問題 ,稱為原整數(shù)規(guī)劃的松弛問題 對于例 1的數(shù)學(xué)模型，不考慮整數(shù)約束的最優(yōu)解： x1 *=28/9， x2 * =25/9， Z * =293/9 舍入化整 x1 =3， x2 =3， Z =33，不滿足約束條件 5x1 +7 x2 ≤35，非可行解； x1 =3， x2 =2， Z =28，滿足約束條件，是可行解，但不是最優(yōu)解； x1 =4， x2 =1， Z =29，滿足約束條件，才是最優(yōu)解。 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ù)解 。 ???????????????????????????????????????????皆為整數(shù)54321543215545435432432132121154321,0,35813119810..m i nxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxZ按規(guī)定，服務(wù)員連續(xù)工作 8小時(shí)(4個(gè)時(shí)段 )為一班。 每年可用勞動(dòng)力 8200h，布料 8800m2。倉庫選址決策引入 01變量 wj ： 87 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 七、設(shè)施選址問題 ? 供應(yīng)能力平衡約束： ? 市場需求平衡約束： ? 倉儲能力限制約束： ? 分銷中心不存留產(chǎn)品： ? 所有變量大于等于零： 1 1 1 2 2 1 2 2 1 1 1 2 1 3 2 1 2 2 2 31 2 1 1 1 2 2 1 2 2m in 2 5 4 2 3 4 5 2 2 31 0 2 0 2 ( ) 3 ( )Z x x x x y y y y y yw w x x x x? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? 1 1 1 22 1 2 250000150000xx?? 1 1 2 11 2 2 21 3 2 35000010000050000yyyyyy?????? 11 12 121 22 2202300250000x x wx x w?? 11 21 11 12 1312 22 21 22 23x x y y yx x y y y? ? ? ?? ? ? ? 1 1 1 2 2 1 2 2 1 1 1 2 1 3 2 1 2 2 2 3, , , , , , , , , 0x x x x y y y y y y 。 ? 若設(shè)立倉庫 W1，建設(shè)成本為 10萬元，最大庫容為 20萬臺，單位產(chǎn)品的月庫存成本為 2元； ? 若設(shè)立倉庫 W2建造成本為 20萬元，最大庫容為 25萬臺，單位產(chǎn)品的月庫存成本為 3元。引入 0—1變量 y，令 ? 互斥問題可由下述的條件來代替，其中 M是充分大的數(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ù)規(guī)劃問題，可行的整數(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ù)解。 maxZ= 6x1 +5 x2 2x1 + x2 ≤9 5x1 +7 x2 ≤35 x1, x2 ≥0 x1, x2 取整數(shù) 74 OR:SM 第一節(jié) 整數(shù)規(guī)劃問題 二、 01規(guī)劃 登山隊(duì)員可攜帶最大重量為 25公斤。 出讓決策的線性規(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ù)解顯然是不合理的。 ? 若原問題價(jià)值系數(shù) Cj表示單位利潤 ， 則 yi 稱為 影子利潤 。 3. 對偶性定理 若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，而且 兩者的目標(biāo)函數(shù)值相等 。 ? 對偶問題的最優(yōu)解對應(yīng)于原問題最優(yōu)單純型法表中，初始基變量的檢驗(yàn)數(shù)的負(fù)值。 ? 在這個(gè)問題上廠長面臨著兩種選擇：自行生產(chǎn)或出租設(shè)備 。 ( )BX B b b?? ? ???????????????????? ?rmrrrrrbabababB**2*11?**11**22**rrrm m rbababba? ? ? ?? ? ? ?? ? ? ?? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?1100rB b B b??????????? ? ?????????只要 X39。選址規(guī)劃在于二者的實(shí)際取值。 1 2 30 30 15 240 0x x x? ? ?1 2 310 20 0 240 0x x x? ? ?1 2 331 21 21 480 0x? ?313 24 480 0x x x? ?設(shè)備 E： 設(shè)備 F： 設(shè)備 G： 設(shè)