運籌學——第2章_線性規(guī)劃的圖解法

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

2、小時的規(guī)則下，如何安排勞動力，才能用最少的勞動力來滿如何安排勞動力，才能用最少的勞動力來滿足工作的需要。足工作的需要。 3& 6運輸問題。一個公司有若干個生產單位與銷售單運輸問題。一個公司有若干個生產單位與銷售單位，根據各生產單位的產量及銷售單位的銷量，如何制位，根據各生產單位的產量及銷售單位的銷量，如何制定調運方案，將產品運到各銷售單位而總的運費最小。定調運方案，將產品運到各銷售單位而總的運費最小。& 以上的這些問題，線性規(guī)劃都能成功地加以解決。以上的這些問題，線性規(guī)劃都能成功地加以解決。這些例子都有一個共同的特點這些例子都有一個共同的特點:& 首先，每個例子中都要求

3、達到某些數量上的最大化首先，每個例子中都要求達到某些數量上的最大化或最小化的目標。或最小化的目標。& 其次，所有線性規(guī)劃問題都是在一定的約束條件下其次，所有線性規(guī)劃問題都是在一定的約束條件下來追求其目標的。來追求其目標的。4 2.1 問題的提出問題的提出5如何建立模型？如何建立模型？6& 這個問題可以用以下的數學模型來加以描述。工廠目前要決這個問題可以用以下的數學模型來加以描述。工廠目前要決策的問題是生產多少個策的問題是生產多少個產品和生產多少個產品和生產多少個產品，把這個要決產品，把這個要決策的問題用變量策的問題用變量x1、x2來表示，則稱來表示，則稱x1和和x2為決策變量，

4、即決策為決策變量，即決策變量變量x1=生產生產I產品的數量，決策變量產品的數量，決策變量x2=生產生產產品的數量。產品的數量。& 用用x1和和x2的線性函數形式來表示工廠所要求的最大利潤的目標：的線性函數形式來表示工廠所要求的最大利潤的目標： max Z=50 x1+100 x2 （稱為目標函數）。（稱為目標函數）。& 其中其中max為最大化的符號為最大化的符號(最小化為最小化為min)；50和和100分別為單位產分別為單位產品品 、 的利潤。同樣也可以用的利潤。同樣也可以用x1和和x2的線性不等式來表示問題的線性不等式來表示問題的約束條件。對于臺時數的限制可以表示為：的約束條

5、件。對于臺時數的限制可以表示為： X1+X2300 & 同樣，兩種原材料的限量可分別表示為：同樣，兩種原材料的限量可分別表示為：& 2X1+X2400, X2250.& 除了上述約束外，顯然還應該有除了上述約束外，顯然還應該有x10，x20，因為，因為產品產品, 產產品的品的 產量是不能取負值的。綜上所述，就得到了例產量是不能取負值的。綜上所述，就得到了例1的數學模型的數學模型如下：如下：7& 目標函數：目標函數： max Z=50 x1+100 x2，& 滿足約束條件：滿足約束條件：x1+x2300，& 2 x1+x2400，& x22

6、50,& x10, x20.& 由于上述數學模型的目標函數為變量的線性函數，由于上述數學模型的目標函數為變量的線性函數，約束條件也為變量的線性等式或不等式，故此模型稱約束條件也為變量的線性等式或不等式，故此模型稱之為線性規(guī)劃。如果目標函數是變量的非線性函數，之為線性規(guī)劃。如果目標函數是變量的非線性函數，或約束條件中含有變量非線性的等式或不等式的數學或約束條件中含有變量非線性的等式或不等式的數學模型則稱之為非線性規(guī)劃。模型則稱之為非線性規(guī)劃。& 把滿足所有約束條件的解稱為該線性規(guī)劃的可行把滿足所有約束條件的解稱為該線性規(guī)劃的可行解。把使得目標函數值最大解。把使得目標函數值

