運(yùn)籌學(xué)線性規(guī)劃引論P(yáng)PT課件

1、1.1 線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型(1) 線性規(guī)劃問(wèn)題例1、生產(chǎn)組織與計(jì)劃問(wèn)題A, B 各生產(chǎn)多少, 可獲最大利潤(rùn)?可用資源煤勞動(dòng)力倉(cāng)庫(kù)A B1 23 2 2單位利潤(rùn)40 50306024第1頁(yè)/共26頁(yè)解: 設(shè)產(chǎn)品A, B產(chǎn)量分別為變量x1， x2根據(jù)題意，兩種產(chǎn)品的生產(chǎn)要受到可用資源的限制，具體講：對(duì)于煤，兩種產(chǎn)品生產(chǎn)消耗量不能超過(guò)30，即： x1 + 2x2 30對(duì)于勞動(dòng)力，兩種產(chǎn)品生產(chǎn)的占用量不超過(guò)60，即： 3x1 + 2x2 60對(duì)于倉(cāng)庫(kù)，B種產(chǎn)品生產(chǎn)量的2倍不能超過(guò)24，即： 2x2 24另外，產(chǎn)品數(shù)不能為負(fù)，即： x1，x2 0第2頁(yè)/共26頁(yè)同時(shí)，我們有

2、一個(gè)追求的目標(biāo)-最大利潤(rùn)，即： Max Z= 40 x1 +50 x2綜合上述討論，在生產(chǎn)資源的消耗以及利潤(rùn)與產(chǎn)品產(chǎn)量成線性關(guān)系的假設(shè)下，把目標(biāo)函數(shù)和約束條件放在一起，可以建立如下的數(shù)學(xué)模型：Max Z= 40 x1 +50 x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0s.t目標(biāo)函數(shù)約束條件類(lèi)似的例子：教材P4-P5，例1第3頁(yè)/共26頁(yè)例2 合理配料問(wèn)題求：最低成本的原料混合方案 原料 A B 每單位成本 1 4 1 0 2 2 6 1 2 5 3 1 7 1 6 4 2 5 3 8 每單位添加劑中維生 12 14 8 素最低含量第4頁(yè)/共26頁(yè)解：設(shè)

3、每單位添加劑中原料j的用量為xj(j =1,2,3,4) 根據(jù)題意：混合配料后， 每單位添加劑中A的含量不得低于12，即 4x1 + 6x2 + x3+2x4 12 每單位添加劑中B的含量不得低于14，即 x1 + x2 +7x3+5x4 14 每單位添加劑中C的含量不得低于8，即 2x2 + x3+3x4 8 另外，原料使用量不能為負(fù)，即： x1，x2 ， x3， x4， 0第5頁(yè)/共26頁(yè)同時(shí)，我們有一個(gè)追求的目標(biāo)-成本最低，即： Min Z= 2x1 + 5x2 +6x3+8x4綜合上述討論，在添加劑中各維生素的含量以及成本與原料消耗量成線性關(guān)系的假設(shè)下，把目標(biāo)函數(shù)和約束條件放在一起，可

4、以建立如下的數(shù)學(xué)模型：目標(biāo)函數(shù)約束條件Min Z= 2x1 + 5x2 +6x3+8x44x1 + 6x2 + x3+2x4 12 x1 + x2 + 7x3+5x4 142x2 + x3 + 3x4 8 xj 0 (j =1,4)s.t類(lèi)似的例子：教材P5-P6，例2第6頁(yè)/共26頁(yè)例3、運(yùn)輸問(wèn)題（紡紗廠） 工 廠 1 2 3 庫(kù)存 倉(cāng) 1 2 1 3 50 2 2 2 4 30 庫(kù) 3 3 4 2 10 需求 40 15 35運(yùn)輸單價(jià)求：運(yùn)輸費(fèi)用最小的運(yùn)輸方案。第7頁(yè)/共26頁(yè)解：設(shè)xij為i 倉(cāng)庫(kù)運(yùn)到j(luò)工廠的原棉數(shù)量 其中：i 1，2，3 j 1，2，3Min Z= 2x11 + x12

