運籌學(xué)第四版·清華大學(xué)出版社·運籌學(xué)教材組·2.1線性規(guī)劃

1、1Page 2線性規(guī)劃線性規(guī)劃 Linear ProgrammingPage 3引引 言言 線性規(guī)劃是運籌學(xué)的一個重要分支，也是運籌學(xué)中應(yīng)用線性規(guī)劃是運籌學(xué)的一個重要分支，也是運籌學(xué)中應(yīng)用最廣泛的方法之一。自最廣泛的方法之一。自1947年旦茨基（年旦茨基（G. B. Dantzig）提出了一般線性規(guī)劃問題求解的方法提出了一般線性規(guī)劃問題求解的方法單純形法單純形法（simplex method）之后，線性規(guī)劃已被廣泛應(yīng)用于解）之后，線性規(guī)劃已被廣泛應(yīng)用于解決經(jīng)濟管理和工業(yè)生產(chǎn)中遇到的實際問題。調(diào)查表明，決經(jīng)濟管理和工業(yè)生產(chǎn)中遇到的實際問題。調(diào)查表明，在世界在世界500家最大的企業(yè)中，有家最大的企

2、業(yè)中，有85%的企業(yè)都曾使用過線的企業(yè)都曾使用過線性規(guī)劃解決經(jīng)營管理中遇到的復(fù)雜問題。線性規(guī)劃的使性規(guī)劃解決經(jīng)營管理中遇到的復(fù)雜問題。線性規(guī)劃的使用為應(yīng)用者節(jié)約了數(shù)以億萬計的資金。用為應(yīng)用者節(jié)約了數(shù)以億萬計的資金。 本章中我們將討論什么是線性規(guī)劃問題，線性規(guī)劃問本章中我們將討論什么是線性規(guī)劃問題，線性規(guī)劃問題的數(shù)學(xué)表示，基本理論、概念和求解方法。題的數(shù)學(xué)表示，基本理論、概念和求解方法。 解決有限資源在有競爭的使用方向中如何進行最佳分配。解決有限資源在有競爭的使用方向中如何進行最佳分配。42.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型2.2 線性規(guī)劃問題的幾何意義線性規(guī)劃問題的幾何意義

3、2.3 單純形法單純形法2.4 單純形法的計算步驟單純形法的計算步驟2.5 單純形法的進一步討論單純形法的進一步討論2.6 應(yīng)用舉例應(yīng)用舉例Page 5Page 62.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型 2. 1.1 問題的提出問題的提出生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、物力等生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。（1）當任務(wù)或目標確定后，如何統(tǒng)籌兼顧，合理安排，用）當任務(wù)或目標確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源最少的資源 （如資金、

4、設(shè)備、原標材料、人工、時間等）（如資金、設(shè)備、原標材料、人工、時間等）去完成確定的任務(wù)或目標去完成確定的任務(wù)或目標.（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟效益（如產(chǎn)品量最多好的經(jīng)濟效益（如產(chǎn)品量最多 、利潤最大、利潤最大).Page 72.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型例例2.1 某工廠計劃生產(chǎn)某工廠計劃生產(chǎn)、兩種產(chǎn)品。已知生產(chǎn)單兩種產(chǎn)品。已知生產(chǎn)單位產(chǎn)品所需要的設(shè)備臺時及位產(chǎn)品所需要的設(shè)備臺時及A、B兩種原材料的消耗如兩種原材料的消耗如下表所示。該工廠每生產(chǎn)一件產(chǎn)品下表所示。該工廠每生產(chǎn)一件產(chǎn)品可獲利

