第2章線性規(guī)劃與單純形法

1、第二章第二章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法線性規(guī)劃模型線性規(guī)劃模型線性規(guī)劃圖解法線性規(guī)劃圖解法線性規(guī)劃的基本概念線性規(guī)劃的基本概念線性規(guī)劃的基本性質(zhì)線性規(guī)劃的基本性質(zhì)單純形法單純形法線性規(guī)劃應(yīng)用舉例線性規(guī)劃應(yīng)用舉例本章內(nèi)容要點(diǎn)本章內(nèi)容要點(diǎn)線性規(guī)劃概述線性規(guī)劃概述n1939年蘇聯(lián)數(shù)學(xué)家康托羅維奇在年蘇聯(lián)數(shù)學(xué)家康托羅維奇在生產(chǎn)組織與計(jì)劃中的數(shù)生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法學(xué)方法一書中提出線性規(guī)劃問題，也未引起重視。一書中提出線性規(guī)劃問題，也未引起重視。n1947年美國數(shù)學(xué)家年美國數(shù)學(xué)家G.B.Dantzing提出求解線性規(guī)劃的提出求解線性規(guī)劃的單純形單純形法法，為這門學(xué)科奠定了基礎(chǔ)。，為這門學(xué)

2、科奠定了基礎(chǔ)。n1947年美國數(shù)學(xué)家年美國數(shù)學(xué)家J.von諾伊曼提出諾伊曼提出對(duì)偶對(duì)偶理論理論,開創(chuàng)了線性規(guī)開創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴(kuò)大它的應(yīng)用范圍和解題能力。劃的許多新的研究領(lǐng)域，擴(kuò)大它的應(yīng)用范圍和解題能力。n1951年美國經(jīng)濟(jì)學(xué)家年美國經(jīng)濟(jì)學(xué)家T.C.庫普曼斯把線性規(guī)劃應(yīng)用到經(jīng)濟(jì)領(lǐng)庫普曼斯把線性規(guī)劃應(yīng)用到經(jīng)濟(jì)領(lǐng)域，為此與康托羅維奇一起獲域，為此與康托羅維奇一起獲1975年年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。n1979年蘇聯(lián)的年蘇聯(lián)的Khachian提出提出“橢球法橢球法”n1984年印度的年印度的Karmarkar提出提出“投影梯度法投影梯度法”n 線性規(guī)劃是研究線性不等式組的理論，

3、或者說是研究（高線性規(guī)劃是研究線性不等式組的理論，或者說是研究（高維空間中）凸多面體的理論，是線性代數(shù)的應(yīng)用和發(fā)展。維空間中）凸多面體的理論，是線性代數(shù)的應(yīng)用和發(fā)展。Slide 21. 線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型n1.1 線性規(guī)劃問題的提出線性規(guī)劃問題的提出n1.2 線性規(guī)劃模型的一般形式線性規(guī)劃模型的一般形式n1.3 線性規(guī)劃問題隱含的假定線性規(guī)劃問題隱含的假定n1.4 線性規(guī)劃問題的圖解法線性規(guī)劃問題的圖解法n1.5 線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性規(guī)劃問題的標(biāo)準(zhǔn)形式n1.6 線性規(guī)劃問題的解線性規(guī)劃問題的解Slide 3運(yùn)籌學(xué)運(yùn)籌學(xué) 第二章第二章 線性規(guī)劃與單純形法線性規(guī)劃與

4、單純形法Slide 41. 線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型 設(shè)設(shè) 備備原原 料料A A原原 料料B B 1 4 0 2 0 4 8臺(tái) 時(shí) 1 6 k g 1 2 k g 例例1 某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)和原料品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)和原料A、B的消耗量如下表。的消耗量如下表。 該工廠每生產(chǎn)一件該工廠每生產(chǎn)一件產(chǎn)品產(chǎn)品可獲利可獲利2元，每生產(chǎn)一件產(chǎn)元，每生產(chǎn)一件產(chǎn)品品可獲利可獲利3元，問應(yīng)如何安排生元，問應(yīng)如何安排生產(chǎn)計(jì)劃能使該廠獲利最多？產(chǎn)計(jì)劃能使該廠獲利最多？ 1.1線性規(guī)劃問題的提出線性規(guī)劃

5、問題的提出運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 5預(yù)備知識(shí)：預(yù)備知識(shí)：1、融會(huì)貫通地理解要解決的問題，搞清在什么條、融會(huì)貫通地理解要解決的問題，搞清在什么條件下，要件下，要追求什么目標(biāo)追求什么目標(biāo)？2、這個(gè)要實(shí)現(xiàn)的目標(biāo)是由一組、這個(gè)要實(shí)現(xiàn)的目標(biāo)是由一組變量變量決定的決定的決決策變量策變量。定義決策變量，每一個(gè)問題用一組決策變。定義決策變量，每一個(gè)問題用一組決策變量（量（x1,x2,x3,xn）來表示某一方案，每組決策變量來表示某一方案，每組決策變量的值就代表一個(gè)具體方案；的值就代表一個(gè)具體方案；3、用決策變量的、用決策變量的線性函數(shù)線性函數(shù)來表示寫出所要追

6、求的來表示寫出所要追求的目標(biāo)，我們稱之為目標(biāo)，我們稱之為目標(biāo)函數(shù)目標(biāo)函數(shù)。按問題的不同，可能。按問題的不同，可能要求這目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。要求這目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。4、這些決策變量需要一定的限制和約束，這些約、這些決策變量需要一定的限制和約束，這些約束條件可以用一組束條件可以用一組線性等式線性等式或或不等式不等式來表示。來表示。運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 6建立模型建立模型 設(shè)計(jì)劃期內(nèi)產(chǎn)品、的產(chǎn)量分別為x1，x2Z=2x1+3x2x1+2x284x1 16 4x212x1, x20 設(shè)設(shè) 備備原料原料 A A原料原料 B B 1

