確定型決策課件

確定型決策小組成員：

鄭婕1確定型決策主要內(nèi)容確定型決策

--確定型決策概述--確定型決策應(yīng)具備的條件--確定型決策主要方法線性規(guī)劃法

--線性規(guī)劃法概述--線性規(guī)劃法數(shù)學(xué)模型--線性規(guī)劃法求解2確定型決策確定型決策概述確定型決策是指決策的自然狀態(tài)是一種既定的情況，即在已知未來可能發(fā)生的情況的條件下，根據(jù)每一個行動方案只能產(chǎn)生的唯一的結(jié)果，選擇最優(yōu)方案。自然狀態(tài)：指各種可行方案可能遇到的客觀情況和狀態(tài)。

例如：公司可以生產(chǎn)兩種產(chǎn)品1和2，生產(chǎn)產(chǎn)品1在銷量好的情況下獲利100萬，不好的情況下獲50萬，產(chǎn)品2在好的情況下獲利90萬，差的時候獲利60萬。3確定型決策應(yīng)具備的條件（1）存在著決策人希望達(dá)到的一個明確目標(biāo)。（2）只存在一個確定的自然狀態(tài)。（3）存在著可供選擇的兩個或兩個以上的行動方案。（4）不同的行動方案在確定狀態(tài)下的損失或利益值可以計(jì)算出來。例如：某企業(yè)可向三家銀行借貸，但利率不同，分別為8%、7.5%、和8.5%。企業(yè)需決定向哪家銀行借款。很明顯，向利率最底的銀行借款為最佳方案。這就是確定型決策。此外，象企業(yè)中確定狀態(tài)下的庫存管理，生產(chǎn)日程計(jì)劃或設(shè)備計(jì)劃的決策都屬于確定型決策。4確定型決策確定型決策方法（1）線性規(guī)劃法（2）直觀分析法（3）盈虧平衡分析方法（4）投資回收期法（5）排隊(duì)法

5確定型決策線性規(guī)劃法概述線性規(guī)劃（LinearProgramming),簡稱LP。線性規(guī)劃法產(chǎn)生于20世紀(jì)40年代，廣泛應(yīng)用于生產(chǎn)制造、物料分配、人力資源計(jì)劃、運(yùn)輸問題和投資決策等方面。這種方法的本質(zhì)是尋求如何使用有限的資源獲得最大的效果，或者用最小的成本完成一項(xiàng)既定的任務(wù)。通常是在一些線性等式或不等式的約束條件下，尋求目標(biāo)函數(shù)的最優(yōu)值。6確定型決策線性規(guī)劃數(shù)學(xué)模型問題的提出例1：生產(chǎn)計(jì)劃問題某公司可以生產(chǎn)兩種新產(chǎn)品，其主要數(shù)據(jù)如下表所示。問：產(chǎn)品Ⅰ、Ⅱ各生產(chǎn)多少件，使利潤最大？ⅠⅡ限制

設(shè)備臺時128臺時

材料A4016kg材料B0412kg利潤23顯然，此問題是在設(shè)備可用時間和材料重量受到限制的情況下來尋求每周利潤最大化，其決策方案是決定產(chǎn)品一和產(chǎn)品二各自的產(chǎn)量為多少才最佳？7確定型決策線性規(guī)劃的幾個概念（1）決策變量變量是運(yùn)籌學(xué)問題或系統(tǒng)中待確定的某些量，在實(shí)際問題中常常把變量X叫決策變量。在例1中，就可以記x1為生產(chǎn)產(chǎn)品1的產(chǎn)量；x2為生產(chǎn)產(chǎn)品二的產(chǎn)量。（2）約束條件求目標(biāo)函極值時的某些限制稱為約束條件。在例1中，設(shè)備可用時間和材料重量的約束，全為“≤”的不等式約束。（3）目標(biāo)函數(shù)在例1中，生產(chǎn)計(jì)劃安排的“最優(yōu)化”要有一定的標(biāo)準(zhǔn)或評價方法，目標(biāo)函數(shù)就是這種標(biāo)準(zhǔn)的數(shù)學(xué)描述，這里的目標(biāo)要求生產(chǎn)的利潤為最大。8確定型決策根據(jù)上面的規(guī)定，例1的產(chǎn)品組合問題可抽象地歸結(jié)為一個數(shù)學(xué)模型，如下：ⅠⅡ限制

設(shè)備臺時128臺時

材料A4016kg材料B0412kg利潤23目標(biāo)函數(shù)：max

z=2x1

+

3x2約束條件：1x1

+

2x2≤84x1

≤

16

4x2

≤

12x1，x2

≥

0

