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

1、數(shù)據(jù)、模型與決策 線性規(guī)劃Linear Programming1.1 LP的數(shù)學(xué)模型 Mathematical Model of LP1.2 圖解法 Graphical Method1.3 規(guī)范型 Standard form of LP1.4 根本概念 Basic Concepts1.5 單純形法 Simplex Method1.1 數(shù)學(xué)模型 Mathematical Model 1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 線性規(guī)劃通常研討資源的最優(yōu)利用、設(shè)備最正確運(yùn)轉(zhuǎn)等問題。例如，當(dāng)義務(wù)或目確實(shí)定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源 如資金、設(shè)備、原標(biāo)資

2、料、人工、時(shí)間等去完成確定的義務(wù)或目的；企業(yè)在一定的資源條件限制下，如何組織安排消費(fèi)獲得最好的經(jīng)濟(jì)效益如產(chǎn)品量最多 、利潤最大。線性規(guī)劃Linear Programming,縮寫為L(zhǎng)P是運(yùn)籌學(xué)的重要分支之一，在實(shí)踐中運(yùn)用得較廣泛，其方法也較成熟，借助計(jì)算機(jī)，使得計(jì)算更方便，運(yùn)用領(lǐng)域更廣泛和深化?！纠?.1】最優(yōu)消費(fèi)方案問題。某企業(yè)在方案期內(nèi)方案消費(fèi)甲、乙、丙三種產(chǎn)品。這些產(chǎn)品分別需求要在設(shè)備A、B上加工，需求耗費(fèi)資料C、D，按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工及所需求的資源如表1.1所示。知在方案期內(nèi)設(shè)備的加工才干各為200臺(tái)時(shí)，可供資料分別為360、300公斤；每消費(fèi)一件甲、乙、丙三種產(chǎn)

3、品，企業(yè)可獲得利潤分別為40、30、50元，假定市場(chǎng)需求無限制。企業(yè)決策者應(yīng)如何安排消費(fèi)方案，使企業(yè)在方案期內(nèi)總的利潤收入最大？1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP1.1.1 運(yùn)用模型舉例 產(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)品資源耗費(fèi)1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP【解】設(shè)x1、x2、x3 分別為甲、乙、丙三種產(chǎn)品的產(chǎn)量數(shù)學(xué)模型為：1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathe

4、matical 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=3400線性規(guī)劃的數(shù)學(xué)模型由決策變量 Decision variables 目的函數(shù)Objective function及約束條件Constraints構(gòu)成。稱為三個(gè)要素。其特征是：1處理問題的目的函數(shù)是多個(gè)決策變量的 線性函數(shù)，通常是求最大值或 最小值；2處理問題的約束條件是一組多個(gè)決策變量 的線性不等式或等式。怎樣區(qū)分一個(gè)模型是線性規(guī)劃模型？1.1 線

5、性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP【例1.2】某商場(chǎng)決議：營業(yè)員每周延續(xù)任務(wù)5天后延續(xù)休憩2天，輪番休憩。根據(jù)統(tǒng)計(jì)，商場(chǎng)每天需求的營業(yè)員如表1.2所示。表1.2 營業(yè)員需求量統(tǒng)計(jì)表商場(chǎng)人力資源部應(yīng)如何安排每天的上班人數(shù)，使商場(chǎng)總的營業(yè)員最少。 星期需要人數(shù)星期需要人數(shù)一300五480二300六600三350日550四4001.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP【解】 設(shè)xj(j=1，2，7)為休憩2天后星期一到星期日開場(chǎng)上班的營業(yè)員，那么這個(gè)問題的線性規(guī)劃模型為 1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Mode

6、l of LP星期需要人數(shù)星期需要人數(shù)一300五480二300六600三350日550四4001X10C1404=3001042X267C2301=30013X3146C3350=35004X4170C4400=40005X597C5480=48006X6120C6600=60007X717C7550=5500最優(yōu)解：Z617人【例1.3】合理用料問題。某汽車需求用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是1.5，1，0.7m，這些軸需求用同一種圓鋼來做，圓鋼長(zhǎng)度為4 m。如今要制造1000輛汽車，最少要用多少圓鋼來消費(fèi)這些軸？ 【解】這是一個(gè)條材下料問題 ，設(shè)切口寬度為零。 設(shè)一根圓鋼

