線性規(guī)劃線性規(guī)劃問題單純形法_第1頁
線性規(guī)劃線性規(guī)劃問題單純形法_第2頁
線性規(guī)劃線性規(guī)劃問題單純形法_第3頁
線性規(guī)劃線性規(guī)劃問題單純形法_第4頁
線性規(guī)劃線性規(guī)劃問題單純形法_第5頁
已閱讀5頁,還剩107頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

線性規(guī)劃線性規(guī)劃問題單純形法第一頁,共一百一十二頁,2022年,8月28日1第一講第二章線性規(guī)劃及圖解法第二頁,共一百一十二頁,2022年,8月28日問題的提出解決有限資源在有競爭的使用方向中如何進行最佳分配。線性規(guī)劃是運籌學的一個重要分支,也是運籌學中應(yīng)用最廣泛的方法之一。自1947年旦茨基(G.B.Dantzig)提出了一般線性規(guī)劃問題求解的方法——單純形法(simplexmethod)之后,線性規(guī)劃已被廣泛應(yīng)用于解決經(jīng)濟管理和工業(yè)生產(chǎn)中遇到的實際問題。調(diào)查表明,在世界500家最大的企業(yè)中,有85%的企業(yè)都曾使用線性規(guī)劃解決經(jīng)營管理中遇到的復(fù)雜問題。線性規(guī)劃的使用為應(yīng)用者節(jié)約了數(shù)以億萬計的資金。線性規(guī)劃LinearProgramming(LP)第三頁,共一百一十二頁,2022年,8月28日本講中我們將討論什么是線性規(guī)劃問題,線性規(guī)劃問題的數(shù)學表示,基本概念和圖解方法。線性規(guī)劃問題是什么樣的一類問題呢?請看案例線性規(guī)劃LinearProgramming(LP)第四頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)曾幾何時長江水,哺育華夏代代人;誰知后代疏珍惜,清清江水黑如泥。案例河流污染治理規(guī)劃問題第五頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)曾幾何時長江水,哺育華夏代代人;誰知后代疏珍惜,清清江水黑如泥。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7案例河流污染治理規(guī)劃問題第六頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)曾幾何時長江水,哺育華夏代代人;誰知后代疏珍惜,清清江水黑如泥。今日認識未為晚,吾輩齊心治環(huán)境;線性規(guī)劃大有用,定讓江水綠如藍。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7案例河流污染治理規(guī)劃問題第七頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)今日認識未為晚,吾輩齊心治環(huán)境;線性規(guī)劃大有用,定讓江水綠如藍。曾幾何時長江水,哺育華夏代代人;誰知后代疏珍惜,清清江水黑如泥。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7案例河流污染治理規(guī)劃問題第八頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)案例河流污染治理規(guī)劃問題背景資料:長江流域某區(qū)域內(nèi)有9化工廠,各廠每月產(chǎn)生的工業(yè)污水量如表-1,流經(jīng)各化工廠的河流流量如表-2,各化工廠治理工業(yè)污水的成本如表-3。上游廠排放的污水流到相鄰下游廠以前,有20%可自然凈化。根據(jù)環(huán)保標準河流中此種工業(yè)污水的含量不應(yīng)超過0.2%。從該區(qū)域整體考慮,各化工廠應(yīng)該分別處理多少工業(yè)污水才能既滿足環(huán)保要求,又使9化工廠治理工業(yè)污水的總費用最少。第九頁,共一百一十二頁,2022年,8月28日背景資料:線性規(guī)劃LinearProgramming(LP)化工廠11.2化工廠42化工廠72化工廠21化工廠51化工廠80.8化工廠33化工廠61化工廠91.5表-1污水產(chǎn)生量單位:萬m3表-2流經(jīng)各化工廠的河流流量單位:萬m3表-3治理工業(yè)污水的成本單位:百萬元/萬m3化工廠1500化工廠41200化工廠71200化工廠2300化工廠5600化工廠8200化工廠31800化工廠6400化工廠9700化工廠13化工廠44化工廠71化工廠25化工廠55化工廠82化工廠32化工廠66化工廠93第十頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)194582637問題分析:區(qū)域污染治理的決策——各個化工廠應(yīng)處理的工業(yè)污水量(或應(yīng)排放的工業(yè)污水量)。區(qū)域污染治理的約束——即滿足環(huán)保要求排放工業(yè)污水(區(qū)域內(nèi)河流中任何點檢測都應(yīng)符合環(huán)保標準)。區(qū)域污染治理的目標——總治理成本最少。第十一頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)194582637模型描述:設(shè)第i個化工廠應(yīng)處理的工業(yè)污水量為Xi萬m3,則根據(jù)問題描述的情況以化工廠1、2、…、9加以分析則可得如下近似關(guān)系式對化工廠2應(yīng)有(1-X2)/300≦0.2%對化工廠8應(yīng)有(0.8-X8)/200≦0.2%對化工廠1應(yīng)有{(1.2-X1)+0.8(1-X2)+(0.8-X8)}/500≦0.2%第十二頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)194582637對化工廠9應(yīng)有——(1.5-X9)/700≦0.2%對化工廠7應(yīng)有——

