第二章 線性規(guī)劃

1、第一章第一章 線性規(guī)劃線性規(guī)劃LINEAR PROGRAMMINGLINEAR PROGRAMMING本章的主要內(nèi)容本章的主要內(nèi)容一般線性規(guī)劃問題的數(shù)學(xué)模型一般線性規(guī)劃問題的數(shù)學(xué)模型圖解法圖解法單純形法原理單純形法原理單純形法的計(jì)算步驟單純形法的計(jì)算步驟單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論數(shù)據(jù)包絡(luò)分析數(shù)據(jù)包絡(luò)分析 School of Management Harbin Institute of Technology 2線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型規(guī)劃問題規(guī)劃問題生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排，使人力、物力等資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題線性規(guī)劃通常解

2、決以下兩類問題線性規(guī)劃通常解決以下兩類問題當(dāng)任務(wù)和目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源去完成確定的任務(wù)和目標(biāo)在一定的資源限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益School of Management Harbin Institute of Technology 3線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型School of Management Harbin Institute of Technology 4線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型 例子例子1.2 1.2 某企業(yè)計(jì)劃生產(chǎn)甲，乙兩種產(chǎn)品。這兩某企業(yè)計(jì)劃生產(chǎn)甲，乙兩種產(chǎn)品。這兩種產(chǎn)品需要在種產(chǎn)品需要在A A，

3、B B，C C三種不同的設(shè)備上進(jìn)行三種不同的設(shè)備上進(jìn)行加工。按工藝需求，加工各種產(chǎn)品所需每種設(shè)加工。按工藝需求，加工各種產(chǎn)品所需每種設(shè)備的單位工時(shí)如下表所示，問如何安排生產(chǎn)計(jì)備的單位工時(shí)如下表所示，問如何安排生產(chǎn)計(jì)劃，使企業(yè)的總利潤(rùn)最大？劃，使企業(yè)的總利潤(rùn)最大？School of Management Harbin Institute of Technology 5ABC甲甲2402乙乙2053121615線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型School of Management Harbin Institute of Technology 6線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)

4、模型線性規(guī)劃的數(shù)學(xué)模型由以下三個(gè)要素線性規(guī)劃的數(shù)學(xué)模型由以下三個(gè)要素決策變量決策變量 decision variabledecision variable目標(biāo)函數(shù)目標(biāo)函數(shù) objective functionobjective function約束條件約束條件 constrainsconstrains線性規(guī)劃問題的辨別線性規(guī)劃問題的辨別目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù)，取最大值或最小值約束條件是一組多個(gè)決策變量的線性不等式或等式School of Management Harbin Institute of Technology 7線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型School of

5、 Management Harbin Institute of Technology 8線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型School of Management Harbin Institute of Technology 9線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型標(biāo)準(zhǔn)形式的轉(zhuǎn)換標(biāo)準(zhǔn)形式的轉(zhuǎn)換目標(biāo)函數(shù)的轉(zhuǎn)換目標(biāo)函數(shù)的轉(zhuǎn)換無約束決策變量的轉(zhuǎn)換無約束決策變量的轉(zhuǎn)換約束方程的轉(zhuǎn)換約束方程的轉(zhuǎn)換 松弛變量松弛變量 剩余變量剩余變量非正決策變量的轉(zhuǎn)換非正決策變量的轉(zhuǎn)換School of Management Harbin Institute of Technology 10線性規(guī)劃問題的

6、數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型School of Management Harbin Institute of Technology 11線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型School of Management Harbin Institute of Technology 12School of Management Harbin Institute of Technology 13線性規(guī)劃數(shù)學(xué)模型假設(shè)線性規(guī)劃數(shù)學(xué)模型假設(shè)（1 1）比例性）比例性（2 2）可疊加性）可疊加性（3 3）可分性）可分性（4 4）確定性）確定性School of Management Harbin Ins

