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

1、數(shù)學(xué)規(guī)劃第二章-線性規(guī)劃數(shù)學(xué)規(guī)劃第二章-線性規(guī)劃本章主要內(nèi)容線性規(guī)劃問題的標(biāo)準(zhǔn)型基本解和基本可行解線性規(guī)劃的基本定理基本可行解與極點(diǎn)的關(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ì)：在頂點(diǎn)達(dá)到極值，通過代數(shù)方法，描述高維空間中多面體的頂點(diǎn)，然后，進(jìn)一步求出達(dá)到極值的頂點(diǎn)。線性規(guī)劃問題的雛形考慮問題：x1x2CBADX0=5X0=0其中，f（x）、hi（x）和gp（x）為En內(nèi)的實(shí)函數(shù)。目標(biāo)函數(shù)約束函數(shù)當(dāng)目標(biāo)函數(shù)與約束函

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

3、4資源限制b1b2b3b41.1求：使預(yù)測(cè)利潤(rùn)最大的方案。解：設(shè)甲、乙、丙、丁四種產(chǎn)品的產(chǎn)量分別為x1,x2,x3和x例1.2 某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分別要在A、B、C、D、四種不同的設(shè)備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺(tái)時(shí)如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使企業(yè)總的利潤(rùn)最大？ 設(shè) 備產(chǎn) 品 A B C D利潤(rùn)（元） 甲 2 1 4 0 2 乙 2 2 0 4 3 有 效 臺(tái) 時(shí) 12 8 16 12例1.2 某企業(yè)計(jì)劃生產(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 某沖積平原有四個(gè)供水井，擬取砂石承壓含水層地下水作供水之用，設(shè)四個(gè)井的允許降深分別為15，18，17，20米，問各井抽水量為多少，才能使總開采量最大？ 解：設(shè)各抽水井的抽水量分別為x1，x2，x3，x4，四個(gè)井同時(shí)工作，相互間產(chǎn)生水位干擾，根據(jù)線性疊加原理，流場(chǎng)內(nèi)任一點(diǎn)，水位降深等于各井抽水對(duì)該點(diǎn)降深之和。設(shè)aij代表第j井單位抽水量在i井處產(chǎn)生的降深，則四個(gè)井的降深分別為： ， ， ，依題意

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

6、題的標(biāo)準(zhǔn)型1. 線性規(guī)劃的數(shù)學(xué)模型由三個(gè)要目標(biāo)函數(shù)：約束條件：2. 線性規(guī)劃數(shù)學(xué)模型的一般形式簡(jiǎn)寫為：目標(biāo)函數(shù)：約束條件：2. 線性規(guī)劃數(shù)學(xué)模型的一般形式簡(jiǎn)寫為：向量形式：其中：向量形式：其中：矩陣形式：其中：矩陣形式：其中：3. 線性規(guī)劃問題的標(biāo)準(zhǔn)形式特點(diǎn)：(1) 目標(biāo)函數(shù)求最大值（有時(shí)求最小值）(2) 約束條件都為等式方程，且右端常數(shù)項(xiàng)bi都大于或等于零(3) 決策變量xj為非負(fù)。3. 線性規(guī)劃問題的標(biāo)準(zhǔn)形式特點(diǎ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) 第一個(gè)約束條件是“”號(hào)，在“”左端加入松馳變量x4，x40,化為等式；(3) 第二個(gè)約束條件是“”號(hào)，在“”左端減去剩余變量x5，x50；(4) 第3個(gè)約束方程右端常數(shù)項(xiàng)為-5，方程兩邊同乘以(-1)，將右端常數(shù)項(xiàng)化為正數(shù)； (5) 目標(biāo)函數(shù)是最小值，為了化為求最大值，令z=-z,得到max z=-z，即當(dāng)z

8、達(dá)到最小值時(shí)z達(dá)到最大值，反之亦然;解:（）因?yàn)閤3無符號(hào)要求 ，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以用 替換 ，且 (2) 第一個(gè)約束條件是“”號(hào)，在“”左端加入松馳變量x標(biāo)準(zhǔn)形式如下：標(biāo)準(zhǔn)形式如下：線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組中找出一個(gè)解，使目標(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ī)劃問題的一個(gè)基。設(shè)：稱 B中每個(gè)列向量Pj ( j = 1 2 m) 為基向量。與基向量Pj 對(duì)應(yīng)的變量xj 為基變量。除基變量以外的變量為非基變量。 可行解：滿足約束條件、的解為可行解。所有可行解的集合 基解：某一確定的基B，令非基變量等于零，由約束條件方程解出基變量，稱這組解為基解。在基解中變量取非0值的個(gè)數(shù)不大于方程數(shù)m，基解的總數(shù)不超過 基可行解：滿足變量非負(fù)約束條件的基本解，簡(jiǎn)稱基可行解。 可行基：對(duì)應(yīng)于基可行解的基稱為可行基。非可行解可行解基解基可行解 基解：某一確定的基B，令非基變量等于零，由約束條件方程對(duì)于有n個(gè)變量、m個(gè)等式約束的線性規(guī)劃問題，基本解的個(gè)數(shù)最

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

11、何意義等優(yōu)點(diǎn)。2.4 基本可行解與極點(diǎn)的關(guān)系圖解法線性規(guī)劃問題的求解方法一 般 有圖 解 法兩個(gè)變量、直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此點(diǎn)是唯一最優(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、有點(diǎn)都是最優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值max Z=34.2是唯一的?？尚杏驁D解法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）可行域此點(diǎn)是唯一最優(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í)要點(diǎn)：1. 通過圖解法了解線性規(guī)劃有幾種解的形式（唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解）2. 作圖的關(guān)鍵有三點(diǎn)： (1) 可行解區(qū)域要畫正確 (2) 目標(biāo)函數(shù)增加的方向不能畫錯(cuò) (3) 目標(biāo)函數(shù)的直線怎樣平行移動(dòng)圖解法學(xué)習(xí)要點(diǎn)：相關(guān)定理與推論相關(guān)定理與推論本章小結(jié)1、線性規(guī)劃的標(biāo)準(zhǔn)型2、線性規(guī)劃的基本解和基本可行解3、線性規(guī)劃的常用求解方法圖解法本章小結(jié)1、線性規(guī)劃的標(biāo)準(zhǔn)型作業(yè)靠近某河流有兩個(gè)化工廠，流經(jīng)第一化工廠的河流流量為每天500萬m3，在兩個(gè)工廠之間有一條流量為每天200萬m3的支流。第一化工廠每天排放含有某種有害物質(zhì)的工業(yè)污水2萬m3，第二天化工廠每天