數(shù)據(jù)、模型與決策--線性規(guī)劃（PPT 110頁）(1)

1、數(shù)據(jù)、模型與決策 線性規(guī)劃Linear Programming1.1 LP的數(shù)學(xué)模型 Mathematical Model of LP1.2 圖解法 Graphical Method1.3 標(biāo)準(zhǔn)型 Standard form of LP1.4 基本概念 Basic Concepts1.5 Simplex Method7/23/20221.1 數(shù)學(xué)模型 Mathematical Model 7/23/20221.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 線性規(guī)劃通常研究資源的最優(yōu)利用、設(shè)備最佳運(yùn)行等問題。例如，當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資

2、源 （如資金、設(shè)備、原標(biāo)材料、人工、時間等）去完成確定的任務(wù)或目標(biāo)；企業(yè)在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多 、利潤最大）。線性規(guī)劃（Linear Programming,縮寫為LP）是運(yùn)籌學(xué)的重要分支之一，在實(shí)際中應(yīng)用得較廣泛，其方法也較成熟，借助計(jì)算機(jī)，使得計(jì)算更方便，應(yīng)用領(lǐng)域更廣泛和深入。7/23/2022【例1.1】最優(yōu)生產(chǎn)計(jì)劃問題。某企業(yè)在計(jì)劃期內(nèi)計(jì)劃生產(chǎn)甲、乙、丙三種產(chǎn)品。這些產(chǎn)品分別需要要在設(shè)備A、B上加工，需要消耗材料C、D，按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工及所需要的資源如表1.1所示。已知在計(jì)劃期內(nèi)設(shè)備的加工能力各為200臺時，可供

3、材料分別為360、300公斤；每生產(chǎn)一件甲、乙、丙三種產(chǎn)品，企業(yè)可獲得利潤分別為40、30、50元，假定市場需求無限制。企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使企業(yè)在計(jì)劃期內(nèi)總的利潤收入最大？1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP1.1.1 應(yīng)用模型舉例7/23/2022 產(chǎn)品 資源 甲 乙 丙現(xiàn)有資源設(shè)備A 3 1 2 200設(shè)備B 2 2 4 200材料C 4 5 1 360材料D 2 3 5 300利潤（元/件） 40 30 50表1.1 產(chǎn)品資源消耗1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP7/23/2022【解】設(shè)x1、

4、x2、x3 分別為甲、乙、丙三種產(chǎn)品的產(chǎn)量數(shù)學(xué)模型為：1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 產(chǎn)品 資源 甲 乙 丙現(xiàn)有資源設(shè)備A 3 1 2 200設(shè)備B 2 2 4 200材料C 4 5 1 360材料D 2 3 5 300利潤（元/件） 40 30 50最優(yōu)解X=(50,30,10);Z=34007/23/2022線性規(guī)劃的數(shù)學(xué)模型由決策變量 Decision variables 目標(biāo)函數(shù)Objective function及約束條件Constraints構(gòu)成。稱為三個要素。其特征是：1解決問題的目標(biāo)函數(shù)是多個決策變量的 線性函數(shù)，通常是求最大值或

5、最小值；2解決問題的約束條件是一組多個決策變量 的線性不等式或等式。怎樣辨別一個模型是線性規(guī)劃模型？1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP7/23/2022【例1.2】某商場決定：營業(yè)員每周連續(xù)工作5天后連續(xù)休息2天，輪流休息。根據(jù)統(tǒng)計(jì)，商場每天需要的營業(yè)員如表1.2所示。表1.2 營業(yè)員需要量統(tǒng)計(jì)表商場人力資源部應(yīng)如何安排每天的上班人數(shù)，使商場總的營業(yè)員最少。 星期需要人數(shù)星期需要人數(shù)一300五480二300六600三350日550四4001.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP7/23/2022【解】 設(shè)xj(j=1

6、，2，7)為休息2天后星期一到星期日開始上班的營業(yè)員，則這個問題的線性規(guī)劃模型為 1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP星期需要人數(shù)星期需要人數(shù)一300五480二300六600三350日550四4007/23/20221X10C1404=3001042X267C2301=30013X3146C3350=35004X4170C4400=40005X597C5480=48006X6120C6600=60007X717C7550=5500最優(yōu)解：Z617（人）7/23/2022【例1.3】合理用料問題。某汽車需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是

