韓伯棠管理運(yùn)籌學(xué)(第三版)_第二章_線性規(guī)劃的圖解法

1、1& 2& 3投資問題。從許多不同的投資項(xiàng)目中選投資問題。從許多不同的投資項(xiàng)目中選出一個(gè)投資方案，使得投資的回報(bào)為最大。出一個(gè)投資方案，使得投資的回報(bào)為最大。& 4產(chǎn)品生產(chǎn)計(jì)劃。合理充分地利用廠里產(chǎn)品生產(chǎn)計(jì)劃。合理充分地利用廠里現(xiàn)有的人力、物力、財(cái)力，作出最優(yōu)的產(chǎn)品現(xiàn)有的人力、物力、財(cái)力，作出最優(yōu)的產(chǎn)品生產(chǎn)計(jì)劃，使得工廠獲利最大。生產(chǎn)計(jì)劃，使得工廠獲利最大。& 5勞動(dòng)力安排。某單位由于工作需要，勞動(dòng)力安排。某單位由于工作需要，在不同時(shí)間段需要不同數(shù)量的勞動(dòng)力，在每在不同時(shí)間段需要不同數(shù)量的勞動(dòng)力，在每個(gè)勞動(dòng)力工作日連續(xù)工作八小時(shí)的規(guī)則下，個(gè)勞動(dòng)力工作日連續(xù)工作八

2、小時(shí)的規(guī)則下，如何安排勞動(dòng)力，才能用最少的勞動(dòng)力來滿如何安排勞動(dòng)力，才能用最少的勞動(dòng)力來滿足工作的需要。足工作的需要。 3& 6運(yùn)輸問題。一個(gè)公司有若干個(gè)生產(chǎn)單位與銷售單運(yùn)輸問題。一個(gè)公司有若干個(gè)生產(chǎn)單位與銷售單位，根據(jù)各生產(chǎn)單位的產(chǎn)量及銷售單位的銷量，如何制位，根據(jù)各生產(chǎn)單位的產(chǎn)量及銷售單位的銷量，如何制定調(diào)運(yùn)方案，將產(chǎn)品運(yùn)到各銷售單位而總的運(yùn)費(fèi)最小。定調(diào)運(yùn)方案，將產(chǎn)品運(yùn)到各銷售單位而總的運(yùn)費(fèi)最小。& 以上的這些問題，線性規(guī)劃都能成功地加以解決。以上的這些問題，線性規(guī)劃都能成功地加以解決。當(dāng)然其在管理上的應(yīng)用遠(yuǎn)不止這些。這些例子都有一個(gè)當(dāng)然其在管理上的應(yīng)用遠(yuǎn)不止這些。這些例子

3、都有一個(gè)共同的特點(diǎn)。共同的特點(diǎn)。& 首先，每個(gè)例子中都要求達(dá)到某些數(shù)量上的最大化首先，每個(gè)例子中都要求達(dá)到某些數(shù)量上的最大化或最小化的目標(biāo)。如問題或最小化的目標(biāo)。如問題1，是要求使用原料鋼管最少；，是要求使用原料鋼管最少；問題問題2是要求利潤(rùn)最大；問題是要求利潤(rùn)最大；問題3是要求投資回報(bào)最大等等。是要求投資回報(bào)最大等等。在所有線性規(guī)劃的問題中某些數(shù)量上的最大化或最小化在所有線性規(guī)劃的問題中某些數(shù)量上的最大化或最小化就是線性規(guī)劃問題的目標(biāo)。就是線性規(guī)劃問題的目標(biāo)。& 其次，所有線性規(guī)劃問題都是在一定的約束條件下其次，所有線性規(guī)劃問題都是在一定的約束條件下來追求其目標(biāo)的。例如問題來

4、追求其目標(biāo)的。例如問題1，是在滿足生產(chǎn)需要的一，是在滿足生產(chǎn)需要的一定數(shù)量、不同規(guī)格的鋼管的約束下來追求原材料鋼管的定數(shù)量、不同規(guī)格的鋼管的約束下來追求原材料鋼管的最小使用量。而在問題最小使用量。而在問題2中是在原料供應(yīng)量的限制和保中是在原料供應(yīng)量的限制和保證產(chǎn)品成分的含量約束下來追求最大利潤(rùn)的。證產(chǎn)品成分的含量約束下來追求最大利潤(rùn)的。4 2.1 問題的提出問題的提出5如何建立模型？如何建立模型？6& 這個(gè)問題可以用以下的數(shù)學(xué)模型來加以描述。工廠目前要決這個(gè)問題可以用以下的數(shù)學(xué)模型來加以描述。工廠目前要決策的問題是生產(chǎn)多少個(gè)策的問題是生產(chǎn)多少個(gè)產(chǎn)品和生產(chǎn)多少個(gè)產(chǎn)品和生產(chǎn)多少個(gè)產(chǎn)品，把這

5、個(gè)要決產(chǎn)品，把這個(gè)要決策的問題用變量策的問題用變量x1、x2來表示，則稱來表示，則稱x1和和x2為決策變量，即決策為決策變量，即決策變量變量x1=生產(chǎn)生產(chǎn)I產(chǎn)品的數(shù)量，決策變量產(chǎn)品的數(shù)量，決策變量x2=生產(chǎn)生產(chǎn)產(chǎn)品的數(shù)量。產(chǎn)品的數(shù)量。& 用用x1和和x2的線性函數(shù)形式來表示工廠所要求的最大利潤(rùn)的目標(biāo)：的線性函數(shù)形式來表示工廠所要求的最大利潤(rùn)的目標(biāo)： max Z=50 x1+100 x2 （稱為目標(biāo)函數(shù)）。（稱為目標(biāo)函數(shù)）。& 其中其中max為最大化的符號(hào)為最大化的符號(hào)(最小化為最小化為min)；50和和100分別為單位產(chǎn)分別為單位產(chǎn)品品 、 的利潤(rùn)。同樣也可以用的利潤(rùn)。同樣也可

