1、線性規劃線性規劃(xin xn u hu)數學模型數學模型第一頁，共48頁。第1頁/共48頁第二頁，共48頁。第2頁/共48頁第三頁，共48頁。第3頁/共48頁第四頁，共48頁。第4頁/共48頁第五頁，共48頁。第5頁/共48頁第六頁，共48頁。 某化工廠要用三種原料某化工廠要用三種原料 A，B，C 混合配制三種不同規混合配制三種不同規格格(gug)的產品的產品 X，Y，Z。有關數據如下：。有關數據如下： 產品產品規規 格格單價單價(元元/kg)X原料原料D不少于不少于50%原料原料P不超過不超過25%50Y原料原料D不少于不少于25%原料原料P不超過不超過50%35Z不不 限限25原料原料最

2、大供量最大供量(kg/天天)單價單價(元元/kg)A100B100C60應如合配制，才能使利潤應如合配制，才能使利潤(lrn)達到最大？達到最大？表表2-3表表2-4第6頁/共48頁第七頁，共48頁。一、決策(juc)變量 設以 xij 表示每天生產的第i 種產品中所含第j 種原料的數量(kg，右表)。ji A B CXYZx11 x12 x13x21 x22 x23x31 x32 x33二、約束條件二、約束條件 規格規格(gug)約束約束(據表據表2-3)x11+ x12 + x13x11 0.50 x11+ x12 + x13x12 0.25x11+ x12 + x13x21 0.25x1

3、1+ x12 + x13x22 0.50第7頁/共48頁第八頁，共48頁。改寫改寫(gixi)成成 - - x11 + x12 + x13 0 - - x11+ 3 x12 - -x13 0- -3 x21 +x22 + x23 0 x21 +x22 - - x23 0 資源資源(zyun)約束約束(據表據表2-4)x11+ x21 + x31 100 x12+ x22 + x32 100 x13+ x23 + x33 60第8頁/共48頁第九頁，共48頁。三、目標三、目標(mbio)函數函數 總產值總產值(據據表表2-3)產品產品(chnpn)X的產值的產值: 50(x11+ x12 + x

4、13 )產品產品(chnpn)Y的產值的產值: 35(x21+ x22 + x23 )產品產品(chnpn)Z的產值的產值: 25(x31+ x32 + x33 )以上三項之和即以上三項之和即總產值總產值。 總成本總成本(據據表表2-4)原料原料A的成本的成本: (x11+ x21 + x31 )原料原料B的成本的成本: (x12+ x22 + x32 )原料原料C的成本的成本: (x13+ x23 + x33 )以上三項之和即以上三項之和即總成本總成本。第9頁/共48頁第十頁，共48頁。 目標函數目標函數(hnsh)為：為： 總利潤總利潤 = 總產值總產值 - 總成本總成本max =- -1

5、5x11+25x12+15x13- -30 x21+10 x22- -40 x31- -10 x33 該問題該問題(wnt)(wnt)的數學模型為的數學模型為: :s.t. - - x11 +x12 + x13 0 - - x11+3x12 - - x13 0 - -3x21+x22 +x23 0 x21+x22 - - x23 0 x11 +x21 +x31 100 x12 +x22 +x32 100 x13 +x23 +x33 60 xij 0， i = 1, 2, 3； j = 1, 2, 3第10頁/共48頁第十一頁，共48頁。第11頁/共48頁第十二頁，共48頁。 成分含量成分含量(

6、%)(%) 原原 料料 化學成分化學成分 甲甲 乙乙 產品成分產品成分 最低含量最低含量(%)(%)A B C 12 3 2 3 3 15 4 2 5 成本（元成本（元/ /千克）千克） 3 2 min = 3x1+2x2 12 x1 +3x2 4 2 x1 +3x2 2s.t. 3 x1+15x2 5 x1 +x2 = 1 x1 , , x2 0配料配料(pi lio)(pi lio)平衡條件平衡條件第12頁/共48頁第十三頁，共48頁。第13頁/共48頁第十四頁，共48頁。練習：練習： 某晝夜服務的公交線路每天各時間段內某晝夜服務的公交線路每天各時間段內所需司機和乘務人員人數所需司機和乘務

