線(xiàn)性規(guī)劃的圖解法

第二章

線(xiàn)性規(guī)劃的圖解法§1問(wèn)題的提出§2圖解法§3線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)化§4圖解法的靈敏度分析1第二章

線(xiàn)性規(guī)劃的圖解法在管理中一些典型的線(xiàn)性規(guī)劃應(yīng)用合理利用線(xiàn)材問(wèn)題：如何在保證生產(chǎn)的條件下，下料最少配料問(wèn)題：在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)投資問(wèn)題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等，使獲利最大勞動(dòng)力安排：用最少的勞動(dòng)力來(lái)滿(mǎn)足工作的需要運(yùn)輸問(wèn)題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小線(xiàn)性規(guī)劃模型的組成：決策變量用符號(hào)來(lái)表示可控制的因素目標(biāo)函數(shù)MaxF或MinF約束條件s.t.(subjectto)滿(mǎn)足于2§1問(wèn)題的提出例1.某工廠(chǎng)在計(jì)劃期內(nèi)要安排Ⅰ、Ⅱ兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗、資源的限制，如下表：?jiǎn)栴}：工廠(chǎng)應(yīng)分別生產(chǎn)多少單位Ⅰ、Ⅱ產(chǎn)品才能使工廠(chǎng)獲利最多？線(xiàn)性規(guī)劃模型：目標(biāo)函數(shù)：Maxz=50x1+100x2約束條件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥03一家工廠(chǎng)制造三種產(chǎn)品，需要三種資源：技術(shù)服務(wù)、勞動(dòng)力、行政管理。下表列出了三種單位產(chǎn)品對(duì)每種資源的需要量。今有100h的技術(shù)服務(wù)，600h的勞動(dòng)力和300h的行政管理時(shí)間可供使用。試確定能使總利潤(rùn)最大的產(chǎn)品生產(chǎn)量的線(xiàn)性規(guī)劃模型。產(chǎn)品資源/h單位利潤(rùn)/元技術(shù)服務(wù)勞動(dòng)力行政管理111021021426315644解：設(shè)三種產(chǎn)品的生產(chǎn)量分別為x1、x2、x3。線(xiàn)性規(guī)劃模型為：Maxz=10x1+6x2+4x3S.t.x1+x2+x3≤10010x1+4x2+5x3≤6002x1+2x2+6x3≤300x1,x2,x3≥05例2

M&D公司生產(chǎn)兩種產(chǎn)品A和B，基于對(duì)現(xiàn)有的存儲(chǔ)水平和下一個(gè)月的市場(chǎng)潛力的分析，M&D公司管理層決定A和B的總產(chǎn)量至少要達(dá)到350千克，此外，公司的一個(gè)客戶(hù)訂了125千克的A產(chǎn)品必須首先滿(mǎn)足。每千克A、B產(chǎn)品的制造時(shí)間分別為2小時(shí)和1小時(shí)，總工作時(shí)間為600小時(shí)。每千克A、B產(chǎn)品的原材料成本分別為2$和3$。確定在滿(mǎn)足客戶(hù)要求的前提下，原材料成本最小的生產(chǎn)計(jì)劃。67§1問(wèn)題的提出建模過(guò)程1.理解要解決的問(wèn)題，了解解題的目標(biāo)和條件；2.定義決策變量（x1，x2，…，xn），每一組值表示一個(gè)方案；3.用決策變量的線(xiàn)性函數(shù)形式寫(xiě)出目標(biāo)函數(shù)，確定最大化或最小化目標(biāo)；4.用一組決策變量的等式或不等式表示解決問(wèn)題過(guò)程中必須遵循的約束條件一般形式目標(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≥08max（min）z=c1x1+c2x2+…

…

+cnxn

x1，x2，…

…

，xn

≥0st.a11x1+a12x2+…

…

+a1nxn

≤(或=,≥)b1a21x1+a22x2+…

…

+a2nxn

≤(或=,≥)b2an1x1+a2nx2+…

…

+annxn

≤(或=,≥)bm…

…目標(biāo)函數(shù)約束條件決策變量xj稱(chēng)為該問(wèn)題的決策變量。資源擁有量?jī)r(jià)值系數(shù)在目標(biāo)函數(shù)中xj的系數(shù)cj稱(chēng)為該決策變量的價(jià)值系數(shù)。技術(shù)系數(shù)或工藝系數(shù)aij稱(chēng)為該問(wèn)題的技術(shù)系數(shù)或工藝系數(shù)。由所有aij組成的矩陣稱(chēng)為約束方程的系數(shù)矩陣。在問(wèn)題中，xj的取值受m項(xiàng)資源的約束，bi稱(chēng)為第i項(xiàng)資源的擁有量。9其它表示方式xj≥