7、titute of Technology 14構(gòu)建構(gòu)建線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型（1 1）分析問題：確定決策內(nèi)容、要實(shí)）分析問題：確定決策內(nèi)容、要實(shí)現(xiàn)的目標(biāo)以及所受到的限制條件?，F(xiàn)的目標(biāo)以及所受到的限制條件。（2）具體構(gòu)造模型：選擇合適的決策具體構(gòu)造模型：選擇合適的決策變量、確定目標(biāo)函數(shù)的表達(dá)式、約變量、確定目標(biāo)函數(shù)的表達(dá)式、約束條件的表達(dá)式，分析各變量取值束條件的表達(dá)式，分析各變量取值的符號(hào)限制。的符號(hào)限制。School of Management Harbin Institute of Technology 15構(gòu)建構(gòu)建線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型例例1：某工廠在生產(chǎn)過程中需要使

8、用濃度為：某工廠在生產(chǎn)過程中需要使用濃度為80%的硫酸的硫酸100 噸，而市面上只有濃度為噸，而市面上只有濃度為30%，45%，73%，85%，92%的硫酸出售，的硫酸出售， 每噸的價(jià)格每噸的價(jià)格分別為分別為400、700、1400、1900和和2500元。元。 問：?jiǎn)枺翰捎迷鯓拥馁?gòu)買方案，才能使所需總費(fèi)用最?。坎捎迷鯓拥馁?gòu)買方案，才能使所需總費(fèi)用最??？School of Management Harbin Institute of Technology 16構(gòu)建構(gòu)建線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型例例2：設(shè)有下面四個(gè)投資機(jī)會(huì)：設(shè)有下面四個(gè)投資機(jī)會(huì)： 甲：在三年內(nèi)，投資人應(yīng)在每年年初投資，每年

9、每元投甲：在三年內(nèi)，投資人應(yīng)在每年年初投資，每年每元投資可獲利資可獲利0.2元，每年取息后可重新將本息用于投資。元，每年取息后可重新將本息用于投資。 乙：在三年內(nèi)，投資人應(yīng)在第一年年初投資，每?jī)赡昝恳遥涸谌陜?nèi)，投資人應(yīng)在第一年年初投資，每?jī)赡昝吭顿Y可獲利元投資可獲利0.5元，兩年后取息，取息后可重新將本息用元，兩年后取息，取息后可重新將本息用于投資。這種投資最多不得超過于投資。這種投資最多不得超過20,000元。元。 丙：在三年內(nèi)，投資人應(yīng)在第二年年初投資，兩年后每丙：在三年內(nèi)，投資人應(yīng)在第二年年初投資，兩年后每元投資可獲利元投資可獲利0.6元。這種投資最多不得超過元。這種投資最多不得超過

10、15,000元。元。 ?。涸谌陜?nèi)，投資人應(yīng)在第三年年初投資，一年后每丁：在三年內(nèi)，投資人應(yīng)在第三年年初投資，一年后每元投資可獲利元投資可獲利0.4元。這種投資最多不得超過元。這種投資最多不得超過10,000元。元。 假定在這三年為一期的投資中，每期的開始有假定在這三年為一期的投資中，每期的開始有30,000元元資金可供使用，問：采取怎樣的投資計(jì)劃，才能在第三年資金可供使用，問：采取怎樣的投資計(jì)劃，才能在第三年年底獲得最大收益？年底獲得最大收益？School of Management Harbin Institute of Technology 17構(gòu)建構(gòu)建線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型例

11、例3：合理下料：合理下料問題問題： ： 要制作要制作100套套鋼鋼筋架子，每套含筋架子，每套含2.9米、米、2.1米、米、1.5米的米的鋼鋼筋各一根。已知原料筋各一根。已知原料長(zhǎng)長(zhǎng)7.4米，米，問問：如何下料，使用料最：如何下料，使用料最?。渴?？方案方案下料數(shù)下料數(shù)長(zhǎng)長(zhǎng)度度2.9米米2.1米米1.5米米121221 3123合合計(jì)計(jì)(米米)7.47.37.27.16.6料料頭頭(米米)00.10.20.30.8School of Management Harbin Institute of Technology 18思考思考題題： ：目目標(biāo)標(biāo)函數(shù)是否可以函數(shù)是否可以選選取取為為 min z=x

