復(fù)習(xí)課運籌學(xué)課件

復(fù)習(xí)課

運籌學(xué)紹興文理學(xué)院工學(xué)院計算機系2005.12.模型、概念圖解法標(biāo)準化單純形法對偶理論線性規(guī)劃問題第五章線性規(guī)劃的圖解法

maxz=x1+3x2 約束條件：

x1+

x2≤6 -x1+2x2≤8 x1≥0,x2≥0可行域目標(biāo)函數(shù)等值線最優(yōu)解(4/3,14/3)64-860x1x2約束條件(s.t.)線性規(guī)劃問題⑴2.5x1+1.5x2≤904x1+5x2≤2003x1+10x2≤300x1≥0,x2≥0目標(biāo)函數(shù)maxz=7x1+12x2若干個決策變量x1,x2;2.約束條件(≤或≥或＝);3.符號約束(非負或非正或自由);4.目標(biāo)函數(shù)(max或min)。圖解法線性規(guī)劃問題⑵x1+x2≤6x1－x2≤4x1+3x2≥62x1+x2≥4x1≥0,x2≥0s.t.Minz=3x1+2x2約束條件2x1+9x2≤182x1+4x2≤103x1+2x2≤12

x1≥0,x2≥0線性規(guī)劃問題⑵目標(biāo)函數(shù)maxf=3x1+4x2線性規(guī)劃問題⑵2x1+9x2=18最優(yōu)解(3.5,0.75)目標(biāo)函數(shù)f=3x1+4x2=13.53x1+2x2=122x1+4x2=10可行解區(qū)域約束條件x1+2x2≤84x1≤164x2≤12

x1≥0,x2≥0線性規(guī)劃問題⑶目標(biāo)函數(shù)Maxf=2x1+3x2線性規(guī)劃的標(biāo)準化用單純形法求解線性規(guī)劃要先標(biāo)準化：目標(biāo)函數(shù)求極大；全部是等式約束；所有決策變量全有非負約束。MinzMax-z不等式約束通過添加松弛變量(≤)或剩余變量(≥)化為等式約束。處理非正和自由的變量LP問題的單純形法用單純形法求解下列線性規(guī)劃求最大；全是≤的不等式；常數(shù)項b≥0;全有非負約束。這類最適用：

單純形法LP問題的單純形法標(biāo)準化；列初始單純形表；迭代。引入松弛變量x3,成x1+2x2+x3=2引入松弛變量x4,成2x1+x2+x4=2極小化極大。兩個松弛變量LP問題的單純形法初始單純形表基變量是哪兩個？x3x4230000CB=?LP問題的單純形法初始單純形表頭兩行?Zj=?末行？2300121022101200LP問題的單純形法單純形表最優(yōu)?誰進基?比值?誰出基？12LP問題的單純形法迭代X2進基，x3出基，紅格要變成幾?LP問題的單純形法第一次迭代是最優(yōu)解?誰進基?誰出基?LP問題的單純形法第二次迭代是最優(yōu)解?最優(yōu)解是?max?LP問題的單純形法標(biāo)準化；列初始單純形表；迭代。引入松弛變量x4,成x1+x4=2引入松弛變量x5,成x1+x2+2x3+x5=4三個松弛變量引入松弛變量x6,成3x2+4x3+x6=6LP問題的單純形法初始單純形表基變量是哪三個？x４x51200x640000CB=?1

00

1

00

21

12

0

10

40

34

0

01

60

00

0

0001

24

0

00線性規(guī)劃例1.一目標(biāo)函數(shù)是MaxZ的LP問題，用單純形法解的過程中，得到如下數(shù)據(jù)有缺的單純形表。其中u為常數(shù)，求表中(*處)所有缺失的數(shù)。分析CB列中可確定哪幾個？06000Zj行中可確定哪幾個？60000000Z1=？σj行中可確定哪幾個？C1-σ1=666u35-6u-31150a12=?右下角=?基變量列中可確定哪幾個？續(xù)u=?時已得到唯一最優(yōu)解。u>5/6u=0時有最優(yōu)解嗎?無有界最優(yōu)解.u=0.5時有唯一最優(yōu)解嗎?迭代一次得最優(yōu)解.對偶線性規(guī)劃LP問題對偶規(guī)劃的提出求LP問題的對偶規(guī)劃LP問題對偶單純形法例(對偶理論):原問題幾個變量？這是要求X1,

X2使銷售收入最____的LP問題LP的對偶理論設(shè)X1,

X2為產(chǎn)品1,產(chǎn)品2的產(chǎn)量大約束條件有幾個？

等式還是不等式約束？Minf=y1y2

y3

y4

其對偶有幾個變量？約束條件有幾個？求極大？極?。?2極小12+16+12y1y2y3y4y1y2y3y4y1y2y3y42++4+02+2+0+423≥≥≥0，，，+8Minz=2x1+x2-x3x1+x2-x3=

1x1-x2+x3

2x2+x3

3x10,x20,x3自由例1、寫出下面問題的對偶規(guī)劃Maxw=

y1y2y3

+2+3y1y2y3

y1y2y3

y1y2y3

y1y2y3

++0－+－++２１-１≤≥＝自由,≥0,≤0對一般的LP問題中：

原問題第k個約束為等式或≥，對偶問題第k個變量是自由或非正變量。原問題第k個變量是自由或非正變量，則對偶問題第k個約束為等式或≤約束。對偶問題

