《管理運籌學》全套課件（完整版）

1、經(jīng)濟管理學院 1.期末考試成績占70%。 2.平時成績占30% ，包括： l點名若干次 缺席六次不能參加考試，五次40分，四次50分，三次 60分，二次70分，一次80分，0次90分 l論文一篇 l論文題目待定 成績評定方法成績評定方法 第第0 0章章 緒論緒論 0.1 什么是運籌學 0.2 運籌學簡史 0.3 運籌學模型 為何學習運籌學？最有效率！最經(jīng)濟！最和諧！ 政府需要、企業(yè)需要、家庭需要、個人成長需要。 運籌學（Operations Research）是近幾十年發(fā)展起來的一門 新興的應(yīng)用性學科。其主要思想主要思想是運用數(shù)學模型方法研究各種決 策問題的優(yōu)化途徑及方案，為管理決策者提供科學

2、決策的參考依 據(jù)。 管理運籌學與運籌學的含義基本一致，只不過是為突出運籌 學的管理性質(zhì)而加上了“管理”二字。 0.1 什么是運籌學 l0.1.1 引言 l田忌賽馬；沈括運糧 l0.1.2 名稱 l0.1.3 定義 l我國的定義： l0.1.4 特點 l0.1.5 內(nèi)容 l確定型；隨機型；混合型；模糊型 l0.1.6 相關(guān)學科 0.2 運籌學簡史 混沌時期；朦眬時期；初創(chuàng)時期；確立時期； 擴展時期 我國運籌學發(fā)展概況 運籌學是指通過運用科學方法研究某一系統(tǒng)的 最優(yōu)管理和控制，或者分析研究某一系統(tǒng)的運行狀況， 以及系統(tǒng)的管理問題和生產(chǎn)經(jīng)營活動。主要研究方法 是定量化和模型化，特別是運用各種數(shù)學模型

3、，目的 是基于所研究的系統(tǒng)，力求獲得一個合理運用人力、 物力、財力和各種資源的最佳方案，以使系統(tǒng)獲得最 優(yōu)目標。 1948年，美國麻省理工學院率先開設(shè)了運籌學課程； 1950年，美國出版了第一份運籌學雜志； 1951年，Morse 和 Kimball 出版了運籌學方法第一 本以運籌學為名的專著，給出了運籌學的定義：為決策 機構(gòu)在對其控制下業(yè)務(wù)活動進行決策時，提供以數(shù)量化 為基礎(chǔ)的科學方法。 運籌學在中國的發(fā)展（我國現(xiàn)代運籌學概況） 1. 50年代中期錢學森、華羅庚、許國志等著名學者將 Operations ResearchOperations Research（簡稱OROR）從西方引入我國。

