管理運(yùn)籌學(xué)講義第1章線性規(guī)劃

1、1,第1章 線性規(guī)劃,Sub title,學(xué)習(xí)要點(diǎn),線性規(guī)劃模型的結(jié)構(gòu)及建模步驟 線性規(guī)劃的圖解法及解的可能性 線性規(guī)劃的標(biāo)準(zhǔn)型及其轉(zhuǎn)化方法 正確理解可行解、可行域、最優(yōu)解 了解基矩陣、基變量、非基變量、基可行解 線性規(guī)劃的單純形法原理和解的判定,2,一、線性規(guī)劃的三個(gè)要素,第一節(jié) 線性規(guī)劃的一般模型,決策變量決策問(wèn)題待定的量值取值要求非負(fù)約束條件任何管理決策問(wèn)題都是限定在一定條件下來(lái)進(jìn)行的把各種限制條件表示為一組

2、等式或不等式稱為約束條件約束條件是決策方案可行的保障約束條件是決策變量的線性函數(shù)目標(biāo)函數(shù)衡量決策優(yōu)劣的準(zhǔn)則，如時(shí)間最短、利潤(rùn)最大、成本最低目標(biāo)函數(shù)是決策變量的線性函數(shù)有的目標(biāo)要求實(shí)現(xiàn)極大，有的則要求極小,3,二、線性規(guī)劃模型舉例,第一節(jié) 線性規(guī)劃的一般模型,1.生產(chǎn)計(jì)劃問(wèn)題,例. 某廠生產(chǎn)甲乙兩種產(chǎn)品，生產(chǎn)工藝路線為：各自的零部件分別在設(shè)備A、B上加工，最后都需在設(shè)備C上裝配。經(jīng)測(cè)算得到相關(guān)數(shù)據(jù)如表所示。應(yīng)如何制定生產(chǎn)計(jì)劃，

3、使總利潤(rùn)為最大。 據(jù)市場(chǎng)分析，單位甲乙產(chǎn)品的銷售價(jià)格分別為73和75元，試確定獲利最大的產(chǎn)品生產(chǎn)計(jì)劃。,4,第一節(jié) 線性規(guī)劃的一般模型,(1)決策變量：設(shè)x1為甲產(chǎn)品的產(chǎn)量，x2為乙產(chǎn)品的產(chǎn)量。(2)約束條件：生產(chǎn)受設(shè)備能力制約，能力需求不能突破有效供給量。設(shè)備A的約束條件表達(dá)為 2 x1 ≤16同理，設(shè)備B的加工能力約束條件表達(dá)為 2x2 ≤10

4、設(shè)備C的裝配能力也有限，其約束條件為 3x1+ 4x2 ≤32(3)目標(biāo)函數(shù)：目標(biāo)是企業(yè)利潤(rùn)最大化 max Z= 3x1 +5x2 (4)非負(fù)約束：甲乙產(chǎn)品的產(chǎn)量為非負(fù) x1 ≥0， x2 ≥0,綜上的LP模型：,5,第一節(jié) 線性規(guī)劃的一般模型,2.物資運(yùn)輸問(wèn)題,,例：某產(chǎn)品有3個(gè)供貨源A1、A2、A3，有4個(gè)經(jīng)銷商（需求市場(chǎng)）B1、B2、B3

5、、B4。已知各廠的產(chǎn)量、各經(jīng)銷商的銷售量及從Ai 到Bj 的單位運(yùn)費(fèi)為Cij。為發(fā)揮集團(tuán)優(yōu)勢(shì)，公司要統(tǒng)一籌劃運(yùn)銷問(wèn)題，求運(yùn)費(fèi)最小的調(diào)運(yùn)方案。,6,第一節(jié) 線性規(guī)劃的一般模型,,(1)決策變量：設(shè)從Ai到Bj的運(yùn)輸量為xij，(2)目標(biāo)函數(shù)：運(yùn)費(fèi)最小的目標(biāo)函數(shù)為minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 (3)約束條件：產(chǎn)量之和等于銷量之和,故要滿

6、足：供應(yīng)平衡條件,x11+x12+x13+x14=50x21+x22+x23+x24=20x31+x32+x33+x34 =30,銷售平衡條件,x11+x21+x31=20x12+x22+x32=30x13+x23+x33=10x14+x24+x34=40,非負(fù)性約束 xij≥0 (i=1,2,3；j=1,2,3,4),7,第一節(jié) 線性規(guī)劃的一般模型,3.產(chǎn)品配比問(wèn)題,,例：用濃度45%和92%的

7、硫酸配置100噸濃度80%的硫酸。,決策變量：取45%和92%的硫酸分別為 x1 和 x2 噸 約束條件：,求解二元一次方程組得解,非負(fù)約束： x1 ≥0， x2 ≥0,8,第一節(jié) 線性規(guī)劃的一般模型,若用5種不同濃度的硫酸(30%,45%,73%,85%,92%)配置100噸濃度80%的硫酸，5種硫酸價(jià)格分別為400、700、1400、1900、2500元/t，,取這5種硫酸分別為 x1、x2、x3、x4、x5 ，有,有

8、多少種配比方案？何為最好？,9,三、線性規(guī)劃的一般數(shù)學(xué)模型,第一節(jié) 線性規(guī)劃的一般模型,用一組非負(fù)決策變量表示的一個(gè)決策問(wèn)題； 存在一組等式或不等式的線性約束條件； 有一個(gè)希望達(dá)到的目標(biāo)，可表示成決策變量的極值線性函數(shù)。具備以上三個(gè)特點(diǎn)的數(shù)學(xué)模型稱為線性規(guī)劃（Linear Programming，簡(jiǎn)記為L(zhǎng)P），它的一般形式為：,,10,三、線性規(guī)劃的一般數(shù)學(xué)模型,第一節(jié) 線性規(guī)劃的一般模型,,在線性規(guī)劃模型中， z 為目

