運(yùn)籌學(xué)-第2章-線性規(guī)劃的圖解法_第1頁(yè)
運(yùn)籌學(xué)-第2章-線性規(guī)劃的圖解法_第2頁(yè)
運(yùn)籌學(xué)-第2章-線性規(guī)劃的圖解法_第3頁(yè)
運(yùn)籌學(xué)-第2章-線性規(guī)劃的圖解法_第4頁(yè)
運(yùn)籌學(xué)-第2章-線性規(guī)劃的圖解法_第5頁(yè)
已閱讀5頁(yè),還剩38頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡(jiǎn)介

管理運(yùn)籌學(xué)朱曉輝管理科學(xué)與工程2-1第二章

線性規(guī)劃的圖解法教學(xué)目標(biāo):掌握線性規(guī)劃的數(shù)學(xué)模型,能夠結(jié)合問題列出模型理解圖解法求解了解圖解法的靈敏度分析2-2第二章

線性規(guī)劃的圖解法§1問題的提出§2圖解法§3圖解法的靈敏度分析2-3第二章

線性規(guī)劃的圖解法在管理中一些典型的線性規(guī)劃應(yīng)用:合理利用線材問題:如何在保證生產(chǎn)的條件下,下料最少配料問題:在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)投資問題:從投資項(xiàng)目中選取方案,使投資回報(bào)最大產(chǎn)品生產(chǎn)計(jì)劃:合理利用人力、物力、財(cái)力等,使獲利最大勞動(dòng)力安排:用最少的勞動(dòng)力來滿足工作的需要運(yùn)輸問題:如何制定調(diào)運(yùn)方案,使總運(yùn)費(fèi)最小2-4線性規(guī)劃的組成:目標(biāo)函數(shù)MaxF或MinF約束條件s.t.(subjectto)滿足于決策變量用符號(hào)來表示可控制的因素§1問題的提出2-5例1.某工廠在計(jì)劃期內(nèi)要安排Ⅰ、Ⅱ兩種產(chǎn)品的生產(chǎn),已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗、資源的限制,如下表:?jiǎn)栴}:工廠應(yīng)分別生產(chǎn)多少單位Ⅰ、Ⅱ產(chǎn)品才能使工廠獲利最多?線性規(guī)劃模型:

目標(biāo)函數(shù):Maxz=50x1+100x2

約束條件:s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0

把滿足所有約束條件的解稱為該線性規(guī)劃的可行解。把使得目標(biāo)函數(shù)值最大(即利潤(rùn)最大)的可行解稱為該線性規(guī)劃的最優(yōu)解,此目標(biāo)函數(shù)值稱為最優(yōu)目標(biāo)函數(shù)值,簡(jiǎn)稱最優(yōu)值。2-6§1問題的提出建模過程1.理解要解決的問題,了解解題的目標(biāo)和條件;2.定義決策變量(x1,x2,…

,xn

),每一組值表示一個(gè)方案;3.用決策變量的線性函數(shù)形式寫出目標(biāo)函數(shù),確定最大化或最小化目標(biāo);4.用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件一般形式:目標(biāo)函數(shù):Max(Min)z=c1x1+c2x2+…+cnxn

約束條件:s.t.a11x1+a12x2+…+a1nxn

≤(=,≥)b1

a21x1+a22x2+…+a2nxn

≤(=,≥)b2…………

am1x1+am2x2+…+amnxn

≤(=,≥)bm

x1,x2,…,xn≥02-7練習(xí)題:

某公司由于生產(chǎn)需要,共需要A,B兩種原料至少350噸(A,B兩種原料有一定替代性),其中原料A至少購(gòu)進(jìn)125t.但由于A,B兩種原料的規(guī)格不同,各自所需的加工時(shí)間也是不同的,加工每噸原料A需要2小時(shí),加工每噸原料B需要1小時(shí),而公司總共有600個(gè)加工時(shí)數(shù).又知道每噸原料A的價(jià)格為2萬元,每噸原料B的價(jià)格為3萬元,試問在滿足生產(chǎn)需要的前提下,在公司加工能力的范圍內(nèi),如何購(gòu)買A,B兩種原料,使得購(gòu)進(jìn)成本最低?2-8例1.目標(biāo)函數(shù):

Maxz=50x1+100x2約束條件:

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最優(yōu)解:

x1=50,x2=250

最優(yōu)目標(biāo)值z(mì)=275002-9§2圖解法

對(duì)于只有兩個(gè)決策變量的線性規(guī)劃問題,可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問題的有關(guān)概念,并求解。下面通過例1詳細(xì)講解其方法:§2圖解法

(1)分別取決策變量X1,X2