4、2. 1956年將Operations ResearchOperations Research直譯為“運用學” 3. 1957年將Operations ResearchOperations Research.意譯為“運籌學” 是取自史記高祖本記“夫運籌帷幄之中，決勝 于千里之外，吾不如子房” 一語，摘取“運籌”二字 作為這門科學的名稱，既顯示其軍事的起源，也表明 運籌學的哲理思想遠在我國古代已經(jīng)存在。 ( (港臺稱港臺稱“作業(yè)研究作業(yè)研究”） 中國的第一個運籌學研究小組是在錢學森、許國 志先生的推動下于1956年在中國科學院力學研究所成 立的。其應(yīng)用是在1957年始于建筑業(yè)和紡織業(yè)，從 195

5、8年開始在交通運輸、工業(yè)、農(nóng)業(yè)、水利建設(shè)、郵 電等方面使用。尤其是在運輸方面，從物資調(diào)運、裝 卸到調(diào)度等等。 1958年，建立了專門的運籌學研究室，但由于在 應(yīng)用單純形法解決糧食合理運輸問題時遇到了困難， 我國運籌學工作者于是創(chuàng)立了運輸問題的“圖上作業(yè) 法”。1959年成立國際運籌學聯(lián)合會(International Federation of Operations Research Societies， IFORS)，我國于1982年加入IFORS，并于1999年8月組 織了第15屆大會。 0.3 運籌學模型 l0.3.1 引言 l模型：就是現(xiàn)實系統(tǒng)的簡仿物或抽象表示。 l運籌學模型屬于后者

6、。 l決策變量；約束條件；目標函數(shù) l可行解、最優(yōu)解。 l0.3.2 模型建立 數(shù)學模型舉例：成本、收益和利潤的數(shù) 學模型（略） 運籌學的應(yīng)用（略） 1.1 線性規(guī)劃的一般模型線性規(guī)劃的一般模型 1.2 線性規(guī)劃的圖解法線性規(guī)劃的圖解法 1.3 線性規(guī)劃的標準形式線性規(guī)劃的標準形式 1.4 線性規(guī)劃的解及其性質(zhì)線性規(guī)劃的解及其性質(zhì) 1.5 線性規(guī)劃的應(yīng)用模型線性規(guī)劃的應(yīng)用模型 第第1章章 線性規(guī)劃的基本性質(zhì)線性規(guī)劃的基本性質(zhì) l線性規(guī)劃是運籌學的一個分支，主要用于研 究解決有限資源的最佳分配問題，即如何對 有限資源做出最佳方式的調(diào)配和最有利的使 用，以便最充分地發(fā)揮資源的效能，以獲取 最佳經(jīng)濟

7、效益。 lLinear Programming - LP 1.1 線性規(guī)劃的一般模型線性規(guī)劃的一般模型 1.1.1 引引 例例 例例1 1 產(chǎn)品配比問題（產(chǎn)品配比問題（范例范例） 某廠擬生產(chǎn)甲、乙兩種產(chǎn)品，每件利潤分別為某廠擬生產(chǎn)甲、乙兩種產(chǎn)品，每件利潤分別為3 3、5 5百元。百元。 甲、乙產(chǎn)品的部件各自在甲、乙產(chǎn)品的部件各自在A、B兩個車間分別生產(chǎn)，每件甲、兩個車間分別生產(chǎn)，每件甲、 乙產(chǎn)品的部件分別需要乙產(chǎn)品的部件分別需要A、B車間的生產(chǎn)能力車間的生產(chǎn)能力1 1、2 2工時。兩件工時。兩件 產(chǎn)品的部件最后都要在產(chǎn)品的部件最后都要在C車間裝配，裝配每件甲、乙產(chǎn)品分別車間裝配，裝配每件甲、乙

8、產(chǎn)品分別 需要需要3 3、4 4工時，三車間每天可用于生產(chǎn)這兩種產(chǎn)品的工時分別工時，三車間每天可用于生產(chǎn)這兩種產(chǎn)品的工時分別 為為8 8、1212、3636，問應(yīng)如何安排生產(chǎn)這兩種產(chǎn)品才能獲利最多？，問應(yīng)如何安排生產(chǎn)這兩種產(chǎn)品才能獲利最多？ 1.1 線性規(guī)劃的一般模型線性規(guī)劃的一般模型 x1 x2決策變量決策變量 = 3x1 +5x2 0 目標函數(shù)目標函數(shù) x1 8 2x2 12 3x1 + 4x2 36 函數(shù)約束函數(shù)約束 x1 ， ， x2 0 非負性約束非負性約束 甲甲 乙乙 1 0 3 0 2 4 8 12 36 A B C 車間車間 產(chǎn)品產(chǎn)品 單耗（工時單耗（工時/ /件）件）最大生產(chǎn)

9、能力最大生產(chǎn)能力 （工時（工時/ /天）天） 單位利潤單位利潤 （百元（百元/ /件）件） 3 5 1.1 線性規(guī)劃的一般模型線性規(guī)劃的一般模型 例例2 2 配料問題配料問題 某化工廠根據(jù)一項合同要為用戶生產(chǎn)一種用甲、乙某化工廠根據(jù)一項合同要為用戶生產(chǎn)一種用甲、乙 兩種原料混合配制而成的特殊產(chǎn)品。甲、乙兩種原料都兩種原料混合配制而成的特殊產(chǎn)品。甲、乙兩種原料都 含有含有A，B，C三種化學成分三種化學成分，其含量其含量( (%) )是是: :甲為甲為1212， 2 2， 3 3；乙為乙為3 3，3 3，1515。按合同規(guī)定按合同規(guī)定，產(chǎn)品中三種化學產(chǎn)品中三種化學 成分的含量成分的含量( (%)

10、)不得低于不得低于4 4，2 2，5 5。甲、乙原料成本為甲、乙原料成本為 每千克每千克3 3，2 2元。元。 廠方希望總成本達到最小廠方希望總成本達到最小，則應(yīng)如何配制該產(chǎn)品則應(yīng)如何配制該產(chǎn)品？ 1.1 線性規(guī)劃的一般模型線性規(guī)劃的一般模型 成分含量 成分含量(%)(%) 原原 料 料 化學成分化學成分 甲甲 乙乙 產(chǎn)品成分產(chǎn)品成分 最低含量最低含量(%)(%) A B C 12 3 2 3 3 15 4 2 5 成本（元成本（元 / /千克）千克） 3 2 min = 3x1+2x2 12 x1 +3x2 4 2 x1 +3x2 2 s.t. 3 x1+15x2 5 x1 +x2 = 1

11、x1 , , x2 0 配料平衡條件配料平衡條件 1.1 線性規(guī)劃的一般模型線性規(guī)劃的一般模型 1.1. 2線性規(guī)劃的一般模型線性規(guī)劃的一般模型 一般一般LP模型的模型的： ，. LP模型的模型的：，. s.t. opt z = c1 x1+c2 x2+c3 x3+cn xn a11x1 +a12 x2+a1n xn b1 a21x1 +a22 x2+a2n xn b2 am1x1+am2x2+amn xn bm xj(或或) 0, , 或自由或自由, , j=1, ,2, , ,n 1.2 線性規(guī)劃的圖解法線性規(guī)劃的圖解法 1.2.1 圖解法的基本步驟圖解法的基本步驟 X*= (4, , 6

12、)T z* = 42 1畫出可行域圖形畫出可行域圖形 2畫出目標函數(shù)的畫出目標函數(shù)的 等值線及其法線等值線及其法線 3確定最優(yōu)點確定最優(yōu)點 max z = 3x1+5x2 x1 8 2 x2 12 3x1+ 4 x2 36 x1, , x2 0 s.t. x1 x2 O(0, ,0) x1= 8 A(8, ,0) 2x2= 12 D(0, ,6) 3x1 + 4x2 = 36 O(0, ,0) x1 x2 D(0, ,6) C(4, ,6) B(8, ,3) A(8, ,0) z = 15 z = 30 z 法向法向 z* = 42 1.2 線性規(guī)劃的圖解法線性規(guī)劃的圖解法 1.2.2 幾點說

13、明幾點說明 實際運用時還須注意以下幾點實際運用時還須注意以下幾點: : (1)(1)若函數(shù)約束原型就是等式若函數(shù)約束原型就是等式, ,則其代表的區(qū)域僅為一直線則其代表的區(qū)域僅為一直線, ,而且問而且問 題的整個可行域題的整個可行域( (若存在的話若存在的話) )也必然在此直線上。也必然在此直線上。 (2)(2)在畫目標函數(shù)等值線時只須畫兩條就能確定其法線方向在畫目標函數(shù)等值線時只須畫兩條就能確定其法線方向, ,為此為此, , 只須賦給只須賦給 兩個適當?shù)闹?。兩個適當?shù)闹怠?(3)(3)在找出最優(yōu)點后在找出最優(yōu)點后, ,關(guān)于其坐標值有兩種確定方法關(guān)于其坐標值有兩種確定方法: : 在圖上觀測最優(yōu)點

14、坐標值在圖上觀測最優(yōu)點坐標值 通過解方程組得出最優(yōu)點坐標值通過解方程組得出最優(yōu)點坐標值 1.2 線性規(guī)劃的圖解法線性規(guī)劃的圖解法 1.2.3 幾種可能結(jié)果幾種可能結(jié)果 一、唯一解一、唯一解 如例如例1 1、例、例2 2都只有一個都只有一個 最優(yōu)點，屬于唯一解的情形最優(yōu)點，屬于唯一解的情形 s.t. max z = 3x1+4x2 x1 8 2x2 12 3x1 + 4x2 36 x1 ， ， x2 0 二二多重解多重解 z = 12 z* = 36 線段線段上無窮多個上無窮多個 點均為最優(yōu)解。點均為最優(yōu)解。 O(0, ,0) x1 x2 D(0, ,6) C(4, ,6) B(8, ,3) A