9、標(biāo)函數(shù)；xj ，j = 1 , 2 ,…, n 為決策變量； cj ，j = 1 , 2 , … , n 為價(jià)值系數(shù); bi ，i = 1 , 2 ,… , m 為資源常數(shù)；aij ，i = 1 , 2 , … , m ; j = 1 , 2 , … , n 為工藝系數(shù)或技術(shù)系數(shù)。這里，cj ，bi ，aij 均為常數(shù)。,11,四、線性規(guī)劃的圖解方法,第一節(jié) 線性規(guī)劃的一般模型,1.線性規(guī)劃的可行域,,可行域：滿足所有約束條件的解的集

10、合，即所有約束條件共同圍城的區(qū)域。,maxZ= 3x1 +5 x2 2 x1 ≤16 2x2 ≤10 3x1 +4 x2 ≤32 x1 ≥0, x2 ≥0,,S.t.,12,四、線性規(guī)劃的圖解方法,第一節(jié) 線性規(guī)劃的一般模型,2.線性規(guī)劃的最優(yōu)解,,

11、目標(biāo)函數(shù) Z= 3x1 +5 x2 代表以 Z 為參數(shù)的一族平行線。最優(yōu)解點(diǎn)C(4,5)，MaxZ=37,13,五、線性規(guī)劃解的可能性,第一節(jié) 線性規(guī)劃的一般模型,1. 唯一最優(yōu)解：只有一個(gè)最優(yōu)點(diǎn),,2. 多重最優(yōu)解：無(wú)窮多個(gè)最優(yōu)解,,14,五、線性規(guī)劃解的可能性,第一節(jié) 線性規(guī)劃的一般模型,3. 無(wú)界解：可行域無(wú)界，目標(biāo)函數(shù)值無(wú)限增大或減小,,15,五、線性規(guī)劃解的可能性,第一節(jié) 線性規(guī)劃的一般模型,4. 沒(méi)有可行解：線性規(guī)劃問(wèn)

12、題的可行域是空集,,,,16,五、線性規(guī)劃解的可能性,第一節(jié) 線性規(guī)劃的一般模型,,,,線性規(guī)劃問(wèn)題的可行域可記為：S = { x ? Ax = b, x ? 0 }如果 S 為一空集，線性規(guī)劃不可行 或 無(wú)可行解。如果 S 不為空集，該線性規(guī)劃一定有可行解，但不一定有有界最優(yōu)解；若 S 為一非空有界集合，則線性規(guī)劃一定存在最優(yōu)解；,17,一、線性規(guī)劃的標(biāo)準(zhǔn)型式,第二節(jié) 線性規(guī)劃的單純形法,,,,標(biāo)準(zhǔn)型的特征,w目標(biāo)函數(shù)最大

13、化w約束條件為等式w右端項(xiàng)為非負(fù)值w決策變量非負(fù)值,18,一、線性規(guī)劃的標(biāo)準(zhǔn)型式,第二節(jié) 線性規(guī)劃的單純形法,1.標(biāo)準(zhǔn)型表達(dá)方式,,,1）代數(shù)式,2）向量式,,3）矩陣式,A：技術(shù)系數(shù)矩陣，簡(jiǎn)稱系數(shù)矩陣；b：可用的資源量，稱資源向量；C：決策變量對(duì)目標(biāo)的貢獻(xiàn)，稱價(jià)值向量；X：決策向量。,19,一、線性規(guī)劃的標(biāo)準(zhǔn)型式,第二節(jié) 線性規(guī)劃的單純形法,1.標(biāo)準(zhǔn)型表達(dá)方式,,,矩陣A也可表示為：A = ( p1， p2，…，pn )

14、，,其中 pj = ( a1j，a2j，…，amj )T,20,一、線性規(guī)劃的標(biāo)準(zhǔn)型式,第二節(jié) 線性規(guī)劃的單純形法,2.標(biāo)準(zhǔn)型轉(zhuǎn)換方法,,,,,1）對(duì)于極小化原問(wèn)題minZ=CX，則令 Z'=-Z，轉(zhuǎn)為求 maxZ'=-CX 2）若某個(gè)bi<0，則以－1乘該約束兩端，使之滿足非負(fù)性的要求。3）對(duì)于≤型約束，則在左端加上一個(gè)非負(fù)松弛變量，使其為等式。 4）對(duì)于≥型約束，則在左端減去一個(gè)

15、非負(fù)剩余變量，使其為等式。 5）若某決策變量xk無(wú)非負(fù)約束，令xk=x'k-x"k ，(x'k≥ 0,x"k ≥0) 。,21,非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例,minZ=x1+2x2-3x3 x1+x2+x3 ≤9 -x1-2x2+x3 ≥2 3x1+x2-3x3=5 x1≤0，x2≥0， x3無(wú)約束,,標(biāo)準(zhǔn)型為maxZ&#

16、39;=x1'-2x2＋3(x3'- x3") -x1'+x2+x3'- x3"＋x4 =9 x1'-2x2+ x3'- x3" - x5 = 2 -3 x1' +x2-3(x3'- x3" ) =5 x1'x2 x3' x3" x4 x5 ≥0,令x1=-x1'，x

