運(yùn)籌學(xué)課件第一章

1、第一第一 章章 線性規(guī)劃線性規(guī)劃1 線性規(guī)劃問題及其模型線性規(guī)劃問題及其模型2 線性規(guī)劃問題幾何意義線性規(guī)劃問題幾何意義3 單純形法單純形法4 單純形法計(jì)算步驟單純形法計(jì)算步驟5 單純形法進(jìn)一步討論單純形法進(jìn)一步討論6 應(yīng)用舉例應(yīng)用舉例線性規(guī)劃（線性規(guī)劃（LP）簡介）簡介 線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支。由前蘇聯(lián)線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支。由前蘇聯(lián)經(jīng)濟(jì)學(xué)家康托洛維奇于經(jīng)濟(jì)學(xué)家康托洛維奇于1939年提出，而此人也因年提出，而此人也因此獲得此獲得1975年的諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。年的諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。 線性規(guī)劃是一類特殊的最優(yōu)化問題，它是針對(duì)線性規(guī)劃是一類特殊的最優(yōu)化問題，它是針對(duì)一類有限資源如何合理

2、利用這樣的問題而提出的。一類有限資源如何合理利用這樣的問題而提出的。 1947年年 G.B.Dantzig 提出求線性規(guī)劃的單純形提出求線性規(guī)劃的單純形法（法（simple method），理論上趨向成熟，實(shí)際上），理論上趨向成熟，實(shí)際上的應(yīng)用也越來越廣泛。的應(yīng)用也越來越廣泛。例例1 1 生產(chǎn)計(jì)劃問題生產(chǎn)計(jì)劃問題某企業(yè)要在計(jì)劃期內(nèi)安排生產(chǎn)甲、乙兩種產(chǎn)品，某企業(yè)要在計(jì)劃期內(nèi)安排生產(chǎn)甲、乙兩種產(chǎn)品，這個(gè)企業(yè)現(xiàn)有的生產(chǎn)資料是：設(shè)備這個(gè)企業(yè)現(xiàn)有的生產(chǎn)資料是：設(shè)備1818臺(tái)時(shí)，原材臺(tái)時(shí)，原材料料A 4A 4噸，原材料噸，原材料 B 12B 12噸；已知單位產(chǎn)品所需消噸；已知單位產(chǎn)品所需消耗生產(chǎn)資料及利潤

3、如表耗生產(chǎn)資料及利潤如表1 1。問應(yīng)如何確定生產(chǎn)計(jì)劃使企業(yè)獲利最多。問應(yīng)如何確定生產(chǎn)計(jì)劃使企業(yè)獲利最多。 1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型1.1 問題的提出問題的提出 產(chǎn)品產(chǎn)品資源資源甲甲已已資源量資源量設(shè)備設(shè)備/ /機(jī)時(shí)機(jī)時(shí)3218原料原料A/A/噸噸104原料原料B/B/噸噸0212單位贏利單位贏利/ /萬元萬元35n首先首先明確要我們決策什么明確要我們決策什么確定產(chǎn)品甲、乙的生產(chǎn)量。確定產(chǎn)品甲、乙的生產(chǎn)量。n為了定量分析解決這個(gè)問題，首先應(yīng)建立其數(shù)學(xué)模型。為了定量分析解決這個(gè)問題，首先應(yīng)建立其數(shù)學(xué)模型。n設(shè)設(shè) x1 、x2 分別表示甲、乙兩種產(chǎn)品的產(chǎn)量，稱為分別表示甲

4、、乙兩種產(chǎn)品的產(chǎn)量，稱為決策變量決策變量. .n用一組決策變量用一組決策變量( (x1 ,x2) )表示一個(gè)表示一個(gè)方案方案，變量的不同取值表示，變量的不同取值表示不同的方案。（不同的方案。（目標(biāo)：找尋最優(yōu)方案目標(biāo)：找尋最優(yōu)方案。）。）n其次其次分析分析 x1、x2 應(yīng)滿足什么條件，才能使生產(chǎn)正常進(jìn)行。應(yīng)滿足什么條件，才能使生產(chǎn)正常進(jìn)行。由于現(xiàn)有的生產(chǎn)資料總量是有限的由于現(xiàn)有的生產(chǎn)資料總量是有限的. .因此，因此， 正常生產(chǎn)過程中生產(chǎn)資料消耗不能超過現(xiàn)有量正常生產(chǎn)過程中生產(chǎn)資料消耗不能超過現(xiàn)有量. 問題分析問題分析問題分析問題分析 現(xiàn)在的問題是找出現(xiàn)在的問題是找出 x1 、x2 ，在上述各種條

5、件，在上述各種條件限制下，使限制下，使 Z 達(dá)到最大值。達(dá)到最大值。0,021xx2153xxz40121xx122021xxx1 、x2應(yīng)同時(shí)滿足下列條件：應(yīng)同時(shí)滿足下列條件：設(shè)備臺(tái)時(shí)限制設(shè)備臺(tái)時(shí)限制原材料原材料A限制限制原材料原材料B限制限制由于產(chǎn)品產(chǎn)量不能是負(fù)的，故有非負(fù)限制：由于產(chǎn)品產(chǎn)量不能是負(fù)的，故有非負(fù)限制：該生產(chǎn)計(jì)劃的總利潤為：該生產(chǎn)計(jì)劃的總利潤為：123218xx12max 35zxx綜上所述，該生產(chǎn)計(jì)綜上所述，該生產(chǎn)計(jì)劃問題的劃問題的數(shù)學(xué)模型數(shù)學(xué)模型為：為：121212321842120,0 xxxxxx. .t s21x5x3zmax目標(biāo)方程目標(biāo)方程約束條件約束條件非負(fù)約束

6、條件非負(fù)約束條件某公司要運(yùn)銷一種物資。該物資有甲、乙兩個(gè)產(chǎn)地，產(chǎn)某公司要運(yùn)銷一種物資。該物資有甲、乙兩個(gè)產(chǎn)地，產(chǎn)量分別是量分別是2000噸、噸、1000噸；另有噸；另有A、B、C三個(gè)銷地，銷三個(gè)銷地，銷量分別是量分別是1700噸、噸、1100噸、噸、200噸。已知該物資的單位運(yùn)噸。已知該物資的單位運(yùn)價(jià)如下表。問應(yīng)如何確定調(diào)運(yùn)方案，才能使在產(chǎn)銷平衡價(jià)如下表。問應(yīng)如何確定調(diào)運(yùn)方案，才能使在產(chǎn)銷平衡的條件下，總運(yùn)費(fèi)最低？的條件下，總運(yùn)費(fèi)最低？例例2 （物資運(yùn)輸問題）（物資運(yùn)輸問題）ABC產(chǎn)量產(chǎn)量甲甲212572000乙乙5151371000銷量銷定調(diào)運(yùn)方案就是確定從不同產(chǎn)地