15、(8, ,0) 1.2 線性規(guī)劃的圖解法線性規(guī)劃的圖解法 x1 x2 z* 三、無界解三、無界解 3 6 9 4812 x1 x2 四、無可行解四、無可行解 + 1.3 線性規(guī)劃的標準形式線性規(guī)劃的標準形式 1.3.1 線性規(guī)劃問題的標準形式線性規(guī)劃問題的標準形式 max z=c1x1+c2x2+c3x3+cnxn s.t. a11x1 +a12x2+ +a1nxn = b1 (0) a21x1 +a22x2+ +a2nxn = b2 (0) am1x1+am2x2+amnxn = bm (0) x1 , , x2 , , , , xn 0 簡記為：簡記為： max z =cjxj j=1 n

16、 s.t. aijx j = bi , , i=1, 2 , , m j=1 n xj 0, , j=1, 2 , , n max z =CTX s.t. AX = b X 0 (M1): (M2): (M3): (M) 1.3 線性規(guī)劃的標準形式線性規(guī)劃的標準形式 1.3.2 非標準形非標準形LP問題的標準化問題的標準化 一、目標函數(shù)一、目標函數(shù) min z = CTX 令令 z= z max z= CTX 例例：min z = 3x1 2x2 max z= 3x1 2x2 二、函數(shù)約束二、函數(shù)約束 bi0 兩邊同時乘以兩邊同時乘以 - -1 約束為約束為形式形式 加上加上松弛變量松弛變量

17、約束為約束為形式形式 減去減去剩余變量剩余變量 三、決策變量三、決策變量 若若xk 0, , 令令 xk = xk, ,則則 xk 0 若若xk為為自由變量自由變量, , 令令 xk = xk xk且且 xk, ,xk 0 x x* f (x) - - f (x) 1.3 線性規(guī)劃的標準形式線性規(guī)劃的標準形式 = 3x1+5x2max x1 8 2x2 12 3x1+4x2 36 x1 ， ， x2 0 s.t. x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 = 36 x1 ， ， x2 ， x3 ，x4 ，x5 0 s.t. = 3x1+5x2max+ x3+

18、x4+ x5 1.3 線性規(guī)劃的標準形式線性規(guī)劃的標準形式 min z = x1 2 x2 3 x3 x1 2 x2 x3 5 2x1 3 x2 x3 6 x1 x2 x3 2 x1 0, , x3 0 s.t. 解:max z= x1 2x2 3x3 s.t. x1 2x2 x3 + x4 = 5 2x1 3x2 x3 - - x5 = 6 x1 x2 x3 +x6 = 2 x1 , , x4 , , x5 , , x6 0 , , x3 0 例例4 4 將下述將下述LP問題化成標準形問題化成標準形 1.3 線性規(guī)劃的標準形式線性規(guī)劃的標準形式 令令x2 = x2 ，且 ，且 x2， 0 x

19、3 = - - 代入上式中，得代入上式中，得 max z= x1 2 x2+ + 2 3 x1 + +2x2 2 + + + + x4 = 5 2x1+ +3x2 3 + + x5 = 6 x1 + + x2 + + + +x6 = 2 x1 , , x2, , , , , , x4 , , x5 , , x6 0 s.t. 1.4 線性規(guī)劃的解及其性質(zhì)線性規(guī)劃的解及其性質(zhì) 1.4.1 線性規(guī)劃的解的概念線性規(guī)劃的解的概念 一、一、可行解可行解: : 滿足滿足LP問題所有約束條件的問題所有約束條件的X。 二、二、最優(yōu)解最優(yōu)解: : 滿足目標要求的可行解滿足目標要求的可行解X。 三、三、基本解基

20、本解: : 只適用于標準形只適用于標準形LP問題問題（M）。）。 (1) 基基(矩陣矩陣) AX = b 設(shè)設(shè) 為為A的一個的一個m階子矩陣，若階子矩陣，若| | |0,|0,則稱則稱 為約束方程組為約束方程組AX=b或標準形或標準形LP問題問題(M)的一個的一個 基（矩陣）基（矩陣）。 1.4 線性規(guī)劃的解及其性質(zhì)線性規(guī)劃的解及其性質(zhì) A = 1 0 1 0 0 0 2 0 1 0 3 4 0 0 1 x1 x2 x3 x4 x5 a1 a2 a3 a4 a5 可取可取 B0=（a3 , ,a4 , ,a5）為基（）為基（| B0 |0）, ,這時這時 稱稱 a3 , ,a4 , ,a5 為

21、為基向量基向量，而，而 a1 , ,a2 為為非基向量非基向量；稱稱 x3 , ,x4 , ,x5 為為基變量基變量，而，而 x1 , ,x2 為為非基變量非基變量。 1.4 線性規(guī)劃的解及其性質(zhì)線性規(guī)劃的解及其性質(zhì) (2) (2) 基本解基本解 的標準形的標準形 max z = 3x1 + 5x2 s.t. x1 +x3 = 8 2 x2 +x4 = 12 3x1 + 4x2 +x5 = 36 x1 , , x2 , , x3 , , x4 , , x5 0 取取 B0=（a3 , ,a4 , ,a5）為基，令一切非基變量為基，令一切非基變量 x1= x2 = 0, 可解得基變量可解得基變量

22、 x3 = 8 ， x4 = 12 ， x5 = 36 則得一特解則得一特解 X0 = ( 0，0，8，12，36 )T 稱為一個稱為一個(關(guān)于關(guān)于 B0 為基的為基的) 基本解基本解。 1.4 線性規(guī)劃的解及其性質(zhì)線性規(guī)劃的解及其性質(zhì) 也可取也可取 B1= ( a2 , ,a3 , ,a4 )為基為基, ,得得 X1 = ( 0，9，8，- - 6，0 )T 還可取還可取 B2= ( a1 , ,a2 , ,a3 )為基為基, ,得得 X2 = ( 4，6，4，0，0 )T 等等等等。 四、四、基本可行解基本可行解 滿足非負性約束的基本解滿足非負性約束的基本解。 如如 X0 ， ， X2 ；

