《管理運(yùn)籌學(xué)》全套課件（完整版）

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

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

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

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

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

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

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

8、產(chǎn)品分別 需要需要3 3、4 4工時(shí)，三車間每天可用于生產(chǎn)這兩種產(chǎn)品的工時(shí)分別工時(shí)，三車間每天可用于生產(chǎn)這兩種產(chǎn)品的工時(shí)分別 為為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 目標(biāo)函數(shù)目標(biāo)函數(shù) x1 8 2x2 12 3x1 + 4x2 36 函數(shù)約束函數(shù)約束 x1 ， ， x2 0 非負(fù)性約束非負(fù)性約束 甲甲 乙乙 1 0 3 0 2 4 8 12 36 A B C 車間車間 產(chǎn)品產(chǎn)品 單耗（工時(shí)單耗（工時(shí)/ /件）件）最大生產(chǎn)

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

10、)不得低于不得低于4 4，2 2，5 5。甲、乙原料成本為甲、乙原料成本為 每千克每千克3 3，2 2元。元。 廠方希望總成本達(dá)到最小廠方希望總成本達(dá)到最小，則應(yīng)如何配制該產(chǎn)品則應(yīng)如何配制該產(chǎn)品？ 1.1 線性規(guī)劃的一般模型線性規(guī)劃的一般模型 成分含量 成分含量(%)(%) 原原 料 料 化學(xué)成分化學(xué)成分 甲甲 乙乙 產(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畫出目標(biāo)函數(shù)的畫出目標(biāo)函數(shù)的 等值線及其法線等值線及其法線 3確定最優(yōu)點(diǎn)確定最優(yōu)點(diǎn) 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 幾點(diǎn)說

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

14、坐標(biāo)值在圖上觀測(cè)最優(yōu)點(diǎn)坐標(biāo)值 通過解方程組得出最優(yōu)點(diǎn)坐標(biāo)值通過解方程組得出最優(yōu)點(diǎn)坐標(biāo)值 1.2 線性規(guī)劃的圖解法線性規(guī)劃的圖解法 1.2.3 幾種可能結(jié)果幾種可能結(jié)果 一、唯一解一、唯一解 如例如例1 1、例、例2 2都只有一個(gè)都只有一個(gè) 最優(yōu)點(diǎn)，屬于唯一解的情形最優(yōu)點(diǎn)，屬于唯一解的情形 s.t. max z = 3x1+4x2 x1 8 2x2 12 3x1 + 4x2 36 x1 ， ， x2 0 二二多重解多重解 z = 12 z* = 36 線段線段上無窮多個(gè)上無窮多個(gè) 點(diǎn)均為最優(yōu)解。點(diǎn)均為最優(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ī)劃的標(biāo)準(zhǔn)形式線性規(guī)劃的標(biāo)準(zhǔn)形式 1.3.1 線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性規(guī)劃問題的標(biāo)準(zhǔn)形式 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 簡(jiǎn)記為：簡(jiǎn)記為： 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ī)劃的標(biāo)準(zhǔn)形式線性規(guī)劃的標(biāo)準(zhǔn)形式 1.3.2 非標(biāo)準(zhǔn)形非標(biāo)準(zhǔn)形LP問題的標(biāo)準(zhǔn)化問題的標(biāo)準(zhǔn)化 一、目標(biāo)函數(shù)一、目標(biāo)函數(shù) min z = CTX 令令 z= z max z= CTX 例例：min z = 3x1 2x2 max z= 3x1 2x2 二、函數(shù)約束二、函數(shù)約束 bi0 兩邊同時(shí)乘以兩邊同時(shí)乘以 - -1 約束為約束為形式形式 加上加上松弛變量松弛變量