17、3=x3' -x3" Z=-Z'。,,22,二、線性規(guī)劃之解的概念,,,,第二節(jié) 線性規(guī)劃的單純形法,1. 線性規(guī)劃的基與基本可行解線性規(guī)劃的基本定理單純形法解題思路,23,1. 線性規(guī)劃的基與基本可行解,基的定義：給定線性規(guī)劃問(wèn)題 LP： A是 m?n 滿秩矩陣, n > m，如果 B 是其中任一個(gè) m ? m 滿秩子矩陣，則稱 B 是 LP 的一個(gè)基。,第二節(jié) 線性規(guī)劃

18、的單純形法,24,基變量與非基變量假定 B 由 A 中前 m 個(gè)列向量構(gòu)成，約束矩陣可劃分為： A = ( B, N )與基 B 對(duì)應(yīng)的變量稱為基變量，用 xB 表示；與非基 N 對(duì)應(yīng)的變量稱為非基變量，用 xN 表示。,,第二節(jié) 線性規(guī)劃的單純形法,25,基本解（基解）如果令 xN = 0，則有： Ax =( B,N ) (xB , xN) = BxB + NxN = BxB Ax = b

19、等價(jià)于 BxB = b，由于 B 滿秩， BxB = b 有唯一解 ：xB = B-1b 則 x = (xB , xN ) = (B?1b, 0) 是線性規(guī)劃 P 的基本解。最多為C mn個(gè),26,,,基本可行解與可行基滿足非負(fù)條件的基本解為基本可行解，即 XB=B-1b≥0 。該解對(duì)應(yīng)的基為可行基。,可行解,基本可行解,基本解,第二節(jié) 線性規(guī)劃的單純形法,27,例 考慮線性規(guī)劃模型 Max z = 1500

20、x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 ≥ 0   注意，線性規(guī)劃的基本解、基本可行解和可行基只與線性規(guī)劃問(wèn)題標(biāo)準(zhǔn)形式的約束條件有關(guān)。,28,3 2 1 0 0 A = [P1,P2,P

21、3,P4,P5]= 2 1 0 1 0 0 3 0 0 1 A矩陣包含以下10個(gè)3×3的子矩陣：  B1=[p1，p2，p3] B2=[p1，p2，p4] B3=[p1，p2，p5] B4=[p1，p3，p4] B5=[p1，p3，p5] B6=[p1，p4，p5] B7=[p2，p3，p4] B8=[p2，p3，p

22、5] B9=[p2，p4，p5] B10=[p3，p4，p5],29,其中?B4?= 0，因而B4不是該線性規(guī)劃問(wèn)題的基。其余均為非奇異方陣，因此該問(wèn)題共有9個(gè)基。 對(duì)于基B3=[p1，p2，p5]，令非基變量x3 = 0，x4 = 0，在等式約束中令x3 = 0，x4 = 0，解線性方程組： 3 x1 + 2 x2 + 0 x5 = 65 2 x1 + x2 + 0 x5 =

23、 40 0 x1 + 3 x2 + x5 = 75得到x1 =15，x2 = 10，x5 = 45，對(duì)應(yīng)的基本可行解： x(3) =(x1，x2，x3，x4，x5)T=(15，10，0，0，45)T。,30,于是對(duì)應(yīng)的基B3是一個(gè)可行基。類似可得到: x(1) = (7.5,25,-7.5,0,0)T （對(duì)應(yīng)B1） x(2) = (5,25,0,5,0)T （對(duì)應(yīng)B

24、2） x(3) = (15，10，0，0，45)T （對(duì)應(yīng)B3） x(5) = (20,0,5,0,75)T （對(duì)應(yīng)B5） x(6) = (65/3,0,0,-10/3,75)T （對(duì)應(yīng)B6） x(7) = (0,25,15,15,0)T （對(duì)應(yīng)B7） x(8) = (0,40,-15,0,-45)T （對(duì)應(yīng)B8） x(9) = (0,32.5,0,7.5,-2

25、2.5)T （對(duì)應(yīng)B9） x(10)= (0,0,65,40,75)T （對(duì)應(yīng)B10） 是基本解。,31,其中 x(2) = (5,25,0,5,0)T （對(duì)應(yīng)B2） x(3) = (15，10，0，0，45)T （對(duì)應(yīng)B3） x(5) = (20,0,5,0,75)T （對(duì)應(yīng)B5） x(7) = (0,25,15,15,0)T （對(duì)

26、應(yīng)B7） x(10)= (0,0,65,40,75)T （對(duì)應(yīng)B10）是基本可行解，對(duì)應(yīng)基本可行解的基B2 B3 B5 B7 B10都是可行基。,32,,2.線性規(guī)劃基本原理,定理1. 若線性規(guī)劃問(wèn)題存在可行域，則其可行域一定是凸集。定理2. 線性規(guī)劃問(wèn)題的基可行解對(duì)應(yīng)可行域的頂點(diǎn)。定理3. 若可行域有界，線性規(guī)劃的目標(biāo)函數(shù)一定可以在可行域的頂點(diǎn)上達(dá)到最優(yōu)。定理4. 線性規(guī)劃如果有可行解，則一定有基可行解；如

27、果有最優(yōu)解，則一定有基可行解是最優(yōu)解。,第二節(jié) 線性規(guī)劃的單純形法,33,定義1：集合C 稱為凸集，如果對(duì)任意 x1, x2 ?C , 0<?<1 , 有?x1 + (1 - ?) x2 ?C。,凸集沒(méi)有凹陷部分，該集合內(nèi)任取兩點(diǎn)連線上的任何點(diǎn)都應(yīng)該在集合內(nèi)。,補(bǔ)充概念：,34,凸集,,,,,,,,,,,,,35,非凸集,,,,,,,,,,,,,36,在凸集中，不能表示為不同點(diǎn)的凸組合的點(diǎn)稱為凸集的頂點(diǎn)（極點(diǎn)），用嚴(yán)格的定

