線性規(guī)劃基本概念應(yīng)用標準型圖解法靈敏度分析

1、11008 . 092. 045. 01002121xxxx1008 . 092. 085. 073. 045. 03 . 01005432154321xxxxxxxxxx 有多少種配比方案？為什么？有多少種配比方案？為什么？5 , 2 , 1, 01008 . 092. 085. 073. 045. 03 . 0100. .250019001400700400543215432154321jxxxxxxxxxxxt sxxxxxMinZj 何為最好？何為最好？某工廠在計劃期內(nèi)要安排、兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗、資源的限制，如下表：問題：工廠應(yīng)分別生

2、產(chǎn)多少單位、產(chǎn)品才能使工廠獲利最多？ 1212122501003002400. .2500,1, 2jMaxZxxxxxxs txxj71.1 線性規(guī)劃問題及的數(shù)學(xué)模型線性規(guī)劃問題及的數(shù)學(xué)模型單位活動單位活動對對z的貢獻的貢獻 c1 c2 cn a11 a12 a1n b1a21 a22 a2n b2 am1 am2 amn bm資源可利用量資源可利用量 單位活動對資源的使用量單位活動對資源的使用量 1 2 n資源資源12 m表：表： 線性規(guī)劃模型所需數(shù)據(jù)線性規(guī)劃模型所需數(shù)據(jù)一般的產(chǎn)品組合問題：一般的產(chǎn)品組合問題：設(shè)有設(shè)有m種資源用于生產(chǎn)種資源用于生產(chǎn)n種不同產(chǎn)品，種不同產(chǎn)品，各種資源的擁有量

3、分別為各種資源的擁有量分別為bi( (i i= =1,2, , ,m).).生產(chǎn)單位第生產(chǎn)單位第j種產(chǎn)品種產(chǎn)品時將消費第時將消費第i種資源種資源aij單位，利潤為單位，利潤為cj元，見下表：元，見下表：81.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃模型的一般形式線性規(guī)劃模型的一般形式 Max (Min) z = c1 x1 + c2 x2 + + cn xns.ta11 x1 + a12 x2 + + a1n xn ( =, ) b1a21 x1 + a22 x2 + + a2n xn ( =, ) b2 am1 x1 + am2 x2 + + amn xn (=, ) b

4、mx1 ，x2 ， ，xn 0利潤系數(shù)利潤系數(shù)/成本系數(shù)成本系數(shù)資源限制量資源限制量技術(shù)系數(shù)技術(shù)系數(shù)/消耗系數(shù)消耗系數(shù)決策變量決策變量9線性規(guī)劃應(yīng)用舉例線性規(guī)劃應(yīng)用舉例例例: 某工廠要用三種原料某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如下表。的產(chǎn)品甲、乙、丙，數(shù)據(jù)如下表。假設(shè)混合沒有質(zhì)量損假設(shè)混合沒有質(zhì)量損耗耗。問：該廠應(yīng)如何安排生產(chǎn)，使利潤收入為最大？。問：該廠應(yīng)如何安排生產(chǎn)，使利潤收入為最大？配料問題配料問題10線性規(guī)劃應(yīng)用舉例線性規(guī)劃應(yīng)用舉例解：解：設(shè)設(shè) xij 表示第表示第 i 種（甲、乙、丙）產(chǎn)品中原料種（甲、乙、丙）產(chǎn)品中原料

5、j 的含量。的含量。這樣我們建立數(shù)學(xué)模型時，要考慮：這樣我們建立數(shù)學(xué)模型時，要考慮： 對于甲：對于甲： x11，x12，x13； 對于乙：對于乙： x21，x22，x23； 對于丙：對于丙： x31，x32，x33； 對于原料對于原料1： x11，x21，x31； 對于原料對于原料2： x12，x22，x32； 對于原料對于原料3： x13，x23，x33；如何建立線性規(guī)劃模型如何建立線性規(guī)劃模型? ? 請先自己完成請先自己完成11目標函數(shù)：目標函數(shù)：利潤最大，利潤利潤最大，利潤 = = 收入收入 - - 原料支出原料支出 約束條件：約束條件：規(guī)格要求規(guī)格要求 4 4 個；供應(yīng)量限制個；供應(yīng)量