7、到各個(gè)銷地的確定調(diào)運(yùn)方案就是確定從不同產(chǎn)地到各個(gè)銷地的運(yùn)輸量運(yùn)輸量。問題分析問題分析假設(shè)：假設(shè)：11x12x13x甲地運(yùn)往甲地運(yùn)往A地地B地地C地地21x22x23x乙地運(yùn)往乙地運(yùn)往A地地B地地C地地n從兩產(chǎn)地甲、乙分別調(diào)往三銷地從兩產(chǎn)地甲、乙分別調(diào)往三銷地A、B、C的物資數(shù)量應(yīng)該分別等于兩產(chǎn)的物資數(shù)量應(yīng)該分別等于兩產(chǎn)地甲、乙的產(chǎn)量地甲、乙的產(chǎn)量,所以所以 xij 應(yīng)滿足：應(yīng)滿足：10002000232221131211xxxxxx由于要求產(chǎn)銷平衡：由于要求產(chǎn)銷平衡：20011001700231322122111xxxxxxn運(yùn)到運(yùn)到A、B、C三銷地的物資數(shù)量應(yīng)三銷地的物資數(shù)量應(yīng)分別等于分別等

8、于A、B、C三銷地的銷量，所三銷地的銷量，所以以xij 還應(yīng)該滿足：還應(yīng)該滿足：顯然：顯然：3 , 2 , 1; 2 , 10jixij23222113121137515172521xxxxxxz調(diào)運(yùn)方案的總運(yùn)費(fèi)為：調(diào)運(yùn)方案的總運(yùn)費(fèi)為：建立產(chǎn)銷平衡下運(yùn)費(fèi)最省的調(diào)運(yùn)問題的數(shù)學(xué)模型：建立產(chǎn)銷平衡下運(yùn)費(fèi)最省的調(diào)運(yùn)問題的數(shù)學(xué)模型：111213212223min21257515137zxxxxxx3 , 2 , 1; 2 , 101000200020011001700. .232221131211231322122111jixxxxxxxxxxxxxt sij(1) 變量變量，或稱決策變量，是問題中要確

9、定的未知量，它用，或稱決策變量，是問題中要確定的未知量，它用以表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決以表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制；定和控制；(2)目標(biāo)函數(shù)目標(biāo)函數(shù)，它是決策變量的函數(shù)，按優(yōu)化目標(biāo)分別在這，它是決策變量的函數(shù)，按優(yōu)化目標(biāo)分別在這個(gè)函數(shù)前加上個(gè)函數(shù)前加上max或或min；(3)約束條件約束條件，指決策變量取值時(shí)受到的各種資源條件的限，指決策變量取值時(shí)受到的各種資源條件的限制，通常表達(dá)為含決策變量的等式或不等式。制，通常表達(dá)為含決策變量的等式或不等式。上述例子表明規(guī)劃問題的數(shù)學(xué)模型由三個(gè)要素組成：上述例子表明規(guī)劃問題的數(shù)學(xué)模型由三個(gè)要素組成：

10、如果規(guī)劃問題的數(shù)學(xué)模型中，決策變量的取值可以是如果規(guī)劃問題的數(shù)學(xué)模型中，決策變量的取值可以是連續(xù)的，目標(biāo)函數(shù)是決策變量的線性函數(shù)，約束條件是含連續(xù)的，目標(biāo)函數(shù)是決策變量的線性函數(shù)，約束條件是含決策變量的線性等式或不等式，則該類規(guī)劃問題的數(shù)學(xué)模決策變量的線性等式或不等式，則該類規(guī)劃問題的數(shù)學(xué)模型稱為型稱為線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型。線性規(guī)劃問題的一般數(shù)學(xué)模型線性規(guī)劃問題的一般數(shù)學(xué)模型1 122max(min)nnzc xc xc x11 11221121 1222221 122120,0,0nnnnmmmnnmna xa xa xba xa xa xba xaxaxbxxx1.2 圖解

11、法圖解法圖解法適用于求解只有兩個(gè)變量的線性規(guī)劃問題圖解法適用于求解只有兩個(gè)變量的線性規(guī)劃問題. .0 x0 xbxaxabxaxabxaxatsxcxcz21m22m11m222212112121112211,. .max(min)圖解法簡單直觀，有助于了解線性規(guī)劃問題求解圖解法簡單直觀，有助于了解線性規(guī)劃問題求解的基本原理和思想。的基本原理和思想。例例12153maxxxz0,12241823212121xxxxxx圖解法求解線性規(guī)劃問題圖解法求解線性規(guī)劃問題下面舉例說明圖解法求解線性規(guī)劃問題的步驟。下面舉例說明圖解法求解線性規(guī)劃問題的步驟。一、圖解法的步驟一、圖解法的步驟圖解法的圖解法的步

12、驟步驟可概括為：在平面上建立直角坐標(biāo)系；圖示可概括為：在平面上建立直角坐標(biāo)系；圖示約束條件，找出可行域；圖示目標(biāo)函數(shù)和尋找最優(yōu)解。約束條件，找出可行域；圖示目標(biāo)函數(shù)和尋找最優(yōu)解。0 2 4 6 8 x1x2 8 6 4 2 0 x1=42 x2 = 123x1+2x2=18可行域可行域QQ0(0,0)Q1(0,6)Q2(2,6)Q3(4,3)Q4(4,0)3x1+5x2= z =363x1+5x2= z =203x1+5x2= z =0圖解法解題過程圖解法解題過程圖圖1-12153maxxxz0,12241823212121xxxxxx可行域可行域可行解可行解最優(yōu)解最優(yōu)解凸凸 集集頂頂 點(diǎn)點(diǎn)本

13、問題只有唯一最優(yōu)解本問題只有唯一最優(yōu)解.例例2213maxxxz0, 021260521212121xxxxxxxx解解 ：-x1+x2=0 x1+x2=56x1+2x2=213x1 + x2 = z =03x1 + x2 = z =63x1 + x2 = z =21/2A(11/4, 9/4)B(21/6,0)x1x2213maxxxz0,021260521212121xxxxxxxx本問題有無窮本問題有無窮多個(gè)最優(yōu)解。多個(gè)最優(yōu)解。例例3212minxxz0,0331212121xxxxxx1x2x3321 xxzxx212解：解：121 xx212minxxz0, 0331212121xx

14、xxxx該問題的可行該問題的可行域是一個(gè)無界域是一個(gè)無界的凸多邊形。的凸多邊形。本問題有可行解，但無最優(yōu)解，稱為無界解本問題有可行解，但無最優(yōu)解，稱為無界解. .1x2xx1-x2=-1x1+x2=-1注：本問題無可行解，更無最優(yōu)解。注：本問題無可行解，更無最優(yōu)解。 213maxxxz0,11212121xxxxxx該問題的可行域是空的，即無可行解該問題的可行域是空的，即無可行解.例例4 有唯一的最優(yōu)解。有唯一的最優(yōu)解。 最優(yōu)解是可行域的一個(gè)頂點(diǎn)。最優(yōu)解是可行域的一個(gè)頂點(diǎn)。 有無窮多的最優(yōu)解。有無窮多的最優(yōu)解。 最優(yōu)解是可行域的一段邊界。最優(yōu)解是可行域的一段邊界。無界解無界解(有可行解有可行解

15、,但無最優(yōu)解但無最優(yōu)解)。產(chǎn)生無界解的原。產(chǎn)生無界解的原因是在建立實(shí)際問題的數(shù)學(xué)模型時(shí)遺漏了某些必因是在建立實(shí)際問題的數(shù)學(xué)模型時(shí)遺漏了某些必要的約束條件。要的約束條件。無可行解。產(chǎn)生原因是模型的約束條件之間存在無可行解。產(chǎn)生原因是模型的約束條件之間存在矛盾，建模時(shí)有錯(cuò)誤矛盾，建模時(shí)有錯(cuò)誤.一般線性規(guī)劃問題也有類似結(jié)論一般線性規(guī)劃問題也有類似結(jié)論? ?那結(jié)論成立的判定準(zhǔn)則如何？那結(jié)論成立的判定準(zhǔn)則如何？二、線性規(guī)劃問題求解的幾種可能結(jié)局：二、線性規(guī)劃問題求解的幾種可能結(jié)局： 圖解法的解題思路和幾何上直觀得到的一些概念判斷圖解法的解題思路和幾何上直觀得到的一些概念判斷, ,對(duì)后面的求解一般線性規(guī)劃