17、約束為約束為形式形式 減去減去剩余變量剩余變量 三、決策變量三、決策變量 若若xk 0, , 令令 xk = xk, ,則則 xk 0 若若xk為為自由變量自由變量, , 令令 xk = xk xk且且 xk, ,xk 0 x x* f (x) - - f (x) 1.3 線性規(guī)劃的標(biāo)準(zhǔn)形式線性規(guī)劃的標(biāo)準(zhǔn)形式 = 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ī)劃的標(biāo)準(zhǔn)形式線性規(guī)劃的標(biāo)準(zhǔn)形式 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問題化成標(biāo)準(zhǔn)形問題化成標(biāo)準(zhǔn)形 1.3 線性規(guī)劃的標(biāo)準(zhǔn)形式線性規(guī)劃的標(biāo)準(zhǔn)形式 令令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)解: : 滿足目標(biāo)要求的可行解滿足目標(biāo)要求的可行解X。 三、三、基本解基

20、本解: : 只適用于標(biāo)準(zhǔn)形只適用于標(biāo)準(zhǔn)形LP問題問題（M）。）。 (1) 基基(矩陣矩陣) AX = b 設(shè)設(shè) 為為A的一個(gè)的一個(gè)m階子矩陣，若階子矩陣，若| | |0,|0,則稱則稱 為約束方程組為約束方程組AX=b或標(biāo)準(zhǔn)形或標(biāo)準(zhǔn)形LP問題問題(M)的一個(gè)的一個(gè) 基（矩陣）基（矩陣）。 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）, ,這時(shí)這時(shí) 稱稱 a3 , ,a4 , ,a5 為

21、為基向量基向量，而，而 a1 , ,a2 為為非基向量非基向量；稱稱 x3 , ,x4 , ,x5 為為基變量基變量，而，而 x1 , ,x2 為為非基變量非基變量。 1.4 線性規(guī)劃的解及其性質(zhì)線性規(guī)劃的解及其性質(zhì) (2) (2) 基本解基本解 的標(biāo)準(zhǔn)形的標(biāo)準(zhǔn)形 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 稱為一個(gè)稱為一個(gè)(關(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 等等等等。 四、四、基本可行解基本可行解 滿足非負(fù)性約束的基本解滿足非負(fù)性約束的基本解。 如如 X0 ， ， X2 ；

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

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

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

26、, s,且且，則稱則稱 = + + 為點(diǎn)為點(diǎn) 的一個(gè)的一個(gè)凸組合凸組合。 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)的一個(gè)基本可行解與可行域的一個(gè)基本可行解與可行域 R 的一個(gè)極點(diǎn)的一個(gè)極點(diǎn) 互相對(duì)應(yīng)?；ハ鄬?duì)應(yīng)。 3： 對(duì)于一個(gè)給定的標(biāo)準(zhǔn)型對(duì)于一個(gè)給定的標(biāo)準(zhǔn)型LP問題問題(M)來說：來說： 若若(M)有可行解，則必有基本可行解；有可行解，則必有基本可行解； 若若(M)有最優(yōu)解，則必有最優(yōu)基本解。有最優(yōu)解，則必有最優(yōu)基

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

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