6、限制 3 3 個。個。Max z = -15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 s.t. 0.5 x11-0.5 x12 -0.5 x13 0 （甲中原材料（甲中原材料1不少于不少于50%） -0.25x11+0.75x12 -0.25x13 0 （甲中原材料（甲中原材料2不超過不超過25%） 0.75x21-0.25x22 -0.25x23 0 （乙中原材料（乙中原材料1不少于不少于25%） -0.5 x21+0.5 x22 -0.5 x23 0 （乙中原材料（乙中原材料2不超過不超過50%） x11+x21+x31 100 (原料原料1，

7、供應(yīng)量限制），供應(yīng)量限制） x12+x22+x32 100 (原料原料2，供應(yīng)量限制），供應(yīng)量限制） x13+x23+x33 60 (原料原料3，供應(yīng)量限制），供應(yīng)量限制） xij0 ,i = 1,2,3; j = 1,2,3線性規(guī)劃應(yīng)用舉例線性規(guī)劃應(yīng)用舉例121350525 .42215231042502270213121321321322131321xxxxxxxxxxxxxxxxxx141.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃模型線性規(guī)劃模型 Max (Min) z = c1 x1 + c2 x2 + + cn xns.ta11 x1 + a12 x2 + + a

8、1n xn ( =, ) b1a21 x1 + a22 x2 + + a2n xn ( =, ) b2 am1 x1 + am2 x2 + + amn xn (=, ) bmx1 ，x2 ， ，xn 0隱含的假設(shè)隱含的假設(shè) 比例性：決策變量變化引起目標的改變量與決策變量改變量成比例性：決策變量變化引起目標的改變量與決策變量改變量成 正比正比 可加性：每個決策變量對目標和約束的影響?yīng)毩⒂谄渌兞靠杉有裕好總€決策變量對目標和約束的影響?yīng)毩⒂谄渌兞?連續(xù)性：每個決策變量取連續(xù)值連續(xù)性：每個決策變量取連續(xù)值 確定性：線性規(guī)劃中的參數(shù)確定性：線性規(guī)劃中的參數(shù)aij , bi , cj為確定值為確定值1

9、5線性規(guī)劃問題的應(yīng)用舉例線性規(guī)劃問題的應(yīng)用舉例(xn , yn)(x1 , y1)(x2 , y2)(xi , yi)ei = yi-yi16線性規(guī)劃問題的應(yīng)用舉例線性規(guī)劃問題的應(yīng)用舉例(回歸分析回歸分析)iiiiixyeMinZ|10nieexy-eetseeMinZiiiiiiiiii, 2 , 1, 0,. .2110102121無符號限制還可以加上一些特定的需求還可以加上一些特定的需求. .例如例如, ,要求必須過某要求必須過某一點一點. .新標準新標準: :最小化絕對誤差之和最小化絕對誤差之和. .17線性規(guī)劃問題的應(yīng)用舉例線性規(guī)劃問題的應(yīng)用舉例(回歸分析回歸分析)|eMaxMini

10、i10,0,. .1010eexyetseMinZii無符號限制新標準新標準: :最小化最大絕對誤差最小化最大絕對誤差. .18線性規(guī)劃問題的應(yīng)用舉例線性規(guī)劃問題的應(yīng)用舉例18 例在每周的不同工作日，一個郵局需要不同數(shù)量的例在每周的不同工作日，一個郵局需要不同數(shù)量的專職員工。下表給出了每天需要的專職員工的數(shù)量。專職員工。下表給出了每天需要的專職員工的數(shù)量。工會的章程規(guī)定，每個專職員工每周必須連續(xù)工作工會的章程規(guī)定，每個專職員工每周必須連續(xù)工作5 5天天，然后休息，然后休息2 2天。這個郵局希望通過只用專職員工來滿天。這個郵局希望通過只用專職員工來滿足它每天的需要。表述一個足它每天的需要。表述一

11、個LPLP，使得這個郵局可以利，使得這個郵局可以利用它使必須聘用的專職員工的數(shù)量最少。用它使必須聘用的專職員工的數(shù)量最少。19線性規(guī)劃問題的應(yīng)用舉例線性規(guī)劃問題的應(yīng)用舉例 解：設(shè) x1表示星期1開始工作,工作到星期5的人數(shù) x2表示星期2開始工作,工作到星期6的人數(shù) 類似定義x3 ,x4 ,x5x6 x7 20Minimizez = x1 + x2 + x3 + x4 + x5 + x6 + x7subject tox1 + x4 + x5 + x6 + x7 17Day Mon Tues Wed Thurs Fri Sat Sun Demand 17 13 15 19 14 16 11 x1

12、 + x2 + x5 + x6 + x7 13 x1 + x2 + x3 + x6 + x7 15 x1 + x2 + x3 + x4 + x7 19 x1 + x2 + x3 + x4 + x5 14 x2 + x3 + x4 + x5 + x6 16 x3 + x4 + x5 + x6 + x7 11 xj 0 for j = 1 to 721 是不是可以將決策變量設(shè)為第是不是可以將決策變量設(shè)為第j j天開始休天開始休息的工人數(shù)息的工人數(shù)? ?第第j j天工作的工人數(shù)至少是天工作的工人數(shù)至少是 d dj j. . 每一個工人休息每一個工人休息2 2天后工作天后工作5 5天天. . 結(jié)論結(jié)論

13、: :有些時候決策變量隱含了約束條件有些時候決策變量隱含了約束條件. . 做好很難做好很難, ,但一旦定義好了模型很簡單但一旦定義好了模型很簡單. .我們會在整數(shù)規(guī)劃中看到更多的例子我們會在整數(shù)規(guī)劃中看到更多的例子. .關(guān)于決策變量的選擇的啟示關(guān)于決策變量的選擇的啟示22關(guān)于模型的一些變形關(guān)于模型的一些變形 假定每天開始工作的工資不同假定每天開始工作的工資不同. .第第j j天開始工作天開始工作的工人的工資是每單人的工人的工資是每單人c cj j 元元. . Minimizez = c1 x1 + c2 x2 + c3 x3 + + c7 x723關(guān)于模型的一些變形關(guān)于模型的一些變形 假定每天

14、可以雇傭零時工假定每天可以雇傭零時工, ,第第j j天雇傭的零時工天雇傭的零時工的工資是每單人的工資是每單人PTPTj j 元元. . 設(shè)設(shè) y yj j = =第第j j天雇傭的零時工的人數(shù)天雇傭的零時工的人數(shù)24修改后的線性規(guī)劃?subject tox1 + x4 + x5 + x6 + x7 17x1 + x2 + x5 + x6 + x7 13 x1 + x2 + x3 + x6 + x7 15 x1 + x2 + x3 + x4 + x7 19 x1 + x2 + x3 + x4 + x5 14 x2 + x3 + x4 + x5 + x6 16 x3 + x4 + x5 + x6

15、+ x7 11 xj 0 for j = 1 to 7z = x1 + x2 + x3 + x4 + x5 + x6 + x7Minimize關(guān)于模型的一些變形（原始模型）關(guān)于模型的一些變形（原始模型）25Minimizez = c1x1 + c2x2 + c3x3 + c4x4 + c5x5 + c6x6 + c7x7subject tox1 + x4 + x5 + x6 + x7 + y1 17x1 + x2 + x5 + x6 + x7 + y2 13 x1 + x2 + x3 + x6 + x7 + y3 15 x1 + x2 + x3 + x4 + x7 + y4 19 x1 + x

16、2 + x3 + x4 + x5 + y5 14 x2 + x3 + x4 + x5 + x6 + y6 16 x3 + x4 + x5 + x6 + x7 + y7 11 xj 0 , yj 0 for j = 1 to 7+ PT1 y1 + PT2 y2 + + PT7 y726 假定第假定第j天的需求工人數(shù)量是天的需求工人數(shù)量是dj. 設(shè)設(shè)yj表示表示第第j天實際的工人數(shù)量天實際的工人數(shù)量.設(shè)第設(shè)第j天的費用定天的費用定義為第義為第j天超過需求的人數(shù)的某個函數(shù)天超過需求的人數(shù)的某個函數(shù),記記為為fj(yj dj),什么是最小費用的人員安排什么是最小費用的人員安排? NOTE: 這里的變

17、形是一個非線性規(guī)劃問這里的變形是一個非線性規(guī)劃問題題,不是線性規(guī)劃問題不是線性規(guī)劃問題. 我們可以設(shè)我們可以設(shè)sj = yj dj 為第為第j天超出的人數(shù)天超出的人數(shù).關(guān)于模型的一些變形關(guān)于模型的一些變形27原始的模型subject tox1 + x4 + x5 + x6 + x7 17x1 + x2 + x5 + x6 + x7 13 x1 + x2 + x3 + x6 + x7 15 x1 + x2 + x3 + x4 + x7 19 x1 + x2 + x3 + x4 + x5 14 x2 + x3 + x4 + x5 + x6 16 x3 + x4 + x5 + x6 + x7 11

18、xj 0 for j = 1 to 7z = x1 + x2 + x3 + x4 + x5 + x6 + x7Minimize28Minimizez = f1(s1) + f2(s2) + f3(s3) + f4(s4) + f5(s5) + f6(s6) + f7(s7)subject tox1 + x4 + x5 + x6 + x7 - s1 = 17x1 + x2 + x5 + x6 + x7 - s2 = 13 x1 + x2 + x3 + x6 + x7 - s3 = 15 x1 + x2 + x3 + x4 + x7 - s4 = 19 x1 + x2 + x3 + x4 + x5

19、 - s5 = 14 x2 + x3 + x4 + x5 + x6 - s6 = 16 x3 + x4 + x5 + x6 + x7 - s7 = 11 xj 0 , sj 0 for j = 1 to 729假設(shè)我們要求至少假設(shè)我們要求至少30%30%的工人能在星期天休息的工人能在星期天休息? ?(x1 + x2 )/(x1 + x2 + x3 + x4 + x5 + x6 + x7) .3關(guān)于模型的一些變形關(guān)于模型的一些變形:一個比率約束一個比率約束30 需要產(chǎn)生工人個數(shù)為整數(shù)值需要產(chǎn)生工人個數(shù)為整數(shù)值整數(shù)規(guī)劃問題整數(shù)規(guī)劃問題 考慮長期排班的問題考慮長期排班的問題一次對一次對6 6個星期進

20、行建模個星期進行建模 考慮短期排班的問題考慮短期排班的問題對午休換班進行建模對午休換班進行建模 考慮每個工人考慮每個工人允許工人有不同的偏好允許工人有不同的偏好關(guān)于模型的其他變形關(guān)于模型的其他變形3131 例某工廠要做例某工廠要做100100套鋼架，每套用長為套鋼架，每套用長為2.9 m,2.1 m,1.5 m2.9 m,2.1 m,1.5 m的圓鋼的圓鋼各一根。已知原料每根長各一根。已知原料每根長7.4 m7.4 m，問：應(yīng)如何下料，可使所，問：應(yīng)如何下料，可使所用原料最??？用原料最??？設(shè)設(shè) x x1 1, ,x x2 2, ,x x3 3, ,x x4 4, ,x x5 5 分別為上面分別

21、為上面 5 5 種方案下料的原材料根數(shù)。這樣我們建立如下種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學(xué)模型。的數(shù)學(xué)模型。 目標函數(shù)：目標函數(shù)： Min Min x x1 1 + + x x2 2 + + x x3 3 + + x x4 4 + + x x5 5 約束條件：約束條件： s.t. s.t. x x1 1 + 2 + 2x x2 2 + + x x4 4 100 100 2 2x x3 3 + 2 + 2x x4 4 + + x x5 5 100 100 3 3x x1 1 + + x x2 2 + 2 + 2x x3 3 + 3 + 3x x5 5 100 100 x x1 1,

22、,x x2 2, ,x x3 3, ,x x4 4, ,x x5 5 0 0套裁下料問題套裁下料問題 注1:教材這里有不同. 注2:怎么產(chǎn)生這里的下料方案?你有什么妙招? 注3:如果下料方案很多怎么辦?32套裁下料問題套裁下料問題某部門在今后五年內(nèi)考慮給下列項目投資，已知：某部門在今后五年內(nèi)考慮給下列項目投資，已知： 項目項目A A，從第一年到第四年每年年初需要投資，從第一年到第四年每年年初需要投資，并于次年末回收本利并于次年末回收本利115%115%； 項目項目B B，第三年初需要投資，到第五年末能回收，第三年初需要投資，到第五年末能回收本利本利125%125%，但規(guī)定最大投資額不超過，但規(guī)

23、定最大投資額不超過4 4萬元；萬元； 項目項目C C，第二年初需要投資，到第五年末能回收，第二年初需要投資，到第五年末能回收本利本利140%140%，但規(guī)定最大投資額不超過，但規(guī)定最大投資額不超過3 3萬元；萬元； 項目項目D D，五年內(nèi)每年初可購買公債，于當年末歸，五年內(nèi)每年初可購買公債，于當年末歸還，并加利息還，并加利息6%6%。 該部門現(xiàn)有資金該部門現(xiàn)有資金1010萬元，問它應(yīng)如何確定給這些萬元，問它應(yīng)如何確定給這些項目每年的投資額，使到第五年末擁有的資金的項目每年的投資額，使到第五年末擁有的資金的本利總額為最大本利總額為最大? ?33連續(xù)投資問題連續(xù)投資問題34項目 第一年 第二年 第

24、三年 第四年 第五年 A x1A x2A x3A x4A / B / / x3B / / C / x2C / / / D x1D x2D x3D x4D x5D 以xiA,xiB,xiC,xiD(i=1,2,，5)分別表示第i年年初給項目A，B，C，D的投資額，它們都是待定的未知變量。投資額應(yīng)等于手中擁有的資金額投資額應(yīng)等于手中擁有的資金額355 , 2 , 1, 0,3000040000006. 115. 1006. 115. 1006. 115. 1006. 110000006. 14 . 125. 115. 1max234353244213331222115224ixxxxxxxxxxx

25、xxxxxxxxxxxxxxxxxziDiCiBiACBDADDADADADBADDCADADCBA約束條件：目標函數(shù)： 注記注記1. 1.為什么第一個約束取等號為什么第一個約束取等號? ? 注記注記2. 2.如果對投資項目如果對投資項目B B要求，每次投要求，每次投資必須為資必須為10001000美元的整數(shù)倍，應(yīng)如何建美元的整數(shù)倍，應(yīng)如何建模？模？3637線性規(guī)劃應(yīng)用結(jié)束38 生產(chǎn)計劃問題的另一種建模方法生產(chǎn)計劃問題的另一種建模方法: : 設(shè)設(shè)s s1 1， s s2 2， s s3 3表示各資源的使用剩余量表示各資源的使用剩余量, ,則建立的模型為則建立的模型為 目標函數(shù)：目標函數(shù)：Max

26、 z = 2 x1 + 3 x2 約束條件：約束條件：s.t. s1 = 8- x1 - 2x2 s2 = 16-4 x1 s3 = 12-4x2 x1 , x2 , s1 , s2 , s3 0 s1 ， s2 ，s3稱為稱為松馳變量松馳變量（含義是資源的閑散量）（含義是資源的閑散量） 我們所建立的兩個模型間有什么關(guān)系？我們所建立的兩個模型間有什么關(guān)系？ 兩個問題等價兩個問題等價. .1.1 線性規(guī)劃問題及數(shù)學(xué)模型線性規(guī)劃問題及數(shù)學(xué)模型39 問題討論問題討論1042321xxx0104244321ssxxx412324100sxxx40目標函數(shù)約定是極大化目標函數(shù)約定是極大化Max;Max;

27、 約束條件均用等式表示約束條件均用等式表示; ; 決策變量限于取非負值決策變量限于取非負值; ; 右端常數(shù)均為非負值右端常數(shù)均為非負值 ; ;410,. .21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcMaxZ424321kkkxxx注意注意: 在目標函數(shù)和約束條件中將所有的在目標函數(shù)和約束條件中將所有的xk用用xk1, xk2代替代替.44符號不受限制321321321321321,0,1382310.32xxxxxxxxxxxxtsxxxMinZ討論：討論：如何下手？標準化過程排序如何下手？標準

28、化過程排序 -課堂練習(xí)課堂練習(xí)45令令433xxx460,1)(38)(2310)(. .00)(3265432143216432154321654321xxxxxxxxxxxxxxxxxxxxtsxxxxxxZMax0,1382310. .32654321432164321543214321xxxxxxxxxxxxxxxxxxxxtsxxxxZMax47 練習(xí)習(xí)題48（1）一般形式）一般形式 0,),(),(),(. .)(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax或49（1）標

29、準形式）標準形式 0,. .21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcMaxZ50111,2,. .01,2,njjjnijjijjMaxZc xa xbimstxjn51（3）矩陣形式）矩陣形式. .0TM axZcxAxbs tx其中其中 : 12( ,)Tncc cc12(,)nxx xxmnmmnnaaaaaaaaaA212222111211Tmbbbb),(2152（4）向量）向量矩陣形式：矩陣形式：1. .0TnjjjM axZcxP xbs tx其中：其中：njaaaPTmjjjj

30、, 2 , 1,),(21),(21nPPPA53練習(xí) 以以生產(chǎn)計劃問題生產(chǎn)計劃問題為例，寫出線性規(guī)為例，寫出線性規(guī)劃的劃的4種模型種模型 例例1.目標函數(shù)： Max z = 50 x1 + 100 x2 約束條件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E)得到最優(yōu)解： x1 = 50， x2 = 250 最優(yōu)目標值 z = 275002 圖圖 解解 法法 對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標系上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。 下面通過教材例1詳細講解其方法：2 圖圖 解解