5、+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33x11 + x12+ x13 50 x21 + x22+ x23 30 x31 + x32+ x33 10 x11 + x21+ x31 = 40 x12 + x22+ x32 = 15x13 + x23+ x33 = 35 xij 0s.t類(lèi)似的例子：教材P6-P7，例3第8頁(yè)/共26頁(yè) 2.9m鋼筋架子100個(gè)，每個(gè)需用 2.1m 各1，原料長(zhǎng)7.4m 1.5m求：如何下料，使得殘余料頭最少。例4、合理下料問(wèn)題解：首先列出各種可能的下料方案； 計(jì)算出每個(gè)方案可得到的不同長(zhǎng)度鋼筋的數(shù)量及殘余料頭長(zhǎng)度； 確定決策變

6、量； 根據(jù)不同長(zhǎng)度鋼筋的需要量確定約束方程; 根據(jù)下料目標(biāo)確定目標(biāo)函數(shù)。 第9頁(yè)/共26頁(yè)設(shè)按第i種方案下料的原材料為xi根8 , 7 , 6 , 5 , 4 , 3 , 2 , 1100432030100002302010000002. .4 . 18 . 02 . 01 . 109 . 03 . 01 . 087654321876543218765432187654321ixxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxZMini為大于零的整數(shù)，組合方案 1 2 3 4 5 6 7 8 2.9m 2 1 1 1 0 0 0 0 2.1m 0 2 1 0 3 2 1 0

7、 1.5m 1 0 1 3 0 2 3 4 合 計(jì) 7.3m 7.1m 6.5m 7.4m 6.3m 7.2m 6.6m 6.0m 料 長(zhǎng) 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 料 頭 0.1m 0.3m 0.9m 0.0m 1.1m 0.2m 0.8m 1.4m第10頁(yè)/共26頁(yè)(2) 線性規(guī)劃問(wèn)題的特點(diǎn)l決策變量： (x1 xn)T 代表某一方案， 決策者要考慮和控制的因素非負(fù)；l目標(biāo)函數(shù)：Z=(x1 xn) 為線性函數(shù)，求Z極大或極小;l約束條件：可用線性等式或不等式表示.具備以上三個(gè)要素的問(wèn)題就稱(chēng)為 線性規(guī)劃問(wèn)題。第11頁(yè)/共26頁(yè)0,.212

8、21122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax目標(biāo)函數(shù)約束條件(3) 線性規(guī)劃模型一般形式第12頁(yè)/共26頁(yè)隱含的假設(shè)隱含的假設(shè)l比例性：決策變量變化引起目標(biāo)的改變量與決策變量比例性：決策變量變化引起目標(biāo)的改變量與決策變量改變量成比例（即線性關(guān)系假定，比例可能會(huì)不同）改變量成比例（即線性關(guān)系假定，比例可能會(huì)不同）l可加性：每個(gè)決策變量對(duì)目標(biāo)和約束的影響?yīng)毩⒂谄淇杉有裕好總€(gè)決策變量對(duì)目標(biāo)和約束的影響?yīng)毩⒂谄渌兞克兞縧連續(xù)性：每個(gè)決策變量取連續(xù)值連續(xù)性：每個(gè)決策變量取連續(xù)值l確定性：線性規(guī)劃

9、中的參數(shù)確定性：線性規(guī)劃中的參數(shù)aij , bi , cj為確定值為確定值第13頁(yè)/共26頁(yè)1.2 線性規(guī)劃問(wèn)題的圖解法線性規(guī)劃問(wèn)題的圖解法 20,.1XbAXtsCXZMinMax定義2：滿足約束(2)的X=(X1 Xn)T稱(chēng)為線性規(guī)劃問(wèn)題的可行解，全部可行解的集合稱(chēng)為可行域。定義3：滿足(1)的可行解稱(chēng)為線性規(guī)劃問(wèn)題的最優(yōu)解。定義1：一組決策變量X=(X1 Xn)T的集合稱(chēng)為一個(gè)解。第14頁(yè)/共26頁(yè)例1 Max Z= 40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t第15頁(yè)/共26頁(yè)解：(1) 確定可行域 X1+2X2 30 3X1+2

