線性規(guī)劃數(shù)學(xué)模型學(xué)習(xí)教案

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

2、大供量最大供量(kg/天天)單價單價(元元/kg)A100B100C60應(yīng)如合配制，才能使利潤應(yīng)如合配制，才能使利潤(lrn)達(dá)到最大？達(dá)到最大？表表2-3表表2-4第6頁/共48頁第七頁，共48頁。一、決策(juc)變量 設(shè)以 xij 表示每天生產(chǎn)的第i 種產(chǎn)品中所含第j 種原料的數(shù)量(kg，右表)。ji A B CXYZx11 x12 x13x21 x22 x23x31 x32 x33二、約束條件二、約束條件 規(guī)格規(guī)格(gug)約束約束(據(jù)表據(jù)表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)約束約束(據(jù)表據(jù)表2-4)x11+ x21 + x31 100 x12+ x22 + x32 100 x13+ x23 + x33 60第8頁/共48頁第九頁，共48頁。三、目標(biāo)三、目標(biāo)(mbio)函數(shù)函數(shù) 總產(chǎn)值總產(chǎn)值(據(jù)據(jù)表表2-3)產(chǎn)品產(chǎn)品(chnpn)X的產(chǎn)值的產(chǎn)值: 50(x11+ x12 + x

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

5、5x11+25x12+15x13- -30 x21+10 x22- -40 x31- -10 x33 該問題該問題(wnt)(wnt)的數(shù)學(xué)模型為的數(shù)學(xué)模型為: :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、%)(%) 原原 料料 化學(xué)成分化學(xué)成分 甲甲 乙乙 產(chǎn)品成分產(chǎn)品成分 最低含量最低含量(%)(%)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頁。練習(xí)：練習(xí)： 某晝夜服務(wù)的公交線路每天各時間段內(nèi)某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員人數(shù)所需司機和乘務(wù)

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

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

9、臺機床所需軸件數(shù)每臺機床所需軸件數(shù) A 3.1 1 B 2.1 2 C 4 余料余料 找出全部找出全部(qunb)省料截法省料截法一根圓鋼所截各類軸件數(shù)一根圓鋼所截各類軸件數(shù) 截法截法軸類軸類 軸軸 件件 需要量需要量 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)的數(shù)學(xué)模型的數(shù)學(xué)模型為為:設(shè)第設(shè)第 j 種截法下料種截法下料 xj 根。根。第19頁/共48頁第二十頁，共48頁。例：現(xiàn)有一批某種型號的圓鋼例：現(xiàn)有一批某種型號的圓鋼(yun n)長長8米，需要截米，需要截取取2.5米長的毛坯米長的毛坯100根，長根，長1.3米的毛坯米的毛坯200根。問如何才根。問如何才能既滿足需要，又能使總的用料最少？能既滿足需要，又能使總的用料最少？解：為了找到一個省料的套裁方案，必須先設(shè)計出較好的幾個下料方案。解：為了找到一個省料的套裁方案，必須先設(shè)計出較好的幾個下料方案。其次其次(qc)要求這些方案的總體能裁下所有

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

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

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

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

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

16、共48頁。 一、決策變量 設(shè)xj為第j種產(chǎn)品的計劃產(chǎn)量 二、約束條件 指標(biāo)約束 xj ej , j = 1,2, ,n 需求約束 xj dj , j = 1,2, ,n 資源(zyun)約束 三、目標(biāo)函數(shù) 總產(chǎn)值 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頁。某廠生產(chǎn)某廠生產(chǎn)(shngchn)、三種產(chǎn)品，三種產(chǎn)品，都分別經(jīng)都分別經(jīng)A、B兩道工序加工。設(shè)兩道工序加工。設(shè)A工序可分別在設(shè)工序可分別在設(shè)備備A1和和A2上完成，有上完成，有B1、B2、B3三種設(shè)備可用于三種設(shè)備可用于完成完成B工序。已知產(chǎn)品工序。已知產(chǎn)品可在可在A、B任何一種設(shè)備上任何一種設(shè)備上加工；產(chǎn)品加工；產(chǎn)品可在任何規(guī)格的可在任何規(guī)格的A設(shè)備上加工，但完設(shè)備上加工

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

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

20、12212112211111 kjixxxxxxxxxxxxxxxxxxxxxijk第32頁/共48頁第三十三頁，共48頁。 5131)()(ii該該設(shè)設(shè)備備實實際際使使用用臺臺時時每每臺臺時時的的設(shè)設(shè)備備費費用用該該產(chǎn)產(chǎn)品品件件數(shù)數(shù)銷銷售售單單價價原原料料單單價價利利潤潤帶入數(shù)據(jù)整理帶入數(shù)據(jù)整理(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種營養(yǎng)成分。食品用種營養(yǎng)成分。食品用 j = 1,2, ,n表示，養(yǎng)分用表示，養(yǎng)分用 i

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

23、的數(shù)量，種食品的數(shù)量，則該問題的數(shù)學(xué)模型為則該問題的數(shù)學(xué)模型為: 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三種機床可加工這兩種零件，每種機床的臺數(shù)，以及每臺機床的生產(chǎn)率如下表所示。 求產(chǎn)量最大的生產(chǎn)方案。第39頁/共48頁第四十頁，共48頁。 一、決策變量一、決策變量 設(shè)以設(shè)以xij表示每臺

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