1、第一章線性規(guī)劃及單純形法,線性規(guī)劃及單純形法,線性規(guī)劃問題及數(shù)學(xué)模型 圖解法 單純形法原理 單純形法計算步驟 單純形法進一步討論 數(shù)據(jù)包絡(luò)分析 其他應(yīng)用例子,1線性規(guī)劃問題,問題的提出 線性規(guī)劃問題的數(shù)學(xué)模型 線性規(guī)劃概念和模型,問題的提出,例1 美佳公司計劃制造、兩種家電產(chǎn)品。已知各制造一件時分別占用的設(shè)備A，B的臺時、調(diào)試工序時間及每天可用于這兩種家電的能力、各售出一件時的獲利情況，如表1-1所示。問該公司應(yīng)制造兩種家電各多少件，使獲取的利潤為最大。 表1-1,數(shù)學(xué)模型,例1中先用變量x1和x2分別表示美佳公司制造家電和的數(shù)量。這時該公司可獲取的利潤為(2x1+x2)元，令z=2x1+x2

2、，因問題中要求獲取的利潤為最大，即max z。 z是該公司能獲取的利潤的目標值，它是變量x1，x2的函數(shù)，稱為目標函數(shù)。 x1，x2的取值受到設(shè)備A、B和調(diào)試工序能力的限制，用于描述限制條件的數(shù)學(xué)表達式稱為約束條件。 由此例1的數(shù)學(xué)模型可表為：,數(shù)學(xué)模型,max: maximize的縮寫， “最大化”， s.t. subject to的縮寫， “受限制于”,問題的提出,例2 捷運公司在下一年度的14月的4個月內(nèi)擬租用倉庫堆放物資。已知各月份所需倉庫面積列于表1-2。倉庫租借費用隨合同期而定，期限越長，折扣越大，具體數(shù)字見表1-3。租借倉庫的合同每月初都可辦理，每份合同具體規(guī)定租用面積和期限。因

3、此該廠可根據(jù)需要，在任何一個月初辦理租借合同。每次辦理時可簽一份合同，也可簽若干份租用面積和租借期限不同的合同，試確定該公司簽訂租借合同的最優(yōu)決策，目的是使所付租借費用最小。,數(shù)學(xué)模型,例2中若用變量xij表示捷運公司在第i(i=1,4)個月初簽訂的租借期為j(j=1,4)個月的倉庫面積的合同。因5月份起該公司不需要租借倉庫，故x24，x33，x34，x42，x43，x44均為零。該公司希望總的租借費用為最小，故有如下數(shù)學(xué)模型：,min：minimize ， “最小化”,概念和模型,定義： 對于求取一組變量xj(j=1,2,.,n)，使之既滿足線性約束條件，又使具有線性的目標函數(shù)取得極值的一類

4、最優(yōu)化問題稱為線性規(guī)劃問題。,max（或min）,概念和模型,一般形式：,max（或min）,目標函數(shù),約束條件,非負約束,稱為決策變量,稱為價值系數(shù)或目標函數(shù)系數(shù),稱為資源常數(shù)或約束右端常數(shù),稱為技術(shù)系數(shù)或約束系數(shù),概念和模型,緊縮形式：,max（或min）,概念和模型,矩陣形式：,max（或min）,稱為決策變量向量,稱為價值系數(shù)向量或目標函數(shù)系數(shù)向量,稱為資源常數(shù)向量或約束右端常數(shù)向量,稱為技術(shù)系數(shù)或約束系數(shù)矩陣,圖解法,單純形法的定義,概念和模型,一般形式：,max（或min）,目標函數(shù),約束條件,非負約束,稱為決策變量,稱為價值系數(shù)或目標函數(shù)系數(shù),稱為資源常數(shù)或約束右端常數(shù),稱為技術(shù)

5、系數(shù)或約束系數(shù),標準形式,標準型的主要特征： 目標最大； 約束等式； 變量非負； 右端非負。,為何要進行線性規(guī)劃問題的標準化？,標準化,把一般的LP（Linear-Programming）化成標準型的過程稱為線性規(guī)劃問題的標準化 方法： 1 目標標準化 min Z 等價于 max ( - Z ) max Z=-cjxj 2 化約束為等式 加松弛變量、減剩余變量 3 變量非負化 做變換 或 4 右端非負,標準化,標準化舉例（例3）：,線性規(guī)劃及單純形法,線性規(guī)劃問題及數(shù)學(xué)模型 圖解法 單純形法原理 單純形法計算步驟 單純形法進一步討論 數(shù)據(jù)包絡(luò)分析 其他應(yīng)用例子,2圖解法,1什麼是圖解法？ 線性