6、以用x1和和x2的線性不等式來表示問題的線性不等式來表示問題的約束條件。對(duì)于臺(tái)時(shí)數(shù)的限制可以表示為：的約束條件。對(duì)于臺(tái)時(shí)數(shù)的限制可以表示為： X1+X2300 & 同樣，兩種原材料的限量可分別表示為：同樣，兩種原材料的限量可分別表示為：& 2X1+X2400, X2250.& 除了上述約束外，顯然還應(yīng)該有除了上述約束外，顯然還應(yīng)該有x10，x20，因?yàn)?，因?yàn)楫a(chǎn)品產(chǎn)品, 產(chǎn)產(chǎn)品的品的 產(chǎn)量是不能取負(fù)值的。綜上所述，就得到了例產(chǎn)量是不能取負(fù)值的。綜上所述，就得到了例1的數(shù)學(xué)模型的數(shù)學(xué)模型如下：如下：7& 目標(biāo)函數(shù)：目標(biāo)函數(shù)： max Z=50 x1+100 x2，&

7、amp; 滿足約束條件：滿足約束條件：x1+x2300，& 2 x1+x2400，& x2250,& x10, x20.& 由于上述數(shù)學(xué)模型的目標(biāo)函數(shù)為變量的線性函數(shù)，由于上述數(shù)學(xué)模型的目標(biāo)函數(shù)為變量的線性函數(shù)，約束條件也為變量的線性等式或不等式，故此模型稱約束條件也為變量的線性等式或不等式，故此模型稱之為線性規(guī)劃。如果目標(biāo)函數(shù)是變量的非線性函數(shù)，之為線性規(guī)劃。如果目標(biāo)函數(shù)是變量的非線性函數(shù)，或約束條件中含有變量非線性的等式或不等式的數(shù)學(xué)或約束條件中含有變量非線性的等式或不等式的數(shù)學(xué)模型則稱之為非線性規(guī)劃。模型則稱之為非線性規(guī)劃。& 把滿足所有約束條件的

8、解稱為該線性規(guī)劃的可行把滿足所有約束條件的解稱為該線性規(guī)劃的可行解。把使得目標(biāo)函數(shù)值最大解。把使得目標(biāo)函數(shù)值最大(即利潤(rùn)最大即利潤(rùn)最大)的可行解稱的可行解稱為該線性規(guī)劃的最優(yōu)解，此目標(biāo)函數(shù)值稱為最優(yōu)目標(biāo)為該線性規(guī)劃的最優(yōu)解，此目標(biāo)函數(shù)值稱為最優(yōu)目標(biāo)函數(shù)值，簡(jiǎn)稱最優(yōu)值。函數(shù)值，簡(jiǎn)稱最優(yōu)值。8& 1要正確理解所要解決的問題，要搞清在什么條件要正確理解所要解決的問題，要搞清在什么條件下，追求什么樣的目標(biāo)。下，追求什么樣的目標(biāo)。& 2定義決策變量，每一個(gè)問題都用一組決策變量定義決策變量，每一個(gè)問題都用一組決策變量(X1，X2, , Xn)表示任何一個(gè)方案；這組決策變量的值就代表示任何一

9、個(gè)方案；這組決策變量的值就代表一個(gè)具體方案，一般這些變量取值是非負(fù)的。表一個(gè)具體方案，一般這些變量取值是非負(fù)的。& 3用決策變量的線性函數(shù)形式寫出所要追求的目標(biāo)，用決策變量的線性函數(shù)形式寫出所要追求的目標(biāo)，稱之為目標(biāo)函數(shù)，按問題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最稱之為目標(biāo)函數(shù)，按問題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。大化或最小化。& 4用一組決策變量的等式或不等式來表示在解決問用一組決策變量的等式或不等式來表示在解決問題過程上所必須遵循的約束條件。題過程上所必須遵循的約束條件。& 滿足以上滿足以上2、3、4三個(gè)條件的數(shù)學(xué)模型稱之為線性規(guī)三個(gè)條件的數(shù)學(xué)模型稱之為線性規(guī)劃的數(shù)

10、學(xué)模型，其一般形式為劃的數(shù)學(xué)模型，其一般形式為:對(duì)于一般線性規(guī)劃問題的建模過程。應(yīng)注意對(duì)于一般線性規(guī)劃問題的建模過程。應(yīng)注意如下幾個(gè)問題：如下幾個(gè)問題：9線性規(guī)劃的數(shù)學(xué)模型的一般形式為線性規(guī)劃的數(shù)學(xué)模型的一般形式為:& 目標(biāo)函數(shù)：目標(biāo)函數(shù)：& max (min) Z=c1x1+c2x2+cnxn& 約束條件：約束條件：& a11x1+a12x2+a1nxn( =, ) b1,& a21x1+a22x2+a2nxn( =, ) b2,& & am1x1+am2x2+amnxn( =, ) bm,& x1, x2, , xn0.10&

