運籌學(xué)第二章線性規(guī)劃的圖解法

1、Chapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 1 2022年5月9日星期一1【例例1.1】最優(yōu)生產(chǎn)計劃問題。最優(yōu)生產(chǎn)計劃問題。某企業(yè)在計劃期內(nèi)計劃生產(chǎn)甲、某企業(yè)在計劃期內(nèi)計劃生產(chǎn)甲、乙、丙三種產(chǎn)品。這些產(chǎn)品分別需要要在設(shè)備乙、丙三種產(chǎn)品。這些產(chǎn)品分別需要要在設(shè)備A、B上加工，需上加工，需要消耗材料要消耗材料C、D，按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加，按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工及所需要的資源如表工及所需要的資源如表1.1所示。已知在計劃期內(nèi)設(shè)備的加工能所示。已知在計劃期內(nèi)設(shè)備的加工能力各為力各為200臺時，可供材料分別為臺時，可供材料分別為

2、360、300公斤；每生產(chǎn)一件甲、公斤；每生產(chǎn)一件甲、乙、丙三種產(chǎn)品，企業(yè)可獲得利潤分別為乙、丙三種產(chǎn)品，企業(yè)可獲得利潤分別為40、30、50元，假定元，假定市場需求無限制。市場需求無限制。企業(yè)決策者應(yīng)如何安排生產(chǎn)計劃，使企業(yè)在計劃期內(nèi)總的企業(yè)決策者應(yīng)如何安排生產(chǎn)計劃，使企業(yè)在計劃期內(nèi)總的利潤收入最大？利潤收入最大？問題問題舉例舉例一一、線性規(guī)劃、線性規(guī)劃Chapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 2 2022年5月9日星期一2 產(chǎn)品產(chǎn)品 資源資源 甲甲 乙乙 丙丙現(xiàn)有資源現(xiàn)有資源設(shè)備設(shè)備A 3 1 2 200設(shè)備設(shè)備B 2 2 4 200材料材料C 4

3、 5 1 360材料材料D 2 3 5 300利潤（元利潤（元/件）件） 40 30 50表表1.1 產(chǎn)品資源消耗產(chǎn)品資源消耗Chapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 3 2022年5月9日星期一3321503040maxxxxZ0003005323605420042220023321321321321321xxxxxxxxxxxxxxx，【解解】設(shè)設(shè)x1、x2、x3 分別為甲、乙、丙三種產(chǎn)品的產(chǎn)量數(shù)學(xué)模型分別為甲、乙、丙三種產(chǎn)品的產(chǎn)量數(shù)學(xué)模型為：為： 產(chǎn)品產(chǎn)品 資源資源 甲甲 乙乙 丙丙現(xiàn)有資現(xiàn)有資源源設(shè)備設(shè)備A 3 1 2 200設(shè)備設(shè)備B 2 2

4、 4 200材料材料C 4 5 1 360材料材料D 2 3 5 300利潤（元利潤（元/件）件） 40 30 50最優(yōu)解最優(yōu)解X=(50,30,10);Z=3400Chapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 4 2.2 二維問題的圖解法二維問題的圖解法 Graphical Method1212122401.5300,0 xxxxxx 2143maxxxZChapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 5 2022年5月9日星期一51111221211222212( ,)( ,)0,0a xa xba xa xbxx

5、1122max(min) Zc xc x二維線性規(guī)劃二維線性規(guī)劃(目標函數(shù)目標函數(shù))(約束條件約束條件)具有兩個變量的最優(yōu)化問題有明顯的幾何意義，具有兩個變量的最優(yōu)化問題有明顯的幾何意義，往往可以用圖解法獲得最優(yōu)解往往可以用圖解法獲得最優(yōu)解Chapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 6 2022年5月9日星期一6可行點可行點( (解解) )：滿足所有約束條件的點：滿足所有約束條件的點 可行域可行域：可行點組成的集合：可行點組成的集合1111221211222212( ,)( ,)0,0a xa xba xa xbxx 1122max(min) Zc xc

6、 x(目標函數(shù)目標函數(shù))(約束條件約束條件)Chapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 7 2022年5月9日星期一712326xx 1x2xo12326xx12326xxChapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 8 2022年5月9日星期一81232xxk 0k 6k 12k (3,2)1x2xo直線沿著矢量直線沿著矢量( (梯度梯度) )方向移方向移動動,k,k值增大；值增大；反之反之k k值減小。值減小。矢量矢量(梯度梯度)方向方向Chapter 1 線性規(guī)劃線性規(guī)劃Linear Programming P

7、age 9 2022年5月9日星期一9 線性規(guī)劃：線性規(guī)劃：圖解法的步驟圖解法的步驟：1.1.求可行解集合。求可行解集合。分別求出滿足每個約束包括變量非分別求出滿足每個約束包括變量非 負要求負要求的區(qū)域，其交集就是可行解集合，或稱為的區(qū)域，其交集就是可行解集合，或稱為可行域可行域；2.繪制目標函數(shù)圖形。繪制目標函數(shù)圖形。先過原點作一條矢量指向點（先過原點作一條矢量指向點（c1,c2)，矢量的方向就是目，矢量的方向就是目標函數(shù)標函數(shù)增加增加的方向，稱為的方向，稱為梯度方向梯度方向，再作一條與矢量垂直的，再作一條與矢量垂直的直線，這條直線就是目標函數(shù)圖形；直線，這條直線就是目標函數(shù)圖形；3.求最優(yōu)