28、義描述如下。 定義2 設(shè)S為一凸集，且X1 ? S，X2 ? S。 對(duì)于0 ? ? ? 1，若 X = ? X1 + (1-? ) X2 則必定有X = X1 = X2，則稱X為S的一個(gè)頂點(diǎn)。,37,頂點(diǎn)多邊形上的點(diǎn)是頂點(diǎn),,,,,,,圓周上的點(diǎn)都是頂點(diǎn),,38,,3.單純形法解題思路,從可行域的一個(gè)基本可行解(頂點(diǎn))出發(fā)，判別它是否已是最優(yōu)解，如果不是，尋找下一個(gè)基本可行解，并使目標(biāo)函數(shù)得到改進(jìn)，如此

29、迭代下去，直到找到最優(yōu)解或判定問(wèn)題無(wú)界為止。,第二節(jié) 線性規(guī)劃的單純形法,39,三、單純形法的基本原理,,1.單純形法的代數(shù)解法,第二節(jié) 線性規(guī)劃的單純形法,40,注：,單純形是指0維中的點(diǎn)，一維中的線段，二維中的三角形，三維中的四面體，n維空間中的有n+1個(gè)頂點(diǎn)的多面體。例如在三維空間中的四面體，其頂點(diǎn)分別為(0，0，0)，(1，0，0)，(0，1，0)，(0，0，1)。具有單位截距的單純形的方程是∑xi≤1，并且xi≥0，i=1,2

30、,…,m。,例,變成標(biāo)準(zhǔn)型,42,約束方程的系數(shù)矩陣,為基變量,為非基變量,I 為單位矩陣且線性獨(dú)立,43,令：,則：,∴ 基本可行解為（0 0 12 8 16 12）T 此時(shí)，Z = 0,然后，找另一個(gè)基本可行解。即將非基變量換入基變量中，但保證其余的非負(fù)。如此循環(huán)下去，直到找到最優(yōu)解為止。,注意：為盡快找到最優(yōu)解，在換入變量時(shí)有一定的要求。如將價(jià)值系數(shù)大的先換入。,44,當(dāng) 時(shí)， 為換入變量,確

31、定換出變量,為換出變量,接下來(lái)有下式：,,,45,,,,,,,,,,用高斯法，將 的系數(shù)列向量換為單位列向量，其步驟是：,結(jié)果是：,,,46,代入目標(biāo)函數(shù)：,有正系數(shù)表明：還有潛力可挖，沒(méi)有達(dá)到最大值；,此時(shí)：令 得到另一個(gè)基本可行解 （0，3，6，2，16，0）T,如此循環(huán)進(jìn)行，直到找

32、到最優(yōu)為止。,本例最優(yōu)解為： （4，2，0，0，0，4）T,找出一個(gè)初始可行解,是否最優(yōu),轉(zhuǎn)移到另一個(gè)基可行解并且使目標(biāo)函數(shù)上升,最優(yōu)解,,,,,,,是,否,循環(huán),直到找出最優(yōu)解或判斷問(wèn)題無(wú)解為止，核心是：變量迭代,,結(jié)束,其步驟總結(jié)如下：,48,2. 單純形法和單純形表,（1）檢驗(yàn)數(shù)的意義和計(jì)算公式考慮LP問(wèn)題,49,假定所有b1，…bm≥0。顯然問(wèn)題有基可行解X1=（b1，b2，…，bm，0，…，0，），相應(yīng)目標(biāo)函數(shù)值

33、為了判定X1是否最優(yōu)解，首先應(yīng)當(dāng)把目標(biāo)函數(shù)z用非基變量表示出來(lái)。由約束方程組得到：,,,i=（1，2，…，m）,50,其中：,,,51,上式是目標(biāo)函數(shù)通過(guò)非基變量表達(dá)的公式，每個(gè)變量的系數(shù)稱為它的檢驗(yàn)數(shù)。顯然，基變量的檢驗(yàn)數(shù)永遠(yuǎn)為0。而非基變量xj的檢驗(yàn)數(shù)σj是引入xj一個(gè)單位時(shí)目標(biāo)函數(shù)z的改變量；只有σj>0時(shí)，方值得讓xj入基。,52,（2）單純形表,0 0 … 0,…,…,53,這個(gè)表格稱為單純形表，它的右半部

34、第二行指明各個(gè)變量的位置，第一行是它們的價(jià)值系數(shù)，其下方m行是方程組的系數(shù)矩陣，它包括一個(gè)m階單位陣。左半部3列中，b列是右端常數(shù)，XB列依次標(biāo)明各方程的基變量，CB是相應(yīng)的價(jià)值系數(shù)。表的最后一行稱為檢驗(yàn)數(shù)行，填寫各個(gè)變量的檢驗(yàn)數(shù)。單純形表的主要部分是約束方程組的增廣矩陣和檢驗(yàn)數(shù)行。應(yīng)當(dāng)注意的是，系數(shù)矩陣中必須包含一個(gè)m階單位陣。,54,單純形表的便利之處首先在于，從表中可以直接讀出基可行解X：xi=bi（i=1，…，m），其它xj=0