11、amp; 對(duì)于只包含兩個(gè)決策變量的線性規(guī)劃問題，可對(duì)于只包含兩個(gè)決策變量的線性規(guī)劃問題，可以用圖解法來求解。大于兩個(gè)決策變量不能用圖解以用圖解法來求解。大于兩個(gè)決策變量不能用圖解法來解了。法來解了。& 圖解法圖解法.首先把每個(gè)約束條件（代表一個(gè)平面）首先把每個(gè)約束條件（代表一個(gè)平面）畫在二維坐標(biāo)軸上。畫在二維坐標(biāo)軸上。100300100300X1+X2=300 x1x22.2 圖圖 解解 法法111004001003002X1+X2=400 x1x2100100300X2=250 x1x212X1+X2=300100400100300 x1x2X2=2502x1+x2=400Z=100

12、00=50 x1+100 x2Z=27500=50 x1+100 x2B 陰影部分的每陰影部分的每一點(diǎn)一點(diǎn)(包括邊界包括邊界線線)都是這個(gè)線都是這個(gè)線性規(guī)劃的可行性規(guī)劃的可行解，而此公共解，而此公共部分是例部分是例1的可的可行解的集合，行解的集合，稱為可行域。稱為可行域。B點(diǎn)為最優(yōu)解，坐標(biāo)為（點(diǎn)為最優(yōu)解，坐標(biāo)為（50，250）Z=0=50 x1+100 x213問題的解：?jiǎn)栴}的解：& 最佳決策為最佳決策為x1=50, x2=250，此時(shí)，此時(shí)z=27500。 這說明該廠的最優(yōu)生產(chǎn)計(jì)劃方案是生產(chǎn)這說明該廠的最優(yōu)生產(chǎn)計(jì)劃方案是生產(chǎn)I產(chǎn)品產(chǎn)品50單位，單位，生產(chǎn)生產(chǎn)產(chǎn)品產(chǎn)品250單位，可得最

13、大利潤(rùn)單位，可得最大利潤(rùn)27500元。元。& 把把x1=50, x2=250代入約束條件得：代入約束條件得：& 50+250=300臺(tái)時(shí)設(shè)備臺(tái)時(shí)設(shè)備& 250+250=350千克原料千克原料A，& 1250=250千克原料千克原料B& 這表明了生產(chǎn)這表明了生產(chǎn)50單位單位產(chǎn)品和產(chǎn)品和250單位單位產(chǎn)品將消產(chǎn)品將消耗完所有可使用的設(shè)備臺(tái)時(shí)數(shù)和原料耗完所有可使用的設(shè)備臺(tái)時(shí)數(shù)和原料B，但對(duì)原料，但對(duì)原料A來來說只消耗了說只消耗了350千克，還有千克，還有(400350)=50千克沒有千克沒有使用。使用。在線性規(guī)劃中，對(duì)一個(gè)在線性規(guī)劃中，對(duì)一個(gè)約束條件中沒使用的

14、資約束條件中沒使用的資源或能力的大小稱之為松弛量。源或能力的大小稱之為松弛量。14松弛變量和線性規(guī)劃標(biāo)準(zhǔn)化松弛變量和線性規(guī)劃標(biāo)準(zhǔn)化&為了把一個(gè)線性規(guī)劃標(biāo)準(zhǔn)化，需要有代表沒使用的為了把一個(gè)線性規(guī)劃標(biāo)準(zhǔn)化，需要有代表沒使用的資源或能力的變量，稱之為松弛變量，記為資源或能力的變量，稱之為松弛變量，記為Si。顯。顯然這些松弛變量對(duì)目標(biāo)函數(shù)不會(huì)產(chǎn)生影響，可以在然這些松弛變量對(duì)目標(biāo)函數(shù)不會(huì)產(chǎn)生影響，可以在目標(biāo)函數(shù)中把這些松弛變量的系數(shù)看成零，加了松目標(biāo)函數(shù)中把這些松弛變量的系數(shù)看成零，加了松弛變量后我們得到如下的例弛變量后我們得到如下的例1的數(shù)學(xué)模型：的數(shù)學(xué)模型：& 目標(biāo)函數(shù)：目標(biāo)函數(shù)：

15、& max Z=50 x1+100 x2+0s1+0s2+0s3，& 約束條件：約束條件： x1+x2+s1=300,& 2x1+x2+s2=400,& x2+s3=250,& x1,x2,s1,s2,s3015& 像這樣把所有的約束條件都寫成等式，稱為線性像這樣把所有的約束條件都寫成等式，稱為線性規(guī)劃模型的標(biāo)準(zhǔn)化，所得結(jié)果稱為線性規(guī)劃的標(biāo)準(zhǔn)形規(guī)劃模型的標(biāo)準(zhǔn)化，所得結(jié)果稱為線性規(guī)劃的標(biāo)準(zhǔn)形式。在標(biāo)準(zhǔn)型中式。在標(biāo)準(zhǔn)型中 bj(右邊常量右邊常量)都要大于等于零，都要大于等于零， 對(duì)某對(duì)某個(gè)個(gè)bj小于零時(shí)，只要方程兩邊都乘以小于零時(shí)，只要方程兩邊都乘以