7、切割成甲、乙、丙三種軸的根數(shù)分別為y1，y2，y3,那么切割方式可用不等式1.5y1+y2+0.7y34表示，求這個(gè)不等式關(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余料（m）00.30.5 0.1o.4 00.30.60.20.51.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP設(shè)xj(j=1,2,10)為第j種下料方案所用圓

8、鋼的根數(shù)。那么用料最少數(shù)學(xué)模型為:求下料方案時(shí)應(yīng)留意，余料不能超越最短毛坯的長(zhǎng)度；最好將毛坯長(zhǎng)度按降的次序陳列，即先切割長(zhǎng)度最長(zhǎng)的毛坯，再切割次長(zhǎng)的，最后切割最短的，不能脫漏了方案 。假設(shè)方案較多，用計(jì)算機(jī)編程排方案，去掉余料較長(zhǎng)的方案，進(jìn)展初選。1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 方案規(guī)格 1234 5678910需求量y1(根) 221 11 0 00001000y2 102 10 4 32101000y3 010 23 0 12451000余料（m）00.30.5 0.1o.4 00.30.60.20.51X15002X203X304X405X5

9、06X662.57X708X809X925010X100Z812.5【例1.4】配料問題。某鋼鐵公司消費(fèi)一種合金，要求的成分規(guī)格是：錫不少于28%，鋅不多于15%，鉛恰好10%，鎳要界于35%55%之間，不允許有其他成分。鋼鐵公司擬從五種不同級(jí)別的礦石中進(jìn)展冶煉，每種礦物的成分含量和價(jià)錢如表1.4所示。礦石雜質(zhì)在治煉過程中廢棄，現(xiàn)要求每噸合金本錢最低的礦物數(shù)量。假設(shè)礦石在冶煉過程中，合金含量沒有發(fā)生變化。表1.4 礦石的金屬含量 合金礦石錫%鋅%鉛%鎳%雜質(zhì)費(fèi)用（元/t ）1251010253034024000303026030155206018042020040202305851517551

10、901.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP解: 設(shè)xjj=1,2，5是第j 種礦石數(shù)量，得到以下線性規(guī)劃模型 留意，礦石在實(shí)踐冶煉時(shí)金屬含量會(huì)發(fā)生變化，建模時(shí)應(yīng)將這種變化思索進(jìn)去，有能夠是非線性關(guān)系。配料問題也稱配方問題、營養(yǎng)問題或混合問題，在許多行業(yè)消費(fèi)中都能遇到。1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP礦石錫%鋅%鉛%鎳%雜質(zhì)費(fèi)用（元/t ）1251010253034024000303026030155206018042020040202305851517551901X102X20.33333X304X40.5833

11、5X50.6667最優(yōu)解：Z=347.51.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP【例1.5】投資問題。某投資公司在第一年有200萬元資金，每年都有如下的投資方案可供思索采用：“假使第一年投入一筆資金，第二年又繼續(xù)投入此資金的50%，那么到第三年就可回收第一年投入資金的一倍金額。投資公司決議最優(yōu)的投資戰(zhàn)略使第六年所掌握的資金最多。第五年：(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+2

12、x7，整理后得到以下線性規(guī)劃模型 1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP【解】設(shè) x1：第一年的投資； x2：第一年的保管資金 x3：第二年新的投資；x4：第二年的保管資金 x5：第三年新的投資； x6：第三年的保管資金 x7：第四年新的投資 x8：第四年的保管資金 x9：第五年的保管資金 1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP1X155.28462X2144.71553X3117.07324X405X552.03256X607X7208.13018X809X90最優(yōu)解：Z 416.26萬元x1：第一年的投資； x2：

13、第一年的保管資金 x3：第二年新的投資；x4：第二年的保管資金 x5：第三年新的投資； x6：第三年的保管資金 x7：第四年新的投資 x8：第四年的保管資金 x9：第五年的保管資金 【例1.6】平衡配套消費(fèi)問題。某產(chǎn)品由2件甲、3件乙零件組裝而成。兩種零件必需經(jīng)過設(shè)備A、B上加工，每件甲零件在A、B上的加工時(shí)間分別為5分鐘和9分鐘，每件乙零件在A、B上的加工時(shí)間分別為4分鐘和10分鐘?，F(xiàn)有2臺(tái)設(shè)備A和3臺(tái)設(shè)備B，每天可供加工時(shí)間為8小時(shí)。為了堅(jiān)持兩種設(shè)備平衡負(fù)荷消費(fèi)，要求一種設(shè)備每天的加工總時(shí)間不超越另一種設(shè)備總時(shí)間1小時(shí)。怎樣安排設(shè)備的加工時(shí)間使每天產(chǎn)品的產(chǎn)量最大?！窘狻?設(shè)x1、x2為每天

14、加工甲、乙兩種零件的件數(shù)，那么產(chǎn)品的產(chǎn)量是設(shè)備A、B每天加工工時(shí)的約束為要求一種設(shè)備每臺(tái)每天的加工時(shí)間不超越另一種設(shè)備1小時(shí)的約束為 1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP目的函數(shù)線性化。產(chǎn)品的產(chǎn)量y等價(jià)于整理得到線性規(guī)劃模型 約束線性化。將絕對(duì)值約束寫成兩個(gè)不等式1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP1.1.2 線性規(guī)劃的普通模型普通地，假設(shè)線性規(guī)劃數(shù)學(xué)模型中，有m個(gè)約束，有n個(gè)決策變量xj, j=1,2,n，目的函數(shù)的變量系數(shù)用cj表示, cj稱為價(jià)值系數(shù)。約束條件的變量系數(shù)用aij表示，aij稱為工藝系數(shù)。約束條

15、件右端的常數(shù)用bi表示，bi稱為資源限量。那么線性規(guī)劃數(shù)學(xué)模型的普通表達(dá)式可寫成為了書寫方便，上式也可寫成： 1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP在實(shí)踐中普通xj0,但有時(shí)xj0或xj無符號(hào)限制。1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP1.什么是線性規(guī)劃，掌握線性規(guī)劃在管理中的幾個(gè)運(yùn)用例子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é)：圖解法1.2 圖解法 Graphical

16、Method圖解法的步驟：1.求可行解集合。分別求出滿足每個(gè)約束包括變量非 負(fù)要求的區(qū)域，其交集就是可行解集合，或稱為可行域；2.繪制目的函數(shù)圖形。先過原點(diǎn)作一條矢量指向點(diǎn)c1,c2)，矢量的方向就是目的函數(shù)添加的方向，稱為梯度方向，再作一條與矢量垂直的直線，這條直線就是目的函數(shù)圖形；3.求最優(yōu)解。根據(jù)目的函數(shù)求最大或最小挪動(dòng)目的函數(shù)直線，直線與可行域相交的點(diǎn)對(duì)應(yīng)的坐標(biāo)就是最優(yōu)解。普通地，將目的函數(shù)直線放在可行域中 求最大值時(shí)直線沿著矢量方向挪動(dòng) 求最小值時(shí)沿著矢量的反方向挪動(dòng)1.2 圖解法The Graphical Methodx1x2O1020304010203040(3,4)(15,10

17、)最優(yōu)解X=(15,10)最優(yōu)值Z=85例1.71.2 圖解法The Graphical Method246x1x2246最優(yōu)解X=(3,1)最優(yōu)值Z=5(3,1)min Z=x1+2x2例1.8(1,2)1.2 圖解法The Graphical Method246x1x2246X23,1X11,3(5,5)min Z=5x1+5x2例1.9有無窮多個(gè)最優(yōu)解即具有多重解,通解為 01 當(dāng)=0.5時(shí)=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) 1.2 圖解法The Graphical Method246x1x2246(1,2)無界解(無最優(yōu)解)max Z=x1+2x2例1.1