5、可獲利2元，生元，生產(chǎn)一件產(chǎn)品產(chǎn)一件產(chǎn)品可獲利可獲利3元，元，問企業(yè)決策者應(yīng)如何安排問企業(yè)決策者應(yīng)如何安排生產(chǎn)計劃，使該工廠獲得的利潤最大？生產(chǎn)計劃，使該工廠獲得的利潤最大？ 產(chǎn)品資源 總資源 設(shè)備 1 2 8臺時 原材料A 4 0 16千克 原材料B 0 4 12千克Page 82.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型 解解：設(shè)設(shè)x1、x2分別為產(chǎn)品分別為產(chǎn)品、的產(chǎn)量，則數(shù)學(xué)模的產(chǎn)量，則數(shù)學(xué)模型為：型為：Page 92.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型例例2.1 河流污染治理規(guī)劃問題河流污染治理規(guī)劃問題工廠工廠2工廠工廠1500w200wPage 10 靠

6、近某河流有兩個化工廠靠近某河流有兩個化工廠, ,流經(jīng)第一化工廠的河流流量流經(jīng)第一化工廠的河流流量為每天為每天500萬立方米，在兩個工廠之間有一條流量為每天萬立方米，在兩個工廠之間有一條流量為每天200萬立方米的支流。萬立方米的支流?；S化工廠1每天排放工業(yè)污水每天排放工業(yè)污水2萬立方米，萬立方米，化工廠化工廠2每天排放工業(yè)污水為每天排放工業(yè)污水為1.4萬立方米。從化工廠萬立方米。從化工廠1排出排出的污水流到化工廠的污水流到化工廠2前，有前，有20%可自然凈化。可自然凈化。 據(jù)環(huán)保要求，河流中工業(yè)污水的含量應(yīng)不大于據(jù)環(huán)保要求，河流中工業(yè)污水的含量應(yīng)不大于0.2%。因此兩個工廠都需處理一部分工業(yè)

7、污水?；S因此兩個工廠都需處理一部分工業(yè)污水?；S1處理污水處理污水的成本是的成本是1000元元/萬立方米萬立方米,化工廠化工廠2處理污水的成本是處理污水的成本是800元元/萬立方米。問萬立方米。問:在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使兩個工廠處理工業(yè)污水的總費用最小？少工業(yè)污水，使兩個工廠處理工業(yè)污水的總費用最?。?.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型Page 11解：設(shè)解：設(shè)化工廠化工廠1每天處理的污水量為每天處理的污水量為x1萬立方米；萬立方米；化工廠化工廠2每天處理的污水量為每天處理的污水量為x2萬立方米萬立方

8、米112(2)22500100020.8(2)(1.4)27001000 xxx 經(jīng)經(jīng)第第 工工廠廠前前的的水水質(zhì)質(zhì)要要求求：經(jīng)經(jīng)第第 工工廠廠后后的的水水質(zhì)質(zhì)要要求求：2.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型Page 12121121212min100080010.81.621.4,0zxxxxxxxxx 得到本問題的數(shù)學(xué)模型為：得到本問題的數(shù)學(xué)模型為：2.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型Page 13l每一個線性規(guī)劃問題都用一組決策變量每一個線性規(guī)劃問題都用一組決策變量 表示某一方案，這組決策變量的值代表一個具體方案。一表示某一方案，這組決策變量的值代表

9、一個具體方案。一般這些變量的取值是非負且連續(xù)的；般這些變量的取值是非負且連續(xù)的；l都有關(guān)于各種資源和資源使用情況的技術(shù)數(shù)據(jù)，創(chuàng)造新價都有關(guān)于各種資源和資源使用情況的技術(shù)數(shù)據(jù)，創(chuàng)造新價值的數(shù)據(jù)；值的數(shù)據(jù)；l存在可以量化的約束條件，這些約束條件可以用一組線性存在可以量化的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示等式或線性不等式來表示; ;l都有一個達到某一目標的要求，可用決策變量的線性函數(shù)都有一個達到某一目標的要求，可用決策變量的線性函數(shù)( (稱為目標函數(shù)稱為目標函數(shù)) )來表示。按問題的要求不同，要求目標函來表示。按問題的要求不同，要求目標函數(shù)實現(xiàn)最大化或最小化。數(shù)實現(xiàn)最大化或

