管理運籌學講義第1章線性規(guī)劃

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

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

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

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

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

6、足：供應平衡條件,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,非負性約束 xij≥0 (i=1,2,3；j=1,2,3,4),7,第一節(jié) 線性規(guī)劃的一般模型,3.產(chǎn)品配比問題,,例：用濃度45%和92%的

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

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

9、標函數(shù)；xj ，j = 1 , 2 ,…, n 為決策變量； cj ，j = 1 , 2 , … , n 為價值系數(shù); bi ，i = 1 , 2 ,… , m 為資源常數(shù)；aij ，i = 1 , 2 , … , m ; j = 1 , 2 , … , n 為工藝系數(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、目標函數(shù) Z= 3x1 +5 x2 代表以 Z 為參數(shù)的一族平行線。最優(yōu)解點C(4,5)，MaxZ=37,13,五、線性規(guī)劃解的可能性,第一節(jié) 線性規(guī)劃的一般模型,1. 唯一最優(yōu)解：只有一個最優(yōu)點,,2. 多重最優(yōu)解：無窮多個最優(yōu)解,,14,五、線性規(guī)劃解的可能性,第一節(jié) 線性規(guī)劃的一般模型,3. 無界解：可行域無界，目標函數(shù)值無限增大或減小,,15,五、線性規(guī)劃解的可能性,第一節(jié) 線性規(guī)劃的一般模型,4. 沒有可行解：線性規(guī)劃問

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

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

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

15、非負剩余變量，使其為等式。 5）若某決策變量xk無非負約束，令xk=x'k-x"k ，(x'k≥ 0,x"k ≥0) 。,21,非標準型轉化舉例,minZ=x1+2x2-3x3 x1+x2+x3 ≤9 -x1-2x2+x3 ≥2 3x1+x2-3x3=5 x1≤0，x2≥0， x3無約束,,標準型為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ī)劃問題 LP： A是 m?n 滿秩矩陣, n > m，如果 B 是其中任一個 m ? m 滿秩子矩陣，則稱 B 是 LP 的一個基。,第二節(jié) 線性規(guī)劃

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

19、等價于 BxB = b，由于 B 滿秩， BxB = b 有唯一解 ：xB = B-1b 則 x = (xB , xN ) = (B?1b, 0) 是線性規(guī)劃 P 的基本解。最多為C mn個,26,,,基本可行解與可行基滿足非負條件的基本解為基本可行解，即 XB=B-1b≥0 。該解對應的基為可行基。,可行解,基本可行解,基本解,第二節(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ī)劃問題標準形式的約束條件有關。,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個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ī)劃問題的基。其余均為非奇異方陣，因此該問題共有9個基。 對于基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，對應的基本可行解： x(3) =(x1，x2，x3，x4，x5)T=(15，10，0，0，45)T。,30,于是對應的基B3是一個可行基。類似可得到: x(1) = (7.5,25,-7.5,0,0)T （對應B1） x(2) = (5,25,0,5,0)T （對應B

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

41、120 2x1 + x2 + x4 = 50 x1 , x2 , x3 , x4 ? 0 選 x3 , x4 為基變量,63,單純形計算表,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問題的最優(yōu)解（課題練習）,,66,解:

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

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

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

48、0，但aik≤0，i=1，2，…，m。即xk的系數(shù)列向量無正分量，則問題有無界解。證： 在約束方程組中，令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，所以對于任意λ>0，上述決策變量的值都是可行解；相應的z=z1+σkλ，顯然當λ→+∞時，z→+∞。,74,例,max Z=3x1+2x2 -2x

49、1+2x2≤ 3 x1-2x2 ≤2 x1,x2≥ 0,,標準型,max Z=3x1+2x2 -2x1+2x2+x3 = 3 x1-2x2 +x4=2 x1,x2,x3,x4≥ 0,,,,,,√,√,75,,因為σ2=8 ≥ 0，對應的p´= -2 -2 T<0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

65、的典型案例,121,建模,目標函數(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非負性約束：xj ≥0,j=1,2,…6,,122,課堂練習1— 生產(chǎn)計劃問題 某廠生產(chǎn)兩種產(chǎn)品

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

68、00克，VB每天至少30克，VC每天剛好200克?，F(xiàn)有五種飼料，搭配使用，飼料成分如下表：,125,完整的數(shù)學模型,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,課堂練習3 農(nóng)作物布局問題,某農(nóng)場要在 B1，B2，…，Bn n 塊土地上，種植 A1，A2，…，Am m 種農(nóng)作物。各種作物計劃播種面積及各種作物在各塊地上的單產(chǎn)（每畝的產(chǎn)量）如下表所示，問應如何合理安排種植計劃，才使總產(chǎn)量最大？,127,表中：ai 表示作物 Ai 的播種面積（i=1,2,…,m);,bj 表示土地 Bj 的畝數(shù)（j=1,2,…,n);,128,cij 表示在土地Bj 上種植作物 Ai 的單產(chǎn)數(shù)