第2章 線規(guī)劃.ppt

1、運(yùn)籌學(xué) Operational research 第一章 線性規(guī)劃及單純形法,管理學(xué)院管理科學(xué)與工程 -郝海,如果規(guī)劃問題的數(shù)學(xué)模型中，決策變量的取值是連續(xù)的，目標(biāo)函數(shù)是決策變量的線性函數(shù)，約束條件是含決策變量的線性等式或不等式，則該類規(guī)劃問題的數(shù)學(xué)模型稱為線性規(guī)劃的數(shù)學(xué)模型。,一、定義,線性規(guī)劃介紹,二、線性規(guī)劃的重要地位 是運(yùn)籌學(xué)中應(yīng)用最廣泛的方法之一； 是運(yùn)籌學(xué)最基本的方法之一，整數(shù)規(guī)劃，目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃，網(wǎng)絡(luò)規(guī)劃都是以線性規(guī)劃為基礎(chǔ)的； 是解決稀缺資源最優(yōu)分配的有效方法，使付出的費(fèi)用最小或獲得的收益最大。,線性規(guī)劃介紹,三、線性規(guī)劃解決的管理問題：,合理利用線材問題； 配料問題；

2、投資問題； 產(chǎn)品生產(chǎn)計(jì)劃； 勞動力安排； 運(yùn)輸問題。,線性規(guī)劃介紹,四、研究對象,有一定的人力、財(cái)力、資源條件下，如何合理安排使用，效益最高 某項(xiàng)任務(wù)確定后，如何安排人、財(cái)、物，使之最省,線性規(guī)劃介紹,要求達(dá)到某些數(shù)量上的最大化或最小化； 在一定的約束條件下追求其目標(biāo)。,五、線性規(guī)劃問題的共同點(diǎn)：,線性規(guī)劃介紹,線性規(guī)劃的數(shù)學(xué)模型,一、問題的提出 二、線性規(guī)劃數(shù)學(xué)模型的一般形式 三、線性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)形式,例1 美佳公司計(jì)劃制造I，II兩種家電產(chǎn)品。已知各制造一件時分別占用的設(shè)備A、B的臺時、調(diào)試時間及A、B設(shè)備和調(diào)試工序每天可用于這兩種家電的能力、各售出一件時的獲利情況如表Il所示。問該

3、公司應(yīng)制造A、B兩種家電各多少件，使獲取的利潤為最大。,分析和表述問題,1、確定決策目標(biāo)，明確主要決策什么,目標(biāo) ： 利潤最大！,例1 美佳公司計(jì)劃制造I，II兩種家電產(chǎn)品。已知各制造一件時分別占用的設(shè)備A、B的臺時、調(diào)試時間及A、B設(shè)備和調(diào)試工序每天可用于這兩種家電的能力、各售出一件時的獲利情況如表Il所示。問該公司應(yīng)制造A、B兩種家電各多少件，使獲取的利潤為最大。,分析和表述問題,假設(shè)：利潤Z 家電I的數(shù)量x1 家電II的數(shù)量x2,例1 美佳公司計(jì)劃制造I，II兩種家電產(chǎn)品。已知各制造一件時分別占用的設(shè)備A、B的臺時、調(diào)試時間及A、B設(shè)備和調(diào)試工序每天可用于這兩種家電的能力、各售出一件時的

4、獲利情況如表Il所示。問該公司每天應(yīng)制造I、II兩種家電各多少件，使獲取的利潤為最大。,分析和表述問題,目標(biāo)函數(shù)：maxZ=2x1x2,例1 美佳公司計(jì)劃制造I，II兩種家電產(chǎn)品。已知各制造一件時分別占用的設(shè)備A、B的臺時、調(diào)試時間及A、B設(shè)備和調(diào)試工序每天可用于這兩種家電的能力、各售出一件時的獲利情況如表Il所示。問該公司應(yīng)制造A、B兩種家電各多少件，使獲取的利潤為最大。,分析和表述問題,2、要辨認(rèn)哪些是決策的關(guān)鍵影響因素，在選取這些關(guān)鍵因素時存在哪些資源和環(huán)境的限制,設(shè)備，調(diào)試工序時間受限制,例1 美佳公司計(jì)劃制造I，II兩種家電產(chǎn)品。已知各制造一件時分別占用的設(shè)備A、B的臺時、調(diào)試時間及

