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

第二章

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

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

M&D公司生產兩種產品A和B，基于對現有的存儲水平和下一個月的市場潛力的分析，M&D公司管理層決定A和B的總產量至少要達到350千克，此外，公司的一個客戶訂了125千克的A產品必須首先滿足。每千克A、B產品的制造時間分別為2小時和1小時，總工作時間為600小時。每千克A、B產品的原材料成本分別為2$和3$。確定在滿足客戶要求的前提下，原材料成本最小的生產計劃。67§1問題的提出建模過程1.理解要解決的問題，了解解題的目標和條件；2.定義決策變量（x1，x2，…，xn），每一組值表示一個方案；3.用決策變量的線性函數形式寫出目標函數，確定最大化或最小化目標；4.用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件一般形式目標函數：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…

…目標函數約束條件決策變量xj稱為該問題的決策變量。資源擁有量價值系數在目標函數中xj的系數cj稱為該決策變量的價值系數。技術系數或工藝系數aij稱為該問題的技術系數或工藝系數。由所有aij組成的矩陣稱為約束方程的系數矩陣。在問題中，xj的取值受m項資源的約束，bi稱為第i項資源的擁有量。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用向量表達Pj=（a1j,

a2j,

…

…,anj）Tb=（b1,

b2,

…

…,bm）T簡化表示X=（x1,

x2,

…

…,xn）T其中X

≥

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

c2,

…

…,cn）10例2-1.目標函數：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)目標值z=27500§2圖解法對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標系上作圖表示線性規(guī)劃問題的有關概念，并求解。下面通過例1詳細講解其方法：11圖解線性規(guī)劃問題步驟第一步，畫直角坐標系第二步，根據約束條件畫可行域第三步，畫過坐標原點的目標函數線，斜率為-c1/c2第四步，確定目標函數值的增大（減?。┓较虻谖宀?，讓目標函數沿著增大（減?。┓较蚱叫幸苿樱c可行域相交且有最大（最?。┠繕撕瘮抵档捻旤c，即為線性規(guī)劃問題的最優(yōu)解，然后根據最優(yōu)解求最優(yōu)值。12x1x2z=20000=50x1+100x2圖z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE13二元一次不等式（組）表示的平面區(qū)域的確定怎樣判斷二元一次不等式表示的是直線哪一側的平面區(qū)域？可以用“選點法”確定具體區(qū)域：任選一個不在直線上的點，檢驗它的坐標是否滿足所給的不等式．若適合，則該點所在的一側即為不等式所表示的平面區(qū)域；否則，直線的另一側為所求的平面區(qū)域．14畫出下列不等式所表示的平面區(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為坐標向量建立直角坐標系。在直角坐標系里，圖上任意一點的坐標代表了決策變量的一組值，例1的每個約束條件都代表一個半平面。x2x1X2≥0X2=0x2x1X1≥0X1=017§2圖解法（2）對每個不等式(約束條件)，先取其等式在坐標系中作直線，然后確定不等式所決定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=40030020030040018§2圖解法（3）把五個圖合并成一個圖，取各約束條件的公共部分，如圖2-1所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2-119§2圖解法（4）目標函數z=50x1+100x2，當z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標函數值，稱之為“等值線”。平行移動等值線，當移動到B點時，z在可行域內實現了最大化。A，B，C，D，E是可行域的頂點，對有限個約束條件則其可行域的頂點也是有限的。x1x2z=20000=50x1+100x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE斜截式20價值系數的符號與目標函數直線族的平行移動寫成斜截式比較容易弄清楚移動方向Z=50x1+100x2（+，+）求最大右上方移動，求最小左下方移動Z=-50x1-100x2（-，-）求最大左下方移動，求最小右上方移動Z=-50x1+100x2（-，+）求最大左上方移動，求最小右下方移動Z=50x1-100x2（+，-）求最大右下方移動，求最小左上方移動關鍵在C2，C2為正，則往上平移；C2為負，則往下平移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有無窮多個最優(yōu)解即具有多重解,通解為0≤α≤1

當α=0.5時Ｘ=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)24246x1x2246(1,2)無界解(無最優(yōu)解)maxZ=x1+2x2例2-525x1x2O10203040102030405050無可行解即無最優(yōu)解maxZ=10x1+4x2例2-626由以上例題可知，線性規(guī)劃的解有4種形式：1.有唯一最優(yōu)解(例2-2例2-3)2.有多重最優(yōu)解(例2-4)3.有無界解(例2-5)4.無可行解(例2-6)1、2情形為有最優(yōu)解3、4情形為無最優(yōu)解27§2圖解法重要結論：如果線性規(guī)劃有最優(yōu)解，則一定可以在可行域的某個頂點上找到最優(yōu)解；無窮多個最優(yōu)解，在邊界上取得。若將例2-1中的目標函數變?yōu)閙axz=50x1+50x2，則線段BC上的所有點都代表了最優(yōu)解；無界解。即可行域的范圍延伸到無窮遠，目標函數值可以無窮大或無窮小。一般來說，這說明模型有錯，忽略了一些必要的約束條件；無可行解。若在例2-1的數學模型中再增加一個約束條件4x1+3x2≥1200，則可行域為空域，不存在滿足約束條件的解，當然也就不存在最優(yōu)解了。28進一步討論例2某公司由于生產需要，共需要A，B兩種原料至少350噸（A，B兩種材料有一定替代性），其中A原料至少購進125噸。但由于A，B兩種原料的規(guī)格不同，各自所需的加工時間也是不同的，加工每噸A原料需要2個小時，加工每噸B原料需要1小時，而公司總共有600個加工小時。又知道每噸A原料的價格為2萬元，每噸B原料的價格為3萬元，試問在滿足生產需要的前提下，在公司加工能力的范圍內，如何購買A，B兩種原料，使得購進成本最低？29進一步討論解：目標函數：Minf=2x1+3x2約束條件：s.t.x1+x2≥350x1≥

