第二章 線性規(guī)劃.ppt

1、第二章 線性規(guī)劃,2.1線性規(guī)劃問題及其模型 2.2.1線性規(guī)劃圖解法 2.2.2 線性規(guī)劃解的性質(zhì) 2.3單純形法原理 2.4單純形法計(jì)算步驟 2.5.1單純形法的進(jìn)一步討論,線性規(guī)劃問題的提出 線性規(guī)劃的基本概念 線性規(guī)劃的數(shù)學(xué)模型 線性規(guī)劃問題的標(biāo)準(zhǔn)形式,2.1 線性規(guī)劃問題及其數(shù)學(xué)模型,問題的提出,例: 生產(chǎn)計(jì)劃問題,決策變量（Decision variables） 目標(biāo)函數(shù)（Objective function） 約束條件（Constraint conditions） 可行域（Feasible region) 最優(yōu)解（Optimal solution),基本概念,問題中要確定的未知量

2、，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。,它是決策變量的函數(shù),指決策變量取值時(shí)受到的各種資源條件的限制，通常表達(dá)為含決策變量的等式或不等式。,滿足約束條件的決策變量的取值范圍,可行域中使目標(biāo)函數(shù)達(dá)到最優(yōu)的決策變量的值,是問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。,第1步 -確定決策變量,設(shè) I的產(chǎn)量 II的產(chǎn)量 利潤,第2步 -定義目標(biāo)函數(shù),Max Z = x1 + x2,Max Z = 2 x1 + 3 x2,第2步 -定義目標(biāo)函數(shù),第3步 -表示約束條件,x1 + 2 x2 8 4 x1 16 4 x2 12 x1、 x2 0,該計(jì)

3、劃的數(shù)學(xué)模型,目標(biāo)函數(shù) Max Z = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,x1,x2,線性規(guī)劃問題的共同特征,一組決策變量X表示一個方案,一般X大于等于零。 約束條件是線性等式或不等式。 目標(biāo)函數(shù)是線性的。 求目標(biāo)函數(shù)最大化或最小化,線性規(guī)劃模型的一般形式,線性規(guī)劃問題的標(biāo)準(zhǔn)形式,標(biāo)準(zhǔn)形式為:,目標(biāo)函數(shù)最小 約束條件等式 決策變量非負(fù),簡寫為,用向量表示,用矩陣表示,C價(jià)值向量 b資源向量 X決策變量向量,max f=CX 等價(jià)于 min f = -CX “” 約束：加入非負(fù)松馳變量,一般線性規(guī)劃問題的標(biāo)準(zhǔn)化,例：,目標(biāo)函數(shù) Ma

4、x f = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,max Z=CX 等價(jià)于 min Z = -CX “” 約束：加入非負(fù)松馳變量,一般線性規(guī)劃問題的標(biāo)準(zhǔn)形化,例：,Min,“” 約束： 減去非負(fù)剩余變量；,例 ：,可正可負(fù)（即無約束）；,解 ：標(biāo)準(zhǔn)形為,圖解法 線性規(guī)劃問題求解的 幾種可能結(jié)果 由圖解法得到的啟示,2.2.1 線性規(guī)劃的圖解法,例1的數(shù)學(xué)模型,目標(biāo)函數(shù) Max f = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,x1,x2,9 8 7 6 5 4 3 2 1 0,|

5、 123456789,x1,x2,x1 + 2x2 8,目標(biāo)函數(shù) Max f = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,4x1 16,4 x2 12,圖解法,9 8 7 6 5 4 3 2 1 0,x2,目標(biāo)函數(shù) Max f = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,可行域,圖解法,9 8 7 6 5 4 3 2 1 0,| 123456789,x1,x2,目標(biāo)函數(shù) Max f = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2

6、0,可行域,圖解法,9 8 7 6 5 4 3 2 1 0,x2,目標(biāo)函數(shù) Max f = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,2x1 + 3x2 = 6,圖解法,9 8 7 6 5 4 3 2 1 0,x2,目標(biāo)函數(shù) Max f = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,x1+ 2x2=8 4x1 =16,圖解法,圖解法求解步驟,由全部約束條件作圖求出可行域； 作目標(biāo)函數(shù)等值線，確定使目標(biāo)函數(shù)最優(yōu)的移動方向； 平移目標(biāo)函數(shù)的等值線，找出最優(yōu)點(diǎn)，算出最優(yōu)值。,線性規(guī)劃問題求

