運籌學01-線性規(guī)劃引論ppt課件

1、第一章第一章 線性規(guī)劃引論線性規(guī)劃引論1.1 線性規(guī)劃問題及其數學模型線性規(guī)劃問題及其數學模型1.2 線性規(guī)劃問題的圖解法線性規(guī)劃問題的圖解法1.1 線性規(guī)劃問題及其數學模型線性規(guī)劃問題及其數學模型(1) 線性規(guī)劃問題線性規(guī)劃問題例例1 1、生產組織與計劃問題、生產組織與計劃問題A, B A, B 各生產多少各生產多少, , 可獲最大利潤可獲最大利潤? ?可用資源可用資源煤煤勞動力勞動力倉庫倉庫A B1 23 2 2單位利潤單位利潤40 50306024解解: : 設產品設產品A, BA, B產量分別為變量產量分別為變量x1x1， x2x2根據題意，兩種產品的生產要受到可用資源的限制，根據題意

2、，兩種產品的生產要受到可用資源的限制，具體講：具體講：對于煤，兩種產品生產消耗量不能超過對于煤，兩種產品生產消耗量不能超過30，即：，即： x1 + 2x2 30對于勞動力，兩種產品生產的占用量不超過對于勞動力，兩種產品生產的占用量不超過60，即：，即： 3x1 + 2x2 60對于倉庫，對于倉庫，B種產品生產量的種產品生產量的2倍不能超過倍不能超過24，即：，即： 2x2 24另外，產品數不能為負，即：另外，產品數不能為負，即： x1，x2 0同時，我們有一個追求的目標同時，我們有一個追求的目標-最大利潤，即：最大利潤，即： Max Z= 40 x1 +50 x2綜合上述討論，在生產資源的消

3、耗以及利潤與產品產量成綜合上述討論，在生產資源的消耗以及利潤與產品產量成線性關系的假設下，把目標函數和約束條件放在一起，可線性關系的假設下，把目標函數和約束條件放在一起，可以建立如下的數學模型：以建立如下的數學模型：Max Z= 40 x1 +50 x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0s.t目標函數目標函數約束條件約束條件類似的例子：類似的例子：教材教材P4-P5，例，例1例例2 2 合理配料問題合理配料問題求：最低成本的原料混合方案求：最低成本的原料混合方案 原料原料 A B 每單位成本每單位成本 1 4 1 0 2 2 6 1 2 5 3 1

4、 7 1 6 4 2 5 3 8 每單位添每單位添加劑中維生加劑中維生 12 14 8 素最低含量素最低含量解：設每單位添加劑中原料解：設每單位添加劑中原料j j的用量為的用量為xj(j =1,2,3,4)xj(j =1,2,3,4) 根據題意：混合配料后，根據題意：混合配料后， 每單位添加劑中每單位添加劑中A A的含量不得低于的含量不得低于1212，即，即 4x1 + 6x2 + x3+2x4 4x1 + 6x2 + x3+2x4 1212 每單位添加劑中每單位添加劑中B B的含量不得低于的含量不得低于1414，即，即 x1 + x2 +7x3+5x4 x1 + x2 +7x3+5x4 14

5、14 每單位添加劑中每單位添加劑中C C的含量不得低于的含量不得低于8 8，即，即 2x2 + x3+3x4 2x2 + x3+3x4 8 8 另外，原料使用量不能為負，即：另外，原料使用量不能為負，即： x1x1，x2 x2 ， x3x3， x4x4， 0 0同時，我們有一個追求的目標同時，我們有一個追求的目標-成本最低，即：成本最低，即： Min Z= 2x1 + 5x2 +6x3+8x4綜合上述討論，在添加劑中各維生素的含量以及成本與原綜合上述討論，在添加劑中各維生素的含量以及成本與原料消耗量成線性關系的假設下，把目標函數和約束條件放料消耗量成線性關系的假設下，把目標函數和約束條件放在一

6、起，可以建立如下的數學模型：在一起，可以建立如下的數學模型：目標函數目標函數約束條件約束條件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類似的例子：類似的例子：教材教材P5-P6，例，例2例例3 3、運輸問題紡紗廠）、運輸問題紡紗廠） 工工 廠廠 1 2 3 庫存庫存 倉倉 1 2 1 3 50 2 2 2 4 30 庫庫 3 3 4 2 10 需求需求 40 15 35運輸運輸單價單價求：運輸費用最小的運輸方案。求：運輸費用最小的運輸方案

7、。解：設解：設xijxij為為i i 倉庫運到倉庫運到j j工廠的原棉數量工廠的原棉數量 其中：其中：i i 1 1，2 2，3 3 j j 1 1，2 2，3 3Min Z= 2x11 + x12+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類似的例子：類似的例子：教材教材P6-P7，例，例3 2.9m 2.9m鋼筋架子

8、鋼筋架子100100個，每個需用個，每個需用 2.1m 2.1m 各各1 1，原料長，原料長7.4m7.4m 1.5m 1.5m求：如何下料，使得殘余料頭最少。求：如何下料，使得殘余料頭最少。例例4 4、合理下料問題、合理下料問題解：首先列出各種可能的下料方案；解：首先列出各種可能的下料方案； 計算出每個方案可得到的不同長度鋼筋的數量及計算出每個方案可得到的不同長度鋼筋的數量及殘余料頭長度；殘余料頭長度； 確定決策變量；確定決策變量； 根據不同長度鋼筋的需要量確定約束方程根據不同長度鋼筋的需要量確定約束方程; ; 根據下料目標確定目標函數。根據下料目標確定目標函數。 設按第設按第i i種方案下