7、1.5，1，0.7（m），這些軸需要用同一種圓鋼來做，圓鋼長度為4 m。現(xiàn)在要制造1000輛汽車，最少要用多少圓鋼來生產(chǎn)這些軸？ 【解】這是一個條材下料問題 ，設(shè)切口寬度為零。 設(shè)一根圓鋼切割成甲、乙、丙三種軸的根數(shù)分別為y1，y2，y3,則切割方式可用不等式1.5y1+y2+0.7y34表示，求這個不等式關(guān)于y1，y2，y3的非負(fù)整數(shù)解。象這樣的非負(fù)整數(shù)解共有10組，也就是有10種下料方式，如表1.3所示。表13 下料方案 方案規(guī)格 1234 5678910需求量y1(根) 221 11 0 00001000y2 102 10 4 32101000y3 010 23 0 12451000余料

8、（m）00.30.5 0.1o.4 00.30.60.20.51.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP7/23/2022設(shè)xj(j=1,2,10)為第j種下料方案所用圓鋼的根數(shù)。則用料最少數(shù)學(xué)模型為:求下料方案時應(yīng)注意，余料不能超過最短毛坯的長度；最好將毛坯長度按降的次序排列，即先切割長度最長的毛坯，再切割次長的，最后切割最短的，不能遺漏了方案 。如果方案較多，用計(jì)算機(jī)編程排方案，去掉余料較長的方案，進(jìn)行初選。1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 方案規(guī)格 1234 5678910需求量y1(根) 221 11 0 0

9、0001000y2 102 10 4 32101000y3 010 23 0 12451000余料（m）00.30.5 0.1o.4 00.30.60.20.57/23/20221X15002X203X304X405X506X662.57X708X809X925010X100Z812.57/23/2022【例1.4】配料問題。某鋼鐵公司生產(chǎn)一種合金，要求的成分規(guī)格是：錫不少于28%，鋅不多于15%，鉛恰好10%，鎳要界于35%55%之間，不允許有其他成分。鋼鐵公司擬從五種不同級別的礦石中進(jìn)行冶煉，每種礦物的成分含量和價格如表1.4所示。礦石雜質(zhì)在治煉過程中廢棄，現(xiàn)要求每噸合金成本最低的礦物數(shù)量

10、。假設(shè)礦石在冶煉過程中，合金含量沒有發(fā)生變化。表1.4 礦石的金屬含量 合金礦石錫%鋅%鉛%鎳%雜質(zhì)費(fèi)用（元/t ）1251010253034024000303026030155206018042020040202305851517551901.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP7/23/2022解: 設(shè)xj（j=1,2，5）是第j 種礦石數(shù)量，得到下列線性規(guī)劃模型 注意，礦石在實(shí)際冶煉時金屬含量會發(fā)生變化，建模時應(yīng)將這種變化考慮進(jìn)去，有可能是非線性關(guān)系。配料問題也稱配方問題、營養(yǎng)問題或混合問題，在許多行業(yè)生產(chǎn)中都能遇到。1.1 線性規(guī)劃的數(shù)學(xué)模型 Mat

11、hematical Model of LP礦石錫%鋅%鉛%鎳%雜質(zhì)費(fèi)用（元/t ）1251010253034024000303026030155206018042020040202305851517551907/23/20221X102X20.33333X304X40.58335X50.6667最優(yōu)解：Z=347.51.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP7/23/2022【例1.5】投資問題。某投資公司在第一年有200萬元資金，每年都有如下的投資方案可供考慮采納：“假使第一年投入一筆資金，第二年又繼續(xù)投入此資金的50%，那么到第三年就可回收第一年投入資金的

12、一倍金額”。投資公司決定最優(yōu)的投資策略使第六年所掌握的資金最多。第五年：(x7/2+x9)=x8+2x5第一年：x1+x2=200(萬元)第二年：(x1/2 +x3)+x4=x2第三年(x3/2+x5)+x6=x4+2x1第四年：(x5/2+x7)+x8=x6+2x3到第六年實(shí)有資金總額為x9+2x7，整理后得到下列線性規(guī)劃模型 1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP【解】設(shè) x1：第一年的投資； x2：第一年的保留資金 x3：第二年新的投資；x4：第二年的保留資金 x5：第三年新的投資； x6：第三年的保留資金 x7：第四年新的投資 x8：第四年的保留資