29、j種產(chǎn)品的合同與指令性計(jì)劃的產(chǎn)量指標(biāo)為種產(chǎn)品的合同與指令性計(jì)劃的產(chǎn)量指標(biāo)為 ej, , 最高需求量為最高需求量為dj。 該企業(yè)應(yīng)如何擬定生產(chǎn)計(jì)劃該企業(yè)應(yīng)如何擬定生產(chǎn)計(jì)劃？ 一、決策變量決策變量 設(shè)設(shè)xj為第為第j種產(chǎn)品的計(jì)劃產(chǎn)量種產(chǎn)品的計(jì)劃產(chǎn)量 二、約束條件約束條件 指標(biāo)約束指標(biāo)約束 xj ej , , j = 1, ,2, , , ,n 需求約束需求約束 xj dj , , j = 1, ,2, , , ,n 資源約束資源約束 三、目標(biāo)函數(shù)目標(biāo)函數(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. 則則 總利潤(rùn)總利潤(rùn) z = z1 -z2 1.5.2 食譜問題食譜問題 有有n種食品種食品, 每種食品中含有每種食品

31、中含有m種營(yíng)養(yǎng)成分種營(yíng)養(yǎng)成分。食品用食品用 j = 1, ,2, , , ,n表示表示，養(yǎng)分用養(yǎng)分用 i = 1, ,2, , , ,m表示表示。已知第已知第 j 種種 食品單價(jià)為食品單價(jià)為 cj, 每天最大供量為每天最大供量為 dj; 而每單位第而每單位第 j種食品所含種食品所含 第第 i 種養(yǎng)分的數(shù)量為種養(yǎng)分的數(shù)量為 aij。 假定某種生物每天對(duì)第假定某種生物每天對(duì)第 i 種養(yǎng)分的種養(yǎng)分的 需求量至少為需求量至少為 bi, 而每天進(jìn)食數(shù)量限定在而每天進(jìn)食數(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ù)學(xué)模型為則該問題的數(shù)學(xué)模型為: 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個(gè)個(gè)B1零件零件, , 3個(gè)個(gè)B2零件配套組裝零件配套組裝 而成而成。該廠有該廠有A1, , A2, , A3三種機(jī)床可加工這兩種零件三種機(jī)床可加工這兩

33、種零件，每種每種 機(jī)床的臺(tái)數(shù)機(jī)床的臺(tái)數(shù)，以及每臺(tái)機(jī)床的生產(chǎn)率如下表所示以及每臺(tái)機(jī)床的生產(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表示每臺(tái)表示每臺(tái)Ai (i=1, 2, 3)機(jī)床每個(gè)工作日加工機(jī)床每個(gè)工作日加工Bj( j = 1, 2 ) 零件的時(shí)間零件的時(shí)間(單位單位:工作日工作日)； z為為B1, B2零件按零件按 2: 3 的比例配套的數(shù)量的比例配套的數(shù)量(套套/日日)。 機(jī)床機(jī)床 種類種類 機(jī)床機(jī)床 臺(tái)數(shù)臺(tái)數(shù) 機(jī)床生產(chǎn)率機(jī)床生產(chǎn)率( 件件/日日

34、 ) 零件零件B1零件零件B2 A13 A22 A34 x11x12 x21x22 x31x32 1.5 線性規(guī)劃的應(yīng)用模型線性規(guī)劃的應(yīng)用模型 二、約束條件二、約束條件 工時(shí)約束工時(shí)約束 配套約束配套約束 機(jī)床機(jī)床 種類種類 生產(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 非線性，等價(jià)改寫成

35、：非線性，等價(jià)改寫成： 或或 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ù)學(xué)模型為則該問題的數(shù)學(xué)模型為: 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 制造某種機(jī)床制造某種機(jī)床，需要需要 A, ,B, ,C三種軸件三種軸件，其規(guī)格與數(shù)量如表其規(guī)格與數(shù)量如表 所示所示，各類軸件都用各類軸件都用5.5米長(zhǎng)的同一種圓鋼下料米長(zhǎng)的同一種圓鋼下料。 若計(jì)劃生產(chǎn)若計(jì)劃生產(chǎn)100臺(tái)機(jī)床臺(tái)機(jī)床，最少需要用多少根圓鋼最少需要用多少根圓鋼？ 1.5. 4 下料問題下料問題 1.5 線性規(guī)劃的應(yīng)用模型線性規(guī)劃的應(yīng)用模型 軸類軸類 規(guī)格：長(zhǎng)度（米）規(guī)格：長(zhǎng)度（米） 每臺(tái)機(jī)床所需軸件數(shù)每臺(tái)機(jī)床所需軸件數(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ù)學(xué)模型為則該問題的數(shù)學(xué)模型為: 設(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ī) 格格單價(jià)單價(jià)(元元/kg) A 原料原料D不少于不少于50% 原料原料P不超過不超過25% 50 B 原料原料D不少于不少于25% 原料原料P不超過不超過50% 35 C不不 限限25 原料原料 最大供量最大供量 (kg/天天) 單價(jià)單價(jià) (元元/kg) D100 P100 H60 應(yīng)如合配制應(yīng)如合配制，才能使利潤(rùn)達(dá)到最大才能使利潤(rùn)達(dá)到最大？ 表表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)用模型 三、目標(biāo)函數(shù)三、目標(biāo)函數(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 ) 以上三項(xiàng)之和即以上三項(xiàng)之和即總產(chǎn)值總產(chǎn)值。 總成本總成本(據(jù)據(jù)表表1-11) 原料原料D的成本的成本: (x11+ x21 + x31 ) 原料原料P的成本的成本: (x12+ x22 + x32 ) 原料原料H的成本的成本: (x13+ x23 + x33 ) 以上三項(xiàng)之和即以上三項(xiàng)之和即總成本總成本。 1.5 線性規(guī)劃的應(yīng)用模型線性規(guī)劃的應(yīng)用模型 目標(biāo)函數(shù)目標(biāo)函數(shù)為：為： = 總產(chǎn)值總產(chǎn)值 - - 總成本總成本 max =- -15x11+25x12+15x13- -30 x21+10 x22- -40 x31- -10 x33 該問題的

42、數(shù)學(xué)模型為該問題的數(shù)學(xué)模型為: : 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單純形法是美國(guó)運(yùn)籌學(xué)家丹茨格于1947年首 創(chuàng)的求解LP問題的通用有效算法。 l是整數(shù)規(guī)劃、非線性規(guī)劃的基礎(chǔ)。 l方程組形式、表格形式、矩陣形式。 l基本思路：基于標(biāo)準(zhǔn)形LP問題。 2.1 單純形法的基本思想單純形法的基

43、本思想 2.2 單純形法的計(jì)算過程單純形法的計(jì)算過程 2.3 人工變量法人工變量法 2.4 單純形法補(bǔ)遺單純形法補(bǔ)遺 第第2章章 單純形法單純形法 2.1 單純形法的基本思想單純形法的基本思想 單純形法有三種形式：?jiǎn)渭冃畏ㄓ腥N形式： 方程組形式方程組形式 表格形式表格形式 矩陣形式矩陣形式 2.1.1 方程組形式的單純形法方程組形式的單純形法 ：由一個(gè)基本可行解轉(zhuǎn)化為另一個(gè)基本可行解。由一個(gè)基本可行解轉(zhuǎn)化為另一個(gè)基本可行解。 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 范例范例 等價(jià)改寫為等價(jià)改寫為 s.t. z -3x1 -5x2 = 0 x1 + +x3 = 8 2x2 +x4 = 12 3x1+4x2 +x5 = 36 x1 ， ， x2 ，x3，x4，x5 0 max z 目標(biāo)方程目標(biāo)方程 2.1 單純形法的基本思想單純形法的基本思想 1 0 0 0 1 0 0 0 1 當(dāng)前基：當(dāng)前基：m階階排列陣排列陣 目標(biāo)方程目標(biāo)方程中：一切基變量中：一切基變量 的系數(shù)的系數(shù) j = 0 Z - -3x1 - -5x2 = x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 = 36