5、A、B設(shè)備和調(diào)試工序每天可用于這兩種家電的能力、各售出一件時的獲利情況如表Il所示。問該公司應(yīng)制造A、B兩種家電各多少件，使獲取的利潤為最大。,分析和表述問題,3、列出表述問題的各種基本要素，并確定各要素之間的關(guān)系。,5x215,6x1 +2x224,x1 +x25,x1 0, x2 0,用數(shù)學(xué)語言描述,解：用變量x1和x2分別表示美佳公司制造家電I和II的數(shù)量。,例2、生產(chǎn)計(jì)劃問題,A B 備用資源 煤 1 2 30 勞動日 3 2 60 倉庫 0 2 24 利潤 40 50,max Z= 40 x1 +50 x2,解:設(shè)產(chǎn)品A, B產(chǎn)量分別為變量x1 ， x2,例3,求：最低成本的原料混合

6、方案,解：設(shè)每單位添加劑中原料i的用量為xi(i =1,2,3,4),minZ= 2x1 + 5x2 +6x3+8x4,線性規(guī)劃模型特點(diǎn),決策變量：向量(x1 xn)T 決策人要考慮和控制的因素。非負(fù)。 約束條件：線性等式或不等式 目標(biāo)函數(shù)：Z=(x1 xn) 線性式，求Z極大或極小,19,線性規(guī)劃的一般式,max(min)Z=C1x1+ C2x2+Cnxn,簡寫為：,用向量形式表示：,線性規(guī)劃的適用情況,要解決的問題的目標(biāo)可以用數(shù)值指標(biāo)反映 對于要實(shí)現(xiàn)的目標(biāo)有多種方案可選擇 有影響決策的若干約束條件,線性規(guī)劃標(biāo)準(zhǔn)形式,線性規(guī)劃的標(biāo)準(zhǔn)形式 目標(biāo)函數(shù)：max 約束條件：= 變量符號：0,（一）一

7、般型,maxZ=c1x1+ c2x2+cnxn,其中 bi 0 (i=1,2,m),線性規(guī)劃標(biāo)準(zhǔn)型的幾種表示法,（二）矩陣型,maxZ=CX AX=b X 0 b0,C=(C1 C2 Cn ),(三) 向量型,P1 x1+ P2 x2 + +Pn xn=b,化標(biāo)準(zhǔn)型,(2)、約束條件,(4)、變量,(1)、目標(biāo)函數(shù),(3)、右端常數(shù),（1）目標(biāo)函數(shù),目標(biāo)函數(shù)為求最小值，,令Z = -Z,（2）約束條件,x3為松弛變量,x4為剩余變量,松弛變量或剩余變量在實(shí)際問題中分別表示未被充分利用的資源和超出的資源數(shù)，均未轉(zhuǎn)化為價值和利潤，所以引進(jìn)模型后它們在目標(biāo)函數(shù)中的系數(shù)均為零。,當(dāng)約束條件為“”時，,

8、當(dāng)約束條件為“”時，,轉(zhuǎn)化為：maxZ=40 x1+ 50 x2+0 x3 +0 x4+0 x5,例：max Z= 40 x1 +50 x2,松弛變量,例:,剩余變量,（3）右端常數(shù),右端項(xiàng)b0時，只需將等式或不等式兩端同乘(1)，則等式右端項(xiàng)必大于零。,（4）變量,a、x 0的情況，,令x1= x1- x1 ,b、x取值無約束的情況。,令x -x。,令x= x-x,c、x兩邊有約束的情況。,-6+6 x1+6 10+6 令x1 = x1 +6 0 x1 16,將 min Z = -x1+2x2 3x3,化為標(biāo)準(zhǔn)型,例：,解： 令x3 =x4 - x5, 加松弛變量x6,加剩余變量x7, 令Z