35、；相應(yīng)目標(biāo)函數(shù)值是CB列與b列元素乘積之和；其次，每個(gè)變量xj（包括基變量在內(nèi)）的檢驗(yàn)數(shù)σj，等于cj減去CB列元素與表中xj的系數(shù)列向量元素乘積之和更有益的是，單純形法的全部分析和計(jì)算過(guò)程，可以比較方便地在單純形表中完成。下面四個(gè)法則總結(jié)了運(yùn)算各個(gè)環(huán)節(jié)的具體操作方法。,,55,3. 單純形法的基本法則,法則1: 最優(yōu)性判定法則若對(duì)基可行解X1，所有檢驗(yàn)數(shù)σj≤0，則X1為最優(yōu)解。證: 由公式 可知，

36、當(dāng)所有σj ≤0時(shí)， 總有Z≤Z1。而當(dāng)X= X1 =(b1，…bm，0，…，0)T時(shí)，Z=Z1，因此X1是最優(yōu)解。換個(gè)角度來(lái)說(shuō)，由于某個(gè)非基變量檢驗(yàn)數(shù)非正，引入任意非基變量都不能使Z值上升，故X1是最優(yōu)解。對(duì)應(yīng)于最優(yōu)解的單純形表稱為最優(yōu)表（或最終表）。反之，如果存在某個(gè)σj>0，則X1不是最優(yōu)解，計(jì)算過(guò)程要繼續(xù)下去。首先應(yīng)該選擇換入變量。,,56,法則2: 換入變量確定法則,設(shè)

37、 ，則xk為換入變量。按照檢驗(yàn)數(shù)的意義，任何具有正檢驗(yàn)數(shù)的非基變量均可入基，都能使目標(biāo)函數(shù)值上升；選擇具有最大正檢驗(yàn)數(shù)的變量入基，目的是為了使目標(biāo)函數(shù)盡快上升。,,57,法則3: 換出變量確定法則,設(shè)xk為換入變量，變量xm+1，xm+2，…，xn中除xk外均保持為0，約束方程組實(shí)際成為：,,58,設(shè)xk為換入變量，并設(shè)則最小比值所在行的原基變量xl為換出變量。強(qiáng)調(diào)：這個(gè)法則的目的

38、是，保證下一個(gè)基本解的可行性，違背這一法則，下一個(gè)基本解一定包含負(fù)分量，即不是可行解。在單純形表中，換入變量所在列稱為主元列，換出變量所在行稱為主元行，兩者交叉處的元素稱為主元。主元在迭代過(guò)程中起重要作用，通常用括號(hào)括起來(lái)。,,59,法則4: 換基迭代運(yùn)算法則,確定換入變量xk、換出變量xl以后，下一個(gè)環(huán)節(jié)是以xk替換xl，把約束方程組變換為對(duì)新基變量的解出形式。前面已經(jīng)提及，這種變換等價(jià)于方程組的增廣矩陣實(shí)施行的初等變換，結(jié)果使得變

39、量xk的系數(shù)列向量成為單位向量，且其第l個(gè)分量為1。因此得到以下法則：,60,對(duì)方程組的增廣矩陣實(shí)施行的初等變換，使主元alk化為1，主元列其它元素化為0。具體地說(shuō)，第l行乘以1/alk，并將第l行的－aik/alk倍加到第i行上去，i=1，2，…，m，i≠l。與此同時(shí)，對(duì)單純形表的CB列和XB列作適當(dāng)調(diào)整，再按公式計(jì)算檢驗(yàn)數(shù)，就得到下一張單純形表。然后返回法則1，檢驗(yàn)新表的最優(yōu)性。循環(huán)使用上述法則，直到求出最優(yōu)解或判定無(wú)最優(yōu)解。,6

40、1,例 求解線性規(guī)劃：max z = 50x1 + 30x2 s.t. 4x1 + 3x2 ? 120 2x1 + x2 ? 50 x1, x2 ? 0,,62,解：將原問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)型模型： max z = 50x1+ 30x2s.t. 4x1 + 3x2 + x3 =

41、120 2x1 + x2 + x4 = 50 x1 , x2 , x3 , x4 ? 0 選 x3 , x4 為基變量,63,單純形計(jì)算表,c 50 30 0 0 cB xB b x1 x2 x3 x4

42、 ? 0 x3 120 4 3 1 0 30 0 x4 50 2 1 0 1 25 σj 0 50 30 0 0,

43、,,,,,,,,1,1/2,1/2,20,25,0,1,-2,x1,50,1250,0,5,-25,20,50,,,,,,64,c 50 30 0 0 cB xB b x1 x2 x3 x4 ? 0 x3 20 0 1 1 -

44、2 2050 x1 25 1 1/2 0 1/2 50 σj 1250 0 5 0 -25,,,,,,,,,,,1350,0,-1/2,3/2,15,0,-5,-15,x2,30,最優(yōu)解為x* = (15, 20, 0, 0), z* = 1350,65,例 求下列LP問(wèn)題的最優(yōu)解（課題練習(xí)）,,66,解:

45、方程組中x1，x4，x6的系數(shù)矩陣正好是單位陣，可以直接列單純形表計(jì)算：,67,第三表中，所有σj≤0，故X*=（0，4，5，0，0，11）T，z*=－1×4+3×5=11,68,4. 關(guān)于單純形法的補(bǔ)充說(shuō)明,（1）無(wú)窮多最優(yōu)解與唯一最優(yōu)解的判別法則若對(duì)某可行解X1，（1）所有檢驗(yàn)數(shù)σj≤0，且有一個(gè)非基變量xk的檢驗(yàn)數(shù)等于0，則問(wèn)題有無(wú)窮多最優(yōu)解；（2）所有非基變量的檢驗(yàn)數(shù)σj<0，則問(wèn)題有唯一最優(yōu)解。,6