18、0 x1x2O10203040102030405050無可行解即無最優(yōu)解max Z=10 x1+4x2例1.111.2 圖解法The Graphical Method由以上例題可知，線性規(guī)劃的解有4種方式：1.有獨(dú)一最優(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 Method1.經(jīng)過圖解法了解線性規(guī)劃有幾種解的方式2.作圖的關(guān)鍵有三點(diǎn) (1)可行解區(qū)域要畫正確 (2)目的函數(shù)添加的方向不能畫錯(cuò) (3)目的函數(shù)的直線怎樣平行挪動(dòng)作業(yè)：教材P34 T7 1.2 圖

19、解法The Graphical Method下一節(jié)：線性規(guī)劃的規(guī)范型1.3 線性規(guī)劃的規(guī)范型Standard form of LP 在用單純法求解線性規(guī)劃問題時(shí)，為了討論問題方便，需將線性規(guī)劃模型化為一致的規(guī)范方式。1.3 線性規(guī)劃的規(guī)范型Standard form of LP線性規(guī)劃問題的規(guī)范型為:1目的函數(shù)求最大值或求最小值2約束條件都為等式方程3變量xj非負(fù)4常數(shù)bi非負(fù)max(或min)Z=c1x1+c2x2+cnxn1.3 線性規(guī)劃的規(guī)范型Standard form of LP注：本教材默許目的函數(shù)是 max或?qū)懗梢韵路绞剑?或用矩陣方式1.3 線性規(guī)劃的規(guī)范型Standard fo