9、= -Z,maxZ= x1 2x2 +3x4 3x5,練 習(xí),補(bǔ)充作業(yè)、運(yùn)輸問題,從倉庫到工廠運(yùn)送單位原材料的成本，工廠對原材料的需求量，倉庫目前庫存分別如表所示，求成本最低的運(yùn)輸方案。,設(shè)xij為i 倉庫運(yùn)到 j工廠的原棉數(shù)量(i 1，2，3， j 1，2，3),minZ= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33,線性規(guī)劃的圖解法,定義1：滿足約束(1)、(2)的X=(x1 xn)T稱為LP問題的可行解，全部可行解的集合稱為可行域。,定義2：滿足(3)的可行解稱為LP問題的最優(yōu)解.,1、判別線性規(guī)劃問題的求解結(jié)局； 2、是在存在最

10、優(yōu)解的條件下，找出問題的最優(yōu)解。,1、在平面上建立直角坐標(biāo)系 2、圖示約束條件，找出可行域 3、圖示目標(biāo)函數(shù)和尋找最優(yōu)解,圖解法求解的目的：,圖解法的步驟：,例1、maxZ=40 x1+ 50 x2,(1)、建立坐標(biāo)系,x1+2x2 30 x1+2x2 =30 (0,15) (30,0),3x1+2x2 =60 (0,30) (20,0),2x2 =24,X1+2X2 30 3X1+2X2 60 2X2 24 X1 , X2 0,x1 0 x1 =0 (縱) x2 0 x2=0 (橫),(2)、確定可行域,解：,maxZ=40 x1+ 50 x2,(3)、求最優(yōu)解,解：x1 = 15, x2

11、= 7.5,Z=40 x1+50 x2 0=40 x1+50 x2 (0,0)， (10,-8),maxZ =975,maxZ=40 x1+ 50 x2,最優(yōu)解：BC線段 B點(diǎn) C點(diǎn) x(1)=(6,12) x(2)=(15,7.5) x= x(1)+(1-) x(2) (0 1),求解,maxZ=1200,無界解 無有限最優(yōu)解,無解 無可行解,max z=x1+3x2 x1+ x26 s.t. -x1+2x28 x1 0, x20,練 習(xí),max z=x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20,可行域,目標(biāo)函數(shù)等值線,最優(yōu)解,6,4,-8,6,0,x1,x2

12、,練 習(xí),由圖解法得到的啟示,(1)、線性規(guī)劃問題的解的情況有四種：唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解。,(3)、若有最優(yōu)解，定可在可行域的頂點(diǎn)得到。,(2)、若線性規(guī)劃可行域存在，則可行域是一個凸集。,(4)、解題思路是找出凸集的各頂點(diǎn)的最大目標(biāo)函數(shù)值。,線性規(guī)劃解的情況,當(dāng)目標(biāo)函數(shù)的直線族與某約束條件直線平行，且該問題有解時。,線性規(guī)劃解的情況,有解但可行域可伸展到無窮時,線性規(guī)劃解的情況,約束條件直線無公共區(qū)域。,線性規(guī)劃的單純形法,一、線性規(guī)劃的基本概念 二、單純形法的迭代原理 三、單純形法的計(jì)算步驟 四、單純形法的進(jìn)一步討論 五、單純形法小結(jié),n階行列式定義為n階方陣A中所有

13、取自不同行不同列的n個元素的乘積的代數(shù)和。,線性規(guī)劃的相關(guān)概念,線性規(guī)劃的相關(guān)概念,矩陣的秩矩陣A中，不為零的子式的最高階數(shù)，稱為矩陣A的秩。,逆設(shè)有n階方陣A，如果存在n階方陣B，滿足AB=BA=E，則稱A陣是可逆的，且稱B是A的逆矩陣。,線性規(guī)劃的相關(guān)概念,矩陣的初等變換： （1）對調(diào)矩陣的兩行或兩列； （2）以非零數(shù)k乘矩陣的某一行（列）的所有元素； （3）以數(shù)k乘矩陣的某行（列）的所有元素加到另一行（列）的對應(yīng)元素上去。,對方程組的系數(shù)矩陣A作初等行變換，得到新的方程組與原方程組同解。,基(基陣) 設(shè)A為約束方程組的mn階系數(shù)矩陣, (nm)，設(shè)其秩為m，B是矩陣A中的一個mm階的滿秩

