第二章

線性規劃的圖解法§1問題的提出§2圖解法§3圖解法的靈敏度分析1整理課件第二章

線性規劃的圖解法在管理中一些典型的線性規劃應用合理利用線材問題：如何在保證生產的條件下，下料最少配料問題：在原料供應量的限制下如何獲取最大利潤投資問題：從投資項目中選取方案，使投資回報最大產品生產計劃：合理利用人力、物力、財力等，使獲利最大勞動力安排：用最少的勞動力來滿足工作的需要運輸問題：如何制定調運方案，使總運費最小線性規劃的組成：目標函數maxf或minf約束條件s.t.(subjectto)滿足于決策變量用符號來表示可控制的因素2整理課件§1問題的提出例1.某工廠在計劃期內要安排Ⅰ、Ⅱ兩種產品的生產，已知生產單位產品所需的設備臺時及A、B兩種原材料的消耗、資源的限制，如下表：問題：工廠應分別生產多少單位Ⅰ、Ⅱ產品才能使工廠獲利最多？線性規劃模型：目標函數：maxz=50x1+100x2

約束條件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥03整理課件§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≥04整理課件例1.目標函數：

maxz=50x1+100x2約束條件：

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

x1=50，x2=250

最優目標值z=27500§2圖解法

對于只有兩個決策變量的線性規劃問題，可以在平面直角坐標系上作圖表示線性規劃問題的有關概念，并求解。下面通過例1詳細講解其方法：5整理課件§2圖解法(1)分別取決策變量X1,X2

為坐標向量建立直角坐標系。在直角坐標系里，圖上任意一點的坐標代表了決策變量的一組值，例1的每個約束條件都代表一個半平面。x2x1X2≥0X2=0x2x1X1≥0X1=06整理課件§2圖解法（2）對每個不等式(約束條件)，先取其等式在坐標系中作直線，然后確定不等式所決定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400x1x1x2x27整理課件§2圖解法（3）把五個圖合并成一個圖，取各約束條件的公共部分，如圖2-1所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2-1x1x28整理課件§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+100x2CBADE9整理課件§2圖解法線性規劃的標準化內容之一：——引入松馳變量（含義是資源的剩余量）例1中引入s1，s2，s3模型化為目標函數：maxz=50x1+100x2+0s1+0s2+0s3

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

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

對于最優解

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

說明：生產50單位Ⅰ產品和250單位Ⅱ產品將消耗完所有可能的設備臺時數及原料B，但對原料A則還剩余50千克。10整理課件§2圖解法重要結論：如果線性規劃有最優解，則一定有一個可行域的頂點對應一個最優解；無窮多個最優解。若將例1中的目標函數變為maxz=50x1+50x2，則線段BC上的所有點都代表了最優解；無界解。即可行域的范圍延伸到無窮遠，目標函數值可以無窮大或無窮小。一般來說，這說明模型有錯，忽略了一些必要的約束條件；無可行解。若在例1的數學模型中再增加一個約束條件4x1+3x2≥1200，則可行域為空域，不存在滿足約束條件的解，當然也就不存在最優解了。11整理課件圖解法–無界解線性規劃存在無界解，即無最優解的情況。對下述線性規劃問題：約束條件：maxz=x1+x2；x1-x2

≤1

-3x1+2x2≤6x1≥0,x2≥012整理課件圖解法–無界解用圖解法求解結果，如圖所示，可以看到，該問題可行域無界，目標函數值可以增大到無窮大，成為無界解，即為無最優解。x1x2x2=0x1=0圖2-11234-1-21234-1z=0=x1+x2z=1=x1+x2z=3=x1+x213整理課件進一步討論

例2

某公司由于生產需要，共需要A，B兩種原料至少350噸（A，B兩種材料有一定替代性），其中A原料至少購進125噸。但由于A，B兩種原料的規格不同，各自所需的加工時間也是不同的，加工每噸A原料需要2個小時，加工每噸B原料需要1小時，而公司總共有600個加工小時。又知道每噸A原料的價格為2萬元，每噸B原料的價格為3萬元，試問在滿足生產需要的前提下，在公司加工能力的范圍內，如何購買A，B兩種原料，使得購進成本最低？14整理課件進一步討論解：目標函數：minf=2x1+3x2

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