20、rm of LP通常X記為： 稱為約束方程的系數(shù)矩陣，m是約束方程的個(gè)數(shù)，n是決策變量的個(gè)數(shù)，普通情況mn，且r()m。其中:1.3 線性規(guī)劃的規(guī)范型Standard form of LP【例1.12】將以下線性規(guī)劃化為規(guī)范型 【解】由于x3無符號(hào)要求 ，即x3取正值也可取負(fù)值，規(guī)范型中要求變量非負(fù)，所以令 1.3 線性規(guī)劃的規(guī)范型Standard form of LP (3)第二個(gè)約束條件是號(hào)，在號(hào) 左端減去剩余變量(Surplus variable)x5，x50。也稱松馳變量1.3 線性規(guī)劃的規(guī)范型Standard form of LP(2) 第一個(gè)約束條件是號(hào)，在左端參與松馳變量 (sl

21、ack variable) x4，x40,化為等式；(4)第三個(gè)約束條件是號(hào)且常數(shù)項(xiàng)為負(fù)數(shù)，因此在左邊參與松馳變量x6，x60，同時(shí)兩邊乘以1。 5目的函數(shù)是最小值，為了化為求最大值，令Z=Z,得到max Z=Z，即當(dāng)Z到達(dá)最小值時(shí)Z到達(dá)最大值，反之亦然。 綜合起來得到以下規(guī)范型 1.3 線性規(guī)劃的規(guī)范型Standard form of LP 當(dāng)某個(gè)變量xj0時(shí),令x/j=xj 。 當(dāng)某個(gè)約束是絕對(duì)值不等式時(shí)，將絕對(duì)值不等式化為兩個(gè)不等式，再化為等式，例如約束 將其化為兩個(gè)不等式 再參與松馳變量化為等式。 1.3 線性規(guī)劃的規(guī)范型Standard form of LP【例1.13】將下例線性規(guī)

22、劃化為規(guī)范型【解】 此題關(guān)鍵是將目的函數(shù)中的絕對(duì)值去掉。令 那么有1.3 線性規(guī)劃的規(guī)范型Standard form of LP得到線性規(guī)劃的規(guī)范方式 1.3 線性規(guī)劃的規(guī)范型Standard form of LP對(duì)于axb(a、b均大于零)的有界變量化為規(guī)范方式有兩種方法，一種方法是添加兩個(gè)約束xa及xb，另一種方法是令=xa，那么axb等價(jià)于0ba，添加一個(gè)約束ba并且將原問題一切x用x=+a交換。1.如何化規(guī)范方式？ 可以對(duì)照四條規(guī)范逐一判別！ 規(guī)范方式是人為定義的，目的函數(shù)可以是求最小值。2.用WinQSB軟件求解時(shí)，不用化成規(guī)范型。圖解法時(shí)不用化為規(guī)范型。3.單純形法求解時(shí)一定要化為

