1、此組片的內(nèi)容講三節(jié)課,*第一節(jié)基本概念 *第二節(jié) 線性規(guī)劃問(wèn)題的圖解法 *第三節(jié) 線性規(guī)劃模型的解及性質(zhì) *第四節(jié) 單純形法 第五節(jié) 對(duì)偶規(guī)劃 第六節(jié) 運(yùn)輸問(wèn)題及表上作業(yè)法,第一章線性規(guī)劃,第二節(jié) 線性規(guī)劃問(wèn)題的圖解法,一 、圖解法解極大化問(wèn)題 二、 圖解法求解極小化問(wèn)題 三、 線性規(guī)劃模型的解的各種情況 四、 解法的優(yōu)點(diǎn)及局限性,一 、用圖解法解極大化問(wèn)題,例1MaxZ 60 x 50y 2x 4y 80 3x 2y 60 x, y 0,(1)以x、y作為坐標(biāo)軸，建立平面直角坐標(biāo)系，根據(jù)x、y非負(fù)的約束，可行解區(qū)域位于坐標(biāo)圖的第一象限（見(jiàn)圖（a）,1圖示全部約束條件， 確定可行解區(qū)域,（2）

2、用等式約束代替非 等式約束，畫(huà)出直線 2x4y80 和 3x2y60 （見(jiàn)圖（b）,2從可行解中找出 最優(yōu)解,（1）等直線法 （2）試算法,（ 1）等直線法：把目標(biāo)函數(shù) Z60 x50y 看成是隨著Z的取值不同而產(chǎn)生的一族直線。令目標(biāo)函數(shù)值分別為0、600、1200作平行線族（見(jiàn)圖（2）.,從圖中可見(jiàn)，Z值越高，目標(biāo)函數(shù)直線離原點(diǎn)越遠(yuǎn)。所以，尋找最優(yōu)解問(wèn)題可歸結(jié)為：找出離原點(diǎn)最遠(yuǎn)的一條直線與可行解集的交點(diǎn)。,（2）試算法：,（a）線性規(guī)劃的可行域是凸多邊形或凸集； （b）線性規(guī)劃的最優(yōu)解如果存在，必然在 可行解集的某個(gè)頂點(diǎn)上達(dá)到。,* 試算法是根據(jù)下面線性規(guī)劃解的性質(zhì)而得出的一種算法：,* 根

3、據(jù)線性規(guī)劃解的性質(zhì)，先求出可行解集各頂點(diǎn)的坐標(biāo)，然后試算目標(biāo)函數(shù)之值，使目標(biāo)函數(shù)達(dá)到極值的解，即為最優(yōu)解,（見(jiàn)下面表13）,表13 例1試算結(jié)果,最優(yōu)解為（x，y）（10，15）最優(yōu)值為 ZMax 1350,返回,二、 圖解法求解極小化問(wèn)題,例 MinZ 50 x 80y 4x + 10y 40 10 x 5y 50 35x + 35y 245 x， y 0,解： 1、圖示全部約束條件， 確定可行解區(qū)域,2可行解中找出最優(yōu)解 （1）用等直線法求最優(yōu)解。本例是極小值問(wèn)題，因此目標(biāo)函數(shù)值應(yīng)該取離原點(diǎn)盡可能近的等直線的值（見(jiàn)圖（4）。通過(guò)p2點(diǎn)的等直線離原點(diǎn)最近， p2點(diǎn)的坐標(biāo)既滿足全部約束條件又能

4、使目標(biāo)函數(shù)取得最小值，故為最優(yōu)解。,（2）用試算法求最優(yōu)解（見(jiàn)表14）,表1-4 例2試算結(jié)果,最優(yōu)解為（x，y）（5，2）最優(yōu)值為 ZMin 410,返回,三、線性規(guī)劃模型的解的各種情況,例3,解：在本例中，由于目標(biāo)函數(shù)（Z2x4y）的等直線與約束條件（x2y 8）的直線相平行，故最優(yōu)解同時(shí)在兩個(gè)頂點(diǎn)上達(dá)到。則在此兩頂點(diǎn)連線上的任何一點(diǎn)都是最優(yōu)解，即有無(wú)限多個(gè)最優(yōu)解。,從圖（6）可見(jiàn)，本例的可行域無(wú)上界，目標(biāo)函數(shù)的值可趨于無(wú)窮大。在這種情況下無(wú)法確定最優(yōu)解。,解：,例4,從圖（7）可以看出，本題的可行域是一個(gè)空集，因此，無(wú)可行解。這是由于本題中包括了相互矛盾的約束條件的緣故。,解：,例5,線

5、性規(guī)劃問(wèn)題解的幾種情況,（1）有唯一的最優(yōu)解。這時(shí)最優(yōu)解一定在可行域的某個(gè)頂點(diǎn)達(dá)到； （2）有最優(yōu)解，但不唯一。這時(shí)最優(yōu)解一定充滿一個(gè)線段，此線段是可行域的一條邊； （3）有可行解，但沒(méi)有最優(yōu)解。這時(shí)可行域上的點(diǎn)能使目標(biāo)函數(shù)趨向無(wú)窮大； （4）沒(méi)有可行解（空集）。即線性規(guī)劃問(wèn)題是不可行的。,返回,圖解法的優(yōu)點(diǎn)及局限性,圖解法的優(yōu)點(diǎn)：直觀、形象，它容易使人具體地認(rèn)識(shí)線性規(guī)劃模型的求解過(guò)程。,圖解法的局限性：一般僅適用于只有兩個(gè)變量的。對(duì)于三維以上的模型，約束條件表現(xiàn)為平面，這就難用圖解法去求解了。,返回,第三節(jié) 線性規(guī)劃模型的解及有關(guān)概念,一、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型 二、線性規(guī)劃模型的解 （性質(zhì)略