16、問題的單純形法有很大啟示：對(duì)后面的求解一般線性規(guī)劃問題的單純形法有很大啟示：1.1.解的情況有：唯一最優(yōu)解解的情況有：唯一最優(yōu)解, ,無窮多最優(yōu)解無窮多最優(yōu)解, ,無界解無界解, ,無可行解；無可行解；2.2.若線性規(guī)劃問題的可行域存在，則可行域是一個(gè)凸集；若線性規(guī)劃問題的可行域存在，則可行域是一個(gè)凸集；3.3.若線性規(guī)劃問題的最優(yōu)解存在若線性規(guī)劃問題的最優(yōu)解存在, ,則最優(yōu)解或最優(yōu)解之一是可則最優(yōu)解或最優(yōu)解之一是可行域的凸集的某個(gè)頂點(diǎn)；行域的凸集的某個(gè)頂點(diǎn)；4.4.解題思路是：先找出凸集的任一頂點(diǎn)解題思路是：先找出凸集的任一頂點(diǎn), ,計(jì)算在頂點(diǎn)處的目標(biāo)計(jì)算在頂點(diǎn)處的目標(biāo)函數(shù)值函數(shù)值. .比較

17、周圍相鄰頂點(diǎn)的目標(biāo)函數(shù)值是否比這個(gè)值大比較周圍相鄰頂點(diǎn)的目標(biāo)函數(shù)值是否比這個(gè)值大, ,如如果為否果為否, ,則該頂點(diǎn)就是最優(yōu)解的點(diǎn)或最優(yōu)解的點(diǎn)之一則該頂點(diǎn)就是最優(yōu)解的點(diǎn)或最優(yōu)解的點(diǎn)之一, ,否則轉(zhuǎn)否則轉(zhuǎn)到比這個(gè)點(diǎn)的目標(biāo)函數(shù)值更大的另一頂點(diǎn)到比這個(gè)點(diǎn)的目標(biāo)函數(shù)值更大的另一頂點(diǎn), ,重復(fù)上述過程。一重復(fù)上述過程。一直到找出使目標(biāo)函數(shù)值達(dá)到最大的頂點(diǎn)為止。直到找出使目標(biāo)函數(shù)值達(dá)到最大的頂點(diǎn)為止。 三、圖解法的啟示三、圖解法的啟示最大值點(diǎn)（最小值點(diǎn)）一定在可行域的邊界上！最大值點(diǎn)（最小值點(diǎn)）一定在可行域的邊界上！21xcxzmax0 x0 x10 x2x6xxts212121,.已知線性規(guī)劃問題，試用

18、圖解法分析，問題最優(yōu)解已知線性規(guī)劃問題，試用圖解法分析，問題最優(yōu)解隨隨 c（- c )變化的情況。變化的情況。練習(xí)練習(xí)線性規(guī)劃問題的一般數(shù)學(xué)模型線性規(guī)劃問題的一般數(shù)學(xué)模型1.3 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型1 122max(min)1.1nnzc xc xc x11 11221121 1222221 122121.20,0,01.3nnnnmmmnnmna xa xa xba xa xa xba xaxaxbxxx1.1.目標(biāo)函數(shù)可為最小值，也可為最大值。目標(biāo)函數(shù)可為最小值，也可為最大值。2.2.約束條件可以是線性方程組，也可以是約束條件可以是線性方程組，也可以是線性不等式組。線性不等式組

19、。3.3.有的變量可以是無約束的。有的變量可以是無約束的。 為討論方便，用統(tǒng)一的形式為討論方便，用統(tǒng)一的形式 標(biāo)準(zhǔn)形。標(biāo)準(zhǔn)形。一般線性規(guī)劃問題的特點(diǎn)：一般線性規(guī)劃問題的特點(diǎn)：1 . 1max2211nnxcxcxcz11 11221121 1222221 122121.2. .0,0,01.3nnnnmmmnnmna xa xa xba xa xa xbsta xaxaxbxxx標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形mn一般1、方程組（、方程組（1.2）中不含有多余的方程）中不含有多余的方程2、0(1. )ibim解決一般線性規(guī)劃問題的第一步：標(biāo)準(zhǔn)形的轉(zhuǎn)換解決一般線性規(guī)劃問題的第一步：標(biāo)準(zhǔn)形的轉(zhuǎn)換若目標(biāo)函數(shù)為最小值若目

20、標(biāo)函數(shù)為最小值,min2211nnxcxcxcz。nnxcxcxcz2211max將線性規(guī)劃模型化為標(biāo)準(zhǔn)型的主要步驟：將線性規(guī)劃模型化為標(biāo)準(zhǔn)型的主要步驟：只需令只需令 , 再求再求 的最大值的最大值z(mì)zz若約束關(guān)系是不等式，引入松弛變量若約束關(guān)系是不等式，引入松弛變量(slack variables) ,把不等式改成等式。把不等式改成等式。n當(dāng)約束條件是當(dāng)約束條件是“”不等式，在不等式，在“”不等式的左端減不等式的左端減去一個(gè)非負(fù)松弛變量，把去一個(gè)非負(fù)松弛變量，把“”不等式變?yōu)榈仁?。不等式變?yōu)榈仁健當(dāng)約束條件是當(dāng)約束條件是“”不等式時(shí)，在不等式時(shí)，在“”不等式左端不等式左端加入非負(fù)松弛變量，

21、加入非負(fù)松弛變量， 把原把原“”不等式變?yōu)榈仁讲坏仁阶優(yōu)榈仁?ininiibxaxaxa2211iinniniibxxaxaxa12211iinniniibxxaxaxa12211ininiibxaxaxa2211若變量不滿足若變量不滿足“0”。0jx,jjxx jxjxn當(dāng)當(dāng)，可記，可記用用代替代替jx,jjjxxxn當(dāng)當(dāng)無約束時(shí)，無約束時(shí)，可記可記0,jx jjxx0,jx jx其中其中用用代替代替注：任意實(shí)數(shù)都可以表示為兩個(gè)非負(fù)實(shí)數(shù)的差，注：任意實(shí)數(shù)都可以表示為兩個(gè)非負(fù)實(shí)數(shù)的差，如如1=3-2=8-7；-1=0-1=10-11則在約束方程兩邊同乘則在約束方程兩邊同乘 -1。0ib當(dāng)當(dāng)例例

