《線性規(guī)劃基本性質(zhì)》PPT課件.ppt

1、,第 1 章,Linear Programming,L P,線性規(guī)劃,基本性質(zhì),第1章 線性規(guī)劃的基本性質(zhì),2,1.1 線性規(guī)劃的一般模型 1.2 線性規(guī)劃的圖解法 1.3 線性規(guī)劃的標準形式 1.4 線性規(guī)劃的解及其性質(zhì) 1.5 線性規(guī)劃的應(yīng)用模型,第1章 線性規(guī)劃的基本性質(zhì),第1章 線性規(guī)劃的基本性質(zhì),3,1.1 線性規(guī)劃的一般模型,1.1.1 引 例 例1 產(chǎn)品配比問題（范例） 某廠擬生產(chǎn)甲、乙兩種產(chǎn)品，每件利潤分別為3、5百元。 甲、乙產(chǎn)品的部件各自在A、B兩個車間分別生產(chǎn)，每件甲、 乙產(chǎn)品的部件分別需要A、B車間的生產(chǎn)能力1、2工時。兩件 產(chǎn)品的部件最后都要在C車間裝配，裝配每件甲、

2、乙產(chǎn)品分別 需要3、4工時，三車間每天可用于生產(chǎn)這兩種產(chǎn)品的工時分別 為8、12、36，問應(yīng)如何安排生產(chǎn)這兩種產(chǎn)品才能獲利最多？,第1章 線性規(guī)劃的基本性質(zhì),4,1.1 線性規(guī)劃的一般模型,z,x1 x2,決策變量,z = 3x1 +5x2,max,0,目標函數(shù),x1 8 ,2x2 12 ,3x1 + 4x2 36 ,函數(shù)約束,x1 ， x2 0 ,非負性約束,s.t.,第1章 線性規(guī)劃的基本性質(zhì),5,1.1 線性規(guī)劃的一般模型,例2 配料問題 某化工廠根據(jù)一項合同要為用戶生產(chǎn)一種用甲、乙 兩種原料混合配制而成的特殊產(chǎn)品。甲、乙兩種原料都 含有A，B，C三種化學成分，其含量(%)是:甲為12，

3、 2， 3；乙為3，3，15。按合同規(guī)定，產(chǎn)品中三種化學 成分的含量(%)不得低于4，2，5。甲、乙原料成本為 每千克3，2元。 廠方希望總成本達到最小，則應(yīng)如何配制該產(chǎn)品？,第1章 線性規(guī)劃的基本性質(zhì),6,1.1 線性規(guī)劃的一般模型,x1,x2,min z = 3x1+2x2 12 x1 +3x2 4 2 x1 +3x2 2 s.t. 3 x1+15x2 5 x1 +x2 = 1 x1 , x2 0,配料平衡條件,z,第1章 線性規(guī)劃的基本性質(zhì),7,1.1 線性規(guī)劃的一般模型,1.1. 2 線性規(guī)劃的一般模型,一般LP模型的三類參數(shù)： 價值系數(shù)c j，消耗系數(shù)a ij，右端常數(shù)b i . L

4、P模型的三要素：決策變量，目標函數(shù)，約束條件.,s.t.,opt z = c1 x1+c2 x2+c3 x3+cn xn a11x1 +a12 x2+a1n xn b1 a21x1 +a22 x2+a2n xn b2 am1x1+am2x2+amn xn bm xj(或) 0, 或自由, j=1,2,n,第1章 線性規(guī)劃的基本性質(zhì),8,1.2 線性規(guī)劃的圖解法,1.2.1 圖解法的基本步驟,X*= (4, 6)T,z* = 42,1畫出可行域圖形 2畫出目標函數(shù)的 等值線及其法線 3確定最優(yōu)點,x1= 8,A(8,0),2x2= 12,D(0,6),3x1 + 4x2 = 36,z = 15,

5、z = 30,z 法向,z* = 42,邊界方程,第1章 線性規(guī)劃的基本性質(zhì),9,1.2 線性規(guī)劃的圖解法,1.2.2 幾點說明 實際運用時還須注意以下幾點: (1)若函數(shù)約束原型就是等式,則其代表的區(qū)域僅為一直線,而且問 題的整個可行域R(若存在的話)也必然在此直線上。 (2)在畫目標函數(shù)等值線時只須畫兩條就能確定其法線方向,為此, 只須賦給z 兩個適當?shù)闹怠?(3)在找出最優(yōu)點后,關(guān)于其坐標值有兩種確定方法: 在圖上觀測最優(yōu)點坐標值 通過解方程組得出最優(yōu)點坐標值,第1章 線性規(guī)劃的基本性質(zhì),10,1.2 線性規(guī)劃的圖解法,1.2.3 幾種可能結(jié)果 一、唯一解 如例1、例2都只有一個 最優(yōu)點

