衛(wèi)生管理運籌學課件-線性規(guī)劃

第一節(jié) 基本概念第二節(jié) 線性規(guī)劃問題的圖解法第三節(jié) 線性規(guī)劃模型的解及性質第四節(jié)

單純形法第五節(jié) 對偶規(guī)劃第六節(jié) 運輸問題及表上作業(yè)法線性規(guī)劃第二節(jié) 線性規(guī)劃問題的圖解法—

、圖解法解極大化問題二、圖解法求解極小化問題三、

線性規(guī)劃模型的解的各種情況四、

解法的優(yōu)點及局限性—

、用圖解法解極大化問題例1．MaxZ

＝

60x

＋50y2x

＋

4y

≤803x

＋

2y

≤60x,

y

≥

01．圖示全部約束條件，確定可行解區(qū)域(1)以x、y作為坐標軸，建立平面直角坐標系，根據(jù)x、y非負的約束，可行解區(qū)域位于坐標圖的第一象限（見圖（a））（2）用等式約束代替非等式約束，畫出直線

2x＋4y＝80和3x＋2y＝60（見圖（b））從可行解中找出 最優(yōu)解等直線法試算法（

1）等直線法：把目標函數(shù)Z＝60x＋50y

看成是隨著Z的取值不同而產(chǎn)生的一族直線。令目標函數(shù)值分別為0、600、1200作平行線族（見圖（2））.從圖中可見，Z值越高，目標函數(shù)直線離原點越遠。所以，尋找最優(yōu)解問題可歸結為：找出離原點最遠的一條直線與可行解集的交點。（2）試算法：*

試算法是根據(jù)下面線性規(guī)劃解的性質而得出的一種算法：線性規(guī)劃的可行域是凸多邊形或凸集；線性規(guī)劃的最優(yōu)解如果存在，必然在可行解集的某個頂點上達到。*

根據(jù)線性規(guī)劃解的性質，先求出可行解集各頂點的坐標，然后試算目標函數(shù)之值，使目標函數(shù)達到極值的解，即為最優(yōu)解（見下面表1－3）表1－3

例1試算結果目標函數(shù)可行解集 頂點的坐標頂點目標函數(shù)之值Ｏ0Ａ1200Ｂ1350(最優(yōu)解)*1000最優(yōu)解為（x，y）＝（10，15）最優(yōu)值為ZMax

＝

1350返回二、圖解法求解極小化問題例２MinZ

＝

50x

＋80y4x

+10y

≥4010x

＋

5y

≥

5035x

+

35y

≥

245x，

y

≥

0解：1、圖示全部約束條件，確定可行解區(qū)域2．可行解中找出最優(yōu)解用等直線法求最優(yōu)解。本例是極小值問題，因此目標函數(shù)值應該取離原點盡可能近的等直線的值（見圖（4））。通過p2點的等直線離原點最近，p2點的坐標既滿足全部約束條件又能使目標函數(shù)取得最小值，故為最優(yōu)解。用試算法求最優(yōu)解（見表1－4）表1-4

例2試算結果目標函數(shù)頂點的坐標可行解集頂

點Ｐ1目標函數(shù)之

值500Ｐ2410(最優(yōu)解)Ｐ3470800Ｐ4最優(yōu)解為（x，y）＝（5，2）最優(yōu)值為ZMin

＝410返回三、線性規(guī)劃模型的解的各種情況例3解：在本例中，由于目標函數(shù)（Z＝2x＋4y）的等直線與約束條件（x＋2y

≤8）的直線相平行，故最優(yōu)解同時在兩個頂點上達到。則在此兩頂點連線上的任何一點都是最優(yōu)解，即有無限多個最優(yōu)解。解：從圖（6）可見，本例的可行域無上界，目標函數(shù)的值可趨于無窮大。在這種情況下無法確定最優(yōu)解。例4解：從圖（7）可以看出，本題的可行域是一個空集，因此，無可行解。這是由于本題中包括了相互矛盾的約束條件的緣故。例5線性規(guī)劃問題解的幾種情況有唯一的最優(yōu)解。這時最優(yōu)解一定在可行域的某個頂點達到；有最優(yōu)解，但不唯一。這時最優(yōu)解一定充滿一個線段，此線段是可行域的一條邊；有可行解，但沒有最優(yōu)解。這時可行域上的點能使目標函數(shù)趨向無窮大；沒有可行解（空集）。即線性規(guī)劃問題是不可行的。返回圖解法的優(yōu)點及局限性圖解法的優(yōu)點：直觀、形象，它容易使人具體地認識線性規(guī)劃模型的求解過程。圖解法的局限性：一般僅適用于只有兩個變量的。對于三維以上的模型，約束條件表現(xiàn)為平面，這就難用圖解法去求解了。返回第三節(jié) 線性規(guī)劃模型的解及有關概念一、線性規(guī)劃問題的標準型二、線性規(guī)劃模型的解（性質略，見P15）線性規(guī)劃的標準形有如下四個特點：目標最大化、變量均非負、約束為等式、右端項非負。一、線性規(guī)劃問題的標準型返回二、線性規(guī)劃模型的解（1－2）（1－3）（1－4）我們把滿足約束條件（1-3）、（1-4）的解稱為線性規(guī)劃模型的可行解。當m＜n時，約束方程組（1-3）可以有無窮多個解。全部可行解的集合，稱為可行域。線性規(guī)劃模型的最優(yōu)解，就是指能滿足（1-2），即能使目標函數(shù)達到最大值的可行解。1．線性規(guī)劃的解2．線性規(guī)劃標準形式的基、基本解、基本可行解我們稱這個解為基本解，若這個解能同時滿足線性規(guī)劃模型的非負約束條件，則把這個基本解稱為基本可行解。基基變量非基變量稱變量

