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

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

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

3、最大？ 1.1 線(xiàn)性規(guī)劃的基本概念線(xiàn)性規(guī)劃的基本概念一、問(wèn)題的提出一、問(wèn)題的提出解：解：1.決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量分 別為 x1、x22.目標(biāo)函數(shù)：設(shè)總利潤(rùn)為z，則有： max z = 2 x1 + 3 x23.約束條件： x1 + 2x2 8 4x1 16 4x2 12 x1， x20例1.2 （配料問(wèn)題配料問(wèn)題）某廠(chǎng)生產(chǎn)三種藥物，這些藥物可以從四種不同的原料中提取。下表給出了單位原料可提取的藥物量：要求：生產(chǎn)A種藥物至少160單位；B種藥物恰好200單位，C種藥物不超過(guò)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é)模型稱(chēng)為線(xiàn)性規(guī)劃具有以上三個(gè)特征的數(shù)學(xué)模型稱(chēng)為線(xiàn)性規(guī)劃2 都有一個(gè)要達(dá)到的目標(biāo)，并且目標(biāo)要求可以表示成決策變量的線(xiàn)性函數(shù)； 根據(jù)目標(biāo)要求的不同，可以是求max，也可以是求min；3 都有一組約束條件，這些約束條件可以用決策變量的線(xiàn)性等式或線(xiàn)性不等 式來(lái)表示。其它形式其它形式),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 線(xiàn)性規(guī)劃數(shù)學(xué)模型的建立線(xiàn)性規(guī)劃數(shù)學(xué)模型的建立一、建模條件一、建模條件1 優(yōu)化條件優(yōu)化條件：?jiǎn)栴}所要達(dá)到的目標(biāo)能用線(xiàn)型函數(shù)描述，且能夠用極值 （max 或 min）來(lái)表示；2 限定條件限定條件：達(dá)到目標(biāo)受到一定的限制，且這些限制能夠用決策變量的 線(xiàn)性等式或線(xiàn)性不等式表示；3 選擇條件選擇條件：有多種可選擇的方案

7、供決策者選擇，以便找出最優(yōu)方案。二、建模步驟二、建模步驟1 確定決策變量：確定決策變量：即需要我們作出決策或選擇的量。一般情況下，題目 問(wèn)什么就設(shè)什么為決策變量。2 找出所有限定條件：找出所有限定條件：即決策變量受到的所有的約束；3 寫(xiě)出目標(biāo)函數(shù)：寫(xiě)出目標(biāo)函數(shù)：即問(wèn)題所要達(dá)到的目標(biāo)，并明確是max 還是 min。三、建模案例三、建模案例例例1.3 （生產(chǎn)計(jì)劃問(wèn)題生產(chǎn)計(jì)劃問(wèn)題）某工廠(chǎng)生產(chǎn)A、B兩種產(chǎn)品，有關(guān)資料如下所示：設(shè)總成本為設(shè)總成本為z，A、B產(chǎn)品銷(xiāo)量為產(chǎn)品銷(xiāo)量為x1、x2，產(chǎn)品產(chǎn)品C的銷(xiāo)售量為的銷(xiāo)售量為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船只種類(lèi)船只數(shù)拖 輪30A型駁船34B型駁船52航線(xiàn)號(hào)合同貨運(yùn)量12002400航線(xiàn)號(hào)船隊(duì)類(lèi)型編隊(duì)形式貨運(yùn)成本（千元隊(duì)）貨運(yùn)量（千噸）拖輪A型駁船B型駁船1112362521436202322472404142720問(wèn)：應(yīng)如何編隊(duì)，才能既完成合同任務(wù)，又使總貨運(yùn)成本為最?。坷?.4 （合理組織船舶運(yùn)行問(wèn)題合理組織船舶運(yùn)行問(wèn)題）某航運(yùn)局現(xiàn)有船只種類(lèi)、數(shù)量以及計(jì)劃期 內(nèi)各條航線(xiàn)的貨運(yùn)量、貨運(yùn)成本如下表所示：解：設(shè)：xj為第 j 號(hào)類(lèi)型船隊(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ì)類(lèi)型的隊(duì)數(shù)分別是即：四種船隊(duì)類(lèi)型的隊(duì)數(shù)分別是 8、0、7、6，此時(shí)可使總貨運(yùn)成本為最小，為此時(shí)可使總貨運(yùn)成本為最小，為954千元。千