7、解的 幾種可能結(jié)果,(a) 唯一最優(yōu)解,(b)無窮多最優(yōu)解,線性規(guī)劃問題求解的 幾種可能結(jié)果,(c)無界解 Max f = x1 + x2 -2x1 + x2 4 x1 - x2 2 x1、 x2 0,x1,線性規(guī)劃問題求解的 幾種可能結(jié)果,(d)無可行解 Max f = 2x1 + 3x2 x1 +2 x2 8 4 x1 16 4x2 12 -2x1 + x2 4 x1、 x2 0 可行域?yàn)榭占?線性規(guī)劃問題求解的 幾種可能結(jié)果,練習(xí)：用圖解法求解LP問題,圖解法 （練習(xí)）,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,x2,4x1 + 6x2 4

8、8,2x1 + 2x2 18,2x1 + x2 16,圖解法 （練習(xí)）,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,可行域,A,B,C,D,E,圖解法 （練習(xí)）,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),34x1 + 40 x2 = 272,圖解法 （練習(xí)）,18 16 14 12 10 8

9、6 4 2 0,| 24681012141618,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),圖解法 （練習(xí)）,x2,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),最優(yōu)解 (3,6),4x1+ 6x2=48 2x1+ 2x2 =18,圖解法的幾點(diǎn)結(jié)論:（由圖解法得到的啟示）,可行域是有界或無界的凸多邊形。 若線性規(guī)劃問題存在最優(yōu)解，它一定

10、可以在可行域的頂點(diǎn)得到。 若兩個頂點(diǎn)同時(shí)得到最優(yōu)解，則其連線上的所有點(diǎn)都是最優(yōu)解。 解題思路：找出凸集的頂點(diǎn)，計(jì)算其目標(biāo)函數(shù)值，比較即得。,2.2.2 線性規(guī)劃解的性質(zhì),線性規(guī)劃解的概念 線性規(guī)劃問題的幾何意義 （單純形法原理）,線性規(guī)劃問題解的概念,標(biāo)準(zhǔn)型 可行解:滿足AX=b, X=0的解X稱為線性規(guī)劃問題的可行解。 最優(yōu)解：使f=CX達(dá)到最小值的可行解稱為最優(yōu)解。,基：若B是矩陣A中mm階非奇異子矩陣（|B|0），則B是線性規(guī)劃問題的一個基陣。不妨設(shè)：, j=1，2，,m 基向量。 ，j=1，2，,m 基變量。 , j=m+1,n 非基變量。,線性規(guī)劃問題解的概念,求解,線性規(guī)劃問題解的

11、概念,基本解：稱上面求出的X解為基本解。 基本可行解：非負(fù)的基解X稱為基本可行解 可行基：對應(yīng)基本可行解的基稱為可行基,線性規(guī)劃問題解的概念,T,基變量 令 可求出：,線性規(guī)劃解的關(guān)系圖,非可行解,可行解,基本可行解,基本解,線性規(guī)劃問題解的概念,最優(yōu)解？,：求基陣、基可行解。,練習(xí)：,線性規(guī)劃問題解的概念,根據(jù)定義,是一個基陣，它對應(yīng)的基本解為,顯然它是基本可行解。,另根據(jù)定義,也是一個基陣，它對應(yīng)的基本解為,它不是基本可行解。,線性規(guī)劃問題的幾何意義,基本概念 凸集：,線性規(guī)劃問題的幾何意義,頂點(diǎn):若K是凸集，XK；若X不能用不同的兩點(diǎn) 的線性組合表示為： 則X為頂點(diǎn).,凸集,線性規(guī)劃問題

12、的幾何意義,凸組合：,n=2，k=3,線性規(guī)劃問題的幾何意義,定理1: 若線性規(guī)劃問題存在可行域, 則其可行域: 是凸集.,基本定理,證明:,線性規(guī)劃問題的幾何意義,只要驗(yàn)證X在D中即可,引理：可行解X為基可行解 X的正分量對應(yīng)的列向量線性無關(guān),定理3：若可行域有界，線性規(guī)劃 問題的目標(biāo)函數(shù)一定可以在 其可行域的頂點(diǎn)上達(dá)到最優(yōu)。,定理2：線性規(guī)劃問題的基可行解X 對應(yīng)于可行域D的頂點(diǎn)。 證明：反證法。分兩步。,幾點(diǎn)結(jié)論：,線性規(guī)劃問題的可行域是凸集。 基可行解與可行域的頂點(diǎn)一一對應(yīng)。 最優(yōu)解必在頂點(diǎn)上得到。,圖解法,9 8 7 6 5 4 3 2 1 0,x2,可行域?yàn)橥辜?目標(biāo)函數(shù)不同時(shí) 等

