劉舒燕：運(yùn)籌學(xué)-線性規(guī)劃基礎(chǔ)

1、運(yùn)運(yùn) 籌籌 學(xué)學(xué)劉舒燕劉舒燕武漢理工大學(xué)管理學(xué)院武漢理工大學(xué)管理學(xué)院第一部分第一部分 線性規(guī)劃線性規(guī)劃（Linear Programming，簡稱，簡稱LP）線性規(guī)劃的發(fā)展線性規(guī)劃的發(fā)展1939年，前蘇聯(lián)數(shù)學(xué)家康托洛維奇用線性模型研究提高組織和生產(chǎn)效率問題1947年，Dantzig提出求解線性規(guī)劃的單純形法1950-1956年，主要研究線性規(guī)劃的對偶理論1958年，發(fā)表整數(shù)規(guī)劃的割平面法1960年，Dantzig和Wolfe研究成功分解算法，奠定了大規(guī)模線性規(guī)劃問題理論 和算法的基礎(chǔ)。1979年，Khachiyan，1984年，Karmarka研究成功線性規(guī)劃的多項(xiàng)式算法。線性規(guī)劃研究的主要問

2、題線性規(guī)劃研究的主要問題 一類是已有一定數(shù)量的資源（人力、物質(zhì)、時(shí)間等），研究如何充分合理地使用它們，才能使完成的任務(wù)量為最大。 實(shí)際上，上述兩類問題是一個(gè)問題的兩個(gè)不同的方面，都是在給定實(shí)際上，上述兩類問題是一個(gè)問題的兩個(gè)不同的方面，都是在給定的一組約束條件下求問題的最優(yōu)解（的一組約束條件下求問題的最優(yōu)解（ max 或或 min ）。）。 另一類是當(dāng)一項(xiàng)任務(wù)確定以后，研究如何統(tǒng)籌安排，才能使完成任務(wù)所耗費(fèi)的資源量為最少。第一章第一章 線性規(guī)劃基礎(chǔ)線性規(guī)劃基礎(chǔ)例1.1 （生產(chǎn)計(jì)劃問題生產(chǎn)計(jì)劃問題）某廠生產(chǎn)兩種產(chǎn)品，下表給出了單位產(chǎn)品所需資源及單位產(chǎn)品利潤。問：應(yīng)如何安排生產(chǎn)計(jì)劃，才能使 總利潤

3、最大？ 1.1 線性規(guī)劃的基本概念線性規(guī)劃的基本概念一、問題的提出一、問題的提出解：解：1.決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量分 別為 x1、x22.目標(biāo)函數(shù)：設(shè)總利潤為z，則有： max z = 2 x1 + 3 x23.約束條件： x1 + 2x2 8 4x1 16 4x2 12 x1， x20例1.2 （配料問題配料問題）某廠生產(chǎn)三種藥物，這些藥物可以從四種不同的原料中提取。下表給出了單位原料可提取的藥物量：要求：生產(chǎn)A種藥物至少160單位；B種藥物恰好200單位，C種藥物不超過180單位，且使原料總成本最小。解：解：1.決策變量：設(shè)四種原料的使用 量分別為： x1、x2 、x3 、x42.

4、目標(biāo)函數(shù)：設(shè)總成本為z，則有： min z = 5 x1 + 6 x2 + 7 x3 + 8 x43.約束條件： x1 + 2x2 + x3 + x4 160 2x1 +4 x3 +2 x4 200 3x1 x2 +x3 +2 x4 180 x1、x2 、x3 、x40 藥物原料ABC單位成本（元噸）甲1235乙2016丙1417丁1228二、數(shù)學(xué)模型二、數(shù)學(xué)模型1.決策變量： X = (x1,x2,.,xn)T2.目標(biāo)函數(shù)：max (minz) = c1 x1 + c2 x2 + . + cnxn3.約束條件： a11x1 + a12 x2 +.+ a1n xn (=) b1 a21x1 +