23、 ；而而 X1 不不可行可行。 對對基本基本(可行可行)解解而言而言：在其分量中，若有一個或更多個：在其分量中，若有一個或更多個基變量基變量取值為取值為 ，則，則稱其為一個稱其為一個基本基本(可行可行)解解，否則為，否則為。 如設(shè)：如設(shè)： = ( 0， ， ， ， 0 ，)T 是一個是一個基本可行解基本可行解，其中其中 5= 為為，則該，則該 為為基本可行解基本可行解。 1.4 線性規(guī)劃的解及其性質(zhì)線性規(guī)劃的解及其性質(zhì) 基本基本( (可行可行) )解解， 并恰有并恰有個個 分量。分量。 基本可行解基本可行解對應(yīng)的對應(yīng)的基基，稱為稱為可行基可行基； 對應(yīng)的對應(yīng)的基基，稱為稱為最優(yōu)基最優(yōu)基。 如：

24、如：基基 B0= ( a2 , ,a3 , ,a4 ) 對應(yīng)對應(yīng) X0 = ( 0，0，8，12，36 )T 可行可行 基基 B1= ( a2 , ,a3 , ,a4 ) 對應(yīng)對應(yīng) X1 = ( 0，9，8，0 )T 基基 B2 = ( a1 , ,a2 , ,a3 ) 對應(yīng)對應(yīng) X2 = ( ，4，0，0 )T 恰有恰有 個個分量，分量， 為為可行基可行基 為為基基 為為最優(yōu)基最優(yōu)基 x*x* B* 1.4 線性規(guī)劃的解及其性質(zhì)線性規(guī)劃的解及其性質(zhì) 1.4.2 凸性的幾個基本概念凸性的幾個基本概念 一一、凸集凸集 設(shè)設(shè) En，對任意兩點，對任意兩點X ， ，若對滿足，若對滿足0 1的一切的一

25、切 實數(shù)實數(shù) ，都有，都有 X+(1- ) 則稱則稱 為為凸集凸集。 X X 凸集凸集 凸集凸集非非凸集凸集 非非 表示表示中兩點中兩點 X，連線上的任一點連線上的任一點 凸集凸集的的幾何意義幾何意義：凸集：凸集 中任意兩點中任意兩點 X，連線上的點，都在凸集連線上的點，都在凸集 中。中。 1.4 線性規(guī)劃的解及其性質(zhì)線性規(guī)劃的解及其性質(zhì) 二、二、極點極點 設(shè)凸集設(shè)凸集 , , ，如果如果 不能用不能用 中不同的兩點中不同的兩點 和和 表示為表示為 = +(1-) (01) 則稱則稱 為為 的一個的一個極點極點。 三、三、 凸組合凸組合 設(shè)設(shè), , 實數(shù)實數(shù), ,i = 1, ,2, , ,

26、, s,且且，則稱則稱 = + + 為點為點 的一個的一個凸組合凸組合。 1.4 線性規(guī)劃的解及其性質(zhì)線性規(guī)劃的解及其性質(zhì) 1.4.1.4.3 3 線性規(guī)劃的解的性質(zhì)線性規(guī)劃的解的性質(zhì) 1：LP問題問題(M)的可行域的可行域 R = XAX=b, X 0 是凸集。是凸集。 2：LP問題問題(M)的一個基本可行解與可行域的一個基本可行解與可行域 R 的一個極點的一個極點 互相對應(yīng)。互相對應(yīng)。 3： 對于一個給定的標準型對于一個給定的標準型LP問題問題(M)來說：來說： 若若(M)有可行解，則必有基本可行解；有可行解，則必有基本可行解； 若若(M)有最優(yōu)解，則必有最優(yōu)基本解。有最優(yōu)解，則必有最優(yōu)基

27、本解。 ：若：若LP問題的可行域問題的可行域 R, 則則 R 至少有一極點。至少有一極點。 ：LP問題可行域問題可行域 R 的極點數(shù)目必為有限個。的極點數(shù)目必為有限個。 1.4 線性規(guī)劃的解及其性質(zhì)線性規(guī)劃的解及其性質(zhì) 僅就標準形僅就標準形LP問題問題(M)說明其合理性。說明其合理性。 因因(M)是一個是一個m階階n維的維的LP問題，則從其系數(shù)陣的問題，則從其系數(shù)陣的n列中列中 取出取出m列，所構(gòu)成其列，所構(gòu)成其基基的個數(shù)不超過的個數(shù)不超過 m n= n！ m！(n- -m)！ m n基本可行解基本可行解的個數(shù)的個數(shù)基本解基本解的個數(shù)的個數(shù) 而問題而問題(M)的的 當當m=50，n=100時時

28、，此，此時需要求解的時需要求解的50元元50 階的線性方程組的個數(shù)為階的線性方程組的個數(shù)為 50 100 = 100！ 50！50！ 1029 這是一個天文數(shù)字！故需另尋其他有效方法。這是一個天文數(shù)字！故需另尋其他有效方法。 1.5 線性規(guī)劃的應(yīng)用模型線性規(guī)劃的應(yīng)用模型 1.5.1 生產(chǎn)計劃問題生產(chǎn)計劃問題 某企業(yè)擬用某企業(yè)擬用m種資源生產(chǎn)種資源生產(chǎn)n種產(chǎn)品種產(chǎn)品，已知第已知第i種種 資源的數(shù)量為資源的數(shù)量為bi, ,其單價為其單價為pi, ,每生產(chǎn)一個單位第每生產(chǎn)一個單位第j種種 產(chǎn)品所提供的產(chǎn)值為產(chǎn)品所提供的產(chǎn)值為vj, , 所消耗的第所消耗的第i種資源的數(shù)量種資源的數(shù)量 為為aij。第第