13、值線的斜率不同 最優(yōu)解在頂點(diǎn)產(chǎn)生,目標(biāo)函數(shù)等值線的斜率,最優(yōu)解,圖解法,9 8 7 6 5 4 3 2 1 0,x2,可行域?yàn)橥辜?目標(biāo)函數(shù)不同時(shí) 等值線的斜率不同 最優(yōu)解在頂點(diǎn)產(chǎn)生,目標(biāo)函數(shù)等值線的斜率,最優(yōu)解,2.3 單純形法原理,本節(jié)通過一個引例，可以了解利用單純形法求解線性規(guī)劃問題的思路，并將每一次的結(jié)果與圖解法作一對比，其幾何意義更為清楚。,單純形法的思路,找出一個初始可行解,是否最優(yōu),轉(zhuǎn)移到另一個基本可行解 （找出更小的目標(biāo)函數(shù)值）,最優(yōu)解,是,否,循 環(huán),核心是：變量迭代,結(jié)束,單純形法有三種形式： 方程組形式 表格形式 矩陣形式 1 方程組形式的單純形法 思路：由一個基本可行解

14、轉(zhuǎn)化為另一個基本可行解。,z +3x1 +5x2 = 0,例1 范例,等價(jià)改寫為,目標(biāo)方程,0 0 0 1 0 0 0 1,典式,條 典, 當(dāng)前基：m階排列陣 目標(biāo)方程中：一切基變量 的系數(shù) j = 0,最優(yōu)性檢驗(yàn)：,一切 j 0 ？,初始基本可行解 X0 = (0, 0, 8, 12, 36)T z0 = 0,排列陣： 每行每列有且僅有一個元素 為1，其余元素全為0 的方陣。, 1 = 3 0, 2 = 5 0,當(dāng)前解 X0 非優(yōu)；,+0 x3+0 x4+0 x5,須由X0 轉(zhuǎn)化為另一個基本可行解 X1。,滿足條典的方程組稱為典式(方程組)。,思路：讓X0 中的一個非基變量進(jìn)基，去替換原來的

15、一個基變量（離基）。,x1仍為非基變量，其值為0。, x2 12/2 x2 36/4,離基（最小比值規(guī)則） ： x2 min ，12/2，36/4 = 6 x2 = min ，12/2，36/4 = 6,x4,x4為離基變量,進(jìn)基（最大檢驗(yàn)數(shù)規(guī)則）： 在正檢驗(yàn)數(shù)中選擇最大的進(jìn)基。 max j j0 = k xk 進(jìn)基 max 3，5 = 5= 2 x2 進(jìn)基, 0, 0, 0,=,= 12,X1 =,(,12,0,6,8,0,)T,由 有,主方程,0,主列,主元,f + 3x1 +5 x2 = 0,x1 +x3 = 8,2 x2 +x4 = 12,3x1 + 4 x2 +x5 = 36,(),

16、- 6 9,比值,min,以主列中正值元素為分母，同行右端常數(shù)為分子，求比值；,按最小比值規(guī)則確定主方程和主元素，以及離基變量。,X0 = ( 0, 0, 8, 12, 36 )T z0 = 0,(),x1 +x3 = 8 ,3x1 -2x4 +x5 = 12 ,得,X1 =,z0 =- 30,稱為單純形法的一次迭代。,(,12,0,6,8,0,)T,換基運(yùn)算 方程組的初等變換 目的是把主列變?yōu)?單位向量：主元變 為1，其余變?yōu)?。,用換基運(yùn)算 將X0 轉(zhuǎn)化為 另一個基本 可行解 X1。,0 0 1 0,(),(),x1 +x3 = 8 ,3 x1 -2x4 + x5 = 12 ,得,X* =

17、 ( 4, 6, 4, 0, 0 )T,z* = -42,8 - 4,min,比值,1 0,2 單純形法的幾何意義,z = 0,( 4, 6, 4, 0, 0 )T,( 0, 0, 8, 12, 36 )T,( 0, 6, 8, 0, 12 )T,z 法向,單純形法迭代原理,從引例中了解了線性規(guī)劃的求解過程，將按上述思路介紹一般的線性規(guī)劃模型的求解方法單純形法迭代原理。,3 單純形法的計(jì)算步驟 1 把LP問題化為標(biāo)準(zhǔn)形。 2 在系數(shù)陣中找出或構(gòu)造一個m階排列陣作為初始 可行基，建立初始單純形表,若對應(yīng)的單純形不是典型，要化為典型。 3 最優(yōu)性檢驗(yàn): 若所有檢驗(yàn)數(shù) j 0，就得到一個 最優(yōu)基本解

18、，停止計(jì)算；否則轉(zhuǎn)4 。 4 解無界判斷: 在所有 j0中, 只要有一個 r 0 所對應(yīng)的系數(shù)列向量 ar 0，即一切 air 0 ， i=1, 2, , m 則該LP問題解無界，停止計(jì)算；否則轉(zhuǎn)5 。,預(yù) 備 步 驟,迭 代 步 驟,5 確定主元 先按最大檢驗(yàn)數(shù)規(guī)則 max j j 0 = k 確定進(jìn)基變量 xk 和主列ak； 再按最小比值規(guī)則,確定主元ar k, 同時(shí)也就確定第r行的基變量 xr離基。 6 以ar k為主元對當(dāng)前表格進(jìn)行一次換基運(yùn)算，得到 一個新單純形表，返3 。,迭 代 步 驟,在上一節(jié)單純形法迭代原理中可知，每一次迭代計(jì)算只要表示出當(dāng)前的約束方程組及目標(biāo)函數(shù)即可。 按定