23、規(guī)范型。作業(yè)：教材P34 T 81.3 線性規(guī)劃的規(guī)范型Standard form of LP下一節(jié)：根本概念1.4 線性規(guī)劃的有關(guān)概念Basic Concepts of LP 設(shè)線性規(guī)劃的規(guī)范型 max Z=CX 1.1 AX=b 1.2 X 0 1.3式中A 是mn矩陣，mn并且rA=m，顯然A中至少有一個(gè)mm子矩陣B，使得rB=m。1.4 根本概念Basic Concepts 基 (basis)A中mm子矩陣B并且有rB=m，那么稱B是線性規(guī)劃的一個(gè)基或基矩陣basis matrix 。當(dāng)m=n時(shí)，基矩陣獨(dú)一，當(dāng)mn時(shí)，基矩陣就能夠有多個(gè)，但數(shù)目不超越【例1.14】線性規(guī)劃 求一切基矩陣

24、。 【解】約束方程的系數(shù)矩陣為25矩陣 容易看出r(A)=2，2階子矩陣有C52=10個(gè)，其中第1列與第3列構(gòu)成的2階矩陣不是一個(gè)基，基矩陣只需9個(gè)，即1.4 根本概念Basic Concepts 由線性代數(shù)知，基矩陣B必為非奇特矩陣并且|B|0。當(dāng)矩陣B的行列式等式零即|B|=0時(shí)就不是基 當(dāng)確定某一矩陣為基矩陣時(shí)，那么基矩陣對(duì)應(yīng)的列向量稱為基向量(basis vector)，其他列向量稱為非基向量 基向量對(duì)應(yīng)的變量稱為基變量(basis variable)，非基向量對(duì)應(yīng)的變量稱為非基變量 在上例中B2的基向量是A中的第一列和第四列，其他列向量是非基向量，x1、x4是基變量，x2、x3、x5

25、是非基變量?；兞?、非基變量是針對(duì)某一確定基而言的，不同的基對(duì)應(yīng)的基變量和非基變量也不同。1.4 根本概念Basic Concepts 可行解(feasible solution) 滿足式1.2及1.3的解X=x1,x2，xn)T 稱為可行解 。根本可行解(basis feasible solution) 假設(shè)根本解是可行解那么稱為是根本可行解也稱基可行解。 例如， 與X=0，0，0，3，2，都是例1 的可行解。 根本解(basis solution) 對(duì)某一確定的基B，令非基變量等于零，利用式1. 解出基變量，那么這組解稱為基的根本解。 最優(yōu)解(optimal solution) 滿足式 1

26、 .1的可行解稱為最優(yōu)解，即是使得目的函數(shù)到達(dá)最大值的可行解就是最優(yōu)解，例如可行解 是例2的最優(yōu)解。非可行解(Infeasible solution) 無界解 (unbound solution)1.4 根本概念Basic Concepts 顯然，只需根本解中的基變量的解滿足式1.的非負(fù)要求，那么這個(gè)根本解就是根本可行解。 在例1.13中，對(duì)來說，x1,x2是基變量，x3,x4，x5是非基變量，令x3=x4=x5=0，那么式1.為對(duì)B2來說，x1,x4,為基變量，令非變量x2,x3,x5為零，由式1.2得到 ，x4=4，因|B1|，由克萊姆法那么知，x1、x2有獨(dú)一解x12/5,x2=1那么

