線性規(guī)劃解的概念、性質(zhì)及圖解法

1、圖解法 線性規(guī)劃問題求解的 幾種可能結(jié)果 由圖解法得到的啟示,2.2 線性規(guī)劃解的概念、性質(zhì)及圖解法,例1的數(shù)學(xué)模型,目標函數(shù) Max Z = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,x1,x2,9 8 7 6 5 4 3 2 1 0,| 123456789,x1,x2,x1 + 2x2 8,目標函數(shù) Max Z = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,4x1 16,4 x2 12,圖解法,可行域,步驟一：由全部約束條件作圖求出可行域；,9 8 7 6 5 4 3 2 1 0

2、,| 123456789,x1,x2,目標函數(shù) Max Z = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,可行域,圖解法,B,9 8 7 6 5 4 3 2 1 0,x2,目標函數(shù) Max Z = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,2x1 + 3x2 = 6,圖解法,步驟二：作目標函數(shù)等值線，確定使目標函數(shù)最優(yōu)的移動方向；,9 8 7 6 5 4 3 2 1 0,x2,目標函數(shù) Max Z = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x

3、1、 x2 0,圖解法,x1+ 2x2=8 4x1 =16,Max Z=14,步驟三：平移目標函數(shù)的等值線，找出最優(yōu)點，算出最優(yōu)值。,圖解法求解步驟,由全部約束條件作圖求出可行域； 作目標函數(shù)等值線，確定使目標函數(shù)最優(yōu)的移動方向； 平移目標函數(shù)的等值線，找出最優(yōu)點，算出最優(yōu)值。,9 8 7 6 5 4 3 2 1 0,x2,改變約束條件或目標函數(shù)，解的結(jié)果如何？,線性規(guī)劃問題求解的 幾種可能結(jié)果,(a) 唯一最優(yōu)解,9 8 7 6 5 4 3 2 1 0,x2,線性規(guī)劃問題求解的 幾種可能結(jié)果,x1 + 2x2 = 8,目標函數(shù) Max Z = x1 + 2x2 約束條件 x1 + 2x2 8

4、 4x1 16 4x2 12 x1、 x2 0,(b)無窮多最優(yōu)解,(c)無界解 Max Z = x1 + x2 -2x1 + x2 4 x1 - x2 2 x1、 x2 0,x1,線性規(guī)劃問題求解的 幾種可能結(jié)果,(d)無可行解 Max Z = 2x1 + 3x2 x1 +2 x2 8 4 x1 16 4x2 12 -2x1 + x2 4 x1、 x2 0 可行域為空集,線性規(guī)劃問題求解的 幾種可能結(jié)果,圖解法的幾點結(jié)論:（由圖解法得到的啟示）,可行域是有界或無界的凸多邊形。 若線性規(guī)劃問題存在最優(yōu)解，它一定可以在可行域的頂點得到。 若兩個頂點同時得到最優(yōu)解，則其連線上的所有點都是最優(yōu)解。

5、解題思路：找出凸集的頂點，計算其目標函數(shù)值，比較即得。,練習(xí)：用圖解法求解LP問題,max z = 15x1 +25x2 s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0,L1,Z=250,目標函數(shù)變形：,x2=-3/5 x1+z/25,x2,x1,最優(yōu)解： x1=30 x2 =10 最優(yōu)值：zmax=700,B點是使z達到最大的唯一可行點,(30,10),A（0,20）,C（40, 0）,0,B,習(xí)題：用圖解法求下列線性規(guī)劃:,習(xí)題2 max z = 2x1 + 2x2 s.t. 2x1 x2 2 -x1 + 4x2 4 x1，x2 0,習(xí)題3 max z = 2x1