7、4 0 2 0 4 8 臺(tái)時(shí) 16kg 12kgMax運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 7建立模型建立模型n整理得整理得：Max Z=2x1+3x2 約束條件：約束條件：s.t. s.t. ： x1 + 2+ 2x2 8 8 4 4x1 16 16 4 4x2 12 12 x1 , x2 0 0 運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 11n設(shè)置決策變量，它們體現(xiàn)解決問題的方案。小結(jié)小結(jié)1：建模的基本步驟：建模的基本步驟 確定目標(biāo)函數(shù)，它是決策變量的函數(shù)。 確定決策變量的取值范圍，給出優(yōu)化方向。 確定約束條件，它們是

8、含有決策變量的確定約束條件，它們是含有決策變量的不等式或等式。不等式或等式。Slide 12小結(jié)小結(jié)2 2：數(shù)學(xué)模型的共同結(jié)構(gòu)：數(shù)學(xué)模型的共同結(jié)構(gòu) 1 1. .存在一組決策變量，對(duì)它們可有非負(fù)要求；存在一組決策變量，對(duì)它們可有非負(fù)要求； 2. 2.存在一個(gè)以決策變量為自變量的目標(biāo)函數(shù)，且它存在一個(gè)以決策變量為自變量的目標(biāo)函數(shù)，且它為為線性函數(shù)；線性函數(shù)； 3. 3.存在一組約束條件，且每個(gè)條件都是由決策變量存在一組約束條件，且每個(gè)條件都是由決策變量構(gòu)成的構(gòu)成的線性線性不等式或等式；不等式或等式； 4. 4.結(jié)構(gòu)要求出這樣的變量組，或者說決策向量結(jié)構(gòu)要求出這樣的變量組，或者說決策向量X X，在滿

9、足約束條件和非負(fù)約束的同時(shí)，使相應(yīng)的目在滿足約束條件和非負(fù)約束的同時(shí)，使相應(yīng)的目標(biāo)函數(shù)值達(dá)到標(biāo)函數(shù)值達(dá)到 最大或者最小。簡言之，在一定最大或者最小。簡言之，在一定條件下使目標(biāo)函數(shù)優(yōu)化。條件下使目標(biāo)函數(shù)優(yōu)化。具有上述結(jié)構(gòu)的數(shù)學(xué)模型為線性規(guī)劃模型運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 13一類是在現(xiàn)有人力、物力、財(cái)力的條件下，研一類是在現(xiàn)有人力、物力、財(cái)力的條件下，研究如何合理地計(jì)劃和安排，使得某一目標(biāo)達(dá)到最大究如何合理地計(jì)劃和安排，使得某一目標(biāo)達(dá)到最大（產(chǎn)量最大、利潤最大）。（產(chǎn)量最大、利潤最大）。另一類是任務(wù)確定后，如何計(jì)劃和安排，用最另一類是任務(wù)確定后，如

10、何計(jì)劃和安排，用最少的人力、物力和財(cái)力，去實(shí)現(xiàn)該任務(wù)，使得成本少的人力、物力和財(cái)力，去實(shí)現(xiàn)該任務(wù)，使得成本最小。最小。線性規(guī)劃研究對(duì)象：線性規(guī)劃研究對(duì)象：n決策變量決策變量n目標(biāo)函數(shù)目標(biāo)函數(shù)n約束條件約束條件運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 14一般形式一般形式目標(biāo)函數(shù)目標(biāo)函數(shù)： Max （Min） z = c1 x1 + c2 x2 + + cn xn （2-1） 約束條件約束條件： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1

11、+ am2 x2 + + amn xn （ =, ）bm （2-2） x1 ，x2 ， ，xn 0 （2-3） 1.2 線性規(guī)劃模型的一般形式運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 15運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 162132maxxxz124164822121xxxx0,21xx例1x2=-(2/3)x1+z/3目標(biāo)函數(shù)目標(biāo)函數(shù)等值線等值線2132xxz可行解可行解 滿足約束條滿足約束條件（包括非負(fù)條件）件（包括非負(fù)條件）的一組變量值，稱可的一組變量值，稱可行解。所有可行解的行解。所有可行解的集合為可行解集（

12、或集合為可行解集（或可行域）?？尚杏颍?。運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 17 Max Max z=2x1+3x2s.t.s.t. x1+ 2x28 4x1 16 4x212 x1 0, x20目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線最優(yōu)解最優(yōu)解840 x1x23423Q3（2，3）Q4（3，0）Q2（4，2）Q1（4，0）可行域可行域目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線: :x2=-(2/3)=-(2/3)x1+z/3+z/3運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 18確定目標(biāo)函數(shù)值增加的方向的方法：確定目標(biāo)函數(shù)值增加的方向的方法：z