22、1 將下列線性規(guī)劃化成標(biāo)準(zhǔn)形將下列線性規(guī)劃化成標(biāo)準(zhǔn)形。2153maxxxz0,12241823212121xxxxxx例例1 將下列線性規(guī)劃化成標(biāo)準(zhǔn)形將下列線性規(guī)劃化成標(biāo)準(zhǔn)形。2153maxxxz0,12241823212121xxxxxx,543xxx、解：先引入三個(gè)松弛變量解：先引入三個(gè)松弛變量等式等式中分別加上松弛變量使不等式化為等式，中分別加上松弛變量使不等式化為等式，在每個(gè)約束不在每個(gè)約束不3x1+2x2 183x1+2x2+x3 =18+x3x1 4x1 +x4 =4+x4 2x2 12 2x2 +x5=12+x5得到標(biāo)準(zhǔn)形：得到標(biāo)準(zhǔn)形：0,12241823543215241321

23、xxxxxxxxxxxx12345max35000zxxxxx利用的資源，當(dāng)然不會(huì)產(chǎn)生利潤，故在目標(biāo)函數(shù)中利用的資源，當(dāng)然不會(huì)產(chǎn)生利潤，故在目標(biāo)函數(shù)中的系數(shù)應(yīng)為的系數(shù)應(yīng)為0。此時(shí)，。此時(shí)，z 仍可簡寫為仍可簡寫為 ,543xxx、2153xxz注：注：加入的松弛變量加入的松弛變量可以看成沒有被可以看成沒有被解解: 在第一個(gè)約束方程兩端同乘在第一個(gè)約束方程兩端同乘 -1； 令令 ，其中，其中 在第二個(gè)約束不等式左端加上松弛變量在第二個(gè)約束不等式左端加上松弛變量 ； 在第三個(gè)約束不等式左端減去松弛變量在第三個(gè)約束不等式左端減去松弛變量 ； 令令 ；化；化 為為 。444xxx440,0;xx6xz

24、zmaxminzz43215243minxxxxz無約束4321432143214321, 0,2232143224xxxxxxxxxxxxxxxx從而，該問題的標(biāo)準(zhǔn)型為：從而，該問題的標(biāo)準(zhǔn)型為：5x例例2 將下列線性規(guī)劃化成標(biāo)準(zhǔn)形。將下列線性規(guī)劃化成標(biāo)準(zhǔn)形。12344max34255zxxxxx12344123445123446123445642231423222,0 xxxxxxxxxxxxxxxxxx x x x x x x43215243minxxxxz無約束4321432143214321, 0,2232143224xxxxxxxxxxxxxxxx標(biāo)準(zhǔn)型為：標(biāo)準(zhǔn)型為：11111212

25、1222221212, ,nnmmmnmnnbxaaaaaabxAbXaaabxCc cc 線性規(guī)劃問題標(biāo)準(zhǔn)形的線性規(guī)劃問題標(biāo)準(zhǔn)形的矩陣表示矩陣表示：A為系數(shù)矩陣；為系數(shù)矩陣；b是資源向量，是資源向量，C是價(jià)值向量，是價(jià)值向量，X為決策變量向量為決策變量向量.1 . 1max2211nnxcxcxcz11112211211222221122121.2. .0,0,01.3nnnnmmmnnmna xa xa xba xaxaxbs taxaxaxbxxx記記m ax. .0zCXAXbs tX則矩陣表示為：則矩陣表示為：0; bAmn其中約定：秩.11112212221212,nnnmmmna

26、aaaaaPPPaaa,21nPPPA線性規(guī)劃問題線性規(guī)劃問題標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形的的向量表示向量表示:1 . 1max2211nnxcxcxcz3 .10,0,02 .1.2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats目標(biāo)函數(shù)目標(biāo)函數(shù) z = CX 可寫成：可寫成：此時(shí)約束方程此時(shí)約束方程AX=b 可寫成：可寫成：則則向量表示向量表示為：為：若令若令z = c1 x1 + c2 x2 + + cn xnP1x1 + P2 x2 + + Pn xn = bmax z = c1 x1 + c2 x2 + + cn xns.t. P1

27、x1 + P2x2 + + Pn xn = b x j 0, j = 1 , 2 , , n給定一個(gè)線性規(guī)劃問題給定一個(gè)線性規(guī)劃問題LP：1 . 1max2211nnxcxcxcz11112211211222221122121.2. .0,0,01.3nnnnmmmnnmna xa xa xba xaxaxbs taxaxaxbxxx1.4 線性規(guī)劃問題解的概念線性規(guī)劃問題解的概念1.可行解可行解 (a feasible solution)滿足約束條件的滿足約束條件的 X 稱為線性規(guī)劃問題的稱為線性規(guī)劃問題的可行解可行解;TnxxxX,21所有可行解的集合稱為所有可行解的集合稱為可行域可行域

28、(feasible region),記為記為使目標(biāo)函數(shù)達(dá)到最大值使目標(biāo)函數(shù)達(dá)到最大值的可行解稱為的可行解稱為最優(yōu)解最優(yōu)解(an optimal solution)?？尚杏蚩尚杏蚩尚薪饪尚薪釷2(2,6)2 2、基基(base)記約束方程系數(shù)矩陣記約束方程系數(shù)矩陣A的列向量是的列向量是nPPP,21即即,21nPPPA是是 A 的任意的任意 m 個(gè)列向量個(gè)列向量,設(shè)設(shè)jmjjPPP,21是線性無關(guān)的，是線性無關(guān)的，如果如果jmjjPPP,21構(gòu)成線性規(guī)劃問題的一個(gè)構(gòu)成線性規(guī)劃問題的一個(gè)基基(base)。則稱則稱12,jjjmxxx對(duì)應(yīng)的變量對(duì)應(yīng)的變量jmjjxxx,21稱為稱為基變量基變量.其余

29、的變量稱為其余的變量稱為非基變量非基變量(non-basic-variable).稱為稱為基陣基陣.矩陣矩陣jmjjPPPB,21行列式行列式0基陣基陣=目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件右邊常量右邊常量基矩陣所對(duì)應(yīng)的變量為基變量基矩陣所對(duì)應(yīng)的變量為基變量例例1 列出基變量、非基變量等各項(xiàng)參數(shù)列出基變量、非基變量等各項(xiàng)參數(shù).2153maxxxz0,12241823543215241321xxxxxxxxxxxx約束方程約束方程A的系數(shù)矩陣為：的系數(shù)矩陣為：100200100100123A10001000120201354321PPPPP，其列向量為：分別是變量分別是變量54321,xxxxx的系