6、+ 2x2 s.t. x1 + x2 1 x1 3x2 3 x1 3 x1，x2 0,習(xí)題4 max z = 5x1 + 3x2 s.t. x1 + x2 1 x1 + 2x2 4 x1，x2 0,O,x1,x2,Note: 可行域為無界區(qū)域， 目標函數(shù)值可無限 增大，即解無界。 稱為無最優(yōu)解。,A(1,0),可行域為無界區(qū)域一定無最優(yōu)解嗎？,max z = 2x1 + 2x2 s.t. 2x1 x2 2 -x1 + 4x2 4 x1，x2 0,習(xí)題：用圖解法求下列線性規(guī)劃:,0,x1,x2,A (1,0),minZ,(多解) 線段AD上的任一點都是最優(yōu)解 minZ = 2,習(xí)題3 max z

7、 = 2x1 + 2x2 s.t. x1 + x2 1 x1 3x2 3 x1 3 x1，x2 0,(30,10),B(3,0),C(3,2),D(0,1),若min Z 換為max Z 則最優(yōu)解為?點,0,x1,x2,A (1,0),(30,10),B(4,0),D(0,1),習(xí)題4 max z = 5x1 + 3x2 s.t. x1 + x2 1 x1 + 2x2 4 x1，x2 0,C(0,2),無可行解,根據(jù)以上例題，進一步分析討論可知線性規(guī)劃的可行域和最優(yōu)解有以下幾種可能的情況 1.可行域為封閉的有界區(qū)域 (a)有唯一的最優(yōu)解； (b)有無窮多個最優(yōu)解； 2.可行域為非封閉的無界區(qū)域

8、 (c)有唯一的最優(yōu)解； (d)有無窮多個最優(yōu)解； (e)目標函數(shù)無界(即雖有可行解，但在可行域中，目標函數(shù)可以無限增大或無限減少)，因而沒有有限最優(yōu)解。 3.可行域為空集 (f)沒有可行解，原問題無最優(yōu)解,1.圖解法求解步驟,由全部約束條件作圖求出可行域； 作目標函數(shù)等值線，確定使目標函數(shù)最優(yōu)的移動方向； 平移目標函數(shù)的等值線，找出最優(yōu)點，算出最優(yōu)值。,小結(jié)：,1.可行域為封閉的有界區(qū)域 (a)有唯一的最優(yōu)解； (b)有無窮多個最優(yōu)解； 2.可行域為非封閉的無界區(qū)域 (c)有唯一的最優(yōu)解； (d)有無窮多個最優(yōu)解； (e)目標函數(shù)無界(即雖有可行解，但在 可行域中，目標函數(shù)可以無限增大或無限

9、 減少)，因而沒有有限最優(yōu)解。 3.可行域為空集 (f)沒有可行解，原問題無最優(yōu)解,2.線性規(guī)劃的可行域和最優(yōu)解,二、線性規(guī)劃解的有關(guān)概念,可行解、最優(yōu)解 基、基變量、非基變量 基本解、基本可行解 可行基、最優(yōu)基,定義 線性規(guī)劃的標準型： A 是mn矩陣，mn 并且r(A)=m。,（1）線性規(guī)劃的基,基 (basis)： B 是A中的一個非奇異（可逆）的 mm子矩陣，即|B|0 ，則稱B是線性規(guī)劃的一個基(或基矩陣)。,行滿秩的矩陣,當m=n時，基矩陣唯一； 當mn時，最多不超過 Cnm 。,【解】約束方程的系數(shù)矩陣為25矩陣,【例1-14】已知線性規(guī)劃,求所有基矩陣。,容易看出r(A)=2，

10、2階子矩陣最多有幾個？,C52=10,其中基矩陣有幾個？,基向量：基B中的列向量 pj (j=1,2,m);,基變量：與基向量對應(yīng)的決策變量 xj (j=1,2,m) ；,非基變量：與非基向量對應(yīng)的決策變量,非基向量：其余的列向量,（2）基向量、非基向量、基變量、非基變量,基向量： p1和p4,基變量：x1和x4 ，,基變量、非基變量是針對某一確定基而言的，不同的基對應(yīng)的基變量和非基變量也不同。,非基向量： p2 、p3和p5,非基變量：x2 、x3和x5,（3） 可行解：滿足約束條件（1-2）（1-3）的解為 可行解。所有可行解的集合為可行域。 （4） 最優(yōu)解：滿足式（1-1）的可行解，使得

