4-2 線性規(guī)劃簡介.ppt

1、文 科 數(shù) 學(xué),2 線性規(guī)劃簡介,一、線性規(guī)劃問題舉例,二、圖解法,三、線性規(guī)劃的標(biāo)準(zhǔn)型,四、線性規(guī)劃解的概念,五、單純形法,六、線性規(guī)劃的應(yīng)用,文 科 數(shù) 學(xué),線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支。由前蘇聯(lián)經(jīng)濟(jì)學(xué)家康托洛維奇于1939年提出，而此人也因此獲得1960年的諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。,線性規(guī)劃是一類特殊的最優(yōu)化問題，它是針對一類有限資源如何合理利用這樣的問題而提出的。,1947年，G. B. Dantzig 提出求線性規(guī)劃的單純形法（simple method），理論上趨向成熟，實(shí)際上的應(yīng)用也越來越廣泛。,文 科 數(shù) 學(xué),例1. 生產(chǎn)計(jì)劃問題 某企業(yè)要在計(jì)劃期內(nèi)安排生產(chǎn)甲、乙兩種產(chǎn)品，該企業(yè)現(xiàn)有

2、生產(chǎn)資料：設(shè)備18臺時(shí)，原材料A 4噸，原材料 B 12噸；已知單位產(chǎn)品所需消耗的生產(chǎn)資料及利潤如下表。 問應(yīng)如何確定生產(chǎn)計(jì)劃使企業(yè)獲利最多？,一、線性規(guī)劃問題舉例,文 科 數(shù) 學(xué),問題的分析 首先明確要決策什么確定產(chǎn)品甲、乙的生產(chǎn)量 為了定量分析解決該問題，應(yīng)先建立數(shù)學(xué)模型 設(shè) x1 , x2 分別表示甲、乙兩種產(chǎn)品的產(chǎn)量，稱為決策變量 用一組決策變量 (x1, x2)T 表示一個(gè)方案，變量的不同取值表示不同的方案（目標(biāo)：尋找最優(yōu)方案） 其次分析 x1, x2 應(yīng)滿足什么條件，才能使生產(chǎn)正常進(jìn)行 由于現(xiàn)有的生產(chǎn)資料總量是有限的，因此：正常生產(chǎn)過程中生產(chǎn)資料的消耗不能超過現(xiàn)有量,文 科 數(shù) 學(xué)

3、,x1, x2 應(yīng)同時(shí)滿足下列條件： 設(shè)備臺時(shí)限制： 原材料A限制： 原材料B限制： 由于產(chǎn)品產(chǎn)量不能是負(fù)的，故有非負(fù)限制：,文 科 數(shù) 學(xué),x1, x2 應(yīng)同時(shí)滿足下列條件： 設(shè)備臺時(shí)限制： 原材料A限制： 原材料B限制： 由于產(chǎn)品產(chǎn)量不能是負(fù)的，故有非負(fù)限制： 該生產(chǎn)計(jì)劃的總利潤為： 現(xiàn)在的問題是：找出 x1, x2 ，在上述各種條件的限制下，使 z 達(dá)到最大值,文 科 數(shù) 學(xué),該生產(chǎn)計(jì)劃問題的數(shù)學(xué)模型,文 科 數(shù) 學(xué),一般的資源合理利用問題 設(shè)某企業(yè)利用 m 種資源來生產(chǎn) n 種產(chǎn)品，已知該企業(yè)擁有的第 i 種資源的數(shù)量是 bi, 生產(chǎn)單位第 j 種產(chǎn)品所消耗的第 i 種資源的數(shù)量為 a

4、ij，第 j 種產(chǎn)品的單位利潤為 cj。 現(xiàn)制定一個(gè)生產(chǎn)計(jì)劃方案，使總利潤最大。 注：常用術(shù)語 aij：技術(shù)系數(shù)，bi：資源系數(shù)，cj：價(jià)值系數(shù) 用 xj 表示第 j 種產(chǎn)品的生產(chǎn)量,文 科 數(shù) 學(xué),一般的資源合理利用問題的數(shù)學(xué)模型,文 科 數(shù) 學(xué),例2. 人員分配問題 設(shè)某單位現(xiàn)有 n 個(gè)人員A1, A2, , An 來完成 n 項(xiàng)工作B1, B2, , Bn。按工作要求，每個(gè)人員需干一項(xiàng)工作，每項(xiàng)工作也需一人去完成；已知人員Ai 做工作Bj 的效率是 cij。 問應(yīng)如何分配，才使總效率最好？ 問題的分析 令 xij 表示分配人員 Ai 完成工作 Bj 的決策變量， xij = 1 表示分配

5、 Ai 干工作 Bj xij = 0 表示不分配 Ai 干工作 Bj 按問題要求：每人要做一項(xiàng)工作，每項(xiàng)工作需一人去做。,文 科 數(shù) 學(xué),令 xij 表示分配人員 Ai 完成工作 Bj 的決策變量， xij = 1 表示分配 Ai 干工作 Bj xij = 0 表示不分配 Ai 干工作 Bj 按問題要求：每人要做一項(xiàng)工作，每項(xiàng)工作需一人去做。 對人員 Ai，要求承擔(dān)一項(xiàng)工作： 對工作 Bj，要求一人去完成： 派工方案的總效益：,文 科 數(shù) 學(xué),人員分配問題的數(shù)學(xué)模型,文 科 數(shù) 學(xué),例3. 物資運(yùn)輸問題 某公司要運(yùn)銷一種物資。該物資有甲、乙兩個(gè)產(chǎn)地，產(chǎn)量分別是2000噸、1000噸；另有A、B