7、最大(即利潤最大即利潤最大)的可行解稱的可行解稱為該線性規(guī)劃的最優(yōu)解，此目標函數值稱為最優(yōu)目標為該線性規(guī)劃的最優(yōu)解，此目標函數值稱為最優(yōu)目標函數值，簡稱最優(yōu)值。函數值，簡稱最優(yōu)值。8& 1要正確理解所要解決的問題，要搞清在什么條件要正確理解所要解決的問題，要搞清在什么條件下，追求什么樣的目標。下，追求什么樣的目標。& 2定義決策變量，每一個問題都用一組決策變量定義決策變量，每一個問題都用一組決策變量(X1，X2, , Xn)表示任何一個方案；這組決策變量的值就代表示任何一個方案；這組決策變量的值就代表一個具體方案，一般這些變量取值是非負的。表一個具體方案，一般這些變量取值是非負

8、的。& 3用決策變量的線性函數形式寫出所要追求的目標，用決策變量的線性函數形式寫出所要追求的目標，稱之為目標函數，按問題的不同，要求目標函數實現最稱之為目標函數，按問題的不同，要求目標函數實現最大化或最小化。大化或最小化。& 4用一組決策變量的等式或不等式來表示在解決問用一組決策變量的等式或不等式來表示在解決問題過程上所必須遵循的約束條件。題過程上所必須遵循的約束條件。& 滿足以上滿足以上2、3、4三個條件的數學模型稱之為線性規(guī)三個條件的數學模型稱之為線性規(guī)劃的數學模型，其一般形式為劃的數學模型，其一般形式為:對于一般線性規(guī)劃問題的建模過程。應注意對于一般線性規(guī)劃問題的

9、建模過程。應注意如下幾個問題：如下幾個問題：9線性規(guī)劃的數學模型的一般形式為線性規(guī)劃的數學模型的一般形式為:& 目標函數：目標函數：& max (min) Z=c1x1+c2x2+cnxn& 約束條件：約束條件：& a11x1+a12x2+a1nxn( =, ) b1,& a21x1+a22x2+a2nxn( =, ) b2,& & am1x1+am2x2+amnxn( =, ) bm,& x1, x2, , xn0.10& 對于只包含兩個決策變量的線性規(guī)劃問題，可對于只包含兩個決策變量的線性規(guī)劃問題，可以用圖解法來求解。

10、大于兩個決策變量不能用圖解以用圖解法來求解。大于兩個決策變量不能用圖解法來解了。法來解了。& 圖解法圖解法.首先把每個約束條件（代表一個平面）首先把每個約束條件（代表一個平面）畫在二維坐標軸上。畫在二維坐標軸上。100300100300X1+X2=300 x1x22.2 圖圖 解解 法法111004001003002X1+X2=400 x1x2100100300X2=250 x1x212X1+X2=300100400100300 x1x2X2=2502x1+x2=400Z=10000=50 x1+100 x2Z=27500=50 x1+100 x2B 陰影部分的每陰影部分的每一點一點(

11、包括邊界包括邊界線線)都是這個線都是這個線性規(guī)劃的可行性規(guī)劃的可行解，而此公共解，而此公共部分是例部分是例1的可的可行解的集合，行解的集合，稱為可行域。稱為可行域。B點為最優(yōu)解，坐標為（點為最優(yōu)解，坐標為（50，250）Z=0=50 x1+100 x213問題的解：問題的解：& 最佳決策為最佳決策為x1=50, x2=250，此時，此時z=27500。 這說明該廠的最優(yōu)生產計劃方案是生產這說明該廠的最優(yōu)生產計劃方案是生產I產品產品50單位，單位，生產生產產品產品250單位，可得最大利潤單位，可得最大利潤27500元。元。& 把把x1=50, x2=250代入約束條件得：代入約束

12、條件得：& 50+250=300臺時設備臺時設備& 250+250=350千克原料千克原料A，& 1250=250千克原料千克原料B& 這表明了生產這表明了生產50單位單位產品和產品和250單位單位產品將消產品將消耗完所有可使用的設備臺時數和原料耗完所有可使用的設備臺時數和原料B，但對原料，但對原料A來來說只消耗了說只消耗了350千克，還有千克，還有(400350)=50千克沒有千克沒有使用。使用。在線性規(guī)劃中，對一個在線性規(guī)劃中，對一個約束條件中沒使用的資約束條件中沒使用的資源或能力的大小稱之為松弛量。源或能力的大小稱之為松弛量。14松弛變量和線性規(guī)劃標準化松

