管理運(yùn)籌學(xué)02線性規(guī)劃課件

1、1. 線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型2. 線性規(guī)劃的圖解法3. 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式4. 線性規(guī)劃的解集特征5. 線性規(guī)劃的單純形法6. 單純形法的進(jìn)一步討論第二章 線性規(guī)劃7/26/20221線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型資源合理利用問(wèn)題：第5頁(yè)例2-1質(zhì)量檢驗(yàn)問(wèn)題：第6頁(yè)例2-2線性規(guī)劃數(shù)學(xué)模型的一般形式7/26/20222資源合理利用問(wèn)題：第5頁(yè)例2-1 1. 決策變量：x1和x2 2. 目標(biāo)函數(shù)：max (2 x1+3 x2) 3. 約束條件：10 x1+20 x2 80 4 x1 16 6 x2 18 x1，x2 07/26/20223 質(zhì)量檢驗(yàn)問(wèn)題：第6頁(yè)例2-2 1.決策變量：x1和x2

2、2.目標(biāo)函數(shù)：min(40 x1+36 x2) 3.約束條件：5 x1+3 x2 45 x1 8 x2 10 x1，x2 07/26/20224線性規(guī)劃數(shù)學(xué)模型的一般形式 1. 決策變量是非負(fù)變量； 2. 目標(biāo)函數(shù)是線性函數(shù)； 3. 約束條件是線性等式或不等式組。 一般形式為： max(min)(c1 x1+ c2 x2 + cn xn ) a11 x1+ a12 x2 + a1n xn (=,) b1 a21 x1+ a22 x2 + a2n xn (=,) b2 am1 x1+ am2 x2 + amn xn (=,) bm x1 ， x2 ， ， xn 0 7/26/20225 線性規(guī)劃

3、的圖解法1.局限性：只能求解具有兩個(gè)變量的線性規(guī)劃問(wèn)題。2.學(xué)習(xí)目的：圖解法只能求解具有兩個(gè)決策變量的線性規(guī)劃問(wèn)題，其應(yīng)用具有很大的局限性，因此學(xué)習(xí)圖解法的目的并非是要掌握一種線性規(guī)劃問(wèn)題的求解方法，而是要通過(guò)圖解法揭示線性規(guī)劃問(wèn)題的內(nèi)在規(guī)律，為學(xué)習(xí)線性規(guī)劃問(wèn)題的一般算法（單純形法）奠定基礎(chǔ)。3.線性規(guī)劃有關(guān)解的幾個(gè)概念4.圖解法的基本步驟5.圖解法所反映出的一般結(jié)論7/26/20226線性規(guī)劃有關(guān)解的幾個(gè)概念 1. 可行解：滿足約束條件的一組決策變量的取值； 2. 可行域：可行解所構(gòu)成的集合； 3. 最優(yōu)解：使目標(biāo)函數(shù)達(dá)到極值的可行解； 4. 最優(yōu)值：與最優(yōu)解相對(duì)應(yīng)的目標(biāo)函數(shù)的取值。7/26

4、/20227圖解法的基本步驟 1.畫出平面直角坐標(biāo)系； 2.將約束條件逐一反映進(jìn)平面直角坐標(biāo)系，用標(biāo)號(hào)和箭線表明約束條件的順序和不等號(hào)的方向； 3.找出可行域并反映出目標(biāo)函數(shù)直線的斜率； 4.平移目標(biāo)函數(shù)直線找出最優(yōu)解。 5.例題：第7頁(yè)例2-3：用圖解法求解例2-1 6.習(xí)題：第8頁(yè)例2-4：用圖解法求解例2-2 7/26/20228用圖解法求解例2-1x1x2432101 2 3 4 5 6 7 87/26/20229用圖解法求解例2-1x1x2432101 2 3 4 5 6 7 87/26/202210用圖解法求解例2-1x1x2432101 2 3 4 5 6 7 87/26/202