6、規(guī)劃的圖解法就是用幾何作圖的方法分析并求出其最優(yōu)解的過程。 求解的思路是：先將約束條件加以圖解，求得滿足約束條件的解的集合（即可行域），然后結(jié)合目標函數(shù)的要求從可行域中找出最優(yōu)解。,圖解法,2. 圖解法(例1),運用圖解法，以求出最優(yōu)生產(chǎn)計劃（最優(yōu)解）。,圖解法,由于線性規(guī)劃模型中只有兩個決策變量，因此只需建立平面直角坐標系就可以進行圖解了。,1.建立平面直角坐標系，標出坐標原點, 坐標軸的指向和單位長度。 2.對約束條件加以圖解，找出可行域。 3.畫出目標函數(shù)等值線。 4.結(jié)合目標函數(shù)的要求求出最優(yōu)解。,圖解法,圖解法,(a)可行域有界 (b)可行域有界 (c)可行域無界 唯一最優(yōu)解多個最優(yōu)

7、解 唯一最優(yōu)解,(d)可行域無界 (e)可行域無界 (f)可行域為空集 多個最優(yōu)解 目標函數(shù)無界 無可行解,線性規(guī)劃及單純形法,線性規(guī)劃問題及數(shù)學(xué)模型 圖解法 單純形法原理 單純形法計算步驟 單純形法進一步討論 數(shù)據(jù)包絡(luò)分析 其他應(yīng)用例子,3單純形法原理,線性規(guī)劃問題的解的概念 凸集及其頂點 幾個基本定理,解的概念,可行解： 變量滿足所有約束條件的一組值 可行解集： 所有可行解構(gòu)成的集合 可行域： 可行解集構(gòu)成n維空間的區(qū)域,線性規(guī)劃問題,解的概念,最優(yōu)解： 使得目標函數(shù)達到最優(yōu)的可行解 最優(yōu)值： 最優(yōu)解對應(yīng)的目標函數(shù)值 目的： 求最優(yōu)解和最優(yōu)值 求解方法： 單純形法,解的概念,先研究AX=b

8、 設(shè) 系數(shù)矩陣A是mn矩陣，秩為m， B是A中mm階非奇異子矩陣（即|B|0），則稱B是線性規(guī)劃問題 的一個基。 B 是由m個線性獨立的列向量組成,基向量,基變量,非基變量： 其余變量,解的概念,AX=BXB+NXN=b 令 非基變量XN=0 得BXB=b 和特解XB =B-1b 結(jié)合XN=0 稱為對應(yīng)于B的基本解； 基本解個數(shù)=基的個數(shù)Cnm 基可行解 可行的基本解 XB0 XN=0 可行基：對應(yīng)于基可行解的基,A=（B | N）,解的概念,最優(yōu)基： 對應(yīng)的基本可行解也是最優(yōu) 基本可行解個數(shù)基的個數(shù)Cnm 基本可行解的非零分量均為正分量， 其正分量個數(shù) m。 退化的基本可行解： 基本可行解的

9、非零分量個數(shù)小于m時，也就是在基本可行解中一個或多于一個的基變量取零值時,凸集及其頂點,1、基本概念： 凸集設(shè)K是n維歐氏空間的一個點集，若任意兩點X（1）K，X（2）K的連線上的一切點： X（1）+（1-）X（2） K （01），則稱K為凸集。,凸集的概念,頂點設(shè)K是凸集，XK；若K中不存在兩個不同的點X（1） K，X（2） K 使 X=X（1）+（1-）X（2） （01） 則稱X為K的一個頂點（也稱為極點或角點）。,凸集的概念,凸集,凸集,不是凸集,頂點,基本定理,若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解（可行域頂點）是最優(yōu)解。,定理1,引理,定理2,定理3,若線性規(guī)劃問題存在可行解，

10、則該問題的可行解集（即可行域）是凸集。,線性規(guī)劃問題的可行解x(x1, x2, xn)為基可行解的充要條件是x的正分量所對應(yīng)的系數(shù)列向量是線性獨立的。,線性規(guī)劃問題的基可行解x對應(yīng)線性規(guī)劃問題可行域(凸集)的頂點,解的幾何意義,猜想1 線性規(guī)劃的可行域是凸集； 猜想2 最優(yōu)解若存在，則可以在可行域的頂點上得到； 猜想3 可行域的頂點的個數(shù)是有限的； 猜想4 若有兩個最優(yōu)解，則其連線上的點也是最優(yōu)解，即最優(yōu)解有無窮多個 猜想5 對于標準型的線性規(guī)劃X是可行域頂點的充分必要條件是X是基本可行解。,求解思路,求一個初始基本可行解 是 判斷基本可行解是否最優(yōu) 結(jié) 束 不是 求使目標得到改善的基本可行解