13、弛變量和線性規(guī)劃標準化&為了把一個線性規(guī)劃標準化，需要有代表沒使用的為了把一個線性規(guī)劃標準化，需要有代表沒使用的資源或能力的變量，稱之為松弛變量，記為資源或能力的變量，稱之為松弛變量，記為Si。顯。顯然這些松弛變量對目標函數不會產生影響，可以在然這些松弛變量對目標函數不會產生影響，可以在目標函數中把這些松弛變量的系數看成零，加了松目標函數中把這些松弛變量的系數看成零，加了松弛變量后我們得到如下的例弛變量后我們得到如下的例1的數學模型：的數學模型：& 目標函數：目標函數： & max Z=50 x1+100 x2+0s1+0s2+0s3，& 約束條件：約束條件：

14、x1+x2+s1=300,& 2x1+x2+s2=400,& x2+s3=250,& x1,x2,s1,s2,s3015& 像這樣把所有的約束條件都寫成等式，稱為線性像這樣把所有的約束條件都寫成等式，稱為線性規(guī)劃模型的標準化，所得結果稱為線性規(guī)劃的標準形規(guī)劃模型的標準化，所得結果稱為線性規(guī)劃的標準形式。在標準型中式。在標準型中 bj(右邊常量右邊常量)都要大于等于零，都要大于等于零， 對某對某個個bj小于零時，只要方程兩邊都乘以小于零時，只要方程兩邊都乘以(-1)即可。即可。&實際上以后可看到應同時具備如下三個條件的模型實際上以后可看到應同時具備如下三個

15、條件的模型才是標準型：才是標準型：&一是約束條件必須化為等式；二是所有變量必須化一是約束條件必須化為等式；二是所有變量必須化為大于或者等于零；三是約束條件中的右端常數項必為大于或者等于零；三是約束條件中的右端常數項必須是大于或者等于零。須是大于或者等于零。& 對例對例1 的最優(yōu)解的最優(yōu)解 x1=50,x2=250來說，松弛變量的值來說，松弛變量的值如下所示：如下所示：& 約束條件約束條件 松弛變量的值松弛變量的值& 設備臺時數設備臺時數 s1=0& 原料原料A s2=50 & 原料原料B s3=016&習題習題1：&目標函數：目標

16、函數： max Z=6x1+2x2，& 滿足約束條件：滿足約束條件：2x1+3x29，& 4x1+7x24，& x10, x20.&1、用圖解法求解、用圖解法求解&2、寫出線性規(guī)劃問題的標準形式、寫出線性規(guī)劃問題的標準形式&3、求出此線性規(guī)劃問題的兩個松弛變量的值、求出此線性規(guī)劃問題的兩個松弛變量的值17線性規(guī)劃問題解的有如下特點：線性規(guī)劃問題解的有如下特點：& 1如果某一個線性規(guī)劃問題有最優(yōu)解，則一如果某一個線性規(guī)劃問題有最優(yōu)解，則一定有一個可行域的頂點對應一個最優(yōu)解。定有一個可行域的頂點對應一個最優(yōu)解。& 2線性規(guī)劃存在有無窮

17、多個最優(yōu)解的情況。線性規(guī)劃存在有無窮多個最優(yōu)解的情況。若將例若將例1中的目標函數變?yōu)榍笾械哪繕撕瘮底優(yōu)榍髆ax Z =50 x1+50 x2，則可見代表目標函數的直線平移到最優(yōu)位置后將則可見代表目標函數的直線平移到最優(yōu)位置后將和直線和直線x1+x2=300重合。詳見下圖。重合。詳見下圖。& 此時不僅頂點此時不僅頂點B，C都代表了最優(yōu)解，而且都代表了最優(yōu)解，而且線段線段BC上的所有點都代表了最優(yōu)解，這樣最優(yōu)上的所有點都代表了最優(yōu)解，這樣最優(yōu)解就有無窮多個了。當然這些最優(yōu)解都對應著相解就有無窮多個了。當然這些最優(yōu)解都對應著相同的最優(yōu)值（只有一個）：同的最優(yōu)值（只有一個）：& 50