13、cxccx212121:) 0(. 122211化為將cxcxczzc21）從而若01(022cc2211xcxcz2121,ccxzxz運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 19例例2 2： max max z=z=2 2x1+ 3+ 3x2s.t.s.t. x1+ 2+ 2x288 4 4x1 16 16 4 4x212 12 x1 0, 0, x200目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線最優(yōu)解最優(yōu)解8x1x2403423可行域可行域無窮多最優(yōu)解4運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 20例例3 3： max max z=

14、z=x1+ +x2s.t.s.t. -2 -2x1+ + x244 x1 - - x2 2 2 x1 0, 0, x200目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線4x1x202可行域?yàn)闊o界區(qū)域，目標(biāo)值可無限增大，無界解，稱為無最優(yōu)解運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 21例例4 4： max max z=z=2 2x1+ + 4 4x2s.t.s.t. x1+ 2+ 2x288 4 4x1 16 16 4 4x212 12 x1 0, 0, x200最優(yōu)解最優(yōu)解8x1x2403423可行域可行域85 . 121xx85 . 121xx（無可行域）（無可行域）無可行解

15、無可行解線性規(guī)劃問題圖解法的基本步驟線性規(guī)劃問題圖解法的基本步驟n在平面上建立直角坐標(biāo)系；在平面上建立直角坐標(biāo)系；n圖示約束條件，確定可行域和頂點(diǎn)圖示約束條件，確定可行域和頂點(diǎn)坐標(biāo)；坐標(biāo)；n圖示目標(biāo)函數(shù)（等值線）和移動(dòng)方圖示目標(biāo)函數(shù)（等值線）和移動(dòng)方向；向；n尋找最優(yōu)解。尋找最優(yōu)解。運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 22唯一最優(yōu)解無窮多最優(yōu)解x1x2x1x2 解無界無可行解 線性規(guī)劃問題如線性規(guī)劃問題如果有最優(yōu)解果有最優(yōu)解, ,則最則最優(yōu)解一定在可行域優(yōu)解一定在可行域的邊界上取得的邊界上取得, ,特特別地別地, ,一定可在可一定可在可行域的頂點(diǎn)上取得行

16、域的頂點(diǎn)上取得. .小結(jié)小結(jié)運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 24線性規(guī)劃問題解的狀況線性規(guī)劃問題解的狀況無可行解無可行解有可行解有可行解 無最優(yōu)解無最優(yōu)解有最優(yōu)解有最優(yōu)解唯一最優(yōu)解唯一最優(yōu)解無窮多最優(yōu)解無窮多最優(yōu)解線性規(guī)劃問題線性規(guī)劃問題運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 25兩個(gè)直觀的結(jié)論v 線性規(guī)劃的線性規(guī)劃的可行區(qū)域可行區(qū)域D D是若干是若干半平面半平面的的交交集集如果存在最優(yōu)解，它一定在可行域的某個(gè)如果存在最優(yōu)解，它一定在可行域的某個(gè)頂點(diǎn)得到頂點(diǎn)得到v若在兩個(gè)頂點(diǎn)得到最優(yōu)解，那么兩頂點(diǎn)連若在兩個(gè)頂點(diǎn)得到

17、最優(yōu)解，那么兩頂點(diǎn)連線上任一點(diǎn)都是最優(yōu)解線上任一點(diǎn)都是最優(yōu)解運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 26練習(xí)練習(xí):用圖解法求解以下用圖解法求解以下LP模型模型無符號(hào)限制21212121,2322265maxxxxxxxxxz運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 27Answerx1x2-2x1+3x2=2x1-2x2=20Ax1= -10,x2= -6,z= -86無符號(hào)限制21212121,2322265maxxxxxxxxxz練習(xí)練習(xí) ：用圖解法求解以下模型：用圖解法求解以下模型運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與

18、單純形法線性規(guī)劃與單純形法Slide 28x2504030201010203040 x1x2504030201010203040 x1x2504030201010203040 x12x1+x2 504x1+3x2 120 x2504030201010203040 x1O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）x2504030201010203040 x1x2504030201010203040 x1x2504030201010203040 x1Q2（15，20）運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 361.5 線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性

19、規(guī)劃問題的標(biāo)準(zhǔn)型max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm x1, x2, , xn0其中，bi0 (i=1,2,m) 否則等式兩端乘以-1，當(dāng)某一bi=0時(shí)，出現(xiàn)退化1 1、目標(biāo)函數(shù)為、目標(biāo)函數(shù)為極大化。極大化。2 2、所有的約束、所有的約束條件都是等式，條件都是等式，且右端常數(shù)均為且右端常數(shù)均為非負(fù)。非負(fù)。3 3、所有決策變、所有決策變量均非負(fù)。量均非負(fù)。運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 38n,j;bbbb;aaaP;xxx

20、X;c ,c ,cCn ,j,xbxPCXzmax:Mmmjjjjnnjnjjj 212102121212111約束條件：目標(biāo)函數(shù)：用向量形式表示的標(biāo)準(zhǔn)形式線性規(guī)劃用向量形式表示的標(biāo)準(zhǔn)形式線性規(guī)劃運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 39用矩陣形式表示的標(biāo)準(zhǔn)形式線性規(guī)劃用矩陣形式表示的標(biāo)準(zhǔn)形式線性規(guī)劃Tnnmnmn x,x,xX;P,P,PaaaaAXbAXCXzmax:M21m12111111bbb0000決策變量向量：；資源向量：零向量：系數(shù)矩陣：約束條件：目標(biāo)函數(shù)：運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 40如何轉(zhuǎn)

21、化為標(biāo)準(zhǔn)型：如何轉(zhuǎn)化為標(biāo)準(zhǔn)型：1.目標(biāo)函數(shù)為最小：目標(biāo)函數(shù)為最?。?min z=c1x1+c2x2+cnxn令令z =-z ,變?yōu)樽優(yōu)?max z = -c1x1- c2x2- -cnxn2.約束條件為不等式：約束條件為不等式：加入非負(fù)變量加入非負(fù)變量xn+1，稱為稱為松弛變量松弛變量，有，有 ai1x1+ai2x2+ainxn+xn+1=bi（2）約束條件為）約束條件為 “”： ai1x1+ai2x2+ainxnbi減去非負(fù)變量減去非負(fù)變量xn+1，稱為稱為剩余變量，有，有 ai1x1+ai2x2+ainxn - xn+1=bi（1）約束條件為約束條件為“”：ai1x1+ai2x2+ainx

22、nbi運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 413.決策變量決策變量xj無非負(fù)約束無非負(fù)約束。（1） xj 0，令xj= - xj ， xj 0（2） xj無約束，令xj= xj - xj，xj ,xj 04. 右端項(xiàng)右端項(xiàng)bi 0 ,不等式或等式兩端同時(shí)乘不等式或等式兩端同時(shí)乘 1運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 42例例1：2132maxxxz124164822121xxxx0,21xx x1 + 2x2 + x3 =8 4x1 +x4 =16 4x2 +x5 =12max z=2x1 + 3x2 + 0 x3

23、+0 x4 +0 x5 x1 ,x2 ,x3 ,x4 ,x5 0運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 43例2：將下述線性規(guī)劃問題化為標(biāo)準(zhǔn)形32132minxxxz0,42843104321321321321xxxxxxxxxxxnx3無約束，令無約束，令x3= x4-x5 ，x4，x5 0n第一個(gè)約束不等式第一個(gè)約束不等式 ，在左，在左端加入松弛變量端加入松弛變量x6n第二個(gè)約束不等式第二個(gè)約束不等式 ，在左，在左端端減去減去剩余變量剩余變量x7n目標(biāo)函數(shù)為最小目標(biāo)函數(shù)為最小，令令z =-z 運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形