10、最小化。上述兩個問題具有的共同特征：上述兩個問題具有的共同特征：2.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型 12,nxxxPage 142.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型Page 152.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型00 )( )( (min) max12211112121112211 nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz)21(j 0 )21(i )( Z (min)max 11nxmbxaxcjnjijijnjjj 簡寫為：簡寫為：Page 16 線性規(guī)劃問題的求解方法一一 般般 方法方法圖圖 解解

11、 法法單純形法單純形法兩個變量、直角坐標兩個變量、直角坐標三個變量、立體坐標三個變量、立體坐標適用于任意變量、但必需將適用于任意變量、但必需將一般形式變成標準形式一般形式變成標準形式下面我們分析一下簡單的情況下面我們分析一下簡單的情況 只有兩個決策變量的線只有兩個決策變量的線性規(guī)劃問題，這時可以通過圖解的方法來求解。圖解法具性規(guī)劃問題，這時可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何有簡單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點。意義等優(yōu)點。2.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型Page 172.1.2 2.1.2 圖解法

12、圖解法0124164223221212121x,xxxxxxxzmax2.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型Page 18目標值在（目標值在（4，2）點，達到最大值）點，達到最大值142.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型12max23zxx21233zxx 表表示示一一簇簇平平行行Page 19（1）唯一最優(yōu)解。）唯一最優(yōu)解。（2）無窮多最優(yōu)解）無窮多最優(yōu)解(多重最優(yōu)解多重最優(yōu)解)。（3）無界解。）無界解。（4）無可行解。）無可行解。通過圖解法，可觀察到線性規(guī)劃的解可能出現(xiàn)通過圖解法，可觀察到線性規(guī)劃的解可能出現(xiàn)的幾種情況：的幾種情況：2.1 線性規(guī)劃問題

13、及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型Page 20（2）無窮多最優(yōu)解（多重最優(yōu)解）無窮多最優(yōu)解（多重最優(yōu)解）2.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型12121212max2422416412,0zxxxxxxxx 21244zxx 表表示示一一簇簇平平行行Page 21ox ,xxxxxxxzmax2121121242（3）無界解）無界解2.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型Page 22 當存在相互矛盾的約束條件時，線性規(guī)劃問題的可當存在相互矛盾的約束條件時，線性規(guī)劃問題的可行域為空集。行域為空集。（4）無可行解）無可行解2.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性

14、規(guī)劃問題及其數(shù)學(xué)模型121.58xx例如在例例如在例2.1的數(shù)學(xué)模型中增加一個約束條件的數(shù)學(xué)模型中增加一個約束條件: 12121212max2322416412,0zxxxxxxxx Page 2385 . 121xx增加的約束條件2.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型則該問題的可行域即為空集，即無可行解，則該問題的可行域即為空集，即無可行解，Page 24x1x2O10203040102030405050無可行解無可行解(即無最優(yōu)解即無最優(yōu)解)1212121212m ax342401.530500,0zxxxxxxxxxxPage 252.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)

15、劃問題及其數(shù)學(xué)模型簡寫為：簡寫為：minjxbxatsxcZjnjijijnjjj, 2 , 1, 2 , 1, 0.max11 11221111221111221max 00nnnnmmmnnmnzc xc xc xa xa xa xbaxaxaxbxxPage 262.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型特點：特點：(1) 目標函數(shù)求最大值（有時求最小值）目標函數(shù)求最大值（有時求最小值）(2) 約束條件都為等式方程，且右端常數(shù)項約束條件都為等式方程，且右端常數(shù)項bi都大于或等于零都大于或等于零(3) 決策變量決策變量xj為非負。為非負。Page 272.1 線性規(guī)劃問題及其