10、X2 60 2X2 24 X1 0 X2 02030100102030X2DABC2X2 24X1+2X2 303X1+2X2 60X1 0X2 0可行域第16頁(yè)/共26頁(yè)(2) 求最優(yōu)解最優(yōu)解：X* = (15,7.5) Zmax =975Z=40X1+50X20=40X1+50X2 (0,0)， (10,-8)C點(diǎn)： X1+2X2 =30 3X1+2X2 =600203010102030X1X2DABC最優(yōu)解Z=975可行解Z=0等值線第17頁(yè)/共26頁(yè)例2、 Max Z=40X1+ 80X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t第18頁(yè)/共26頁(yè)

11、解：(1) 確定可行域與上例完全相同。 (2) 求最優(yōu)解0203010102030DABC最優(yōu)解Z=1200最優(yōu)解：BC線段X1X2第19頁(yè)/共26頁(yè)最優(yōu)解：BC線段B點(diǎn)：X(1)=(6,12) C點(diǎn)：X(2)=(15,7.5)X=X(1)+(1-)X(2) (0 1) Max Z=1200 X1 6 15 X2 12 7.5X= = +(1- )X1 =6 +(1- )15X2=12+(1- )7.5X1 =15-9X2 =7.5+4.5 (0 1)第20頁(yè)/共26頁(yè)例3、 Max Z=2X1+ 4X2 2X1+X2 8-2X1+X2 2X1 , X2 0s.tZ=08246X240X1-2

12、X1+X2 22X1+X2 8X1 0X20可行域無(wú)界無(wú)有限最優(yōu)解可行域無(wú)上界無(wú)有限最優(yōu)解第21頁(yè)/共26頁(yè)例4、 Max Z=3X1+2X2 -X1 -X2 1X1 , X2 0無(wú)可行域無(wú)可行解-1X2-1X10s.tX2 0X1 0-X1 -X2 1第22頁(yè)/共26頁(yè)直觀結(jié)論直觀結(jié)論若線性規(guī)劃問(wèn)題有解，則可行域是一個(gè)凸多邊若線性規(guī)劃問(wèn)題有解，則可行域是一個(gè)凸多邊形（或凸多面體）；形（或凸多面體）；若線性規(guī)劃問(wèn)題有最優(yōu)解，則若線性規(guī)劃問(wèn)題有最優(yōu)解，則唯一最優(yōu)解對(duì)應(yīng)于可行域的一個(gè)頂點(diǎn)；唯一最優(yōu)解對(duì)應(yīng)于可行域的一個(gè)頂點(diǎn)；無(wú)窮多個(gè)最優(yōu)解對(duì)應(yīng)于可行域的一條邊；無(wú)窮多個(gè)最優(yōu)解對(duì)應(yīng)于可行域的一條邊；若線性規(guī)劃問(wèn)題有可行解，但無(wú)有限最優(yōu)解，若線性規(guī)劃問(wèn)題有可行解，但無(wú)有限最優(yōu)解，則可行域必然是無(wú)界的；則可行域必然是無(wú)界的；若線性規(guī)劃問(wèn)題無(wú)可行解，則可行域必為空集。若線性規(guī)劃問(wèn)題無(wú)可行解，則可行域必為空集。第23頁(yè)/共26頁(yè)第一章作業(yè)第一章作業(yè)P P1616-P-P1717:6:6、7 7、8 8、9 9、1010中任選三題中任選三題第24頁(yè)/共26頁(yè)思