30、數(shù)向量。的系數(shù)向量。100200100100123A543,PPP543,xxx5431,PPPB 向量組向量組 是線性無關(guān)組是線性無關(guān)組可構(gòu)成此問題的一個(gè)基；可構(gòu)成此問題的一個(gè)基；是相應(yīng)的基陣是相應(yīng)的基陣稱稱 為基變量，而為基變量，而 是非基變量。是非基變量。543,xxx21,xx542,PPP542,xxx5422,PPPB 542,xxx31,xx向量組向量組 是線性無關(guān)組是線性無關(guān)組可構(gòu)成此問題的一個(gè)基；可構(gòu)成此問題的一個(gè)基；是相應(yīng)的基陣是相應(yīng)的基陣.稱為基變量，稱為基變量，而而 是非基變量是非基變量.（2）設(shè)）設(shè)B是是A的一個(gè)的一個(gè) m 階子矩陣，則階子矩陣，則B是線是線性規(guī)劃問題

31、的基陣，當(dāng)且僅當(dāng)性規(guī)劃問題的基陣，當(dāng)且僅當(dāng)B是可逆陣是可逆陣 0.B （3）基的個(gè)數(shù)）基的個(gè)數(shù)（1）基不一定唯一）基不一定唯一.注：注：.mnC給定一個(gè)基給定一個(gè)基jmjjPPPB,2112,jjjmxxxNX令所有非基變量都等于令所有非基變量都等于0，即，即0NX3.基解基解12,TBjjjmXxxx基陣基陣記記為基變量向量為基變量向量.為非基變量向量為非基變量向量.則約束方程則約束方程(1.2)可化為：可化為：4 . 12211bBXbxPxPxPBjmjmjjjjP1x1 + P2x2 + + Pn xn = b 稱為相應(yīng)于基稱為相應(yīng)于基B的一個(gè)的一個(gè)基解基解 (a basic solu

32、tion)。bBXB1100BNXB bXX (1.4)BBXb它是一個(gè)它是一個(gè) m 個(gè)變量個(gè)變量 m 個(gè)方程組成的線性方程組，個(gè)方程組成的線性方程組，B又是可逆陣，從而可得又是可逆陣，從而可得(1.4)的唯一解的唯一解令令至少含有至少含有 n-m 個(gè)個(gè)0元元10BXB b如果如果則稱則稱 為一個(gè)為一個(gè)基可行解基可行解.100B bX相應(yīng)的基相應(yīng)的基B也稱為也稱為可行基可行基.2153maxxxz0,12241823543215241321xxxxxxxxxxxx5431,PPPB 為基陣為基陣543,xxx為基變量為基變量120 xx令非基變量令非基變量得到的解得到的解(0,0,18,4,1

33、2)為基解。為基解。一個(gè)基對(duì)應(yīng)一個(gè)基解一個(gè)基對(duì)應(yīng)一個(gè)基解在上例在上例1中，中，且是基可行解。且是基可行解。5422,PPPB 為基陣為基陣542,xxx為基變量為基變量130 xx令非基變量令非基變量得到的解得到的解0,9,0,4,6 .為基解。為基解。但不是基可行解。但不是基可行解。思考題：試列出例思考題：試列出例1中問題的所有基解、基可行解。中問題的所有基解、基可行解。注：基可行解的數(shù)目是有限個(gè)，不會(huì)超過注：基可行解的數(shù)目是有限個(gè)，不會(huì)超過 。mnC非可行解非可行解可行解可行解基基 解解基可行解基可行解解之間的關(guān)系解之間的關(guān)系解空間解空間2 線性規(guī)劃問題的幾何意義線性規(guī)劃問題的幾何意義那么

34、，可行域具有什么特征？那么，可行域具有什么特征？ 可行域的頂點(diǎn)與基可行解的關(guān)系？可行域的頂點(diǎn)與基可行解的關(guān)系？兩個(gè)變量的線性規(guī)劃問題的可行域是一個(gè)兩個(gè)變量的線性規(guī)劃問題的可行域是一個(gè)凸多邊形，并且如果存在最優(yōu)解，則一定凸多邊形，并且如果存在最優(yōu)解，則一定可以在可行域的頂點(diǎn)上找到。這個(gè)性質(zhì)對(duì)可以在可行域的頂點(diǎn)上找到。這個(gè)性質(zhì)對(duì)于于 n 個(gè)變量的線性規(guī)劃問題也是成立的。個(gè)變量的線性規(guī)劃問題也是成立的。設(shè)如果存在 k 個(gè)實(shí)數(shù)使得則稱 。；個(gè)點(diǎn)，中的是nnkRXkRXXX,21, 110,121kiiik，并且,2211kkXXXX的凸組合是kXXXX,212.1 凸組合、凸集與頂點(diǎn)凸組合、凸集與頂點(diǎn)

35、,:1 ,01a bx xab。例例1 在 中，給定兩個(gè)a、b，ab，則a、b在 的凸組合是閉區(qū)間1R1R a x bx凸組合凸組合例例2 在在 中，給定兩個(gè)點(diǎn)中，給定兩個(gè)點(diǎn)則則 在在 中的凸組合是以中的凸組合是以 為端點(diǎn)的直線段。為端點(diǎn)的直線段。2R,21XX,21XX2R21XX 與2X1x2x1X例例3 設(shè)設(shè) 在在 中不共線，中不共線，即即 線性無關(guān)，線性無關(guān)，則則 的凸組合是的凸組合是 中以中以 為頂點(diǎn)的閉三角形區(qū)域?yàn)轫旤c(diǎn)的閉三角形區(qū)域.321,XXX2R2131 XXXX與321,XXX2R321,XXX1X1x2x2X3X 一般地，在一般地，在 中，給定中，給定 k+1 個(gè)頂點(diǎn)個(gè)頂