12、1+x2+x3+x4+x5 ， ，為為什么？什么？構(gòu)建構(gòu)建線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型School of Management Harbin Institute of Technology 19構(gòu)建構(gòu)建線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型例例4 4：有：有A A、 、B B兩種兩種產(chǎn)產(chǎn)品，都需要品，都需要經(jīng)過經(jīng)過前、后兩到化學(xué)反前、后兩到化學(xué)反應(yīng)過應(yīng)過程。每種程。每種產(chǎn)產(chǎn)品需品需要的反要的反應(yīng)時(shí)間應(yīng)時(shí)間及其可供使用的及其可供使用的總時(shí)間總時(shí)間如表示。如表示。 每生每生產(chǎn)產(chǎn)一個(gè)一個(gè)單單位位產(chǎn)產(chǎn)品品B B的同的同時(shí)時(shí)，會(huì)，會(huì)產(chǎn)產(chǎn)生生2 2個(gè)個(gè)單單位的副位的副產(chǎn)產(chǎn)品品C C，且不需，且不需外加任何外

13、加任何費(fèi)費(fèi)用。副用。副產(chǎn)產(chǎn)品品C C的一部分可以出售盈利，其余的只能加以的一部分可以出售盈利，其余的只能加以銷毀銷毀。 。 副副產(chǎn)產(chǎn)品品C C每每賣賣出一個(gè)出一個(gè)單單位可位可獲獲利利3 3元，但是如果元，但是如果賣賣不出去，不出去，則則每每單單位需位需銷毀費(fèi)銷毀費(fèi)用用2 2元。元。預(yù)測(cè)預(yù)測(cè)表明，最多可售出表明，最多可售出5 5個(gè)個(gè)單單位的副位的副產(chǎn)產(chǎn)品品C C。 。 要求確定使利要求確定使利潤(rùn)潤(rùn)最大的最大的生生產(chǎn)計(jì)產(chǎn)計(jì)劃。劃。線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的解線性規(guī)劃問題的解求解線性規(guī)劃問題，就是從滿足約束條件（2）（3）的解中找出一個(gè)解，使目標(biāo)函數(shù)（1）達(dá)到最大值S

14、chool of Management Harbin Institute of Technology 20線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型School of Management Harbin Institute of Technology 21線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型 基解：某一確定的基基解：某一確定的基B B，零非基變量等于零，由約束條，零非基變量等于零，由約束條件方程（件方程（2 2）解出基變量，稱這組解為基解。在基解中）解出基變量，稱這組解為基解。在基解中，變量取非零的個(gè)數(shù)不大于方程數(shù)，變量取非零的個(gè)數(shù)不大于方程數(shù)m m。 基可行解：滿足變量非負(fù)約束的基

15、解稱為基可行解。基可行解：滿足變量非負(fù)約束的基解稱為基可行解。 可行基：對(duì)應(yīng)于基可行解的基稱為可行基?？尚谢簩?duì)應(yīng)于基可行解的基稱為可行基。School of Management Harbin Institute of Technology 22線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型有解，或無解有解，或無解解就在那里解就在那里可行才是關(guān)鍵可行才是關(guān)鍵最優(yōu)，或不優(yōu)最優(yōu)，或不優(yōu)答案就在那里答案就在那里頂點(diǎn)才能發(fā)現(xiàn)頂點(diǎn)才能發(fā)現(xiàn)School of Management Harbin Institute of Technology 23線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型School o

16、f Management Harbin Institute of Technology 24線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型基基基解基解是基可行解？是基可行解？ 目目標(biāo)標(biāo)函數(shù)函數(shù)x1x2x3x4x5P1P2P343-200否17P1P2P433040是15*P1P2P542005是14P1P3P5404015是8P1P4P5600-815否12P2P3P4036160是9P2P4P506016-15否18P3P4P500121615是0School of Management Harbin Institute of Technology 25圖解法圖解法線性規(guī)劃求解方法線性規(guī)劃求解

17、方法圖解法單純形法對(duì)于只有兩個(gè)決策變量的線性規(guī)劃問對(duì)于只有兩個(gè)決策變量的線性規(guī)劃問題，可以通過圖解的方法求解。圖解題，可以通過圖解的方法求解。圖解法簡(jiǎn)單直觀，有助于我們理解線性規(guī)法簡(jiǎn)單直觀，有助于我們理解線性規(guī)劃求解的基本原理和幾何意義。劃求解的基本原理和幾何意義。School of Management Harbin Institute of Technology 26圖解法圖解法School of Management Harbin Institute of Technology 27圖解法圖解法School of Management Harbin Institute of Techno