13、金 x9：第五年的保留資金 7/23/20221.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP1X155.28462X2144.71553X3117.07324X405X552.03256X607X7208.13018X809X90最優(yōu)解：Z 416.26萬元x1：第一年的投資； x2：第一年的保留資金 x3：第二年新的投資；x4：第二年的保留資金 x5：第三年新的投資； x6：第三年的保留資金 x7：第四年新的投資 x8：第四年的保留資金 x9：第五年的保留資金 7/23/2022【例1.6】均衡配套生產(chǎn)問題。某產(chǎn)品由2件甲、3件乙零件組裝而成。兩種零件必須經(jīng)過設(shè)

14、備A、B上加工，每件甲零件在A、B上的加工時間分別為5分鐘和9分鐘，每件乙零件在A、B上的加工時間分別為4分鐘和10分鐘。現(xiàn)有2臺設(shè)備A和3臺設(shè)備B，每天可供加工時間為8小時。為了保持兩種設(shè)備均衡負(fù)荷生產(chǎn)，要求一種設(shè)備每天的加工總時間不超過另一種設(shè)備總時間1小時。怎樣安排設(shè)備的加工時間使每天產(chǎn)品的產(chǎn)量最大?！窘狻?設(shè)x1、x2為每天加工甲、乙兩種零件的件數(shù)，則產(chǎn)品的產(chǎn)量是設(shè)備A、B每天加工工時的約束為要求一種設(shè)備每臺每天的加工時間不超過另一種設(shè)備1小時的約束為 1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP7/23/2022目標(biāo)函數(shù)線性化。產(chǎn)品的產(chǎn)量y等價于整理得

15、到線性規(guī)劃模型 約束線性化。將絕對值約束寫成兩個不等式1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP7/23/20221.1.2 線性規(guī)劃的一般模型一般地，假設(shè)線性規(guī)劃數(shù)學(xué)模型中，有m個約束，有n個決策變量xj, j=1,2,n，目標(biāo)函數(shù)的變量系數(shù)用cj表示, cj稱為價值系數(shù)。約束條件的變量系數(shù)用aij表示，aij稱為工藝系數(shù)。約束條件右端的常數(shù)用bi表示，bi稱為資源限量。則線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式可寫成為了書寫方便，上式也可寫成： 1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP7/23/2022在實(shí)際中一般xj0,但有時xj

16、0或xj無符號限制。1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP7/23/20221.什么是線性規(guī)劃，掌握線性規(guī)劃在管理中的幾個應(yīng)用例子2.線性規(guī)劃數(shù)學(xué)模型的組成及其特征3.線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式。作業(yè)：教材P31 T 2，3，4，5，61.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP下一節(jié)：圖解法7/23/20221.2 圖解法 Graphical Method7/23/2022圖解法的步驟：1.求可行解集合。分別求出滿足每個約束包括變量非 負(fù)要求的區(qū)域，其交集就是可行解集合，或稱為可行域；2.繪制目標(biāo)函數(shù)圖形。先過原點(diǎn)作一條

17、矢量指向點(diǎn)（c1,c2)，矢量的方向就是目標(biāo)函數(shù)增加的方向，稱為梯度方向，再作一條與矢量垂直的直線，這條直線就是目標(biāo)函數(shù)圖形；3.求最優(yōu)解。依據(jù)目標(biāo)函數(shù)求最大或最小移動目標(biāo)函數(shù)直線，直線與可行域相交的點(diǎn)對應(yīng)的坐標(biāo)就是最優(yōu)解。一般地，將目標(biāo)函數(shù)直線放在可行域中 求最大值時直線沿著矢量方向移動 求最小值時沿著矢量的反方向移動1.2 圖解法The Graphical Method7/23/2022x1x2O1020304010203040(3,4)(15,10)最優(yōu)解X=(15,10)最優(yōu)值Z=85例1.71.2 圖解法The Graphical Method7/23/2022246x1x2246最

18、優(yōu)解X=(3,1)最優(yōu)值Z=5(3,1)min Z=x1+2x2例1.8(1,2)1.2 圖解法The Graphical Method7/23/2022246x1x2246X（2）（3,1）X（1）（1,3）(5,5)min Z=5x1+5x2例1.9有無窮多個最優(yōu)解即具有多重解,通解為 01 當(dāng)=0.5時=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) 1.2 圖解法The Graphical Method7/23/2022246x1x2246(1,2)無界解(無最優(yōu)解)max Z=x1+2x2例1.107/23/2022x1x2O10203040102030405050無

