《數(shù)學(xué)規(guī)劃》第二章-線性規(guī)劃

1、數(shù)學(xué)規(guī)劃第二章-線性規(guī)劃數(shù)學(xué)規(guī)劃第二章-線性規(guī)劃本章主要內(nèi)容線性規(guī)劃問題的標(biāo)準(zhǔn)型基本解和基本可行解線性規(guī)劃的基本定理基本可行解與極點的關(guān)系（圖解法）本章主要內(nèi)容線性規(guī)劃問題的標(biāo)準(zhǔn)型線性規(guī)劃問題的雛形考慮問題：求 max x0=x1+3x2滿足條件：-x1+x21 x1+x2 2 （p） X1，x20 x1x2CBADX0=5X0=0線性規(guī)劃問題最基本的性質(zhì)：在頂點達(dá)到極值，通過代數(shù)方法，描述高維空間中多面體的頂點，然后，進(jìn)一步求出達(dá)到極值的頂點。線性規(guī)劃問題的雛形考慮問題：x1x2CBADX0=5X0=0其中，f（x）、hi（x）和gp（x）為En內(nèi)的實函數(shù)。目標(biāo)函數(shù)約束函數(shù)當(dāng)目標(biāo)函數(shù)與約束函

2、數(shù)均為線性函數(shù)時，則稱為線性規(guī)劃。線性規(guī)劃通常解決下列兩類問題：（1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源 （如資金、設(shè)備、原標(biāo)材料、人工、時間等）去完成確定的任務(wù)或目標(biāo)（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多 、利潤最大）其中，f（x）、hi（x）和gp（x）為En內(nèi)的實函數(shù)。目標(biāo)解：設(shè)甲、乙、丙、丁四種產(chǎn)品的產(chǎn)量分別為x1,x2,x3和x4，則上述問題可表示為線性規(guī)劃問題：產(chǎn)品臺時材料1材料2材料3每千克產(chǎn)品預(yù)測利潤甲a11a21a31a41c1乙a12a22a32a42c2丙a13a23a33a43c3丁a14a24a34a44c

3、4資源限制b1b2b3b41.1求：使預(yù)測利潤最大的方案。解：設(shè)甲、乙、丙、丁四種產(chǎn)品的產(chǎn)量分別為x1,x2,x3和x例1.2 某企業(yè)計劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分別要在A、B、C、D、四種不同的設(shè)備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺時如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計劃，使企業(yè)總的利潤最大？ 設(shè) 備產(chǎn) 品 A B C D利潤（元） 甲 2 1 4 0 2 乙 2 2 0 4 3 有 效 臺 時 12 8 16 12例1.2 某企業(yè)計劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分別要在解：設(shè)x1、x2分別為甲、乙兩種產(chǎn)品的產(chǎn)量，則 數(shù)學(xué)模型為：max Z = 2x1 + 3x

4、2 x1 0 , x2 0s.t. 2x1 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 12解：設(shè)x1、x2分別為甲、乙兩種產(chǎn)品的產(chǎn)量，則max Z 水資源系統(tǒng)中的線性規(guī)劃問題例1.3 某沖積平原有四個供水井，擬取砂石承壓含水層地下水作供水之用，設(shè)四個井的允許降深分別為15，18，17，20米，問各井抽水量為多少，才能使總開采量最大？ 解：設(shè)各抽水井的抽水量分別為x1，x2，x3，x4，四個井同時工作，相互間產(chǎn)生水位干擾，根據(jù)線性疊加原理，流場內(nèi)任一點，水位降深等于各井抽水對該點降深之和。設(shè)aij代表第j井單位抽水量在i井處產(chǎn)生的降深，則四個井的降深分別為： ， ， ，依題意