16、數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型) (21ncccC nxxX1 mjjjaaP1 mbbB1其中：其中：max 0 jjzCXp xBX Page 282.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型其中：其中：) (21ncccC nxxX1 mbbB1max 0 ZCXAXBX 111121(,)nnmmnaaAP PPaa000 Page 292.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型 目標函數(shù)的轉(zhuǎn)換目標函數(shù)的轉(zhuǎn)換 如果是求極小值即如果是求極小值即 ，則可將目標函數(shù)乘以，則可將目標函數(shù)乘以(- (-1)1)，可化為求極大值問題。，可化為求極大值問題。 jjxczm

17、in也就是：令也就是：令 ，可得到上式。，可得到上式。zz jjxczzmax即即 若存在取值無約束的變量若存在取值無約束的變量 ，可令，可令 其中：其中：jxjjjxxx 0, jjxx 變量的變換變量的變換Page 302.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型 約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。 ijijbxa0 iniinjijxbxxa稱為松弛變量稱為松弛變量 ijijbxa0 iniinjijxbxxa稱為剩余變量稱為剩余變量 變量變量 的變換的變換0 jx 可令可令 ，顯然，顯然jjxx 0 jxPage 311.3 線性規(guī)劃問

18、題的標準型式線性規(guī)劃問題的標準型式例例2.3 將例將例2.12.1的數(shù)學(xué)模型化為標準形式的線性規(guī)劃。的數(shù)學(xué)模型化為標準形式的線性規(guī)劃。12121212max2328416412,0zxxxxxxxx 1234512314251234max2300028416412,0zxxxxxxxxxxxxxxxxx Page 322.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型例例2.4 將下列線性規(guī)劃問題化為標準形式將下列線性規(guī)劃問題化為標準形式 ,0,52324 7 532min321321321321321無無約約束束xxxxxxxxxxxxxxxZ用用 替換替換 ，且，且 解解:（）因為（

19、）因為x3無符號要求無符號要求 ，即，即x3取正值也可取負值，標準取正值也可取負值，標準型中要求變量非負，所以型中要求變量非負，所以33xx 3x0,33 xxPage 332.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型(2) 第一個約束條件是第一個約束條件是“”號，在號，在“”左端加入松馳變量左端加入松馳變量x4，x40,化為等式；化為等式；(3) 第二個約束條件是第二個約束條件是“”號，在號，在“”左端減去剩余變量左端減去剩余變量x5，x50；(4) 第第3個約束方程右端常數(shù)項為個約束方程右端常數(shù)項為-5，方程兩邊同乘以，方程兩邊同乘以(-1),將右將右端常數(shù)項化為正數(shù)；端常數(shù)項

20、化為正數(shù)； (5) 目標函數(shù)是最小值，為了化為求最大值，令目標函數(shù)是最小值，為了化為求最大值，令z=-z,得到得到max z=-z，即當，即當z達到最小值時達到最小值時z達到最大值，反之亦然達到最大值，反之亦然;Page 342.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型 0,5 )(252 )( 7 )(500)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ標準形式如下：標準形式如下：Page 352.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型 )3(, 2 , 1, 0)2(), 2 , 1(.)