(2-X7)+0.8(1.5-X9)/1200≦0.2%……此外顯然還應(yīng)有Xi≧0(i=1,2,3…8,9)綜上所述決策者所需考慮的區(qū)域內(nèi)各個化工廠應(yīng)處理的工業(yè)污水量Xi應(yīng)滿足上述所有不等式方程。我們將這些不等式方程構(gòu)成的方程組稱為污水治理的約束條件。第十三頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)194582637另一方面污水治理的總成本可表示為Z(單位:百萬元)Z=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9而決策者的目標是:確定滿足約束條件的Xi使得Z取得最小值。將上述分析歸納后即可得如下數(shù)學符合模型:第十四頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)河流污染治理規(guī)劃問題數(shù)學模型(整理之后)194582637MinZ=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9X2≧0.4X8≧1.6X1+0.8X2+0.8X8≧4.4X9≧0.1X7+0.8X9≧0.8X4+0.8X7+0.64X9≧2.16X6≧0.2X5+0.8X6≧0.6X3+0.8X4+0.8X5+0.64X6+0.64X7+5.12X9≧9.4Xi≧0(i=1,2,3,4,5,6,7,8,9)s.t.第十五頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)線性規(guī)劃模型——

LinearProgrammingModel或LinearOptimizationModel用線性規(guī)劃方法解決實際經(jīng)濟與管理問題的第一步是分析建立能夠完整描述和反映實際問題的線性規(guī)劃模型。第十六頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)通常建立LP模型有以下幾個基本步驟:確定決策變量:決策變量是模型要確定的未知變量,也是模型最重要的參數(shù),是決策者解決實際問題的控制變量。確定目標函數(shù):目標函數(shù)決定線性規(guī)劃問題的優(yōu)化方向,是模型的重要組成部分。實際問題的目標可表示為決策變量的一個線性函數(shù),并根據(jù)目標函數(shù)的實質(zhì)確定優(yōu)化方向,一般可為最大化(max)或最小化(min)。第十七頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)通常建立LP模型有以下幾個步驟:確定約束方程:一個正確的線性規(guī)劃模型應(yīng)能通過約束方程來描述和反映一系列客觀條件或環(huán)境的限制,這些限制通過一系列線性等式或不等式方程組來描述。變量取值限制:一般情況下,決策變量取正值(非負值)。因此,模型中應(yīng)有變量的非負約束即Xj≥0,但要注意也存在例外的情形。第十八頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)線性規(guī)劃的一般形式:max(或min)z=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn(≤=≥)b1a21x1+a22x2+…+a2nxn