18、logy 28圖解法圖解法 線性規(guī)劃問題的解：唯一最優(yōu)解、無窮多最線性規(guī)劃問題的解：唯一最優(yōu)解、無窮多最優(yōu)解、無界解、無可行解優(yōu)解、無界解、無可行解 若線性規(guī)劃問題的可行域存在，則該可行域若線性規(guī)劃問題的可行域存在，則該可行域是一個(gè)凸集是一個(gè)凸集 若若LPLP的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一一定能夠在可行域（凸集）的某個(gè)頂點(diǎn)找到一定能夠在可行域（凸集）的某個(gè)頂點(diǎn)找到 解題思路是先找到凸集中的任意一點(diǎn)，計(jì)算解題思路是先找到凸集中的任意一點(diǎn)，計(jì)算目標(biāo)函數(shù)值，與周邊相鄰頂點(diǎn)目標(biāo)函數(shù)進(jìn)行目標(biāo)函數(shù)值，與周邊相鄰頂點(diǎn)目標(biāo)函數(shù)進(jìn)行比較比較School of Managem

19、ent Harbin Institute of Technology 29單純形法原理單純形法原理School of Management Harbin Institute of Technology 30單純形法原理單純形法原理School of Management Harbin Institute of Technology 31單純形法原理單純形法原理School of Management Harbin Institute of Technology 32單純形法原理單純形法原理School of Management Harbin Institute of Technology 3

20、3單純形法原理單純形法原理可行解聚成凸集可行解聚成凸集向量獨(dú)立方為基向量獨(dú)立方為基頂點(diǎn)對(duì)應(yīng)基可行頂點(diǎn)對(duì)應(yīng)基可行最優(yōu)需到基中尋最優(yōu)需到基中尋School of Management Harbin Institute of Technology 34單純形法原理單純形法原理School of Management Harbin Institute of Technology 35單純形法原理單純形法原理 從初始基可行解轉(zhuǎn)換為另一基可行解從初始基可行解轉(zhuǎn)換為另一基可行解 最優(yōu)解檢驗(yàn)和解的判斷最優(yōu)解檢驗(yàn)和解的判斷 所有檢驗(yàn)數(shù)不大于零，對(duì)應(yīng)的基可行解為最優(yōu)解 所有檢驗(yàn)數(shù)不大于零，并且某個(gè)非基變量的檢驗(yàn)數(shù)

21、等于零，則該問題有無窮多最優(yōu)解； 如果某個(gè)檢驗(yàn)數(shù)大于零，并且其對(duì)應(yīng)的約束條件系數(shù)向量的所有分量均不大于零，則該問題存在無界解。School of Management Harbin Institute of Technology 36單純形法原理單純形法原理檢驗(yàn)主要看貢獻(xiàn)檢驗(yàn)主要看貢獻(xiàn)系數(shù)比較成關(guān)鍵系數(shù)比較成關(guān)鍵目系減去基系權(quán)目系減去基系權(quán)收益不增方清閑收益不增方清閑另一非基無增減另一非基無增減只要可行無窮錢只要可行無窮錢就怕有個(gè)冒頭鳥就怕有個(gè)冒頭鳥處處作對(duì)解無邊處處作對(duì)解無邊School of Management Harbin Institute of Technology 37單純形法計(jì)

22、算步驟單純形法計(jì)算步驟 求出線性規(guī)劃的初始基可行解，列出初求出線性規(guī)劃的初始基可行解，列出初始單純形表始單純形表 進(jìn)行最優(yōu)性檢驗(yàn)進(jìn)行最優(yōu)性檢驗(yàn) 從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)函數(shù)從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)函數(shù)值更大的基可行解，列出新的單純形表值更大的基可行解，列出新的單純形表 重復(fù)第二、三步一直到計(jì)算終止重復(fù)第二、三步一直到計(jì)算終止School of Management Harbin Institute of Technology 38單純形法計(jì)算步驟單純形法計(jì)算步驟 確定換入基的變量確定換入基的變量 確定換出基的變量確定換出基的變量 用換入變量替換基變量中的換出變量用換入變量替換基變量

