線性規(guī)劃在工商管理中的.ppt

在建立數(shù)學(xué)模型并求解的同時(shí)，要結(jié)合實(shí)際應(yīng)用！,運(yùn)籌學(xué)的實(shí)質(zhì),求解運(yùn)籌學(xué)問題的基本思路,一、建立運(yùn)籌學(xué)問題數(shù)學(xué)模型 （第四章建模） 二、求運(yùn)籌學(xué)問題的解 （第二章、第五章求解） 三、運(yùn)籌學(xué)問題的靈敏度分析 （第六章結(jié)果分析）,例題,某廠生產(chǎn)甲、乙兩種產(chǎn)品，要消耗A、B、C三種資源，已知每生產(chǎn)單位產(chǎn)品甲需要A 、B、C資源分別是3、2、0，生產(chǎn)單位產(chǎn)品乙需要A 、B、C資源分別是2、1、3， 資源A 、B、C的現(xiàn)有數(shù)量分別是65、40、75，甲、乙兩種產(chǎn)品的單位利潤(rùn)分別是1500、2500，問如何安排生產(chǎn)計(jì)劃，使得既能充分利用現(xiàn)有資源又使總利潤(rùn)最大 ？,x2,x1,解： 1確定決策變量： 設(shè)x1表示生產(chǎn)甲產(chǎn)品的數(shù)量；x2表示生產(chǎn)乙產(chǎn)品的數(shù)量 2確定目標(biāo)函數(shù)：工廠的目標(biāo)是總利潤(rùn)最大 z=1500x1+2500x2 3確定約束條件： 3x1+2x265（A資源的限制） 2x1+ x2 40（B資源的限制） 3x2 75（C資源的限制） 4變量取值限制： 一般情況，決策變量只取大于等于0的值（非負(fù)值） x1 0, x2 0,用max表示最大值，s.t.（subject to的簡(jiǎn)寫）表示約束條件， 得到該問題的數(shù)學(xué)模型為： max Z=1500x1+2500x2 3x1+2x2 65 s.t. 2x1+ x2 40 3x2 75 x1, x2 0,目標(biāo)函數(shù),約束條件,決策變量,決策變量 目標(biāo)函數(shù) 約束條件,運(yùn)籌學(xué)數(shù)學(xué)模型三要素：,一、人力資源分配的問題 二、生產(chǎn)計(jì)劃問題 三、套裁下料問題 四、配料問題 五、運(yùn)輸問題 六、投資問題,第四章 線性規(guī)劃在工商管理中的應(yīng)用,一、人力資源分配的問題,例1、某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員人數(shù)如表所示，設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段開始時(shí)上班，并連續(xù)工作八小時(shí)，問該公交線路應(yīng)怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又使配備司機(jī)和乘務(wù)人員的人數(shù)最少？,.解：設(shè)x i表示在第i個(gè)時(shí)期初開始工作的司機(jī)和乘務(wù)人員人數(shù)(i=1,2,6)，z表示所需的總?cè)藬?shù)，則根據(jù)題意，得到原問題的數(shù)學(xué)模型為:,例2、一家中型的百貨商場(chǎng)對(duì)售貨員的需求經(jīng)過統(tǒng)計(jì)分析如表所示，為了保證售貨員充分休息，要求售貨員每周工作五天，休息兩天，并要求休息的兩天是連續(xù)的，問應(yīng)該如何安排售貨員的休息日期，既滿足工作需要，又使配備的售貨員的人數(shù)最少？,解：設(shè)x i表示在星期i開始休息的人數(shù)(i=1,2,7) ，z表示所需的總?cè)藬?shù)，則根據(jù)題意，得到原問題的數(shù)學(xué)模型為:,X1+x2+x3+x4+x528 x2+x3+x4+x5+X615 x3+x4+x5+X6+x724 s.t. x4+x5+ X6+x7+x125 x5+X6+x7+X1+x219 X6+x7+X1+x2+x331 x7+X1+x2+x3+x428 X1,x2,x3,x4,x5,x6,x70,二、生產(chǎn)計(jì)劃問題,例3、某公司面臨一個(gè)是外包協(xié)作還是自行生產(chǎn)的問題。該公司有甲、乙、丙三種產(chǎn)品，這三種產(chǎn)品都要經(jīng)過鑄造、機(jī)械加工和裝配三道工序，甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須由本廠鑄造才能保證質(zhì)量，有關(guān)情況如表所示，公司中可利用的總工時(shí)為：鑄造8000小時(shí)，機(jī)械加工12000小時(shí)和裝配10000小時(shí)。為了獲得最大利潤(rùn)，甲乙丙三種產(chǎn)品各應(yīng)生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄件有多少由本公司鑄造？有多少為外包協(xié)作？,解：設(shè)x1,x2,x3分別表示三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù),x4,x5分別為由外包協(xié)作鑄造再由本公司進(jìn)行機(jī)械加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)，則根據(jù)題意，得到原問題的數(shù)學(xué)模型為:,Maxz=23(x1+x4)+18(x2+x5)+16x3-3x1-5x2-4x3-5x4-6x5 -2(x1+x4)-(x2+x5)-3x3-3(x1+x4)-2(x2+x5)-2x3 5X1+10x2+7x38000 s.t. 6(x1+x4)+4(x2+x5)+8x3 12000 3(x1+x4)+2(x2+X5)+2x3 10000 X1,x2,x3,x4,x50,Maxz=15x1+10x2+7x3+13x4+9x5 5X1+10x2+7x38000 s.t. 6x1+ 4x2+8x3+6x4 +4x5 12000 3x1+2x2+2x3+3X4+2x5 10000 X1,x2,x3,x4,x50,整理得：,例4、永久機(jī)械廠生產(chǎn)甲、乙、丙三種產(chǎn)品，每種產(chǎn)品均要經(jīng)過A、B兩道加工工序。設(shè)該廠有兩種規(guī)格的設(shè)備能完成工序A，它們以A1、A2表示；有三種規(guī)格的設(shè)備能完成工序B，它們以B1、B2、B3表示。產(chǎn)品甲可在工序A和B的任何規(guī)格的設(shè)備上加工；產(chǎn)品乙可在工序A的任何一種規(guī)格的設(shè)備上加工，但完成工序B時(shí)，只能在設(shè)備B1上加工；產(chǎn)品丙只能在設(shè)備A2與B2上加工。已知在各種設(shè)備上加工的單件工時(shí)、各種設(shè)備的有效臺(tái)時(shí)如表所示。另外已知產(chǎn)品甲、乙、丙的原料單價(jià)分別為0.25元/件、0.35元/件和0.5元/件，銷售單價(jià)分別為1.25元/件、2元/件和2.8元/件，要求制定最優(yōu)的產(chǎn)品加工方案，使該廠利潤(rùn)最大。,解：根據(jù)題意，生產(chǎn)三種產(chǎn)品分別有如下幾種方案： 甲：（A1,B1) , (A1,B2), (A1,B3), (A2,B1), (A2,B2), (A2,B3)六種方案 乙：（A1，B1），（A2，B1）兩種方案 丙：（A2，B2）一種方案 令xi表示采用第i種方案進(jìn)行加工的某種產(chǎn)品的數(shù)量(i=1,2,9),x1 x2 x3 x4 x5 x6,x7 x8,x9,Maxz= (1.25-0.25)(x1+x2+x3+x4+x5+x6)+(2-0.35)(x7+x8)+(2.8-0.5)x9 5(x1+x2+x3)+10x76000 7(x4+x5+x6)+9x8+12x9 10000 s.t. 6(x1+x4)+8x7 +8x8 4000 4(x2+x5)+11x97000 7(x3+x6) 4000 xi0 (i=1,2,9),整理得： Maxz= x1+x2+x3+x4+x5+x6 +1.35x7+1.65x8+2.3x9 5x1+5x2+5x3 +10x7 6000 7x4+7x5+7x6 +9x8+12x9 10000 s.t. 6x1 +6x4 +8x7 +8x8 4000 4x2 +4x5 +11x97000 7x3 +7x6 4000 xi0 (i=1,2,9),例5、永久機(jī)械廠生產(chǎn)甲、乙、丙三種產(chǎn)品，每種產(chǎn)品均要經(jīng)過A、B兩道加工工序。設(shè)該廠有兩種規(guī)格的設(shè)備能完成工序A，它們以A1、A2表示；有三種規(guī)格的設(shè)備能完成工序B，它們以B1、B2、B3表示。產(chǎn)品甲可在工序A和B的任何規(guī)格的設(shè)備上加工；產(chǎn)品乙可在工序A的任何一種規(guī)格的設(shè)備上加工，但完成工序B時(shí)，只能在設(shè)備B1上加工；產(chǎn)品丙只能在設(shè)備A2與B2上加工。已知在各種設(shè)備上加工的單件工時(shí)、各種設(shè)備的有效臺(tái)時(shí)以及滿負(fù)荷操作時(shí)的設(shè)備費(fèi)用如表所示。另外已知產(chǎn)品甲、乙、丙的原料單價(jià)分別為0.25元/件、0.35元/件和0.5元/件，銷售單價(jià)分別為1.25元/件、2元/件和2.8元/件，要求制定最優(yōu)的產(chǎn)品加工方案，使該廠利潤(rùn)最大。,解：根據(jù)題意，生產(chǎn)三種產(chǎn)品分別有如下幾種方案： 甲：（A1,B1) , (A1,B2), (A1,B3), (A2,B1), (A2,B2), (A2,B3)六種方案 乙：（A1,B1），（A2，B1）兩種方案 丙：（A2,B2）一種方案 xi表示采用第i種方案進(jìn)行加工的某種產(chǎn)品的數(shù)量(i=1,2,9),x1 x2 x3 x4 x5 x6,x7 x8,x9,Maxz= x1+x2+x3+x4+x5+x6 +1.35x7+1.65x8+2.3x9 -300/6000(5x1+5x2+5x3 +10x7 ) -321/10000(7x4+7x5+7x6 +9x8+12x9 ) -250/4000(6x1+6x4+8x7 ) -783/7000(4x2 +4x5 +11x9 ) -200/4000(7x3 +7x6),約束條件不變,思考！,決策變量的另一種表示方法： 根據(jù)題意，生產(chǎn)三種產(chǎn)品分別有如下幾種方案： 甲：（A1，B1) , (A1,B2), (A1,B3), (A2,B1), (A2,B2), (A2,B3)六種方案 乙：（A1，B1），（A2，B1）兩種方案 丙：（A2，B2）一種方案 設(shè)i=1,2,3分別表示甲、乙、丙三種產(chǎn)品； j=1,2,.分別表示第j個(gè)方案； xij表示第i種產(chǎn)品采用第j個(gè)方案進(jìn)行加工的產(chǎn)品的數(shù)量,x11 x12 x13 x14 x15 x16,x21 x22,x31,三、套裁下料問題,例6、 某工廠要做100套鋼架，每套鋼架需要長(zhǎng)度分別為2.9m，2.1m和1.5m的圓鋼各一根。已知原料每根長(zhǎng)7.4m，問應(yīng)該如何下料，可使所用原料最省？,解：做法一：截取法。 每根原材料中各截取一根組成一套，2.9+2.1+1.5=6.5 每根料頭0.9m, 100根90m料頭，浪費(fèi) 做法二：套裁法。,x1 x2 x3 x4 x5,設(shè)xi (i=1,2,5)表示按照方案i下料的原材料的根數(shù)，則該問題的數(shù)學(xué)模型如下：,Minz=x1+x2+x3+x4+x5 x1+2x2+x4100 s.t. 2x3+2x4+x5100 3x1+x2+2x3+3x5100 x1,x2,x3,x4,x5 0,思考,1、約束條件用等于號(hào)如何？ 2、如果問如何下料，可使料頭最少？,四、配料問題,例7、某化工廠根據(jù)一項(xiàng)合同要為用戶生產(chǎn)一種用甲、乙兩種原料混合配制而成的特殊產(chǎn)品. 甲、乙兩種原料都含有A、B、C三種化學(xué)成分，其含量（%）和單位成本以及按合同規(guī)定產(chǎn)品中三種化學(xué)成分的最低含量（%）限制如表所示. 問廠方應(yīng)如何配制該產(chǎn)品，使得總成本達(dá)到最??？,解：(1) 確定決策變量： 設(shè)每單位該產(chǎn)品用x1單位甲原料和x2單位乙原料配制而成. (2) 所滿足的約束條件 對(duì)化學(xué)成分A的要求：12 x1+ 3 x2 4 對(duì)化學(xué)成分B的要求：2 x1 + 3 x2 2 對(duì)化學(xué)成分C的要求：3 x1 + 15 x2 5 配料平衡條件：x1 + x2 = 1 (3) 明確目標(biāo)函數(shù)：成本最小，即求 z = 3x1 + 2x2的最小值 (4)變量取值限制： x1，x2 0,記為 min z = 3x1 + 2x2 s.t. 12x1 + 3x2 4 2x1 + 3x2 2 3x1 + 15x2 5 x1 + x2 = 1 x1，x2 0,例8、某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，產(chǎn)品的規(guī)格要求、產(chǎn)品的單價(jià)、每天能供應(yīng)的原材料數(shù)量及原材料單價(jià)如表所示，該廠應(yīng)如何安排生產(chǎn)，才能使利潤(rùn)最大？,解：xij設(shè)表示第i種產(chǎn)品中原材料j的含量(i,j=1,2,3), 則三種產(chǎn)品的數(shù)量和原材料的數(shù)量分別是：,甲： x11+x12+x13 乙： x21+x22+x23 丙： x31+x32+x33 材料1： x11+x21+x31 材料2： x12+x22+x32 材料3： x13+x23+x33,根據(jù)題意，得到原問題的數(shù)學(xué)模型: Max z=50 (x11+x12+x13)+35 (x21+x22+x23)+25 (x31+x32+x33) -65(x11+x21+x31)-25 (x12+x22+x32)-35 (x13+x23+x33) x1150% (x11+x12+x13) x12 25%(x11+x12+x13) x2125%(x21+x22+x23) s.t. x22 50%(x21+x22+x23) x11+x21+x31100 x12+x22+x32 100 x13+x23+x33 60 xij0 (i,j=1,2,3),例9、汽油混合問題 教科書P49,五、 運(yùn)輸問題,例10、設(shè)某種物資有兩個(gè)產(chǎn)地A1，A2，其產(chǎn)量分別為2000噸、1100噸，另有四個(gè)銷地B1、B2、B3、B4需要該種物資，其需求量分別為1700噸、1100噸、200噸、100噸. 已知每噸運(yùn)費(fèi)如表所示，問如何調(diào)運(yùn)，才能使總運(yùn)費(fèi)最??？,解：設(shè)xij表示由產(chǎn)地Ai運(yùn)往銷地Bj（i = 1,2；j = 1,2,3,4）的運(yùn)量. 由于總產(chǎn)量與總需求量相等（產(chǎn)銷平衡）,所以有約束條件： 對(duì)產(chǎn)地產(chǎn)量的約束 : x11 + x12 + x13 + x14 = 2000 x21 + x22 + x23 + x24 = 1100 對(duì)銷地需求量的約束 : x11 + x21 = 1700 x12 + x13 = 1100 x13 + x23 = 200 x14 + x24 = 100 另外xij是運(yùn)輸量，應(yīng)滿足xij0（i = 1,2；j = 1,2,3,4） 目標(biāo)函數(shù)為總運(yùn)費(fèi)最小: minZ = 21x11 + 25x12 + 7x13 + 15x14 + 51x21 + 51x22 + 37x23 + 15x24,所以運(yùn)輸問題的數(shù)學(xué)模型可記為,min z = 21x11 + 25x12 + 7x13 + 15x14 + 51x21 + 51x22 + 37x23 + 15x24 x11 + x12 + x13 + x14 = 2000 x21 + x22 + x23 + x24 = 1100 x11 + x21 = 1700 s.t. x12 + x22 = 1100 x13 + x23 = 200 x14 + x24 = 100 xij 0（i = 1,2；j = 1,2,3,4）.,六、投資問題,例11、某公司在今后四年內(nèi)考慮以下四個(gè)投資項(xiàng)目選擇問題： 項(xiàng)目甲：第二年初需投資，到第四年年末收回本利180%；