9確定型決策線性規(guī)劃的假定條件（1）比例性假定。意味著每種經(jīng)營活動對目標(biāo)函數(shù)的貢獻(xiàn)是一個常數(shù)，對資源的消耗也是一個常數(shù)。（2）可加性假定。每個決策變量對目標(biāo)函數(shù)和約束方程的影響是獨(dú)立于其他變量的，目標(biāo)函數(shù)值是每個決策變量對目標(biāo)函數(shù)貢獻(xiàn)的總和。（3）連續(xù)性假定。決策變量應(yīng)取連續(xù)值。（4）確定性假定。所有參數(shù)都是確定的參數(shù)，不包含隨機(jī)因素。

10確定型決策線性規(guī)劃模型所需的數(shù)據(jù)資源單位活動對資源的使用量資源可利用量12…n1a11a12…a1nb12a21a22…a2nb2………………mam1am2…amnbm單位活動對Z的貢獻(xiàn)c1c2…cn11確定型決策線性規(guī)劃的數(shù)學(xué)模型：其中，目標(biāo)函數(shù)可以是min的形式，函數(shù)約束中“≤”可以是“=”或“≥”，變量的非負(fù)性限制也可以取消。

12確定型決策說明：

(1)決策變量：x1，x2，···，xn。

一組決策變量表示為問題的一個方案；(2)目標(biāo)函數(shù)：max(min)zz為決策變量的線性函數(shù);(3)約束條件一組線性不等式。cj為價值系數(shù),bi為資源，aij為技術(shù)系數(shù)(i=1,…,m;j=1,…,n).13確定型決策線性規(guī)劃的標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型（z極大值，等式，b非負(fù)，x非負(fù)）

14確定型決策用向量表示15確定型決策

用矩陣描述為：

其中:X=(x1,x2,···,xn)TC=(c1,c2,···,cn)b=(b1,b2,···,bm)T

16確定型決策標(biāo)準(zhǔn)型的化法

(1)min→max。

令z’=-z即可。(2)不等式。對于“≤”情況，在“≤”左邊加上一個松弛變量（非負(fù)），變?yōu)榈仁?，如x1≤4,可令x1+x3=4,則x3≥0；對于“≥”情況：在“≥”左邊減去一個剩余變量（非負(fù)），變?yōu)榈仁剑?.6x1+0.4x2≥6,可令0.6x1+0.4x2+x4=6。

注意：松弛變量、剩余變量在目標(biāo)函數(shù)中的價值系數(shù)為0。(3)無約束變量。令xj=xj’-

xj”，xj’,xj”≥

0，代入即可。(4)變量xj≤0。令xj’=-xj即可。

17確定型決策

將下述問題化為標(biāo)準(zhǔn)型

minz=-x1+2x2-3x3x1+x2+x3

≤

7① x1-x2+x3

≥

2② -3x1+x2+2x3

=5③ x1,x2

≥

0，x3無約束解：令x3

=x3’-x3”，x3’,x3”≥

0；①式加上一個松弛變量x4；②式減去一個剩余變量x5；令z’=-z、；

maxz’=x1-

2x2

+

3(x3’

-

x3”)

+

0x4

+

0x5x1

+

x2

+(x3’

-

x3”)

+

x4

=7 x1

-

x2

+(x3’

-

x3”)

-

x5=2 -3x1

+

x2

+

2(x3’

-

x3”)

=5 x1,x2,x3’,x3”,x4,x5

≥

0 18確定型決策線性規(guī)劃求解圖解法比較簡單、直觀，適用于只有兩個變量的線性規(guī)劃問題。單純形法適用于兩個或兩個以上變量的線性規(guī)劃問題，比較復(fù)雜的問題需要借助計(jì)算機(jī)軟件求解。

19確定型決策線性規(guī)劃解的概念設(shè)線性規(guī)劃為max

z=cx

①Ax=b②x≥0③

A為m

×

n矩陣,n

>

m,Rank