27、根本解為1.4 根本概念Basic Concepts 由于 是根本解，從而它是根本可行解，在 中x10,因此不是可行解，也就不是根本可行解。 反之，可行解不一定是根本可行解例如 滿足式1.21.3，但不是任何基矩陣的根本解。根本解為1.4 根本概念Basic Concepts 可行基 基可行解對(duì)應(yīng)的基稱為可行基；最優(yōu)基根本最優(yōu)解對(duì)應(yīng)的基稱為最優(yōu)基；如上述B3就是最優(yōu)基，最優(yōu)基也是可行基。當(dāng)最優(yōu)解獨(dú)一時(shí)，最優(yōu)解亦是根本最優(yōu)解，當(dāng)最優(yōu)解不獨(dú)一時(shí)，那么最優(yōu)解不一定是根本最優(yōu)解。例如右圖中線段 的點(diǎn)為最優(yōu) 解時(shí)，Q1點(diǎn)及Q2點(diǎn)是根本最優(yōu)解,線段 的內(nèi)點(diǎn)是最優(yōu)解而不是根本最優(yōu)解。 根本最優(yōu)解 最優(yōu)解是根

28、本解稱為根本最優(yōu)解。例如，滿足式1.1(1.3)是最優(yōu)解,又是B3的根本解,因此它是根本最優(yōu)解。1.4 根本概念Basic Concepts 根本最優(yōu)解、最優(yōu)解、根本可行解、根本解、可行解的關(guān)系如下所示：根本最優(yōu)解根本可行解可行解最 優(yōu) 解根本解例如,B點(diǎn)和D點(diǎn)是可行解,不是根本解;C點(diǎn)是根本可行解;A點(diǎn)是根本最優(yōu)解,同時(shí)也是最優(yōu)解、根本可行解、根本解和可行解。1.4 根本概念Basic Concepts 凸集(Convex set)設(shè)K是n維空間的一個(gè)點(diǎn)集，對(duì)恣意兩點(diǎn) 時(shí)，那么稱K為凸集。 就是以X1、X2為端點(diǎn)的線段方程，點(diǎn)X的位置由的值確定，當(dāng)=0時(shí)，X=X2，當(dāng)=1時(shí)X=X1凸組合(C

29、onvex combination) 設(shè) 是Rn 中的點(diǎn)假設(shè)存在 使得 成立， 那么稱X為 的凸組合。1.4 根本概念Basic Concepts 極點(diǎn)(Extreme point) 設(shè)K是凸集， ，假設(shè)X不能用K中兩個(gè)不同的 點(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 Method3018最

30、優(yōu)解X=(18，4，0，0)T，最優(yōu)值Z=70O20301040(3,4)X(3)=(18,4)最優(yōu)解X=(18,4)最優(yōu)值Z=70X(1)=(0,0)2010 x2x1301.5 單純形法 Simplex MethodX(2)=(0,10)單純形法全過程的計(jì)算，可以用列表的方法計(jì)算更為簡(jiǎn)約，這種表格稱為單純形表表1.4。計(jì)算步驟：1.求初始基可行解，列出初始單純形表，求出檢驗(yàn)數(shù)。其中基變量的檢驗(yàn)數(shù)必為零； 2.判別： a假設(shè)jj，n得到最解； b某個(gè)k0且aiki=1，2,m那么線性規(guī)劃具有無界解(見例1.18)。 c假設(shè)存在k0且aik (i=1,m)不全非正，那么進(jìn)展換基；1.5 單純形

31、法 Simplex Method第個(gè)比值最小 ，選最小比值對(duì)應(yīng)行的基變量為出基變量，假設(shè)有一樣最小比值，那么任選一個(gè)。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)基變量【例1.16】 用單純形法求解【解】將數(shù)學(xué)模型化為規(guī)范方式：不難看出x4、x5可作為初始基變量，單純法計(jì)算結(jié)果如表 1.所示 。 1.5 單純形法 Simplex MethodCj12100b

32、CBXBx1x2x3x4x50 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 Method【例1.17】用單純形法求解 【解】 這是一個(gè)極小化的線性規(guī)劃問題,可以將其化為極大化問題求解,也可以直接求解,這時(shí)判別規(guī)范是：j0(j=1，n)時(shí)得到最優(yōu)解。容易察看到,系數(shù)矩陣中有一個(gè)3階單位矩陣,x3、x4、x5為基變