8、解。求最優(yōu)解。依據(jù)目標函數(shù)求最大或最小移動目標函數(shù)直線，依據(jù)目標函數(shù)求最大或最小移動目標函數(shù)直線，直線與可行域相交的點對應(yīng)的坐標就是直線與可行域相交的點對應(yīng)的坐標就是最優(yōu)解。最優(yōu)解。2.2 圖解法圖解法The Graphical Method1122Zc xc x 目目標標函函數(shù)數(shù)Chapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 10 2022年5月9日星期一10一般地，將目標函數(shù)直線放在可行域中一般地，將目標函數(shù)直線放在可行域中求最大值時直線沿著求最大值時直線沿著矢量矢量(梯度梯度)方向移動方向移動 求最小值時沿著矢量求最小值時沿著矢量(梯度梯度)的反方向移

9、動的反方向移動Chapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 11 2022年5月9日星期一11x1x2O1020304010203040(3,4)(15,10)最優(yōu)解最優(yōu)解 X = (15,10)最優(yōu)值最優(yōu)值 Z = 8540221xx305 . 121xx1212122401.5300,0 xxxxxx 例例3.112max34Zxx 2.2 圖解法圖解法The Graphical MethodChapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 12 2022年5月9日星期一12246x1x2246最優(yōu)解最優(yōu)解 X = (

10、 3, 1 )最優(yōu)值最優(yōu)值 Z = 5(3,1)121212123643600 xxxxxxxx 、min Z = x1+2x2例例3.2(1,2)3 圖解法圖解法The Graphical MethodChapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 13 2022年5月9日星期一13246x1x2246X（2）（3,1）X（1）（1,3）(5,5)121212123643600 xxxxxxxx 、min Z=5 x1+5 x2例例3.3有無窮多個最優(yōu)解有無窮多個最優(yōu)解即具有多重解即具有多重解,通解為通解為 01 ,)1 ()2() 1 (XXX 當當=0

11、.5時時=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) 3 圖解法圖解法The Graphical MethodChapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 14 2022年5月9日星期一14246x1x2246(1,2)121212123643600 xxxxxxxx 、無界解無界解(無最優(yōu)解無最優(yōu)解)max Z=x1+2x2例例3.43 圖解法圖解法The Graphical MethodChapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 15 2022年5月9日星期一15x1x2O1020304010

12、2030405050121212122401.530500,0 xxxxxxxx 無可行解無可行解即無最優(yōu)解即無最優(yōu)解max Z=10 x1+4x2例例3.53 圖解法圖解法The Graphical MethodChapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 16 2022年5月9日星期一16由以上例題可知，線性規(guī)劃的解有由以上例題可知，線性規(guī)劃的解有4 4種形式：種形式：1.有唯一最優(yōu)解有唯一最優(yōu)解( (例例3.13.1，例，例3.2)3.2)2.有多重解有多重解( (例例3.3)3.3)3.有無界解有無界解( (例例3.4)3.4)4.無可行解無可行解

13、( (例例3.5)3.5)1 1、2 2情形為有最優(yōu)解情形為有最優(yōu)解3 3、4 4情形為無最優(yōu)解情形為無最優(yōu)解2.2 圖解法圖解法The Graphical MethodChapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 17 線性規(guī)劃問題的一般模型 一般地，假設(shè)線性規(guī)劃數(shù)學(xué)模型中有m個約束，有n個決策變量xj， j=1,2,n。 目標函數(shù)中變量的系數(shù)用cj表示，cj稱為價值系數(shù)。 約束條件的變量系數(shù)用aij表示，aij稱為工藝系數(shù)。 約束條件右端的常數(shù)用bi表示，i=1,2,m，bi稱為資源限量。Chapter 1 線性規(guī)劃線性規(guī)劃Linear Program

14、ming Page 18 2.1 線性規(guī)劃的標準型線性規(guī)劃的標準型Standard form of LPChapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 19 2022年5月9日星期一1912312312312328(1)3(2)325(3)00 xxxxxxxxxxxx 、 無符號要求3213maxxxxZ線性規(guī)劃問題的模型線性規(guī)劃問題的模型Chapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 20 2022年5月9日星期一201 1221111221121 1222221 122max(min)(, )(, )(, )0,1,

15、2,nnnnnnmmmnnmjZc xc xc xa xa xa xba xa xa xba xaxaxbxjn 或或或線性規(guī)劃問題的模型線性規(guī)劃問題的模型Chapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 21 2022年5月9日星期一21 在用單純法求解線性規(guī)劃問題時，為了討論問題在用單純法求解線性規(guī)劃問題時，為了討論問題方便，需將線性規(guī)劃模型化為統(tǒng)一的標準形式。方便，需將線性規(guī)劃模型化為統(tǒng)一的標準形式。1.3 線性規(guī)劃的標準型線性規(guī)劃的標準型Standard form of LP線性規(guī)劃問題的標準型為線性規(guī)劃問題的標準型為:1目標函數(shù)求目標函數(shù)求最大值最大