(≤=≥)b2s.t.………………am1x1+am2x2+…+amnxn(≤=≥)bm

xj≥0(j=1,2…n)第十九頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)線性規(guī)劃問題的標準形式1、目標函數(shù)極大化——“max”2、等式約束條件——“=”且右端常數(shù)bi非負3、變量非負——“xj≥0”maxz=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2s.t.……………am1x1+am2x2+…+amnxn=bmxj≥0(j=1,2…n)第二十頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)化標準形式的一般步驟目標函數(shù)極小化“極大化”約束條件的右端項bi≤0“bi≥0”約束條件為不等式≤或≥“=”取值無約束(自由)變量“非負變量”取值非正變量“非負變量”線性規(guī)劃問題的標準形式的作用——為單純形法求解作準備!第二十一頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)線性規(guī)劃問題的求解:(圖解)如何求解一般的線性規(guī)劃呢?下面我們分析一下簡單的情況——只有兩個決策變量的線性規(guī)劃問題,這時可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點。第二十二頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)基本概念例1(page11)maxz=2x1+x25x2

≤15s.t.6x1+2x2

≤24x1+x2

≤5x1,x2

≥0第二十三頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)基本概念maxz=2x1+x25x2≤15s.t.6x1+2x2≤24x1+x2≤5x1,x2≥0唯一最優(yōu)解X=(9/2,3/2)第二十四頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)基本概念例maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1,X2≥0第二十五頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)基本概念maxZ=2X1+X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)4=2X1+X2

20=2X1+X2

17.2=2X1+X2

11=2X1+X2

Lo:0=2X1+X2

(7.6,2)DmaxZminZ此點是唯一最優(yōu)解,且最優(yōu)目標函數(shù)值maxZ=17.2可行域第二十六頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)基本概念maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)(7.6,2)DL0:0=3X1+5.7X2

maxZminZ(3.8,4)34.2=3X1+5.7X2

綠色線段上的所有點都是最優(yōu)解這種情形為有無窮多最優(yōu)解,但是最優(yōu)目標函數(shù)值maxZ=34.2是唯一的。可行域第二十七頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)基本概念minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)DL0:0=5X1+4X2

maxZminZ8=5X1+4X2

43=5X1+4X2

(0,2)可行域此點是唯一最優(yōu)解第二十八頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)基本概念minZ=5X1+4X2x1x2oD可行域第二十九頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)基本概念maxZ=5X1+4X2x1x2oD可行域maxZminZ最優(yōu)解目標值Z趨于無窮第三十頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)基本概念maxZ=5X1+4X2x1x2o可行解域為空第三十一頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)基本概念圖解法的啟示線性規(guī)劃問題解的可能情況a.唯一最優(yōu)解b.無窮多最優(yōu)解c.無解(沒有有界最優(yōu)解,無可行解)若線性規(guī)劃問題的可行域非空,則可行域是一個凸集;若線性規(guī)劃問題的最優(yōu)解存在,則一定可以在可行域的凸集的某個頂點上達到。第三十二頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法

單純形方法是于1947年首先發(fā)明的。近50年來,一直是求解線性規(guī)劃的最有效的方法之一,被廣泛應(yīng)用于各種線性規(guī)劃問題的求解。本節(jié)討論單純形法的基本概念、原理及算法。第三十三頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法給定線性規(guī)劃問題(標準形式)maxz=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn

=b1a21x1+a22x2+…+a2nxn

=b2s.t.……………am1x1+am2x2+…+amnxn

=bmxj≥0(j=1,2…n)第三十四頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法一、線性規(guī)劃問題的解的概念

可行解最優(yōu)解基基解(基本解)基可行解可行基第三十五頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法二、凸集及其頂點凸集頂點(極點)凸集凹集第三十六頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)12345678基解(可行)基解(不可行)第三十七頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法三、線性規(guī)劃基本定理基本定理1