6、，屬于唯一解的情形。,二、多重解,z = 12,z* = 36,線段BC上無窮多個 點均為最優(yōu)解。,第1章 線性規(guī)劃的基本性質(zhì),11,1.2 線性規(guī)劃的圖解法,x1,x2,z*,三、無界解,R2,R1R2 = ,四、無可行解,+,R1,第1章 線性規(guī)劃的基本性質(zhì),12,1.3 線性規(guī)劃的標準形式,1.3.1 線性規(guī)劃問題的標準形式,max z=c1x1+c2x2+c3x3+cnxn,s.t.,a11x1 +a12x2+ +a1nxn = b1 (0) a21x1 +a22x2+ +a2nxn = b2 (0) am1x1+am2x2+amnxn = bm (0) x1 , x2 , , xn

7、0,簡記為：,s.t.,xj 0, j=1, 2 , , n,max z =CTX,s.t.,AX = b,X 0,(M1):,(M2):,(M3):,(M),第1章 線性規(guī)劃的基本性質(zhì),13,1.3 線性規(guī)劃的標準形式,1.3.2 非標準形LP問題的標準化 一、目標函數(shù) min z = CTX 令 z= z max z= CTX 例：min z = 3x1 2x2 max z= 3x1 2x2 二、函數(shù)約束 bi0 兩邊同時乘以 -1 約束為形式 加上松弛變量 約束為形式 減去剩余變量 三、決策變量 若xk 0, 令 xk = xk,則 xk 0 若xk為自由變量, 令 xk = xk xk

8、且 xk,xk 0,- f (x),第1章 線性規(guī)劃的基本性質(zhì),14,1.3 線性規(guī)劃的標準形式,x1 +x3 = 8,2x2 +x4 = 12,3x1 + 4x2 +x5 = 36,x1 ， x2 ， x3 ，x4 ，x5 0,s.t.,范例,+0 x3+0 x4+0 x5,第1章 線性規(guī)劃的基本性質(zhì),15,1.3 線性規(guī)劃的標準形式,解:,max z= x1 2x2 3x3,s.t.,x1 2x2 x3 + x4 = 5 2x1 3x2 x3 - x5 = 6 x1 x2 x3 +x6 = 2 x1 , x4 , x5 , x6 0 , x3 0,例4 將下述LP問題化成標準形,第1章 線

9、性規(guī)劃的基本性質(zhì),16,1.3 線性規(guī)劃的標準形式,令,x2 = x2 x2 ，且 x2，x2 0,x3 = -x3,代入上式中，得,第1章 線性規(guī)劃的基本性質(zhì),17,1.4 線性規(guī)劃的解及其性質(zhì),1.4.1 線性規(guī)劃的解的概念 一、可行解: 滿足LP問題所有約束條件的X。 二、最優(yōu)解: 滿足目標要求的可行解X。 三、基本解: 只適用于標準形LP問題（M）。 (1) 基(矩陣) AX = b 設(shè)B為A的一個m階子矩陣，若|B|0,則稱B 為約束方程組AX=b或標準形LP問題(M)的一個 基（矩陣）。,第1章 線性規(guī)劃的基本性質(zhì),18,1.4 線性規(guī)劃的解及其性質(zhì),范 例,A =,x1 x2 x

10、3 x4 x5,a1 a2 a3 a4 a5,可取 B0=（a3 ,a4 ,a5）為基（| B0 |0）,這時 稱 a3 ,a4 ,a5 為基向量，而 a1 ,a2 為非基向量；稱 x3 ,x4 ,x5 為基變量，而 x1 ,x2 為非基變量。,第1章 線性規(guī)劃的基本性質(zhì),19,1.4 線性規(guī)劃的解及其性質(zhì),(2) 基本解 范例的標準形,max z = 3x1 + 5x2,s.t.,x1 +x3 = 8 2 x2 +x4 = 12 3x1 + 4x2 +x5 = 36 x1 , x2 , x3 , x4 , x5 0,取 B0=（a3 ,a4 ,a5）為基，令一切非基變量 x1= x2 = 0

11、, 可解得基變量 x3 = 8 ， x4 = 12 ， x5 = 36 則得一特解 X0 = ( 0，0，8，12，36 )T,稱為一個(關(guān)于 B0 為基的) 基本解。,第1章 線性規(guī)劃的基本性質(zhì),20,1.4 線性規(guī)劃的解及其性質(zhì),也可取 B1= ( a2 ,a3 ,a4 )為基,得 X1 = ( 0，9，8，- 6，0 )T 還可取 B2= ( a1 ,a2 ,a3 )為基,得 X2 = ( 4，6，4，0，0 )T 等等。 四、基本可行解 滿足非負性約束的基本解。 如 X0 ， X2 ；而 X1 不可行。 對基本(可行)解而言：在其分量中，若有一個或更多個基變量取值為 0，則稱其為一個退