6、、C三個(gè)銷地，銷量分別是1700噸、1100噸、200噸；已知該物資的單位運(yùn)價(jià)如下表。 問應(yīng)如何確定調(diào)運(yùn)方案，才能使在產(chǎn)銷平衡的條件下，總運(yùn)費(fèi)最低？,文 科 數(shù) 學(xué),問題的分析 確定調(diào)運(yùn)方案就是確定從不同產(chǎn)地到各個(gè)銷地的運(yùn)輸量。 假設(shè) A 地：x11 A 地：x21 甲地運(yùn)往 B 地：x12 乙地運(yùn)往 B 地：x22 C 地：x13 C 地：x23 由于要求產(chǎn)銷平衡： .從兩產(chǎn)地甲、乙分別調(diào)往三銷地A、B、C的物資數(shù)量應(yīng)該分別等于兩產(chǎn)地的產(chǎn)量，故 xij 應(yīng)滿足：,文 科 數(shù) 學(xué),由于要求產(chǎn)銷平衡： .運(yùn)到A、B、C三銷地的物資數(shù)量應(yīng)分別等于三銷地的銷量，故 xij 還應(yīng)滿足： 顯然： 調(diào)運(yùn)方

7、案的總運(yùn)費(fèi)為：,文 科 數(shù) 學(xué),產(chǎn)銷平衡下運(yùn)費(fèi)最省的調(diào)運(yùn)問題的數(shù)學(xué)模型,文 科 數(shù) 學(xué),上述例子表明 規(guī)劃問題的數(shù)學(xué)模型由三個(gè)要素組成： .變量(決策變量)，是問題中要確定的未知量，用以表明規(guī)劃中用數(shù)量表示的方案、措施等，可由決策者決定和控制； .目標(biāo)函數(shù)，是決策變量的函數(shù)，按優(yōu)化目標(biāo)分別在該函數(shù)前加上 max 或 min； .約束條件，指決策變量取值時(shí)受到的各種條件的限制，通常表達(dá)為含決策變量的等式或不等式。 如果規(guī)劃問題的數(shù)學(xué)模型中，目標(biāo)函數(shù)是決策變量的線性函數(shù)，約束條件是含決策變量的線性等式或不等式，則該類規(guī)劃問題的數(shù)學(xué)模型稱為線性規(guī)劃的數(shù)學(xué)模型。,文 科 數(shù) 學(xué),一般線性規(guī)劃問題的數(shù)學(xué)

8、模型,文 科 數(shù) 學(xué),二、圖解法 圖解法適用于求解只有兩個(gè)變量的線性規(guī)劃問題 圖解法簡單直觀，有助于我們了解線性規(guī)劃問題求解的基本原理和思想。,文 科 數(shù) 學(xué),1.圖解法的步驟 .在平面上建立直角坐標(biāo)系； .圖示約束條件，找出可行域； .圖示目標(biāo)函數(shù)并尋找最優(yōu)解。 下面舉例說明圖解法求解線性規(guī)劃問題的步驟。 例1.利用圖解法求解線性規(guī)劃問題(生產(chǎn)計(jì)劃問題),文 科 數(shù) 學(xué),可行域 Q,3x1+5x2= z =36,3x1+5x2= z =20,3x1+5x2= z =0,圖解法解題過程,文 科 數(shù) 學(xué),結(jié)論 最優(yōu)生產(chǎn)方案為： 生產(chǎn)產(chǎn)品甲2件，生產(chǎn)產(chǎn)品乙6件；最大利潤為36萬元。 注：本問題只有

9、唯一最優(yōu)解。 練習(xí).利用圖解法求解線性規(guī)劃問題,文 科 數(shù) 學(xué),-x1+x2=0,x1+x2=5,6x1+2x2=21,3x1 + x2 = z =0,3x1 + x2 = z =6,3x1 + x2 = z =21/2,A (11/4, 9/4),B (21/6,0),注：本問題有無窮多個(gè)最優(yōu)解。,圖解法解題過程,文 科 數(shù) 學(xué),例2.利用圖解法求解線性規(guī)劃問題 該問題的可行域 是一個(gè)無界的凸多 邊形。 注：本問題有可 行解，但無最優(yōu)解， 稱為無界解。,文 科 數(shù) 學(xué),例3.利用圖解法求解線性規(guī)劃問題 該問題的可行域是 空集，即無可行解。 注：本問題無可行 解，更無最優(yōu)解。,x1-x2=-1

10、,x1+x2=-1,文 科 數(shù) 學(xué),2.線性規(guī)劃問題求解的幾種可能結(jié)局 .有唯一的最優(yōu)解：最優(yōu)解是可行域的一個(gè)頂點(diǎn) .有無窮多最優(yōu)解：最優(yōu)解是可行域的一段邊界 .無界解(有可行解，但無最優(yōu)解)：產(chǎn)生無界解的原因在于建立實(shí)際問題的數(shù)學(xué)模型時(shí)遺漏了某些必要的約束條件； .無可行解：產(chǎn)生原因在于模型的約束條件之間存在矛盾，建模時(shí)有錯(cuò)誤。 一般線性規(guī)劃問題也有類似結(jié)論，但結(jié)論成立的判定準(zhǔn)則如何？,文 科 數(shù) 學(xué),3.圖解法的啟示 圖解法的解題思路和幾何直觀上得到的一些概念和判斷，對后面求解一般線性規(guī)劃問題的單純形法有很大啟示： .解的情況：唯一最優(yōu)解，無窮多最優(yōu)解，無界解，無可行解； .若線性規(guī)劃問題的可行域存在，則可行域是一個(gè)凸集； .若線性規(guī)劃問題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一是可行域凸集的某個(gè)頂點(diǎn)；,文 科 數(shù) 學(xué),3.圖解法的啟