為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里,圖上任意一點(diǎn)的坐標(biāo)代表了決策變量的一組值,例1的每個(gè)約束條件都代表一個(gè)半平面。2-10x2x1X2≥0X2=0x2x1X1≥0X1=0§2圖解法

(2)對(duì)每個(gè)不等式(約束條件),先取其等式在坐標(biāo)系中作直線,然后確定不等式所決定的半平面。2-11100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400§2圖解法

(3)把五個(gè)圖合并成一個(gè)圖,取各約束條件的公共部分(包括五條邊界線),如圖2-1所示。2-12100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2-1

可行域可行域的幾何形狀由于問題不同可以千變?nèi)f化,但可行域的幾何結(jié)構(gòu)是凸集要求集合中的任何兩點(diǎn)的連線段落在這個(gè)集合中

2-13§2圖解法

(4)目標(biāo)函數(shù)z=50x1+100x2,當(dāng)z取某一固定值時(shí)得到一條直線,直線上的每一點(diǎn)都具有相同的目標(biāo)函數(shù)值,稱之為“等值線”。平行移動(dòng)等值線,當(dāng)移動(dòng)到B點(diǎn)時(shí),z在可行域內(nèi)實(shí)現(xiàn)了最大化。A,B,C,D,E是可行域的頂點(diǎn),對(duì)有限個(gè)約束條件則其可行域的頂點(diǎn)也是有限的。2-14x1x2z=20000=50x1+100x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE§2圖解法重要結(jié)論:如果線性規(guī)劃有最優(yōu)解,則一定有一個(gè)可行域的頂點(diǎn)對(duì)應(yīng)一個(gè)最優(yōu)解;無窮多個(gè)最優(yōu)解。若將例1中的目標(biāo)函數(shù)變?yōu)閙axz=50x1+50x2,則線段BC上的所有點(diǎn)都代表了最優(yōu)解;無界解。即可行域的范圍延伸到無窮遠(yuǎn),目標(biāo)函數(shù)值可以無窮大或無窮小。一般來說,這說明模型有錯(cuò),忽略了一些必要的約束條件;無可行解。若在例1的數(shù)學(xué)模型中再增加一個(gè)約束條件4x1+3x2≥1200,則可行域?yàn)榭沼颍淮嬖跐M足約束條件的解,當(dāng)然也就不存在最優(yōu)解了。2-15練習(xí)題2.用圖解法求解下列線性規(guī)劃問題,并指出哪個(gè)問題具有惟一最優(yōu)解、無窮多最優(yōu)解、無界解或無可行解.

(1)minf=6x1+4x2;

約束條件:

2x1+x2≥1,

3x1+4x2≥3,

x1,x2≥0.

(2)maxz=4x1+8x2;

約束條件:

2x1+2x2≤10,

-x1+x2≥8,

x1,x2≥0.

2-16(3)maxz=3x1-2x2;

約束條件:

x1+x2≤1,

2x1+2x2≥4,

x1,x2≥0.

(4)maxz=3x1+9x2;

約束條件:

x1+3x2≤22,

-x1+x2≤4,

x2≤6,

2x1-5x2≤0,

x1,x2≥02-17答案(1)有唯一解x1=0.2,x2=0.6函數(shù)值為3.6(2)無可行解(4)無可行解(5)無窮多解2-18§2圖解法

在最優(yōu)生產(chǎn)方案下資源消耗的情況:把x1=50,x2=250代入約束條件得設(shè)備臺(tái)時(shí):1*50+1*250=300原料A:2*50+1*250=350原料B:0*50+1*250=250

說明:生產(chǎn)50單位Ⅰ產(chǎn)品和250單位Ⅱ產(chǎn)品將消耗完所有可能的設(shè)備臺(tái)時(shí)數(shù)及原料B,但對(duì)原料A則還剩余50千克。

在線性規(guī)劃中,一個(gè)“

”約束條件中沒使用的資源或能力稱之為松弛量。為了把一個(gè)線性規(guī)劃標(biāo)準(zhǔn)化,需要有代表沒有使用的資源或能力的變量,稱之為松弛變量,記為si2-19§2圖解法線性規(guī)劃的標(biāo)準(zhǔn)化內(nèi)容之一:——引入松馳變量(含義是資源的剩余量)例1中引入s1,s2,s3模型化為目標(biāo)函數(shù):Maxz=50x1+100x2+0s1+0s2+0s3

約束條件:s.t.x1+x2+s1=3002x1+x2+s2=400x2+s3=

250x1,x2,s1,s2,s3≥0

對(duì)于最優(yōu)解

x1=50x2=250,s1=0s2=50s3=0

