工程優(yōu)化3文檔ppt第1頁(yè)，共53頁(yè)。

兩階段法的第一階段是用單純形法消去人工變量(可以的話)，即把人工變量都變換成非基變量，求出原來(lái)問(wèn)題的一個(gè)基本可行解。消去人工變量的其中一種方法其中e是分量全為1的m維列向量，兩階段法的基本思想是解下列一個(gè)問(wèn)題：第2頁(yè)，共53頁(yè)。

兩階段法的基本思想設(shè)(6)的最優(yōu)基本可行解是事實(shí)上，如果(LP)存在可行解，則是(6)的可行解，對(duì)應(yīng)(6)的目標(biāo)函數(shù)值是矛盾！是(6)的最優(yōu)解這時(shí)，m個(gè)基變量都是原來(lái)的變量，是(6)的基本可行解，(i)若，則標(biāo)準(zhǔn)的線性規(guī)劃(LP)沒(méi)有可行解；(ii)若，且xa

的分量都是非基變量。是(LP)的一個(gè)基本可行解。第3頁(yè)，共53頁(yè)。

兩階段法的基本思想設(shè)(6)的最優(yōu)基本可行解是此時(shí)的最優(yōu)值是0.這時(shí)，可用主元消去法，把原來(lái)變量中的非基變量引進(jìn)基，替換出基變量中的人工變量，此時(shí)的最優(yōu)值一直都保持是0，從而就

得到(LP)的一個(gè)基本可行解。第一階段結(jié)束，得到原來(lái)線性規(guī)劃的一個(gè)基本可行解。(iii)若，且xa

的某些分量是基變量?？苫癁榈?ii)種情況，第4頁(yè)，共53頁(yè)。兩階段法的第二階段，就是從得到的基本可行解出發(fā)，用單純形法求問(wèn)題(LP)的最優(yōu)解。第5頁(yè)，共53頁(yè)。例1.利用兩階段法求解如下的線性規(guī)劃問(wèn)題。

min-2x1-x2

s.t.x1

+x2

≥

2x1-x2

≥1x1≤3x1,x2≥0min-2x1-x2

s.t.x1

+x2

-

x3

=

2x1-x2

-

x4

=1x1+x5=3xj≥0,j=1,2,…,5解：1.首先把問(wèn)題化成標(biāo)準(zhǔn)形式：系數(shù)矩陣中不包含單位矩陣第6頁(yè)，共53頁(yè)。minx6+x7

s.t.x1

+x2

-

x3

+x6

=

2x1-x2

-

x4

+x7

=1x1+x5=3xj≥0,j=1,2,……,72.引進(jìn)人工變量x6

,x7構(gòu)造單位矩陣，求解下面的問(wèn)題3.x6

,x7,x

5對(duì)應(yīng)的是單位矩陣，可選擇作為基變量，建立單純形表，利用主元消去法，進(jìn)行迭代。min-2x1-x2

s.t.x1

+x2

-

x3

=

2x1-x2

-

x4

=1x1+x5=3xj≥0,j=1,2,…,5第7頁(yè)，共53頁(yè)。xBx1x2x3x4x5x6

x7

11-100101-10-10011000100x6x7x5213

20-1-100002-1101-11-10-1001010110-1x6x1x5112

02-1100-2cB1102131/2--2100x2x1x501-1/21/201/2-1/210-1/2-1/201/21/2001/21/21-1/2-1/21/23/23/2

00000-1-1000c

000001

1

minx6+x7

s.t.x1

+x2

-

x3

+x6

=

2x1-x2

-

x4

+x7

=1x1+x5=3xj≥0,j=1,2,……,7第8頁(yè)，共53頁(yè)。x2x1x501-1/21/201/2-1/210-1/2-1/201/21/2001/21/21-1/2-1/21/23/23/2

00000-1-1000xBx1x2x3x4x5x6

x7

cBc

000001

1

4.所有判別數(shù)zj-cj≤0