5、有：該問題的目標(biāo)是使開采量最大化，即：maxZ=x1+x2+x3+x4同時，各井的降深不能超過允許降深，即 約束條件為：顯然還應(yīng)有：x1，x2，x3，x40水資源系統(tǒng)中的線性規(guī)劃問題例1.3 某沖積平原有四個供水井，2.1 線性規(guī)劃問題的標(biāo)準(zhǔn)型1. 線性規(guī)劃的數(shù)學(xué)模型由三個要素構(gòu)成決策變量 Decision variables 目標(biāo)函數(shù) Objective function約束條件 Constraints其特征是：（1）問題的目標(biāo)函數(shù)是多個決策變量的線性函數(shù)，通常是求最大值或最小值；（2）問題的約束條件是一組多個決策變量的線性不等式或等式。 怎樣辨別一個模型是線性規(guī)劃模型？ 2.1 線性規(guī)劃問

6、題的標(biāo)準(zhǔn)型1. 線性規(guī)劃的數(shù)學(xué)模型由三個要目標(biāo)函數(shù)：約束條件：2. 線性規(guī)劃數(shù)學(xué)模型的一般形式簡寫為：目標(biāo)函數(shù)：約束條件：2. 線性規(guī)劃數(shù)學(xué)模型的一般形式簡寫為：向量形式：其中：向量形式：其中：矩陣形式：其中：矩陣形式：其中：3. 線性規(guī)劃問題的標(biāo)準(zhǔn)形式特點：(1) 目標(biāo)函數(shù)求最大值（有時求最小值）(2) 約束條件都為等式方程，且右端常數(shù)項bi都大于或等于零(3) 決策變量xj為非負(fù)。3. 線性規(guī)劃問題的標(biāo)準(zhǔn)形式特點：如何化標(biāo)準(zhǔn)形式？ 目標(biāo)函數(shù)的轉(zhuǎn)換 如果是求極小值即 ，則可將目標(biāo)函數(shù)乘以(-1)，可化為求極大值問題。也就是：令 ，可得到上式。即若存在取值無約束的變量 ，可令 其中： 變量的變

7、換如何化標(biāo)準(zhǔn)形式？ 目標(biāo)函數(shù)的轉(zhuǎn)換 如果是求極小值即 約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。稱為松弛變量稱為剩余變量 變量 的變換 可令 ，顯然 約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。稱為松弛變量稱為剩余變例1.4 將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式例1.4 將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式(2) 第一個約束條件是“”號，在“”左端加入松馳變量x4，x40,化為等式；(3) 第二個約束條件是“”號，在“”左端減去剩余變量x5，x50；(4) 第3個約束方程右端常數(shù)項為-5，方程兩邊同乘以(-1)，將右端常數(shù)項化為正數(shù)； (5) 目標(biāo)函數(shù)是最小值，為了化為求最大值，令z=-z,得到max z=-z，即當(dāng)z

8、達(dá)到最小值時z達(dá)到最大值，反之亦然;解:（）因為x3無符號要求 ，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以用 替換 ，且 (2) 第一個約束條件是“”號，在“”左端加入松馳變量x標(biāo)準(zhǔn)形式如下：標(biāo)準(zhǔn)形式如下：線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組中找出一個解，使目標(biāo)函數(shù)(1)達(dá)到最大值。2.2 基本解和基本可行解線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3 可行解：滿足約束條件、的解為可行解。所有可行解的集合為可行域。 最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。 基：設(shè)A為約束條件的mn階系數(shù)矩陣(mn)，其秩為m，B是矩陣A中m階滿秩子矩陣

9、（B0），稱B是規(guī)劃問題的一個基。設(shè)：稱 B中每個列向量Pj ( j = 1 2 m) 為基向量。與基向量Pj 對應(yīng)的變量xj 為基變量。除基變量以外的變量為非基變量。 可行解：滿足約束條件、的解為可行解。所有可行解的集合 基解：某一確定的基B，令非基變量等于零，由約束條件方程解出基變量，稱這組解為基解。在基解中變量取非0值的個數(shù)不大于方程數(shù)m，基解的總數(shù)不超過 基可行解：滿足變量非負(fù)約束條件的基本解，簡稱基可行解。 可行基：對應(yīng)于基可行解的基稱為可行基。非可行解可行解基解基可行解 基解：某一確定的基B，令非基變量等于零，由約束條件方程對于有n個變量、m個等式約束的線性規(guī)劃問題，基本解的個數(shù)最