5、211用圖解法求解例2-1x1x2432101 2 3 4 5 6 7 87/26/202212用圖解法求解例2-1x1x2432101 2 3 4 5 6 7 87/26/202213用圖解法求解例2-1x1x2432101 2 3 4 5 6 7 87/26/202214用圖解法求解例2-1x1x2432101 2 3 4 5 6 7 87/26/202215用圖解法求解例2-2x1x2 5 10 151510507/26/202216圖解法所反應(yīng)出的一般結(jié)論1.線性規(guī)劃問(wèn)題的可行域是凸多邊形；2.如果線性規(guī)劃問(wèn)題有最優(yōu)解，其最優(yōu)解一定可以在其可行域的頂點(diǎn)上得到，而不會(huì)在可行域的內(nèi)部；3.

6、如果線性規(guī)劃問(wèn)題在其可行域的兩個(gè)頂點(diǎn)上得到最優(yōu)解，那么兩頂點(diǎn)連線上的所有點(diǎn)均為最優(yōu)解點(diǎn)；4.線性規(guī)劃問(wèn)題的解可能有四種情況：唯一最優(yōu)解；無(wú)窮多最優(yōu)解；無(wú)界解和無(wú)可行解。7/26/202217線形規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式1. 標(biāo)準(zhǔn)形式的基本條件：（1）決策變量非負(fù)；（2）目標(biāo)函數(shù)極大化（或極小化）；（3）約束條件為嚴(yán)格等式，且右端項(xiàng)非負(fù)。2. 標(biāo)準(zhǔn)形式的表示： 代數(shù)式；和式；向量式；矩陣式 3. 標(biāo)準(zhǔn)形式的轉(zhuǎn)化7/26/202218線性規(guī)劃的標(biāo)準(zhǔn)型：代數(shù)式 min z =c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2

7、x2+amnxn=bm xj 0 j =1,2,n 7/26/202219線性規(guī)劃的標(biāo)準(zhǔn)型：和式 min z =cjxj aijxj=bi i=1,2,m xj 0 j=1,2,nj=1nnj=17/26/202220線性規(guī)劃的標(biāo)準(zhǔn)型：向量式 min z = CX pjxj=bi i=1,2,m xj 0 j=1,2,n C=(c1,c2,c3,cn) X=(X1,X2,X3,Xn) Tnj=17/26/202221線性規(guī)劃的標(biāo)準(zhǔn)型：矩陣式 min z =CX AX=b，X 0 ， b 0 其中： b=(b1,b2,bm)T a11 a12 .a1n A= a21 a22 a2n am1 am

8、2 amn7/26/202222標(biāo)準(zhǔn)形式的轉(zhuǎn)化1.無(wú)約束變量x的處理： x=y-z, 其中y,z02.負(fù)數(shù)變量x的處理： x=-y,其中y03.目標(biāo)函數(shù)極小化的處理： Min CX=- Max(-CX)4.非等式約束條件的處理： 加松弛變量或減剩余變量5.右端項(xiàng)為負(fù)：兩端同乘“-1”7/26/202223線形規(guī)劃的解集特征1.線性規(guī)劃基與解的概念 (1)基、基列、基變量和非基變量 (2)基解、基可行解和可行基2.凸集的概念與解集的基本定理 (1)凸集的概念 (2)解集的基本定理7/26/202224線性規(guī)劃基與解的概念1.基、基列、基變量和非基變量 (1) 基： Max CX, AX=b, X

9、0, b0 Amn其秩為m，B 是 Amn中的一個(gè)mm階滿秩矩陣，則稱B是線 性規(guī)劃問(wèn)題的一個(gè)基 (2) 基列：基 B 中所包含的m個(gè)列向量 (3) 基變量：基列所對(duì)應(yīng)的決策變量 (4) 非基變量：基變量以外的決策變量2.基解、基可行解、可行基 (1) 基解：令所有的非基變量為零，所求得的一組解 (2) 基可行解：所有分量均為非負(fù)的基解 (3) 可行基：與基可行解所對(duì)應(yīng)的基7/26/202225凸集的概念與解集的基本定理1.凸集的概念：設(shè) K 是 n 維歐氏空間的一點(diǎn)集，若任意兩點(diǎn) X(1) k，X(2) k 的連線上的一切點(diǎn) X(1) + (1-) X(2) k，(0 1) 則稱 k 為凸集