18、x1+50 x2=5050+50250=15000。 18X1+X2=300100400100300 x1x2X2=2502x1+x2=400Z=10000=50 x1+50 x2Z=15000=50 x1+50 x2BZ=0=50 x1+50 x219 線性規(guī)劃存在無界解，即無線性規(guī)劃存在無界解，即無最優(yōu)解的情況。對下述線性規(guī)劃問最優(yōu)解的情況。對下述線性規(guī)劃問題：題：& 目標函數：目標函數： max z =x1+x2& 約束條件：約束條件： x1-x21 & - 3x1+2x26& x10，x20 20&從圖中可知該問從圖中可知該問題可行域無界，題可行

19、域無界，目標函數值可以目標函數值可以增大到無窮大，增大到無窮大，成為無界解即無成為無界解即無最優(yōu)解。出現這最優(yōu)解。出現這種情況，一般說種情況，一般說明線性規(guī)劃模型明線性規(guī)劃模型有錯誤，有錯誤，該模型該模型中忽略了一些實中忽略了一些實際存在的必要的際存在的必要的約束條件。約束條件。1 2 3 4 x1-113-1x2Z=3=X1+X2Z=1=X1+X2Z=0=X1+X2-3x1+2x2=6X1-X2=121& 4線性規(guī)劃存在無可行解的情況。若在線性規(guī)劃存在無可行解的情況。若在例例1的數學模型中再增加一個約束條件的數學模型中再增加一個約束條件4x1+3x21200，顯然可見新的線性規(guī)劃的可

20、行，顯然可見新的線性規(guī)劃的可行域為空域，也即不存在滿足所有約束條件的域為空域，也即不存在滿足所有約束條件的x1和和x2的解，當然更不存在最優(yōu)解了。出現這種的解，當然更不存在最優(yōu)解了。出現這種情況是由于約束條件自相矛盾導致的建模錯誤。情況是由于約束條件自相矛盾導致的建模錯誤。X1+X2=300100400100300 x1x2X2=2504x1+3x2=120022目標函數最小化的線性規(guī)劃問題目標函數最小化的線性規(guī)劃問題 某公司由于生產需要，共需要某公司由于生產需要，共需要A，B兩種原料至兩種原料至少少350噸噸(A，B兩種材料有一定替代性兩種材料有一定替代性)，其中，其中A原料原料至少購進至少

21、購進125噸。但由于噸。但由于A，B兩種原料的規(guī)格不同，兩種原料的規(guī)格不同，各自所需的加工時間也是不同的，加工每噸各自所需的加工時間也是不同的，加工每噸A原料需原料需要要2個小時，加工每噸個小時，加工每噸B原料需要原料需要1小時，而公司總共小時，而公司總共有有600個加工小時。又知道每噸個加工小時。又知道每噸A原料的價格為原料的價格為2萬元，萬元，每噸每噸B原料的價格為原料的價格為3萬元，試問在滿足生產需要的萬元，試問在滿足生產需要的前提下，在公司加工能力的范圍內，如何購買前提下，在公司加工能力的范圍內，如何購買A，B兩種原料，使得購進成本最低兩種原料，使得購進成本最低?& 解：設解：

22、設x1為購進原料為購進原料A的噸數，的噸數，x2為購進原料為購進原料B的的噸數。得到了此線性規(guī)劃的數學模型如下：噸數。得到了此線性規(guī)劃的數學模型如下：& 目標函數：目標函數： min f=2x1+3x2，& 約束條件：約束條件： x1+x2350，& x1125，2x1+x2600, x1,x20. 23用圖解法來解：用圖解法來解： 100 300 500 600 x1100300500 x2X1=1252X1+X2=600X1+X2=3502x1+3x2=12002x1+3x2=800QQ點坐標為點坐標為x1=250,x2=10024& Q點坐標為點坐標為x1