29、j種產(chǎn)品的合同與指令性計劃的產(chǎn)量指標為種產(chǎn)品的合同與指令性計劃的產(chǎn)量指標為 ej, , 最高需求量為最高需求量為dj。 該企業(yè)應(yīng)如何擬定生產(chǎn)計劃該企業(yè)應(yīng)如何擬定生產(chǎn)計劃？ 一、決策變量決策變量 設(shè)設(shè)xj為第為第j種產(chǎn)品的計劃產(chǎn)量種產(chǎn)品的計劃產(chǎn)量 二、約束條件約束條件 指標約束指標約束 xj ej , , j = 1, ,2, , , ,n 需求約束需求約束 xj dj , , j = 1, ,2, , , ,n 資源約束資源約束 三、目標函數(shù)目標函數(shù) 總產(chǎn)值總產(chǎn)值 1.5 線性規(guī)劃的應(yīng)用模型線性規(guī)劃的應(yīng)用模型 j=1 n aijxj bi, , i = 1, ,2, , ,m j=1 nm i

30、=1 z2=pi(aij xj) 總成本總成本 z1=vj xj n j=1 1.5 線性規(guī)劃的應(yīng)用模型線性規(guī)劃的應(yīng)用模型 i=1 =vj xj -pi(aij xj) j=1 nm j=1 n =(vj- pi aij ) xj j=1 n i=1 m 令令 cj = vj- pi aij i=1 m xj ej , , j =1, ,2, , , ,n xj dj aijxj bi, , i =1, ,2, , ,m j=1 n max z=cj xj j=1 n s.t. 則則 總利潤總利潤 z = z1 -z2 1.5.2 食譜問題食譜問題 有有n種食品種食品, 每種食品中含有每種食品

31、中含有m種營養(yǎng)成分種營養(yǎng)成分。食品用食品用 j = 1, ,2, , , ,n表示表示，養(yǎng)分用養(yǎng)分用 i = 1, ,2, , , ,m表示表示。已知第已知第 j 種種 食品單價為食品單價為 cj, 每天最大供量為每天最大供量為 dj; 而每單位第而每單位第 j種食品所含種食品所含 第第 i 種養(yǎng)分的數(shù)量為種養(yǎng)分的數(shù)量為 aij。 假定某種生物每天對第假定某種生物每天對第 i 種養(yǎng)分的種養(yǎng)分的 需求量至少為需求量至少為 bi, 而每天進食數(shù)量限定在而每天進食數(shù)量限定在 h1, , h2 范圍內(nèi)范圍內(nèi)。 試求該生物的食譜試求該生物的食譜，使總成本為最小使總成本為最小。 1.5 線性規(guī)劃的應(yīng)用模型

32、線性規(guī)劃的應(yīng)用模型 1.5 線性規(guī)劃的應(yīng)用模型線性規(guī)劃的應(yīng)用模型 設(shè)設(shè) xj 為每天提供給該生物食用的第為每天提供給該生物食用的第 j 種食品的數(shù)量，種食品的數(shù)量， 則該問題的數(shù)學模型為則該問題的數(shù)學模型為: s.t. 0 xj dj , , j=1, ,2, , ,n min z=cj xj j=1 n j=1 h1 xj h2 n j=1 aij xj bi , , i=1, ,2, , ,m n 某廠制造某種部件，由某廠制造某種部件，由2個個B1零件零件, , 3個個B2零件配套組裝零件配套組裝 而成而成。該廠有該廠有A1, , A2, , A3三種機床可加工這兩種零件三種機床可加工這兩

33、種零件，每種每種 機床的臺數(shù)機床的臺數(shù)，以及每臺機床的生產(chǎn)率如下表所示以及每臺機床的生產(chǎn)率如下表所示。 求產(chǎn)量最大的生產(chǎn)方案求產(chǎn)量最大的生產(chǎn)方案。 1.5. 3 產(chǎn)品配套問題產(chǎn)品配套問題 1.5 線性規(guī)劃的應(yīng)用模型線性規(guī)劃的應(yīng)用模型 一、決策變量一、決策變量 設(shè)以設(shè)以xij表示每臺表示每臺Ai (i=1, 2, 3)機床每個工作日加工機床每個工作日加工Bj( j = 1, 2 ) 零件的時間零件的時間(單位單位:工作日工作日)； z為為B1, B2零件按零件按 2: 3 的比例配套的數(shù)量的比例配套的數(shù)量(套套/日日)。 機床機床 種類種類 機床機床 臺數(shù)臺數(shù) 機床生產(chǎn)率機床生產(chǎn)率( 件件/日日

34、 ) 零件零件B1零件零件B2 A13 A22 A34 x11x12 x21x22 x31x32 1.5 線性規(guī)劃的應(yīng)用模型線性規(guī)劃的應(yīng)用模型 二、約束條件二、約束條件 工時約束工時約束 配套約束配套約束 機床機床 種類種類 生產(chǎn)率生產(chǎn)率( 件件/日日 ) 零件零件B1零件零件B2 A1 A2 A3 x11x12 x21x22 x31x32 z=min (60 x11+70 x21+40 x31), , (90 x12+90 x22+72x32) 1 2 1 3 z (60 x11+70 x21+40 x31) 1 2 z (90 x12+90 x22+72x32) 1 3 非線性，等價改寫成

35、：非線性，等價改寫成： 或或 x11 + x12 = 1 x21 + x22 = 1 x31 + x32 = 1 z - -35x11- -35x21- -20 x31 0 z - -30 x12- -30 x22- -24x32 0 1.5 線性規(guī)劃的應(yīng)用模型線性規(guī)劃的應(yīng)用模型 則該問題的數(shù)學模型為則該問題的數(shù)學模型為: max z s.t. x11 + x12 = 1 x21 + x22 = 1 x31 + + x32 = 1 z 35x11 35x21 20 x31 0 z 30 x12 30 x22 24x32 0 z, , x11, , x12, , x21, , x22, , x3

36、1, , x32 0 制造某種機床制造某種機床，需要需要 A, ,B, ,C三種軸件三種軸件，其規(guī)格與數(shù)量如表其規(guī)格與數(shù)量如表 所示所示，各類軸件都用各類軸件都用5.5米長的同一種圓鋼下料米長的同一種圓鋼下料。 若計劃生產(chǎn)若計劃生產(chǎn)100臺機床臺機床，最少需要用多少根圓鋼最少需要用多少根圓鋼？ 1.5. 4 下料問題下料問題 1.5 線性規(guī)劃的應(yīng)用模型線性規(guī)劃的應(yīng)用模型 軸類軸類 規(guī)格：長度（米）規(guī)格：長度（米） 每臺機床所需軸件數(shù)每臺機床所需軸件數(shù) A 3.1 1 B 2.1 2 C 4 余料余料 找出全部找出全部 省料截法省料截法 一根圓鋼所截各類軸件數(shù)一根圓鋼所截各類軸件數(shù) 截法截法 軸