21、1 (max11njxmibxatsxcZjnjijijnjjj線性規(guī)劃問題線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組的方程組中找出一個解，使目標函數(shù)中找出一個解，使目標函數(shù)(1)達到最大值。達到最大值。Page 362.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型 可行解可行解：滿足約束條件：滿足約束條件(2)(2)、(3)(3)的解為可行解。所有可行的解為可行解。所有可行解的集合為可行域。解的集合為可行域。 最優(yōu)解最優(yōu)解：使目標函數(shù)達到最大值的可行解。：使目標函數(shù)達到最大值的可行解。 基：基：設(shè)設(shè)A為約束條件為約束條件

22、(2)的的mn階系數(shù)矩陣階系數(shù)矩陣(mn)，其秩為，其秩為m，B是矩陣是矩陣A中中m階滿秩子矩陣（階滿秩子矩陣（ B 0），稱），稱B是規(guī)劃問題的是規(guī)劃問題的一個基。設(shè)：一個基。設(shè)：) (11111mmmmmppaaaaB 稱稱 B中每個列向量中每個列向量Pj ( j = 1 2 m) 為基向量。與基向量為基向量。與基向量Pj 對應(yīng)的變量對應(yīng)的變量xj 為為基變量基變量。除基變量以外的變量為。除基變量以外的變量為非基變量非基變量。Page 372.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型 基解：某一確定的基某一確定的基B，令非基變量等于零，由約束條，令非基變量等于零，由約束條件方程

23、件方程(2)(2)解出基變量，稱這組解為基解。解出基變量，稱這組解為基解。 在基解中變量取非零值的個數(shù)不大于方程數(shù)在基解中變量取非零值的個數(shù)不大于方程數(shù)m，基，基解的總數(shù)不超過解的總數(shù)不超過 基可行解：滿足變量非負約束條件的基本解。滿足變量非負約束條件的基本解。 可行基：對應(yīng)于基可行解的基稱為可行基。對應(yīng)于基可行解的基稱為可行基。mnCPage 38約束方程的約束方程的解空間解空間基礎(chǔ)解基礎(chǔ)解可行解可行解非可行解非可行解基礎(chǔ)基礎(chǔ)可行解可行解退化解退化解Page 392.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型例例2.5 求下列約束方程所對應(yīng)的線性規(guī)劃的所有基本解，基求下列約束方程所

24、對應(yīng)的線性規(guī)劃的所有基本解，基本可行解。本可行解。解：化為標準形式解：化為標準形式 12212282 ,0 xxxxx 1232412342 8 2 ,0 xxxxxxxxx 12341210A=(P ,P ,P ,P )240101 為為階階矩矩陣陣，8b=2 242,C .RA 且且所所以以線線性性規(guī)規(guī)劃劃基基的的個個數(shù)數(shù)Page 4011212B =(P ,P )01 取取，12,xx 為為基基變變量量，340 xx若若令令非非基基變變量量12228 2xxx 約約束束方方程程組組為為1(4,2,0,0)TX 可可得得基基本本解解 ， ，是是一一基基本本可可行行解解。Page 41按相同

25、步驟，可求得線性規(guī)劃其他按相同步驟，可求得線性規(guī)劃其他4 4個基個基：21410B =(P ,P )01對應(yīng)基本解對應(yīng)基本解是一個基本可行解。是一個基本可行解。 32321B =(P ,P )1042420B =(P ,P )1153410B =(P ,P )01T5X =(0,0,8,2)12341210A=(P,P ,P ,P )0101T2X =(8,0,0,2)T3X =(0,2,4,0)T4X =(0,4,0,-2)對應(yīng)基本解對應(yīng)基本解是一個基本可行解。是一個基本可行解。 對應(yīng)基本解對應(yīng)基本解不是一個基本可行解。不是一個基本可行解。 對應(yīng)基本解對應(yīng)基本解是一個基本可行解。是一個基本可

26、行解。 8b=2 Page 42若利用圖解法畫出線性規(guī)劃的可行域，如圖，若利用圖解法畫出線性規(guī)劃的可行域，如圖，12212282 ,0 xxxxx 12345X =(4,2,0,0)B, X =(8,0,0,2)A, X =(0,2,4,0)CX =(0,4,0,-2)D, X =(0,0,8,2)O.CDOBA4481228xx22xPage 431.凸集：設(shè)凸集：設(shè)k是是n維歐式空間的一個點集，若任意兩維歐式空間的一個點集，若任意兩點點X(1）k, X(2）k的連線上的一切點的連線上的一切點X(1(1+ (1-+ (1-)X(2(2）k(01),(01),則稱則稱k為凸集。為凸集。 連接幾何形體中任意兩點的線段仍完全在該幾何連接幾何形體中任意兩點的線段仍完全在該幾何形體之中。形體之中。 有限個凸集的交集仍然是凸集。有限個凸集的交集仍然是凸集。2.2 線性規(guī)劃問題的幾何意義線性規(guī)劃問題的幾何意義Page 442.2 線性規(guī)劃問題的幾何意義線性規(guī)劃問題的幾何意義2.2. 凸組合：設(shè)凸組合：設(shè)X X(1(1），X