36、點(diǎn) 如果如果 線性無關(guān)，線性無關(guān)，則稱則稱 的凸組合是的凸組合是 中中的一個(gè)的一個(gè) k 維維單純形單純形，簡稱單形（，簡稱單形（simplex）。）。nRnR00201,XXXXXXk,10XXkXX,2,10XXkXX,2單純形單純形設(shè)設(shè) ，如果，如果 中任意兩點(diǎn)間的連線仍屬中任意兩點(diǎn)間的連線仍屬于于 ，即對(duì)于任意，即對(duì)于任意 及及 0，1，成立成立則稱則稱 是凸集。是凸集。 nRKKK,21KXXKXX21)1 (K凸凸 集集直觀上，凸集是沒有凹入部分，且其內(nèi)部又沒直觀上，凸集是沒有凹入部分，且其內(nèi)部又沒有空洞的幾何形體。有空洞的幾何形體。 任何兩個(gè)凸集的交集是凸集。任何兩個(gè)凸集的交集是凸

37、集。設(shè)設(shè) 是一個(gè)凸集，是一個(gè)凸集， ，如果，如果 不是不是 中中任意兩個(gè)不同點(diǎn)連線的中間點(diǎn)，即任意兩個(gè)不同點(diǎn)連線的中間點(diǎn)，即X 不是不是 K 中的中的兩個(gè)不同點(diǎn)的凸組合，則稱兩個(gè)不同點(diǎn)的凸組合，則稱X是是K的一個(gè)的一個(gè)頂點(diǎn)頂點(diǎn)。nRKKX XK1X2X3X4X圖圖1-8頂頂 點(diǎn)點(diǎn) 4321,XXXX與例如，在圖例如，在圖1-8的凸多邊形的凸多邊形K 中，中，僅有四個(gè)頂點(diǎn)僅有四個(gè)頂點(diǎn) 。而在一個(gè)實(shí)心圓區(qū)域內(nèi)，其而在一個(gè)實(shí)心圓區(qū)域內(nèi)，其邊界圓周上的每個(gè)點(diǎn)都是該邊界圓周上的每個(gè)點(diǎn)都是該凸集的頂點(diǎn)。凸集的頂點(diǎn)。2.2 基可行解的性質(zhì)與幾何特征基可行解的性質(zhì)與幾何特征定理定理1. 若若 ，則，則 是凸集

38、。是凸集。 引理引理1. 設(shè)設(shè) X 是一個(gè)可行解，則是一個(gè)可行解，則 X 是基可行解當(dāng)且是基可行解當(dāng)且僅當(dāng)僅當(dāng) X 的正分量對(duì)應(yīng)的系數(shù)列向量是線性無關(guān)的的正分量對(duì)應(yīng)的系數(shù)列向量是線性無關(guān)的.定理定理2. 如果線性規(guī)劃問題有可行解，則一定有基可行解。如果線性規(guī)劃問題有可行解，則一定有基可行解。定理定理3. 設(shè)設(shè) 是一個(gè)可行解，則是一個(gè)可行解，則 是基可行解當(dāng)且僅是基可行解當(dāng)且僅 當(dāng)當(dāng) 是是 的頂點(diǎn)。的頂點(diǎn)。 0X0X0X定理定理4. 如果線性規(guī)劃問題有最優(yōu)解，則一定存在一個(gè)基如果線性規(guī)劃問題有最優(yōu)解，則一定存在一個(gè)基 可行解是最優(yōu)解?？尚薪馐亲顑?yōu)解。 應(yīng)用上述術(shù)語，我們討論線性規(guī)劃可行域的特征。

39、應(yīng)用上述術(shù)語，我們討論線性規(guī)劃可行域的特征。max. .0zCXAXbstX 不一定所有的基可行解都是最優(yōu)解，最優(yōu)解也不一定不一定所有的基可行解都是最優(yōu)解，最優(yōu)解也不一定都是基解都是基解； 如果有兩個(gè)基可行解是最優(yōu)解，則兩解的凸組合也都如果有兩個(gè)基可行解是最優(yōu)解，則兩解的凸組合也都是最優(yōu)解。是最優(yōu)解。 如果最優(yōu)解不唯一，則會(huì)有多個(gè)基本可行解是最優(yōu)解，如果最優(yōu)解不唯一，則會(huì)有多個(gè)基本可行解是最優(yōu)解，它們必然在同一個(gè)面上。它們必然在同一個(gè)面上。 基可行解個(gè)數(shù)有限，可以在基可行解中尋找最優(yōu)解?；尚薪鈧€(gè)數(shù)有限，可以在基可行解中尋找最優(yōu)解。剩余的問題是如何判斷一個(gè)基可行解是最優(yōu)解，如果剩余的問題是如何

40、判斷一個(gè)基可行解是最優(yōu)解，如果不是則如何從一個(gè)基可行解轉(zhuǎn)到另一個(gè)基可行解。不是則如何從一個(gè)基可行解轉(zhuǎn)到另一個(gè)基可行解。說明：說明：定理定理1. 若若 ，則，則 是凸集。是凸集。 ）（211XXAbbb)1 (0)1 (21XX21)1 (XX有有 。所以，可行域所以，可行域 是凸集。是凸集。21XX ，證明證明 設(shè)設(shè) ，要證對(duì)任何，要證對(duì)任何 ，00， 其所有的其所有的ik0，則線，則線性規(guī)劃問題無最優(yōu)解，計(jì)算結(jié)束；否則轉(zhuǎn)至性規(guī)劃問題無最優(yōu)解，計(jì)算結(jié)束；否則轉(zhuǎn)至step 3.Step3 進(jìn)行基變換。進(jìn)行基變換。1）確定換入變量）確定換入變量. 規(guī)則規(guī)則,找最大的找最大的其對(duì)應(yīng)的其對(duì)應(yīng)的 xk

41、就是換入變量就是換入變量. max:0kjjlklikiki0:min2）確定換出變量）確定換出變量. 規(guī)則規(guī)則,計(jì)算計(jì)算確定確定 xl 是換出變量是換出變量.找初始可行解找初始可行解X0及可行基及可行基B單純形法計(jì)算框圖單純形法計(jì)算框圖 j 0?寫出最優(yōu)解寫出最優(yōu)解與最優(yōu)值與最優(yōu)值停停是否有是否有 ik0無界解無界解N確定換出變量確定換出變量x l ,klliikik0min以以 kl為主元作基變換為主元作基變換停停NYY確定換入變量確定換入變量x k k=max j | j 001111(1)11122(1)122(1)1121max,0mmnnmmnnmmnnmm mmmnnmmmnzz

42、xxxxxxxxxxxx x xxx基變換基變換示例示例11(1)(1)mmm m1,1 1111 1mnnxxx21 1222 0 nnxxx1 1 0 mmmnnmxxx121 ,0mmnx x xxx01 1max 0nnzzxx 主元主元0011mzz例例1.利用單純形算法求解下面的線性規(guī)劃問題。利用單純形算法求解下面的線性規(guī)劃問題。121324125max35 4212. .32180(1,2, )jzxxxxxxs txxxxjn 解：本問題有一個(gè)明顯的可行基解：本問題有一個(gè)明顯的可行基x3、x4、x5，它的典式為：，它的典式為：非基變量非基變量x1、x2的檢驗(yàn)數(shù)為的檢驗(yàn)數(shù)為3、5

43、，基可行解，基可行解X0=(0,0,4,12,18)T不是最優(yōu)解，取檢驗(yàn)數(shù)最大者，不是最優(yōu)解，取檢驗(yàn)數(shù)最大者，x2作為換入變量作為換入變量121324125max35 4212. .32180(1,2, )jzxxxxxxs txxxxjn 再確定換出變量，由于：再確定換出變量，由于：6218,212,min0121324125max35 4212. .32180(1,2, )jzxxxxxxs txxxxjn 故故x4為換出變量，得到一個(gè)新可行基為換出變量，得到一個(gè)新可行基x3,x2,x5， 其典式為其典式為1413241455max3032 416. .23 60jzxxxxxxs txx

44、xx 由于由于x1的檢驗(yàn)數(shù)為的檢驗(yàn)數(shù)為30，故基可行解，故基可行解X1=(0,6,4,0,6)T不是最不是最優(yōu)解，讓優(yōu)解，讓x1為換入變量。為換入變量。令令146min, ,213 1413241455max3032 416. .23 60jzxxxxxxs txxxx 所以所以 x5 為換出變量，又得一個(gè)新基為換出變量，又得一個(gè)新基x3,x2,x1讓讓 x1 為換入變量，為換入變量，非基變量非基變量x4、x5的檢的檢驗(yàn)數(shù)是驗(yàn)數(shù)是-3/2、-1，故，故X2=(2,6,2,0,0)T是最優(yōu)是最優(yōu)解，并且是唯一最優(yōu)解，并且是唯一最優(yōu)解。解。45345241453max362112331 62112

45、330jzxxxxxxxxxxx ，其典式為：，其典式為：0 2 4 xY 6 4 2 0QQ0(0,0)Q1(0,6)Q2(2,6)Q3(4,3)Q4(4,0)基可行解與圖解法頂點(diǎn)的對(duì)應(yīng)關(guān)系基可行解與圖解法頂點(diǎn)的對(duì)應(yīng)關(guān)系圖示：圖示：X0=(0,0,4,12,18)TX1=(0,6,4,0,6)TX2=(2,6,2,0,0)T是是求解線性規(guī)劃問題的一種著名算法，它是依據(jù)求解線性規(guī)劃問題的一種著名算法，它是依據(jù)基可行解基可行解的性質(zhì)的性質(zhì)而設(shè)計(jì)的。而設(shè)計(jì)的。因因?yàn)橐粋€(gè)給定的線性規(guī)劃問題中基可行解的個(gè)數(shù)是有限的，為一個(gè)給定的線性規(guī)劃問題中基可行解的個(gè)數(shù)是有限的，只要把所有的基可行解一一檢查就可以在