37、類 軸類 軸軸 件 件 需要量需要量 A(3.1) 100 B(2.1) 200 C(1.2) 400 余料余料(米米) 23451 1 1 0 0.3 1 0 2 0 0 2 1 0.1 0 0 1 0 2 4 1 0.7 1.5 線性規(guī)劃的應(yīng)用模型線性規(guī)劃的應(yīng)用模型 min z = x1 + x2 + x3 + x4 + x5 s.t. x1 +x2 100 x1 +2x3 +x4 200 2x2 +x3 +2x4 +4x5 400 x1， x2 ， x3， x4， x5 0 則該問題的數(shù)學模型為則該問題的數(shù)學模型為: 設(shè)第設(shè)第 j 種截法下料種截法下料 xj 根。根。 1.5 線性規(guī)劃的

38、應(yīng)用模型線性規(guī)劃的應(yīng)用模型 某化工廠要用三種原料某化工廠要用三種原料 D，P，H 混合配制三種不同規(guī)格混合配制三種不同規(guī)格 的產(chǎn)品的產(chǎn)品 A，B，C。有關(guān)數(shù)據(jù)如下有關(guān)數(shù)據(jù)如下： 1.5. 5 配料問題配料問題 產(chǎn)品產(chǎn)品規(guī)規(guī) 格格單價單價(元元/kg) A 原料原料D不少于不少于50% 原料原料P不超過不超過25% 50 B 原料原料D不少于不少于25% 原料原料P不超過不超過50% 35 C不不 限限25 原料原料 最大供量最大供量 (kg/天天) 單價單價 (元元/kg) D100 P100 H60 應(yīng)如合配制應(yīng)如合配制，才能使利潤達到最大才能使利潤達到最大？ 表表1-10表表1-11 1.

39、5 線性規(guī)劃的應(yīng)用模型線性規(guī)劃的應(yīng)用模型 一、決策變量決策變量 設(shè)以設(shè)以 xij 表示每天生產(chǎn)的表示每天生產(chǎn)的 第第 j 種產(chǎn)品中所含第種產(chǎn)品中所含第 i 種原料種原料 的數(shù)量的數(shù)量(kg，右表右表)。 j i D P H A B C x11 x12 x13 x21 x22 x23 x31 x32 x33 二、約束條件二、約束條件 規(guī)格約束規(guī)格約束(據(jù)據(jù)表表1-10) x11+ x12 + x13 x11 0.50 x11+ x12 + x13 x12 0.25 x11+ x12 + x13 x21 0.25 x11+ x12 + x13 x22 0.50 1.5 線性規(guī)劃的應(yīng)用模型線性規(guī)劃的

40、應(yīng)用模型 改寫成改寫成 - - x11 + x12 + x13 0 - - x11+ 3 x12 - -x13 0 - -3 x21 +x22 + x23 0 x21 +x22 - - x23 0 資源約束資源約束(據(jù)據(jù)表表1-11) x11+ x21 + x31 100 x12+ x22 + x32 100 x13+ x23 + x33 60 1.5 線性規(guī)劃的應(yīng)用模型線性規(guī)劃的應(yīng)用模型 三、目標函數(shù)三、目標函數(shù) 總產(chǎn)值總產(chǎn)值(據(jù)據(jù)表表1-10) 產(chǎn)品產(chǎn)品A的產(chǎn)值的產(chǎn)值: 50(x11+ x12 + x13 ) 產(chǎn)品產(chǎn)品B的產(chǎn)值的產(chǎn)值: 35(x21+ x22 + x23 ) 產(chǎn)品產(chǎn)品C的產(chǎn)

41、值的產(chǎn)值: 25(x31+ x32 + x33 ) 以上三項之和即以上三項之和即總產(chǎn)值總產(chǎn)值。 總成本總成本(據(jù)據(jù)表表1-11) 原料原料D的成本的成本: (x11+ x21 + x31 ) 原料原料P的成本的成本: (x12+ x22 + x32 ) 原料原料H的成本的成本: (x13+ x23 + x33 ) 以上三項之和即以上三項之和即總成本總成本。 1.5 線性規(guī)劃的應(yīng)用模型線性規(guī)劃的應(yīng)用模型 目標函數(shù)目標函數(shù)為：為： = 總產(chǎn)值總產(chǎn)值 - - 總成本總成本 max =- -15x11+25x12+15x13- -30 x21+10 x22- -40 x31- -10 x33 該問題的

42、數(shù)學模型為該問題的數(shù)學模型為: : s.t. - - x11 +x12 + x13 0 - - x11+3x12 - - x13 0 - -3x21+x22 +x23 0 x21+x22 - - x23 0 x11 +x21 +x31 100 x12 +x22 +x32 100 x13 +x23 +x33 60 xij 0， i = 1, 2, 3； j = 1, 2, 3 l單純形法是美國運籌學家丹茨格于1947年首 創(chuàng)的求解LP問題的通用有效算法。 l是整數(shù)規(guī)劃、非線性規(guī)劃的基礎(chǔ)。 l方程組形式、表格形式、矩陣形式。 l基本思路：基于標準形LP問題。 2.1 單純形法的基本思想單純形法的基

43、本思想 2.2 單純形法的計算過程單純形法的計算過程 2.3 人工變量法人工變量法 2.4 單純形法補遺單純形法補遺 第第2章章 單純形法單純形法 2.1 單純形法的基本思想單純形法的基本思想 單純形法有三種形式：單純形法有三種形式： 方程組形式方程組形式 表格形式表格形式 矩陣形式矩陣形式 2.1.1 方程組形式的單純形法方程組形式的單純形法 ：由一個基本可行解轉(zhuǎn)化為另一個基本可行解。由一個基本可行解轉(zhuǎn)化為另一個基本可行解。 s.t. x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 = 36 x1 ， ， x2 ，x3，x4，x5 0 max z = = 3x1+