把所有的約束條件都寫成等式,稱為線性規(guī)劃模型的標(biāo)準(zhǔn)化。2-20進(jìn)一步討論

例2

某公司由于生產(chǎn)需要,共需要A,B兩種原料至少350噸(A,B兩種材料有一定替代性),其中A原料至少購(gòu)進(jìn)125噸。但由于A,B兩種原料的規(guī)格不同,各自所需的加工時(shí)間也是不同的,加工每噸A原料需要2個(gè)小時(shí),加工每噸B原料需要1小時(shí),而公司總共有600個(gè)加工小時(shí)。又知道每噸A原料的價(jià)格為2萬元,每噸B原料的價(jià)格為3萬元,試問在滿足生產(chǎn)需要的前提下,在公司加工能力的范圍內(nèi),如何購(gòu)買A,B兩種原料,使得購(gòu)進(jìn)成本最低?2-21進(jìn)一步討論解:目標(biāo)函數(shù):Minf=2x1+3x2

約束條件:s.t.x1+x2≥350x1≥

1252x1+x2≤

600x1,x2≥0

采用圖解法。如下圖:得Q點(diǎn)坐標(biāo)(250,100)為最優(yōu)解。2-22100200300400500600100200300400600500x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200x1x2Q

原料A與B的總量及加工時(shí)間正好達(dá)到,而原料A的購(gòu)進(jìn)量則比其最低限多購(gòu)進(jìn)了250-125=125(t),這個(gè)超過量在線性規(guī)劃中稱為剩余量。對(duì)于“

”約束條件,可以增加一些最低限約束的超過量,稱之為剩余變量。從而把“

”約束條件變?yōu)榈仁郊s束條件。2-23

加了松弛變量和剩余變量后的例2的數(shù)學(xué)模型為:目標(biāo)函數(shù):Minf=2x1+3x2+0s1+0s2+0s3

約束條件:s.t.x1+x2-s1=350x1-s2=

1252x1+x2+s3=

600x1,x2,s1,s2,s3

≥02-24§3圖解法的靈敏度分析線性規(guī)劃的標(biāo)準(zhǔn)化一般形式目標(biāo)函數(shù):Max(Min)z=c1x1+c2x2+…+cnxn

約束條件:s.t.a11x1+a12x2+…+a1nxn

≤(=,≥)b1

a21x1+a22x2+…+a2nxn

≤(=,≥)b2…………

am1x1+am2x2+…+amnxn

≤(=,≥)bm

x1,x2,…,xn≥0標(biāo)準(zhǔn)形式目標(biāo)函數(shù):Maxz=c1x1+c2x2+…+cnxn

約束條件:s.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1,x2,…,xn≥0,bi≥02-25§3圖解法的靈敏度分析

可以看出,線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)特點(diǎn):目標(biāo)最大化;約束為等式;決策變量均非負(fù);右端項(xiàng)非負(fù)。對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題,我們總可以通過以下變換,將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式:2-26§3圖解法的靈敏度分析1.極小化目標(biāo)函數(shù)的問題:

設(shè)目標(biāo)函數(shù)為

Minf=c1x1

+c2x2

+…+cnxn

(可以)令z

=-f

,則該極小化問題與下面的極大化問題有相同的最優(yōu)解,即Maxz=-c1x1

-c2x2-…-cnxn

但必須注意,盡管以上兩個(gè)問題的最優(yōu)解相同,但它們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào),即

Minf

=-Maxz2-27§3圖解法的靈敏度分析2、約束條件不是等式的問題:設(shè)約束條件為

ai1x1+ai2x2+…+ainxn

≤bi

可以引進(jìn)一個(gè)新的變量s

,使它等于約束右邊與左邊之差

s=bi–(ai1x1

+ai2x2

+…+ainxn

)顯然,s

也具有非負(fù)約束,即s≥0,這時(shí)新的約束條件成為

ai1x1+ai2x2+…+ainxn+s=bi2-28§3圖解法的靈敏度分析

當(dāng)約束條件為

ai1x1+ai2x2+…+ainxn≥bi

時(shí),類似地令

s=(ai1x1+ai2x2+…+ainxn)-bi

顯然,s也具有非負(fù)約束,即s≥0,這時(shí)新的約束條件成為

ai1x1+ai2x2+…+ainxn-s=bi2-29§3圖解法的靈敏度分析

為了使約束由不等式成為等式而引進(jìn)的變量s,當(dāng)不等式為“小于等于”時(shí)稱為“松弛變量”;當(dāng)不等式為“大于等于”時(shí)稱為“剩余變量”。如果原問題中有若干個(gè)非等式約束,則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí),必須對(duì)各個(gè)約束引進(jìn)不同的松弛變量。