9、料的原材料為種方案下料的原材料為xixi根根8 , 7 , 6 , 5 , 4 , 3 , 2 , 1100432030100002302010000002. .4 . 18 . 02 . 01 . 109 . 03 . 01 . 087654321876543218765432187654321ixxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxZMini為大于零的整數，組合方案組合方案 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 1.5m 1 0 1 3 0 2 3 4 合合 計計 7.3m 7.1

10、m 6.5m 7.4m 6.3m 7.2m 6.6m 6.0m 料料 長長 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(2) 線性規(guī)劃問題的特點線性規(guī)劃問題的特點l決策變量：決策變量： (x1 xn)T (x1 xn)T 代表某一方案，代表某一方案， 決策者要考決策者要考慮和控制的因素非負；慮和控制的因素非負；l目標函數：目標函數：Z=Z=(x1 xn) (x1 xn) 為線性函數，求為線性函數，求Z Z極大或極小極大或極小; ;l約束條件：可用線性等式或不等式表示約

11、束條件：可用線性等式或不等式表示. .l具備以上三個要素的問題就稱為具備以上三個要素的問題就稱為 線性規(guī)劃問題。線性規(guī)劃問題。0,.21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax目標函數目標函數約束條件約束條件(3) 線性規(guī)劃模型一般形式線性規(guī)劃模型一般形式隱含的假設隱含的假設比例性：決策變量變化引起目標的改變量與決策比例性：決策變量變化引起目標的改變量與決策變量改變量成比例即線性關系假定，比例可變量改變量成比例即線性關系假定，比例可能會不同）能會不同）可加性：每個決策變量對目標和約束

12、的影響獨立可加性：每個決策變量對目標和約束的影響獨立于其它變量于其它變量連續(xù)性：每個決策變量取連續(xù)值連續(xù)性：每個決策變量取連續(xù)值確定性：線性規(guī)劃中的參數確定性：線性規(guī)劃中的參數aij , bi , cjaij , bi , cj為確定為確定值值1.2 線性規(guī)劃問題的圖解法線性規(guī)劃問題的圖解法 20,.1XbAXtsCXZMinMax定義定義2 2：滿足約束：滿足約束(2)(2)的的X=(X1 Xn)TX=(X1 Xn)T稱為線性規(guī)劃問題稱為線性規(guī)劃問題的可行解，全部可行解的集合稱為可行域。的可行解，全部可行解的集合稱為可行域。定義定義3 3：滿足：滿足(1)(1)的可行解稱為線性規(guī)劃問題的最優(yōu)

13、解。的可行解稱為線性規(guī)劃問題的最優(yōu)解。定義定義1 1：一組決策變量：一組決策變量X=(X1 Xn)TX=(X1 Xn)T的集合稱為一個解。的集合稱為一個解。例例1 Max Z= 40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t解：解：(1) (1) 確定可行域確定可行域 X1+2X2 X1+2X2 30 30 3X1+2X2 3X1+2X2 60 60 2X2 2X2 24 24 X1 X1 0 0 X2 X2 0 02030100102030X2DABC2X2 24X1+2X2 303X1+2X2 60X1 X1 0 0X2 X2 0 0可

14、行域可行域(2) (2) 求最優(yōu)解求最優(yōu)解最優(yōu)解：最優(yōu)解：X* = (15,7.5) Zmax =975Z=40X1+50X20=40X1+50X2 (0,0)， (10,-8)C點：點： X1+2X2 =30 3X1+2X2 =600203010102030X1X2DABC最優(yōu)解最優(yōu)解Z=975可行解可行解Z=0等值線等值線例例2、 Max Z=40X1+ 80X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t解：解：(1) (1) 確定可行域與上例完全相同。確定可行域與上例完全相同。 (2) (2) 求最優(yōu)解求最優(yōu)解0203010102030DABC最優(yōu)解

15、最優(yōu)解Z=1200最優(yōu)解：最優(yōu)解：BCBC線段線段X1X2最優(yōu)解：最優(yōu)解：BCBC線段線段B B點：點：X(1)=(6,12) CX(1)=(6,12) C點：點：X(2)=(15,7.5)X(2)=(15,7.5)X=X=X(1)+(1-X(1)+(1-)X(2) (0 )X(2) (0 1) 1) Max Z=1200 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)例例3、 Max Z=2X1+ 4X2 2X1+X2 8-2X1+X2 2X1 , X2

16、0s.tZ=08246X240X1-2X1+X2 22X1+X2 8X1 0X20可行域可行域無界無界無有限最優(yōu)解無有限最優(yōu)解可行域可行域無上界無上界無有限最優(yōu)解無有限最優(yōu)解例例4、 Max Z=3X1+2X2 -X1 -X2 1X1 , X2 0無可行域無可行域無可行解無可行解-1X2-1X10s.tX2 0X1 0-X1 -X2 1直觀結論直觀結論n若線性規(guī)劃問題有解，則可行域是一個凸多邊形若線性規(guī)劃問題有解，則可行域是一個凸多邊形或凸多面體）；或凸多面體）；n若線性規(guī)劃問題有最優(yōu)解，那么若線性規(guī)劃問題有最優(yōu)解，那么n唯一最優(yōu)解對應于可行域的一個頂點；唯一最優(yōu)解對應于可行域的一個頂點；n無窮多個最優(yōu)解對應于可行域的一條邊；無窮多個最優(yōu)解對應于可行域的一條邊；n若線性規(guī)劃問題有可行解，但無有限最優(yōu)解，則若線性規(guī)劃問題有可行解，但無有限最優(yōu)解，則可行域必然是無界的；可行域必然是無界的；n若線性規(guī)劃問題無可行解，則可行域必為空集。若線性規(guī)劃問題無可行解，則可行域必為空集。第一章作業(yè)第一章作業(yè)P16-P17:6P16-P17:6、7 7、8 8、9 9、1