10、多為：基本可行解的個數(shù)最多為：2.3 線性規(guī)劃的基本定理對于有n個變量、m個等式約束的線性規(guī)劃問題，基本解的個數(shù)最多例2. 2-1 求線性規(guī)劃問題的所有基矩陣解: 約束方程的系數(shù)矩陣為25矩陣 r(A)=2，2階子矩陣有10個，其中基矩陣只有9個，即例2. 2-1 求線性規(guī)劃問題的所有基矩陣解: 約束方程的系圖解法線性規(guī)劃問題的求解方法一 般 有兩種方法圖 解 法單純形法兩個變量、直角坐標(biāo)三個變量、立體坐標(biāo)適用于任意變量、但必需將一般形式變成標(biāo)準(zhǔn)形式下面我們分析一下簡單的情況 只有兩個決策變量的線性規(guī)劃問題，這時可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾

11、何意義等優(yōu)點。2.4 基本可行解與極點的關(guān)系圖解法線性規(guī)劃問題的求解方法一 般 有圖 解 法兩個變量、直max Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8s.t. X1 + 1.9X2 10.2 X1 - 1.9X2 -3.8 X1 ，X2 0例2.2-2 用圖解法求解線性規(guī)劃問題max Z = 2X1 + X2 例2.2-2 用圖解法圖解法x1x2oX1 - 1.9X2 = 3.8()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()4 = 2X1 + X2 20 = 2X1 + X2

12、17.2 = 2X1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）Dmax Zmin Z此點是唯一最優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值 max Z=17.2可行域max Z = 2X1 + X2圖解法x1x2oX1 - 1.9X2 = 3.8()X1 圖解法max Z=3X1+5.7X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()（7.6，2）DL0： 0=3X1+5.7X2 max Z（3.8，4）34.2 = 3X1+5.7X2 藍(lán)色線段上的所

13、有點都是最優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值max Z=34.2是唯一的。可行域圖解法max Z=3X1+5.7X2x1x2oX1 - 1.圖解法x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 + 1.9X2 = 10.2 ()DL0： 0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2 （0，2）可行域此點是唯一最優(yōu)解min Z=5X1+4X2圖解法x1x2oX1 - 1.9X2 = 3.8 ()X1246x1x2246無界解(無最優(yōu)解)max Z=x1+2x2例2.2-3x1+x2=4()x1+3x2

14、=6()3x1+x2=6() max Z min Z246x1x2246無界解(無最優(yōu)解)max Z=x1+2xx1x2O10203040102030405050無可行解(即無最優(yōu)解)max Z=3x1+4x2例2.2-4x1x2O10203040102030405050無可行解(圖解法學(xué)習(xí)要點：1. 通過圖解法了解線性規(guī)劃有幾種解的形式（唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解）2. 作圖的關(guān)鍵有三點： (1) 可行解區(qū)域要畫正確 (2) 目標(biāo)函數(shù)增加的方向不能畫錯 (3) 目標(biāo)函數(shù)的直線怎樣平行移動圖解法學(xué)習(xí)要點：相關(guān)定理與推論相關(guān)定理與推論本章小結(jié)1、線性規(guī)劃的標(biāo)準(zhǔn)型2、線性規(guī)劃的基本解和基本可行解3、線性規(guī)劃的常用求解方法圖解法本章小結(jié)1、線性規(guī)劃的標(biāo)準(zhǔn)型作業(yè)靠近某河流有兩個化工廠，流經(jīng)第一化工廠的河流流量為每天500萬m3，在兩個工廠之間有一條流量為每天200萬m3的支流。第一化工廠每天排放含有某種有害物質(zhì)的工業(yè)污水2萬m3，第二天化工廠每天