2-303.右端項(xiàng)有負(fù)值的問題:

在標(biāo)準(zhǔn)形式中,要求右端項(xiàng)必須每一個(gè)分量非負(fù)。當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí),如bi<0,則把該等式約束兩端同時(shí)乘以-1,得到:-ai1x1-ai2x2-…-ainxn

=-bi?!?圖解法的靈敏度分析例:將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式

Minf=2x1-3x2+4x3s.t.3x1

+4x2-5x3≤62x1+x3≥8

x1+x2+x3=-9

x1,x2,x3

≥0

解:首先,將目標(biāo)函數(shù)轉(zhuǎn)換成極大化:令z=-f=-2x1+3x2-4x3

其次考慮約束,有2個(gè)不等式約束,引進(jìn)松弛變量和剩余變量x4,x5

≥0。第三個(gè)約束條件的右端值為負(fù),在等式兩邊同時(shí)乘-1。2-31§3圖解法的靈敏度分析通過以上變換,可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題:

Maxz=-2x1+3x2-4x3s.t.3x1+4x2-5x3+x4=62x1+x3-x5=8-x1-x2-x3=9x1,x2,x3,x4,x5≥0***變量無符號(hào)限制的問題***:

2-323.將下述線性規(guī)劃問題化成標(biāo)準(zhǔn)形式:

(1)maxf=3x1+2x2;

約束條件:

9x1+2x2≤30,

3x1+2x2≤13,

2x1+2x2≤9,

x1,x2≥0.

(2)minf=4x1+6x2;

約束條件:

3x1-x2≥6,

x1+2x2≤10,

7x1-6x2=4,

x1,x2≥02-33§3圖解法的靈敏度分析

靈敏度分析:建立數(shù)學(xué)模型和求得最優(yōu)解后,研究線性規(guī)劃的一個(gè)或多個(gè)參數(shù)(系數(shù))ci,aij,bj

變化時(shí),對(duì)最優(yōu)解產(chǎn)生的影響。靈敏度分析是非常重要的,首先是因?yàn)閏i,aij,bj這些都是估計(jì)值和預(yù)測(cè)值,不一定非常精確;再則即使這些系數(shù)值在某一時(shí)刻是精確值,它們也會(huì)隨著市場(chǎng)條件的變化而變化,不會(huì)一成不變的。有了靈敏度分析就不必為了應(yīng)付這些變化而不停地建立新的模型和求新的最優(yōu)解,也不會(huì)由于系數(shù)估計(jì)和預(yù)測(cè)的精確性而對(duì)所求得的最優(yōu)解存有不必要的懷疑。2-34§3圖解法的靈敏度分析3.1目標(biāo)函數(shù)中的系數(shù)ci

的靈敏度分析考慮例1的情況,ci的變化只影響目標(biāo)函數(shù)等值線的斜率,目標(biāo)函數(shù)z=50x1+100x2在z=x2(x2=250斜率為0

)

到z=x1+x2(x2=-x1+z斜率為-1

)之間時(shí),原最優(yōu)解x1=50,x2=250仍是最優(yōu)解。2-35§3圖解法的靈敏度分析

2-36x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400§3圖解法的靈敏度分析2-37x1x2z=20000=50x1+100x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE3.1目標(biāo)函數(shù)中的系數(shù)ci

的靈敏度分析考慮例1的情況,ci的變化只影響目標(biāo)函數(shù)等值線的斜率,目標(biāo)函數(shù)z=50x1+100x2在z=x2(x2=z斜率為0

)

到z=x1+x2(x2=-x1+z斜率為-1

)之間時(shí),原最優(yōu)解x1=50,x2=250仍是最優(yōu)解。一般情況:

z=c1x1+c2x2

寫成斜截式x2=-(c1/c2)x1+z/c2

目標(biāo)函數(shù)等值線的斜率為-(c1/c2),

當(dāng)-1-(c1/c2)0(*式)時(shí),原最優(yōu)解仍是最優(yōu)解。2-38§3圖解法的靈敏度分析

為了計(jì)算出c1在什么范圍變化時(shí)頂點(diǎn)B仍然是其最優(yōu)解,假設(shè)產(chǎn)品Ⅱ的利潤(rùn)100元不變,即c2=100,代到式(*)并整理得0c1100

假設(shè)產(chǎn)品Ⅰ的利潤(rùn)50元不變,即c1=50,代到式(*)并整理得

50c2+

假若產(chǎn)品Ⅰ、Ⅱ的利潤(rùn)均改變

溫馨提示

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

評(píng)論

0/150

提交評(píng)論