【正文】 ? 問題 ① 的最優(yōu)解： x1=4， x2=5， Z*=37。 4. 互補(bǔ)松弛性 最優(yōu)解的充分必要條件是 ， XY YXC Tb?XY 0* ?sXY 0* ?Ys67 OR:SM 第二節(jié) 對(duì)偶規(guī)劃的經(jīng)濟(jì)解釋 一、影子價(jià)值的內(nèi)涵 ? ?? ????njmiiijj ybxcZ1 1?iiybZ ???? 左邊是資源 bi每增加一個(gè)單位對(duì)目標(biāo)函數(shù) Z的貢獻(xiàn)； ? 對(duì)偶變量 yi在經(jīng)濟(jì)上表示原問題第 i種資源的 邊際價(jià)值 。 ? 要求全部或部分決策變量的取值為整數(shù)的線性規(guī)劃問題，稱為整數(shù)規(guī)劃 (Integer Programming)。 ?這樣做除少數(shù)情況外，一般不可行，因?yàn)榛蟮慕庥锌赡艹隽丝尚杏?，成為非可行解；或者雖是可行解，卻不是最優(yōu)解。問A、 B類型基地各建設(shè)多少個(gè)，可使總生產(chǎn)能力最大？ A B 資源限制 占地（萬 平米 ） 費(fèi)用（萬元） 2 5 5 4 13 24 生產(chǎn)能力（百件 / 年） 20 10 解：設(shè) A、 B兩類基地各建設(shè) x1,x2 個(gè)，則其模型為： ????????????且為整數(shù)0,244513521020m a x21212121xxxxxxxxZ81 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 二、人員安排規(guī)劃 某服務(wù)部門各時(shí)段 (每 2小時(shí)為一時(shí)段 )需要的服務(wù)人數(shù)如表： 時(shí)段 1 2 3 4 5 6 7 8 服務(wù)員最少數(shù)目 10 8 9 11 13 8 5 3 解：設(shè)第 j 時(shí)段開始時(shí)上班的服務(wù)員人數(shù)為 xj 第 j 時(shí)段來上班的服務(wù)員將在第 j+3 時(shí)段結(jié)束時(shí)下班，故決策變量有x1,x2,x3,x4,x5 。 ? 如何選址和安排調(diào)運(yùn)，建造費(fèi)用 +運(yùn)輸費(fèi)用 +倉(cāng)儲(chǔ)費(fèi)用為最小？ 10jw ???? 擬規(guī)劃建立倉(cāng)庫(kù) jW 不 規(guī)劃建立倉(cāng)庫(kù)jW 解：設(shè)從供貨源 Si到分銷中心 Wj的運(yùn)輸量為 xij，從分銷中心 到需求市場(chǎng) Rk的運(yùn)輸量為 yjk。 20234 21 ?? xx 18053 21 ?? xx ???? 作用采用天燃?xì)饧訜峒s束起 采用煤加熱約束起作用01y yMxx Myxx ??? ???? 1 8 053 )1(2 0 054 21 2184 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 五、租賃生產(chǎn)問題 服裝公司租用生產(chǎn)線擬生產(chǎn) T恤、襯衫和褲子。 例如，指派問題 。問都帶哪些物品的重要性最大。 ? 影子價(jià)格 =資源成本 +影子利潤(rùn) 68 OR:SM 第二節(jié) 對(duì)偶規(guī)劃的經(jīng)濟(jì)解釋 一、影子價(jià)值的內(nèi)涵 ? 影子價(jià)格不是資源的實(shí)際價(jià)格 ， 反映了資源配置結(jié)構(gòu) ， ? 其它數(shù)據(jù)固定 ， 某資源增加一單位導(dǎo)致目標(biāo)函數(shù)的增量 。 min? =16y1+10y2+32y3 2y1+ 0y2+ 3y3≥ 3 0y1+ 2y2+ 4y3≥ 5 y1， y2， y3≥0 . maxZ= 3x1 +5 x2 2x1 ≤16 2x2 ≤10 3x1 +4 x2 ≤32 x1 , x2 ≥0 66 OR:SM 第一節(jié) 對(duì)偶規(guī)劃的數(shù)學(xué)模型 二、對(duì)偶規(guī)劃的性質(zhì) 對(duì)稱性定理 對(duì)偶問題的對(duì)偶問題是原問題。B≥0 ，則可保持最優(yōu)基不變。 有三個(gè)區(qū)域目標(biāo)市場(chǎng)（銷地或銷售商），各銷地每月的市場(chǎng)需求量為 5萬臺(tái)、 10萬臺(tái)、 5萬臺(tái)。 ? 如果是最優(yōu)解，就得到這個(gè)線性規(guī)劃問題的最優(yōu)解； ? 如果判斷出不是最優(yōu)解，就想法由這個(gè)可行基按一定規(guī)則變化到下一個(gè)可行基，然后再判斷新得到的基可行解是不是最優(yōu)解； ? 如果還不是，再接著進(jìn)行下一個(gè)可行基變化，直到得到最優(yōu)解。 基可行解 ： 滿足非負(fù)性約束的基解稱為基可行解。kxk ， (x39。 ? 目標(biāo)函數(shù)最優(yōu)值一定在可行域的邊界達(dá)到，而不可能在其區(qū)域的內(nèi)部。 （ 3） 可加性假定 ? 決策變量對(duì)目標(biāo)函數(shù)和約束方程的影響是獨(dú)立于其他變量的 。 (2)約束條件 ： 生產(chǎn)受設(shè)備能力制約 ， 能力需求不能突破有效供給量 。在你出發(fā)時(shí)，發(fā)現(xiàn)把票單丟了。 ? Operations Research ? 日本譯作 “ 運(yùn)用學(xué) ” ? 香港 、 臺(tái)灣譯為 “ 作業(yè)研究 ” ? 我國(guó)譯作 “ 運(yùn)籌學(xué) ” ? 源于古語 “ 運(yùn)籌帷幄之中 ， 決勝千里之外 ” ? 取 “ 運(yùn)籌 ” 二字 ， 體現(xiàn)運(yùn)心籌謀 、 策略取勝 ? Management Science 管理科學(xué) ? 運(yùn)用數(shù)學(xué) 、 統(tǒng)計(jì)學(xué)和運(yùn)籌學(xué)中的量化分析原理和方法 ， 建立數(shù)學(xué)模型 /計(jì)算機(jī)仿真 ， 給管理決策提供科學(xué)依據(jù) 。 7 OR:SM ? 企業(yè)的成功要素中： ? 觀念意識(shí)更新 47％ ? 人文文化 35％ ? 技術(shù)優(yōu)勢(shì) 18％ ? 決策意識(shí)的科學(xué)性 ? 成功決策 ? 正確決策 二、學(xué)科作用 ？ 8 OR:SM 二、學(xué)科作用 1. 量化管理的重要性 ? 管理科學(xué)是對(duì)與 定量因素 有關(guān)的管理問題通過 應(yīng)用科學(xué)的方法 進(jìn)行 輔助管理決策 的一門學(xué)科。應(yīng)如何制定生產(chǎn)計(jì)劃，使總利潤(rùn)為最大。 ? 決策變量 ： 取 45%和 92%的硫酸分別為 x1 和 x2 噸 ? 約束條件 ： ? 求解二元一次方程組得解 ????????1002121xxxx? 非負(fù)約束 ： x1 ≥0， x2 ≥0 32 OR:SM 第一節(jié) 線性規(guī)劃的一般模型 若有 5種不同濃度的硫酸可選 (30%,45%,73%,85%,92%)會(huì)如何呢？ ??? ?????? ????? 1005432154321xxxxxxxxxx? 取這 5種硫酸分別為 x x x x x5 ，有 ? 有多少種配比方案？ ? 何為最好？ 若 5種硫酸價(jià)格分別為 400, 700, 1400, 1900, 2500元 /t，則： 1 2 3 4 51 2 3 4 51 2 3 4 5m in 400 700 1400 1900 2500100 . 1000 , 1 , 2 , ...5jZ x x x x xx x x x xx x x x xxj? ? ? ? ?? ? ? ? ? ??? ? ? ? ? ??? ???33 OR:SM 三、線性規(guī)劃模型的特征 第一節(jié) 線性規(guī)劃的一般模型 模型隱含假定 （ 1） 線性化假定 ? 函數(shù)關(guān)系式 f(x)= c1x1+c2x2+… +xn， 稱線性函數(shù) 。 1 1 2 211 1 12 2 1 121 1 22 2 2 21 1 2 212m a x( m in) Z( , )( , ) . ( , ), , 0nnnnnnm m m n n mnc x c x c xa x a x a x ba x a x a x ba x a x a x bx x x? ? ? ?? ? ? ? ? ???? ? ? ? ? ?????? ? ? ? ? ?????35 OR:SM 四、線性規(guī)劃的圖解方法 第一節(jié) 線性規(guī)劃的一般模型 線性規(guī)劃的可行域 可行域： 滿足所有約束條件的解的集合， 即所有約束條件共同圍城的區(qū)域。 (3)對(duì)于 ≤型約束，則在左端加上一個(gè)非負(fù)松弛變量，使其為等式。 基變量： ? 與基向量 Pj 相對(duì)應(yīng)的 m個(gè)變量 xj稱為基變量 ? 其余的 n m個(gè)變量為非基變量 線性規(guī)劃解之關(guān)系 基解： 令所有非基變量等于零，得出基變量的唯一解 。 定理 3. 若可行域有界，線性規(guī)劃的目標(biāo)函數(shù)一定可以在可行域的頂點(diǎn)上達(dá)到最優(yōu)。 ? 總收入 =173x1+233x2+170x3， 原料成本 =65x1+95x2+65x3，營(yíng)運(yùn)費(fèi)用 =11000， 則目標(biāo)函數(shù)為 maxZ= 108x1+138x2+105x311000 ? 崗位工資制薪酬體系下，工作時(shí)間也不會(huì)完全受每天 8小時(shí)工作時(shí)間約束，但有產(chǎn)品市場(chǎng)需求約束，如下： 產(chǎn)品甲： 產(chǎn)品乙： 產(chǎn)品丙： 非負(fù)性約束 1 40?2 80x3 40?1 2 3, , 0x x x ?? 經(jīng) Lindo軟件求解，得到最優(yōu)解為 Z=8560,x1=40,x2=80,x3=40。1 ????? ? jBjjj PBCCC? *1 jjjBj CPBCC ?????? ?60 OR:SM 第四節(jié) 線性規(guī)劃靈敏度分析 一、價(jià)值系數(shù)的變動(dòng)分析 ? 基變量 CBl的變化范圍 Cj C1 5 0 0 0 比 值 CB XB b x1 x2 x3 x4 x5 0 x3 8 0 0 1 4/3 2/3 5 x2 5 0 1 0 1/2 0 C1 x1 4 1 0 0 2/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ù)不變。 64 OR:SM 第一節(jié) 對(duì)偶規(guī)劃的數(shù)學(xué)模型 一、對(duì)偶問題的提出 出讓定價(jià) ? 假設(shè)出讓 A、 B、 C設(shè)備所得利潤(rùn)分別為 y y y3 ? 原本用于生產(chǎn)甲產(chǎn)品的設(shè)備臺(tái)時(shí)，如若出讓，不應(yīng)低于自行生產(chǎn)帶來的利潤(rùn)，否則寧愿自己生產(chǎn)。 ? 對(duì)偶變量的值 yi*表示第 i種資源的邊際價(jià)值 ， 稱為 影子價(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 單臺(tái)利潤(rùn) 6 5 例：某企業(yè)利用材料和設(shè)備生產(chǎn)甲乙產(chǎn)品，其工藝消耗系數(shù)和單臺(tái)產(chǎn)品的獲利能力如下表所示： 問如何安排甲、乙兩產(chǎn)品的產(chǎn)量，使利潤(rùn)為最大。 不考慮整數(shù)約束則是一個(gè) LP問題 ,稱為原整數(shù)規(guī)劃的松弛問題 對(duì)于例 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)解。 ???????????????????????????????????????????皆為整數(shù)54321543215545435432432132121154321,0,35813119810..m i nxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxZ按規(guī)定，服務(wù)員連續(xù)工作 8小時(shí)(4個(gè)時(shí)段 )為一班。倉(cāng)庫(kù)選址決策引入 01變量 wj ： 87 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 七、設(shè)施選址問題 ? 供應(yīng)能力平衡約束： ? 市場(chǎng)需求平衡約束： ? 倉(cāng)儲(chǔ)能力限制約束： ? 分銷中心不存留產(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