管理運籌學-線性規(guī)劃的圖解法-課件

第二章線性規(guī)劃的圖解法一、線性規(guī)劃問題及其數學模型

在生產管理和經營活動中經常需要解決：如何合理地利用有限的資源，以得到最大的效益。11ppt課件

例1.1

某工廠可生產甲、乙兩種產品，需消耗煤、電、油三種資源?，F將有關數據列表如下：

試擬訂使總收入最大的生產方案。資源產品資源單耗甲乙資源限量煤電油9445310360200300單位產品價格71221ppt課件解：設安排甲、乙產量分別為,總收入為，則模型為：31ppt課件目標函數：總收入，記為z,則，為體現

對其追求極大化，在z的前面冠以極大號Max；決策變量：甲、乙產品的計劃產量，記為；約束條件：分別來自資源煤、電、油限量的約束，和產量非負的約束，表示為41ppt課件

線性規(guī)劃模型的三要素3.約束條件：為實現優(yōu)化目標需受到的限制，用決策變量的等式或不等式表示。1.決策變量：需決策的量，即待求的未知數；2.目標函數：需優(yōu)化的量，即欲達的目標，用決策變量的表達式表示；51ppt課件線性規(guī)劃模型的一般形式：（以MAX型、約束為例）決策變量：目標函數：約束條件：61ppt課件則模型可表示為模型一般式的矩陣形式記71ppt課件回顧例1.1的模型其中表示決策變量的向量；表示產品的價格向量；表示資源限制向量；表示產品對資源的單耗系數矩陣。81ppt課件一般地

其中稱為決策變量向量，稱為價格系數向量,

稱為技術系數矩陣,稱為資源限制向量。問題：為什么A稱為技術系數矩陣？91ppt課件二、線性規(guī)劃模型的圖解法圖解法是用畫圖的方式求解線性規(guī)劃的一種方法。它雖然只能用于解二維（兩個變量）的問題，但其主要作用并不在于求解，而是在于能夠直觀地說明線性規(guī)劃解的一些重要性質。101ppt課件例1

用圖解法求解線性規(guī)劃問題maxZ=50X1+100X2

X1+X2≤3002X1+X2≤400s.t.X2≤250X1，X2≥0111ppt課件（1）分別取決策變量X1，X2

為坐標向量建立直角坐標系。在直角坐標系里，圖上任意一點的坐標代表了決策變量的一組值，例1的每個約束條件都代表一個半平面。x2x1X2≥0X2=0x2x1X1≥0X1=0121ppt課件13（2）對每個不等式（約束條件），先取其等式在坐標系中作直線，然后確定不等式所決定的半平面。X1+X2≤300X1+X2=3001001002002X1+X2≤4002X1+X2=400300200300400100200300x1x1100200300x2x2131ppt課件14（3）把五個圖合并成一個圖，取各約束條件的公共部分，如圖2-1所示。100100X2≤250X2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2-1x1x2141ppt課件（4）目標函數Z=50X1+100X2，當Z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標函數值，稱之為“等值線”。平行移動等值線，當移動到B點時，z在可行域內實現了最大化。A，B，C，D，E是可行域的頂點，對有限個約束條件則其可行域的頂點也是有限的。x1x2z=20000=50x1+100x2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE由圖可知：頂點B為最優(yōu)解。X1=50,X2=250Z=50x50+250x100=27500151ppt課件（1）做約束的圖形

先做非負約束的圖形；再做資源約束的圖形。

以例1.1為例，其約束為

各約束的公共部分即模型的約束，稱可行域。1.圖解法的步驟161ppt課件(2)做目標的圖形做出相應的二直線，便可看出增大的方向。對于目標函數便可做出相應的二組任給Z不同的值，形成二直線，用虛線表示。以例1.1為例，其目標為分別令171ppt課件（3）求出最優(yōu)解將目標直線向使目標優(yōu)化的方向移，直至可行域的邊界為止，這時其與可行域的“切”點即最優(yōu)解。

如在例1.1中，是可行域的一個角點，

經求解交出的二約束直線聯(lián)立的方程可解得181ppt課件

由圖解法的結果得到例1.1的最優(yōu)解還可將其代入目標函數求得相應的最優(yōu)目標值。說明當甲產量安排20個單位，乙產量安排24個單位時，可獲得最大的收入428。191ppt課件2.由圖解法得到線性規(guī)劃解的一些特性（1）線性規(guī)劃的約束集（即可行域）是一個凸多面體。

凸多面體:把多面體的任何一個面伸展成平面，如果所有其他各面都在這個平面的同側，這樣的多面體就叫做凸多面體。凸多面體的任何截面都是凸多邊形。201ppt課件（2）線性規(guī)劃的最優(yōu)解（若存在的話）必能在可行域的角點（頂點）獲得。

因為，由圖解法可知，只有當目標直線平移到邊界時，才能使目標z達到最大限度的優(yōu)化。問題：本性質有何重要意義？211ppt課件本性質重要意義：

這樣，問題就轉化為從有限多個角點中尋找最優(yōu)點，使原來從所有可行解中去尋找最優(yōu)解的工作大大簡化。線性規(guī)劃的單純形解法的依據就是這兩個性質。221ppt課件（3）線性規(guī)劃解的幾種情形①