0(j=1,2,…

…,n)st.max（min）z=cjxjaijxj

≤(或=,≥)bi(i=1,2,…

…,m)max（min）z=X

≥0st.CXC=（c1,

c2,

…,cn）Pjxj

≤(或=,≥)b用向量表達(dá)Pj=（a1j,

a2j,

…

…,anj）Tb=（b1,

b2,

…

…,bm）T簡(jiǎn)化表示X=（x1,

x2,

…

…,xn）T其中X

≥

0st.AX≤(或=,≥)b用矩陣表達(dá)A=a11a12…a1na21a22…a2nam1am2amn………矩陣A稱(chēng)為約束方程組（約束條件）的系數(shù)矩陣。max（min）z=CXC=（c1,

c2,

…

…,cn）10例2-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ì)=27500§2圖解法對(duì)于只有兩個(gè)決策變量的線(xiàn)性規(guī)劃問(wèn)題，可以在平面直角坐標(biāo)系上作圖表示線(xiàn)性規(guī)劃問(wèn)題的有關(guān)概念，并求解。下面通過(guò)例1詳細(xì)講解其方法：11圖解線(xiàn)性規(guī)劃問(wèn)題步驟第一步，畫(huà)直角坐標(biāo)系第二步，根據(jù)約束條件畫(huà)可行域第三步，畫(huà)過(guò)坐標(biāo)原點(diǎn)的目標(biāo)函數(shù)線(xiàn)，斜率為-c1/c2第四步，確定目標(biāo)函數(shù)值的增大（減?。┓较虻谖宀?，讓目標(biāo)函數(shù)沿著增大（減?。┓较蚱叫幸苿?dòng)，與可行域相交且有最大（最?。┠繕?biāo)函數(shù)值的頂點(diǎn)，即為線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解，然后根據(jù)最優(yōu)解求最優(yōu)值。12x1x2z=20000=50x1+100x2圖z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE13二元一次不等式（組）表示的平面區(qū)域的確定怎樣判斷二元一次不等式表示的是直線(xiàn)哪一側(cè)的平面區(qū)域？可以用“選點(diǎn)法”確定具體區(qū)域：任選一個(gè)不在直線(xiàn)上的點(diǎn)，檢驗(yàn)它的坐標(biāo)是否滿(mǎn)足所給的不等式．若適合，則該點(diǎn)所在的一側(cè)即為不等式所表示的平面區(qū)域；否則，直線(xiàn)的另一側(cè)為所求的平面區(qū)域．14畫(huà)出下列不等式所表示的平面區(qū)域：（1）y>-2x+1（2）x-y+2>015(1)x>0(2)6x+5y≤22(3)y>x

16§2圖解法(1)分別取決策變量X1,X2為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里，圖上任意一點(diǎn)的坐標(biāo)代表了決策變量的一組值，例1的每個(gè)約束條件都代表一個(gè)半平面。x2x1X2≥0X2=0x2x1X1≥0X1=017§2圖解法（2）對(duì)每個(gè)不等式(約束條件)，先取其等式在坐標(biāo)系中作直線(xiàn)，然后確定不等式所決定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=40030020030040018§2圖解法（3）把五個(gè)圖合并成一個(gè)圖，取各約束條件的公共部分，如圖2-1所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2-119§2圖解法（4）目標(biāo)函數(shù)z=50x1+100x2，當(dāng)z取某一固定值時(shí)得到一條直線(xiàn)，直線(xiàn)上的每一點(diǎn)都具有相同的目標(biāo)函數(shù)值，稱(chēng)之為“等值線(xiàn)”。平行移動(dòng)等值線(xiàn)，當(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)也是有限的。x1x2z=20000=50x1+100x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE斜截式20價(jià)值系數(shù)的符號(hào)與目標(biāo)函數(shù)直線(xiàn)族的平行移動(dòng)寫(xiě)成斜截式比較容易弄清楚移動(dòng)方向Z=50x1+100x2（+，+）求最大右上方移動(dòng)，求最小左下方移動(dòng)Z=-50x1-100x2（-，-）求最大左下方移動(dòng)，求最小右上方移動(dòng)Z=-50x1+100x2（-，+）求最大左上方移動(dòng)，求最小右下方移動(dòng)Z=50x1-100x2（+，-）求最大右下方移動(dòng)，求最小左上方移動(dòng)關(guān)鍵在C2，C2為正，則往上平移；C2為負(fù)，則往下平移21x1x2O1020304010203040(300,400)(15,10)最優(yōu)解X=(15,10)最優(yōu)值Z=8500例2-222246x1x2246最優(yōu)解X=(3,1)最優(yōu)值Z=5(3,1)minZ=x1+2x2例2-3(1,2)23246x1x2246X（2）＝（3,1）X（1）＝（1,3）(5,5)minZ=5x1+5x2例2-4有無(wú)窮多個(gè)最優(yōu)解即具有多重解,通解為0≤α≤1