46、有限次得到最優(yōu)只要把所有的基可行解一一檢查就可以在有限次得到最優(yōu)解或者斷定所給問題無最優(yōu)解，這種求解過程可在一個(gè)所解或者斷定所給問題無最優(yōu)解，這種求解過程可在一個(gè)所謂謂單純形表單純形表中進(jìn)行，也易于編制計(jì)算程序，因而在實(shí)際問中進(jìn)行，也易于編制計(jì)算程序，因而在實(shí)際問題中得到廣泛應(yīng)用。題中得到廣泛應(yīng)用。就就算法復(fù)雜性算法復(fù)雜性分析來講，單純形方法不是一個(gè)有效算法，分析來講，單純形方法不是一個(gè)有效算法，即對(duì)于極端問題，它的運(yùn)算次數(shù)是問題輸入大小即對(duì)于極端問題，它的運(yùn)算次數(shù)是問題輸入大小(size)的一的一個(gè)指數(shù)型函數(shù)；由于這種極端問題出現(xiàn)的概率很少，因此，個(gè)指數(shù)型函數(shù)；由于這種極端問題出現(xiàn)的概率很少

47、，因此，在處理實(shí)際工作中的問題時(shí)并不構(gòu)成多大妨礙在處理實(shí)際工作中的問題時(shí)并不構(gòu)成多大妨礙.單純形法單純形法(simple method)4.2 單純形表單純形表 單純形表單純形表(simple tableau)是為單純形算法而是為單純形算法而設(shè)計(jì)的一種計(jì)算表，其功能類似于方程組的設(shè)計(jì)的一種計(jì)算表，其功能類似于方程組的增廣矩陣，易于進(jìn)行基變換運(yùn)算。增廣矩陣，易于進(jìn)行基變換運(yùn)算。設(shè)可行基設(shè)可行基 的典式為：的典式為： 12,mxxx 01111(1)11122(1)122(1)1max 1.41.501,2, 1.6mmnnmmnnmmnnmm mmmnnmjzzxxxxxxxxxxxxjn 將式

48、將式(1.4)與與(1.5)組成一個(gè)組成一個(gè)m+1個(gè)方程、個(gè)方程、n+1個(gè)變量的方程組為個(gè)變量的方程組為11(1)11122(1)122(1)1110 mmnnmmnnmm mmmnnmmmnnxxxxxxxxxzxxz 121 mmnzxxxxx 111122211100100001000011000nmnmmnmm mmnz 此方程組的增廣矩陣為：此方程組的增廣矩陣為：11(1)11122(1)122(1)1110 mmnnmmnnmm mmmnnmmmnnxxxxxxxxxzxxz 其中基變量其中基變量 的系數(shù)構(gòu)成單位矩陣，的系數(shù)構(gòu)成單位矩陣，z是是 一個(gè)不參一個(gè)不參與基變換的變量。與基

49、變換的變量。mxxx,21可設(shè)計(jì)可設(shè)計(jì)單純形表單純形表表表4-1單純形表單純形表1211211111,11,2222,12,1,01.10.0.01.0.00.1.00.0.mmnBmmnmnmnmmmm mm nmncccccXbxxxxxcxacxacxaz基變量的價(jià)值系數(shù)基變量基矩陣非基變量檢驗(yàn)數(shù)負(fù)目標(biāo)函數(shù)1111,122,1,1(.)mmmmmm mcccc11,22,(.) nnnnmm ncccc注注2：min問題問題如果給定的線性規(guī)劃問題是要求目標(biāo)函數(shù)達(dá)到最小，如果給定的線性規(guī)劃問題是要求目標(biāo)函數(shù)達(dá)到最小，可以直接用單純形計(jì)算，而不必先化成標(biāo)準(zhǔn)形中要求可以直接用單純形計(jì)算，而不必

50、先化成標(biāo)準(zhǔn)形中要求目標(biāo)函數(shù)的極大值。目標(biāo)函數(shù)的極大值。此時(shí)，要求檢驗(yàn)數(shù)此時(shí)，要求檢驗(yàn)數(shù) 時(shí)，基可行解才是最優(yōu)解；時(shí)，基可行解才是最優(yōu)解；迭代時(shí)，選負(fù)檢驗(yàn)數(shù)最小者作為換入變量。迭代時(shí)，選負(fù)檢驗(yàn)數(shù)最小者作為換入變量。0j注注1：上面的計(jì)算過程也可以用基變換公式來實(shí)現(xiàn)。：上面的計(jì)算過程也可以用基變換公式來實(shí)現(xiàn)。單純形算法特別適合計(jì)算機(jī)實(shí)現(xiàn)。單純形算法特別適合計(jì)算機(jī)實(shí)現(xiàn)。思考題：編程實(shí)現(xiàn)單純形算法。思考題：編程實(shí)現(xiàn)單純形算法。解：建立單純形表如下：解：建立單純形表如下：6 , 2 , 1010834124272323min65324325321532jxxxxxxxxxxxxxxxzj例例2 求解線性

51、規(guī)劃問題：求解線性規(guī)劃問題：020310BXb123456 xxxxxx146xxx10127 1803400014200201310020310310412020310BXb123456 xxxxxx146xxx10127 18034000142002013100203103104120 13 0 2 0 BXb123456 xxxxxx631xxx131015 / 201 / 42001 / 211 / 40005 / 203 / 481 9310 0 2024 10/(5/2) 0 13 0 2 0 BXb123456 xxxxxx631xxx131015 / 201 / 42001 /

52、 211 / 40005 / 203 / 481 9310 0 2024 10/(5/2) 020310BXb654321xxxxxx632xxx11541102100105210310510541010152110512540051最優(yōu)解是最優(yōu)解是 ，最優(yōu)值為，最優(yōu)值為 z=-11. *0, 4, 5, 0, 0,11TX 123123412351236123456max23 3 1523 18. . 3,0zxxxxxxxxxxxstxxxxx x x x x x例例3123456456023100015131100018231010031110010 xxxxxxxxx建立建立單純單純形