14、子矩陣，稱B是線性規(guī)劃問題的一個基。,線性規(guī)劃的基本概念,如果矩陣A的滿秩子矩陣不是唯一的， 則基陣也是不唯一的,基向量基陣B中的每一個列向量Pj稱為基向量， 基變量與基向量對應(yīng)的變量稱為基變量， 非基變量基變量外的其他變量稱為非基變量。,線性規(guī)劃的基本概念,x1 x2 x3 x4 x5 x6,x4 x5 x6,線性規(guī)劃的基本概念,可行解滿足方程約束條件的解X（x1，x2，xn)T, 稱為線性規(guī)劃問題的可行解。全部可行解的集合稱為可行域。,線性規(guī)劃的基本概念,AX=b的求解,BXB +NXN=b BXB =b-NXN B-1 BXB = B-1 （b-NXN） XB = B-1 b - B-1

15、N XN,A=(B N) X=(XB XN )T,1.若XN0，,2.若同時B為單位矩陣，,則 XB = b， 即X=(b，0)為AX=b的一個解,基本解對應(yīng)于基B，X= 為AX=b的一個解，則 X為線性規(guī)劃問題的基本解或基解。,B-1 b 0,線性規(guī)劃的基本概念,基本可行解基B，基本解X= ，若B-1 b0，稱基解為基本可行解，也稱基可行解。,可行基對應(yīng)于基可行解的基稱為可行基。,線性規(guī)劃的基本概念,最優(yōu)解使目標(biāo)函數(shù)達(dá)到最大值的可行解， 稱為最優(yōu)解。,基變量x1、x2、x3，非基變量x4、x5、x6,基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0） 是基礎(chǔ)可行解，表

16、示可行域的一個極點(diǎn)。 目標(biāo)函數(shù)值為：z=20,基變量x1、x2、x4，非基變量x3、x5、x6,基礎(chǔ)解為 （x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0） 是基礎(chǔ)可行解，表示可行域的一個極點(diǎn)。 目標(biāo)函數(shù)值為：z=18,基變量x1、x2、x5，非基變量x3、x4、x6,基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0） 是基礎(chǔ)解，但不是可行解，不是一個極點(diǎn)。,基變量x1、x2、x6，非基變量x3、x4、x5,基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4） 是基礎(chǔ)可行解，表示可行域的一個極點(diǎn)。 目標(biāo)函數(shù)值為：z

17、=18,基變量x2、x3、x4，非基變量x1、x5、x6,基礎(chǔ)解為 （x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0） 是基礎(chǔ)解，但不是可行解。,基變量x1、x2、x3，非基變量x4、x5、x6,基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0） 是基礎(chǔ)可行解，表示可行域的一個極點(diǎn)。 目標(biāo)函數(shù)值為：z=15,基變量x1、x2、x3，非基變量x4、x5、x6,基礎(chǔ)解為 （x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10） 是基礎(chǔ)解但不是可行解。, 基本解中最多有m個非零分量。,定理1：線性規(guī)劃問題的可行域一定是

18、凸集。 定理2: 若線性規(guī)劃問題有最優(yōu)解,一定存在 一個 基可行解是最優(yōu)解。 定理3: 若線性規(guī)劃問題有最優(yōu)解，一定存在 一個基可行解是最優(yōu)解。,線性規(guī)劃的基本定理,基陣B,非基陣N,求出一個基本解，并判斷是不是可行解？,令X1 = X2 =0, 則 X3=30, X4=60, X5=24,求出基變量是x1 , x3 , x4的基本解，是不是可行解？,X=(1, 0, 3/2, 3/2)T 是 基本可行解,單純形法的迭代原理,找出一個基可行解,判斷是否最優(yōu),轉(zhuǎn)換到相鄰的基可行解,找到最優(yōu)解,否,是,一、確定初始基可行解,線性規(guī)劃問題的標(biāo)準(zhǔn)型總存在一個單位矩陣（P1,P2,Pm)。 當(dāng)約束條件為