7、人員人數(rn sh)如下表所示：如下表所示：班次班次時間時間所需人員所需人員16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030設司機和乘務人員分別在各時間段開始時上班，并連續工設司機和乘務人員分別在各時間段開始時上班，并連續工作作8小時，問該公交線路應怎樣安排司機和乘務人員，即能小時，問該公交線路應怎樣安排司機和乘務人員，即能滿足工作需要滿足工作需要(xyo)，又使配備司機和乘務人員的人數減，又使配備司機和乘務人員的人數減少少?第14頁/共48頁第十五頁，共48頁。 0,302050607060

8、.min654321655443322161654321xxxxxxxxxxxxxxxxxxtsxxxxxx此問題最優解：此問題最優解：x150， x220， x350， x40， x520， x610，一共一共(ygng)需要司機和乘務員需要司機和乘務員150人。人。第15頁/共48頁第十六頁，共48頁。第16頁/共48頁第十七頁，共48頁。 練習： 制造某種機床，需要 A,B,C三種軸件，其規格與數量如表所示，各類軸件都用5.5米長的同一種圓鋼下料。 若計劃(jhu)生產100臺機床，最少需要用多少根圓鋼？第17頁/共48頁第十八頁，共48頁。軸類軸類 規格：長度（米）規格：長度（米） 每

9、臺機床所需軸件數每臺機床所需軸件數 A 3.1 1 B 2.1 2 C 4 余料余料 找出全部找出全部(qunb)省料截法省料截法一根圓鋼所截各類軸件數一根圓鋼所截各類軸件數 截法截法軸類軸類 軸軸 件件 需要量需要量 A(3.1) 100 B(2.1) 200 C(1.2) 400 余料余料(米米) 234511100.310200210.1 0 0 1 0 2 4 1 0.7第18頁/共48頁第十九頁，共48頁。min z = x1 + x2 + x3 + x4 + x5s.t.x1 +x2 100 x1 +2x3 +x4 200 2x2 +x3 +2x4 +4x5 400 x1， x2

10、， x3， x4， x5 0則該問題則該問題(wnt)的數學模型的數學模型為為:設第設第 j 種截法下料種截法下料 xj 根。根。第19頁/共48頁第二十頁，共48頁。例：現有一批某種型號的圓鋼例：現有一批某種型號的圓鋼(yun n)長長8米，需要截米，需要截取取2.5米長的毛坯米長的毛坯100根，長根，長1.3米的毛坯米的毛坯200根。問如何才根。問如何才能既滿足需要，又能使總的用料最少？能既滿足需要，又能使總的用料最少？解：為了找到一個省料的套裁方案，必須先設計出較好的幾個下料方案。解：為了找到一個省料的套裁方案，必須先設計出較好的幾個下料方案。其次其次(qc)要求這些方案的總體能裁下所有