24、法Slide 44例2：將下述線性規(guī)劃問題化為標(biāo)準(zhǔn)形32132minxxxz0,42843104321321321321xxxxxxxxxxx7 , 6 , 5 , 4 , 2 , 1, 04228443104354217542165421jxxxxxxxxxxxxxxxj5421332maxxxxxz+0 +06x7x運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 451.6 線性規(guī)劃問題的解), 2 , 1(0), 2 , 1(max11njxmibxaxczjnjijijjnjj1-41-51-6運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法

25、Slide 46 1.可行解 可行解可行解 滿足約束條件（包括非負(fù)滿足約束條件（包括非負(fù)條件）的一組變量值，稱可行解。條件）的一組變量值，稱可行解。所有可行解的集合稱為可行域。所有可行解的集合稱為可行域。 最優(yōu)解最優(yōu)解 使目標(biāo)函數(shù)達(dá)到最大的可行使目標(biāo)函數(shù)達(dá)到最大的可行解稱為最優(yōu)解。解稱為最優(yōu)解。運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 470. .maxxbAxtsxczT運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 48DDD運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 49n標(biāo)準(zhǔn)型有標(biāo)準(zhǔn)型有n n

26、個(gè)變量，個(gè)變量， m m 個(gè)約束行個(gè)約束行mnC 2. 2.基基n“基基”的概念：的概念： 設(shè)A是約束方程組mn維的系數(shù)矩陣，其秩為m，B是矩陣A中mm階非奇異子矩陣（B的行列式B0），則稱B是線性規(guī)劃問題的一個(gè)基基。 最多有最多有 個(gè)基個(gè)基運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 50max z=2x1 + 3x2 + 0 x3+0 x4 +0 x5 x1 + 2x2 + x3 =8 4x1 +x4 =16 4x2 +x5 =12 x1 5 0基有：基有：B1， B2 ，B3B4不是方程的基不是方程的基 1 0 0 0 1 0 0 0 1B1=系數(shù)矩陣: 1

27、 2 1 0 0 4 0 0 1 0 0 4 0 0 1A= 1 2 1 4 0 0 0 4 0B2= 1 2 0 4 0 1 0 4 0B3= 2 1 0 0 0 0 4 0 1B4=運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 51設(shè)B （P1，P2，Pm）稱Pj（j1,2, ，m）為基向量基向量。它們是一個(gè)線性無關(guān)的向量組，與基向量對(duì)應(yīng)的變量Xj（j1,2, ，m）稱為基變量基變量。其他變量就稱為非基變量。mmmmmmaaaaaaaaa212211121122基向量、基變量：基向量、基變量：運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Sl

28、ide 52約束方程可改寫為：約束方程可改寫為： X1 X2 Xm Xm1 Xn 用向量的形式表示為： 12111maaa22212maaammmmaaa21mbbb2111211mmmmaaamnnnaaa21nmjjjmjjjxabxa111-7運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 53對(duì)應(yīng)基變量為：對(duì)應(yīng)基變量為： x3， x4， x5非基變量為：非基變量為： x1， x2=（ ， ， ）系數(shù)矩陣: 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1A= 1 0 0 0 1 0 0 0 1B1= x1 + 2x2 + x3 =8 4x1 +x4

29、 =16 4x2 +x5 =12 x1 5 0運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 54復(fù)習(xí)復(fù)習(xí)n線性方程組如果有解線性方程組如果有解, ,那那么當(dāng)系數(shù)么當(dāng)系數(shù)矩陣矩陣A A的秩的秩r=n,r=n,有唯一解有唯一解, ,當(dāng)當(dāng)rn,rn,有無窮有無窮多組解多組解. .運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 553、基解、基可行解、可行基：、基解、基可行解、可行基：基解基解 對(duì)于有對(duì)于有n n個(gè)變量、個(gè)變量、m m個(gè)約束方程的標(biāo)準(zhǔn)型個(gè)約束方程的標(biāo)準(zhǔn)型線性規(guī)劃問題，取其線性規(guī)劃問題，取其m m個(gè)變量。若這些變量在個(gè)變量。若這些

30、變量在約束方程中的系數(shù)列向量線性無關(guān)，則它們約束方程中的系數(shù)列向量線性無關(guān)，則它們組成一組基變量。確定了一組基變量后，其組成一組基變量。確定了一組基變量后，其它它n-mn-m個(gè)變量稱為非基變量。個(gè)變量稱為非基變量。運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 56令方程組的基是令方程組的基是B B，設(shè)設(shè)X XB B是對(duì)應(yīng)于這個(gè)基的基變量，是對(duì)應(yīng)于這個(gè)基的基變量，X XB B= =（x1，x2，xm）T T, ,若令上式的若令上式的非基變量非基變量xm1xm2xn0 0，約束方程變成約束方程變成m m元一次方程：元一次方程：jx=BjBB0可以求出一個(gè)解：可以求出一

31、個(gè)解：X=X=（x1，x2，xm，0 0，0 0）T T稱稱X X為為基礎(chǔ)解基礎(chǔ)解。nmjjjmjjjxabxa11運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 57一個(gè)基解的非零分量個(gè)數(shù)不超過一個(gè)基解的非零分量個(gè)數(shù)不超過m m個(gè)。個(gè)?；尚薪饣尚薪獾姆橇惴至總€(gè)數(shù)的非零分量個(gè)數(shù) m m 時(shí)，稱為退化時(shí)，稱為退化解解若滿足若滿足非負(fù)非負(fù)約束條件的基解。約束條件的基解。稱為稱為基可行解基可行解。對(duì)應(yīng)于基可行解的基，稱為對(duì)應(yīng)于基可行解的基，稱為可行基可行基。當(dāng)基可行解為最優(yōu)解時(shí)當(dāng)基可行解為最優(yōu)解時(shí), ,對(duì)應(yīng)的基稱對(duì)應(yīng)的基稱最優(yōu)基最優(yōu)基。運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性

32、規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 70注意:基可行解的數(shù)目和基解的數(shù)目上限)!( !mnmnCmn運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 71是基可行解43210Q,Q,Q,Q,運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 725 , 4 , 3 , 2 , 1, 052222. .max52142132121jxxxxxxxxxxtsxxzj100110102100112A1000100011BTx)5 , 2 , 2 , 0 , 0(11010110022BTx)6 , 3 , 0 , 0 , 1(2運(yùn)籌學(xué)運(yùn)籌學(xué)

33、第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 731.凸集概念凸集概念： 設(shè)設(shè)K K是是n n2. 線性規(guī)劃問題的幾何意義線性規(guī)劃問題的幾何意義2.1 2.1 基本概念基本概念運(yùn)籌學(xué)運(yùn)籌學(xué) 第二章第二章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 74不是凸集的例子不是凸集的例子： 凸集的例子：凸集的例子：運(yùn)籌學(xué)運(yùn)籌學(xué) 第二章第二章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 75 （運(yùn)籌學(xué)運(yùn)籌學(xué) 第二章第二章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 76圖中的圖中的0，Q1,2,3,4都是頂點(diǎn)。都是頂點(diǎn)。運(yùn)籌學(xué)運(yùn)籌學(xué) 第二章第二章 線性規(guī)劃與單純形法線性規(guī)劃與

34、單純形法Slide 77n定理定理1 1 若線性規(guī)劃問題存在可行域若線性規(guī)劃問題存在可行域, ,則其可行域則其可行域 0,|1jnjjjxbxPXD2.2 2.2 基本定理基本定理是凸集是凸集證證: :設(shè)設(shè)D D中任意兩點(diǎn)中任意兩點(diǎn)X X(1)(1), X, X(2)(2)X X(1)(1)= (= (x(1)1， x(1) 2， x(1) 3， x(1) n ）T TX X(2)(2)= (= (x(2)1， x(2) 2， x(2) 3， x(2) n ）T T因此，因此，0,)1(1)1(jnjjjxbxP0,)2(1)2(jnjjjxbxP運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法

35、線性規(guī)劃與單純形法Slide 78令令X= X= X X的每個(gè)分量的每個(gè)分量)2()1()1 (jjjxxx)1 ()2()1(11jjnjnjjjjxxPxP)2(1)1(11)1 (jnjjjnjnjjjjxPxPxPbb)1 (=b滿足非負(fù)條件0, 0)2() 1 (jjxx0jx運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 79n引理引理1:1:線性規(guī)劃問題的可行解線性規(guī)劃問題的可行解 為基可行解的充要條件是為基可行解的充要條件是X X的正分量所對(duì)應(yīng)的系數(shù)的正分量所對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的。列向量是線性獨(dú)立的。證證（1 1）必要性）必要性 由基可行解的

36、定義可得。由基可行解的定義可得。（2 2）充分性）充分性 設(shè)設(shè)X X的正分量對(duì)應(yīng)的正分量對(duì)應(yīng) ， ， 線性無線性無關(guān)關(guān), , r(A)=m ,故故k m若若k =m， ， ， 構(gòu)成一個(gè)基構(gòu)成一個(gè)基即為可行基即為可行基TKxxxX)0, 0 ,(21TnxxxX),(21 若若k 00,21mkkxxx所以，所以，X為基可行解為基可行解運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 80n定理定理2 2線性規(guī)劃問題的基可行解線性規(guī)劃問題的基可行解X X對(duì)應(yīng)于可行域?qū)?yīng)于可行域D D的頂點(diǎn)。的頂點(diǎn)。n證明思路證明思路: :借助于引理借助于引理1,1,利用反證法完成利用反

37、證法完成, ,即先假設(shè)結(jié)論不成立即先假設(shè)結(jié)論不成立, ,由此推出矛盾由此推出矛盾, ,從而從而證明假設(shè)是錯(cuò)誤的證明假設(shè)是錯(cuò)誤的, ,于是結(jié)論成立于是結(jié)論成立運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 81證：證：設(shè)設(shè)X X的前的前m m個(gè)分量為正分量個(gè)分量為正分量（1 1）若）若X X不是基可行解，則不是基可行解，則X X一定不是一定不是D D的頂點(diǎn)的頂點(diǎn) X X不是基可行解，根據(jù)引理不是基可行解，根據(jù)引理1 1，則其正分量所，則其正分量所對(duì)應(yīng)的對(duì)應(yīng)的 ， ， 線性相關(guān)，即存在一組線性相關(guān)，即存在一組不全為零的數(shù)不全為零的數(shù) ，i =1，2 m使得：使得：022

38、11mmPPPbPxPxPxmmm)()()(222111njjjbxP1簡化為mjjjbxP11-81-9定理定理2 2證明過程證明過程bPxPxPxmmm)()()(222111用用 0 0的數(shù)乘的數(shù)乘1-91-9，再分別與，再分別與1-81-8相加和相減，得相加和相減，得運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 82取取: :即即X X是是X X(1)(1), , X X(2)(2)連線的中點(diǎn)連線的中點(diǎn). .TmxxxX),()1()1(2)1(1)1(由X X(1)(1), , X X(2)(2)可得可得X X不是不是D D的頂點(diǎn)，存在的頂點(diǎn)，存在X

39、X(1)(1)= =X X(2)(2)= =0 , 0),( ,),(),(2211mmxxx0 , 0),( ,),(),(2211mmxxx)2()1(2121XXX當(dāng)當(dāng)充分小時(shí)充分小時(shí), ,存在存在需證明需證明X X(1)(1), , X X(2)(2)的每個(gè)分量的每個(gè)分量000jjxX X不是頂點(diǎn)。不是頂點(diǎn)。DXX)2()1(,因此因此,（2 2）若）若X X不是不是D D的頂點(diǎn)，則的頂點(diǎn)，則X X一定不是基可行解一定不是基可行解DXX)2()1(,TmxxxX),()2()2(2)2(1)2()2()1(XX使使)2()1()1(XXX10運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形

40、法線性規(guī)劃與單純形法Slide 83由于不全為零不全為零假設(shè)假設(shè)X X是基可行解，其對(duì)應(yīng)的列向量是基可行解，其對(duì)應(yīng)的列向量 線性獨(dú)立線性獨(dú)立兩式相減得：兩式相減得：0)1(jxX X不是基可行解不是基可行解當(dāng)當(dāng)mj 時(shí)，有時(shí)，有0)2()1(jjjxxxDXX)2()1(,mjjjbxP1)1(mjjjbxP1)2(0)2(jxmjjjjxxP1)2()1(0)()2()1(XX)()2()1(jjxx向量組向量組 線性相關(guān)。與假設(shè)矛盾線性相關(guān)。與假設(shè)矛盾運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 84n引理：引理：若是有界凸集，則任一點(diǎn)若是有界凸集，則任一點(diǎn)可

41、表示為可表示為的頂點(diǎn)的凸組合的頂點(diǎn)的凸組合例例5 5：設(shè)是三角形中任意一點(diǎn)，設(shè)是三角形中任意一點(diǎn)， 是是三角形的三個(gè)頂點(diǎn)，試用三個(gè)頂點(diǎn)的坐標(biāo)表三角形的三個(gè)頂點(diǎn)，試用三個(gè)頂點(diǎn)的坐標(biāo)表示示X X。運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 85運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 86運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 87定理：若可行域有界，線性規(guī)劃問題的目標(biāo)函定理：若可行域有界，線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)達(dá)到最優(yōu)數(shù)一定可以在其可行域的頂點(diǎn)達(dá)到最優(yōu)證明思路證明思路：因

42、可行域非空有界，因此問題一：因可行域非空有界，因此問題一定有最優(yōu)解倘若在非頂點(diǎn)定有最優(yōu)解倘若在非頂點(diǎn)X X(0)(0)處目標(biāo)函數(shù)值取處目標(biāo)函數(shù)值取得最優(yōu)值，設(shè)法證明，必定能找到一個(gè)頂點(diǎn)得最優(yōu)值，設(shè)法證明，必定能找到一個(gè)頂點(diǎn)X X(m)(m)，使得在使得在X X(m)(m)點(diǎn)的目標(biāo)函數(shù)值也是最優(yōu)值點(diǎn)的目標(biāo)函數(shù)值也是最優(yōu)值運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 88證：證：設(shè)設(shè)X X(1) (1) ,X,X(2)(2), , XX(k)(k)是可行域是可行域 D D的頂點(diǎn)，若的頂點(diǎn)，若X X(0)(0)不是不是頂點(diǎn)，且目標(biāo)函數(shù)在頂點(diǎn)，且目標(biāo)函數(shù)在X X(0)(0

43、)處達(dá)到最優(yōu)處達(dá)到最優(yōu)Z Z* *=C=CX X(0)(0)因?yàn)橐驗(yàn)閄 X(0)(0)不是不是頂點(diǎn)，所以它可用頂點(diǎn)，所以它可用D D的頂點(diǎn)線性表示為：的頂點(diǎn)線性表示為：1-10因此因此只能有只能有: :1,0,1)(1)0(kiiiikiiXX)(1)(1)0(ikiiikiiCXXCCX在在X X(i)(i)中總存在一點(diǎn)中總存在一點(diǎn)X X(m)(m), ,使使CXCX(m)(m)是所有是所有CXCX(i)(i)中最大中最大. .把把X X(m)(m)代替代替1-101-10中的中的X X(i)(i), ,得得: :)()(1)(1)0(mmkiiikiiCXCXCXCX)()0(mCXCX目

44、標(biāo)函數(shù)在目標(biāo)函數(shù)在X X(0)(0)處達(dá)到最優(yōu)處達(dá)到最優(yōu). .)()0(mCXCX即目標(biāo)函數(shù)在頂點(diǎn)即目標(biāo)函數(shù)在頂點(diǎn)X X(m)(m)處也達(dá)到最優(yōu)處也達(dá)到最優(yōu). .運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 89定理：若線性規(guī)劃問題的目標(biāo)函數(shù)在（定理：若線性規(guī)劃問題的目標(biāo)函數(shù)在（）個(gè)點(diǎn)處達(dá)到最優(yōu)值，則在這些）個(gè)點(diǎn)處達(dá)到最優(yōu)值，則在這些頂點(diǎn)的凸組合上也達(dá)到最優(yōu)值頂點(diǎn)的凸組合上也達(dá)到最優(yōu)值證明思路：證明思路：根據(jù)凸組合的定義直接證得結(jié)論根據(jù)凸組合的定義直接證得結(jié)論運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 90有益的啟示：有益的啟示：n

45、在可行域中尋找線性規(guī)劃問題的最優(yōu)解可在可行域中尋找線性規(guī)劃問題的最優(yōu)解可以轉(zhuǎn)化為只在可行域的頂點(diǎn)中找，從而把以轉(zhuǎn)化為只在可行域的頂點(diǎn)中找，從而把一個(gè)無限的問題轉(zhuǎn)化為一個(gè)有限的問題一個(gè)無限的問題轉(zhuǎn)化為一個(gè)有限的問題n線性規(guī)劃問題若存在兩個(gè)或兩個(gè)以上的最線性規(guī)劃問題若存在兩個(gè)或兩個(gè)以上的最優(yōu)解，則一定有無窮多個(gè)最優(yōu)解優(yōu)解，則一定有無窮多個(gè)最優(yōu)解運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 91小結(jié)小結(jié):n如果一個(gè)線性規(guī)劃問題存在可行解，則一如果一個(gè)線性規(guī)劃問題存在可行解，則一定有基解。定有基解。n線性規(guī)劃的可行域是一個(gè)凸集或無界域線性規(guī)劃的可行域是一個(gè)凸集或無界域,

46、,都有有限個(gè)頂點(diǎn)都有有限個(gè)頂點(diǎn). .nLPLP問題的基可行解問題的基可行解, ,對(duì)應(yīng)于可行域的頂點(diǎn)對(duì)應(yīng)于可行域的頂點(diǎn)nLPLP問題若有最優(yōu)解問題若有最優(yōu)解, ,必定在某頂點(diǎn)得到必定在某頂點(diǎn)得到. .運(yùn)籌學(xué)運(yùn)籌學(xué) 第二章第二章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 92單純形法單純形法 要找到線性規(guī)劃問題的最優(yōu)解，只要要找到線性規(guī)劃問題的最優(yōu)解，只要在基本可行解中尋找就可以了。雖然基本可行在基本可行解中尋找就可以了。雖然基本可行解的數(shù)目是有限個(gè)（不超過解的數(shù)目是有限個(gè)（不超過C Cn nm m個(gè)），但當(dāng)個(gè)），但當(dāng)m,nm,n較大時(shí)，要用較大時(shí)，要用“窮舉法窮舉法”求出所有基本可行解求出

47、所有基本可行解也是行不通的。因此，必須尋求一種更有效的也是行不通的。因此，必須尋求一種更有效的方法。方法。運(yùn)籌學(xué)運(yùn)籌學(xué) 第二章第二章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 93主要有三個(gè)問題：一是尋找初始解，二是主要有三個(gè)問題：一是尋找初始解，二是判別最優(yōu)解，三是迭代。判別最優(yōu)解，三是迭代。 單純形法的單純形法的基本思路基本思路是：從線是：從線性規(guī)劃問題的一個(gè)基本可行解開始，轉(zhuǎn)性規(guī)劃問題的一個(gè)基本可行解開始，轉(zhuǎn)換到另一個(gè)使目標(biāo)函數(shù)值增大的基本可換到另一個(gè)使目標(biāo)函數(shù)值增大的基本可行解。反復(fù)迭代，直到目標(biāo)函數(shù)值達(dá)到行解。反復(fù)迭代，直到目標(biāo)函數(shù)值達(dá)到最大時(shí)，就得到了最優(yōu)解最大時(shí)，就得到了最

48、優(yōu)解。運(yùn)籌學(xué)運(yùn)籌學(xué) 第二章第二章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 94單純形法基本思路單純形法基本思路是否最優(yōu)解是否最優(yōu)解求最優(yōu)目標(biāo)函數(shù)值求最優(yōu)目標(biāo)函數(shù)值是是基變換基變換,迭代迭代否否確定初始可行解確定初始可行解運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 953.1舉例舉例A=max z=2x1 + 3x2 + 0 x3+0 x4 +0 x5 x1 + 2x2 + x3 =8 4x1 +x4 =16 4x2 +x5 =12 x1 ,x5 0（1-11）（1-12）（P1，P2，P3，P4， P5）（1-12）的系數(shù)矩陣:=1 2 1 0 04 0

49、 0 1 00 4 0 0 1運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 96B=（P3，P4， P5）=1 0 00 1 00 0 1基變量基變量x3 、x4、x5 ，非基變量非基變量x1、x2(1-12)變換得:x3 =8- x1 - 2x2x4 =16 -4x1 x5 =12- 4x2（1-13）把（1-13)代入目標(biāo)函數(shù)（1-11）得:Z=0+2x1+ 3x2（1-14） x1 + 2x2 + x3 =8 4x1 +x4 =16 4x2 +x5 =12運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 97令非基變量令非基變量x1