12、化的基本(可行)解，否則為非退化的。 如設(shè)： X = ( 0，6，5， 0 ，0 )T 是一個基本可行解，其中 x5 =0 為基變量，則該X為退化的基本可行解。,第1章 線性規(guī)劃的基本性質(zhì),21,1.4 線性規(guī)劃的解及其性質(zhì),非退化的基本(可行)解， 并恰有 n m 個 0 分量。,基本可行解對應(yīng)的基，稱為可行基； 最優(yōu)基本解對應(yīng)的基，稱為最優(yōu)基。 如：基 B0= ( a2 ,a3 ,a4 ) 對應(yīng) X0 = ( 0，0，8，12，36 )T 可行 基 B1= ( a2 ,a3 ,a4 ) 對應(yīng) X1 = ( 0，9，8，- 6，0 )T 不可行 基 B2 = ( a1 ,a2 ,a3 ) 對

13、應(yīng) X2 = ( 4，6，4，0，0 )T,恰有 m 個非 0 分量，,為可行基,為非可行基,為最優(yōu)基,x*,x*,B*,第1章 線性規(guī)劃的基本性質(zhì),22,1.4 線性規(guī)劃的解及其性質(zhì),1.4.2 凸性的幾個基本概念 一、凸集 設(shè)S En，對任意兩點XS ，YS，若對滿足0 1的一切 實數(shù) ，都有 X+(1- )Y S 則稱S為凸集。,凸集,凸集,非凸集,非,表示S 中兩點 X，Y 連線上的任一點,凸集的幾何意義：凸集S中任意兩點 X，Y 連線上的點，都在凸集S中。,第1章 線性規(guī)劃的基本性質(zhì),23,1.4 線性規(guī)劃的解及其性質(zhì),二、極點 設(shè)凸集S En, XS，如果X不能用S中不同的兩點Y和

14、Z 表示為 X =Y+(1-)Z (01) 則稱X為S的一個極點。 三、 凸組合 設(shè)XiEn, 實數(shù)i 0,i = 1,2, , s,且i = 1，則稱 X = 1X1 + 2X2 + sXs 為點 X1，X2， ，Xs 的一個凸組合。,第1章 線性規(guī)劃的基本性質(zhì),24,1.4 線性規(guī)劃的解及其性質(zhì),1.4.3 線性規(guī)劃的解的性質(zhì) 性質(zhì)1：LP問題(M)的可行域 R = XAX=b, X 0 是凸集。 性質(zhì)2：LP問題(M)的一個基本可行解與可行域 R 的一個極點 互相對應(yīng)。 性質(zhì)3：線性規(guī)劃的基本定理 對于一個給定的標準型LP問題(M)來說： 若(M)有可行解，則必有基本可行解； 若(M)有

15、最優(yōu)解，則必有最優(yōu)基本解。 性質(zhì)4：若LP問題的可行域 R, 則 R 至少有一極點。 性質(zhì)5：LP問題可行域 R 的極點數(shù)目必為有限個。,第1章 線性規(guī)劃的基本性質(zhì),25,1.4 線性規(guī)劃的解及其性質(zhì),僅就標準形LP問題(M)說明其合理性。 因(M)是一個m階n維的LP問題，則從其系數(shù)陣的n列中 取出m列，所構(gòu)成其基的個數(shù)不超過, ,基本可行解的個數(shù), 基本解的個數(shù),而問題(M)的,枚舉法: 當m=50，n=100時，此時需要求解的50元50 階的線性方程組的個數(shù)為,=, 1029,這是一個天文數(shù)字！故需另尋其他有效方法。,第1章 線性規(guī)劃的基本性質(zhì),26,1.5 線性規(guī)劃的應(yīng)用模型,1.5.

16、1 生產(chǎn)計劃問題,某企業(yè)擬用m種資源生產(chǎn)n種產(chǎn)品，已知第i種 資源的數(shù)量為bi,其單價為pi,每生產(chǎn)一個單位第j種 產(chǎn)品所提供的產(chǎn)值為vj, 所消耗的第i種資源的數(shù)量 為aij。第j種產(chǎn)品的合同與指令性計劃的產(chǎn)量指標為 ej, 最高需求量為dj。 該企業(yè)應(yīng)如何擬定生產(chǎn)計劃？,第1章 線性規(guī)劃的基本性質(zhì),27,一、決策變量 設(shè)xj為第j種產(chǎn)品的計劃產(chǎn)量 二、約束條件 指標約束 xj ej , j = 1,2, ,n 需求約束 xj dj , j = 1,2, ,n 資源約束 三、目標函數(shù) 總產(chǎn)值,1.5 線性規(guī)劃的應(yīng)用模型, 總成本,第1章 線性規(guī)劃的基本性質(zhì),28,1.5 線性規(guī)劃的應(yīng)用模型,