19、可行解即無最優(yōu)解max Z=10 x1+4x2例1.111.2 圖解法The Graphical Method7/23/2022由以上例題可知，線性規(guī)劃的解有4種形式：1.有唯一最優(yōu)解(例1.7例1.8)2.有多重解(例1.9)3.有無界解(例1.10)4.無可行解(例1.11)1、2情形為有最優(yōu)解3、4情形為無最優(yōu)解1.2 圖解法The Graphical Method7/23/20221.通過圖解法了解線性規(guī)劃有幾種解的形式2.作圖的關(guān)鍵有三點(diǎn) (1)可行解區(qū)域要畫正確 (2)目標(biāo)函數(shù)增加的方向不能畫錯 (3)目標(biāo)函數(shù)的直線怎樣平行移動作業(yè)：教材P34 T7 1.2 圖解法The Grap

20、hical Method下一節(jié)：線性規(guī)劃的標(biāo)準(zhǔn)型7/23/20221.3 線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP7/23/2022 在用單純法求解線性規(guī)劃問題時，為了討論問題方便，需將線性規(guī)劃模型化為統(tǒng)一的標(biāo)準(zhǔn)形式。1.3 線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP線性規(guī)劃問題的標(biāo)準(zhǔn)型為:1目標(biāo)函數(shù)求最大值（或求最小值）2約束條件都為等式方程3變量xj非負(fù)4常數(shù)bi非負(fù)7/23/2022max(或min)Z=c1x1+c2x2+cnxn1.3 線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP注：本教材默認(rèn)目標(biāo)函數(shù)是 max7/23/2022或?qū)懗上铝行问剑?或

21、用矩陣形式1.3 線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP7/23/2022通常X記為： 稱為約束方程的系數(shù)矩陣，m是約束方程的個數(shù)，n是決策變量的個數(shù)，一般情況mn，且r()m。其中:1.3 線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP7/23/2022【例1.12】將下列線性規(guī)劃化為標(biāo)準(zhǔn)型 【解】（）因?yàn)閤3無符號要求 ，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以令 1.3 線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP7/23/2022 (3)第二個約束條件是號，在號 左端減去剩余變量(Surplus variable)x5，x50。也稱松馳變量1

22、.3 線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP(2) 第一個約束條件是號，在左端加入松馳變量 (slack variable) x4，x40,化為等式；(4)第三個約束條件是號且常數(shù)項(xiàng)為負(fù)數(shù)，因此在左邊加入松馳變量x6，x60，同時兩邊乘以1。 （5）目標(biāo)函數(shù)是最小值，為了化為求最大值，令Z=Z,得到max Z=Z，即當(dāng)Z達(dá)到最小值時Z達(dá)到最大值，反之亦然。 7/23/2022綜合起來得到下列標(biāo)準(zhǔn)型 1.3 線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP7/23/2022 當(dāng)某個變量xj0時,令x/j=xj 。 當(dāng)某個約束是絕對值不等式時，將絕對值不等式化為兩個不等式，再

23、化為等式，例如約束 將其化為兩個不等式 再加入松馳變量化為等式。 1.3 線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP7/23/2022【例1.13】將下例線性規(guī)劃化為標(biāo)準(zhǔn)型【解】 此題關(guān)鍵是將目標(biāo)函數(shù)中的絕對值去掉。令 則有1.3 線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP7/23/2022得到線性規(guī)劃的標(biāo)準(zhǔn)形式 1.3 線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP對于axb(a、b均大于零)的有界變量化為標(biāo)準(zhǔn)形式有兩種方法，一種方法是增加兩個約束xa及xb，另一種方法是令=xa，則axb等價于0ba，增加一個約束ba并且將原問題所有x用x=+a替換。7/23