線性規(guī)劃所有可行解組成的集合S={X|AX=b,X≥0}是凸集。基本定理2

X是線性規(guī)劃問題的基本可行解的充要條件為是X是凸集S={X|AX=b,X≥0}的極點。基本定理3

給定線性規(guī)劃問題,A是秩為m的mn矩陣,

(i)若線性規(guī)劃問題存在可行解,則必存在基本可行解(ii)若線性規(guī)劃問題存在有界最優(yōu)解,則必存在有界最優(yōu)基本可行解。第三十八頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法單純形法迭代原理及其思路單純形法的初步討論例1.8求解LP問題

化為標準型MaxZ=50X1+30X2s.t.4X1+3X2≤

1202X1+X2≤50X1,X2≥0MaxZ=50X1+30X2s.t.4X1+3X2+X3

=

1202X1+X2+X4

=50X1,X2,X3,X4

≥0(1.18)第三十九頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法此線性規(guī)劃問題轉(zhuǎn)化為了一個含有四個變量的標準形線性規(guī)劃問題,X3,X4為松弛變量。為求解上面的LP問題,我們要考慮滿足約束條件s.t.并使Z取得Max的X1,X2,X3,X4的值,由此分析如下第四十頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法確定初始基可行解:通過觀察可以發(fā)現(xiàn),松弛變量X3和X4對應(yīng)的等式約束條件中的系數(shù)矩陣為單位矩陣可以作為初始可行基矩陣。因此取X3,X4為基變量;X1,X2為非基變量。則(1.18)可變?yōu)椋?/p>

Max

Z

=50X1+30X2s.t.X3=120-4X1-3X2X4=50-2X1-X2(1.19)X1,X2,X3,X4≥0第四十一頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法典式(1.19)或(1.18)稱為關(guān)于基的典式——1、等式約束條件中顯含基可行解2、目標函數(shù)中不含基變量MaxZ=50X1+30X2s.t.4X1+3X2+X3

=

1202X1+X2+X4

=50(1.18)X1,X2,X3,X4≥0MaxZ

=50X1+30X2s.t.X3

=120-4X1-3X2

X4=50-2X1-X2(1.19)X1,X2,X3,X4≥0第四十二頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法在典式(1.19)中令:X1=X2

=0,我們得到一個基本可行解

X1=(X1,X2,X3,X4)T=(0,0,120,50)T

,其對應(yīng)的目標函數(shù)值Z1=50X1+30X2=0第四十三頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法最優(yōu)性檢驗:基本可行解X1是最優(yōu)解嗎?顯然不是。應(yīng)尋找更好的解。從問題的數(shù)學角度分析,在典式(1.19)的目標函數(shù)中,非基變量X1,X2前的系數(shù)都為正,而此時的X1,X2均取零值,表明只要增加其值,則目標函數(shù)值有增加的可能。因此,將目標函數(shù)中系數(shù)為正的某一非基變量與某一基變量地位對換。第四十四頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法換基迭代:進行換基就是要從非基變量中選一個變量入基,再從基變量中選一個變量出基。并且換基后仍需滿足:新的解仍是基本可行解;目標函數(shù)值將得到改善。第四十五頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法選擇入基變量:

由于在目標函數(shù)Z1

=50X1+30X2中X1,X2的系數(shù)都為正,哪一個入基都可使目標函數(shù)值得到改善。對于求目標函數(shù)極大化的問題,我們希望目標值增加得越快越好,因此系數(shù)最大的X1入基。選擇出基變量:

X1入基后,其值從零增加并由于約束條件的原因會引起其他變量的變化。由典式(1.19)以及變量必須取正值(可行)的條件,我們可以得到下列不等式關(guān)系:X3=120-4X1-3X2≥0X4=50-2X1-X2≥0第四十六頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法