16、(-1)即可。即可。&實(shí)際上以后可看到應(yīng)同時(shí)具備如下三個(gè)條件的模型實(shí)際上以后可看到應(yīng)同時(shí)具備如下三個(gè)條件的模型才是標(biāo)準(zhǔn)型：才是標(biāo)準(zhǔn)型：&一是約束條件必須化為等式；二是所有變量必須化一是約束條件必須化為等式；二是所有變量必須化為大于或者等于零；三是約束條件中的右端常數(shù)項(xiàng)必為大于或者等于零；三是約束條件中的右端常數(shù)項(xiàng)必須是大于或者等于零。須是大于或者等于零。& 對(duì)例對(duì)例1 的最優(yōu)解的最優(yōu)解 x1=50,x2=250來說，松弛變量的值來說，松弛變量的值如下所示：如下所示：& 約束條件約束條件 松弛變量的值松弛變量的值& 設(shè)備臺(tái)時(shí)數(shù)設(shè)備臺(tái)時(shí)數(shù) s1=0&

17、 原料原料A s2=50 & 原料原料B s3=016線性規(guī)劃問題解的有如下特點(diǎn)：線性規(guī)劃問題解的有如下特點(diǎn)：& 1如果某一個(gè)線性規(guī)劃問題有最優(yōu)解，則一如果某一個(gè)線性規(guī)劃問題有最優(yōu)解，則一定有一個(gè)可行域的頂點(diǎn)對(duì)應(yīng)一個(gè)最優(yōu)解。定有一個(gè)可行域的頂點(diǎn)對(duì)應(yīng)一個(gè)最優(yōu)解。& 2線性規(guī)劃存在有無窮多個(gè)最優(yōu)解的情況。線性規(guī)劃存在有無窮多個(gè)最優(yōu)解的情況。若將例若將例1中的目標(biāo)函數(shù)變?yōu)榍笾械哪繕?biāo)函數(shù)變?yōu)榍髆ax Z =50 x1+50 x2，則可見代表目標(biāo)函數(shù)的直線平移到最優(yōu)位置后將則可見代表目標(biāo)函數(shù)的直線平移到最優(yōu)位置后將和直線和直線x1+x2=300重合。詳見下圖。重合。詳見下圖。&a

18、mp; 此時(shí)不僅頂點(diǎn)此時(shí)不僅頂點(diǎn)B，C都代表了最優(yōu)解，而且都代表了最優(yōu)解，而且線段線段BC上的所有點(diǎn)都代表了最優(yōu)解，這樣最優(yōu)上的所有點(diǎn)都代表了最優(yōu)解，這樣最優(yōu)解就有無窮多個(gè)了。當(dāng)然這些最優(yōu)解都對(duì)應(yīng)著相解就有無窮多個(gè)了。當(dāng)然這些最優(yōu)解都對(duì)應(yīng)著相同的最優(yōu)值（只有一個(gè)）：同的最優(yōu)值（只有一個(gè)）：& 50 x1+50 x2=5050+50250=15000。 17X1+X2=300100400100300 x1x2X2=2502x1+x2=400Z=10000=50 x1+50 x2Z=15000=50 x1+50 x2BZ=0=50 x1+50 x218 線性規(guī)劃存在無界解，即無線性規(guī)劃存在

19、無界解，即無最優(yōu)解的情況。對(duì)下述線性規(guī)劃問最優(yōu)解的情況。對(duì)下述線性規(guī)劃問題：題：& 目標(biāo)函數(shù)：目標(biāo)函數(shù)： max z =x1+x2& 約束條件：約束條件： x1-x21 & - 3x1+2x26& x10，x20 19&從圖中可知該問從圖中可知該問題可行域無界，題可行域無界，目標(biāo)函數(shù)值可以目標(biāo)函數(shù)值可以增大到無窮大，增大到無窮大，成為無界解即無成為無界解即無最優(yōu)解。出現(xiàn)這最優(yōu)解。出現(xiàn)這種情況，一般說種情況，一般說明線性規(guī)劃模型明線性規(guī)劃模型有錯(cuò)誤，有錯(cuò)誤，該模型該模型中忽略了一些實(shí)中忽略了一些實(shí)際存在的必要的際存在的必要的約束條件。約束條件。1 2 3

20、4 x1-113-1x2Z=3=X1+X2Z=1=X1+X2Z=0=X1+X2-3x1+2x2=6X1-X2=120& 4線性規(guī)劃存在無可行解的情況。若在線性規(guī)劃存在無可行解的情況。若在例例1的數(shù)學(xué)模型中再增加一個(gè)約束條件的數(shù)學(xué)模型中再增加一個(gè)約束條件4x1+3x21200，顯然可見新的線性規(guī)劃的可行，顯然可見新的線性規(guī)劃的可行域?yàn)榭沼?，也即不存在滿足所有約束條件的域?yàn)榭沼?，也即不存在滿足所有約束條件的x1和和x2的解，當(dāng)然更不存在最優(yōu)解了。出現(xiàn)這種的解，當(dāng)然更不存在最優(yōu)解了。出現(xiàn)這種情況是由于約束條件自相矛盾導(dǎo)致的建模錯(cuò)誤。情況是由于約束條件自相矛盾導(dǎo)致的建模錯(cuò)誤。X1+X2=300

21、100400100300 x1x2X2=2504x1+3x2=120021目標(biāo)函數(shù)最小化的線性規(guī)劃問題目標(biāo)函數(shù)最小化的線性規(guī)劃問題 某公司由于生產(chǎn)需要，共需要某公司由于生產(chǎn)需要，共需要A，B兩種原料至兩種原料至少少350噸噸(A，B兩種材料有一定替代性兩種材料有一定替代性)，其中，其中A原料原料至少購(gòu)進(jìn)至少購(gòu)進(jìn)125噸。但由于噸。但由于A，B兩種原料的規(guī)格不同，兩種原料的規(guī)格不同，各自所需的加工時(shí)間也是不同的，加工每噸各自所需的加工時(shí)間也是不同的，加工每噸A原料需原料需要要2個(gè)小時(shí)，加工每噸個(gè)小時(shí)，加工每噸B原料需要原料需要1小時(shí)，而公司總共小時(shí)，而公司總共有有600個(gè)加工小時(shí)。又知道每噸個(gè)加