17、令,xj ej , j =1,2, ,n xj dj,s.t.,則, 總利潤,z = z1 -z2,第1章 線性規(guī)劃的基本性質(zhì),29,1.5.2 食譜問題 有n種食品, 每種食品中含有m種營養(yǎng)成分。食品用 j = 1,2, ,n表示，養(yǎng)分用 i = 1,2, ,m表示。已知第 j 種 食品單價為 cj, 每天最大供量為 dj; 而每單位第 j種食品所含 第 i 種養(yǎng)分的數(shù)量為 aij。 假定某種生物每天對第 i 種養(yǎng)分的 需求量至少為 bi, 而每天進食數(shù)量限定在 h1, h2 范圍內(nèi)。 試求該生物的食譜，使總成本為最小。,1.5 線性規(guī)劃的應(yīng)用模型,第1章 線性規(guī)劃的基本性質(zhì),30,1.5

18、線性規(guī)劃的應(yīng)用模型,設(shè) xj 為每天提供給該生物食用的第 j 種食品的數(shù)量， 則該問題的數(shù)學模型為:,s.t.,0 xj dj , j=1,2,n,某廠制造某種部件，由2個B1零件, 3個B2零件配套組裝 而成。該廠有A1, A2, A3三種機床可加工這兩種零件，每種 機床的臺數(shù)，以及每臺機床的生產(chǎn)率如下表所示。 求產(chǎn)量最大的生產(chǎn)方案。,1.5. 3 產(chǎn)品配套問題,第1章 線性規(guī)劃的基本性質(zhì),31,1.5 線性規(guī)劃的應(yīng)用模型,一、決策變量 設(shè)以xij表示每臺Ai (i=1, 2, 3)機床每個工作日加工Bj( j = 1, 2 ) 零件的時間(單位:工作日)； z為B1, B2零件按 2: 3

19、 的比例配套的數(shù)量(套/日)。,x11,x12,x21,x22,x31,x32,第1章 線性規(guī)劃的基本性質(zhì),32,1.5 線性規(guī)劃的應(yīng)用模型,二、約束條件 工時約束, 配套約束,x11,x12,x21,x22,x31,x32,非線性，等價改寫成：,或,x11 + x12 = 1 x21 + x22 = 1 x31 + x32 = 1,z -35x11-35x21-20 x31 0,z -30 x12-30 x22-24x32 0,第1章 線性規(guī)劃的基本性質(zhì),33,1.5 線性規(guī)劃的應(yīng)用模型,則該問題的數(shù)學模型為:,max z,s.t.,x11 + x12 = 1 x21 + x22 = 1 x

20、31 + x32 = 1,z 35x11 35x21 20 x31 0,z 30 x12 30 x22 24x32 0,z, x11, x12, x21, x22, x31, x32 0,制造某種機床，需要 A,B,C三種軸件，其規(guī)格與數(shù)量如表 所示，各類軸件都用5.5米長的同一種圓鋼下料。 若計劃生產(chǎn)100臺機床，最少需要用多少根圓鋼？,1.5. 4 下料問題,第1章 線性規(guī)劃的基本性質(zhì),34,1.5 線性規(guī)劃的應(yīng)用模型,余料 j 1.2,找出全部 省料截法,2,3,4,5,1,1,1,0,0.3,1,0,2,0,0,2,1,0.1,0,0,1,0,2,4,1,0.7,第1章 線性規(guī)劃的基本

21、性質(zhì),35,1.5 線性規(guī)劃的應(yīng)用模型,min z = x1 + x2 + x3 + x4 + x5,s.t.,x1 +x2 100 x1 +2x3 +x4 200 2x2 +x3 +2x4 +4x5 400 x1， x2 ， x3， x4， x5 0,則該問題的數(shù)學模型為:,設(shè)第 j 種截法下料 xj 根。,第1章 線性規(guī)劃的基本性質(zhì),36,1.5 線性規(guī)劃的應(yīng)用模型,某化工廠要用三種原料 D，P，H 混合配制三種不同規(guī)格 的產(chǎn)品 A，B，C。有關(guān)數(shù)據(jù)如下：,1.5. 5 配料問題,應(yīng)如合配制，才能使利潤達到最大？,表1-10,表1-11,第1章 線性規(guī)劃的基本性質(zhì),37,1.5 線性規(guī)劃的應(yīng)用模型,一、決策變量 設(shè)以 xij 表示每天生產(chǎn)的 第 j 種產(chǎn)品中所含第 i 種原料 的數(shù)量(kg，右表)。,二、約束條件, 規(guī)格約束(據(jù)表1-10), 0.50, 0.25, 0.25, 0.50,第1章 線性