因為迭代后X2仍為非基變量(仍會令其取值為零),則上式可簡化為:120-4X1≥0,且50-2X1≥0,由此可以看出,雖然我們希望X1入基后取正值,取值越大目標值增加越大,但是X1又得受到以上約束(保證其可行)。顯然,當取X1=min(120/4,50/2)=25時,才能使上述不等式成立,且此時恰使基變量X4變?yōu)榱?,這正好滿足非基變量必須取值零的條件,所以可令X4出基,這樣,新的基變量變?yōu)閄3,X1,而X2,X4成了非基變量,則第四十七頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法約束方程變?yōu)椋?X1+X3=120-3X22X1=50-X2-X4化簡后得:新的典式方程X3=20-X2+2X4X1=25-0.5X2-0.5X4第四十八頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法代入目標函數(shù)可得:Z2

=1250+5X2-25X4

令非基變量X2=X4=0,即可得一個新的基本可行解X2=(25,0,20,0)T,其對應(yīng)的目標函數(shù)值Z2

=1250,并完成了第一次迭代。由于目標函數(shù)Z2=1250+5X2-25X4中X2的系數(shù)仍為正,該解X2仍不是最優(yōu)解。重復(fù)上述迭代過程得到:X2入基,X3出基,則新的典式方程變?yōu)椋篨1=15+0.5X3

-1.5X4X2=20-X3+2X4

Z3

=1350-5X3-15X4第四十九頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法第三個基本可行解X3

=(15,20,0,0)T,其對應(yīng)的目標函數(shù)值Z3

=1350。此時松弛變量都是非基變量(取值為零),這表明資源已用盡;并且目標函數(shù)值Z3

=1350-5X3-15X4中非基變量X3,X4的系數(shù)全為負值,說明目標函數(shù)已無法進一步改善,因此該解已是最優(yōu)解。第五十頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法小結(jié):

單純形法是這樣一種迭代算法——如下圖…當Zk

中非基變量的系數(shù)的系數(shù)全為負值時,這時的基本可行解Xk

即是線性規(guī)劃問題的最優(yōu)解,迭代結(jié)束。X1Z1保持單調(diào)增保持可行性保持可行性保持可行性保持可行性保持單調(diào)增保持單調(diào)增保持單調(diào)增X2X3...XkZ2Z3...Zk當Zk

中非基變量的系數(shù)的系數(shù)全為負值時,這時的基本可行解Xk

即是線性規(guī)劃問題的最優(yōu)解,迭代結(jié)束。第五十一頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形表對于給定的線性規(guī)劃問題:maxZ=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2s.t.………am1x1+am2x2+…+amnxn≤bmxj≥0(j=1,2…n)對此問題添加m個松弛變量后,可得下面線性規(guī)劃問題并且是典式的形式。第五十二頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形表線性規(guī)劃的典式maxZ=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+

xn+2=b2s.t.…am1x1+am2x2+…+amnxn+

xn+m=bmxj≥0(j=1,2…n,n+1,n+2,…n+m)第五十三頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形表:將上面典式中各變量及系數(shù)填寫在一張表格中就形成下面的單純形表cj

c1c2…cncn+1cn+2…cn+mCB基解

x1x2…xnxn+1xn+2…xn+m0000xn+1xn+2…xn+m

b1

b2…

bma11a12…a1n1a21a22…a2n1……………am1am2…amn112…mj=cj–zj

c1c2…cn00…0j=cj–zj

1

2…

nn+1

n+2…n+m第五十四頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形表:

上面的單純形表還可以表示成矩陣的形式基解X

XSXSbAIj

C

0基解XB

XN

XSXSbBNIj

CB

CN

0或第五十五頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法由單純形表進行迭代步驟:選擇Xj入基:當j行中

j=max{

i∣

i0}選擇Xi出基:當i