44、5x2z - -3x1 - -5x2 = 0 例例1 范例范例 等價改寫為等價改寫為 s.t. z -3x1 -5x2 = 0 x1 + +x3 = 8 2x2 +x4 = 12 3x1+4x2 +x5 = 36 x1 ， ， x2 ，x3，x4，x5 0 max z 目標方程目標方程 2.1 單純形法的基本思想單純形法的基本思想 1 0 0 0 1 0 0 0 1 當前基：當前基：m階階排列陣排列陣 目標方程目標方程中：一切基變量中：一切基變量 的系數(shù)的系數(shù) j = 0 Z - -3x1 - -5x2 = x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 = 36

45、() 0 最優(yōu)性檢驗：最優(yōu)性檢驗：j 0 ？ 初始基本可行解初始基本可行解 X0 = (0, 0, 8, 12, 36)T z0 = 排列陣排列陣： 每行每列有且僅有一個元素每行每列有且僅有一個元素 為為 ，其余元素全為，其余元素全為 的方陣。的方陣。 1 = - -3 02 = - -5 0 當前解當前解 X0 非優(yōu)；非優(yōu)； +0 x3+0 x4+0 x5 須由須由X0 轉(zhuǎn)化為另一個基本可行解轉(zhuǎn)化為另一個基本可行解 X1。 滿足滿足的的方程組方程組稱為稱為()。 ：讓：讓X0 中的一個中的一個非基變量非基變量進基進基，去替換原來的一個，去替換原來的一個（離基離基）。）。 2.1 單純形法的基

46、本思想單純形法的基本思想 x1仍為非基變量，其值為仍為非基變量，其值為0。 x3 = 8 x4 = 12 - -2x2 x5 = 36 - -4x2 x2 12/2 x2 36/4 w （） ： x2 min ，12/2，36/4 = 6 x2 = min ，12/2，36/4 = x4 x4為為離基變量離基變量 w 進基進基（）：）： 在在中選擇中選擇進基進基。 min j j0 = k xk 進基 進基 min - -3，- -5 = - -5= 2 x2 進基 進基 z -3x1 -5x2 = x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 = 36 () 0

47、 由由 有有 2.1 單純形法的基本思想單純形法的基本思想 0 主列主列 進基進基 主元主元 z - - 3x1 - - 5 x2 = 0 x1 +x3 = 8 2 x2 +x4 = 12 3x1 + 4 x2 +x5 = 36 () min 以以主列主列中中為為，同行，同行為為，求，求； 按按確定確定和和，以及，以及。 () x1 +x3 = 8 3x1 - -2x4 +x5 = 12 得得 稱為單純形法的一次稱為單純形法的一次迭代迭代。 z- - 3x1 - -5x2 = 0 x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 = 36 () 2 0 x2 + x4

48、 = 6 1 2 z -3x1 + x4 = 300 5 2 的的 是把是把變?yōu)樽優(yōu)?變變 為為1，其余變?yōu)?，其余變?yōu)?。 用用 將將X0 轉(zhuǎn)化為轉(zhuǎn)化為 另一個基本另一個基本 可行解可行解 。 2.1 單純形法的基本思想單純形法的基本思想 2.1 單純形法的基本思想單純形法的基本思想 () x1 - - x4 + x5 = 4 2 3 1 3 x2 + x4 = 6 1 2 () x1 +x3 = 8 3 x1 - -2x4 + x5 = 12 x2 + x4 = 6 1 2 z- -3x1 + x4 = 300 5 2 x3 + x4 - - x5 = 4 2 3 1 3 z + x4 +x

49、5 = 420 1 2 得得 min 1 0 2.1 單純形法的基本思想單純形法的基本思想 2.1.2 單純形法的幾何意義單純形法的幾何意義 D(0,6) O(0,0) C(4,6) B(8,3) A(8,0) x1 x2 z = 0 脊線脊線 2.2.1 單純形表單純形表 范例范例: 基于基于 cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0 比比 值值 1 0 1 0 0 x3 x4 x5 8 12 36 0 2 0 1 0 0 0 0 3 4 0 0 1 檢驗行檢驗行 35 2.2 單純形法的計算過程單純形法的計算過程 s.t. x1 + +x3 = = 8 2x2 +

50、 +x4 = = 12 3x1 + + 4x2 + +x5 = = 36 x1 ， ， x2 ，x3，x4，x5 0 max z = = 3x1+ +5x2 = T 檢驗行檢驗行 = cj , T j=1,2,n 2.2 單純形法的計算過程單純形法的計算過程 初始單純形表初始單純形表的一般形式的一般形式 2.2 單純形法的計算過程單純形法的計算過程 2.2.2 單純形法的計算步驟單純形法的計算步驟 把把LP問題化為問題化為。 在系數(shù)陣中找出或構(gòu)造一個在系數(shù)陣中找出或構(gòu)造一個作為初始作為初始 可行基，建立可行基，建立。 : 若所有檢驗數(shù)若所有檢驗數(shù)j 0，就得到一個，就得到一個 最優(yōu)基本解，停止

51、計算；否則轉(zhuǎn)最優(yōu)基本解，停止計算；否則轉(zhuǎn)4 。 : 在所有在所有j 0中中, 只要有一個只要有一個r 0 所對應(yīng)的系數(shù)列向量所對應(yīng)的系數(shù)列向量 ar 0，即一切，即一切 air 0 ， i=1, 2, , m 則該則該LP問題問題，停止計算；否則轉(zhuǎn)，停止計算；否則轉(zhuǎn)5 。 2.2 單純形法的計算過程單純形法的計算過程 先按先按 min jj 0 = aik bi ak b 2.2 單純形法的計算過程單純形法的計算過程 2 2. .2 2. .3 3 單純形法計算之例單純形法計算之例 范例范例 cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0 比比 值值 1 0 1 0 0 x

52、3 x4 x5 8 12 36 0 2 0 1 0 0 0 0 3 4 0 0 1 0 - -3 - -5 0 0 0 - - 6 9 min 2 2.2 單純形法的計算過程單純形法的計算過程 cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0 比比 值值 1 0 1 0 0 x3 x4 x5 8 12 36 0 2 0 1 0 0 0 0 3 4 0 0 1 0 - -3 - -5 0 0 0 - - 6 9 min2 x3 x2 x5 0 5 0 1/2 8 1 0 1 0 0 - -2 5/2 4 min 16000 123001 30- -3000 8 - - 2.2