50、=x2=0，得得Z=0。得到一個(gè)基可行解：得到一個(gè)基可行解：分析（1-14）TX)12,16,8,0,0()0( x1、x2取正值，目標(biāo)函數(shù)會(huì)增大取正值，目標(biāo)函數(shù)會(huì)增大，必須把必須把x1、x2作作為基變量才能取到正值。當(dāng)非基變量的系數(shù)為為基變量才能取到正值。當(dāng)非基變量的系數(shù)為正值時(shí)，該非基變量應(yīng)該作為基變量來處理。正值時(shí)，該非基變量應(yīng)該作為基變量來處理。基向量的個(gè)數(shù)是一定的。因此，當(dāng)非基變量作基向量的個(gè)數(shù)是一定的。因此，當(dāng)非基變量作基變量后，那么，必須有一個(gè)基變量變成非基基變量后，那么，必須有一個(gè)基變量變成非基變量，這樣保證基變量的個(gè)數(shù)一定。變量，這樣保證基變量的個(gè)數(shù)一定。Z=0+2x1+ 3

51、x2本基可行解的經(jīng)濟(jì)含義是：工廠沒有安排生產(chǎn)產(chǎn)品本基可行解的經(jīng)濟(jì)含義是：工廠沒有安排生產(chǎn)產(chǎn)品、，資源都沒有被利用，所以工廠的利潤為，資源都沒有被利用，所以工廠的利潤為z z=0=0。運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 98確定換入變量：確定換入變量：選用目標(biāo)函數(shù)選用目標(biāo)函數(shù)中中所對(duì)應(yīng)的非基變量為換所對(duì)應(yīng)的非基變量為換入變量入變量。（。（x2為換入變量）為換入變量）確定換出變量：確定換出變量：x1=0LP標(biāo)準(zhǔn)型要求：標(biāo)準(zhǔn)型要求： x2 、x3 、x4、x5 0（1-13）變成下式（）變成下式（1-15）：）：x3 =8- 0 - 2x2 =8- 2x2 0

52、 x4 =16 4*0 =16 0 x5 =12- 4x2 0（1-15）每生產(chǎn)每生產(chǎn)II產(chǎn)品一件消耗產(chǎn)品一件消耗一組固定的資源（一組固定的資源（2，0，4）。）。 x2 =3時(shí)，時(shí)， x5首首先取零值，先取零值， x5應(yīng)作為非應(yīng)作為非基變量，基變量， x5作為換出變作為換出變量。量。要使（要使（1-151-15）成立，）成立， 只能選只能選擇擇x2 = =min(8/2,-,12/4).min(8/2,-,12/4).x3 =8- x1 - 2x2x4 =16 -4x1 x5 =12- 4x2Z=0+2x1+ 3x2運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide

53、99變換后，變換后，基變量基變量x3 、x4、x2 ，非基變量非基變量x1、x5n對(duì)約束方程組（對(duì)約束方程組（1-131-13）進(jìn)行變換，互換）進(jìn)行變換，互換x2、x5位置，位置，得：得：迭代：迭代：x3 + 2x2 =8- x1x4 =16 -4x1 4x2 =12- x5（1-16）（1-17）x3 = 2 - x1+ x5x4 =16 -4x1 x2 =3 - x52141把1-17代入目標(biāo)函數(shù)1-11得：43Z=9+2x1- x5（1-18）令非基變量令非基變量x1=x5=0，得得Z=9。得到一個(gè)得到一個(gè)基可行解：基可行解：TX)0,16,2,3,0()1(x3 =8- x1 - 2x

54、2x4 =16 -4x1 x5 =12- 4x2max z=2x1 + 3x2 + 0 x3+0 x4 +0 x5運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 100（1-18）中系數(shù)為正，目標(biāo)函數(shù)還可以增大）中系數(shù)為正，目標(biāo)函數(shù)還可以增大 用上述方法，確定換入變量為x1，換出變量為x3 。迭代后，可得另一個(gè)基可行解：基可行解：TX)0,8,0,3,2()2(41Z=13-2x3+ x5再用上述方法，確定換入變量為x5換出變量為x4 。迭代后，可得另一個(gè)基可行解：基可行解：TX)4,0,0,2,4()3(目標(biāo)函數(shù)表達(dá)式為：目標(biāo)函數(shù)表達(dá)式為：Z=14-1.5x3-

55、0.125 x4Z=13Z=14（1-19）目標(biāo)函數(shù)中非目標(biāo)函數(shù)中非基變量的系數(shù)都是負(fù)數(shù)?；兞康南禂?shù)都是負(fù)數(shù)。運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 101可行域可行域目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線最優(yōu)解最優(yōu)解840 x1x23423Q3（2，3）Q4（0，3）Q2（4，2）Q1（4，0） 例例1 1的線性規(guī)劃問題是二維的，的線性規(guī)劃問題是二維的，即有兩個(gè)變量即有兩個(gè)變量x1,x2。當(dāng)加入松當(dāng)加入松弛變量弛變量x3,x4,x5后，變換為高維后，變換為高維的。這時(shí)可以想象，滿足所有約的。這時(shí)可以想象，滿足所有約束條件的可行域是高維空間中的束條件的可行域是高維空