當(dāng)α=0.5時(shí)Ｘ=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)24246x1x2246(1,2)無(wú)界解(無(wú)最優(yōu)解)maxZ=x1+2x2例2-525x1x2O10203040102030405050無(wú)可行解即無(wú)最優(yōu)解maxZ=10x1+4x2例2-626由以上例題可知，線(xiàn)性規(guī)劃的解有4種形式：1.有唯一最優(yōu)解(例2-2例2-3)2.有多重最優(yōu)解(例2-4)3.有無(wú)界解(例2-5)4.無(wú)可行解(例2-6)1、2情形為有最優(yōu)解3、4情形為無(wú)最優(yōu)解27§2圖解法重要結(jié)論：如果線(xiàn)性規(guī)劃有最優(yōu)解，則一定可以在可行域的某個(gè)頂點(diǎn)上找到最優(yōu)解；無(wú)窮多個(gè)最優(yōu)解，在邊界上取得。若將例2-1中的目標(biāo)函數(shù)變?yōu)閙axz=50x1+50x2，則線(xiàn)段BC上的所有點(diǎn)都代表了最優(yōu)解；無(wú)界解。即可行域的范圍延伸到無(wú)窮遠(yuǎn)，目標(biāo)函數(shù)值可以無(wú)窮大或無(wú)窮小。一般來(lái)說(shuō)，這說(shuō)明模型有錯(cuò)，忽略了一些必要的約束條件；無(wú)可行解。若在例2-1的數(shù)學(xué)模型中再增加一個(gè)約束條件4x1+3x2≥1200，則可行域?yàn)榭沼?，不存在滿(mǎn)足約束條件的解，當(dāng)然也就不存在最優(yōu)解了。28進(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萬(wàn)元，每噸B原料的價(jià)格為3萬(wàn)元，試問(wèn)在滿(mǎn)足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購(gòu)買(mǎi)A，B兩種原料，使得購(gòu)進(jìn)成本最低？29進(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)解。100200300400500600100200300400600500x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200x1x2Q30§3線(xiàn)性規(guī)劃模型的標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化便于代數(shù)求解，為后面單純形法求解作準(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≥031§3線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)化

可以看出，線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)特點(diǎn)：目標(biāo)最大化；約束為等式；決策變量均非負(fù)；右端項(xiàng)非負(fù)。對(duì)于各種非標(biāo)準(zhǔn)形式的線(xiàn)性規(guī)劃問(wèn)題，我們總可以通過(guò)以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式:32§3線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)化1、決策變量不是非負(fù)

在標(biāo)準(zhǔn)形式中，必須每一個(gè)變量均有非負(fù)約束。1）當(dāng)決策變量xk≤0，則用-xk’代替xk，且xk’≥02）當(dāng)某一個(gè)變量xj無(wú)符號(hào)要求時(shí)，可以令

xj=xj’-xj”其中

xj’≥0，xj”≥0即用兩個(gè)非負(fù)變量之差來(lái)表示一個(gè)無(wú)符號(hào)限制的變量，當(dāng)然xj的符號(hào)取決于xj’和xj”的大小。33§3線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)化2、約束條件不是等式的問(wèn)題：設(shè)約束條件為

ai1x1+ai2x2+…+ainxn

≤bi可以引進(jìn)一個(gè)新的變量s，使它等于約束右邊與左邊之差

s=bi–(ai1x1

+ai2x2

+…+ainxn

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

ai1x1+ai2x2+…+ainxn+s=bi34§3線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)化當(dāng)約束條件為

ai1x1+ai2x2+…+ainxn

≥

bi時(shí)，類(lèi)似地令

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

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

ai1x1+ai2x2+…+ainxn-s=bi35§3線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)化為了使約束由不等式成為等式而引進(jìn)的變量s,當(dāng)不等式為“小于等于”時(shí)稱(chēng)為“松弛變量”；當(dāng)不等式為“大于等于”時(shí)稱(chēng)為“剩余變量”。如果原問(wèn)題中有若干個(gè)非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須對(duì)各個(gè)約束引進(jìn)不同的松弛變量。松弛變量表示未被充分利用的資源，剩余變量表示超過(guò)最低限約束的資源多用量。兩者在目標(biāo)函數(shù)中的價(jià)值系數(shù)均為零。只有決策變量影響到目標(biāo)函數(shù)值。

36§3線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)化3.極小化目標(biāo)函數(shù)的問(wèn)題：設(shè)目標(biāo)函數(shù)為Minf=c1x1

+c2x2

+…+cnxn

(可以)令z＝-f，則該極小化問(wèn)題與下面的極大化問(wèn)題有相同的最優(yōu)解，即Maxz=-c1x1

