第2章-線性規(guī)劃的圖解法

會計學(xué)1第2章__線性規(guī)劃的圖解法

線性規(guī)劃問題的提出線性規(guī)劃的基本概念線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃問題的標(biāo)準(zhǔn)形式繼續(xù)返回第一節(jié)線性規(guī)劃問題

及其數(shù)學(xué)模型第1頁/共63頁問題的提出例1:生產(chǎn)計劃問題第2頁/共63頁產(chǎn)品I產(chǎn)品2如何安排生產(chǎn)使利潤最大？第3頁/共63頁決策變量（Decisionvariables）目標(biāo)函數(shù)（Objectivefunction）約束條件（Constraintconditions）可行域（Feasibleregion)最優(yōu)解（Optimalsolution)基本概念問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。指決策變量取值時受到的各種資源條件的限制，通常表達(dá)為含決策變量的等式或不等式?？尚杏蛑惺鼓繕?biāo)函數(shù)達(dá)到最優(yōu)的決策變量的值第4頁/共63頁是問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。第1步-確定決策變量設(shè)——I的產(chǎn)量

——II的產(chǎn)量

——利潤第5頁/共63頁第2步--定義目標(biāo)函數(shù)MaxZ=x1+x2決策變量第6頁/共63頁

MaxZ=50

x1+100

x2價值系數(shù)第2步--定義目標(biāo)函數(shù)第7頁/共63頁對我們有何限制?第8頁/共63頁第3步--表示約束條件

x1+x2

300

2

x1+x2

400

x2

250x1、x2

0第9頁/共63頁該計劃的數(shù)學(xué)模型

目標(biāo)函數(shù)MaxZ=50x1+100x2約束條件x1+x2

300

2x1+x2

400

x2

250x1、x2

0x1

x2第10頁/共63頁

例2:某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時數(shù)如下表所示：

產(chǎn)品甲產(chǎn)品乙設(shè)備能力/h設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤/（元/件）15002500

第11頁/共63頁

問題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤？解：設(shè)變量xi為第i種（甲、乙）產(chǎn)品的生產(chǎn)件數(shù)（i＝1，2）。根據(jù)題意，我們知道兩種產(chǎn)品的生產(chǎn)受到設(shè)備能力（機時數(shù)）的限制。

對設(shè)備A：兩種產(chǎn)品生產(chǎn)所占用的機時數(shù)不能超過65，于是我們可以得到不等式：3

x1

+2x2

≤65；對設(shè)備B：兩種產(chǎn)品生產(chǎn)所占用的機時數(shù)不能超過40，于是我們可以得到不等式：2x1

+x2

≤40；第12頁/共63頁

對設(shè)備C

：兩種產(chǎn)品生產(chǎn)所占用的機時數(shù)不能超過75，于是我們可以得到不等式：3x2

≤75；另外，產(chǎn)品數(shù)不可能為負(fù)，即x1,x2≥0。同時，我們有一個追求目標(biāo)，即獲取最大利潤。于是可寫出目標(biāo)函數(shù)z為相應(yīng)的生產(chǎn)計劃可以獲得的總利潤：

z

=1500x1

+2500x2

綜合上述討論，在加工時間以及利潤與產(chǎn)品產(chǎn)量成線性關(guān)系的假設(shè)下，把目標(biāo)函數(shù)和約束條件放在一起，可以建立如下的線性規(guī)劃模型：第13頁/共63頁目標(biāo)函數(shù)Maxz=1500x1+2500x2

約束條件

s.t.3x1+2x2≤652x1+x2≤403x2≤75

x1,x2≥0

第14頁/共63頁線性規(guī)劃問題的共同特征一組決策變量X表示一個方案,一般X大于等于零。約束條件是線性等式或不等式。目標(biāo)函數(shù)是線性的，求目標(biāo)函數(shù)最大化或最小化第15頁/共63頁建模過程1.理解要解決的問題，了解解題的目標(biāo)和條件；2.定義決策變量（x1，x2，…，xn