，因此達(dá)到最優(yōu)解。

從表中看到：在一階段問(wèn)題的最優(yōu)解中，人工變量x6,x7都是非基變量。所以我們得到了原線性規(guī)劃的基本可行解:第9頁(yè)，共53頁(yè)。xBx1x2x3x4x5

cB-1-2001-1/21/2010-1/2-1/20001/2-1/21x2x1x51/23/23/2min-2x1-x2

s.t.x1

+x2

-

x3

=

2x1-x2

-

x4

=1x1+x5=3xj≥0,j=1,2,…,5

003/21/20c

-2-1000

5.第二階段，修改最后的單純形表。x2x1x501-1/21/201/2-1/210-1/2-1/201/21/2001/21/21-1/2-1/21/23/23/2

00000-1-1000xBx1x2x3x4x5

x6

x7

cBc

000001

1

修改檢驗(yàn)數(shù)和目標(biāo)函數(shù)，去掉人工變量對(duì)應(yīng)的列，其他不變。第10頁(yè)，共53頁(yè)。xBx1x2x3x4x5

x2x1x3233

000-1-3cB-1-20----3-1-2001-1/21/2010-1/2-1/20001/2-1/21x2x1x51/23/23/2

003/21/2001001100-11001-12c

-2-1000

6.這時(shí)，檢驗(yàn)數(shù)全部小于等于0，得到最優(yōu)解：

x=(3,2,3,0,0)T目標(biāo)函數(shù)的最小值為：f=-2*3-1*2=-8第11頁(yè)，共53頁(yè)。例2.利用兩階段法求解如下的線性規(guī)劃問(wèn)題。

minf=x1-x2s.t.-x1+2x2

+x3

≤

2-4x1+4x2-x3

=4x1

-x3=0

x1,x2,x3

≥0解：1.引入松弛變量x4，把上述問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式minf=x1-x2s.t.-x1+2x2

+x3

+x4

=

2-4x1+4x2

-x3

=4x1

-x3=0

x1,x2,x3,x4≥0系數(shù)矩陣中不包含單位矩陣第12頁(yè)，共53頁(yè)。minf=x5+x6s.t.-x1+2x2

+x3

+x4

=

2-4x1

+4x2

-x3

+x5=4x1

-x3+x6

=0

x1,x2,x3,x4,x5,x6

≥03.x4

，x5，x

6對(duì)應(yīng)的是單位矩陣，可選擇作為基變量，建立單純形表，利用主元消去法，進(jìn)行迭代。2.引進(jìn)人工變量x5

,x6構(gòu)造單位矩陣，用單純形法求解下面的問(wèn)題minf=x1-x2s.t.-x1+2x2

+x3

+x4

=

2-4x1+4x2

-x3

=4x1

-x3=0

x1,x2,x3,x4≥0第13頁(yè)，共53頁(yè)。xBx1x2x3x4

x5

x6

x4x5x6240

-34-2000x2x5x6100cB01111--011-121100-44-101010-1001-1/21-1/21/200-20-3-21010-1001

-10-4-200minf=x5+x6s.t.-x1+2x2

+x3

+x4

=2-4x1

+4x2

-x3

+x5=4x1

-x3+x6=0

x1,x2,x3,x4,x5,x6

≥0c

0

000114.所有判別數(shù)zj-cj≤0

，達(dá)到最優(yōu)解。在一階段問(wèn)題的最優(yōu)解中，人工變量x5，x6

是基變量并且都取0。用原來(lái)的變量（非人工變量）把人工變量從基變量中換出去。第14頁(yè)，共53頁(yè)。xBx1x2x3x4

x5

x6

x2x5x6100cB011-1/21-1/21/200-20-3-21010-1001

-10-4-200c

0

00011用原來(lái)變量(x1,x2,x3

,x4)中的非基變量x1，x3

和x4將人工變量x5,x6

從基變量中換掉。此時(shí)，判別數(shù)、價(jià)格系數(shù)和都可略去。xBx1x2x3x4x5x6