46、9,證明 （1）此時(shí)按法則1，X1已是最優(yōu)解，設(shè)目標(biāo)函數(shù)最優(yōu)值為z*，以xk為換入變量進(jìn)行迭代運(yùn)算，可得另一基可行解X2，由于σk=0，換入xk后，目標(biāo)函數(shù)值不變，故X2也是最優(yōu)解。不難證明，對(duì)于區(qū)間[0，1]之中的所有實(shí)數(shù)α，αX1+（1－α）X2都是最優(yōu)解。（2）由于每個(gè)非基變量的檢驗(yàn)數(shù)σj<0，任何一個(gè)非基變量入基都會(huì)使目標(biāo)函數(shù)值下降，因此不可能有更好的（或同樣好的）基可行解，X1是唯一最優(yōu)解。,70,例 討論線性規(guī)劃的

47、最優(yōu)解的類型,,71,解 約束方程組已經(jīng)是關(guān)于x3，x2的解出形式，直接列表求解：,72,在初始表中，所有σj≤0，所以初始基可行解就是最優(yōu)解，X1*=(0,0,1,0)T，z*=2。由于非基變量x1的檢驗(yàn)數(shù)σ1=0，引入x1，得到第二表，從中得到另一個(gè)最優(yōu)解X2*=(1,1,0,0)T。所以問(wèn)題有無(wú)窮多最優(yōu)解αX1*+(1－α)X2* (0≤α≤1),73,（2）無(wú)界解的判定,若對(duì)基可行解X1，存在非基變量xk的檢驗(yàn)數(shù)σk>

48、0，但aik≤0，i=1，2，…，m。即xk的系數(shù)列向量無(wú)正分量，則問(wèn)題有無(wú)界解。證： 在約束方程組中，令xk=λ>0；xj=0，j=m+1，m+2，…，n，j≠k；xi=bi－aikλ，i=1，2，…， m。由于aik≤0，i=1，2，…，m，所以對(duì)于任意λ>0，上述決策變量的值都是可行解；相應(yīng)的z=z1+σkλ，顯然當(dāng)λ→+∞時(shí)，z→+∞。,74,例,max Z=3x1+2x2 -2x

49、1+2x2≤ 3 x1-2x2 ≤2 x1,x2≥ 0,,標(biāo)準(zhǔn)型,max Z=3x1+2x2 -2x1+2x2+x3 = 3 x1-2x2 +x4=2 x1,x2,x3,x4≥ 0,,,,,,√,√,75,,因?yàn)棣?=8 ≥ 0，對(duì)應(yīng)的p´= -2 -2 T<0

50、,,,所以為無(wú)界解,76,（3）求min z 的情況,這時(shí)可以有兩種處理方式，一種方式是令z1=－z，轉(zhuǎn)化為求max z1，另一種是直接計(jì)算，計(jì)算規(guī)則作相應(yīng)的改變。,77,,,,,,標(biāo)準(zhǔn)型,,,,,最優(yōu)性檢驗(yàn),,換入變量的確定,換出變量的確定,相同,,,78,例 求LP的最優(yōu)解,,79,解： 約束方程組不是典式，不能立即列表計(jì)算。不過(guò)，本例很容易化為典式。,它是關(guān)于變量x2，x3的解出形式，以x2，x3為初始基變量列單純形表計(jì)算如下：,

51、,80,81,（4）初始可行基的求法—人工變量法,利用單純形表求解線性規(guī)劃的前提是，已知初始基可行解，即約束方程組的系數(shù)矩陣A中包含m階單位陣。前面的例題，或者約束全為“≤”型，松弛變量正好構(gòu)成初始基變量，或者從方程組中容易看出初始基變量。但是一般情況下，往往難以看出哪些變量可以充當(dāng)這個(gè)角色。通常的做法是引入人工變量，人為地構(gòu)造一組初始基變量。具體處理方法有大M法和兩階段法兩種不同的形式。,回本章目錄,82,大M法（罰函數(shù)法，虛擬變量法

52、）,求下列LP問(wèn)題的最優(yōu)解,,83,解 引入松弛變量x4，x5，把問(wèn)題化為標(biāo)準(zhǔn) 形式的LP,(P1),,84,給后兩個(gè)方程分別添加人工變量x6，x7，使約束方程組化為,,85,變量x4，x6，x7構(gòu)成初始基變量。但是只有x6=x7=0，新約束方程組才與原來(lái)的方程組等價(jià)。為了迫使x6，x7轉(zhuǎn)化為0，在目標(biāo)函數(shù)中令x6，x7的系數(shù)是任意大正數(shù)M的相反數(shù)－M（如果求最小值，應(yīng)取為M）。,,86,列

53、單純形表，檢驗(yàn)數(shù) σ是含M的多項(xiàng)式，以M的系數(shù)定正負(fù)。,√,√,,87,√,√,,88,√,√,,89,最優(yōu)解為X*=（4，1，9，0，0）T，x6*=x7*=0；因此原問(wèn)題最優(yōu)解為X*，z*=2。,,90,求解LP問(wèn)題,,91,解 引入松弛變量x3，x4和人工變量x5，x6， 得到下列線性規(guī)劃,,92,輔助問(wèn)題最優(yōu)解中人工變量x5*=5>0，故原問(wèn)題無(wú)可行解。,93,兩階段法,繼續(xù)討論大M法中LP問(wèn)題兩階段法是另一種處理人

