【正文】 第四節(jié) 線性規(guī)劃靈敏度分析 二、右端常量的變動分析 ? 參數(shù) bi的變化范圍 第 r個約束的右端項為 br，增量 ?br，其它數(shù)據(jù)不變。選址規(guī)劃在于二者的實際取值。 在分銷渠道中，擬定在 2個地點中選址設(shè)立分銷中心，執(zhí)行產(chǎn)品的轉(zhuǎn)運任務(wù)。 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è)備 H： 1 40x ?2 803 40x ?產(chǎn)品甲： 產(chǎn)品乙： 產(chǎn)品丙： ? 市場需求約束 ? 設(shè)備能力約束 54 OR:SM 第二節(jié) 線性規(guī)劃的適用層次 計劃鏈的層次 粗能力計劃 定單 可行 不可行 CRP 主生產(chǎn)計劃 MPS 物料需求計劃 MRP 能力需求計劃 車間作業(yè)計劃 銷售計劃 可行否 作業(yè)統(tǒng)計與控制 物料清單 庫存管理 外購計劃 供應(yīng)商 成品、在制品信息 生產(chǎn)計劃大綱 預(yù)測 當(dāng)前條件 經(jīng)營計劃 ? 產(chǎn)值計劃 或 利潤計劃 ? 絕對數(shù)量 或 增長幅度 ? 期限 :年度 單位 :萬元 ? 大類產(chǎn)品銷售收入 或 臺套 ? 產(chǎn)品品種 和 數(shù)量 如何確定 ? 期限 :年度 單位 :萬臺 ? 具體產(chǎn)品在具體 時段的出產(chǎn)計劃 ? 合同訂單和預(yù)測 轉(zhuǎn)換為生產(chǎn)任務(wù) ? 將產(chǎn)品出產(chǎn)計劃轉(zhuǎn)換成物料需求表 ? 大類產(chǎn)品年度生產(chǎn)計劃 ? 確定產(chǎn)品的品種 和 數(shù)量 ? 期限 :年度 單位 :萬臺 55 OR:SM 第三節(jié) 線性規(guī)劃的典型案例 ? 配送中心選擇 例： 某企業(yè)存在兩個供貨源（產(chǎn)地），已知原有供貨源每月的供貨能力是 5萬臺產(chǎn)品，新增供貨源的生產(chǎn)能力可以滿足產(chǎn)品的需求，且兩個貨源的價格相同。 ? 總收入 =173x1+233x2+170x3， 原料成本 =65x1+95x2+65x3，營運費用 =11000， 則目標函數(shù)為 maxZ= 108x1+138x2+105x311000 ? 崗位工資制薪酬體系下，工作時間也不會完全受每天 8小時工作時間約束，但有產(chǎn)品市場需求約束，如下： 產(chǎn)品甲： 產(chǎn)品乙： 產(chǎn)品丙： 非負性約束 1 40?2 80x3 40?1 2 3, , 0x x x ?? 經(jīng) Lindo軟件求解，得到最優(yōu)解為 Z=8560,x1=40,x2=80,x3=40。 50 OR:SM 第 2 章 線性規(guī)劃討論 Sub title 內(nèi)容提要 51 OR:SM ? 計件工資體系，目標是企業(yè)利潤最大化： 第一節(jié) 目標函數(shù)的描述技巧 一、計件工資 1 2 3m a x 66 89 70Z x x x? ? ?產(chǎn)品甲： 產(chǎn)品乙： 產(chǎn)品丙： 非負性約束 1 40x ?2 803 40x ?1 2 3, , 0x x x ?? 計件工資制薪酬體系下，工作時間不會完全受每天 8小時工作時間約束，但有產(chǎn)品市場需求約束，如下： ? 經(jīng) Lindo軟件求解，得到最優(yōu)解為 Z=12560，產(chǎn)品甲 x1=40，產(chǎn)品乙 x2=80，產(chǎn)品丙 x3=40。 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 檢驗數(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。 46 OR:SM 二、線性規(guī)劃之解的概念 第二節(jié) 線性規(guī)劃的一般模型 線性規(guī)劃解題思路 ? 先找到一個初始基可行解，也就是找到一個初始可行基，想辦法判斷這個基可行解是不是最優(yōu)解。 定理 3. 若可行域有界，線性規(guī)劃的目標函數(shù)一定可以在可行域的頂點上達到最優(yōu)。 非 可 行 解 可 行 解 基 解 基 可 行 解 45 OR:SM 二、線性規(guī)劃之解的概念 第二節(jié) 線性規(guī)劃的一般模型 線性規(guī)劃基本原理 定理 1. 若線性規(guī)劃問題存在可行域，則其可行域一定是凸集。 最優(yōu)解： 使目標函數(shù)最優(yōu)的可行解，稱為最優(yōu)解 。 可行基 ： 可行解對應(yīng)的基矩陣。 基變量： ? 與基向量 Pj 相對應(yīng)的 m個變量 xj稱為基變量 ? 其余的 n m個變量為非基變量 線性規(guī)劃解之關(guān)系 基解： 令所有非基變量等于零，得出基變量的唯一解 。 ? 矩陣 A中任意 m列的線性無關(guān)子矩陣 B ，稱為一個基。k≥0,xk ≥0) 。 (5)若某決策變量 xk無非負約束，令 xk=x39。 (3)對于 ≤型約束，則在左端加上一個非負松弛變量，使其為等式。=Z，轉(zhuǎn)為求 maxZ39。 38 OR:SM 五、線性規(guī)劃解的可能性 第一節(jié) 線性規(guī)劃的一般模型 唯一最優(yōu)解：只有一個最優(yōu)點 多重最優(yōu)解：無窮多個最優(yōu)解 當(dāng)市場價格下降到 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ī)劃的一般模型 無界解：可行域無界，目標值無限增大 (缺乏必要約束 ) 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目標沖突 利害沖突 目標強沖突 利害弱沖突 41 OR:SM 一、線性規(guī)劃的標準型式 第二節(jié) 線性規(guī)劃的一般模型 標準型表達方式 (1)代數(shù)式 11m a x . 0 njjjnij j ijjZ c xa x bx???????? ????(2)向量式 1m a x .0njjjjZxx??????? ???CXpb(3)矩陣式 m a x0Z ??? ??CXA X = bXA：技術(shù)系數(shù)矩陣，簡稱系數(shù)矩陣； B：可用的資源量，稱資源向量； C：決策變量對目標的貢獻，稱價值向量； X：決策向量。 Z=30 Z=37 Z=15 37 OR:SM 四、線性規(guī)劃的圖解方法 第一節(jié) 線性規(guī)劃的一般模型 線性規(guī)劃解的特性 a b c d ? 由線性不等式組成的可行域是凸多邊形 (凸多邊形是凸集 ) ?凸集定義：集合內(nèi)部任意兩點連線上的點都屬于這個集合 ? 可行域有有限個頂點。 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ū)域。 （ 5） 確定性假定 ? 所有參數(shù)都是確定的 ， 不包含隨機因素 。 ? 目標函數(shù)值是決策變量對目標函數(shù)貢獻的總和 。 （ 2） 同比例假定 ? 決策變量變化引起目標函數(shù)和約束方程的改變量比例 。 ? 決策變量 ： 取 45%和 92%的硫酸分別為 x1 和 x2 噸 ? 約束條件 ： ? 求解二元一次方程組得解 ????????1002121xxxx? 非負約束 ： x1 ≥0， x2 ≥0 32 OR:SM 第一節(jié) 線性規(guī)劃的一般模型 若有 5種不同濃度的硫酸可選 (30%,45%,73%,85%,92%)會如何呢？ ??? ?????? ????? 1005432154321xxxxxxxxxx? 取這 5種硫酸分別為 x x x x x5 ，有 ? 有多少種配比方案？ ? 何為最好？ 若 5種硫酸價格分別為 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ù) 。為發(fā)揮集團優(yōu)勢，公司要統(tǒng)一籌劃運銷問題，求運費最小的調(diào)運方案。 ? 設(shè)備 A的約束條件表達為 2 x1 ≤16 ? 同理 ， 設(shè)備 B的加工能力約束條件表達為 2x2 ≤10 ? 設(shè)備 C的裝配能力也有限 ， 其約束條件為 3x1+ 4x2 ≤32 (3)目標函數(shù)： 目標是企業(yè)利潤最大化 max Z= 3x1 +5x2 (4)非負約束： 甲乙產(chǎn)品的產(chǎn)量為非負 x1 ≥0， x2 ≥0 12121212m a x 3 52 162 10 .3 4 32,0Z x xxxxxxx???????????? ??綜上的 LP模型： 29 OR:SM 二、線性規(guī)劃模型的舉例 第一節(jié) 線性規(guī)劃的一般模型 物資運輸問題 例： 某產(chǎn)品商有三個供貨源 A A A3，其經(jīng)銷商有 4個（需求市場） B B B B4。 產(chǎn)品 設(shè)備 工時消耗 甲 乙 工時成本 元 /h 生產(chǎn)能力 h A B C 2 0 0 2 3