10、元。例1.5 （合理下料問(wèn)題合理下料問(wèn)題）某廠(chǎng)需要做100套鋼架，每套用長(zhǎng)為2.9m、2.1m和1.5m的元鋼各一根。已知原料長(zhǎng)7.4m，問(wèn)應(yīng)如何下料，可使所用的原材料最??？解：1）最簡(jiǎn)單的方法是：在每一根原材料上截取2.9m、2.1m、1.5m元鋼各一根，每根余料頭0.9m，為了做100套鋼架，用料100根，共有90m料頭。2）但若采用套裁的方法，則可節(jié)約原材料。如以下套裁方案： 方案方案長(zhǎng)度長(zhǎng)度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、線(xiàn)性規(guī)劃圖解法線(xiàn)性規(guī)劃圖解法一、解題步驟一、解題步驟4 將最優(yōu)解代入目標(biāo)函數(shù)，求出最優(yōu)值。1 在直角平面坐標(biāo)系中畫(huà)出所有的約束等式，并找出所有約束條件的公共 部分，稱(chēng)為可行域，可行域中的點(diǎn)稱(chēng)為可行解。若無(wú)公共部分，則無(wú)可 行域，從而無(wú)可行解。2 標(biāo)出目標(biāo)函數(shù)值增加的方向。3 若求最大（?。┲?，則令目標(biāo)函數(shù)等值線(xiàn)沿（逆）目標(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該問(wèn)題有無(wú)窮多個(gè)最優(yōu)解（在可行域內(nèi)，該問(wèn)題有無(wú)窮多個(gè)最優(yōu)解（在可行域內(nèi)， 直線(xiàn)直線(xiàn) x12x28上的點(diǎn)都是最優(yōu)解）上的點(diǎn)都是最優(yōu)解） 最優(yōu)值：最優(yōu)值：z* 2(x12x2)28 16目標(biāo)函數(shù)等值線(xiàn)最后與可行域的邊界目標(biāo)函數(shù)等值線(xiàn)最后與可行域的邊界 x12x28重合重合例例3在例1中增加約束條件2x1 + x2 4 無(wú)可行域，因而無(wú)可行解無(wú)可行域，因而無(wú)可行解 該問(wèn)題無(wú)最優(yōu)解該問(wèn)題無(wú)最優(yōu)解例例42x1 + x2 4 x1 x2 2 x1， x20 max z =

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

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

16、ion）：以線(xiàn)性規(guī)劃約束等式的系數(shù)矩陣A中任意m行m 列組成的mm滿(mǎn)秩子矩陣為基矩陣，與基矩陣相對(duì)應(yīng)的變量稱(chēng)為基變量（basic variable），其余變量稱(chēng)為非基變量，令非基變量為零，可求得基變 量的值，這樣求出的解稱(chēng)為基本解基本解。 4 基本可行解（基本可行解（basic feasible solution）： 滿(mǎn)足非負(fù)約束的基本解稱(chēng)為基本可行解基本可行解。若約束等式中有若約束等式中有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）取滿(mǎn)秩子矩陣 為基矩陣，0112322PPB則：基變量為x2、x3，非基變量為x1、x4令非基變量 x10，x4 0則得：X (0, 1, 5, 0 )T基本解基本解基本可行解基本可行解不是基本可行解不是基本可行解例例 討論下述約束方程的解 x1 2x2 x3 3 2x1 x2 x4 1解解系數(shù)矩陣為：10120121A1）取滿(mǎn)秩子矩陣 為基矩陣，1001431PPB則：基變量為x3、x4，非基變量為x1、x23）X (1/2, 1/2, 3/2, 1/2)T不是基本解不是基本解可行解可行解不是基本可行解不是基本可行解1 可行解與最優(yōu)解：最優(yōu)解一定是可行解，但可

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