56、間中的凸多面體凸多面體( (凸集凸集) )。該凸多面體上。該凸多面體上的頂點(diǎn)，就是基可行解。初始基的頂點(diǎn)，就是基可行解。初始基可行解為可行解為 X X(0)(0)=(0,0,8,16,12)=(0,0,8,16,12)T T，對(duì)應(yīng)于圖中的原點(diǎn)，對(duì)應(yīng)于圖中的原點(diǎn)(0(0，0)0)；X X(1)(1)=(0,3,2,16,0)=(0,3,2,16,0)T T對(duì)應(yīng)于圖中對(duì)應(yīng)于圖中的的Q Q4 4點(diǎn)點(diǎn)(0(0，3)3)； X X(2)(2)=(2,3,0,8,0)=(2,3,0,8,0)T T對(duì)應(yīng)于對(duì)應(yīng)于Q Q3 3點(diǎn)點(diǎn)(2,3)(2,3)； 最優(yōu)解最優(yōu)解X X(3)(3)=(4,2,0,0,4)=(

57、4,2,0,0,4)T T相當(dāng)于相當(dāng)于圖中的圖中的 Q Q2 2點(diǎn)點(diǎn)(4,2)(4,2)。運(yùn)籌學(xué)運(yùn)籌學(xué) 第二章第二章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 1023.2初始基可行解的確定n直接觀察法直接觀察法n形式，加松弛變量形式，加松弛變量n形式形式, ,減剩余變量后加人工變量（具體減剩余變量后加人工變量（具體求解要用大法或二階段法）求解要用大法或二階段法）n目的目的: :使初始可行基為單位陣使初始可行基為單位陣, ,令非基變量令非基變量等于零等于零, ,因?yàn)橐驗(yàn)閎0,b0,即可以得到初始基可行即可以得到初始基可行解解. .運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單