22、工小時(shí)。又知道每噸A原料的價(jià)格為原料的價(jià)格為2萬元，萬元，每噸每噸B原料的價(jià)格為原料的價(jià)格為3萬元，試問在滿足生產(chǎn)需要的萬元，試問在滿足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購(gòu)買前提下，在公司加工能力的范圍內(nèi)，如何購(gòu)買A，B兩種原料，使得購(gòu)進(jìn)成本最低兩種原料，使得購(gòu)進(jìn)成本最低?& 解：設(shè)解：設(shè)x1為購(gòu)進(jìn)原料為購(gòu)進(jìn)原料A的噸數(shù)，的噸數(shù)，x2為購(gòu)進(jìn)原料為購(gòu)進(jìn)原料B的的噸數(shù)。得到了此線性規(guī)劃的數(shù)學(xué)模型如下：噸數(shù)。得到了此線性規(guī)劃的數(shù)學(xué)模型如下：& 目標(biāo)函數(shù)：目標(biāo)函數(shù)： min f=2x1+3x2，& 約束條件：約束條件： x1+x2350，& x1125，2x

23、1+x2600, x1,x20. 22用圖解法來解：用圖解法來解： 100 300 500 600 x1100300500 x2X1=1252X1+X2=600X1+X2=3502x1+3x2=12002x1+3x2=800QQ點(diǎn)坐標(biāo)為點(diǎn)坐標(biāo)為x1=250,x2=10023& Q點(diǎn)坐標(biāo)為點(diǎn)坐標(biāo)為x1=250,x2=100。也即得到此線性規(guī)劃問。也即得到此線性規(guī)劃問題的最優(yōu)解，購(gòu)買題的最優(yōu)解，購(gòu)買A原料原料250噸，購(gòu)買噸，購(gòu)買B原料原料100噸，噸，可使成本最小，即可使成本最小，即2x1+3x2=2250+3100=800(萬元萬元)。& 分析分析: 可知購(gòu)買的原料可知購(gòu)買的原

24、料A與原料與原料B的總量為的總量為250+100=350(噸噸)正好達(dá)到約束條件的最低限，所需正好達(dá)到約束條件的最低限，所需的加工時(shí)間為的加工時(shí)間為2250+1100=600正好達(dá)到加工時(shí)間正好達(dá)到加工時(shí)間的最高限。而原料的最高限。而原料A的購(gòu)進(jìn)量的購(gòu)進(jìn)量250噸則比原料噸則比原料A購(gòu)進(jìn)量購(gòu)進(jìn)量的最低限的最低限125噸多購(gòu)進(jìn)了噸多購(gòu)進(jìn)了250-125=125噸，噸， 這個(gè)超過這個(gè)超過量在線性規(guī)劃中稱為剩余量。量在線性規(guī)劃中稱為剩余量。& 目標(biāo)函數(shù)在可行域內(nèi)目標(biāo)函數(shù)在可行域內(nèi)Q點(diǎn)處取得最小點(diǎn)處取得最小 值。值。Q點(diǎn)點(diǎn)的坐標(biāo)下面兩方程的交點(diǎn)：的坐標(biāo)下面兩方程的交點(diǎn)：60023502121x

25、xxx24& 25& 由上節(jié)可知，線性規(guī)劃的標(biāo)準(zhǔn)形式可寫為由上節(jié)可知，線性規(guī)劃的標(biāo)準(zhǔn)形式可寫為& 目標(biāo)函數(shù)：目標(biāo)函數(shù)：max Z=c1x1+c2x2+cnxn& 或：或： min f=c1x1+c2x2+cnxn & 約束條件：約束條件：a11x1+a12x2+a1nxn=b1& a21x1+a22x2+a2nxn=b2,& & am1x1+am2x2+am nxn=bm.& x1, x2,xn0.&其中其中Ci為第為第i個(gè)決策變量個(gè)決策變量Xi在目標(biāo)函數(shù)中的系數(shù)，在目標(biāo)函數(shù)中的系數(shù)，aij為第為第i個(gè)約個(gè)約束條件

26、中第束條件中第j個(gè)決策變量個(gè)決策變量xj的系數(shù)，的系數(shù)，bj為第為第j個(gè)約束條件中的常數(shù)個(gè)約束條件中的常數(shù)項(xiàng)，要求項(xiàng)，要求bj0。當(dāng)。當(dāng)bj 0 時(shí)，可在方程兩邊都乘以時(shí)，可在方程兩邊都乘以-1使使bj0。上。上節(jié)所提到的松弛變量和剩余變量都可以看成決策變量，也可以節(jié)所提到的松弛變量和剩余變量都可以看成決策變量，也可以用用Xi來表示而不用來表示而不用Si來表示。來表示。2.3圖解法的靈敏度分析圖解法的靈敏度分析26&同時(shí)滿足下面三個(gè)條件的模型稱為同時(shí)滿足下面三個(gè)條件的模型稱為標(biāo)準(zhǔn)型：標(biāo)準(zhǔn)型：&一、約束條件為等式。一、約束條件為等式。&二、每個(gè)變量（包括松弛變量和剩二、每