24、/20221.如何化標(biāo)準(zhǔn)形式？ 可以對照四條標(biāo)準(zhǔn)逐一判斷！ 標(biāo)準(zhǔn)形式是人為定義的，目標(biāo)函數(shù)可以是求最小值。2.用WinQSB軟件求解時，不必化成標(biāo)準(zhǔn)型。圖解法時不必化為標(biāo)準(zhǔn)型。3.單純形法求解時一定要化為標(biāo)準(zhǔn)型。作業(yè)：教材P34 T 81.3 線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP下一節(jié)：基本概念7/23/20221.4 線性規(guī)劃的有關(guān)概念Basic Concepts of LP7/23/2022 設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型 max Z=CX （1.1） AX=b （1.2） X 0 （1.3）式中A 是mn矩陣，mn并且r（A）=m，顯然A中至少有一個mm子矩陣B，使得r（B）=m。

25、1.4 基本概念Basic Concepts 基 (basis)A中mm子矩陣B并且有r（B）=m，則稱B是線性規(guī)劃的一個基（或基矩陣basis matrix ）。當(dāng)m=n時，基矩陣唯一，當(dāng)mn時，基矩陣就可能有多個，但數(shù)目不超過7/23/2022【例1.14】線性規(guī)劃 求所有基矩陣。 【解】約束方程的系數(shù)矩陣為25矩陣 容易看出r(A)=2，2階子矩陣有C52=10個，其中第1列與第3列構(gòu)成的2階矩陣不是一個基，基矩陣只有9個，即1.4 基本概念Basic Concepts 7/23/2022由線性代數(shù)知，基矩陣B必為非奇異矩陣并且|B|0。當(dāng)矩陣B的行列式等式零即|B|=0時就不是基 當(dāng)確

26、定某一矩陣為基矩陣時，則基矩陣對應(yīng)的列向量稱為基向量(basis vector)，其余列向量稱為非基向量 基向量對應(yīng)的變量稱為基變量(basis variable)，非基向量對應(yīng)的變量稱為非基變量 在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基變量，x2、x3、x5是非基變量?；兞俊⒎腔兞渴轻槍δ骋淮_定基而言的，不同的基對應(yīng)的基變量和非基變量也不同。1.4 基本概念Basic Concepts 7/23/2022可行解(feasible solution) 滿足式（1.2）及（1.3）的解X=（x1,x2，xn)T 稱為可行解 ?；究尚薪?basis f

27、easible solution) 若基本解是可行解則稱為是基本可行解（也稱基可行解）。 例如， 與X=（0，0，0，3，2，）都是例1 的可行解。 基本解(basis solution) 對某一確定的基B，令非基變量等于零，利用式（1.） 解出基變量，則這組解稱為基的基本解。 最優(yōu)解(optimal solution) 滿足式 （1 .1）的可行解稱為最優(yōu)解，即是使得目標(biāo)函數(shù)達(dá)到最大值的可行解就是最優(yōu)解，例如可行解 是例2的最優(yōu)解。非可行解(Infeasible solution) 無界解 (unbound solution)1.4 基本概念Basic Concepts 7/23/2022顯

28、然，只要基本解中的基變量的解滿足式（1.）的非負(fù)要求，那么這個基本解就是基本可行解。 在例1.13中，對來說，x1,x2是基變量，x3,x4，x5是非基變量，令x3=x4=x5=0，則式（1.）為對B2來說，x1,x4,為基變量，令非變量x2,x3,x5為零，由式（1.2）得到 ，x4=4，因|B1|，由克萊姆法則知，x1、x2有唯一解x12/5,x2=1則 基本解為1.4 基本概念Basic Concepts 7/23/2022由于 是基本解，從而它是基本可行解，在 中x10,因此不是可行解，也就不是基本可行解。 反之，可行解不一定是基本可行解例如 滿足式（1.2）（1.3），但不是任何基矩

29、陣的基本解。基本解為1.4 基本概念Basic Concepts 7/23/2022可行基 基可行解對應(yīng)的基稱為可行基；最優(yōu)基基本最優(yōu)解對應(yīng)的基稱為最優(yōu)基；如上述B3就是最優(yōu)基，最優(yōu)基也是可行基。當(dāng)最優(yōu)解唯一時，最優(yōu)解亦是基本最優(yōu)解，當(dāng)最優(yōu)解不唯一時，則最優(yōu)解不一定是基本最優(yōu)解。例如右圖中線段 的點(diǎn)為最優(yōu) 解時，Q1點(diǎn)及Q2點(diǎn)是基本最優(yōu)解,線段 的內(nèi)點(diǎn)是最優(yōu)解而不是基本最優(yōu)解。 基本最優(yōu)解 最優(yōu)解是基本解稱為基本最優(yōu)解。例如，滿足式（1.1）(1.3)是最優(yōu)解,又是B3的基本解,因此它是基本最優(yōu)解。1.4 基本概念Basic Concepts 7/23/2022基本最優(yōu)解、最優(yōu)解、基本可行解、