19、時，加上松馳變量的系數(shù)矩陣即為單位矩陣。 當(dāng)約束條件為或時，可以構(gòu)造人工變量，人為產(chǎn)生一個單位矩陣。 基向量、基變量、非基向量、非基變量 X=(x1,x2,xm,0,0)T ,即為初始基可行解。,p1 p2 pm pm+1 pj pn,二、基可行解的轉(zhuǎn)換,兩個基可行解相鄰指的是它們之間變換且僅變換一個基變量。,對應(yīng)的系數(shù)矩陣的增廣矩陣為:,設(shè)X(0)=(x10,x20,xm0 , 0,0)T，則有,兩邊乘上一個正數(shù)0，得,因?yàn)榫€性規(guī)劃標(biāo)準(zhǔn)型滿足,存在：,令,所以X(1)是可行解。這樣就實(shí)現(xiàn)了從X(0)到X(1)的轉(zhuǎn)換。,所以得到另一個點(diǎn)X(1) ,有,三、最優(yōu)性檢驗(yàn)和解的判別,將基本可行解X（

20、0）和X（1）分別代入目標(biāo)函數(shù)得：,當(dāng)所有的j0時， 現(xiàn)有基可行解為最優(yōu)解。 當(dāng)所有的j0時，又對某個非基變量xj,有j=0， 則有無窮多最優(yōu)解。 當(dāng)存在某個j0，又Pj0,則有無界解。 所有j0時， 如基變量中仍含有非零的人工變量， 表明問題無可行解。,單純形法計(jì)算步驟,單純形表 特點(diǎn)： （直觀.便于理解計(jì)算關(guān)系.功能與增廣矩陣相似）,增廣矩陣,單純形表：,maxZ=c1x1+ c2x2+cnxn,c1 c2 cm,x1 x2 xm,b1 b2 bm,1) 找出初始基可行解，建立單純形表。,5） 以al,k為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算， 轉(zhuǎn)2 ）.,計(jì)算步驟：,例題：用單純形法求解線性規(guī)劃問題,解：

21、 1、先將上述問題化成標(biāo)準(zhǔn)形式有,找到一個初始基可行解,X=(0,0,15,24,5)T,2、列初始單純形表：,X1進(jìn)基；,X4出基；,x1,2,3、列新單純形表：,X2進(jìn)基；,X5出基；,x2,1,4、列新單純形表：,解為：X=(7/2,3/2,15/2,0,0)。,目標(biāo)函數(shù)值為: maxZ=2x1+x2+0 x3+0 x4+0 x5 =27/2+13/2+015/2+0+0=8.5,解：,練習(xí)題,原問題化為標(biāo)準(zhǔn)型,列初始單純形表,列初始單純形表,X2入基，,X6出基,作業(yè)：,人工變量法,當(dāng)化為標(biāo)準(zhǔn)形后的約束條件的系數(shù)矩陣中不存在單位矩陣時，可以人為地增加變量，在最優(yōu)解中人工變量取值必須為零

22、。為此，令目標(biāo)函數(shù)中人工變量的系數(shù)為任意大的負(fù)值M。這種人為增加變量的方法稱為人工變量法，亦稱大M法。,例1：,Max z= 6x1 +4x2,2x1 +3x2 100 4x1 +2x2 120 x1 =14 x2 22 x1 ,x2 0,解：,化成標(biāo)準(zhǔn)型,maxZ=6x1+4x2,2x1 +3x2 +x3 =100 4x1 +2x2 +x4 =120 x1 =14 x2 - x5 = 22 x1 x7 0,加人工變量,+x6,+x7,-Mx6 -Mx7,列初始單純形表,6 4 0 0 0 - M - M CB xB b x1 x2 x3 x4 x5 x6 x7 0 x3 100 2 3 1