27、個(gè)變量（包括松弛變量和剩余變量）都要余變量）都要0。&三、約束條件的右邊常數(shù)項(xiàng)要三、約束條件的右邊常數(shù)項(xiàng)要0。 如何把模型化為標(biāo)準(zhǔn)型？27靈敏度分析靈敏度分析& 所謂靈敏度分析就是在建立數(shù)學(xué)模型和求得最所謂靈敏度分析就是在建立數(shù)學(xué)模型和求得最優(yōu)解之后，研究線性規(guī)劃的一些系數(shù)優(yōu)解之后，研究線性規(guī)劃的一些系數(shù)ci, aij, bj變化時(shí)，變化時(shí)，對(duì)最優(yōu)解產(chǎn)生什么影響對(duì)最優(yōu)解產(chǎn)生什么影響?靈敏度分析是非常重要的，靈敏度分析是非常重要的，首先是因?yàn)槭紫仁且驗(yàn)閏i, aij, bj這些系數(shù)都是估計(jì)值和預(yù)測(cè)值，這些系數(shù)都是估計(jì)值和預(yù)測(cè)值，不一定非常精確，再則即使這些系數(shù)值在某一時(shí)刻不一定非

28、常精確，再則即使這些系數(shù)值在某一時(shí)刻是精確值，它們也會(huì)隨著市場(chǎng)條件的變化而變化，是精確值，它們也會(huì)隨著市場(chǎng)條件的變化而變化，不會(huì)一成不變的。例如，原材料的價(jià)格、商品的售不會(huì)一成不變的。例如，原材料的價(jià)格、商品的售價(jià)、加工能力、勞動(dòng)力的價(jià)格等等的變化都會(huì)影響價(jià)、加工能力、勞動(dòng)力的價(jià)格等等的變化都會(huì)影響這些系數(shù)的變化，有了靈敏度分析就不必為了應(yīng)付這些系數(shù)的變化，有了靈敏度分析就不必為了應(yīng)付這些變化而不停地建立新的模型和求其新的最優(yōu)解，這些變化而不停地建立新的模型和求其新的最優(yōu)解，也不會(huì)由于系數(shù)的估計(jì)和預(yù)測(cè)的精確性而對(duì)所求得也不會(huì)由于系數(shù)的估計(jì)和預(yù)測(cè)的精確性而對(duì)所求得的最優(yōu)解存有不必要的懷疑。的最優(yōu)

29、解存有不必要的懷疑。& 以下用圖解法的靈敏度分析對(duì)目標(biāo)函數(shù)中的系以下用圖解法的靈敏度分析對(duì)目標(biāo)函數(shù)中的系數(shù)數(shù)ci以及對(duì)約束條件中的常數(shù)項(xiàng)以及對(duì)約束條件中的常數(shù)項(xiàng)bj進(jìn)行靈敏度分析。進(jìn)行靈敏度分析。28& 目標(biāo)函數(shù)目標(biāo)函數(shù) max Z=C1X1+C2X2= 50 x1+100 x2& 以例以例1來看一下來看一下Ci的變化是如何來影響其最優(yōu)解的。的變化是如何來影響其最優(yōu)解的。從例從例1中知道生產(chǎn)一個(gè)單位的中知道生產(chǎn)一個(gè)單位的I產(chǎn)品可以獲利產(chǎn)品可以獲利50元元(C1=50)，生產(chǎn)一個(gè)單位的，生產(chǎn)一個(gè)單位的產(chǎn)品可以獲利產(chǎn)品可以獲利100元元(C2=100)。在目前的生產(chǎn)條件下求

30、得生產(chǎn)。在目前的生產(chǎn)條件下求得生產(chǎn)I產(chǎn)品產(chǎn)品50單位，單位，生產(chǎn)生產(chǎn)產(chǎn)品產(chǎn)品250單位可以獲得最大利潤(rùn)。當(dāng)單位可以獲得最大利潤(rùn)。當(dāng)I、產(chǎn)品中產(chǎn)品中的某一產(chǎn)品的單位利潤(rùn)增加或減少時(shí)，往往都能意識(shí)到的某一產(chǎn)品的單位利潤(rùn)增加或減少時(shí)，往往都能意識(shí)到為了獲取最大利潤(rùn)就應(yīng)該增加或減少這一產(chǎn)品的產(chǎn)量，為了獲取最大利潤(rùn)就應(yīng)該增加或減少這一產(chǎn)品的產(chǎn)量，也就是改變最優(yōu)解。也就是改變最優(yōu)解。但是往往不能精確地定出這一產(chǎn)品但是往往不能精確地定出這一產(chǎn)品利潤(rùn)變化的上限與下限，利潤(rùn)在這個(gè)范圍內(nèi)變化時(shí)其最利潤(rùn)變化的上限與下限，利潤(rùn)在這個(gè)范圍內(nèi)變化時(shí)其最優(yōu)解不變，即仍然生產(chǎn)優(yōu)解不變，即仍然生產(chǎn)50單位的單位的I產(chǎn)品和產(chǎn)品和