），每一組值表示一個方案；3.用決策變量的線性函數(shù)形式寫出目標(biāo)函數(shù)，確定最大化或最小化目標(biāo)；4.用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件第16頁/共63頁

線性規(guī)劃模型的一般形式第17頁/共63頁線性規(guī)劃問題的標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式為:目標(biāo)函數(shù)最大約束條件等式?jīng)Q策變量非負(fù)右端項非負(fù)第18頁/共63頁

標(biāo)準(zhǔn)形式可以簡寫為第19頁/共63頁線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個特點：目標(biāo)最大化；約束為等式；決策變量均非負(fù)；右端項非負(fù)。對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式:第20頁/共63頁1、極小化目標(biāo)函數(shù)的問題：設(shè)目標(biāo)函數(shù)為

Minf=c1x1

+c2x2

+…+cnxn

則可以令z

＝-f

，該極小化問題與下面的極大化問題有相同的最優(yōu)解，即

Maxz=-c1x1

-c2x2-…-cnxn

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

Minf

＝-Maxz一般線性規(guī)劃問題的標(biāo)準(zhǔn)形化第21頁/共63頁

2、約束條件不是等式的問題“”約束：加入非負(fù)松馳變量例：

目標(biāo)函數(shù)MaxZ=2x1+3x2約束條件x1+

2x2

84x1

164x2

12x1、x2

0第22頁/共63頁

例：第23頁/共63頁例：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式

Minf=3.6x1

-5.2x2+1.8x3s.t.2.3x1

+5.2x2-6.1x3

≤15.74.1x1

+3.3x3

≥8.9

x1

+x2+x3

=38

x1

,x2,x3≥0

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

當(dāng)“”

約束：減去非負(fù)剩余變量；

第24頁/共63頁其次考慮約束，有2個不等式約束，引進(jìn)松弛變量x4≥0

，剩余變量x5

≥0。于是，我們可以得到以下標(biāo)準(zhǔn)形式：

Max

z=-3.6x1

+5.2x2-1.8x3s.t.

2.3x1+5.2x2-6.1x3+x4=15.74.1x1+3.3x3-x5=8.9

x1+x2+x3=38

x1,x2,x3,x4,x5

≥0第25頁/共63頁3.變量無符號限制的問題：在標(biāo)準(zhǔn)形式中，必須每一個變量均有非負(fù)約束。當(dāng)某一個變量xj沒有非負(fù)約束時，可以令

xj=xj’-xj”其中

xj’≥0，xj”≥0即用兩個非負(fù)變量之差來表示一個無符號限制的變量，當(dāng)然xj的符號取決于xj’和xj”的大小。第26頁/共63頁

例：Max第27頁/共63頁

解：標(biāo)準(zhǔn)形為第28頁/共63頁4.右端項有負(fù)值的問題：在標(biāo)準(zhǔn)形式中，要求右端項必須每一個分量非負(fù)。當(dāng)某一個右端項系數(shù)為負(fù)時，如bi<0，則把該等式約束兩端同時乘以-1，得到：-ai1x1-ai2x2-…-ainxn=-bi。第29頁/共63頁練習(xí)題：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式

Minf=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

≥396x2+2x3+3x4≤-58

x1,x3,x4

≥0第30頁/共63頁解：首先，將目標(biāo)函數(shù)轉(zhuǎn)換成極大化：令z=-f=3x1–5x2–8x3+7x4

；其次考慮約束，有3個不等式約束，引進(jìn)松弛變量x5,x6,x7

≥0

；由于x2無非負(fù)限制，可令x2=x2’-x2”,其中 x2’≥0，x2”≥0

；由于第3個約束右端項系數(shù)為-58，于是把該式兩端乘以-1。于是，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題：第31頁/共63頁

Maxz=3x1–5x2’+5x2”–8x3+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-2x3-3x4-x7

=58

x1,x2’,x2”,x3,x4,x5,x6,x7

≥0