原問題對偶問題目標(biāo)函數(shù)類型MaxMin目標(biāo)函數(shù)與右邊目標(biāo)函數(shù)系數(shù)右邊常數(shù)項常數(shù)項的對應(yīng)關(guān)系右邊常數(shù)項目標(biāo)函數(shù)系數(shù)變量數(shù)與約束數(shù)變量數(shù)n約束數(shù)n的對應(yīng)關(guān)系約束數(shù)m變量數(shù)m原問題變量類型與 變量≥

0 ≥約束對偶問題約束類型變量≤

0≤約束的對應(yīng)關(guān)系自由變量＝約束原問題約束類型與約束≥

變量≤

0對偶問題變量類型約束≤

變量≥

0的對應(yīng)關(guān)系約束＝自由變量對偶關(guān)系對應(yīng)表原線性規(guī)劃Minz=4X1+2X2-3X3-X1+2X2

62X1+3X3

9X1+5X2-2X3=

4X2,X30Maxf-y1+2y2+y3對偶規(guī)劃例2、寫出下面問題的對偶規(guī)劃=6y1+9y2+4y32y1+5y33y2-2y3y10

,y3自由y20,4

2-3=

Minz=3X1+2X2+X3+4X42X1+4X2+5X3+X403X1-X2+7X3-2X425X1+2X2+X3+6X410X1,X2,X3,

X40例3、用對偶單純形法解規(guī)劃問題運輸問題運輸問題模型；表上作業(yè)法:求初始基可行解、判優(yōu)、迭代。*用Excel解運輸問題。運輸問題產(chǎn)地數(shù)m=2,銷地數(shù)n=3,產(chǎn)銷平衡，決策變量個數(shù)m*n,等式約束數(shù)m+n，不等式約束數(shù)0,目標(biāo)函數(shù)是總運價,要求最小。表上作業(yè)法運輸問題的表上作業(yè)法：平衡產(chǎn)銷；找出初始基可行解(西北角法、最小元素法、Vogel法)；基可行解是否最優(yōu)的判別(閉回路法、位勢法*)；非最優(yōu)的基可行解的改進(閉回路調(diào)整法).

平衡產(chǎn)銷運輸問題中產(chǎn)銷不平衡時：產(chǎn)>銷：增加一個假想的倉庫，運費為0，當(dāng)新銷地。產(chǎn)<銷：增加一個假想的產(chǎn)地，運費為0?？偪梢哉{(diào)整為產(chǎn)銷平衡。

找出初始基可行解運輸問題的獨立的等式約束數(shù)=系數(shù)矩陣的秩=基變量個數(shù)=m+n-1，非基變量個數(shù)=m*n-m-n+1。找出初始基可行解(m+n-1格)：西北角法；最小元素法;伏格爾(Vogel)法*等.

西北角法最后得的初始基可行解。34422223366找初始基可行解的西北角法盡量用下標(biāo)小的（左上角——西北角優(yōu)先安排）：x11=min(s1,d1)=d1=3,劃去第一列（B1已滿足）,s1←s1-x11；x12=min(s1-x11,d2)=4,劃去第一行（A1已滿足）；……劃去m+n-1行(列)大功告成。最小元素法最后得的初始基可行解(不同于西北角法)。31144363333找初始基可行解的最小元素法盡量先用運價小的（就近優(yōu)先安排，可能“因小失大”）：c21=min(cij)=1,x21=min(s2,d1)=3劃去第一列（B1已滿足）s2←s2-x21；c23=min,x23=min(s2-x21,d3)=1劃去第二行（A2已滿足）d3←d3-x23；……劃去m+n-1行(列)大功告成。是基可行解？不是?。?！從閉回路看。？？4+5-1=8。？？？？？基可行解是否最優(yōu)的判別基可行解是否最優(yōu)的判別(閉回路法、位勢法*)；閉回路法求檢驗數(shù),因為非最優(yōu)的基可行解改進時用閉回路調(diào)整,所以優(yōu)先介紹“閉回路法”位勢法求檢驗數(shù)*.

閉回路法對每個非基變量(如x11)求它的閉回路;121求它的檢驗數(shù)：3-1+2-3=1>0。檢驗數(shù)無負是最優(yōu)解，否則可調(diào)整。314633-11012閉回路法調(diào)優(yōu)非基變量如x24檢驗數(shù)負,不是最優(yōu)解;利用它的閉回路調(diào)整:min(1,3)=1;調(diào)整:奇加偶減，新方案再檢驗……。314633121-110121052位勢法判優(yōu)新方案再檢驗,逐個非基變量求檢驗數(shù)太繁，可用位勢法求檢驗數(shù)；檢驗數(shù)全部非負,找到最優(yōu)解(不唯一)。3132560310-23-590221912運輸問題例2.求下列運輸問題的解。檢查產(chǎn)銷是否平衡？產(chǎn)銷平衡？20最小元素法用最小元素法求下列運輸問題的初始基可行解。用位勢法檢查此解是否最優(yōu)？30550350110333位勢法檢驗求出位勢檢查此解是否最優(yōu)？求檢驗數(shù)此解優(yōu)否1否！閉回路？如何調(diào)？迭代、檢驗用閉回路調(diào)整,調(diào)整量？Min{1,3}=1621求位勢！0141001求檢驗數(shù)！361115有負的嗎？最優(yōu)？是！總運費？39！一個求最大的LP問題的單純形表如下：課堂練習(xí)一.求其中空缺的數(shù)(*)分別是什么？求出此LP問題的解。x50040133/40014010000