31、250單位的單位的產(chǎn)產(chǎn)品而使獲利最大。品而使獲利最大。&注意最優(yōu)解不變不等于最優(yōu)值不變。注意最優(yōu)解不變不等于最優(yōu)值不變。&下面就用圖解方法定出其上限與下限。下面就用圖解方法定出其上限與下限。一、目標(biāo)函數(shù)中的系數(shù)一、目標(biāo)函數(shù)中的系數(shù)Ci的靈敏度分析的靈敏度分析29直線直線E(X1+X2=300)100400100300 x1x2直線直線F(X2=250）Z=27500=50 x1+100 x2B直線直線G(2X1+X2=400）CAD30& 直線直線E的方程為：的方程為：x1+x2=300,可改寫為：可改寫為：& x2=-x1+300, 其斜率為其斜率為-1。&a

32、mp; 同理同理 直線直線F :x2=0 x1+250 的斜率為的斜率為0。& 直線直線G :x2=-2x1+400 的斜率為的斜率為-2。& 而且目標(biāo)函數(shù)：而且目標(biāo)函數(shù)：z =c1x1+c2x2 可寫為：可寫為：& x2=-c1/c2x1+z/c2& 可知目標(biāo)函數(shù)的斜率為可知目標(biāo)函數(shù)的斜率為-c1/c2。 各直線的斜率各直線的斜率31& 下面討論下面討論Ci在什么范圍內(nèi)變動(dòng)時(shí)，最優(yōu)解位于哪些點(diǎn)。在什么范圍內(nèi)變動(dòng)時(shí)，最優(yōu)解位于哪些點(diǎn)。& 由上所述：由上所述：1、當(dāng)、當(dāng)-1-c1/c20 (2.1) 時(shí)，時(shí)，& 即直線即直線E的斜率的斜率

33、-c1/c2直線直線F的斜率。目標(biāo)函數(shù)的的斜率。目標(biāo)函數(shù)的直線在直線在E與與F之間變動(dòng)。故最優(yōu)解仍然為之間變動(dòng)。故最優(yōu)解仍然為B點(diǎn)。點(diǎn)。直線直線G(2X1+X2=400,斜率斜率-2）直線直線E(X1+X2=300,斜率斜率-1)100400100300 x1x2直線直線F(X2=250，斜率，斜率0）Z=27500=50 x1+100 x2BCAD斜率為斜率為-C1/C232&問題問題1：固定：固定C2，問，問C1在什么范圍內(nèi)變動(dòng)時(shí)，在什么范圍內(nèi)變動(dòng)時(shí)，B仍為最優(yōu)解仍為最優(yōu)解?& 設(shè)設(shè)C2=100, 則有則有-1-C1/1000, 0C1100. 即當(dāng)即當(dāng)C2=100， 0C

34、1100時(shí)時(shí)B仍為最優(yōu)解。仍為最優(yōu)解。& 問題問題2：固定：固定C1，問，問C2在什么范圍內(nèi)變動(dòng)時(shí)，在什么范圍內(nèi)變動(dòng)時(shí)，B仍為最優(yōu)解仍為最優(yōu)解?& 設(shè)設(shè)C1=50, 則有則有-1-50/C20, 50C2+. 即當(dāng)即當(dāng)C1=50， 50C2+時(shí)時(shí)B仍為最優(yōu)解。仍為最優(yōu)解。直線直線G(2X1+X2=400,斜率斜率-2）直線直線E(X1+X2=300,斜率斜率-1)100400100300 x1x2直線直線F(X2=250，斜率，斜率0）Z=27500=50 x1+100 x2BCAD斜率為斜率為-C1/C233& 2、同樣在、同樣在C1和和C2中一個(gè)值確定不變時(shí)，可求出

35、另一個(gè)值的變化中一個(gè)值確定不變時(shí)，可求出另一個(gè)值的變化范圍，使其最優(yōu)解在范圍，使其最優(yōu)解在C點(diǎn)點(diǎn)(或在或在A點(diǎn)，或在點(diǎn)，或在D點(diǎn)點(diǎn))。& 例如例如 當(dāng)當(dāng)0-C1/C2+時(shí)，最優(yōu)解在時(shí)，最優(yōu)解在A點(diǎn)（即從直線點(diǎn)（即從直線F反時(shí)針轉(zhuǎn)到反時(shí)針轉(zhuǎn)到X2軸）。軸）。 當(dāng)當(dāng)-2-C1/C2-1 時(shí)，最優(yōu)解在時(shí)，最優(yōu)解在C點(diǎn)。點(diǎn)。&當(dāng)當(dāng)-C1/C2-2 時(shí)，最優(yōu)解在時(shí)，最優(yōu)解在D點(diǎn)點(diǎn)直線直線G(2X1+X2=400,斜率斜率-2）直線直線E(X1+X2=300,斜率斜率-1)100400100300 x1x2直線直線F(X2=250，斜率，斜率0）Z=27500=50 x1+100 x2BC

36、AD斜率為斜率為-C1/C234& 3、如果當(dāng)、如果當(dāng)C1和和C2都變化時(shí)，則可以通過都變化時(shí)，則可以通過& -1 -C1/C20 (2.1)式，可以判斷式，可以判斷B點(diǎn)是否仍為其最優(yōu)點(diǎn)是否仍為其最優(yōu)解，解，& 例如當(dāng)例如當(dāng)C1=60；C2=55時(shí)，時(shí)， 因?yàn)橐驗(yàn)?C1/C2=-60/55=-1.09，不滿足不滿足(2.1)不等式，可知不等式，可知B點(diǎn)已不是其最優(yōu)解了，點(diǎn)已不是其最優(yōu)解了，& 但但-2(直線直線G的斜率的斜率)-60/55-1(直線直線E的斜率的斜率)，所以，所以此時(shí)此時(shí)C點(diǎn)點(diǎn)(其坐標(biāo)為其坐標(biāo)為x1=100，x2=200)為其最優(yōu)解。為其最優(yōu)解。

37、x2100400100300 x1CAD斜率為斜率為-C1/C2直線直線G(2X1+X2=400,斜率斜率-2）直線直線E(X1+X2=300,斜率斜率-1)35& 當(dāng)約束條件右邊系數(shù)當(dāng)約束條件右邊系數(shù)bj變化時(shí)，其線性變化時(shí)，其線性規(guī)劃的可行域也將變化，這樣就可能引起最規(guī)劃的可行域也將變化，這樣就可能引起最優(yōu)解的變化。為了說明這方面的靈敏度分析，優(yōu)解的變化。為了說明這方面的靈敏度分析，不妨假設(shè)例不妨假設(shè)例1中的設(shè)備臺(tái)時(shí)數(shù)增加了中的設(shè)備臺(tái)時(shí)數(shù)增加了10個(gè)臺(tái)時(shí)，個(gè)臺(tái)時(shí)，共有臺(tái)時(shí)數(shù)共有臺(tái)時(shí)數(shù)310個(gè)，這樣例個(gè)，這樣例1中的設(shè)備臺(tái)時(shí)數(shù)中的設(shè)備臺(tái)時(shí)數(shù)的約束條件就變?yōu)椋旱募s束條件就變?yōu)椋?amp

38、; x1+x2310,& 增加了增加了10個(gè)臺(tái)時(shí)，擴(kuò)大了可行域。個(gè)臺(tái)時(shí)，擴(kuò)大了可行域。二、二、 約束條件中右邊系數(shù)約束條件中右邊系數(shù)bj的靈敏度分析的靈敏度分析36圖圖26X1+X2=300100400100300 x1x2Z=50 x1+100 x2CADX1+X2=310BBC O由上圖可知新的可行域的最優(yōu)解為由上圖可知新的可行域的最優(yōu)解為B點(diǎn)，為點(diǎn)，為x1=250,x1+x2=310的解：的解：x1=60,x2=250. Z=28000,比原來比原來27500增加了增加了28000-27500=500元。元。每增加每增加1臺(tái)時(shí)獲利臺(tái)時(shí)獲利500/10=50元。元。 像這樣在約束條

39、件右邊常量增加一像這樣在約束條件右邊常量增加一個(gè)單位而使最優(yōu)目標(biāo)函數(shù)值得到改進(jìn)的數(shù)量稱之為這個(gè)約束條件的個(gè)單位而使最優(yōu)目標(biāo)函數(shù)值得到改進(jìn)的數(shù)量稱之為這個(gè)約束條件的對(duì)偶價(jià)格對(duì)偶價(jià)格。即臺(tái)時(shí)數(shù)約束條件的對(duì)偶價(jià)格為。即臺(tái)時(shí)數(shù)約束條件的對(duì)偶價(jià)格為50元元。 你知道對(duì)偶價(jià)格嗎？對(duì)偶價(jià)格的概念對(duì)偶價(jià)格的概念37& 從圖從圖27可以看到由于原料可以看到由于原料A增加了增加了10千克，使例千克，使例1中的原料中的原料A的約束條件變?yōu)榈募s束條件變?yōu)?2 X1+X2410,也使得可行域擴(kuò)也使得可行域擴(kuò) 大了，但是并不大了，但是并不影響它的最優(yōu)解和最優(yōu)值，它的最優(yōu)解仍影響它的最優(yōu)解和最優(yōu)值，它的最優(yōu)解仍 是

40、是B點(diǎn)，它的最優(yōu)值仍點(diǎn)，它的最優(yōu)值仍然是然是 27500，沒有任何的改進(jìn)，沒有任何的改進(jìn). (27500- 27500)10=0 & 這樣得到原料這樣得到原料A的對(duì)偶價(jià)格為零。同理可知原料的對(duì)偶價(jià)格為零。同理可知原料B對(duì)偶價(jià)格為對(duì)偶價(jià)格為不為零（為不為零（為50）。）。圖圖272X1+X2=410100400100300 x1x2Z=50 x1+100 x2CADBO下面來看例下面來看例1中的原料中的原料A如果增加如果增加10千克，將會(huì)對(duì)最優(yōu)解千克，將會(huì)對(duì)最優(yōu)解和最優(yōu)值產(chǎn)生什么影響。和最優(yōu)值產(chǎn)生什么影響。38& 其實(shí)這個(gè)問題不需要通過計(jì)算就很容易理解。由于當(dāng)產(chǎn)品其實(shí)這個(gè)問題不需

41、要通過計(jì)算就很容易理解。由于當(dāng)產(chǎn)品I生生產(chǎn)產(chǎn)50單位，產(chǎn)品單位，產(chǎn)品生產(chǎn)生產(chǎn)250單位時(shí)，原料單位時(shí)，原料A還有還有50千克沒有使用千克沒有使用(即松弛變量即松弛變量s2= 50)，如果再增加，如果再增加10千克原料，也只不過增加庫(kù)千克原料，也只不過增加庫(kù)存而已，是不會(huì)再增加利潤(rùn)的，故原料存而已，是不會(huì)再增加利潤(rùn)的，故原料A的對(duì)偶價(jià)格為零。的對(duì)偶價(jià)格為零。所以所以& 某一約束條件的對(duì)偶價(jià)格僅僅在某一范圍內(nèi)是有效的，當(dāng)這某一約束條件的對(duì)偶價(jià)格僅僅在某一范圍內(nèi)是有效的，當(dāng)這種約束條件的資源不斷的獲得，使得其種約束條件的資源不斷的獲得，使得其bi值不斷增大，由于其他值不斷增大，由于其他約束條件的限制，使得這約束條件的限制，使得這 種約束條件的資源用