54、工變量的方法。它的第一階段是先解輔助問(wèn)題,,大M法在計(jì)算機(jī)上應(yīng)用時(shí)，有時(shí)會(huì)產(chǎn)生溢出現(xiàn)象（M太大，字長(zhǎng)不夠）容易出錯(cuò)。,94,當(dāng)用單純形法求解輔助問(wèn)題時(shí)，若最優(yōu)解中人工變量全為0，x6*=x7*=0，人工變量全部退出基，說(shuō)明各方程的基變量是非人工變量，從而得到原問(wèn)題的基可行解。刪去輔助問(wèn)題最優(yōu)表中人工變量各列，把目標(biāo)函數(shù)系數(shù)換成原來(lái)z的系數(shù)，然后（即第二階段）繼續(xù)求解。若輔助問(wèn)題最優(yōu)解中人工變量不全為0，w*>0，則原無(wú)可行解。輔

55、助問(wèn)題的計(jì)算過(guò)程如下表。,95,96,最優(yōu)表中，人工變量已全部退出基。去掉最優(yōu)表中x6，x7兩列，把目標(biāo)函數(shù)系數(shù)換成z的系數(shù)，繼續(xù)第二階段的計(jì)算。,97,最后得原問(wèn)題的最優(yōu)解X*=(4，1，9，0，0)T，z*=2。,98,（5）關(guān)于退化解的說(shuō)明,LP問(wèn)題,,99,求解過(guò)程如表所示,100,在初始表中，最小比值有兩個(gè)，導(dǎo)致迭代后基變量x2=0。這樣的基可行解稱為退化解。在退化解的情況下，迭代前后目標(biāo)函數(shù)值可能不變，本問(wèn)題從第二表到第三表

56、，z值均為-4。因而存在這樣的可能：經(jīng)過(guò)若干次迭代之后，又轉(zhuǎn)回到原來(lái)的基可行解，計(jì)算過(guò)程出現(xiàn)循環(huán)，人們已經(jīng)發(fā)現(xiàn)了這樣的實(shí)例。為了防止循環(huán)，最簡(jiǎn)單的方法是對(duì)迭代法則作如下修改和補(bǔ)充。,101,（1）若有幾個(gè)變量的檢驗(yàn)數(shù)相等且都大于0，選其中下標(biāo)最小者入基；（2）若有幾個(gè)比值均為最小時(shí)，選對(duì)應(yīng)下標(biāo)最小的變量出基。按上述法則去做，一定能防止循環(huán)。但在實(shí)際問(wèn)題中，循環(huán)是極為罕見(jiàn)的，平常人們還是采用原法則進(jìn)行計(jì)算。,練習(xí)（大M法）,,103,

57、,作業(yè)：（大M法）,105,106,,107,108,本 章 小 結(jié),本章討論了線性規(guī)劃的概念和它的基本解法——單純形法，重點(diǎn)內(nèi)容有：（1）線性規(guī)劃的一般形式和標(biāo)準(zhǔn)形式；（2）基本解和基本可行解的概念；（3）檢驗(yàn)數(shù)的意義及計(jì)算公式；（4）單純形法迭代的四個(gè)法則（最優(yōu)性判定，確定換入變量，確定換出變量，換基迭代運(yùn)算）；（5）人工變量的概念和應(yīng)用方法。,109,單純形法計(jì)算框圖如下：,110,第三節(jié) 線性規(guī)劃的典型案例,一、配送中

58、心選擇,例：某企業(yè)存在兩個(gè)供貨源（S1、S2），已知原有供貨源S1每月的供貨能力是5萬(wàn)臺(tái)產(chǎn)品，新增供貨源S2的生產(chǎn)能力可以滿足產(chǎn)品的需求，且兩個(gè)貨源的價(jià)格相同。有三個(gè)目標(biāo)市場(chǎng)，各銷地每月的市場(chǎng)需求量為5萬(wàn)臺(tái)、10萬(wàn)臺(tái)、5萬(wàn)臺(tái)。在分銷渠道中，擬定在2個(gè)地點(diǎn)中選址設(shè)立分銷中心，執(zhí)行產(chǎn)品的轉(zhuǎn)運(yùn)任務(wù)。各地之間的單位運(yùn)輸物流成本如圖。問(wèn)如何安排調(diào)運(yùn)，使總的運(yùn)輸費(fèi)用最??？,111,第三節(jié) 線性規(guī)劃的典型案例,一、配送中心選擇,決策變量：設(shè)從供貨源

59、到分銷中心的運(yùn)輸量為 ，從分銷中心到需求市場(chǎng)的運(yùn)輸量為 。選址規(guī)劃在于二者的實(shí)際取值。如果 ，則不設(shè)置分銷中心W1；反之，則設(shè)置,其規(guī)模為 如果 ，則不設(shè)置分銷中心W2；反之，則設(shè)置，其規(guī)模為 目標(biāo)函數(shù)：各條路段上的實(shí)際運(yùn)輸量乘以物流運(yùn)輸?shù)膯挝毁M(fèi)用之總和最小，即 存在供應(yīng)能力約束、市場(chǎng)需求約束、配送中轉(zhuǎn)約束，如下：,,,,,,,112,第三節(jié) 線性規(guī)劃的典型案例

60、,一、配送中心選擇,供應(yīng)能力平衡約束：市場(chǎng)需求平衡約束配送中心不存留產(chǎn)品所有變量大于等于零,113,第三節(jié) 線性規(guī)劃的典型案例,二、污水處理問(wèn)題,例：有兩個(gè)化工廠向同一河流中排放污水，如圖所示。流經(jīng)第一化工廠的河水流量為500萬(wàn)立方米/天，在兩個(gè)工廠之間有一條支流進(jìn)入，流量為200萬(wàn)立方米/天。第一化工廠排放污水2萬(wàn)立方米/天。第二化工廠排污1.4萬(wàn)立方米/天。一廠排出的污水流到二廠以前，有20％可以自然凈化，根據(jù)環(huán)