23、0 0 0 0 0 x4 120 4 2 0 1 0 0 0 -M x6 14 1 0 0 0 0 1 0 -M x7 22 0 1 0 0 -1 0 1 -36 M M +6 M +4 0 0 - M 0 0,Cj,0 x3 72 0 3 1 0 0 -2 0 0 x4 64 0 2 0 1 0 -4 0 6 x1 14 1 0 0 0 0 1 0 -M x7 22 0 1 0 0 -1 0 1 84-22M 0 M+4 0 0 -M 6-M 0,Cj,0 x3 6 0 0 1 0 (3) -2 -3 0 x4 20 0 0 0 1 2 -4 -2 6 x1 14 1 0 0 0 0 1 0

24、 4 x2 22 0 1 0 0 -1 0 1 172 0 0 0 0 4 6-M 4-M 0 x5 2 0 0 1/3 0 1 -2/3 -1 0 x4 16 0 0 -2/3 1 0 -8/3 0 6 x1 14 1 0 0 0 0 1 0 x2 24 0 1 1/3 0 0 -2/3 -2 180 0 0 -4/3 0 0 -M-10/3 -M,6 4 0 0 0 - M - M CB xB b x1 x2 x3 x4 x5 x6 x7,解為：X=(14,24,0,16,2)。,目標(biāo)函數(shù)值為: maxZ=6x1+4x2 =614+424=180,練 習(xí),用大M法求解下列問題：,兩階段法,

25、對添加人工變量后的線性規(guī)劃問題分兩個階段來計(jì)算，稱為兩階段法。,兩階段法,第一階段是先求解一個目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃問題，即令目標(biāo)函數(shù)中其它變量的系數(shù)取零，人工變量的系數(shù)取某個正的常數(shù)(一般取1)，在保持原問題約束條件不變的情況下求這個目標(biāo)函數(shù)極小化時的解。,作輔助問題,原問題,兩階段法,在第一階段中，當(dāng)人工變量取值為0時，目標(biāo)函數(shù)值也為0。這時候的最優(yōu)解就是原線性規(guī)劃問題的一個基可行解。如果第一階段求解結(jié)果最優(yōu)解的目標(biāo)函數(shù)值不為0，也即最優(yōu)解的基變量中含有非零的人工變量，表明原線性規(guī)劃問題無可行解。,解題過程：,第1階段：解輔助問題當(dāng)進(jìn)行到最優(yōu)表時， 若W=0, 則得到原問題的一

26、個 基本可行解，轉(zhuǎn)入第2階段。 若W0, 則判定原問題無可行解。,第2階段：去除人工變量，求解原問題。第一階段的最優(yōu)解為原問題的初始基可行解。,maxZ= -x1 +2x2,x1 +x2 2 -x1 +x2 1 x2 3 x1 x2 0,例：,x1 +x2 -x3 =2 -x1 +x2 -x4 =1 x2 +x5 =3 x1 x5 0,1.化標(biāo)準(zhǔn)型：,maxZ= -x1 +2x2,+x6,+x7,2.增加人工變量，構(gòu)造單位矩陣：,x6, x7 0,3. 建立只包含人工變量的輔助問題。,minW=x6 +x7,x1 +x2 -x3 +x6 =2 -x1 +x2 -x4 +x7 =1 x2 +x5 =3 x1 x7 0,3,0 0 0 0 0 1 1 CB xB b x1 x2 x3 x4 x5 x6 x7 1 x6 2 1 1 -1 0 0 1 0 1 x7 1 -1 (1) 0 -1 0 0 1 0 x5 3 0 1 0 0 1 0 0 3 0 -2 1 1 0 0 0,0 x1 1/2 1 0 -1/2 1/2 0 1/2 -1/2 0 x2 3/2 0 1 -1/2 -1/2 0 1/2 1/2 0 x5 3/2 0 0 -1/2 1/2 1 -1/2 -1/2 0 0 0 0 0 0 1 1,1 x6 1 2 0 -1 1 0 1 -1 0 x2 1 -1 1 0 -1