=min{bi/aij∣aij0}換基迭代:當確定了入基變量Xj、出基變量Xi后,以aij作為主元對單純形表進行取主運算,取主運算——即采用初等行變換將主元aij所在列,除將aii變換為1而外,該列中的其余元素都變換為0。注意這種變換只能采用初等行變換!第五十六頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法最優(yōu)解檢驗:當?shù)M行至某一步時,j行中所有檢驗數(shù)均小于等于零,則迭代結(jié)束。表中當前所指基本可行解即為最優(yōu)解。當?shù)M行至某一步時,j行中所有檢驗數(shù)均小于等于零,且此時至少有一個非基變量所對應(yīng)的檢驗數(shù)k等于零,則原線性規(guī)劃問題有無窮多個最優(yōu)解。當?shù)M行至某一步時,j行中至少有一個檢驗數(shù)k大于零,且該檢驗數(shù)對應(yīng)的列中a1k,a2k,…amk,均小于等于零,則原線性規(guī)劃問題最優(yōu)解無界(maxZ→+∞)。第五十七頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形方法的矩陣描述:設(shè)線性規(guī)劃問題maxZ=CXmaxZ=CX+0XS

s.t.AX≤bs.t.AX+IXS=b(I式)

X≥0X,XS≥0其中b≥0,I是mm單位矩陣。對上面(I式)經(jīng)過迭代,并設(shè)最終的最優(yōu)基矩陣為B(不妨設(shè)B

為A的首m列,則將(I式)改寫后有第五十八頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形方法的矩陣描述:maxZ=CBXB+CNXN+0XS

s.t.BXB+NXN+IXS=bXB,XN,XS≥0

maxZ=CBB-1+(CN-CBB-1)XN-

CBB-1XS

s.t.XB+B-1NXN+B-1XS=B-1bXB,XN,XS≥0

B式中最優(yōu)目標函數(shù)值Z*=CBB

-1,檢驗數(shù)CN-CBB

-1≤0

,-

CBB

-1≤0單純形方法迭代(I式)(B式)第五十九頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形方法的矩陣描述:基解XB

XN

XSXSb

BNIj

CB

CN

0基解XB

XN

XSXBB-1b

IB-1NB-1j

0

CN-CBB

–1N-

CBB

-1對應(yīng)I式的單純形表——

I

表對應(yīng)B

式的單純形表——B

表迭代第六十頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形表計算步驟舉例給定線性規(guī)劃問題maxz=50X1+30X2s.t.4X1+3X2≤

1202X1+X2

≤50X1,X2

≥0maxz=50X1+30X2s.t.4X1+3X2+X3=

1202X1+X2+X4=50X1,X2,X3,X4

≥0第六十一頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形表計算步驟舉例maxz=50X1+30X2s.t.4X1+3X2+X3=

1202X1+X2+X4=50X1,X2,X3,X4≥0基XB解B-1bX1X2X3X4X31204310X4502101檢驗數(shù)j

5030002120/450/2X111/201/2250201-2050-2520/125×211X2150-1/23/210-5-15第六十二頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法的進一步討論人工變量法:當一般線性規(guī)劃問題標準化之后,我們或可得到一個顯然的基本可行解(如松弛變量作為基變量的一個初始基本可行解),這樣我們就可以馬上進入單純形表的運算步驟。然而,并非所有問題標準化之后我們都可得到一個顯然的初始基本可行解,這時就需要我們首先確定出一個基本可行解作為初始基本可行解。通常采用的是人工變量法來確定這樣的初始基本可行解。這種情況下一般有兩種方法:

大M法(罰因子法)兩階段法第六十三頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法的進一步討論1、大M法(罰因子法)maxz=-3X1+X3

x1+x2+x3

≤4-2x1+x2–x3

≥13x2+x3=9x1,x2,x3

≥0LPMmaxz=-3x1+x3+0x4+0x5–Mx6–Mx7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1,x2,x3,x4,x5,x6,x7

≥0第六十四頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)1、大M法LPMmaxz=-3x1+x3+0x4+0x5–Mx6–Mx7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1,x2,x3,x4,x5,x6,x7≥0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗數(shù)j-30100-M-M第六十五頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)1、大M法基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗數(shù)j-3-2MM1-M0-M0-M基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗數(shù)j-3-2M4M10-M00第六十六頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)1、大M法基XB解B-1bX1X2X3X4X5X6X7X4411110004X61-21-10-1101X7903100013檢驗數(shù)j-3-2M4M10-M00基XB解B-1bX1X2X3X4X5X6X7X4330211-10X21-21-10-110X7660403-31檢驗數(shù)j-3+6M01+4M03M-4M0第六十七頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)1、大M法基XB解B-1bX1X2X3X4X5X6X7X4330211-101X21-21-10-110X7660403-311檢驗數(shù)j-3+6M01+4M03M-4M0基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6檢驗數(shù)j00301.5-1.5-M0.5-M第六十八頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)1、大M法基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/39X11102/301/2-1/21/63/2檢驗數(shù)j00301.5-1.5-M0.5-M基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X25/2-1/2100-1/41/41/4X33/23/20103/4-3/41/4檢驗數(shù)j-9/2000-3/43/4-M-1/4-M第六十九頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)采用大M法求解線性規(guī)劃問題時可能出現(xiàn)的幾種情況:當采用單純形法求解LPM得到最優(yōu)解時,基變量不含任何人工變量,則所得到的最優(yōu)解就是原問題的最優(yōu)解;當采用單純形法求解LPM得到最優(yōu)解時,基變量至少含有一個人工變量且非零,則原問題無可行解;當采用單純形法求解LPM得到最優(yōu)解時,基變量至少含有一個人工變量且人工變量都為零,則通過變換得到原問題最優(yōu)解;第七十頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)2、兩階段法maxz=-3X1+X3