唯一最優(yōu)解②

多重最優(yōu)解③

無解④

無有限最優(yōu)解（無界解）231ppt課件

重要結論：如果線性規(guī)劃有最優(yōu)解，則一定有一個可行域的頂點對應一個最優(yōu)解；無窮多個最優(yōu)解。無界解。即可行域的范圍延伸到無窮遠，目標函數值可以無窮大或無窮小。一般來說，這說明模型有錯，忽略了一些必要的約束條件；無可行解。則可行域為空域，不存在滿足約束條件的解，當然也就不存在最優(yōu)解了。241ppt課件

小結線性規(guī)劃LP(linearprogramming)的定義：

LP是在有限資源的條件下，合理分配和利用資源，以期取得最佳的經濟效益的優(yōu)化方法。

LP有一組決策變量，一個目標函數，一組約束條件，目標函數和約束方程都是線性的。251ppt課件重要性：

要想在工農業(yè)生產、交通運輸、商業(yè)貿易等各方面提高效益，有兩種途徑：一是革新技術，二是改進生產組織與計劃，即合理安排有限的人力和物力資源，最合理地組織生產過程。

數學規(guī)劃能夠為更好地配置資源、組織生產提供理論與方法，包括線性規(guī)劃、非線性規(guī)劃、整數規(guī)劃、多目標規(guī)劃等很多分支。

其中線性規(guī)劃是在現代管理中運用最廣、理論比較完善的一個部分。隨著電子計算機的發(fā)展，數學規(guī)劃在現代管理中的重要性日益明顯。

261ppt課件線性規(guī)劃的標準化內容之一：——引入松馳變量（含義是資源的剩余量）例1.1中引入s1，s2，s3模型化為目標函數：Maxz=7x1+12x2+0s1+0s2+0s3

約束條件：9x1+4x2+s1=3604x1+5x2+s2=200s.t.3x1+10x2+s3=

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

對于最優(yōu)解

x1=20x2=24，s1=84s2=0s3=0

說明：生產20單位甲產品和24單位乙產品將消耗完所有可能的電和油，但對煤則還剩余84個單位。271ppt課件線性規(guī)劃的標準化一般形式目標函數：Max（Min）z=c1x1+c2x2+…+cnxn

約束條件：a11x1+a12x2+…+a1nxn

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2

s.t.…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn≥0標準形式目標函數：Maxz=c1x1+c2x2+…+cnxn

約束條件：a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2s.t.…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0，bi≥0281ppt課件可以看出，線性規(guī)劃的標準形式有如下四個特點：目標最大化；約束為等式；決策變量均非負；右端項非負。對于各種非標準形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉化為標準形式:291ppt課件1.極小化目標函數的問題：設目標函數為

Minf=c1x1

+c2x2

+…+cnxn

(可以)令z

＝-f

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

-c2x2-…-cnxn

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

Minf

＝-Maxz301ppt課件2.約束條件不是等式的問題：設約束條件為

ai1x1+ai2x2+…+ain

xn

≤bi

可以引進一個新的變量s

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

s=bi–(ai1x1

+ai2x2

+…+ain

xn

)顯然，s

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

ai1x1+ai2x2+…+ain

xn+s=bi311ppt課件當約束條件為

ai1x1+ai2x2+

…

+ain

xn

≥bi

時，類似地令

s=(ai1x1+ai2x2+…+ain

xn)-bi

顯然，s

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

ai1x1+ai2x2+…+ain

xn-s=bi321ppt課件為了使約束由不等式成為等式而引進的變量s，當不等式為“小于等于”時稱為“松弛變量”；當不等式為“大于等于”時稱為“剩余變量”。如果原問題中有若干個非等式約束，則將其轉化為標準形式時，必須對各個約束引進不同的松弛變量。3.右端項有負值的問題：在標準形式中，要求右端項必須每一個分量非負。當某一個右端項系數為負時，如bi<0，則把該等式約束兩端同時乘以-1，得到：331ppt課件例：將以下線性規(guī)劃問題轉化為標準形式

Minf=2x1-3x2+4x33x1

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

s.t.x1+x2+x3=-9

x1,x2,x3

≥0

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

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

x4，x5

≥0。第三個約束條件的右端值為負，在等式兩邊同時乘-1。341ppt課件通過以上變換，可以得到以下標準形式的線性規(guī)劃問題：

Maxz=-2x1

+3x2-4x33x1+4x2-5x3+x4=6

s.t.2x1+x3-x5=8-x1-x2-x3=9

x1,x2,x3,x4,x5

≥0***4.變量無符號限制的問題***：在標準形式中，必須每一個變量均有非負約束。當某一個變量xj沒有非負約束時，可以令

xj

=

xj’-

xj”

其中

xj’≥0，xj”≥0

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

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

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

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

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

)

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

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

z=c1x1+c2x2

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

目標函數等值線的斜率為-(c1/c2)，當-1-(c1/c2)0（*）時，原最優(yōu)解仍是最優(yōu)解。361ppt課件假設產品Ⅱ的利潤100元不變，即c2=100，代到式（*）并整理得

0c1

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

50c2

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

-2-(60/55)

-1

那么，最優(yōu)解為

z=x1+x2

和

z=2x