A=m(A為行滿秩矩陣）

1、可行解：滿足條件②、③的X；

2、最優(yōu)解：滿足條件①的可行解；

3、基：取B為A中的m

×

m子矩陣，Rank

B

=

m，則稱B為線性規(guī)劃問題的一個基。取B=(p1,p2,···,pm)pj=(a1j,a2j,···,amj)T

則稱x1,x2,···,xm為基變量，其它為非基變量。20確定型決策4、基解：取B=(p1,p2,···,pm)

a11,···,a1mx1a1m+1,···,a1nxm+1b1┆┆┆+

┆

┆┆=┆

am1,···,ammxmamm+1,···,amnxnbm

↑↑

↑↑基基變量

非基非基變量

令xm+1=···=xn=0(非基變量為0)則BXB=b

∴

21確定型決策5、基可行解滿足③式要求的基解。如右圖所示，各邊交點(diǎn)O,Q1,Q2,Q3,Q4均為基可行解；而其延長線的交點(diǎn)Q5為基解，但不是基可行解。O(0,0)Q1(4,0)Q2(4,2)Q4(0,3)Q3(2,3)Q5(4,3)6、可行基基可行解對應(yīng)的B為可行基。可行解基可行解非可行解基解22確定型決策

圖解法用圖解法求例1。max

z=2x1

+

3x21x1

+

2x2

≤

8①4x1

≤

16②

4x2

≤

12③x1，x2

≥

0解：(1)建立x1

-

x2坐標(biāo)；x2x1(2)約束條件的幾何表示；

①②Q1Q2③Q3Q4(3)目標(biāo)函數(shù)的幾何表示；

*

z=2x1

+

3x2

o4323確定型決策首先取z=0，然后，使z逐漸增大，直至找到最優(yōu)解所對應(yīng)的點(diǎn)。*可見，在Q2點(diǎn)z取到最大值。因此，Q2點(diǎn)所對應(yīng)的解為最優(yōu)解。Q2點(diǎn)坐標(biāo)為(4，2)。即:x1

=

4，x2

=

2∴由此求得最優(yōu)解：x1*

=

4x2*

=

2最大值：max

z

=

z*

=

2x1

+

3x2

=

14x2x1①②Q1Q2(4,2)③Q3Q4*4324確定型決策討論：(1)唯一最優(yōu)解max

z

=

z*時，解唯一，如上例。(2)無窮多最優(yōu)解

對例1，若目標(biāo)函數(shù)

z

=

2x1

+

4x2，此時表示目標(biāo)函數(shù)的直線與表示條件①的直線平行，最優(yōu)點(diǎn)在線段Q3Q2上。即存在無窮多最優(yōu)解。x2x1②Q1Q2(4,2)③Q3(2,3)Q4o43*①25確定型決策(3)無界解

max

z=2x1

+

3x24x1

≤

16x1，x2

≥

0則x2

→

∞，z

→

∞。即存在無界解。在實(shí)際問題中，可能是缺少約束條件。o22426確定型決策(4)無可行解

max

z

=

2x1

+

3x22x1

+

4x2

≥

8x1

+

x2

≤

1x1，x2

≥

0

無公共部分，無可行域。即無可行解。在實(shí)際問題中，可能是關(guān)系錯。1124x1x227確定型決策

單純形法

基本思路：從可行域的一個頂點(diǎn)到另一個頂點(diǎn)迭代求最優(yōu)解。初始基可行解的確定1、松弛基（松弛變量對應(yīng)的B）

max

z=x1

+

3x2x1

+

2x2≤32x1

+

3x2≤4x1,x2

≥0max

z=x1

+

3x2

+

0x3

+

0x4

x1

+

2x2

+

x3

=32x1

+

3x2

+

x4=4x1,x2,x3,x4

≥0

化標(biāo)準(zhǔn)型

取x3、x4為基變量,令非基變量x1=x2=0∴初始基可行解：X(0)=(0034)T28確定型決策2、觀察法

max

z=x1

+

3x2

+

2x3

+

x4x1

+

2x2

+

3x3

=3

3x2

+

x3

+

x4=4x1,x2,x3,x4

≥0

選XB=(x1x4)T

令x2=x3=0

則初始基可行解：X(0)=(3004)T29確定型決策最優(yōu)性的檢驗(yàn)與解的判別30確定型決策則31確定型決策解的判別：1.若，則此時的基可行解為最優(yōu)解；2.若存在某個非基變量的檢驗(yàn)數(shù)，且，則該線性規(guī)劃問題具有無界解（或稱無最優(yōu)解）；3.若所有，又，對于某個非基變量有，則該線性規(guī)劃問題具有無窮多最優(yōu)解。32確定型決策基變換33確定型決策旋轉(zhuǎn)運(yùn)算（消元運(yùn)算）

a1k’0

┆

┆al-1k’0pk’=（alk’）（1）al+1k’0┆

┆amk’0

得到基可行解，重復(fù)上面的步驟，求出最優(yōu)解。34確定型決策單純形表

35確定型決策

建立單純形表cBxBbc1···cncn+1···cn+mθx1···xnxn+1···xn+mcn+1xn+1b1a11···a1n1···0θ1┆┆┆┆┆┆┆┆cn+mxn+mbmam1···amn0···1θm-z-z0σ1

···σn

0···0σj

用單純形法求解

max

z=x1

+

3x2x1

+

2x2

≤

84x1

≤

16

4x2

≤

12x1,x2

≥

036確定型決策

解：①標(biāo)準(zhǔn)化，建立單純形表

引入松弛變量x3，x4，x5為初始基變量

max

z=x1+3x2+0x3+0x4+0x5x1

+

2x2

+

x3

=84x1

+

x4

=16

4x2

+

x5=12x1,x2,x3,x4,x5≥0cBxBbx1x2x3x4x5θ13000cBxBbx1x2x3x4