45、() 0 最優(yōu)性檢驗(yàn)：最優(yōu)性檢驗(yàn)：j 0 ？ 初始基本可行解初始基本可行解 X0 = (0, 0, 8, 12, 36)T z0 = 排列陣排列陣： 每行每列有且僅有一個(gè)元素每行每列有且僅有一個(gè)元素 為為 ，其余元素全為，其余元素全為 的方陣。的方陣。 1 = - -3 02 = - -5 0 當(dāng)前解當(dāng)前解 X0 非優(yōu)；非優(yōu)； +0 x3+0 x4+0 x5 須由須由X0 轉(zhuǎn)化為另一個(gè)基本可行解轉(zhuǎn)化為另一個(gè)基本可行解 X1。 滿足滿足的的方程組方程組稱為稱為()。 ：讓：讓X0 中的一個(gè)中的一個(gè)非基變量非基變量進(jìn)基進(jìn)基，去替換原來的一個(gè)，去替換原來的一個(gè)（離基離基）。）。 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 進(jìn)基進(jìn)基（）：）： 在在中選擇中選擇進(jìn)基進(jìn)基。 min j j0 = k xk 進(jìn)基 進(jìn)基 min - -3，- -5 = - -5= 2 x2 進(jìn)基 進(jìn)基 z -3x1 -5x2 = x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 = 36 () 0