30、基本解、可行解的關(guān)系如下所示：基本最優(yōu)解基本可行解可行解最 優(yōu) 解基本解例如,B點(diǎn)和D點(diǎn)是可行解,不是基本解;C點(diǎn)是基本可行解;A點(diǎn)是基本最優(yōu)解,同時也是最優(yōu)解、基本可行解、基本解和可行解。1.4 基本概念Basic Concepts 7/23/2022凸集(Convex set)設(shè)K是n維空間的一個點(diǎn)集，對任意兩點(diǎn) 時，則稱K為凸集。 就是以X（1）、X（2）為端點(diǎn)的線段方程，點(diǎn)X的位置由的值確定，當(dāng)=0時，X=X（2），當(dāng)=1時X=X（1）凸組合(Convex combination) 設(shè) 是Rn 中的點(diǎn)若存在 使得 成立， 則稱X為 的凸組合。1.4 基本概念Basic Concepts

31、 7/23/2022極點(diǎn)(Extreme point) 設(shè)K是凸集， ，若X不能用K中兩個不同的 點(diǎn) 的凸組合表示為)10()1()2()1(0i表1-4(1)XBx1x2x3x4bx3211040 x4130130j3400(2)x3x2j(3)x1x2j基變量110001/301/3105/31-1/3405/30-4/330103/5-1/51801-1/5 2/5400-1-1將3化為1乘以1/3后得到1.5 單純形法 Simplex Method30187/23/2022最優(yōu)解X=(18，4，0，0)T，最優(yōu)值Z=70O20301040(3,4)X(3)=(18,4)最優(yōu)解X=(18

32、,4)最優(yōu)值Z=70X(1)=(0,0)2010 x2x1301.5 單純形法 Simplex MethodX(2)=(0,10)7/23/2022單純形法全過程的計(jì)算，可以用列表的方法計(jì)算更為簡潔，這種表格稱為單純形表（表1.4）。計(jì)算步驟：1.求初始基可行解，列出初始單純形表，求出檢驗(yàn)數(shù)。其中基變量的檢驗(yàn)數(shù)必為零； 2.判斷： （a）若j（j，n）得到最解； （b）某個k0且aik（i=1，2,m）則線性規(guī)劃具有無界解(見例1.18)。 （c）若存在k0且aik (i=1,m)不全非正，則進(jìn)行換基；1.5 單純形法 Simplex Method7/23/2022第個比值最小 ，選最小比值對

33、應(yīng)行的基變量為出基變量，若有相同最小比值，則任選一個。aLk為主元素； (c）求新的基可行解：用初等行變換方法將aLk 化為,k列其它元素化為零（包括檢驗(yàn)數(shù)行）得到新的可行基及基本可行解，再判斷是否得到最優(yōu)解。（b）選出基變量 ，求最小比值：1.5 單純形法 Simplex Method3.換基：（a）選進(jìn)基變量設(shè)k=max j | j 0,xk為進(jìn)基變量7/23/2022【例1.16】 用單純形法求解【解】將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：不難看出x4、x5可作為初始基變量，單純法計(jì)算結(jié)果如表 1.所示 。 1.5 單純形法 Simplex Method7/23/2022Cj12100bCBXBx1x

34、2x3x4x50 x423210150 x51/3150120j121000 x42x2j1x12x2j表151/3150120301713751/30902M2025601017/31/31250128/91/92/335/30098/91/97/3最優(yōu)解X=(25，35/3，0，0，0)T，最優(yōu)值Z=145/31.5 單純形法 Simplex Method7/23/2022【例1.17】用單純形法求解 【解】 這是一個極小化的線性規(guī)劃問題,可以將其化為極大化問題求解,也可以直接求解,這時判斷標(biāo)準(zhǔn)是：j0(j=1，n)時得到最優(yōu)解。容易觀察到,系數(shù)矩陣中有一個3階單位矩陣,x3、x4、x5為

35、基變量。目標(biāo)函數(shù)中含有基變量x4,由第二個約束得到x4=6+x1x2，并代入目標(biāo)函數(shù)消去x4得1.5 單純形法 Simplex Method7/23/2022XBx1x2x3x4x5bx3x4x51-1611210001000156215621/2j1-1000 x2x4x51-241001-1-20100015111j20100表中j0,j=1,2,5所以最優(yōu)解為X=(0,5,0,1,11,)最優(yōu)值 Z=2x12x2x4=251=11極小值問題,注意判斷標(biāo)準(zhǔn),選進(jìn)基變量時,應(yīng)選j0, x2進(jìn)基，而a120，a220且aik（i=1，2,m）則線性規(guī)劃具有無界解退化基本可行解的判斷:存在某個基

36、變量為零的基本可行解。1.5 單純形法 Simplex Method7/23/2022在實(shí)際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。【例1.20】用大M法解 下列線性規(guī)劃1. 大M 單純形法1.5.2大M和兩階段單純形法1.5 單純形法 Simplex Method7/23/2022【解】首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式式中x4，x5為松弛變量，x5可作為一個基變量，第一、三約束中分別加入人工變量x6、

37、x7，目標(biāo)函數(shù)中加入Mx6Mx7一項(xiàng)，得到人工變量單純形法數(shù)學(xué)模型用前面介紹的單純形法求解，見下表。 1.5 單純形法 Simplex Method7/23/2022Cj32100MMbCBXBx1x2x3x4x5x6x7M0Mx6x5x74123121211000101000014101j3-2M2+M-1+2MM000M01x6x5x3632532001100010100381j5-6M5M0M00201x2x5x36/53/52/51000011/53/52/50103/531/511/5j50000231x2x1x301010000111025/32/31331/319/3j0005-

38、25/37/23/2022（1）初始表中的檢驗(yàn)數(shù)有兩種算法，第一種算法是利用第一、三約束將x6、x7的表達(dá)式代入目標(biāo)涵數(shù)消去x6和x7，得到用非基變量表達(dá)的目標(biāo)函數(shù)，其系數(shù)就是檢驗(yàn)數(shù)；第二種算法是利用公式計(jì)算，如（2）M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；最優(yōu)解X（31/3，13，19/3，0，0)T；最優(yōu)值Z152/3注意：1.5 單純形法 Simplex Method7/23/2022【例1.21】求解線性規(guī)劃 【解】加入松馳變量x3、x4化為標(biāo)準(zhǔn)型在第二個方程中加入人工變量x5，目標(biāo)函數(shù)中加上M x5一項(xiàng)，得到 1.5 單純形法 Simp

39、lex Method7/23/2022用單純形法計(jì)算如下表所示。 Cj5800MbCBXBx1x2x3x4x50Mx3x5311210010164j5M8+2M0M05Mx1x5101/37/31/31/3010122j029/3+7/3M5/3+1/3MM01.5 單純形法 Simplex Method7/23/2022表中j0，j=1，2，5，從而得到最優(yōu)解X=（2，0，0，0，2）， Z=10+2M。但最優(yōu)解中含有人工變量x50說明這個解是偽最優(yōu)解，是不可行的，因此原問題無可行解。 兩階段單純形法與大M單純形法的目的類似，將人工變量從基變量中換出，以求出原問題的初始基本可行解。將問題分成

40、兩個階段求解，第一階段的目標(biāo)函數(shù)是約束條件是加入人工變量后的約束方程，當(dāng)?shù)谝浑A段的最優(yōu)解中沒有人工變量作基變量時，得到原線性規(guī)劃的一個基本可行解，第二階段就以此為基礎(chǔ)對原目標(biāo)函數(shù)求最優(yōu)解。當(dāng)?shù)谝浑A段的最優(yōu)解w0時，說明還有不為零的人工變量是基變量，則原問題無可行解。1.5 單純形法 Simplex Method2. 兩階段單純形法7/23/2022【例1.22】用兩階段單純形法求解例19的線性規(guī)劃?！窘狻繕?biāo)準(zhǔn)型為在第一、三約束方程中加入人工變量x6、x7后，第一階段問題為用單純形法求解，得到第一階段問題的計(jì)算表如下：1.5 單純形法 Simplex Method7/23/2022Cj00000