x2x5x11000101/201/200-5-21210-1001主元消去期間不會(huì)改變最優(yōu)值0，最優(yōu)解之間的變換。第15頁(yè)，共53頁(yè)。用原來(lái)變量(x1,x2,x3

,x4)中的非基變量x1，x3

和x4將人工變量x5,x6

從基變量中換掉。xBx1x2x3x4x5

x6

x2x5x11000101/201/200-5-21210-1001主元消去xBx1x2x3

x4x5

x6

x2x3x11000101/201/20012/5-1/5-2/51002/5-1/53/55.基變量均為原來(lái)的變量，得到原問(wèn)題的一個(gè)基本可行解第16頁(yè)，共53頁(yè)。6.第二階段，修改最后的單純形表。加上檢驗(yàn)數(shù)行，按照定義計(jì)算檢驗(yàn)數(shù)和目標(biāo)函數(shù)值。去掉人工變量對(duì)應(yīng)的列。其他不變。xBx1x2x3

x4

x5x6

x2x3x11000101/201/20012/5-1/5-2/51002/5-1/53/5xBx1x2x3x4x2x3x11000101/20012/51002/5cBcminf=x1-x2s.t.-x1+2x2+x3

≤2-4x1+4x2-x3=4x1-x3=0

x1,x2,x3

≥0

1-100-101000-1/10

7.這時(shí)，檢驗(yàn)數(shù)全部小于等于0，得到最優(yōu)解：

x=(0,1,0,0)T最優(yōu)值為:f=0*1-1*1=-1第17頁(yè)，共53頁(yè)。大M法標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題:A=(aij)m

n,b≥0,

秩(A)=m.如果A中不包含m階單位矩陣，我們就不能明顯得到線性規(guī)劃的一個(gè)基本可行解此時(shí)除了可以采用兩階段法之外，還可以利用大M法求解線性規(guī)劃。第18頁(yè)，共53頁(yè)。大M法的基本思想在約束中添加人工變量，M>0,e為全1的m維列向量。(7)是可行的,基本可行解由于大M是充分大的正數(shù)，在極小化目標(biāo)函數(shù)的過(guò)程中，就會(huì)迫使人工變量離基。同時(shí)修改目標(biāo)函數(shù)，加上懲罰項(xiàng)通過(guò)求解(7)而獲得(LP)的最優(yōu)解第19頁(yè)，共53頁(yè)。用單純形法求解(7)，如果(7)存在有限最優(yōu)解，設(shè)為(ii)當(dāng)時(shí)，問(wèn)題(LP)無(wú)可行解。(i)當(dāng)時(shí),x*是問(wèn)題(LP)的最優(yōu)解。事實(shí)上，如果(LP)存在可行解，則是(7)的可行解，對(duì)應(yīng)(7)的目標(biāo)函數(shù)值是M是充分大的正數(shù)是(7)的最優(yōu)解矛盾！第20頁(yè)，共53頁(yè)。在單純形表中如果(7)不存在有限最優(yōu)解(i)當(dāng)時(shí)，問(wèn)題(LP)無(wú)界;(ii)當(dāng)時(shí)，即，問(wèn)題(LP)無(wú)可行解.第21頁(yè)，共53頁(yè)。例3.利用大M法求解如下的線性規(guī)劃問(wèn)題。

minx1+x2

-3x3

s.t.x1

-2x2

+x3

≤112x1+x2

-4x3

≥3x1-2x3=1x1,x2

,x3

≥0解：1.將問(wèn)題化成標(biāo)準(zhǔn)形式，引進(jìn)松弛變量x4

,剩余變量x5minx1+x2-3x3

s.t.x1

-2x2

+x3

+

x4

=11

2x1+x2

-4x3

-x5

=3x1-2x3

=1xj≥0,j=1,2,…,5系數(shù)矩陣中不包含單位矩陣第22頁(yè)，共53頁(yè)。2.引進(jìn)人工變量x6,x7構(gòu)造單位矩陣，用單純形法求解下列問(wèn)題minx1+x2