5、 a22 x2 +.+ a2n xn (=) b2 am1x1 + am2 x2 +.+ amn xn (=) bm x1,x2,xn0三、模型特點(diǎn)三、模型特點(diǎn)1 都用一組決策變量X = (x1,x2,xn)T表示某一方案，且決策變量取值非負(fù)； 具有以上三個(gè)特征的數(shù)學(xué)模型稱為線性規(guī)劃具有以上三個(gè)特征的數(shù)學(xué)模型稱為線性規(guī)劃2 都有一個(gè)要達(dá)到的目標(biāo)，并且目標(biāo)要求可以表示成決策變量的線性函數(shù)； 根據(jù)目標(biāo)要求的不同，可以是求max，也可以是求min；3 都有一組約束條件，這些約束條件可以用決策變量的線性等式或線性不等 式來表示。其它形式其它形式),2, 1(0),2, 1(max(min)11njxm

6、ibxaxczjnjijijnjjj求和形式求和形式矩陣形式矩陣形式0 max(min)XbAXCXznxxxX21決策變量決策變量常數(shù)項(xiàng)常數(shù)項(xiàng)nbbbb21系數(shù)矩陣系數(shù)矩陣 nmijmnmmnnaaaaaaaaaaA212222111211價(jià)值系數(shù)價(jià)值系數(shù)ncccC21其中其中：1.2 線性規(guī)劃數(shù)學(xué)模型的建立線性規(guī)劃數(shù)學(xué)模型的建立一、建模條件一、建模條件1 優(yōu)化條件優(yōu)化條件：問題所要達(dá)到的目標(biāo)能用線型函數(shù)描述，且能夠用極值 （max 或 min）來表示；2 限定條件限定條件：達(dá)到目標(biāo)受到一定的限制，且這些限制能夠用決策變量的 線性等式或線性不等式表示；3 選擇條件選擇條件：有多種可選擇的方案

7、供決策者選擇，以便找出最優(yōu)方案。二、建模步驟二、建模步驟1 確定決策變量：確定決策變量：即需要我們作出決策或選擇的量。一般情況下，題目 問什么就設(shè)什么為決策變量。2 找出所有限定條件：找出所有限定條件：即決策變量受到的所有的約束；3 寫出目標(biāo)函數(shù)：寫出目標(biāo)函數(shù)：即問題所要達(dá)到的目標(biāo)，并明確是max 還是 min。三、建模案例三、建模案例例例1.3 （生產(chǎn)計(jì)劃問題生產(chǎn)計(jì)劃問題）某工廠生產(chǎn)A、B兩種產(chǎn)品，有關(guān)資料如下所示：設(shè)總成本為設(shè)總成本為z，A、B產(chǎn)品銷量為產(chǎn)品銷量為x1、x2，產(chǎn)品產(chǎn)品C的銷售量為的銷售量為x3，報(bào)廢量為，報(bào)廢量為x4，則：，則： max z = 4 x1 + 10 x2 +

8、 3 x3 2 x4 2x1 + 3x2 12 3x1 + 4x2 24 2x2 +x3 + x4 = 0 x3 5 x1、x2 、x3 、x40船只種類船只數(shù)拖 輪30A型駁船34B型駁船52航線號合同貨運(yùn)量12002400航線號船隊(duì)類型編隊(duì)形式貨運(yùn)成本（千元隊(duì)）貨運(yùn)量（千噸）拖輪A型駁船B型駁船1112362521436202322472404142720問：應(yīng)如何編隊(duì)，才能既完成合同任務(wù)，又使總貨運(yùn)成本為最??？例1.4 （合理組織船舶運(yùn)行問題合理組織船舶運(yùn)行問題）某航運(yùn)局現(xiàn)有船只種類、數(shù)量以及計(jì)劃期 內(nèi)各條航線的貨運(yùn)量、貨運(yùn)成本如下表所示：解：設(shè)：xj為第 j 號類型船隊(duì)的隊(duì)數(shù)（j =

9、1，2，3，4），z 為總貨運(yùn)成本則： min z = 36x1 + 36x2 + 72x3 + 27x4 x1 + x2 + 2x3 + x4 302x1 + 2x3 34 4x2 + 4x3 + 4x4 5225x1 + 20 x2 200 40 x3 + 20 x4 400 xj 0 j = 1,2,3,4(變量為整數(shù))用單純形法可求得：用單純形法可求得： x1 = 8，x2 = 0 ，x3 = 7， x4 = 6 最優(yōu)值：最優(yōu)值：z = 954即：四種船隊(duì)類型的隊(duì)數(shù)分別是即：四種船隊(duì)類型的隊(duì)數(shù)分別是 8、0、7、6，此時(shí)可使總貨運(yùn)成本為最小，為此時(shí)可使總貨運(yùn)成本為最小，為954千元。千

10、元。例1.5 （合理下料問題合理下料問題）某廠需要做100套鋼架，每套用長為2.9m、2.1m和1.5m的元鋼各一根。已知原料長7.4m，問應(yīng)如何下料，可使所用的原材料最省？解：1）最簡單的方法是：在每一根原材料上截取2.9m、2.1m、1.5m元鋼各一根，每根余料頭0.9m，為了做100套鋼架，用料100根，共有90m料頭。2）但若采用套裁的方法，則可節(jié)約原材料。如以下套裁方案： 方案方案長度長度mIIIIIIIVV2.92.11.5合計(jì)合計(jì)料頭料頭017.30.11207.40.31000213237.27.16.60.00.20.82應(yīng)選擇應(yīng)選擇哪種下哪種下料方案料方案呢呢?顯然顯然,應(yīng)

11、混合使用應(yīng)混合使用各種下料方案各種下料方案,而而不能只采用其中不能只采用其中一種方案。一種方案。3）數(shù)學(xué)模型min z = 0.1x1 + 0.3x20.2x40.8x5 2x1 + x2 +x3 100 2x2 + 2x4 x5 100 x1 3x32x43x5 100 xj 0 j = 1,2,3,4,5(變量為整數(shù))決策變量：設(shè)按第 j 種方案下料的原材料根數(shù)為xj（ j 1,2,3,4,5 ）目標(biāo)函數(shù)：要求原材料最省，則以所余料頭最少為目標(biāo)： min z 0.1x10.3x20.0 x30.2x40.8x5約束條件：采用各種方案截取的三種規(guī)格的元鋼數(shù)各為100根，則數(shù)學(xué)模型為：1.3

12、線性規(guī)劃圖解法線性規(guī)劃圖解法一、解題步驟一、解題步驟4 將最優(yōu)解代入目標(biāo)函數(shù)，求出最優(yōu)值。1 在直角平面坐標(biāo)系中畫出所有的約束等式，并找出所有約束條件的公共 部分，稱為可行域，可行域中的點(diǎn)稱為可行解。若無公共部分，則無可 行域，從而無可行解。2 標(biāo)出目標(biāo)函數(shù)值增加的方向。3 若求最大（?。┲?，則令目標(biāo)函數(shù)等值線沿（逆）目標(biāo)函數(shù)值增加的方 向平行移動(dòng)，找與可行域最后相交的點(diǎn)，該點(diǎn)就是最優(yōu)解。目標(biāo)函數(shù)的梯度方向。目標(biāo)函數(shù)的梯度方向。例例1x1 + 2x2 8 4x1 16 4x2 12 x1， x20 max z = 2 x1 + 3 x2最優(yōu)解：最優(yōu)解：X*= (4,2)T最優(yōu)值：最優(yōu)值：z*

13、= 14二、算例二、算例例例2x1 + 2x2 8 4x1 16 4x2 12 x1， x20 max z = 2 x1 + 4 x2該問題有無窮多個(gè)最優(yōu)解（在可行域內(nèi)，該問題有無窮多個(gè)最優(yōu)解（在可行域內(nèi)， 直線直線 x12x28上的點(diǎn)都是最優(yōu)解）上的點(diǎn)都是最優(yōu)解） 最優(yōu)值：最優(yōu)值：z* 2(x12x2)28 16目標(biāo)函數(shù)等值線最后與可行域的邊界目標(biāo)函數(shù)等值線最后與可行域的邊界 x12x28重合重合例例3在例1中增加約束條件2x1 + x2 4 無可行域，因而無可行解無可行域，因而無可行解 該問題無最優(yōu)解該問題無最優(yōu)解例例42x1 + x2 4 x1 x2 2 x1， x20 max z =

14、x1 + x2 目標(biāo)函數(shù)的等值線與可行域無最后交點(diǎn)目標(biāo)函數(shù)的等值線與可行域無最后交點(diǎn) 該問題有可行解，但無最優(yōu)解。該問題有可行解，但無最優(yōu)解。小結(jié)：小結(jié)：1 線性規(guī)劃問題的解有以下幾種情況：線性規(guī)劃問題的解有以下幾種情況：有最優(yōu)解有最優(yōu)解無最優(yōu)解無最優(yōu)解有唯一最優(yōu)解有唯一最優(yōu)解有無窮多個(gè)最優(yōu)解有無窮多個(gè)最優(yōu)解無可行解，因而無最優(yōu)解無可行解，因而無最優(yōu)解有可行解，但無最優(yōu)解有可行解，但無最優(yōu)解例1例2例3例42 圖解法的適用范圍：圖解法的適用范圍：求解兩個(gè)變量的線性規(guī)劃問題求解兩個(gè)變量的線性規(guī)劃問題問題問題:應(yīng)如何求解應(yīng)如何求解多個(gè)變量的多個(gè)變量的線性規(guī)劃問線性規(guī)劃問題題 ？ 目標(biāo)函數(shù)與可行域最

15、后有唯一交點(diǎn)目標(biāo)函數(shù)與可行域最后有唯一交點(diǎn) 目標(biāo)函數(shù)與可行域最后有兩個(gè)以上交點(diǎn)目標(biāo)函數(shù)與可行域最后有兩個(gè)以上交點(diǎn) 約束條件無公共區(qū)域約束條件無公共區(qū)域 約束條件有公共區(qū)域，但目標(biāo)函數(shù)與可行域無最后交點(diǎn)約束條件有公共區(qū)域，但目標(biāo)函數(shù)與可行域無最后交點(diǎn)1.4 線性規(guī)劃解的概念及性質(zhì)線性規(guī)劃解的概念及性質(zhì)1 可行解（可行解（ feasible solution ）：）：滿足線性規(guī)劃約束條件的解稱為可行解可行解。一、線性規(guī)劃解的概念一、線性規(guī)劃解的概念2 最優(yōu)解（最優(yōu)解（optimal solution）：使線性規(guī)劃目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解稱為 最優(yōu)解最優(yōu)解。3 基本解（基本解（basic solut

16、ion）：以線性規(guī)劃約束等式的系數(shù)矩陣A中任意m行m 列組成的mm滿秩子矩陣為基矩陣，與基矩陣相對應(yīng)的變量稱為基變量（basic variable），其余變量稱為非基變量，令非基變量為零，可求得基變 量的值，這樣求出的解稱為基本解基本解。 4 基本可行解（基本可行解（basic feasible solution）： 滿足非負(fù)約束的基本解稱為基本可行解基本可行解。若約束等式中有若約束等式中有n個(gè)個(gè)變量，變量，m個(gè)約束，則個(gè)約束，則基本解的個(gè)數(shù)基本解的個(gè)數(shù) 即有有限個(gè)基本解即有有限個(gè)基本解mnC基本可行解的個(gè)數(shù)也是有限個(gè)基本可行解的個(gè)數(shù)也是有限個(gè)令非基變量 x10，x2 0則得：X (0, 0,

17、 3, 1 )T基本解基本解2）取滿秩子矩陣 為基矩陣，0112322PPB則：基變量為x2、x3，非基變量為x1、x4令非基變量 x10，x4 0則得：X (0, 1, 5, 0 )T基本解基本解基本可行解基本可行解不是基本可行解不是基本可行解例例 討論下述約束方程的解 x1 2x2 x3 3 2x1 x2 x4 1解解系數(shù)矩陣為：10120121A1）取滿秩子矩陣 為基矩陣，1001431PPB則：基變量為x3、x4，非基變量為x1、x23）X (1/2, 1/2, 3/2, 1/2)T不是基本解不是基本解可行解可行解不是基本可行解不是基本可行解1 可行解與最優(yōu)解：最優(yōu)解一定是可行解，但可

18、行解不一定是最優(yōu)解。二、線性規(guī)劃解之間的關(guān)系二、線性規(guī)劃解之間的關(guān)系基本解不一定是可行解，可行解也不一定是基本解。2 可行解與基本解：3 可行解與基本可行解：基本可行解一定是可行解，但可行解不一定是基本解?；究尚薪饨庖欢ㄊ腔窘?，但基本解不一定是基本可行解。4 基本解與基本可行解：5 最優(yōu)解與基本解：最優(yōu)解不一定是基本解，基本解也不一定是最優(yōu)解。問題：最優(yōu)解與基本可行解？非可行解可行解基本可行解基本解三、線性規(guī)劃解的性質(zhì)三、線性規(guī)劃解的性質(zhì)定理定理1 線性規(guī)劃的可行域 R 是一個(gè)凸集，且有有限個(gè)頂點(diǎn)。定理定理2 X是線性規(guī)劃可行域 R 頂點(diǎn)的充要條件是 X 線性規(guī)劃的基本可行解。定理定理3 若線性規(guī)劃有最優(yōu)解，則必有基本最優(yōu)解。定理定理4 若線性規(guī)劃在可行域的兩個(gè)頂點(diǎn)上達(dá)到最優(yōu)，則在兩個(gè)頂點(diǎn)的連線 上也達(dá)到最優(yōu)。線性規(guī)劃問題的可行域是一個(gè)凸集。線性規(guī)劃問題的可行域是一個(gè)凸集。線性規(guī)劃的每一個(gè)基本可行解對應(yīng)凸集的每一個(gè)頂點(diǎn)。線性規(guī)劃的每一個(gè)基本可行解對應(yīng)凸集的每一個(gè)頂點(diǎn)。若線性規(guī)劃有最優(yōu)解