19、義，化為當(dāng)前基對應(yīng)的典式。,單純形表,用單純形表求解LP問題,例、用單純形表求解LP問題,解：化標(biāo)準(zhǔn)型,15 0 5 1 0 0 24 6 2 0 1 0 5 1 1 0 0 1 0 2 1 0 0 0,主元化為1 主列單位向量 換出 換入,表1：列初始單純形表 （單位矩陣對應(yīng)的變量為基變量）,正檢驗(yàn)數(shù)中最大者對應(yīng)的列為主列,最小的值對應(yīng)的行為主行,2 1 0 0 0 15 0 5 1 0 0 4 1 2/6 0 1 /6 0 1 0 4/6 0 -1/6 1 -8 0 1/3 0 -1/3 0,表2：換基 （初等行變換，主列化為單位向量，主元為1）,檢驗(yàn)數(shù)0 確定主列,最小 確定主列,主元,

20、2 1 0 0 0 15/2 0 0 1 5/4 -15/2 7/2 1 0 0 1/4 -1/2 3/2 0 1 0 -1/4 3/2 -8.5 0 0 0 -1/4 -1/2,檢驗(yàn)數(shù)=0,最優(yōu)解為X=(7/2,3/2,15/2,0,0) 目標(biāo)函數(shù)值f=-8.5,表3：換基 （初等行變換，主列化為單位向量，主元為1）,觀察法:直接觀察得到初始可行基 約束條件: 加入松弛變量即形成可行基。（下頁） 約束條件: 加入非負(fù)人工變量, 以后討論.,1、初始基可行解的確定,(1) 最優(yōu)解判別定理：若： 為基可行解，且全部 則 為最優(yōu)解。 （2）唯一最優(yōu)解判別定理：若所有 則存在唯一最優(yōu)解。,2、最優(yōu)性

21、檢驗(yàn)與解的判別,（3）無窮多最優(yōu)解判定定理：若： 且存在某一個非基變量 則存在無窮多最優(yōu)解。 （4）無界解判定定理：若有某一個非基 變量 并且對應(yīng)的非基變量的系數(shù) 則具有無界解。,2、最優(yōu)性檢驗(yàn)與解的判別,107,2.5.1 單純形法的進(jìn)一步討論,一、大M法 二、兩階段法,-人工變量法,人工變量法,問題：線性規(guī)劃 問題化為標(biāo)準(zhǔn)形時(shí)， 若約束條件的系數(shù) 矩陣中不存在單位 矩陣，如何構(gòu)造 初始可行基？,人工變量法,加入 人工變量,設(shè)線性規(guī)劃問題的標(biāo)準(zhǔn)型為：,加入人工變量,構(gòu)造初始可行基.,人工變量法,系數(shù)矩陣為 單位矩陣， 可構(gòu)成初始 可行基。,約束條件已改變， 目標(biāo)函數(shù)如何調(diào)整？,人工變量法,“

22、懲罰” 人工變量！,（1）大M法 （2）兩階段法,一、大 M 法,人工變量在目標(biāo)函數(shù)中的系數(shù)為 M, 其中，M 為任意大的正數(shù)。,目標(biāo)函數(shù)中添加“罰因子” -M（M是任意大的正數(shù)） 為人工變量系數(shù)，只要人 工變量0，則目標(biāo)函數(shù) 不可能實(shí)現(xiàn)最優(yōu)。,例: 求解線性規(guī)劃問題,一、大 M 法,一、大 M 法,解:,加入松弛變量和剩余變量進(jìn)行標(biāo)準(zhǔn) 化, 加入人工變量構(gòu)造初始可行基.,求解結(jié)果出現(xiàn)檢驗(yàn)數(shù)非正 若基變量中含非零的人工變量， 則無可行解； 否則，有最優(yōu)解。,一、大 M 法,用單純形法求解（見下頁）。,目標(biāo)函數(shù)中添加“罰因子” -M為人工變量系數(shù)，只要人 工變量0，則目標(biāo)函數(shù) 不可能實(shí)現(xiàn)最優(yōu)。,表1（初始單純形表）,一、大 M 法（單純形法求解）,0,一、大 M 法（單純形法求解）,表2,1+M,表3,一、大 M 法（單純形法求解）,2,表4,一、大 M 法（單純形法求解）,最優(yōu)解為 目標(biāo)函數(shù) 值 f=-2,檢