-3x3+M(x6+x7)

s.t.x1

-2x2

+x3

+

x4

=11

2x1+x2

-4x3

-x5

+

x

6

=3x1-2x3

+

x7=1xj,≥0,j=1,2,…,73.x4

，x6，x

7

對(duì)應(yīng)的是單位矩陣，可選擇作為基變量，建立單純形表，利用主元消去法，進(jìn)行迭代。第23頁(yè)，共53頁(yè)。xBx1x2x3

x4x5

x6

x7

x4x6x711313M-1M-1-6M+30-M00x4x6x11011

0M-110-M01-3McB0MM113/21--1--0M1x4x2x11211011c

11-300M

M1-21100021-40-11010-20001minx1+x2

-3x3+M(x6+x7)

s.t.x1

-2x2

+x3

+

x4

=11

2x1+x2

-4x3

-x5

+

x

6

=3x1-2x3

+

x

7=1xj,≥0,j=1,2,…,70-23100-10100-11-210-200010031-22-50100-11-210-20001

0010-11-M-1-M4----第24頁(yè)，共53頁(yè)。

000-1/3-1/31/3-M2/3-M419xBx1x2x3x4

x5

x6

x7

cBx4x2x11211011c

11-300M

M0031-22-50100-11-210-20001

0010-11-M-1-M4----x3x2x1-3110011/3-2/32/3-5/30100-11-21002/3-4/34/3-7/34.檢驗(yàn)數(shù)全部小于等于0，并且人工變量全取0，于是得到最優(yōu)解：最優(yōu)值為：f=9+1-3*4=-2

x=(9,1,4)T第25頁(yè)，共53頁(yè)。單純性法小結(jié)M0不處理令z′=-zmaxz=-minz′減去xs加入xa加入人工變量xa加松弛變量xs約束條件兩端同乘以-1不處理令

xj’

=-xj令xj=

xj′

-xj″

xj′

≥0xj″

≥0不處理單純形法圖解法、單純形法求解

xaxs

minzmaxz≥=≤bi<0

bi

≥0xj≤0xj無(wú)約束xj≥0三個(gè)以上兩個(gè)新加變量系數(shù)極大或極小等式或不等式右端項(xiàng)取值變量個(gè)數(shù)建立模型第26頁(yè)，共53頁(yè)。作業(yè)1.用兩階段法或者大M法求解P1595.85.92.利用大M法求解如下的線性規(guī)劃問(wèn)題。

min-2x1-x2

s.t.x1+x2≥

2x1-x2≥1x1≤3x1,x2≥0第27頁(yè)，共53頁(yè)。線性規(guī)劃的對(duì)偶理論與對(duì)偶單純性法線性規(guī)劃早期發(fā)展過(guò)程中的最為重要的理論成果之一就是線性規(guī)劃的對(duì)偶問(wèn)題及相關(guān)理論的提出。