58、純形法Slide 1033.2初始基可行解的確定n標(biāo)準(zhǔn)化后直接找到單位陣：標(biāo)準(zhǔn)化后直接找到單位陣：x1 +a1,m+1xm+1+a1nxn=b1 x2 +a2,m+1xm+1+a2nxn=b2 xm+am,m+1xm+1+amnxn=bm xj 0,j=1,2,n顯然得到一個(gè)顯然得到一個(gè)m mm m單位矩陣：單位矩陣：（1-22）B=（P1，P2， Pm）=1 0 00 1 00 0 1 運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 1043.2初始基可行解的確定以以B B作為可行基，將（作為可行基，將（1-221-22）式移項(xiàng)得：）式移項(xiàng)得：x1 =b1 -a1

59、,m+1xm+1-a1nxn x2 =b2 -a2,m+1xm+1-a2nxn xm=bm -am,m+1xm+1-amnxn令： xm+1 = xm+2 =xn=0, ,由（由（1-231-23）得：）得：（1-23）xi = bi (i=1,2,m)又因?yàn)橛忠驗(yàn)?b bi i 0 0 ，所以得到一個(gè)初始基可行解所以得到一個(gè)初始基可行解：X=X=（ x1 ， x2 ， xm ，0 0，0 0）T T= =（ b1 ， b2 ， bm ，0 0，0 0）T Tn-mn-m運(yùn)籌學(xué)運(yùn)籌學(xué) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Slide 105 標(biāo)準(zhǔn)化后找不到單位陣，采用人造基給方程標(biāo)

60、準(zhǔn)化后找不到單位陣，采用人造基給方程加入人工變量加入人工變量maxZ= 3x1 - x2 -x3x1 -2 x2 +x3 11 -4 x1 +x2 +2x3 3 2x1 -x3= -1x1 ， x2， x3 0 x1 -2 x2 +x3 +x4 =11 -4 x1 +x2 +2x3 x5 = 3 -2x1 +x3 = 1 x1 -2 x2 + x3 +x4 =11 -4 x1 + x2 +2x3 x5 +x6 = 3 -2x1 +x3 +x7 = 1A= 1 -2 1 1 0-4 1 2 0 -1 2 0 1 0 0 1 -2 1 1 0 0 0-4 1 2 0 -1 1 0 2 0 1 0