11、各種規格的圓鋼，以滿足對各要求這些方案的總體能裁下所有各種規格的圓鋼，以滿足對各種不同規格圓鋼的需要并達到省料的目的，為此可以設計出種不同規格圓鋼的需要并達到省料的目的，為此可以設計出4種下料方案種下料方案以供套裁用。以供套裁用。2.5m32101.3m0246料頭料頭00.40.30.2第20頁/共48頁第二十一頁，共48頁。 )4.3.2.1(020064210023min4323214321jxxxxxxxxxxxZj設按方案設按方案(fng n)、下料的原材料根數分別為下料的原材料根數分別為xj (j=1，2,3,4)，可列出下面的數學模型：，可列出下面的數學模型：第21頁/共48頁第

12、二十二頁，共48頁。第22頁/共48頁第二十三頁，共48頁。例例 某廠擬生產甲、乙兩種產品某廠擬生產甲、乙兩種產品(chnpn)(chnpn)，每件利潤分，每件利潤分別為別為3 3、5 5百元。百元。甲、乙產品甲、乙產品(chnpn)(chnpn)的部件各自在的部件各自在A A、B B兩個車間分別生產，兩個車間分別生產，每件甲、每件甲、乙產品乙產品(chnpn)(chnpn)的部件分別需要的部件分別需要A A、B B車間的生產能力車間的生產能力1 1、2 2工工時。兩件時。兩件產品產品(chnpn)(chnpn)的部件最后都要在的部件最后都要在C C車間裝配，裝配每件甲、車間裝配，裝配每件甲、

13、乙產品乙產品(chnpn)(chnpn)分別分別需要需要3 3、4 4工時，三車間每天可用于生產這兩種產品工時，三車間每天可用于生產這兩種產品(chnpn)(chnpn)的工時分別的工時分別為為8 8、1212、3636，問應如何安排生產這兩種產品，問應如何安排生產這兩種產品(chnpn)(chnpn)才能才能獲利最多？獲利最多？第23頁/共48頁第二十四頁，共48頁。 x1 x2決策決策(juc)變變量量 = 3x1 +5x20目標目標(mbio)函數函數x1 8 2x2 12 3x1 + 4x2 36 函數約束函數約束 x1 ， x2 0 非負性約束非負性約束甲甲 乙乙1030 2 4 8

14、 12 36A B C車間車間產品產品單耗（工時單耗（工時/ /件）件）最大生產能力最大生產能力（工時（工時/ /天）天）單位利潤單位利潤（百元（百元/ /件）件） 3 5第24頁/共48頁第二十五頁，共48頁。練習：某企業計劃生產練習：某企業計劃生產(shngchn)甲、乙兩種產品。這些甲、乙兩種產品。這些產品分別要在產品分別要在A、B、C、D、四種不同的設備上加工。按工、四種不同的設備上加工。按工藝資料規定，單件產品在不同設備上加工所需要的臺時如藝資料規定，單件產品在不同設備上加工所需要的臺時如下表所示，企業決策者應如何安排生產下表所示，企業決策者應如何安排生產(shngchn)計劃，計劃

15、，使企業總的利潤最大？使企業總的利潤最大？ 設設 備備產產 品品 A B C D利潤（元）利潤（元） 甲甲 2 1 4 0 2 乙乙 2 2 0 4 3 有有 效效 臺臺 時時 12 8 16 12第25頁/共48頁第二十六頁，共48頁。第26頁/共48頁第二十七頁，共48頁。 某企業擬用m種資源生產n種產品(chnpn)，已知第i種資源的數量為bi,其單價為pi,每生產一個單位第j種產品(chnpn)所提供的產值為vj, 所消耗的第i種資源的數量為aij。第j種產品(chnpn)的合同與指令性計劃的產量指標為ej, 最高需求量為dj。 該企業應如何擬定生產計劃？第27頁/共48頁第二十八頁，

16、共48頁。 一、決策變量 設xj為第j種產品的計劃產量 二、約束條件 指標約束 xj ej , j = 1,2, ,n 需求約束 xj dj , j = 1,2, ,n 資源(zyun)約束 三、目標函數 總產值 j=1naijxj bi, , i = 1, ,2, , ,m j=1nm i=1z2=pi(aij xj) 總成本總成本z1=vj xj nj=1第28頁/共48頁第二十九頁，共48頁。 i=1=vj xj -pi(aij xj)j=1nmj=1n=(vj- pi aij ) xjj=1n i=1m令令 cj = vj- pi aij i=1mxj ej , , j =1, ,2,

17、 , , ,nxj djaijxj bi, , i =1, ,2, , ,m j=1nmax z=cj xjj=1n s.t.則則 總利潤總利潤(lrn)(lrn) z = z1 -z2第29頁/共48頁第三十頁，共48頁。某廠生產某廠生產(shngchn)、三種產品，三種產品，都分別經都分別經A、B兩道工序加工。設兩道工序加工。設A工序可分別在設工序可分別在設備備A1和和A2上完成，有上完成，有B1、B2、B3三種設備可用于三種設備可用于完成完成B工序。已知產品工序。已知產品可在可在A、B任何一種設備上任何一種設備上加工；產品加工；產品可在任何規格的可在任何規格的A設備上加工，但完設備上加工

18、，但完成成B工序時，只能在工序時，只能在B1設備上加工；產品設備上加工；產品只能在只能在A2與與B2設備上加工。加工單位產品所需工序時間設備上加工。加工單位產品所需工序時間及其他各項數據如下表，試安排最優生產及其他各項數據如下表，試安排最優生產(shngchn)計劃，使該廠獲利最大。計劃，使該廠獲利最大。第30頁/共48頁第三十一頁，共48頁。設備設備產品產品設備有效設備有效臺時臺時設備加工費設備加工費（單位小時）（單位小時）27910 000321B168124000250B247000783B37114000200原料費（每件）原料費（每件）0.250.350.5

19、售價（每件）售價（每件）1.252.002.8第31頁/共48頁第三十二頁，共48頁。）（上加工的數量相等）上加工的數量相等），在工序在工序（產品（產品上加工的數量相等）上加工的數量相等），在工序在工序（產品（產品上加工的數量相等）上加工的數量相等），在工序在工序（產品（產品設備設備設備設備）（設備（設備）（設備（設備設備設備3 , 2 , 1; 2 , 1; 3 , 2 , 10BAIIIBAIIBAI)3B(40007)2B(70001141B4000862A100001297)1A(60001053223122212122111231221211121111233221222211213

20、12212112211111 kjixxxxxxxxxxxxxxxxxxxxxijk第32頁/共48頁第三十三頁，共48頁。 5131)()(ii該該設設備備實實際際使使用用臺臺時時每每臺臺時時的的設設備備費費用用該該產產品品件件數數銷銷售售單單價價原原料料單單價價利利潤潤帶入數據整理帶入數據整理(zhngl)得到：得到：12332212222112131221221111211135. 023. 1448. 05 . 0375. 0915. 136. 115. 1775. 075. 0maxxxxxxxxxxx 第33頁/共48頁第三十四頁，共48頁。 ）（3,2,1;2,1;3,2,104

21、000770001144000861000012976000105.35.023.1448.05.0375.0915.136.115.1775.075.0max322312221212211123122121112111123322122221121312212112211111123322122221121312212211112111kjixxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxxijk第34頁/共48頁第三十五頁，共48頁。 有有n種食品種食品, 每種食品中含有每種食品中含有m種營養成分。食品用種營養成分。食品用 j = 1,2, ,n表示，養分用表示，養分用 i

22、 = 1,2, ,m表示。已知第表示。已知第 j 種種食品單價為食品單價為 cj, 每天最大供量為每天最大供量為 dj; 而每單位而每單位(dnwi)第第 j種食品所含種食品所含第第 i 種養分的數量為種養分的數量為 aij。 假定某種生物每天對第假定某種生物每天對第 i 種養分種養分的的需求量至少為需求量至少為 bi, 而每天進食數量限定在而每天進食數量限定在 h1, h2 范圍內。范圍內。 試求該生物的食譜，使總成本為最小。試求該生物的食譜，使總成本為最小。 第35頁/共48頁第三十六頁，共48頁。 設設 xj 為每天提供給該生物為每天提供給該生物(shngw)食用的第食用的第 j 種食品

23、的數量，種食品的數量，則該問題的數學模型為則該問題的數學模型為: s.t. 0 xj dj , , j=1, ,2, , ,nmin z=cj xjj=1nj=1 h1 xj h2nj=1 aij xj bi , , i=1, ,2, , ,m n第36頁/共48頁第三十七頁，共48頁。例：某人每天食用例：某人每天食用(shyng)甲、乙兩種食物（如豬肉、雞蛋），甲、乙兩種食物（如豬肉、雞蛋），其資料如下：問兩種食物各食用其資料如下：問兩種食物各食用(shyng)多少，才能既滿足需多少，才能既滿足需要、又使總費用最??？要、又使總費用最??？ 2 1.5原料單價1.007.5010.00 0.1

24、0.15 1.7 0.75 1.10 1.30A1A2A3 最 低需要量 甲 乙含量 食物成分第37頁/共48頁第三十八頁，共48頁。 0,00.1030.110.150.775.070.100.115.010.05.12min2121212121xxxxxxxxxxZ第38頁/共48頁第三十九頁，共48頁。 某廠制造某種部件，由2個B1零件, 3個B2零件配套(pi to)組裝而成。該廠有A1, A2, A3三種機床可加工這兩種零件，每種機床的臺數，以及每臺機床的生產率如下表所示。 求產量最大的生產方案。第39頁/共48頁第四十頁，共48頁。 一、決策變量一、決策變量 設以設以xij表示每臺

25、表示每臺Ai (i=1, 2, 3)機床每個工作日機床每個工作日加工加工Bj( j = 1, 2 )零件零件(ln jin)的時間的時間(單位單位:工作日工作日)； z為為B1, B2零件零件(ln jin)按按 2: 3 的比例配套的比例配套的數量的數量(套套/日日)。機床機床種類種類機床機床臺數臺數機床生產率機床生產率( 件件/日日 )零件零件B1零件零件B2A13A22A34x11x12x21x22x31x32第40頁/共48頁第四十一頁，共48頁。 二、約束條件二、約束條件 工時工時(gngsh)約束約束 配套配套(pi to)約束約束機床機床種類種類生產率生產率( 件件/日日 )零件零件B1零件零件B2A1A2A3x11x12x21x22x3