61、保要求，河水中污水含量不應(yīng)大于2‰。這兩個(gè)工廠需要各自處理一部分污水。一廠的污水處理成本是1000元/萬(wàn)立方米，二廠的污水處理成本是800元/萬(wàn)立方米，問(wèn)各廠應(yīng)各自處理多少污水，使兩廠的污水處理費(fèi)用總額為最低。,114,第三節(jié) 線性規(guī)劃的典型案例,二、污水處理問(wèn)題,設(shè)決策變量 為一廠污水處理量， 為二廠污水處理量。從一廠到二廠之間的河水中污水含量不得高于2‰

62、‰二廠下游河水中污水含量也要低于2‰ ‰各廠污水處理量應(yīng)小于其排放量,115,第三節(jié) 線性規(guī)劃的典型案例,三、合理下料問(wèn)題,例：某建筑公司要用鋁型材作為構(gòu)架，制作100個(gè)鋁合金窗子，每個(gè)窗子需要2.8米的材料3根，1.8米的2根，1.17米的4根，0.6米的4根

63、，原材料每根6米，怎樣下料，才能使余料最少?,下料的可能方案,116,第三節(jié) 線性規(guī)劃的典型案例,三、合理下料問(wèn)題,這個(gè)問(wèn)題的數(shù)學(xué)模型為：,117,第三節(jié) 線性規(guī)劃的典型案例,三、合理下料問(wèn)題 （另一種模型為）,這個(gè)問(wèn)題的數(shù)學(xué)模型為：,設(shè)長(zhǎng)度為2.8米的材料多余根數(shù)為s1，1.8米多余s2，1.17米多余s3，0.6米多余s4。,118,第三節(jié) 線性規(guī)劃的典型案例,四、營(yíng)養(yǎng)配餐問(wèn)題,例：假定一個(gè)成年人每天需要從食物中獲得3000千卡的熱

64、量、55克蛋白質(zhì)和800毫克的鈣。如果市場(chǎng)上只有四種食品可供選擇(當(dāng)然可以擴(kuò)充到n種食品)，它們每千克所含的熱量和營(yíng)養(yǎng)成分和市場(chǎng)價(jià)格見(jiàn)表2-3。問(wèn)如何選擇才能在滿足營(yíng)養(yǎng)的前提下使購(gòu)買食品的費(fèi)用最?。?119,第三節(jié) 線性規(guī)劃的典型案例,四、營(yíng)養(yǎng)配餐問(wèn)題,建模：設(shè)xj為第種食品每天的購(gòu)入量，則配餐問(wèn)題的線性規(guī)劃模型為：,120,醫(yī)院護(hù)士24小時(shí)值班，每次值班8小時(shí)。不同時(shí)段需要的護(hù)士人數(shù)不等。據(jù)統(tǒng)計(jì)：,五、人員值班問(wèn)題,第三節(jié) 線性規(guī)劃

65、的典型案例,121,建模,目標(biāo)函數(shù)：min Z=x1+x2+x3+x4+x5+x6約束條件： x1+x2 ≥70 x2+x3 ≥60 x3+x4 ≥ 50

66、 x4+x5 ≥20 x5+x6 ≥30 x1 +x6 ≥60非負(fù)性約束：xj ≥0,j=1,2,…6,,122,課堂練習(xí)1— 生產(chǎn)計(jì)劃問(wèn)題 某廠生產(chǎn)兩種產(chǎn)品

67、，需要三種資源，已知各產(chǎn)品的利潤(rùn)、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表：?jiǎn)栴}：如何安排生產(chǎn)計(jì)劃，使得獲利最多？,123,完整的數(shù)學(xué)模型,max Z=10X1+14X2 9X1+4X2≤460 4X1+5X2≤250 3X1+10X2≤320 X1≥0，X2≥0,,124,課堂練習(xí)2——配方問(wèn)題 養(yǎng)海貍鼠飼料中營(yíng)養(yǎng)要求：VA每天至少7

68、00克，VB每天至少30克，VC每天剛好200克?，F(xiàn)有五種飼料，搭配使用，飼料成分如下表：,125,完整的數(shù)學(xué)模型,minZ=2x1+7x2+4x3+9x4+5x5 3x1+2x2+x3+6x4+18x5 ≥700 x1+0.5x2+0.2x3+2x4+0.5x5 ≥30 0.5x1+x2+0.2x3+2x4+0.8x5=200 x1 ≥0,x2 ≥0,x3 ≥0, x4 ≥0,x5 ≥0,,1

69、26,課堂練習(xí)3 農(nóng)作物布局問(wèn)題,某農(nóng)場(chǎng)要在 B1，B2，…，Bn n 塊土地上，種植 A1，A2，…，Am m 種農(nóng)作物。各種作物計(jì)劃播種面積及各種作物在各塊地上的單產(chǎn)（每畝的產(chǎn)量）如下表所示，問(wèn)應(yīng)如何合理安排種植計(jì)劃，才使總產(chǎn)量最大？,127,表中：ai 表示作物 Ai 的播種面積（i=1,2,…,m);,bj 表示土地 Bj 的畝數(shù)（j=1,2,…,n);,128,cij 表示在土地Bj 上種植作物 Ai 的單產(chǎn)數(shù)