1252x1+x2≤

600x1,x2≥0采用圖解法。如下圖：得Q點坐標（250，100）為最優(yōu)解。100200300400500600100200300400600500x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200x1x2Q30§3線性規(guī)劃模型的標準化標準化便于代數求解，為后面單純形法求解作準備。一般形式目標函數：Max（Min）z=c1x1+c2x2+…+cnxn約束條件：s.t.a11x1+a12x2+…+a1nxn

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn≥0標準形式目標函數：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線性規(guī)劃的標準化

可以看出，線性規(guī)劃的標準形式有如下四個特點：目標最大化；約束為等式；決策變量均非負；右端項非負。對于各種非標準形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉化為標準形式:32§3線性規(guī)劃的標準化1、決策變量不是非負

在標準形式中，必須每一個變量均有非負約束。1）當決策變量xk≤0，則用-xk’代替xk，且xk’≥02）當某一個變量xj無符號要求時，可以令

xj=xj’-xj”其中

xj’≥0，xj”≥0即用兩個非負變量之差來表示一個無符號限制的變量，當然xj的符號取決于xj’和xj”的大小。33§3線性規(guī)劃的標準化2、約束條件不是等式的問題：設約束條件為

ai1x1+ai2x2+…+ainxn

≤bi可以引進一個新的變量s，使它等于約束右邊與左邊之差

s=bi–(ai1x1

+ai2x2

+…+ainxn

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

ai1x1+ai2x2+…+ainxn+s=bi34§3線性規(guī)劃的標準化當約束條件為

ai1x1+ai2x2+…+ainxn

≥

bi時，類似地令

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

顯然，s也具有非負約束，即s≥0，這時新的約束條件成為

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

36§3線性規(guī)劃的標準化3.極小化目標函數的問題：設目標函數為Minf=c1x1

+c2x2

+…+cnxn

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

-c2x2-…-cnxn

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

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

45目標函數線旋轉CBD0AC2的符號46目標函數線旋轉CBD0A47目標函數線旋轉CBD0A48目標函數線旋轉CBD0A關鍵是找出斜率的分界點49目標函數線旋轉CBD0A關鍵是找出斜率的分界點50目標函數線旋轉CBD0A關鍵是找出斜率的分界點51目標函數線旋轉CBD0A關鍵是找出斜率的分界點52§4圖解法的靈敏度分析假設產品Ⅱ的利潤100元不變，即c2=100，代到式（*）并整理得

0c1

100假設產品Ⅰ的利潤50元不變，即c1=50，代到式（*）并整理得

50c2

+假若產品Ⅰ、Ⅱ的利潤均改變，則可直接用式（*）來判斷。假設產品Ⅰ、Ⅱ的利潤分別為60元、55元，則

-2-(60/55)

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