41、11 bCBXBx1x2x3x4x5x6x7101x6x5x74123121211000101000014101j2121000100 x6x5x3632532001100010100381j650100000 x2x5x36/53/52/51000011/53/52/50103/531/511/5j000001.5 單純形法 Simplex Method7/23/2022最優(yōu)解為 最優(yōu)值w=0。第一階段最后一張最優(yōu)表說明找到了原問題的一組基可行解，將它作為初始基可行解，求原問題的最優(yōu)解，即第二階段問題為1.5 單純形法 Simplex Method7/23/2022Cj32-100bCBXB

42、x1x2x3x4x5201x2x5x3100001010j50000231x2x1x3010100001110213j0005Cj32100bCBXBx1x2x3x4x5201x2x5x36/53/52/51000011/53/52/50103/531/5 11/5j5 0000231x2x1x301010000111025/32/31331/319/3j000525/3用單純形法計(jì)算得到下表最優(yōu)解X（31/3，13，19/3，0，0)T；最優(yōu)值Z152/31.5 單純形法 Simplex Method7/23/2022【例1.23】用兩階段法求解例1.21的線性規(guī)劃?！窘狻坷?.21的第一階

43、段問題為用單純形法計(jì)算如下表：1.5 單純形法 Simplex Method7/23/2022Cj00001bCBXBx1x2x3x4x501x3x5311210010164j1201001x1x5101/37/31/31/3010122j07/31/310j0,得到第一階段的最優(yōu)解X=(2,0,0,0,2)T,最優(yōu)目標(biāo)值w=20,x5仍在基變量中,從而原問題無可行解。1.5 單純形法 Simplex Method7/23/2022解的判斷唯一最優(yōu)解的判斷：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零,則線 規(guī)劃具有唯一最優(yōu)解 多重最優(yōu)解的判斷:最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解