16、值;2約束條件都為等式方程約束條件都為等式方程;3變量變量 xj 非負非負;4常數(shù)常數(shù) bi 非負非負.Chapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 22 2022年5月9日星期一22mibnjxbxaxaxabxaxaxabxaxaxaijmnmnmmnnnn,2, 1,0,2, 1,02211222222111212111max Z=c1 x1+c2 x2+cn xn 1.3 線性規(guī)劃的標準型線性規(guī)劃的標準型Standard form of LP線性規(guī)劃問題的標準型為線性規(guī)劃問題的標準型為: :Chapter 1 線性規(guī)劃線性規(guī)劃Linear Prog

17、ramming Page 23 2022年5月9日星期一231212121212max342403303320,0Zxxxxxxxxx x1231231231228332500 xxxxxxxxxxx 、3213maxxxxZChapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 24 2022年5月9日星期一2412121212min34240330,0Zxxxxxxxx Chapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 25 2022年5月9日星期一250,30340243min21212121xxxxxxxxZ【例例1】 將下

18、列線性規(guī)劃化為標準型將下列線性規(guī)劃化為標準型 Chapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 26 2022年5月9日星期一2612min34Zxx 12max34Zxx 0 xyZ = f(x)( )zf x 目標函數(shù)求最大值目標函數(shù)求最大值？zz Chapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 27 2022年5月9日星期一27【解解】化為標準型化為標準型341212121234m ax34240330,0Zxxxxxxxxxxxx0,30340243min21212121xxxxxxxxZ則標準型為則標準型為:12m

19、ax34Zxx 加入松馳變量加入松馳變量 x3123240 xxx124330 xxx加入松馳變量加入松馳變量 x4Chapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 28 2022年5月9日星期一28【例例2】將下列線性規(guī)劃化為標準型將下列線性規(guī)劃化為標準型 【解解】（）因為（）因為x3無符號要求無符號要求 ，即，即x3取正值也取正值也可取負值，標準型中要求變量非負，所以令可取負值，標準型中要求變量非負，所以令 0,33333 xxxxx其中1.3 線性規(guī)劃的標準型線性規(guī)劃的標準型Standard form of LP1231231231228(1)3(2)3

20、25(3)00 xxxxxxxxxxx 、123min3ZxxxChapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 29 2022年5月9日星期一29 (3)第二個約束條件是第二個約束條件是號，在號，在號號 左端減去剩余變量左端減去剩余變量(Surplus variable)x5，x50。也稱松馳變量。也稱松馳變量123min3Zxxx 12312312312328(1)3(2)325(3)00 xxxxxxxxxxxx 、無符號要求、無符號要求1.3 線性規(guī)劃的標準型線性規(guī)劃的標準型Standard form of LP(2) 第一個約束條件是第一個約束條件是

21、號，在號，在左端左端加入松馳變量加入松馳變量 (slack variable) x4，x40,化為等式；化為等式；341228xxxx12353xxxxChapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 30 2022年5月9日星期一30(4)第三個約束條件是第三個約束條件是號且常數(shù)項為負數(shù)號且常數(shù)項為負數(shù).2613325xxxx 523321xxx123min3Zxxx 12312312312328(1)3(2)325(3)00 xxxxxxxxxxxx 、無符號要求、無符號要求加入松馳變量加入松馳變量x6同時兩邊乘以同時兩邊乘以1Chapter 1 線性規(guī)劃

22、線性規(guī)劃Linear Programming Page 31 2022年5月9日星期一31（5）目標函數(shù)是）目標函數(shù)是最小值最小值，為了化為求，為了化為求最大值最大值，令，令Z= - Z,得到得到 maxZ= - minZ，即當，即當Z達到達到最大值最大值時時, Z達到達到最小值最小值，反之亦，反之亦然。然。 3213minxxxZ無符號要求、32132132132100)3(523)2(3) 1 (82xxxxxxxxxxxx123max3Zxxx Chapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 32 2022年5月9日星期一321.3 線性規(guī)劃的標準型線

23、性規(guī)劃的標準型Standard form of LP綜合起來得到下列標準型綜合起來得到下列標準型 4563333331212121233456(28332)50 xxxxxxxxxxxxxxxxxxxxxx 、 、 、 、 、 、 、 、 、 、 、12333max3Zxxxx 123min3Zxxx 12312312312328(1)3(2)325(3)00 xxxxxxxxxxxx 、無符號要求、無符號要求Chapter 1 線性規(guī)劃線性規(guī)劃Linear Programming Page 33 2022年5月9日星期一33注：化標準型的方法注：化標準型的方法1、目標極小化極大：、目標極小化極大：min( f )= - max ( - f )2、不等