31、 法法 (1)分別取決策變量X1 , X2 為坐標向量建立直角坐標系。在直角坐標系里，圖上任意一點的坐標代表了決策變量的一組值，例1的每個約束條件都代表一個半平面。x2x1X20X2=0 x2x1X10X1=02 圖圖 解解 法法（2）對每個不等式(約束條件)，先取其等式在坐標系中作直線，然后確定不等式所決定的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=4003002003004002 圖圖 解解 法法（3）把五個圖合并成一個圖，取各約束條件的公共部分，如圖2-1所示。100100 x2250 x2=250

32、200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400圖2-12 圖圖 解解 法法（4）目標函數(shù)z=50 x1+100 x2，當z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標函數(shù)值，稱之為“等值線”。平行移動等值線，當移動到B點時，z在可行域內(nèi)實現(xiàn)了最大化。A，B，C，D，E是可行域的頂點，對有限個約束條件則其可行域的頂點也是有限的。x1x2z=20000=50 x1+100 x2圖2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE練習(xí)練習(xí)2 圖圖 解

33、解 法法 重要結(jié)論： 如果線性規(guī)劃有最優(yōu)解，則一定有一個可行域的頂點對應(yīng)一個最優(yōu)解； 無窮多個最優(yōu)解。若將例1中的目標函數(shù)變?yōu)閙ax z=50 x1+50 x2，則線段BC上的所有點都代表了最優(yōu)解； 無界解。即可行域的范圍延伸到無窮遠，目標函數(shù)值可以無窮大或無窮小。一般來說，這說明模型有錯，忽略了一些必要的約束條件； 無可行解。若在例1的數(shù)學(xué)模型中再增加一個約束條件4x1+3x21200，則可行域為空域，不存在滿足約束條件的解，當然也就不存在最優(yōu)解了。定義：如果集合定義：如果集合C中任意兩點中任意兩點x1,x2連線上的所有點也都是集合連線上的所有點也都是集合C中的點，則稱集合中的點，則稱集合C