6、，見(jiàn)P16）,線性規(guī)劃的標(biāo)準(zhǔn)形有如下四個(gè)特點(diǎn)： 目標(biāo)最大化、 約束為等式、 變量均非負(fù)、 右端項(xiàng)非負(fù)。,一、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型,返回,二、線性規(guī)劃模型的解,我們把滿足約束條件（1-3）、（1-4）的解稱為線性規(guī)劃模型的可行解。當(dāng)mn時(shí)，約束方程組（1-3）可以有無(wú)窮多個(gè)解。全部可行解的集合，稱為可行域。 線性規(guī)劃模型的最優(yōu)解，就是指能滿足（1-2），即能使目標(biāo)函數(shù)達(dá)到最大值的可行解。,1線性規(guī)劃的解,2線性規(guī)劃標(biāo)準(zhǔn)形式的基、基本解、基本可行解,我們稱這個(gè)解為基本解，若這個(gè)解能同時(shí)滿足線性規(guī)劃模型的非負(fù)約束條件，則把這個(gè)基本解稱為基本可行解。,任取A中的3個(gè)線性無(wú)關(guān)列向量構(gòu)成矩陣B，那么B為線

7、性規(guī)劃的一個(gè)基。如果B為單位矩陣，則稱B為一個(gè)單位基。 線性規(guī)劃的任一個(gè)基， 總可以通過(guò)線性方程 組的變換化成單位基。,一般形式：,對(duì)于線性規(guī)劃的約束條件系數(shù)矩陣A,設(shè)B是A矩陣中的一 個(gè)非奇異（可逆）的子矩陣，則稱B為線性規(guī)劃的一個(gè)基。 任取A中的m個(gè)線性無(wú)關(guān)列向量構(gòu)成矩陣B，那么B為線性規(guī) 劃的一個(gè)基。如果B為單位矩陣，則稱B為一個(gè)單位基。 稱對(duì)應(yīng)于基B的變量為基變量，而其它變量稱為非基變量。,（1） 線性規(guī)劃的基、基變量,（2） 基本解、基本可行解和可行基,對(duì)于線性規(guī)劃問(wèn)題，設(shè)矩陣B為一個(gè)基，令所有非基變量為零，可以得到m個(gè)關(guān)于基變量的線性方程，解這個(gè)線性方程組得到基變量的值。我們稱這個(gè)

8、解為一個(gè)基本解。若得到的基變量的值均非負(fù)，則稱為基本可行解，同時(shí)稱這個(gè)基B為可行基。,返回,第一步 建立平面直角坐標(biāo)系 第二步 求滿足約束條件的可行解區(qū)域 第三步 作目標(biāo)函數(shù)的等值線簇，確定 目標(biāo)函數(shù)值增加方向（或用等 值線法）。 第四步 從可行解區(qū)內(nèi)找滿足目標(biāo)函數(shù) 的最優(yōu)解。,1.兩個(gè)變量的線性規(guī)劃問(wèn)題的圖解法步驟,本次課小結(jié),第二節(jié) 線性規(guī)劃問(wèn)題的圖解法,2. 圖解法的優(yōu)點(diǎn)及局限性,圖解法的優(yōu)點(diǎn)：直觀、形象，它容易使人具體地認(rèn)識(shí)線性規(guī)劃模型的求解過(guò)程。,線性規(guī)劃問(wèn)題解的幾種情況,圖解法的局限性：一般僅適用于只有兩個(gè)變量的。對(duì)于三維以上的模型，約束條件表現(xiàn)為平面，這就難用圖解法去求解了。,本

9、次課小結(jié),（1）有唯一的最優(yōu)解； （2）有最優(yōu)解，但不唯一； （3）有可行解，但沒(méi)有最優(yōu)解； （4）沒(méi)有可行解（空集）。,一、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型（四個(gè)特點(diǎn)） 二、線性規(guī)劃模型的解及有關(guān)概念,第三節(jié) 線性規(guī)劃模型的解及有關(guān)概念,線性規(guī)劃模型的解的概念： 可行解、可行域、最優(yōu)解、 基本解、基本可行解。,2線性規(guī)劃標(biāo)準(zhǔn)形式的基的概念： 基、單位基、可行基、 基變量、非基變量。,本次課小結(jié),練 習(xí),1思考題 (1)建立線性規(guī)劃模型的三個(gè)步驟是什么? (2)兩個(gè)變量的線性規(guī)劃問(wèn)題的圖解法的一般步驟是什么? (3)求解線性規(guī)劃問(wèn)題時(shí)可能出現(xiàn)幾種結(jié)果? (4)什么是線性規(guī)劃的標(biāo)準(zhǔn)型?如何把一個(gè)非標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題轉(zhuǎn)化成標(biāo)準(zhǔn)形式? (5)理解線性規(guī)劃問(wèn)題的可行解、基本解、基本可行解、最優(yōu)解的概念。,練 習(xí),2判斷下列說(shuō)法是否正確 (1)線性規(guī)劃問(wèn)題的最優(yōu)解一定在可行域的頂點(diǎn)達(dá)到。 (2)線性規(guī)劃的可行解集是凸集。 (3)如果一個(gè)線性規(guī)劃問(wèn)題有兩個(gè)不同的最優(yōu)解，則