1252x1+x2≤

600x1,x2≥0

采用圖解法。如下圖：得Q點坐標（250，100）為最優解。100200300400500600100200300400600500x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200x1x2Q15整理課件§3圖解法的靈敏度分析線性規劃的標準化一般形式目標函數：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≥016整理課件§3圖解法的靈敏度分析

可以看出，線性規劃的標準形式有如下四個特點：目標最大化；約束為等式；決策變量均非負；右端項非負。對于各種非標準形式的線性規劃問題，我們總可以通過以下變換，將其轉化為標準形式:17整理課件§3圖解法的靈敏度分析1.極小化目標函數的問題：設目標函數為

minf=c1x1

+c2x2

+…+cnxn

(可以)令z

＝-f

，則該極小化問題與下面的極大化問題有相同的最優解，即maxz=-c1x1

-c2x2-…-cnxn

但必須注意，盡管以上兩個問題的最優解相同，但它們最優解的目標函數值卻相差一個符號，即

minf

＝-maxz18整理課件§3圖解法的靈敏度分析2、約束條件不是等式的問題：設約束條件為

ai1x1+ai2x2+…+ainxn

≤bi

可以引進一個新的變量s

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

s=bi–(ai1x1

+ai2x2

+…+ainxn

)顯然，s

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

ai1x1+ai2x2+…+ainxn+s=bi19整理課件§3圖解法的靈敏度分析

當約束條件為

ai1x1+ai2x2+

…

+ainxn

≥bi

時，類似地令

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

顯然，s

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

ai1x1+ai2x2+…+ainxn-s=bi20整理課件§3圖解法的靈敏度分析

為了使約束由不等式成為等式而引進的變量s,當不等式為“小于等于”時稱為“松弛變量”；當不等式為“大于等于”時稱為“剩余變量”。如果原問題中有若干個非等式約束，則將其轉化為標準形式時，必須對各個約束引進不同的松弛變量或剩余變量。3.右端項有負值的問題：

在標準形式中，要求右端項必須每一個分量非負。當某一個右端項系數為負時，如bi<0，則把該等式約束兩端同時乘以-1，得到：-ai1x1-ai2x2-…-ainxn

=-bi。21整理課件§3圖解法的靈敏度分析例：將以下線性規劃問題轉化為標準形式

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

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

x1+x2+x3=-9

x1,x2,x3

≥0

解：首先,將目標函數轉換成極大化：令z=-f=-2x1+3x2-4x3

其次考慮約束，有2個不等式約束，引進松弛變量或剩余變量x4，x5

≥0。第三個約束條件的右端值為負，在等式兩邊同時乘-1。22整理課件§3圖解法的靈敏度分析通過以上變換，可以得到以下標準形式的線性規劃問題：

maxz=-2x1

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

x1,x2,x3,x4,x5

≥0***變量無符號限制的問題***：

在標準形式中，必須每一個變量均有非負約束。當某一個變量xj沒有非負約束時，可以令xj=xj’-xj”

其中xj’≥0，xj”≥0

即用兩個非負變量之差來表示一個無符號限制的變量，當然xj的符號取決于xj’和xj”的大小。23整理課件§3圖解法的靈敏度分析

靈敏度分析：建立數學模型和求得最優解后，研究線性規劃的一個或多個參數（系數）ci,aij,bj

變化時，對最優解產生的影響。3.1目標函數中的系數ci

的靈敏度分析考慮例1的情況，ci的變化只影響目標函數等值線的斜率，目標函數z=50x1+100x2

在z=x2(x2=z斜率為0

)

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

)之間時，原最優解x1=50，x2=100仍是最優解。一般情況：

z=c1x1+c2x2

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

目標函數等值線的斜率為-(c1/c2)，當-1-(c1/c2)0（*）時，原最優解仍是最優解。24整理課件§3圖解法的靈敏度分析假設產品Ⅱ的利潤100元不變，即c2=100，代到式（*）并整理得

0c1

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

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

-2-(60/55)

-1

那么，最優解為