23、中的換出變量將主元素所在行數(shù)字除以主元素其它行變換檢驗(yàn)數(shù)變換School of Management Harbin Institute of Technology 39單純形法計(jì)算步驟單純形法計(jì)算步驟School of Management Harbin Institute of Technology 40老虎里面打蒼蠅老虎里面打蒼蠅被抓全因臺(tái)不硬被抓全因臺(tái)不硬串通一窩全被免串通一窩全被免重新洗牌新聯(lián)姻重新洗牌新聯(lián)姻豎除橫乘負(fù)后加豎除橫乘負(fù)后加新主登基換新人新主登基換新人政權(quán)是否穩(wěn)如山政權(quán)是否穩(wěn)如山照鏡檢驗(yàn)萬里行照鏡檢驗(yàn)萬里行單純形法計(jì)算步驟單純形法計(jì)算步驟School of Manageme

24、nt Harbin Institute of Technology 41單純形法計(jì)算步驟單純形法計(jì)算步驟School of Management Harbin Institute of Technology 42 人工變量法人工變量法前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組初始基可行解。但實(shí)際問題中有一些模型并不含有單位矩陣，為得到一組基向量和初始基可行解，在約束條件的等式左端（標(biāo)準(zhǔn)化后的模型）加一組虛擬變量，從而得到一組基變量。這種人為加的變量稱為人工變量，對(duì)應(yīng)的可行基稱為人工基，用大M法或兩階段法求解。School of Management Harbin Institute

25、 of Technology 43單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論School of Management Harbin Institute of Technology 44單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論School of Management Harbin Institute of Technology 45Cj-30100-M-MCB基bx1x2x3x4x5x6x70 x441111000-Mx61-21-10-110-Mx790310001cj-zj-2M-34M10-M000 x4330211-100 x21-21-10-110

26、-Mx7660403-31cj-zj6M-304M+103M-4M00 x400011-1/21/2-1/20 x23011/30001/3-3x11102/301/2-1/21/6cj-zj00303/2-M-3/2-M+1/20 x400001-1/21/2-1/20 x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cj-zj-9/2000-3/4-M+3/4-M-1/4 兩階段法兩階段法第一階段：求解一個(gè)目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃問題。令目標(biāo)函數(shù)中其他變量的系數(shù)取零，人工變量的系數(shù)取某個(gè)正的常數(shù)（一般取1），在保持原問題約束條件不變的情況下

27、求這個(gè)目標(biāo)函數(shù)極小化時(shí)的解（目標(biāo)函數(shù)為零）第二階段：當(dāng)?shù)谝浑A段有可行解時(shí)，從第一階段的最終單純形表出發(fā)，去掉人工變量，并按原問題的目標(biāo)函數(shù)繼續(xù)尋求最優(yōu)解。School of Management Harbin Institute of Technology 46單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論- -兩階段法兩階段法School of Management Harbin Institute of Technology 47單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論- -兩階段法兩階段法School of Management Harbin Insti

28、tute of Technology 48Cj00000-1-1CB基bx1x2x3x4x5x6x70 x441111000-1x61-21-10-110-1x790310001cj-zj-2400-1000 x4330211-100 x21-21-10-110-1x7660403-31cj-zj60403-400 x400011-1/21/2-1/20 x23011/30001/3-3x11102/301/2-1/21/6cj-zj00000-1-1單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論- -兩階段法兩階段法School of Management Harbin Institute of

29、Technology 49Cj-30100CB基bx1x2x3x4x50 x400011-1/20 x23011/300-3x11102/301/2cj-zj00303/20 x400001-1/20 x25/2-1/2100-1/41x33/23/20103/4cj-zj-9/2000-3/4單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論School of Management Harbin Institute of Technology 50CB基基bx1x2x3x4x53x13101/20-1/50 x4400-214/53x2301001/500-3/200CB基基bx1x2x3x4x53x141001/400 x5500-5/25/413x22011/2-1/4000-3/