23、=250,x2=100。也即得到此線性規(guī)劃問。也即得到此線性規(guī)劃問題的最優(yōu)解，購買題的最優(yōu)解，購買A原料原料250噸，購買噸，購買B原料原料100噸，噸，可使成本最小，即可使成本最小，即2x1+3x2=2250+3100=800(萬元萬元)。& 分析分析: 可知購買的原料可知購買的原料A與原料與原料B的總量為的總量為250+100=350(噸噸)正好達到約束條件的最低限，所需正好達到約束條件的最低限，所需的加工時間為的加工時間為2250+1100=600正好達到加工時間正好達到加工時間的最高限。而原料的最高限。而原料A的購進量的購進量250噸則比原料噸則比原料A購進量購進量的最低限的最

24、低限125噸多購進了噸多購進了250-125=125噸，噸， 這個超過這個超過量在線性規(guī)劃中稱為剩余量。量在線性規(guī)劃中稱為剩余量。& 目標函數在可行域內目標函數在可行域內Q點處取得最小點處取得最小 值。值。Q點點的坐標下面兩方程的交點：的坐標下面兩方程的交點：60023502121xxxx25& 26&習題習題2：&目標函數：目標函數： max Z=2x1+3x2，& 滿足約束條件：滿足約束條件：-3x1+x21，& 4x1+2x220，& 4x1-x2 10，& -x1+2x25，& x10, x20.&1、用圖

25、解法求解、用圖解法求解&2、寫出線性規(guī)劃問題的標準形式、寫出線性規(guī)劃問題的標準形式&3、求出此線性規(guī)劃問題的四個松弛變量的值、求出此線性規(guī)劃問題的四個松弛變量的值27& 由上節(jié)可知，線性規(guī)劃的標準形式可寫為由上節(jié)可知，線性規(guī)劃的標準形式可寫為& 目標函數：目標函數：max Z=c1x1+c2x2+cnxn& 或：或： min f=c1x1+c2x2+cnxn & 約束條件：約束條件：a11x1+a12x2+a1nxn=b1& a21x1+a22x2+a2nxn=b2,& & am1x1+am2x2+am nxn=bm.&a

26、mp; x1, x2,xn0.&其中其中Ci為第為第i個決策變量個決策變量Xi在目標函數中的系數，在目標函數中的系數，aij為第為第i個約個約束條件中第束條件中第j個決策變量個決策變量xj的系數，的系數，bj為第為第j個約束條件中的常數個約束條件中的常數項，要求項，要求bj0。當。當bj 0 時，可在方程兩邊都乘以時，可在方程兩邊都乘以-1使使bj0。上。上節(jié)所提到的松弛變量和剩余變量都可以看成決策變量，也可以節(jié)所提到的松弛變量和剩余變量都可以看成決策變量，也可以用用Xi來表示而不用來表示而不用Si來表示。來表示。2.3圖解法的靈敏度分析圖解法的靈敏度分析28&同時滿足下面三個

27、條件的模型稱為同時滿足下面三個條件的模型稱為標準型：標準型：&一、約束條件為等式。一、約束條件為等式。&二、每個變量（包括松弛變量和剩二、每個變量（包括松弛變量和剩余變量）都要余變量）都要0。&三、約束條件的右邊常數項要三、約束條件的右邊常數項要0。 如何把模型化為標準型？29靈敏度分析靈敏度分析& 所謂靈敏度分析就是在建立數學模型和求得最所謂靈敏度分析就是在建立數學模型和求得最優(yōu)解之后，研究線性規(guī)劃的一些系數優(yōu)解之后，研究線性規(guī)劃的一些系數ci, aij, bj變化時，變化時，對最優(yōu)解產生什么影響對最優(yōu)解產生什么影響?靈敏度分析是非常重要的，靈敏度分析是非常重