33、量。目的函數(shù)中含有基變量x4,由第二個(gè)約束得到x4=6+x1x2，并代入目的函數(shù)消去x4得1.5 單純形法 Simplex MethodXBx1x2x3x4x5bx3x4x51-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極小值問題,留意判別規(guī)范,選進(jìn)基變量時(shí),應(yīng)選j0, x2進(jìn)基，而a120，a220且aiki=1，2,m那么線性規(guī)劃具有無界解退化根本可行解的判別:存在某個(gè)基變量為零的根本可行解。1

34、.5 單純形法 Simplex Method在實(shí)踐問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法?！纠?.20】用大M法解 以下線性規(guī)劃1. 大M 單純形法1.5.2大M和兩階段單純形法1.5 單純形法 Simplex Method【解】首先將數(shù)學(xué)模型化為規(guī)范方式式中x4，x5為松弛變量，x5可作為一個(gè)基變量，第一、三約束中分別參與人工變量x6、x7，目的函數(shù)中參與Mx6Mx7一項(xiàng)，得到人工變量單純形法數(shù)

35、學(xué)模型用前面引見的單純形法求解，見下表。 1.5 單純形法 Simplex MethodCj32100MMbCBXBx1x2x3x4x5x6x7M0Mx6x5x74123121211000101000014101j3-2M2+M-1+2MM000M01x6x5x3632532001100010100381j5-6M5M0M00201x2x5x36/53/52/51000011/53/52/50103/531/511/5j50000231x2x1x301010000111025/32/31331/319/3j0005-25/31初始表中的檢驗(yàn)數(shù)有兩種算法，第一種算法是利用第一、三約束將x6、x7

36、的表達(dá)式代入目的涵數(shù)消去x6和x7，得到用非基變量表達(dá)的目的函數(shù)，其系數(shù)就是檢驗(yàn)數(shù)；第二種算法是利用公式計(jì)算，如2M是一個(gè)很大的籠統(tǒng)的數(shù)，不需求給出詳細(xì)的數(shù)值，可以了解為它能大于給定的任何一個(gè)確定數(shù)值；最優(yōu)解X31/3，13，19/3，0，0)T；最優(yōu)值Z152/3留意：1.5 單純形法 Simplex Method【例1.21】求解線性規(guī)劃 【解】參與松馳變量x3、x4化為規(guī)范型在第二個(gè)方程中參與人工變量x5，目的函數(shù)中加上M x5一項(xiàng)，得到 1.5 單純形法 Simplex Method用單純形法計(jì)算如下表所示。 Cj5800MbCBXBx1x2x3x4x50Mx3x53112100101

37、64j5M8+2M0M05Mx1x5101/37/31/31/3010122j029/3+7/3M5/3+1/3MM01.5 單純形法 Simplex Method表中j0，j=1，2，5，從而得到最優(yōu)解X=2，0，0，0，2， Z=10+2M。但最優(yōu)解中含有人工變量x50闡明這個(gè)解是偽最優(yōu)解，是不可行的，因此原問題無可行解。 兩階段單純形法與大M單純形法的目的類似，將人工變量從基變量中換出，以求出原問題的初始根本可行解。將問題分成兩個(gè)階段求解，第一階段的目的函數(shù)是約束條件是參與人工變量后的約束方程，當(dāng)?shù)谝浑A段的最優(yōu)解中沒有人工變量作基變量時(shí)，得到原線性規(guī)劃的一個(gè)根本可行解，第二階段就以此為根

38、底對(duì)原目的函數(shù)求最優(yōu)解。當(dāng)?shù)谝浑A段的最優(yōu)解w0時(shí)，闡明還有不為零的人工變量是基變量，那么原問題無可行解。1.5 單純形法 Simplex Method2. 兩階段單純形法【例1.22】用兩階段單純形法求解例19的線性規(guī)劃?！窘狻恳?guī)范型為在第一、三約束方程中參與人工變量x6、x7后，第一階段問題為用單純形法求解，得到第一階段問題的計(jì)算表如下：1.5 單純形法 Simplex MethodCj0000011 bCBXBx1x2x3x4x5x6x7101x6x5x74123121211000101000014101j2121000100 x6x5x3632532001100010100381j650

