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

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