第32頁/共63頁例：將以下線性規(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

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

其次考慮約束，有2個不等式約束，引進(jìn)松弛變量x4，x5

≥0。第三個約束條件的右端值為負(fù)，在等式兩邊同時乘-1。第34頁/共63頁通過以上變換，可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題：

Maxz=-2x1+3x2-4x3s.t.3x1+4x2-5x3+x4=62x1+x3-x5=8-x1-x2-x3=9

x1,x2,x3,x4,x5

≥0第35頁/共63頁練習(xí)建立LP數(shù)學(xué)模型有兩個煤廠A、B，每月分別供應(yīng)三個居民區(qū)X、Y、Z。求運費最少的方案。第36頁/共63頁例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=27500§2圖解法

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

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

為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里，圖上任意一點的坐標(biāo)代表了決策變量的一組值，例1的每個約束條件都代表一個半平面。第38頁/共63頁x2x1X2≥0X2=0x2x1X1≥0X1=0第39頁/共63頁（2）對每個不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。第40頁/共63頁100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400第41頁/共63頁100100x2≤250x2=250200300200300第42頁/共63頁（3）把五個圖合并成一個圖，取各約束條件的公共部分，如圖所示。第43頁/共63頁x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400第44頁/共63頁（4）目標(biāo)函數(shù)z=50x1+100x2，當(dāng)z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動等值線，當(dāng)移動到B點時，z在可行域內(nèi)實現(xiàn)了最大化。A，B，C，D，E是可行域的頂點，對有限個約束條件則其可行域的頂點也是有限的。第45頁/共63頁x1x2z=20000=50x1+100x2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE第46頁/共63頁重要結(jié)論：如果線性規(guī)劃有最優(yōu)解，則一定有一個可行域的頂點對應(yīng)一個最優(yōu)解；無窮多個最優(yōu)解。若將例1中的目標(biāo)函數(shù)變?yōu)閙axz=50x1+50x2，則線段BC上的所有點都代表了最優(yōu)解；第47頁/共63頁無界解。即可行域的范圍延伸到無窮遠(yuǎn)，目標(biāo)函數(shù)值可以無窮大或無窮小。一般來說，這說明模型有錯，忽略了一些必要的約束條件；無可行解。若在例1的數(shù)學(xué)模型中再增加一個約束條件4x1+3x2≥1200，則可行域為空域，不存在滿足約束條件的解，當(dāng)然也就不存在最優(yōu)解了。第48頁/共63頁圖解法的幾點結(jié)論:

（由圖解法得到的啟示）可行域是有界或無界的凸多邊形。若線性規(guī)劃問題存在最優(yōu)解，它一定可以在可行域的頂點得到。若兩個頂點同時得到最優(yōu)解，則其連線上的所有點都是最優(yōu)解。解題思路：找出凸集的頂點，計算其目標(biāo)函數(shù)值，比較即得。第49頁/共63頁例2

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

約束條件：

s.t.x1+x2≥350x1≥

1252x1+x2≤

600x1,x2≥0

采用圖解法。如下圖：得Q點坐標(biāo)（250，100）為最優(yōu)解。第51頁/共63頁100200300400500600100200300400600500x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200x1x2Q第52頁/共63頁

§3圖解法的靈敏度分析

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

變化時，對最優(yōu)解產(chǎn)生的影響。第53頁/共63頁

(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)之間時，原最優(yōu)解x1=50，x2=100仍是最優(yōu)解。第54頁/共63頁一般情況：

z=c1x1+c2x2

寫成斜截式x2=-(c1/c2)x1+z/c2，目標(biāo)函數(shù)等值線的斜率為-(c1/c2)，當(dāng)-1-(c1/c2)0（*）時，原最優(yōu)解仍是最優(yōu)解。第55頁/共63頁假設(shè)產(chǎn)品Ⅱ的利潤100元不變，即c2=100，代到式（*）并整理得

0c1

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

50c2

+第56頁/共63頁假若產(chǎn)品Ⅰ、Ⅱ的利潤均改變，則可直接用式（*）來判斷。