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

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

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

4、目標函數：設總成本為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二、數學模型二、數學模型1.決策變量： X = (x1,x2,.,xn)T2.目標函數：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三、模型特點三、模型特點1 都用一組決策變量X = (x1,x2,xn)T表示某一方案，且決策變量取值非負； 具有以上三個特征的數學模型稱為線性規劃具有以上三個特征的數學模型稱為線性規劃2 都有一個要達到的目標，并且目標要求可以表示成決策變量的線性函數； 根據目標要求的不同，可以是求max，也可以是求min；3 都有一組約束條件，這些約束條件可以用決策變量的線性等式或線性不等 式來表示。其它形式其它形式),2, 1(0),2, 1(max(min)11njxm

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

7、供決策者選擇，以便找出最優方案。二、建模步驟二、建模步驟1 確定決策變量：確定決策變量：即需要我們作出決策或選擇的量。一般情況下，題目 問什么就設什么為決策變量。2 找出所有限定條件：找出所有限定條件：即決策變量受到的所有的約束；3 寫出目標函數：寫出目標函數：即問題所要達到的目標，并明確是max 還是 min。三、建模案例三、建模案例例例1.3 （生產計劃問題生產計劃問題）某工廠生產A、B兩種產品，有關資料如下所示：設總成本為設總成本為z，A、B產品銷量為產品銷量為x1、x2，產品產品C的銷售量為的銷售量為x3，報廢量為，報廢量為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船只種類船只數拖 輪30A型駁船34B型駁船52航線號合同貨運量12002400航線號船隊類型編隊形式貨運成本（千元隊）貨運量（千噸）拖輪A型駁船B型駁船1112362521436202322472404142720問：應如何編隊，才能既完成合同任務，又使總貨運成本為最??？例1.4 （合理組織船舶運行問題合理組織船舶運行問題）某航運局現有船只種類、數量以及計劃期 內各條航線的貨運量、貨運成本如下表所示：解：設：xj為第 j 號類型船隊的隊數（j =

9、1，2，3，4），z 為總貨運成本則： 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(變量為整數)用單純形法可求得：用單純形法可求得： x1 = 8，x2 = 0 ，x3 = 7， x4 = 6 最優值：最優值：z = 954即：四種船隊類型的隊數分別是即：四種船隊類型的隊數分別是 8、0、7、6，此時可使總貨運成本為最小，為此時可使總貨運成本為最小，為954千元。千

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

11、混合使用應混合使用各種下料方案各種下料方案,而而不能只采用其中不能只采用其中一種方案。一種方案。3）數學模型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(變量為整數)決策變量：設按第 j 種方案下料的原材料根數為xj（ j 1,2,3,4,5 ）目標函數：要求原材料最省，則以所余料頭最少為目標： min z 0.1x10.3x20.0 x30.2x40.8x5約束條件：采用各種方案截取的三種規格的元鋼數各為100根，則數學模型為：1.3

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

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

14、x1 + x2 目標函數的等值線與可行域無最后交點目標函數的等值線與可行域無最后交點 該問題有可行解，但無最優解。該問題有可行解，但無最優解。小結：小結：1 線性規劃問題的解有以下幾種情況：線性規劃問題的解有以下幾種情況：有最優解有最優解無最優解無最優解有唯一最優解有唯一最優解有無窮多個最優解有無窮多個最優解無可行解，因而無最優解無可行解，因而無最優解有可行解，但無最優解有可行解，但無最優解例1例2例3例42 圖解法的適用范圍：圖解法的適用范圍：求解兩個變量的線性規劃問題求解兩個變量的線性規劃問題問題問題:應如何求解應如何求解多個變量的多個變量的線性規劃問線性規劃問題題 ？ 目標函數與可行域最

15、后有唯一交點目標函數與可行域最后有唯一交點 目標函數與可行域最后有兩個以上交點目標函數與可行域最后有兩個以上交點 約束條件無公共區域約束條件無公共區域 約束條件有公共區域，但目標函數與可行域無最后交點約束條件有公共區域，但目標函數與可行域無最后交點1.4 線性規劃解的概念及性質線性規劃解的概念及性質1 可行解（可行解（ feasible solution ）：）：滿足線性規劃約束條件的解稱為可行解可行解。一、線性規劃解的概念一、線性規劃解的概念2 最優解（最優解（optimal solution）：使線性規劃目標函數達到最優的可行解稱為 最優解最優解。3 基本解（基本解（basic solut

16、ion）：以線性規劃約束等式的系數矩陣A中任意m行m 列組成的mm滿秩子矩陣為基矩陣，與基矩陣相對應的變量稱為基變量（basic variable），其余變量稱為非基變量，令非基變量為零，可求得基變 量的值，這樣求出的解稱為基本解基本解。 4 基本可行解（基本可行解（basic feasible solution）： 滿足非負約束的基本解稱為基本可行解基本可行解。若約束等式中有若約束等式中有n個個變量，變量，m個約束，則個約束，則基本解的個數基本解的個數 即有有限個基本解即有有限個基本解mnC基本可行解的個數也是有限個基本可行解的個數也是有限個令非基變量 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解解系數矩陣為：10120121A1）取滿秩子矩陣 為基矩陣，1001431PPB則：基變量為x3、x4，非基變量為x1、x23）X (1/2, 1/2, 3/2, 1/2)T不是基本解不是基本解可行解可行解不是基本可行解不是基本可行解1 可行解與最優解：最優解一定是可行解，但可

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