x1+x2+x3≤4-2x1+x2–x3≥13x2+x3=9x1,x2,x3≥0I階段問題maxz=–x6–x7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1,x2,x3,x4,x5,x6,x7

≥0第七十一頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)2、兩階段法I階段問題maxz=–x6–x7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1,x2,x3,x4,x5,x6,x7≥0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗數(shù)j00000-1-1第七十二頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)2、兩階段法——第I階段基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗數(shù)j00000-1-1基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗數(shù)j-2400-100第七十三頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)2、兩階段法——第I階段基XB解B-1bX1X2X3X4X5X6X7X4411110004X61-21-10-1101X7903100013檢驗數(shù)j-2400-100基XB解B-1bX1X2X3X4X5X6X7X4330211-10X21-21-10-110X7660403-31檢驗數(shù)j60403-40第七十四頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)2、兩階段法——第I階段基XB解B-1bX1X2X3X4X5X6X7X4330211-101X21-21-10-110X7660403-311檢驗數(shù)j60403-40基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6檢驗數(shù)j00000-1-1第七十五頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)2、兩階段法——第II階段基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6檢驗數(shù)j00000-1-1基XB解B-1bX1X2X3X4X5X400001-1/2X23011/300X11102/301/2檢驗數(shù)j00303/2-30100第七十六頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)2、兩階段法——第II階段基XB解B-1bX1X2X3X4X5X400001-1/2X23011/3009X11102/301/23/2檢驗數(shù)j00303/2基XB解B-1bX1X2X3X4X5X400001-1/2X25/2-1/2100-1/4X33/23/20103/4檢驗數(shù)j-9/2000-3/4第七十七頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)單純形法中的幾個問題目標函數(shù)極小化時,解的最優(yōu)判別:

j≥0退化:一個或幾個基變量等于零,一個簡單易行的避免退化的方法是1974年由勃蘭德(Bland)提出的Bkand法則。無可行解的判別:在采用人工變量求解線性規(guī)劃問題得到最優(yōu)解時,如果基變量中仍含有非零人工變量,則原問題無可行解。第七十八頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)數(shù)據(jù)包絡(luò)分析DEA(dateenvelopmentanalysis)引言一種基于線性規(guī)劃的用于評價同類型組織(或項目)工作績效相對有效性的特殊工具手段。這類組織例如學校、醫(yī)院、銀行的分支機構(gòu)、超市的各個營業(yè)部等,各自具有相同的投入相同的產(chǎn)出。衡量這類組織之間的績效高低,通常采用投入產(chǎn)出比這個指標,當各自的投入產(chǎn)出均可折算成同一單位計量時,容易計算出各自的投入產(chǎn)出比并按其大小進行績效排序。但當被衡量的同類型組織有多項投入和多項產(chǎn)出,且不能折算成統(tǒng)一單位時,就無法算出投入產(chǎn)出比的數(shù)值,因而,需采用一種全新的方法進行績效比較。這種方法就是二十世紀七十年代末產(chǎn)生的數(shù)據(jù)包絡(luò)分析DEA。第七十九頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)數(shù)據(jù)包絡(luò)分析DEA(dateenvelopmentanalysis)引言1978年,著名運籌學家、美國德克薩斯大學教授A.Charnes及W.W.Cooperh和E.Rhodes發(fā)表了一篇重要論文:“Measuringtheefficiencyofdecisionmakingunits”(決策單元的有效性度量),刊登在權(quán)威的“歐洲運籌學雜志”上。正式提出了運籌學的一個新領(lǐng)域:數(shù)據(jù)包絡(luò)分析。其模型簡稱C2R模型。第八十頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)相對有效性評價問題例子

例1:碩士點教育質(zhì)量評價某系統(tǒng)工程研究所對我國金屬熱處理專業(yè)的26個碩士點的教育質(zhì)量,進行了有效性評價。評價采用的指標體系為:輸入:導(dǎo)師人數(shù);實驗設(shè)備;圖書資料;學生入學情況。輸出:科研成果;論文篇數(shù);學生畢業(yè)時的情況。使用DEA進行評價,結(jié)果基本合理。第八十一頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)相對有效性評價問題例子

例2:行風(行業(yè)作風)建設(shè)有效性評價本項目研究人員選定江蘇省S市交通客運系統(tǒng)作為對象,包括7家交通客運汽車公司。評價采用的指標基礎(chǔ)依據(jù)為:1、國際公交組織頒布的“十項基本考核指標”2、國內(nèi)頒布的公交運營服務(wù)的“八項考核指標”。在此基礎(chǔ)上,根據(jù)該系統(tǒng)實際情況,最終選定了輸入指標4項,輸出指標4項。分別是:第八十二頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)相對有效性評價問題例子輸入指標:1、年末職工總熟(單位:人);2、單位成本(單位:元/千人公里);3、燃料單位消耗(單位:升/千人公里);4、行車責任事故率(單位:次/千人公里)。輸出指標:1、勞動生產(chǎn)率(單位:元/人);2、行車準點率(%);3、群眾滿意率(按問卷調(diào)查)(%)4、車輛服務(wù)合格率(包括:服務(wù)態(tài)度、服務(wù)措施、車輛設(shè)施等)(%)第八十三頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)相對有效性評價問題例子

收集到所需數(shù)據(jù)后,使用DEA方法綜合評價,結(jié)果為:3家公司為行風建設(shè)有效;4家公司在行風建設(shè)上存在不同程度(以量化形式給出)的缺點與不足。第八十四頁,共一百一十二頁,2022年,8月28日線性規(guī)劃LinearProgramming(LP)相對有效性評價問題舉例

4所小學S1,S2,S3,S4,在校學生分別為1200,1000,1600,1400人,按800名標準學生的規(guī)模折算各個學校的教職工人數(shù)和建筑面積的投入,如下表:

學校投入S1S2S3S4教職工人數(shù)建筑面積/m2251800401500351700202500請您評價:就培養(yǎng)800名學生而言,那些學校

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論