在約束方程組對應的系數(shù)列向量為線性規(guī)劃模型的一個基。基對應的變量稱為基變量，其它變量稱為非基變量。即：任取A中的3個線性無關列向量構成矩陣B，那么B為線性規(guī)劃的一個基。如果B為單位矩陣，則稱B為一個單位基。線性規(guī)劃的任一個基，總可以通過線性方程

組的變換化成單位基。基基變量非基變量一般形式：（1）線性規(guī)劃的基、基變量對于線性規(guī)劃的約束條件系數(shù)矩陣A,設B是A矩陣中的一個非奇異（可逆）的子矩陣，則稱B為線性規(guī)劃的一個基。任取A中的m個線性無關列向量構成矩陣B，那么B為線性規(guī)劃的一個基。如果B為單位矩陣，則稱B為一個單位基。稱對應于基B的變量為基變量，而其它變量稱為非基變量。（2）基本解、基本可行解和可行基對于線性規(guī)劃問題，設矩陣B為一個基，令所有非基變量為零，可以得到m個關于基變量的線性方程，解這個線性方程組得到基變量的值。我們稱這個解為一個基本解。若得到的基變量的值均非負，則稱為基本可行解，同時稱這個基B為可行基。上面線性規(guī)劃約束方程組（*）的一個單位基為B，對應的基變量為，非基變量為。令所有非基變量為零，解線性方程組（*）得到基變量的值我們稱解為一個基本可行解，同時稱基B為可行基。＃返回本次課小結第二節(jié)線性規(guī)劃問題的圖解法1.兩個變量的線性規(guī)劃問題的圖解法步驟第一步建立平面直角坐標系第二步求滿足約束條件的可行解區(qū)域第三步作目標函數(shù)的等值線簇，確定目標函數(shù)值增加方向（或用等值線法）。第四步從可行解區(qū)內找滿足目標函數(shù)的最優(yōu)解。本次課小結2.

圖解法的優(yōu)點及局限性圖解法的優(yōu)點：直觀、形象，它容易使人具體地認識線性規(guī)劃模型的求解過程。圖解法的局限性：一般僅適用于只有兩個變量的。對于三維以上的模型，約束條件表現(xiàn)為平面，這

就難用圖解法去求解了。３．線性規(guī)劃問題解的幾種情況有唯一的最優(yōu)解；有最優(yōu)解，但不唯一；有可行解，但沒有最優(yōu)解；沒有可行解（空集）。第三節(jié) 線性規(guī)劃模型的解及有關概念一、線性規(guī)劃問題的標準型（四個特點）二、線性規(guī)劃模型的解及有關概念１．線性規(guī)劃模型的解的概念：可行解、可行域、最優(yōu)解、基本解、基本可行解。2．線性規(guī)劃標準形式的基的概念：基、單位基、可行基、基變量、非基變量。本次課小結練

習思考題建立線性規(guī)劃模型的三個步驟是什么?

(2)兩個變量的線性規(guī)劃問題的圖解法的一般步驟是什么?(3)求解線性規(guī)劃問題時可能出現(xiàn)幾種結果?

(4)什么是線性規(guī)劃的標準型?如何把一個非標準形式的線性規(guī)劃問題轉化成標準形式?(5)理解線性規(guī)劃問題的可行解、基本解、基本可行解、最優(yōu)解的概念。練

習判斷下列說法是否正確線性規(guī)劃問題的最優(yōu)解一定在可行域的頂點達到。線性規(guī)劃的可行解集是凸集。如果一個線性規(guī)劃問題有兩個不同的最優(yōu)解，則它有無窮多個最優(yōu)解。如果一