28、要的，首先是因為首先是因為ci, aij, bj這些系數都是估計值和預測值，這些系數都是估計值和預測值，不一定非常精確，再則即使這些系數值在某一時刻不一定非常精確，再則即使這些系數值在某一時刻是精確值，它們也會隨著市場條件的變化而變化，是精確值，它們也會隨著市場條件的變化而變化，不會一成不變的。例如，原材料的價格、商品的售不會一成不變的。例如，原材料的價格、商品的售價、加工能力、勞動力的價格等等的變化都會影響價、加工能力、勞動力的價格等等的變化都會影響這些系數的變化，有了靈敏度分析就不必為了應付這些系數的變化，有了靈敏度分析就不必為了應付這些變化而不停地建立新的模型和求其新的最優(yōu)解，這些變化而

29、不停地建立新的模型和求其新的最優(yōu)解，也不會由于系數的估計和預測的精確性而對所求得也不會由于系數的估計和預測的精確性而對所求得的最優(yōu)解存有不必要的懷疑。的最優(yōu)解存有不必要的懷疑。& 以下用圖解法的靈敏度分析對目標函數中的系以下用圖解法的靈敏度分析對目標函數中的系數數ci以及對約束條件中的常數項以及對約束條件中的常數項bj進行靈敏度分析。進行靈敏度分析。30& 目標函數目標函數 max Z=C1X1+C2X2= 50 x1+100 x2& 以例以例1來看一下來看一下Ci的變化是如何來影響其最優(yōu)解的。的變化是如何來影響其最優(yōu)解的。從例從例1中知道生產一個單位的中知道生產一個單

30、位的I產品可以獲利產品可以獲利50元元(C1=50)，生產一個單位的，生產一個單位的產品可以獲利產品可以獲利100元元(C2=100)。在目前的生產條件下求得生產。在目前的生產條件下求得生產I產品產品50單位，單位，生產生產產品產品250單位可以獲得最大利潤。當單位可以獲得最大利潤。當I、產品中產品中的某一產品的單位利潤增加或減少時，往往都能意識到的某一產品的單位利潤增加或減少時，往往都能意識到為了獲取最大利潤就應該增加或減少這一產品的產量，為了獲取最大利潤就應該增加或減少這一產品的產量，也就是改變最優(yōu)解。也就是改變最優(yōu)解。但是往往不能精確地定出這一產品但是往往不能精確地定出這一產品利潤變化的