34、為為凸集凸集或用解析表達式表示為或用解析表達式表示為對任意對任意x1 1, ,x2 2C，有有 x1 1+(1+(1 ) )x2 2C,(0,(0 11),),則稱集合則稱集合C為為凸集凸集定義：定義：對任意對任意x1 1, ,x2 2C，不存在不存在x = = x1 1+(1-+(1- ) )x2 2C,(0,(0 11),),則稱則稱x是是集合集合C的的頂點頂點或或極點極點。 可行域是可行域是(有界或無界有界或無界)的凸集合的凸集合線性規(guī)劃基本定理線性規(guī)劃基本定理 定理定理. . 若線性規(guī)劃問題存在可行解若線性規(guī)劃問題存在可行解, , 則問題的可行域是凸集則問題的可行域是凸集. . 定理定

35、理. . 若可行域有界若可行域有界, , 線性規(guī)劃問題的目標函數(shù)一定可以在線性規(guī)劃問題的目標函數(shù)一定可以在其可行域的頂點上達到最優(yōu)。其可行域的頂點上達到最優(yōu)。 定理定理: :對于可行域是凸集對于可行域是凸集, ,目標函數(shù)是凸函數(shù)的問題目標函數(shù)是凸函數(shù)的問題( (稱為凸稱為凸優(yōu)化問題優(yōu)化問題),),局部最優(yōu)解一定是全局最優(yōu)解局部最優(yōu)解一定是全局最優(yōu)解. .63各種求解結(jié)果與各種類型的可行域之間的各種求解結(jié)果與各種類型的可行域之間的對應(yīng)關(guān)系對應(yīng)關(guān)系64 ，所以下圖中，所以下圖中 所示陰所示陰影區(qū)不可能是某個線性規(guī)劃的可行域，影區(qū)不可能是某個線性規(guī)劃的可行域，而而 所示陰影區(qū)則有可能。所示陰影區(qū)則有可能。 65下圖表示目標函數(shù)值遞增方向與其系數(shù)下圖表示目標函數(shù)值遞增方向與其系數(shù)a、b的關(guān)系，其中箭頭所指為目標函數(shù)值的關(guān)系，其中箭頭所指為目標函數(shù)值遞增的方向。遞增的方向。 a0 b b a0，b0 a a a0，b0，b0 3 圖解法的靈敏度分析圖解法的靈敏度分析 靈敏度分析靈敏度分析：建立數(shù)學(xué)模型和求得最優(yōu)解后，研究線性規(guī)劃的一個或多個參數(shù)（系數(shù)）ci , aij , bj 變化時，對