【文章內(nèi)容簡介】 xx???????????? ??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ī)劃的一般模型 標(biāo)準(zhǔn)型表達(dá)方式 (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：決策變量對目標(biāo)的貢獻(xiàn)，稱價值向量； X：決策向量。 42 OR:SM 一、線性規(guī)劃的標(biāo)準(zhǔn)型式 第二節(jié) 線性規(guī)劃的一般模型 標(biāo)準(zhǔn)型轉(zhuǎn)換方法 (1)如果極小化原問題 minZ=CX，則令 Z39。=Z，轉(zhuǎn)為求 maxZ39。=CX (2)若某個 bi0，則以－ 1乘該約束兩端，使之滿足非負(fù)性的要求。 (3)對于 ≤型約束，則在左端加上一個非負(fù)松弛變量，使其為等式。 (4)對于 ≥型約束，則在左端減去一個非負(fù)剩余變量，使其為等式。 (5)若某決策變量 xk無非負(fù)約束，令 xk=x39。kxk ， (x39。k≥0,xk ≥0) 。 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ī)劃的一般模型 基矩陣： 一個非奇異的子矩陣（線性無關(guān)）。 ? 矩陣 A中任意 m列的線性無關(guān)子矩陣 B ，稱為一個基。 ? 組成基 B的列為基向量，用 Pj表示 (j=1,2,…,n ) 。 基變量： ? 與基向量 Pj 相對應(yīng)的 m個變量 xj稱為基變量 ? 其余的 n m個變量為非基變量 線性規(guī)劃解之關(guān)系 基解： 令所有非基變量等于零，得出基變量的唯一解 。 ???????????100010001B? 基變量是 x3, x4, x5 ? 非基變量是 x1, x2 ? 令非基變量 x1=x2=0，得到一個基解 x3=16， x4=10， x5=32 44 OR:SM 二、線性規(guī)劃之解的概念 第二節(jié) 線性規(guī)劃的一般模型 線性規(guī)劃解之關(guān)系 可行解 ： 滿足約束條件 AX=b, X≥0 的解。 可行基 ： 可行解對應(yīng)的基矩陣。 基可行解 ： 滿足非負(fù)性約束的基解稱為基可行解。 最優(yōu)解： 使目標(biāo)函數(shù)最優(yōu)的可行解，稱為最優(yōu)解 。 最優(yōu)基： 最優(yōu)解對應(yīng)的基矩陣，稱為最優(yōu)基。 非 可 行 解 可 行 解 基 解 基 可 行 解 45 OR:SM 二、線性規(guī)劃之解的概念 第二節(jié) 線性規(guī)劃的一般模型 線性規(guī)劃基本原理 定理 1. 若線性規(guī)劃問題存在可行域，則其可行域一定是凸集。 定理 2. 線性規(guī)劃問題的基可行解對應(yīng)可行域的頂點(diǎn)。 定理 3. 若可行域有界，線性規(guī)劃的目標(biāo)函數(shù)一定可以在可行域的頂點(diǎn)上達(dá)到最優(yōu)。 定理 4. 線性規(guī)劃如果有可行解，則一定有基可行解；如果有最優(yōu)解，則一定有基可行解是最優(yōu)解。 46 OR:SM 二、線性規(guī)劃之解的概念 第二節(jié) 線性規(guī)劃的一般模型 線性規(guī)劃解題思路 ? 先找到一個初始基可行解，也就是找到一個初始可行基，想辦法判斷這個基可行解是不是最優(yōu)解。 ? 如果是最優(yōu)解，就得到這個線性規(guī)劃問題的最優(yōu)解； ? 如果判斷出不是最優(yōu)解，就想法由這個可行基按一定規(guī)則變化到下一個可行基，然后再判斷新得到的基可行解是不是最優(yōu)解； ? 如果還不是，再接著進(jìn)行下一個可行基變化，直到得到最優(yōu)解。 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。?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è)管理過程也是如此，把現(xiàn)有方案作為初始方案，找到最急需要改進(jìn)的某個問題和改進(jìn)方向，一次做好某個主要問題的解決與改進(jìn)；一次只解決和改進(jìn)一個問題的難度最??；解決之后，再尋求可以改進(jìn)的其它地方，再次改進(jìn)，不斷地追求完美。 50 OR:SM 第 2 章 線性規(guī)劃討論 Sub title 內(nèi)容提要 51 OR:SM ? 計件工資體系，目標(biāo)是企業(yè)利潤最大化： 第一節(jié) 目標(biāo)函數(shù)的描述技巧 一、計件工資 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 ?? 計件工資制薪酬體系下，工作時間不會完全受每天 8小時工作時間約束，但有產(chǎn)品市場需求約束，如下： ? 經(jīng) Lindo軟件求解，得到最優(yōu)解為 Z=12560，產(chǎn)品甲 x1=40，產(chǎn)品乙 x2=80，產(chǎn)品丙 x3=40。 52 OR:SM 第一節(jié) 目標(biāo)函數(shù)的描述技巧 二、崗位工資 ? 崗位工資制薪酬體系，以計時工資制為基礎(chǔ)，實(shí)行定崗定員。 ? 總收入 =173x1+233x2+170x3， 原料成本 =65x1+95x2+65x3，營運(yùn)費(fèi)用 =11000， 則目標(biāo)函數(shù)為 maxZ= 108x1+138x2+105x311000 ? 崗位工資制薪酬體系下，工作時間也不會完全受每天 8小時工作時間約束，但有產(chǎn)品市場需求約束，如下： 產(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。 53 OR:SM 第一節(jié) 目標(biāo)函數(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。 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)品的需求，且兩個貨源的價格相同。 有三個區(qū)域目標(biāo)市場（銷地或銷售商），各銷地每月的市場需求量為 5萬臺、 10萬臺、 5萬臺。 在分銷渠道中，擬定在 2個地點(diǎn)中選址設(shè)立分銷中心，執(zhí)行產(chǎn)品的轉(zhuǎn)運(yùn)任務(wù)。各地之間的單位運(yùn)輸物流成本（由距離和運(yùn)輸方式?jīng)Q定） 56 OR:SM 第三節(jié) 線性規(guī)劃的典型案例 ? 決策變量：設(shè)從供貨源到分銷中心的運(yùn)輸量為 ，從分銷中心到需求市場的運(yùn)輸量為 。選址規(guī)劃在于二者的實(shí)際取值。 ? 如果 ，則不設(shè)置分銷中心； 反之，則設(shè)置 ,其規(guī)模為 ? 如果 ，則不設(shè)置分銷中心； 反之，則設(shè)置，其規(guī)模為 ? 目標(biāo)函數(shù)：各條路段上的實(shí)際運(yùn)輸量乘以物流運(yùn)輸?shù)膯挝毁M(fèi)用之總和最小，即 ? 存在供應(yīng)能力約束、市場需求約束、配送中轉(zhuǎn)約束，如下： 11 12 21 22 11 12 13 21 22 23m in 2 5 4 2 3 4 5 2 2 3Z x x x x y y y y y y? ? ? ? ? ? ? ? ? ?ijxjky11 21 0x