線性規(guī)劃的對(duì)偶理論是解釋資源的影子價(jià)格、線性規(guī)劃問(wèn)題的靈敏度分析等的理論基礎(chǔ)。主要內(nèi)容對(duì)偶問(wèn)題定義----線性規(guī)劃問(wèn)題寫出其對(duì)偶問(wèn)題，要掌握在對(duì)稱形式和非對(duì)稱情況下由原問(wèn)題寫出對(duì)偶問(wèn)題的方法。對(duì)偶定理----原問(wèn)題與對(duì)偶問(wèn)題解的關(guān)系。對(duì)偶單純形法第28頁(yè)，共53頁(yè)。線性規(guī)劃的對(duì)偶模型設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需4種設(shè)備按A，B，C，D順序加工，每件產(chǎn)品加工所需的機(jī)時(shí)數(shù)、每件產(chǎn)品的利潤(rùn)值及每種設(shè)備的可利用機(jī)時(shí)數(shù)列于下表：1216812設(shè)備可利用機(jī)時(shí)數(shù)(時(shí))34022乙20412甲產(chǎn)品利潤(rùn)（元／件）DCBA設(shè)備產(chǎn)品問(wèn)：充分利用設(shè)備機(jī)時(shí)，工廠應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能獲得最大利潤(rùn)？1.對(duì)偶問(wèn)題的現(xiàn)實(shí)來(lái)源第29頁(yè)，共53頁(yè)。解：設(shè)甲、乙型產(chǎn)品各生產(chǎn)x1及x2件，則數(shù)學(xué)模型為：反過(guò)來(lái)問(wèn)：若廠長(zhǎng)決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機(jī)器用于接受外加工，只收加工費(fèi)，那么４種機(jī)器的機(jī)時(shí)如何定價(jià)才是最佳決策？線性規(guī)劃的對(duì)偶模型第30頁(yè)，共53頁(yè)。在市場(chǎng)競(jìng)爭(zhēng)的時(shí)代，廠長(zhǎng)的最佳決策顯然應(yīng)符合兩條：（1）不吃虧原則。即機(jī)時(shí)定價(jià)所賺利潤(rùn)不能低于加工甲、乙型產(chǎn)品所獲利潤(rùn)。（2）競(jìng)爭(zhēng)性原則。即在上述不吃虧原則下，盡量降低機(jī)時(shí)總收費(fèi)，以便爭(zhēng)取更多用戶。設(shè)A、B、C、D設(shè)備的機(jī)時(shí)價(jià)分別為y1、y2、y3、y4，由此原則，便構(gòu)成了一些不等式約束條件。則新的線性規(guī)劃數(shù)學(xué)模型為：第31頁(yè)，共53頁(yè)。把同種問(wèn)題的兩種提法所獲得的數(shù)學(xué)模型表示出來(lái)，將會(huì)發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象。第32頁(yè)，共53頁(yè)。2.原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系原問(wèn)題（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題（原問(wèn)題）第33頁(yè)，共53頁(yè)。(1)對(duì)稱形式 特點(diǎn)：目標(biāo)函數(shù)求極小值，約束條件“≥”，變量非負(fù);目標(biāo)函數(shù)求極大值，約束條件“≤”，變量非負(fù);對(duì)偶定義互為對(duì)偶第34頁(yè)，共53頁(yè)。例寫出下面線性規(guī)劃的

對(duì)偶問(wèn)題第35頁(yè)，共53頁(yè)。一般稱不具有對(duì)稱形式的一對(duì)線性規(guī)劃為非對(duì)稱形式的對(duì)偶規(guī)劃。

方法一：化成對(duì)稱形式的線性規(guī)劃，寫出其對(duì)偶規(guī)劃。(2)非對(duì)稱形式的對(duì)偶問(wèn)題對(duì)偶定義第36頁(yè)，共53頁(yè)。例1：寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題第37頁(yè)，共53頁(yè)。第38頁(yè)，共53頁(yè)。原問(wèn)題對(duì)偶問(wèn)題第39頁(yè)，共53頁(yè)。例2：標(biāo)準(zhǔn)形式的對(duì)偶問(wèn)題對(duì)偶定義對(duì)偶問(wèn)題第40頁(yè)，共53頁(yè)。變量數(shù)：n個(gè)第j個(gè)變量≤0第j個(gè)變量≥0第j個(gè)變量是自由變量約束條件：m個(gè)第i個(gè)約束類型為“≥”第i個(gè)約束類型為“≤”第i個(gè)約束類型為“＝”目標(biāo)函數(shù)max對(duì)偶問(wèn)題（原問(wèn)題）約束條件：n個(gè)第j個(gè)約束類型為“≤”第j個(gè)約束類型為“≥”第j個(gè)約束類型為“＝”變量數(shù)：m個(gè)第i個(gè)變量≤0第i個(gè)變量≥0第i個(gè)