10、。2.解集的基本定理： (1) 若線性規(guī)劃問(wèn)題存在可行域，則其可行域是凸集； (2) 線性規(guī)劃問(wèn)題的基可行解對(duì)應(yīng)其可行域的頂點(diǎn)； (3) 若線性規(guī)劃問(wèn)題存在最優(yōu)解，則其最優(yōu)解一定能在基可行解中找到。7/26/202226線性規(guī)劃的單純形法1.單純形法的基本原理 (1) 單純形法的基本思路 (2) 第12頁(yè)例2-62.最優(yōu)性檢驗(yàn)與解的判別3.單純形表4.單純形法的基本步驟5.用單純形法求解例2-66.課上習(xí)題7/26/202227單純形法的基本思路1. 找出一個(gè)初始的基可行解；2. 判斷其最優(yōu)性；3. 轉(zhuǎn)移至另一個(gè)較優(yōu)的基可行解；4. 重復(fù)2、3兩步直至最優(yōu)。7/26/202228第12頁(yè)例2-

11、6Max z = 2x1 + 3x2 10 x1 + 20 x2 + x3 = 80 4x1 + x4 = 16 6x2 + x5 = 18 x1， x2， x3， x4， x5 0B = (p3，p4，p5)X(0) = (0，0，80，16，18)T Z(0) = 0，z = 2x1 + 3x2尋找相鄰的基可行解7/26/202229例2-6Max (2，3) = 3 x2入基Min (80/20，18/6) = 3 x5出基B = (p3，p4，p2) 10 x1 + x3 - 10/3 x5 = 20 4x1 + x4 = 16 x2 + 1/6 x5 = 3X(1) = (0，3，2

12、0，16，0)T Z(1) = 9，z = 9 + 2x1 - 1/2 x57/26/202230例2-6Max (2) = 2 x1入基Min (20/10，16/4) = 2 x3出基B = (p1，p4，p2) x1 + 1/10 x3 - 1/3 x5 = 2 - 2/5 x3 + x4 + 4/3 x5 = 8 x2 + 1/6 x5 = 3X(2) = (2，3，0，8，0)T Z(2) = 13，z = 13 - 1/5 x3 + 1/6 x57/26/202231例2-6Max (1/6) = 1/6 x5入基Min (8/(4/3)，3/(1/6) = 6 x4出基B = (

13、p1，p5，p2) x1 + 1/4 x 4 = 4 - 3/10 x3 + 3/4 x4 + x5 = 6 x2 + 1/20 x3 - 1/8 x4 = 2X(3) = (4，2，0，0，6)T Z(3) = 14，z = 14 - 9/10 x3 - 1/8 x47/26/202232最優(yōu)性檢驗(yàn)與解的判別7/26/202233單純形表7/26/202234單純形法的基本步驟1.數(shù)學(xué)模型標(biāo)準(zhǔn)化、正規(guī)化；2.建立初始單純形表；3.計(jì)算檢驗(yàn)數(shù)并判斷最優(yōu)性，結(jié)束或繼續(xù)；4.確定入基變量和出基變量，5.迭代運(yùn)算；6.重復(fù)3、4、5步，直至結(jié)束。7/26/202235用單純形法求解例2-67/26/

14、202236用單純形法求解例2-67/26/202237用單純形法求解例2-67/26/202238用單純形法求解例2-67/26/202239課上習(xí)題1. Max z =2x1 + 4x2 + x3 + x4 x1 + 3x2 + x4 8 2x1 + x2 6 x2 + x3 + x4 6 x1 + x2 + x3 9 x14 02.第17頁(yè)例2-103.第19頁(yè)例2-117/26/202240單純形法的進(jìn)一步討論1. 計(jì)算問(wèn)題 (1) 入基變量的選擇 (2) 解的退化2. 人工變量與初始正規(guī)基 (1) 大M法 (2) 兩階段法7/26/202241入基變量的選擇 入基變量是根據(jù)最大正檢驗(yàn)

15、數(shù)來(lái)選擇的，這樣做的目的是為了使目標(biāo)函數(shù)得到最大的增量，因此當(dāng)最大正檢驗(yàn)數(shù)有多個(gè)時(shí)，可主觀地選擇它們中的任意一個(gè)作為入基變量。其實(shí)具有正檢驗(yàn)數(shù)的所有非基變量都可作為入基變量。7/26/202242出基變量的選擇與解的退化1. 退化解：部分基變量的值為零的基可行解稱為退化解。2. 在選擇出基變量時(shí)，如果最小比值不唯一，可主觀確定出基變量，此時(shí)產(chǎn)生退化解。3. 例7/26/202243例Max z =2x4 +(3/2)x6 x1 + x4 - x5 = 8 x2 + 2 x4 + x6 = 4 x3 + x4 + x5 + x6 = 3 x16 07/26/202244例7/26/202245例

16、7/26/202246例7/26/202247例7/26/202248例7/26/202249人工變量與初始正規(guī)基第21頁(yè)例2-13: Min z = -3x1 + x2 + x3 x1 - 2x2 + x3 11 -4x1 + x2 + 2x3 3 2x1 - x3 = -1 x1 ， x2 ， x3 0(1)標(biāo)準(zhǔn)化7/26/202250例2-13的標(biāo)準(zhǔn)化 Min z = -3x1 + x2 + x3 x1 - 2x2 + x3 + x4 = 11 -4x1 + x2 + 2x3 - x5 = 3 -2x1 + x3 = 1 x15 0(2)正規(guī)化7/26/202251例2-13的正規(guī)化人工

17、變量：為構(gòu)造基變量（正規(guī)基）人為加入的變量 x1 - 2x2 + x3 + x4 = 11 -4x1 + x2 + 2x3 - x5 + x6 = 3 -2x1 + x3 + x7 = 1 x17 0初始正規(guī)基 B= (p4, p6, p7) = E7/26/202252大M法1. 大M法：令人工變量的價(jià)值系數(shù)為“-M” (極大值)或 “M” (極小值)的單純形法即稱為大M法；例如： Min z = -3x1 + x2 + x3 + M x人1+M x人2 Max z = 2x1 + x2 + 4x3 - M x人1+M x人22. 例2-13的大M法3. 習(xí)題（大M法）7/26/202253

18、用大M法求解例2-13 Min z = -3x1 + x2 + x3 x1 - 2x2 + x3 11 -4x1 + x2 + 2x3 3 2x1 - x3 = -1 x1 ， x2 ， x3 07/26/202254用大M法求解例1.13 Min z = -3x1 + x2 + x3 + Mx6 + Mx7 x1 - 2x2 + x3 + x4 = 11 -4x1 + x2 +2x3 - x5 + x6 = 3 -2x1 + x3 + x7 = 1 x17 07/26/202255用大M法求解例1.137/26/202256用大M法求解例1.137/26/202257用大M法求解例1.137

19、/26/202258用大M法求解例1.137/26/202259習(xí)題（用大M法求解） Max z = 2x1 + 4x2 + x3 x1 + x2 + x3 6 x1 + x2 - 2x3 4 x1 - 2x2 + x3 8 x1 ， x2 ， x3 07/26/202260習(xí)題（用大M法求解） Max z = 2x1 + 4x2 + x3 - Mx7 x1 + x2 + x3 + x4 = 6 x1 + x2 - 2x3 + x 5 = 4 x1 - 2x2 + x3 - x6 + x7 = 8 x17 07/26/202261習(xí)題（用大M法求解）7/26/202262習(xí)題（用大M法求解）7/26/202263習(xí)題（用大M法求解）7/26/202264兩階段法1. 兩階段法：第一階段，在原約束條件下，求所有人工變量和的最小值；第一階段的目的是獲得問(wèn)題的一個(gè)初始基可行解（人工變量和的最小值為零）或得出問(wèn)題無(wú)可行解（人工變量和的最小值大于零）的結(jié)論；第二階段，去掉人工變量，在原目標(biāo)下從已得到的基可行解開(kāi)始優(yōu)化。2. 例2-13的兩階段法3. 習(xí)題（兩