-c2x2-…-cnxn

但必須注意，盡管以上兩個(gè)問(wèn)題的最優(yōu)解相同，但它們最優(yōu)解的目標(biāo)函數(shù)值（最優(yōu)值）卻相差一個(gè)符號(hào)，即Minf＝-Maxz374.右端項(xiàng)有負(fù)值的問(wèn)題：在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個(gè)分量非負(fù)。當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí)，如bi<0，則把該等式約束兩端同時(shí)乘以-1。如：x1-4x2≥-538線(xiàn)性規(guī)劃標(biāo)準(zhǔn)化的步驟39【例】將下列線(xiàn)性規(guī)劃化為標(biāo)準(zhǔn)型【解】（１）因?yàn)閤3無(wú)符號(hào)要求，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以令40(3)第二個(gè)約束條件是≥號(hào)，在≥號(hào)左端減去剩余變量(Surplusvariable)x5，x5≥0。也稱(chēng)松馳變量(2)第一個(gè)約束條件是≤號(hào)，在≤左端加入松馳變量(slackvariable)x4，x4≥0,化為等式；(4)第三個(gè)約束條件是≤號(hào)且常數(shù)項(xiàng)為負(fù)數(shù)，因此在≤左邊加入松馳變量x6，x6≥0，同時(shí)兩邊乘以－1。（5）目標(biāo)函數(shù)是最小值，為了化為求最大值，令Z′=－Z,得到maxZ′=－Z，即當(dāng)Z達(dá)到最小值時(shí)Z′達(dá)到最大值，反之亦然。41綜合起來(lái)得到下列標(biāo)準(zhǔn)型42當(dāng)某個(gè)約束是絕對(duì)值不等式時(shí)，將絕對(duì)值不等式化為兩個(gè)不等式，再化為等式，例如約束將其化為兩個(gè)不等式再加入松馳變量化為等式。43對(duì)于a≤x≤b(a、b均大于零)的有界變量化為標(biāo)準(zhǔn)形式有兩種方法。一種方法是增加兩個(gè)約束x≥a及x≤b另一種方法是令x'=x－a，則a≤x≤b等價(jià)于0≤x'≤b－a，增加一個(gè)約束x'≤b－a并且將原問(wèn)題所有x用x=x'+a替換。化標(biāo)準(zhǔn)型的步驟總結(jié)1、決策變量非負(fù)2、約束條件為等式3、目標(biāo)函數(shù)極大化4、右端常數(shù)非負(fù)44§4圖解法的靈敏度分析

靈敏度分析：建立數(shù)學(xué)模型和求得最優(yōu)解后，研究線(xiàn)性規(guī)劃的一個(gè)或多個(gè)參數(shù)（系數(shù)）ci,aij,bj變化時(shí)，對(duì)最優(yōu)解產(chǎn)生的影響。4.1目標(biāo)函數(shù)中的系數(shù)ci的靈敏度分析考慮例1的情況，ci的變化只影響目標(biāo)函數(shù)等值線(xiàn)的斜率，只會(huì)引起目標(biāo)函數(shù)旋轉(zhuǎn)，旋轉(zhuǎn)后再平移，找到最優(yōu)值。目標(biāo)函數(shù)z=50x1+100x2

45目標(biāo)函數(shù)線(xiàn)旋轉(zhuǎn)CBD0AC2的符號(hào)46目標(biāo)函數(shù)線(xiàn)旋轉(zhuǎn)CBD0A47目標(biāo)函數(shù)線(xiàn)旋轉(zhuǎn)CBD0A48目標(biāo)函數(shù)線(xiàn)旋轉(zhuǎn)CBD0A關(guān)鍵是找出斜率的分界點(diǎn)49目標(biāo)函數(shù)線(xiàn)旋轉(zhuǎn)CBD0A關(guān)鍵是找出斜率的分界點(diǎn)50目標(biāo)函數(shù)線(xiàn)旋轉(zhuǎn)CBD0A關(guān)鍵是找出斜率的分界點(diǎn)51目標(biāo)函數(shù)線(xiàn)旋轉(zhuǎn)CBD0A關(guān)鍵是找出斜率的分界點(diǎn)52§4圖解法的靈敏度分析假設(shè)產(chǎn)品Ⅱ的利潤(rùn)100元不變，即c2=100，代到式（*）并整理得

0c1

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

50c2

+假若產(chǎn)品Ⅰ、Ⅱ的利潤(rùn)均改變，則可直接用式（*）來(lái)判斷。假設(shè)產(chǎn)品Ⅰ、Ⅱ的利潤(rùn)分別為60元、55元，則

-2-(60/55)

-1那么，最優(yōu)解為z=x1+x2和z=2x1+x2的交點(diǎn)x1=100，x2=200。