39、100000 x2x5x36/53/52/51000011/53/52/50103/531/511/5j000001.5 單純形法 Simplex Method最優(yōu)解為 最優(yōu)值w=0。第一階段最后一張最優(yōu)表闡明找到了原問題的一組基可行解，將它作為初始基可行解，求原問題的最優(yōu)解，即第二階段問題為1.5 單純形法 Simplex MethodCj32-100bCBXBx1x2x3x4x5201x2x5x3100001010j50000231x2x1x3010100001110213j0005Cj32100bCBXBx1x2x3x4x5201x2x5x36/53/52/51000011/53/52/

40、50103/531/5 11/5j5 0000231x2x1x301010000111025/32/31331/319/3j000525/3用單純形法計(jì)算得到下表最優(yōu)解X31/3，13，19/3，0，0)T；最優(yōu)值Z152/31.5 單純形法 Simplex Method【例1.23】用兩階段法求解例1.21的線性規(guī)劃?！窘狻坷?.21的第一階段問題為用單純形法計(jì)算如下表：1.5 單純形法 Simplex MethodCj00001bCBXBx1x2x3x4x501x3x5311210010164j1201001x1x5101/37/31/31/3010122j07/31/310j0,得到第一

41、階段的最優(yōu)解X=(2,0,0,0,2)T,最優(yōu)目的值w=20,x5仍在基變量中,從而原問題無可行解。1.5 單純形法 Simplex Method解的判別獨(dú)一最優(yōu)解的判別：最優(yōu)表中一切非基變量的檢驗(yàn)數(shù)非零,那么線 規(guī)劃具有獨(dú)一最優(yōu)解 多重最優(yōu)解的判別:最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,那么線那么性規(guī)劃具有多重最優(yōu)解。 無界解的判別: 某個(gè)k0且aiki=1，2,m那么線性規(guī)劃具有無界解退化根本可行解的判別:存在某個(gè)基變量為零的根本可行解。無可行解的判別：(1)當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并且存在Ri0時(shí)，那么闡明原線性規(guī)劃無可行解。(2) 當(dāng)?shù)谝浑A段的最優(yōu)值w0時(shí)，那么原問題無可行解。1.5

42、 單純形法 Simplex Method設(shè)有線性規(guī)劃其中Amn且r(A)=m,X0應(yīng)了解為X大于等于零向量，即xj0,j=1,2,n。1.5.3 計(jì)算公式1.5 單純形法 Simplex Method無妨假設(shè)AP1，P2，Pn中前m個(gè)列向量構(gòu)成一個(gè)可行基，記為B=(P1，P2，Pm)。矩陣A中后nm列構(gòu)成的矩陣記為NPm+1,Pn,那么A可以寫成分塊矩陣A=B，N。對(duì)于基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

43、.5 單純形法 Simplex Method由于rB=m或|B|0所以B 1存在，因此可有 令非基變量XN=0，XB=B1b，由 B是 可行基的假設(shè)，那么得到根本可行解X=(B1b，0)T將目的函數(shù)寫成 1.5 單純形法 Simplex Method得到以下五個(gè)計(jì)算公式：(令XN=0) 1.5 單純形法 Simplex Method上述公式可用下面較簡(jiǎn)單的矩陣表格運(yùn)算得到，設(shè)初始矩陣單純形表1-15 將B化為II為m階單位矩陣,CB化為零,即求根本可行解和檢驗(yàn)數(shù)。用B1左乘表中第二行,得到表1-16XBXNbXBIB-1NB-1bCj-ZjCBCN0XBXNbXBBNbCj-ZjCBCN0表115表1161.5 單純形法 Simplex Method再將第二行左乘CB后加到第三行,得到XBZ0XBXNbXBIB-1NB-1bCj-Zj0CN-CBB1NCBB1b表1171.5 單純形法 Simple