47、 由由 有有 2.1 單純形法的基本思想單純形法的基本思想 0 主列主列 進(jìn)基進(jìn)基 主元主元 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)化為 另一個(gè)基本另一個(gè)基本 可行解可行解 。 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 檢驗(yàn)行檢驗(yàn)行 35 2.2 單純形法的計(jì)算過程單純形法的計(jì)算過程 s.t. x1 + +x3 = = 8 2x2 +

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

51、計(jì)算；否則轉(zhuǎn)最優(yōu)基本解，停止計(jì)算；否則轉(zhuǎn)4 。 : 在所有在所有j 0中中, 只要有一個(gè)只要有一個(gè)r 0 所對(duì)應(yīng)的系數(shù)列向量所對(duì)應(yīng)的系數(shù)列向量 ar 0，即一切，即一切 air 0 ， i=1, 2, , m 則該則該LP問題問題，停止計(jì)算；否則轉(zhuǎn)，停止計(jì)算；否則轉(zhuǎn)5 。 2.2 單純形法的計(jì)算過程單純形法的計(jì)算過程 先按先按 min jj 0 = aik bi ak b 2.2 單純形法的計(jì)算過程單純形法的計(jì)算過程 2 2. .2 2. .3 3 單純形法計(jì)算之例單純形法計(jì)算之例 范例范例 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 單純形法的計(jì)算過程單純形法的計(jì)算過程 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、單純形法的計(jì)算過程單純形法的計(jì)算過程 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 單純形法的計(jì)算過程單純形法的計(jì)算過程 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 人工變量法人工變量法 考慮考慮標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型 (M)： 分別給每個(gè)

55、約束方程分別給每個(gè)約束方程一個(gè)非負(fù)變量一個(gè)非負(fù)變量 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個(gè)個(gè) 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è)分量就構(gòu)成原個(gè)分量就構(gòu)成原問題的一個(gè)基本可行解。問題的一個(gè)基本可行解。 反之，若經(jīng)過迭代，不能把人工變量都變反之，若經(jīng)過迭代，不能把人工變量都變 為非基變量，則表明原為非基變量，則表明原問題問題無可行解無可行解。 2.3 人工變量法人工變量法 2.3 人工變量法人工變量法 2.3.1 大大M法法 在原問題的目標(biāo)函數(shù)中添上全部人工變量，并令其系數(shù)在原問題的目標(biāo)函數(shù)中添上全部人工變量，并令其系數(shù)

57、都為都為- -M， 而而M是一個(gè)是一個(gè)充分大的正數(shù)充分大的正數(shù)。即。即 max z = c1x 1 + c2x 2 + c3x 3 + + cnxn M( xn+1 + xn+2 + xn+m ) 由于問題目標(biāo)要求最大化，因此迭代必然趨向于把具有充分小系由于問題目標(biāo)要求最大化，因此迭代必然趨向于把具有充分小系 數(shù)的人工變量從基變量中替換出去。數(shù)的人工變量從基變量中替換出去。 若迭代最終得到若迭代最終得到，而且，而且中中，則，則的的 前前n個(gè)分量就構(gòu)成原問題的一個(gè)個(gè)分量就構(gòu)成原問題的一個(gè)；否則，原問題；否則，原問題。 若迭代結(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. 因?yàn)槿斯ぷ兞恳驗(yàn)槿斯ぷ兞?xn+1, xn+2, , xn+m 0 所以所以 max w 0 (1) 若若w* 0，則原問題，則原問題無可行解無可行解，停止計(jì)算；，停止計(jì)算； (2) ，且人工變量都不是基變量，則轉(zhuǎn)入，且人工變量都不是基變量，則轉(zhuǎn)入階段階段： 求解原問題求解原問題； 2.3 人工變量法人工變量法 (3) ，但，但“”存在人工變量，例如該列第存在人工變量，例如該列第 行的基變量行的基變量 xB是人工變量，同時(shí)該行的前是人工變量，同時(shí)該行的前n個(gè)系數(shù)個(gè)系數(shù)