53、單純形法的計算過程單純形法的計算過程 cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0 比比 值值 1 0 1 0 0 x3 x2 x5 8 6 12 0 1 0 1/2 0 0 5 0 3 0 0 - -2 1 30 - -3 0 0 5/2 0 x3 x2 x1 0 5 3 6 0 1 0 1/2 0 4 0 0 1 2/3 - -1/3 4 1 0 0 - -2/3 1/3 42 0 0 0 1/2 1 8 - - 4 min 3 X*= (4, 6, 4, 0, 0)T, z* = 42 2.2 單純形法的計算過程單純形法的計算過程 s.t. max z = 3x1+

54、2x2 -2x1 +x2 2 x1 -3x2 3 x1 ， ， x2 0 s.t. max z = 3x1+2x2 -2x1 +x2 +x3 = 2 x1 -3x2 +x4 = 3 x1， ，x2 ，x3， x4 0 cj 基基 解解 x1 x2 x3 x4 3 2 0 0 - -2 1 1 0 x3 x4 2 3 1 - -3 0 1 0 0 0 - -3 - -2 0 0 1 3 - -3 0 1 x3 x1 0 3 8 - -5 1 2 9 - -11 0 3 解無界解無界 例例2 2 求解下述求解下述LP問題問題 2.3 人工變量法人工變量法 考慮考慮標準型標準型 (M)： 分別給每個

55、約束方程分別給每個約束方程一個非負變量一個非負變量 a11x1 +a12x2+a1nxn + +xn+1 n+1 = b1 (0) a12x1 +a22x2+a2nxn + +xn+2 n+2 = b2 (0) am1x1+am2x2+amnxn + +xn+m n+m = bm(0) n個個 xn+1, xn+2, , xn+m 稱為稱為人工變量人工變量。 初始基本可行解：初始基本可行解：( ( ) ) = ( 0, 0, , 0, b1, b2, , bm )T 人造解人造解 X0 不是原不是原問題的基本可行解。問題的基本可行解。 但若能通過單純形法的迭代步驟，將虛擬但若能通過單純形法的迭

56、代步驟，將虛擬 的人工變量都替換出去，都變?yōu)榉腔兞浚吹娜斯ぷ兞慷继鎿Q出去，都變?yōu)榉腔兞浚?人工變量人工變量xn+ +1 = xn+ +2 = = xn+ +m = 0），則），則X0的的 前前n個分量就構(gòu)成原個分量就構(gòu)成原問題的一個基本可行解。問題的一個基本可行解。 反之，若經(jīng)過迭代，不能把人工變量都變反之，若經(jīng)過迭代，不能把人工變量都變 為非基變量，則表明原為非基變量，則表明原問題問題無可行解無可行解。 2.3 人工變量法人工變量法 2.3 人工變量法人工變量法 2.3.1 大大M法法 在原問題的目標函數(shù)中添上全部人工變量，并令其系數(shù)在原問題的目標函數(shù)中添上全部人工變量，并令其系數(shù)

57、都為都為- -M， 而而M是一個是一個充分大的正數(shù)充分大的正數(shù)。即。即 max z = c1x 1 + c2x 2 + c3x 3 + + cnxn M( xn+1 + xn+2 + xn+m ) 由于問題目標要求最大化，因此迭代必然趨向于把具有充分小系由于問題目標要求最大化，因此迭代必然趨向于把具有充分小系 數(shù)的人工變量從基變量中替換出去。數(shù)的人工變量從基變量中替換出去。 若迭代最終得到若迭代最終得到，而且，而且中中，則，則的的 前前n個分量就構(gòu)成原問題的一個個分量就構(gòu)成原問題的一個；否則，原問題；否則，原問題。 若迭代結(jié)果是若迭代結(jié)果是，而且，而且中中， 則原問題也則原問題也 ；否則，原問

58、題；否則，原問題。 2.3 人工變量法人工變量法 例例3 3 用大用大M法求解下述法求解下述LPLP問題問題 max z = 3x1 x2 2x3 3x1+ 2x2 3x3 = 6 x1 2x2 + x3 = 4 x1， ， x2， x3 0 max z = 3x1 x2 2x3 3x1+ 2x2 3x3 +x4 = 6 Mx4 x1 2x2 + x3 + x5 = 4 Mx5 x1， ， x2， x3 ， x4， x5 0 s.t. 解解 s.t. 2.3 人工變量法人工變量法 cj 基基 解解 x1 x2 x3 x4 x5 0 0 0 - M - M 比比 值值 3 2 - -3 1 0

59、x4 x5 6 4 1 - -2 1 0 1 - - M - - M - -10M - -4M- -3 1 2M +2 0 0 2 4 3 2 1 2/3 - -1 1/3 0 x1 x5 0 - - M 2 0 - -8/3 2 - -1/3 1 6- -2M 0 8M/3+3 - -2M- -1 4M/3+1 0 2 3 - -2 x1 x3 1 0 - - 4/3 1 -1/6 1/2 3 1 - -2/3 0 1/6 1/2 7 0 5/3 0 M+5/6 M+1/2 min X* = ( 3, 0, 1 )T, z* = 7 2.3 人工變量法人工變量法 2.3.2 兩階段法兩階段法

60、 階段階段 求解求解人造極大問題人造極大問題 max w = - -xn+1 - -xn+2 - - - -xn+m s.t. 因為人工變量因為人工變量 xn+1, xn+2, , xn+m 0 所以所以 max w 0 (1) 若若w* 0，則原問題，則原問題無可行解無可行解，停止計算；，停止計算； (2) ，且人工變量都不是基變量，則轉(zhuǎn)入，且人工變量都不是基變量，則轉(zhuǎn)入階段階段： 求解原問題求解原問題； 2.3 人工變量法人工變量法 (3) ，但，但“”存在人工變量，例如該列第存在人工變量，例如該列第 行的基變量行的基變量 xB是人工變量，同時該行的前是人工變量，同時該行的前n個系數(shù)個系數(shù)