53、表形表1234564560231000151311001823101031110010231000 xxxxxxxxx56153625611151 0 033331021 1 044180 0 1333151001 0 0 xxx2161510010040112/31/303102110 40045/34/3118002 0 10 xxx4121330101/401/451001/61/31/2 10015/121/3 1/4200005/61/31/2xxx1235,3,1max20 xxxz解畢解畢5 單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論 單純形法是依據(jù)可行基迭代而設(shè)計(jì)的，即從一個(gè)基可

54、單純形法是依據(jù)可行基迭代而設(shè)計(jì)的，即從一個(gè)基可行解構(gòu)造另一個(gè)使目標(biāo)函數(shù)值更好的基可行解。如何行解構(gòu)造另一個(gè)使目標(biāo)函數(shù)值更好的基可行解。如何尋找第一個(gè)基可行解尋找第一個(gè)基可行解(an initial basic feasible solution)呢？呢？在解決線性規(guī)劃問題時(shí)會(huì)碰到下面一種情況：在解決線性規(guī)劃問題時(shí)會(huì)碰到下面一種情況： 1231421234321842 12,0 xxxxxxx x x x初始基不明顯，或者松弛變量個(gè)數(shù)比約束方程個(gè)數(shù)少的初始基不明顯，或者松弛變量個(gè)數(shù)比約束方程個(gè)數(shù)少的情況，問題又應(yīng)該如何解決？情況，問題又應(yīng)該如何解決？解決方法一：解決方法一：通過初等行變換，變換出

55、一組通過初等行變換，變換出一組m個(gè)個(gè)線性不相關(guān)的向線性不相關(guān)的向量來組成量來組成m階初始基矩陣。階初始基矩陣。不利于計(jì)算機(jī)編程實(shí)現(xiàn)，因?yàn)槿绾未_定不利于計(jì)算機(jī)編程實(shí)現(xiàn)，因?yàn)槿绾未_定“一組一組m個(gè)個(gè)線性不相關(guān)的向量線性不相關(guān)的向量”是很隨機(jī)的問題，手工解決比是很隨機(jī)的問題，手工解決比較方便，在程序上的實(shí)現(xiàn)就很困難。較方便，在程序上的實(shí)現(xiàn)就很困難。解決方法二：解決方法二：兩階段法和大兩階段法和大M法法(the Big M Method)。當(dāng)約束方程的系數(shù)矩陣當(dāng)約束方程的系數(shù)矩陣A不包含一個(gè)同階的單位矩不包含一個(gè)同階的單位矩陣，我們就需要引入若干非負(fù)變量，又稱為人工變陣，我們就需要引入若干非負(fù)變量，又

56、稱為人工變量量(an artificial variable),從而構(gòu)造出一個(gè)新的線性規(guī)從而構(gòu)造出一個(gè)新的線性規(guī)劃問題，使其容易找出一個(gè)初始基可行解。劃問題，使其容易找出一個(gè)初始基可行解。一、初始基的確定：一、初始基的確定： 人工變量法：兩階段法、大人工變量法：兩階段法、大M法法.二、單純形法計(jì)算中的幾個(gè)問題二、單純形法計(jì)算中的幾個(gè)問題三、單純形法小結(jié)三、單純形法小結(jié)兩階段法兩階段法：假定約束方程的系數(shù)矩陣：假定約束方程的系數(shù)矩陣A不包含同階不包含同階的單位矩陣的單位矩陣nnxcxcxcz2211max11 11221121 1222221 12212. .0,0,0nnnnmmmnnmna

57、xa xa xba xa xa xbsta xaxaxbxxx加入人加入人工變量工變量11 112211121 12222221 12201,2,nnnnnnmmmnnn mmja xa xa xxba xa xa xxba xaxaxxbxjnm改變目標(biāo)函數(shù)改變目標(biāo)函數(shù)12min nnn mzxxx初始基初始基目標(biāo)函數(shù)在可行域上有一個(gè)明顯的下界目標(biāo)函數(shù)在可行域上有一個(gè)明顯的下界所以它一定有最優(yōu)解，利用單純形法可以求解。所以它一定有最優(yōu)解，利用單純形法可以求解。 此為第一階段，求解后進(jìn)入此為第一階段，求解后進(jìn)入第二階段第二階段。0z 5.1 初始基的確定：初始基的確定：設(shè)設(shè)00100200,1

58、mnnnxxxxxX表示這個(gè)問題表示這個(gè)問題最后得到的最優(yōu)解?？赡艹霈F(xiàn)如下三種情況：最后得到的最優(yōu)解?？赡艹霈F(xiàn)如下三種情況：在在 中，人工變量中，人工變量 全是非基變量，全是非基變量， 此時(shí)，此時(shí)， 得到原線性規(guī)劃問題的一個(gè)可行解得到原線性規(guī)劃問題的一個(gè)可行解 將該可行解代入第二階段計(jì)算。將該可行解代入第二階段計(jì)算。mnnxx,10z ,002001nxxxX0X在在 中，個(gè)別人工變量中，個(gè)別人工變量 是基變量是基變量,并且并且 的目標(biāo)函數(shù)值的目標(biāo)函數(shù)值 說明原線性規(guī)劃問題沒有可行解。說明原線性規(guī)劃問題沒有可行解。njx0z 0X0X在在 中，個(gè)別人工變量中，個(gè)別人工變量 是基變量，若此時(shí)得是

59、基變量，若此時(shí)得 到原線性規(guī)劃問題的目標(biāo)函數(shù)值到原線性規(guī)劃問題的目標(biāo)函數(shù)值 說明基變量說明基變量 xn+j=0，原線性規(guī)劃問題為原線性規(guī)劃問題為退化問題退化問題。njx0z 0X第二階段，第二階段，以第一階段的結(jié)論作為原線性規(guī)劃問題的初始基可以第一階段的結(jié)論作為原線性規(guī)劃問題的初始基可行解計(jì)算。如果是在單純形表上進(jìn)行的，可以將第行解計(jì)算。如果是在單純形表上進(jìn)行的，可以將第一階段所得的最終表，畫去所有的人工變量所在的一階段所得的最終表，畫去所有的人工變量所在的列，將目標(biāo)行的系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù)，列，將目標(biāo)行的系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù)，來作為求解原問題的初始表即可。來作為求解原問題的初

60、始表即可。兩階段方法適用于所有線性規(guī)劃問題的求解。兩階段方法適用于所有線性規(guī)劃問題的求解。第二階段，第二階段，以第一階段的結(jié)論作為原線性規(guī)劃問題的初始基可以第一階段的結(jié)論作為原線性規(guī)劃問題的初始基可行解計(jì)算。如果是在單純形表上進(jìn)行的，可以將第行解計(jì)算。如果是在單純形表上進(jìn)行的，可以將第一階段所得的最終表，畫去所有的人工變量所在的一階段所得的最終表，畫去所有的人工變量所在的列，將目標(biāo)行的系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù)，列，將目標(biāo)行的系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù)，來作為求解原問題的初始表即可。來作為求解原問題的初始表即可。)5 , 2 , 1(01226215min5321432131jxxxxxx