11、,是否存在？ 如何得到？,是否唯一？,如何判斷？,如何改善？ 如何判斷沒有有限最優(yōu)解？,線性規(guī)劃及單純形法,線性規(guī)劃問題及數(shù)學(xué)模型 圖解法 單純形法原理 單純形法計算步驟 單純形法進一步討論 數(shù)據(jù)包絡(luò)分析 其他應(yīng)用例子,4單純形法迭代原理,單純形方法引例 單純形法的一般描述 表格單純形法 一般問題的處理 單純形法矩陣描述 幾點注意事項,單純形方法引例,用單純形法的思想求解線性規(guī)劃問題：,單純形方法引例,例,基本解（0，0，0，3，9）也是可行的,單純形方法引例,例,初始基本可行解X(0)=（0，0，0，3，9） 含義： 不生產(chǎn)任何產(chǎn)品，工時剩余為3，材料剩余為9，利潤為 Z(0)=0 初始基本

12、可行解是否最優(yōu)解 ? 是否可以生產(chǎn)某種產(chǎn)品使目標提高？ 當x1（或x2 , x3）增加一個單位時，會使目標增加2（或3）單位,單純形方法引例,例,初始基本可行解X(0)= （0，0，0，3，9） 當x1（或x2 , x3）增加一個單位時，會使目標增加2（或3）單位 考慮將x1（或x2 , x3）并為非零變量， x2 , x3價值系數(shù)加大，將x2變?yōu)榛兞恳胱兞俊?單純形方法引例,例,初始基本可行解X(0)= （0，0，0，3，9） 當x2作為引入變量，為使新解X(1)仍為基可行解，必須使,且使x4或x5中有一個等于零退出變量,（1-1）,單純形方法引例,例,由(1-1)第四、第五式，得,為使

13、新解X(1)為基可行解,此時，變?yōu)榱悖?x5為退出變量 新的基可行解為X (1) =(0, 9/4, 0, 3/4, 0) 目標函數(shù)值Z(1)=27/4 Z(0),單純形方法引例,例,系數(shù)列向量,此時，進一步分析引入x1或x3是否會更好？引入哪一個更好？,單純形方法引例,首先考慮引入x1 ，由于,計算增加單位x1所創(chuàng)增的凈經(jīng)濟價值,同理，可計算增加單位x3所創(chuàng)增的凈經(jīng)濟價值,檢驗數(shù),單純形方法引例,例,基本可行解X (1) =(0, 9/4, 0, 3/4, 0) 取x1進基，同樣，,此時，為x4退出變量。新的基可行解為 X (2) =(1, 2, 0, 0, 0) 目標函數(shù)Z(2)=2+6=

14、8 27/4 =Z(0) 此時非基變量檢驗數(shù)均為負，解最優(yōu),單純形法一般步驟,1.初始基本可行解的確定（觀察法）；,單純形法一般步驟,1.初始基本可行解的確定（觀察法）；,基,基本可行解,單純形法一般步驟,2.從約束中解出基變量；,5表格單純形法,標準型：,表格單純形法,標準型：,表格單純形法,表格單純形法,基變量,檢驗數(shù),最小比值列,基變量系數(shù),右端常數(shù),解：,表1-7,表1-9中所有j=0,且基變量中不含人工變量，最優(yōu)解 X=(7/2, 3/2, 15/2, 0, 0) ; 最優(yōu)值 Z=17/2.,練習(xí)1：求解線性規(guī)劃,表格單純形法,向右迭代一步,練習(xí)2：求解線性規(guī)劃,表格單純形法,沒有有

15、限最優(yōu)解,算法思路,求一個初始基本可行解 是 判斷基本可行解是否最優(yōu) 結(jié) 束 不是 求使目標得到改善的基本可行解,是否存在？ 如何得到？,是否唯一？,如何判斷？,如何改善？ 如何判斷沒有有限最優(yōu)解？,5單純形法進一步討論,處理方法一 大法,人造基 添加人工變量造成基 去掉人工變量,5單純形法進一步討論,原問題的可行解 新問題的可行解 目標值,結(jié)論：新問題的最優(yōu)解中，如果人工變量均為零，則得到的解也是原問題的最優(yōu)解，否則原問題無可行解,例6 大M法,最優(yōu)解:X=(0,5/2,3/2,0,0,0,0) 最優(yōu)值： Z= 3/2,大M法舉例,所有檢驗數(shù)0 已經(jīng)是最優(yōu)解 x5=2 人工變量不為零, 表示原問題無可行解 參照圖解法結(jié)果,5單純形法進一步討論,處理方法二 兩階段法,人造基 添加人工變量造成基 去掉人工變量,兩階段法,如果線性規(guī)劃問題中的aij、bi或cj等參數(shù)值與這個代表M的數(shù)相對比較接近，或遠遠小于這個數(shù)字，由于計算機計算時取值上的誤差，有可能使計算結(jié)果發(fā)生錯誤。為了克服這