44、。 無界解的判斷: 某個k0且aik（i=1，2,m）則線性規(guī)劃具有無界解退化基本可行解的判斷:存在某個基變量為零的基本可行解。無可行解的判斷：(1)當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并且存在Ri0時，則表明原線性規(guī)劃無可行解。(2) 當(dāng)?shù)谝浑A段的最優(yōu)值w0時，則原問題無可行解。1.5 單純形法 Simplex Method7/23/2022設(shè)有線性規(guī)劃其中Amn且r(A)=m,X0應(yīng)理解為X大于等于零向量，即xj0,j=1,2,n。1.5.3 計(jì)算公式1.5 單純形法 Simplex Method7/23/2022不妨假設(shè)A（P1，P2，Pn）中前m個列向量構(gòu)成一個可行基，記為B=(P1，P2，

45、Pm)。矩陣A中后nm列構(gòu)成的矩陣記為N（Pm+1,Pn）,則A可以寫成分塊矩陣A=（B，N）。對于基B，基變量為XB=（x1,x2，xm ）T, 非基變量為XN=(xm+1,xm+2,xn)T。則X可表示成 同理將C寫成分塊矩陣C=（CB，CN），CB=(C1,C2,Cm), CN=(Cm+1Cm+2，cn) 則AX=b可寫成1.5 單純形法 Simplex Method7/23/2022因?yàn)閞（B）=m（或|B|0）所以B 1存在，因此可有 令非基變量XN=0，XB=B1b，由 B是 可行基的假設(shè)，則得到基本可行解X=(B1b，0)T將目標(biāo)函數(shù)寫成 1.5 單純形法 Simplex Met

46、hod7/23/2022得到下列五個計(jì)算公式：(令XN=0) 1.5 單純形法 Simplex Method7/23/2022上述公式可用下面較簡單的矩陣表格運(yùn)算得到，設(shè)初始矩陣單純形表1-15 將B化為I（I為m階單位矩陣）,CB化為零,即求基本可行解和檢驗(yàn)數(shù)。用B1左乘表中第二行,得到表1-16XBXNbXBIB-1NB-1bCj-ZjCBCN0XBXNbXBBNbCj-ZjCBCN0表115表1161.5 單純形法 Simplex Method7/23/2022再將第二行左乘CB后加到第三行,得到XBZ0XBXNbXBIB-1NB-1bCj-Zj0CN-CBB1NCBB1b表1171.5 單純形法 Simplex Method7/23/2022五個公式的應(yīng)用【例1.24】線性規(guī)劃已知可行基 求(