11、目標函數(shù)達到最大值的可行解就是最優(yōu)解。,（5）基本解：對某一確定的基B，令非基變量等于零，由式（1-2）解出基變量，稱這組解為基本解。 （6）基本可行解：基本解是可行解則稱為是基本可行解（即非負的基本解） 。,顯然，只要基本解中的基變量的解滿足式（1.）的非負要求，那么這個基本解就是基本可行解。,在例1-14中，對來說，x1,x2是基變量，x3,x4，x5是非基變量，令x3=x4=x5=0，則式（1.）為,因|B1|，由克萊姆法則知，x1、x2有唯一解x12/5,x2=1 則基本解為,對B2來說，x1,x4為基變量，令非基變量x2,x3,x5為零，由式 （1.2）得到 ，x4=4，,由于 是基

12、本解，從而它是基本可行解，在 中x10, 因此不是可行解，也就不是基本可行解。,反之，可行解不一定是基本可行解 例如 滿足式（1.2）（1.3），但不是 任何基矩陣的基本解。,（8）可行基 基可行解對應(yīng)的基稱為可行基； 最優(yōu)基 基本最優(yōu)解對應(yīng)的基稱為最優(yōu)基；,（7）基本最優(yōu)解 最優(yōu)解是基本解稱為基本最優(yōu)解。,基本最優(yōu)解、最優(yōu)解、基本可行解、基本解、可行解的關(guān)系如下所示：,基本最優(yōu)解,基本可行解,可行解,最 優(yōu) 解,基本解,當最優(yōu)解唯一時，最優(yōu)解亦是基本最優(yōu)解， 當最優(yōu)解不唯一時，則最優(yōu)解不一定是基本最優(yōu)解。,系數(shù)陣A中可找出多個基B,非負的基本解就是基本可行解,每個基B都對應(yīng)于一個基本解,注意

13、：線性規(guī)劃的基本解、基本可行解和可行基只與線性規(guī)劃問題標準形式的約束條件有關(guān)。與目標函數(shù)無關(guān)。,（9）凸集,定義1 設(shè)集合 是 n 維歐氏空間中的一個點 集，如果 及實數(shù),則稱 K 是一個凸集。,幾何意義：如果集合中任意兩點連線上的一切點都在 該集合中，則稱該集合為凸集。,凸集,定義 2 設(shè) 則稱,為點 的一個凸組合。,（10）凸組合,（11）極點,【定理1.1】 若線性規(guī)劃可行解K非空,則K是凸集。,【定理1.2】線性規(guī)劃的可行解集合K的點X是極點的 充要條件為X是基本可行解。,定理1.3】若線性規(guī)劃有最優(yōu)解,則最優(yōu)值一定可以在可行解集合的某個極點上得到,最優(yōu)解就是極點的坐標向量。,定理1.2刻劃了可行解集的極點與基本可行解的對應(yīng)關(guān)系，極點是基本可行解，反之，基本可行解一定是極點，但它們并非一一 對應(yīng)，有可能兩個或幾個基本可行解對應(yīng)于同一極點（退化基本可行解時）。,(12) 線性規(guī)劃的基本定理,定理1.3描述了最優(yōu)解在可行解集中的位置，若最優(yōu)解唯一，則最優(yōu)解只能在某一極點上達到，若具有多重最優(yōu)解，則最優(yōu)解是某些極點的凸組合，從而最優(yōu)解是可行解集的極點或界點，不可能是可行解集的內(nèi)點 。,若線性規(guī)