31、上限與下限，利潤在這個范圍內變化時其最利潤變化的上限與下限，利潤在這個范圍內變化時其最優(yōu)解不變，即仍然生產優(yōu)解不變，即仍然生產50單位的單位的I產品和產品和250單位的單位的產產品而使獲利最大。品而使獲利最大。&注意最優(yōu)解不變不等于最優(yōu)值不變。注意最優(yōu)解不變不等于最優(yōu)值不變。&下面就用圖解方法定出其上限與下限。下面就用圖解方法定出其上限與下限。一、目標函數中的系數一、目標函數中的系數Ci的靈敏度分析的靈敏度分析31直線直線E(X1+X2=300)100400100300 x1x2直線直線F(X2=250）Z=27500=50 x1+100 x2B直線直線G(2X1+X2=400

32、）CAD32& 直線直線E的方程為：的方程為：x1+x2=300,可改寫為：可改寫為：& x2=-x1+300, 其斜率為其斜率為-1。& 同理同理 直線直線F :x2=0 x1+250 的斜率為的斜率為0。& 直線直線G :x2=-2x1+400 的斜率為的斜率為-2。& 而且目標函數：而且目標函數：z =c1x1+c2x2 可寫為：可寫為：& x2=-c1/c2x1+z/c2& 可知目標函數的斜率為可知目標函數的斜率為-c1/c2。 各直線的斜率各直線的斜率33& 下面討論下面討論Ci在什么范圍內變動時，最優(yōu)解位于哪些點。在什

33、么范圍內變動時，最優(yōu)解位于哪些點。& 由上所述：由上所述：1、當、當-1-c1/c20 (2.1) 時，時，& 即直線即直線E的斜率的斜率 -c1/c2直線直線F的斜率。目標函數的的斜率。目標函數的直線在直線在E與與F之間變動。故最優(yōu)解仍然為之間變動。故最優(yōu)解仍然為B點。點。直線直線G(2X1+X2=400,斜率斜率-2）直線直線E(X1+X2=300,斜率斜率-1)100400100300 x1x2直線直線F(X2=250，斜率，斜率0）Z=27500=50 x1+100 x2BCAD斜率為斜率為-C1/C234&問題問題1：固定：固定C2，問，問C1在什么范圍內變動

34、時，在什么范圍內變動時，B仍為最優(yōu)解仍為最優(yōu)解?& 設設C2=100, 則有則有-1-C1/1000, 0C1100. 即當即當C2=100， 0C1100時時B仍為最優(yōu)解。仍為最優(yōu)解。& 問題問題2：固定：固定C1，問，問C2在什么范圍內變動時，在什么范圍內變動時，B仍為最優(yōu)解仍為最優(yōu)解?& 設設C1=50, 則有則有-1-50/C20, 50C2+. 即當即當C1=50， 50C2+時時B仍為最優(yōu)解。仍為最優(yōu)解。直線直線G(2X1+X2=400,斜率斜率-2）直線直線E(X1+X2=300,斜率斜率-1)100400100300 x1x2直線直線F(X2=250，斜

35、率，斜率0）Z=27500=50 x1+100 x2BCAD斜率為斜率為-C1/C235& 2、同樣在、同樣在C1和和C2中一個值確定不變時，可求出另一個值的變化中一個值確定不變時，可求出另一個值的變化范圍，使其最優(yōu)解在范圍，使其最優(yōu)解在C點點(或在或在A點，或在點，或在D點點)。& 例如例如 當當0-C1/C2+時，最優(yōu)解在時，最優(yōu)解在A點（即從直線點（即從直線F反時針轉到反時針轉到X2軸）。軸）。 當當-2-C1/C2-1 時，最優(yōu)解在時，最優(yōu)解在C點。點。&當當-C1/C2-2 時，最優(yōu)解在時，最優(yōu)解在D點點直線直線G(2X1+X2=400,斜率斜率-2）直線直線

36、E(X1+X2=300,斜率斜率-1)100400100300 x1x2直線直線F(X2=250，斜率，斜率0）Z=27500=50 x1+100 x2BCAD斜率為斜率為-C1/C236& 3、如果當、如果當C1和和C2都變化時，則可以通過都變化時，則可以通過& -1 -C1/C20 (2.1)式，可以判斷式，可以判斷B點是否仍為其最優(yōu)點是否仍為其最優(yōu)解，解，& 例如當例如當C1=60；C2=55時，時， 因為因為-C1/C2=-60/55=-1.09，不滿足不滿足(2.1)不等式，可知不等式，可知B點已不是其最優(yōu)解了，點已不是其最優(yōu)解了，& 但但-2(直線直

37、線G的斜率的斜率)-60/55-1(直線直線E的斜率的斜率)，所以，所以此時此時C點點(其坐標為其坐標為x1=100，x2=200)為其最優(yōu)解。為其最優(yōu)解。x2100400100300 x1CAD斜率為斜率為-C1/C2直線直線G(2X1+X2=400,斜率斜率-2）直線直線E(X1+X2=300,斜率斜率-1)37&習題習題3：&目標函數：目標函數： max Z=4x1+5x2，& 滿足約束條件：滿足約束條件：3x1+x227，& 5x1+5x2=60，& 3x1+2x2 3， & x10, x20.&1、用圖解法求解、用圖解法求解&a

38、mp;2、假定、假定C2 值不變，求出使其最優(yōu)解不變的值不變，求出使其最優(yōu)解不變的C1 值范圍值范圍&3、假定、假定C1值不變，求出使其最優(yōu)解不變的值不變，求出使其最優(yōu)解不變的C2值范圍值范圍&4、 C2 值從值從5變?yōu)樽優(yōu)?， C1值不變，求出新的最優(yōu)解值不變，求出新的最優(yōu)解& 5、C1從從4變?yōu)樽優(yōu)?， C2 值從值從5變?yōu)樽優(yōu)?1，其最優(yōu)解變化嗎？，其最優(yōu)解變化嗎？38& 當約束條件右邊系數當約束條件右邊系數bj變化時，其線性變化時，其線性規(guī)劃的可行域也將變化，這樣就可能引起最規(guī)劃的可行域也將變化，這樣就可能引起最優(yōu)解的變化。為了說明這方面的靈敏度分析，優(yōu)

39、解的變化。為了說明這方面的靈敏度分析，不妨假設例不妨假設例1中的設備臺時數增加了中的設備臺時數增加了10個臺時，個臺時，共有臺時數共有臺時數310個，這樣例個，這樣例1中的設備臺時數中的設備臺時數的約束條件就變?yōu)椋旱募s束條件就變?yōu)椋?amp; x1+x2310,& 增加了增加了10個臺時，擴大了可行域。個臺時，擴大了可行域。二、二、 約束條件中右邊系數約束條件中右邊系數bj的靈敏度分析的靈敏度分析39圖圖26X1+X2=300100400100300 x1x2Z=50 x1+100 x2CADX1+X2=310BBC O由上圖可知新的可行域的最優(yōu)解為由上圖可知新的可行域的最優(yōu)解為B點，

40、為點，為x1=250,x1+x2=310的解：的解：x1=60,x2=250. Z=28000,比原來比原來27500增加了增加了28000-27500=500元。元。每增加每增加1臺時獲利臺時獲利500/10=50元。元。 像這樣在約束條件右邊常量增加一像這樣在約束條件右邊常量增加一個單位而使最優(yōu)目標函數值得到改進的數量稱之為這個約束條件的個單位而使最優(yōu)目標函數值得到改進的數量稱之為這個約束條件的對偶價格對偶價格。即臺時數約束條件的對偶價格為。即臺時數約束條件的對偶價格為50元元。 你知道對偶價格嗎？對偶價格的概念對偶價格的概念40& 從圖從圖27可以看到由于原料可以看到由于原料A增

41、加了增加了10千克，使例千克，使例1中的原料中的原料A的約束條件變?yōu)榈募s束條件變?yōu)?2 X1+X2410,也使得可行域擴也使得可行域擴 大了，但是并不大了，但是并不影響它的最優(yōu)解和最優(yōu)值，它的最優(yōu)解仍影響它的最優(yōu)解和最優(yōu)值，它的最優(yōu)解仍 是是B點，它的最優(yōu)值仍點，它的最優(yōu)值仍然是然是 27500，沒有任何的改進，沒有任何的改進. (27500- 27500)10=0 & 這樣得到原料這樣得到原料A的對偶價格為零。同理可知原料的對偶價格為零。同理可知原料B對偶價格為對偶價格為不為零（為不為零（為50）。）。圖圖272X1+X2=410100400100300 x1x2Z=50 x1+10

42、0 x2CADBO下面來看例下面來看例1中的原料中的原料A如果增加如果增加10千克，將會對最優(yōu)解千克，將會對最優(yōu)解和最優(yōu)值產生什么影響。和最優(yōu)值產生什么影響。41& 其實這個問題不需要通過計算就很容易理解。由于當產品其實這個問題不需要通過計算就很容易理解。由于當產品I生生產產50單位，產品單位，產品生產生產250單位時，原料單位時，原料A還有還有50千克沒有使用千克沒有使用(即松弛變量即松弛變量s2= 50)，如果再增加，如果再增加10千克原料，也只不過增加庫千克原料，也只不過增加庫存而已，是不會再增加利潤的，故原料存而已，是不會再增加利潤的，故原料A的對偶價格為零。的對偶價格為零。所以所以& 某一約束條件的對偶價格僅僅在某一范圍內是有效的，當這某一約束條件的對偶價格僅僅在某一范圍內是有效的，當這種約束條件的資源不斷的獲得，使得其種約束條件的