第二章線性規(guī)劃的標(biāo)準(zhǔn)型與單純形法演示文稿

第二章線性規(guī)劃的標(biāo)準(zhǔn)型與單純形法演示文稿現(xiàn)在是1頁(yè)\一共有120頁(yè)\編輯于星期一優(yōu)選第二章線性規(guī)劃的標(biāo)準(zhǔn)型與單純形法現(xiàn)在是2頁(yè)\一共有120頁(yè)\編輯于星期一運(yùn)籌學(xué)的由來(lái)與發(fā)展運(yùn)籌學(xué)的性質(zhì)與特點(diǎn)

運(yùn)籌學(xué)的主要內(nèi)容運(yùn)籌學(xué)的發(fā)展趨勢(shì)運(yùn)籌學(xué)的學(xué)科地位運(yùn)籌學(xué)概況現(xiàn)在是3頁(yè)\一共有120頁(yè)\編輯于星期一名稱的由來(lái)

OperationResearch

運(yùn)籌帷幄“史記”運(yùn)作研究發(fā)展歷程

運(yùn)籌學(xué)的由來(lái)與發(fā)展二戰(zhàn)以前萌芽二戰(zhàn)期間產(chǎn)生五六十年代發(fā)展七八十年代成熟現(xiàn)在是4頁(yè)\一共有120頁(yè)\編輯于星期一引入數(shù)學(xué)方法解決實(shí)際問(wèn)題

--定性與定量方法結(jié)合系統(tǒng)與整體性

--從全局考察問(wèn)題應(yīng)用性

--源于實(shí)踐、為了實(shí)踐、服務(wù)于實(shí)踐交叉學(xué)科

--涉及經(jīng)濟(jì)、管理、數(shù)學(xué)、工程和系統(tǒng)等多學(xué)科開(kāi)放性

--不斷產(chǎn)生新的問(wèn)題和學(xué)科分支多分支

--問(wèn)題的復(fù)雜和多樣性運(yùn)籌學(xué)的性質(zhì)與特點(diǎn)現(xiàn)在是5頁(yè)\一共有120頁(yè)\編輯于星期一線性規(guī)劃數(shù)學(xué)規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃動(dòng)態(tài)規(guī)劃學(xué)科內(nèi)容多目標(biāo)規(guī)劃雙層規(guī)劃組合優(yōu)化最優(yōu)計(jì)數(shù)問(wèn)題網(wǎng)絡(luò)優(yōu)化排序問(wèn)題統(tǒng)籌圖隨機(jī)優(yōu)化對(duì)策論排隊(duì)論庫(kù)存論決策分析可靠性分析運(yùn)籌學(xué)的主要內(nèi)容現(xiàn)在是6頁(yè)\一共有120頁(yè)\編輯于星期一成熟的學(xué)科分支向縱深發(fā)展新的研究領(lǐng)域產(chǎn)生與新的技術(shù)結(jié)合與其他學(xué)科的結(jié)合加強(qiáng)傳統(tǒng)優(yōu)化觀念不斷變化運(yùn)籌學(xué)的發(fā)展趨勢(shì)現(xiàn)在是7頁(yè)\一共有120頁(yè)\編輯于星期一1在數(shù)學(xué)學(xué)科中的地位運(yùn)籌數(shù)學(xué)1在系統(tǒng)科學(xué)中的地位系統(tǒng)工程1在管理科學(xué)中的地位管理與運(yùn)籌學(xué)1與經(jīng)濟(jì)學(xué)的關(guān)系問(wèn)題與方法1與工程科學(xué)的關(guān)系方法與應(yīng)用1與計(jì)算機(jī)科學(xué)的關(guān)系核心算法與工具基礎(chǔ)理論應(yīng)用理論應(yīng)用技術(shù)運(yùn)籌學(xué)運(yùn)籌學(xué)的學(xué)科地位現(xiàn)在是8頁(yè)\一共有120頁(yè)\編輯于星期一教學(xué)計(jì)劃

數(shù)學(xué)規(guī)劃以線性規(guī)劃和整數(shù)規(guī)劃及動(dòng)態(tài)規(guī)劃為講授重點(diǎn)，組合優(yōu)化部分主要講圖與網(wǎng)絡(luò)優(yōu)化，而隨機(jī)優(yōu)化講授排隊(duì)論部分作為選講內(nèi)容。教學(xué)方法

以授課為主，講課中主要培養(yǎng)用最優(yōu)化方法解決實(shí)際問(wèn)題的能力。教學(xué)計(jì)劃與方法現(xiàn)在是9頁(yè)\一共有120頁(yè)\編輯于星期一考核內(nèi)容及方式

理論方法—期末考試60%理論方法—期中考試20%平時(shí)成績(jī)20%考試與要求現(xiàn)在是10頁(yè)\一共有120頁(yè)\編輯于星期一韓伯棠，管理運(yùn)籌學(xué)，

高等教育出版社，北京，2000年徐光輝等，運(yùn)籌學(xué)手冊(cè)，

科學(xué)出版社，北京，1999年胡運(yùn)權(quán)等，運(yùn)籌學(xué)教程，

清華出版社，北京，1998年劉家壯，王建方，網(wǎng)絡(luò)最優(yōu)化，

華中工學(xué)院出版社，武漢，1987年管梅谷，鄭漢鼎，線性規(guī)劃，

山東科學(xué)技術(shù)出版社，濟(jì)南，1983年參考資料現(xiàn)在是11頁(yè)\一共有120頁(yè)\編輯于星期一運(yùn)籌學(xué)OperationsResearchChapter2線性規(guī)劃LinearProgramming2.1LP的數(shù)學(xué)模型

MathematicalModelofLP2.2圖解法

GraphicalMethod2.3標(biāo)準(zhǔn)型

StandardformofLP2.4基本概念

BasicConcepts2.5單純形法

SimplexMethod現(xiàn)在是12頁(yè)\一共有120頁(yè)\編輯于星期一2.1數(shù)學(xué)模型

MathematicalModel現(xiàn)在是13頁(yè)\一共有120頁(yè)\編輯于星期一問(wèn)題的提出：

在生產(chǎn)管理的經(jīng)營(yíng)活動(dòng)中，通常需要對(duì)“有限的資源”尋求“最佳”的利用或分配方式。有限資源：勞動(dòng)力、原材料、設(shè)備或資金等最佳：有一個(gè)標(biāo)準(zhǔn)或目標(biāo)，使利潤(rùn)達(dá)到最大或成本達(dá)到最小。有限資源的合理配置有兩類問(wèn)題：如何合理的使用有限的資源，使生產(chǎn)經(jīng)營(yíng)的效益達(dá)到最大；在生產(chǎn)或經(jīng)營(yíng)的任務(wù)確定的條件下，合理的組織生產(chǎn)，安排經(jīng)營(yíng)活動(dòng)，使所消耗的資源數(shù)最少?，F(xiàn)在是14頁(yè)\一共有120頁(yè)\編輯于星期一

與規(guī)劃問(wèn)題有關(guān)的數(shù)學(xué)模型總有兩部分組成：約束條件：反映了有限資源對(duì)生產(chǎn)經(jīng)營(yíng)活動(dòng)的種種約束，或者生產(chǎn)經(jīng)營(yíng)必須完成的任務(wù)；目標(biāo)函數(shù)：反映生產(chǎn)經(jīng)營(yíng)者在有限資源條件下希望達(dá)到的生產(chǎn)或經(jīng)營(yíng)的目標(biāo)。現(xiàn)在是15頁(yè)\一共有120頁(yè)\編輯于星期一例１某制藥廠生產(chǎn)甲、乙兩種藥品，生產(chǎn)這兩種藥品要消耗某種維生素。生產(chǎn)每噸藥品所需要的維生素量，所占用的設(shè)備時(shí)間，以及該廠每周可提供的資源總量如下表所示：每噸產(chǎn)品的消耗每周資源總量甲乙維生素（公斤）3020160設(shè)備（臺(tái)班）5115

已知該廠生產(chǎn)每噸甲、乙藥品的利潤(rùn)分別為5萬(wàn)元和2萬(wàn)元。但根據(jù)市場(chǎng)需求調(diào)查的結(jié)果，甲藥品每周的產(chǎn)量不應(yīng)超過(guò)4噸。問(wèn)該廠應(yīng)如何安排兩種藥品的產(chǎn)量才能使每周獲得的利潤(rùn)最大？現(xiàn)在是16頁(yè)\一共有120頁(yè)\編輯于星期一

定義x1為生產(chǎn)甲種藥品的計(jì)劃產(chǎn)量數(shù)，x2為生產(chǎn)乙種藥品的計(jì)劃產(chǎn)量數(shù)。目標(biāo)：使總利潤(rùn)Z=5x1+2x2

極大化約束：每周資源總量的限制，30x1+20x2≤160

5x1+x2≤15甲種藥品每周產(chǎn)量不應(yīng)超過(guò)4噸的限制

x1≤4計(jì)劃生產(chǎn)數(shù)不可能是負(fù)數(shù)，x1≥0x2≥0每噸產(chǎn)品的消耗每周資源總量甲乙維生素（公斤）3020160設(shè)備（臺(tái)班）5115單位利潤(rùn)（萬(wàn)元）5２現(xiàn)在是17頁(yè)\一共有120頁(yè)\編輯于星期一數(shù)學(xué)模型為

s.t.

（subjectto)(suchthat)這是一個(gè)如何合理的使用有限的資源，使生產(chǎn)經(jīng)營(yíng)的效益達(dá)到最大的數(shù)學(xué)規(guī)劃問(wèn)題。在滿足一組約束條件的限制下，尋求決策變量x1，x2的決策值，使目標(biāo)函數(shù)達(dá)到最大值。每噸產(chǎn)品的消耗每周資源總量甲乙維生素（公斤）3020160設(shè)備（臺(tái)班）5115單位利潤(rùn)（萬(wàn)元）5２現(xiàn)在是18頁(yè)\一共有120頁(yè)\編輯于星期一例２某化工廠根據(jù)一項(xiàng)合同要求為用戶生產(chǎn)一種用甲、乙兩種原料混合配制而成的特種產(chǎn)品。已知甲、乙兩種原料都含有A、B、C三種化學(xué)成分，兩種原料分別所含三種化學(xué)成分的百分比含量，以及按合同規(guī)定的產(chǎn)品中三種化學(xué)成分的最低含量如下表所示：已知甲、乙兩種原料的成本分別是每公斤3元和2元，廠方希望總成本達(dá)到最小，問(wèn)如何配置該產(chǎn)品？原料化學(xué)成分含量（%）產(chǎn)品中化學(xué)成分的最低含量（%）甲乙A1234B232C3155化學(xué)成分現(xiàn)在是19頁(yè)\一共有120頁(yè)\編輯于星期一定義x1，x2分別為每公斤產(chǎn)品中甲，乙兩種原料的數(shù)量，目標(biāo)：使總成本Z=3x1+2x2

極小化約束：配料平衡條件，x1+x2=1產(chǎn)品中A、B、C三種化學(xué)成分的最低含量

12x1+3x2≥4

2x1+3x2≥2

3x1+15x2≥5非負(fù)性條件x1≥0,x2≥0原料化學(xué)成分含量（%）產(chǎn)品中化學(xué)成分的最低含量（%）甲乙A1234B232C3155單位成本（元）３２化學(xué)成分現(xiàn)在是20頁(yè)\一共有120頁(yè)\編輯于星期一數(shù)學(xué)模型：

s.t.

這是一個(gè)原料配制問(wèn)題，是在生產(chǎn)任務(wù)確定的條件下，合理的組織生產(chǎn)，使所消耗的資源數(shù)最少的數(shù)學(xué)規(guī)劃問(wèn)題。滿足一組約束條件的同時(shí)，尋求變量x1和x2的值使目標(biāo)函數(shù)取得最小值。原料化學(xué)成分含量（%）產(chǎn)品中化學(xué)成分的最低含量（%）甲乙A1234B232C3155單位成本（元）３２化學(xué)成分現(xiàn)在是21頁(yè)\一共有120頁(yè)\編輯于星期一1．解決問(wèn)題的目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù)，通常是求最大值或最小值；2．解決問(wèn)題的約束條件是一組多個(gè)決策變量的線性不等式或等式。線性規(guī)劃數(shù)學(xué)模型的特征：線性規(guī)劃數(shù)學(xué)模型的三要素：決策變量(Decisionvariables);

目標(biāo)函數(shù)(Objectivefunction);約束條件(Constraints);建立一個(gè)問(wèn)題的線性規(guī)劃模型的一般步驟：確定決策變量；(2)確定目標(biāo)函數(shù)；(3)確定約束條件；(4)確定變量是否有非負(fù)約束。2.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP現(xiàn)在是22頁(yè)\一共有120頁(yè)\編輯于星期一2.1.2線性規(guī)劃的一般模型一般地，假設(shè)線性規(guī)劃數(shù)學(xué)模型中,有m個(gè)約束,有n個(gè)決策變量xj(j=1,2…,n)，目標(biāo)函數(shù)的變量系數(shù)用cj表示,

cj稱為價(jià)值系數(shù)。約束條件的變量系數(shù)用aij表示，aij稱為工藝系數(shù)。約束條件右端的常數(shù)用bi表示，bi稱為資源限量。則線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式可寫成2.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP現(xiàn)在是23頁(yè)\一共有120頁(yè)\編輯于星期一在實(shí)際中一般xj≥0,但有時(shí)xj≤0或xj無(wú)符號(hào)限制。為了書寫方便，上式也可寫成：

2.1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP現(xiàn)在是24頁(yè)\一共有120頁(yè)\編輯于星期一2.2圖解法

GraphicalMethod現(xiàn)在是25頁(yè)\一共有120頁(yè)\編輯于星期一圖解法的步驟：1.在直角坐標(biāo)系中畫出可行解集：分別畫出滿足每個(gè)約束包括變量非負(fù)要求的區(qū)域，其交集就是可行解集，或稱可行域；；2.繪制目標(biāo)函數(shù)圖形：先過(guò)原點(diǎn)作一條矢量指向點(diǎn)(c1,c2)，矢量的方向就是目標(biāo)函數(shù)值增加的方向，稱為梯度方向，再作一條與矢量垂直的直線，這條直線就是目標(biāo)函數(shù)圖形；3.求最優(yōu)解：依據(jù)目標(biāo)函數(shù)求最大或最小移動(dòng)目標(biāo)函數(shù)直線，直線與可行域相交的點(diǎn)對(duì)應(yīng)的坐標(biāo)就是最優(yōu)解。一般地，先將目標(biāo)函數(shù)直線放在可行域中：若要求最大值，則將目標(biāo)函數(shù)直線沿著矢量方向移動(dòng)；若要求最小值，則將目標(biāo)函數(shù)直線沿著矢量的反方向移動(dòng)。2.2圖解法TheGraphicalMethod現(xiàn)在是26頁(yè)\一共有120頁(yè)\編輯于星期一x1x2O1020304010203040(3,4)(15,10)最優(yōu)解X=(15,10)最優(yōu)值Z=85例1.42.2圖解法TheGraphicalMethod現(xiàn)在是27頁(yè)\一共有120頁(yè)\編輯于星期一246x1x2246最優(yōu)解X=(3,1)最優(yōu)值Z=5(3,1)minZ=x1+2x2例2.5(1,2)2.2圖解法TheGraphicalMethod現(xiàn)在是28頁(yè)\一共有120頁(yè)\編輯于星期一246x1x2246X（2）＝（3,1）X（1）＝（1,3）(5,5)minZ=5x1+5x2例2.6有無(wú)窮多個(gè)最優(yōu)解即具有多重解,通解為

0≤α≤1

當(dāng)α=0.5時(shí)Ｘ=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)2.2圖解法TheGraphicalMethod現(xiàn)在是29頁(yè)\一共有120頁(yè)\編輯于星期一246x1x2246(1,2)無(wú)界解(無(wú)最優(yōu)解)maxZ=x1+2x2例1.72.2圖解法TheGraphicalMethod現(xiàn)在是30頁(yè)\一共有120頁(yè)\編輯于星期一x1x2O10203040102030405050無(wú)可行解，從而無(wú)最優(yōu)解。maxZ=10x1+x2例2.82.2圖解法TheGraphicalMethod現(xiàn)在是31頁(yè)\一共有120頁(yè)\編輯于星期一由以上例題可知，線性規(guī)劃的解有4種形式：

1.有惟一最優(yōu)解(例1.4、例1.5)2.有多重解(例1.6)3.有無(wú)界解(例1.7)4.無(wú)可行解(例1.8)1、2情形為有最優(yōu)解3、4情形為無(wú)最優(yōu)解2.2圖解法TheGraphicalMethod現(xiàn)在是32頁(yè)\一共有120頁(yè)\編輯于星期一4.通過(guò)圖解法了解線性規(guī)劃有幾種解的形式；5.作圖的關(guān)鍵有三點(diǎn)：

(1)可行解區(qū)域要畫正確；

(2)目標(biāo)函數(shù)增加的方向不能畫錯(cuò)；

(3)目標(biāo)函數(shù)的直線怎樣平行移動(dòng)。下一節(jié)：線性規(guī)劃的標(biāo)準(zhǔn)型2.2圖解法TheGraphicalMethod1.什么是線性規(guī)劃，掌握線性規(guī)劃在管理中的幾個(gè)應(yīng)用例子；2.線性規(guī)劃數(shù)學(xué)模型的組成及其特征；3.線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式。現(xiàn)在是33頁(yè)\一共有120頁(yè)\編輯于星期一2.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP現(xiàn)在是34頁(yè)\一共有120頁(yè)\編輯于星期一在用單純法求解線性規(guī)劃問(wèn)題時(shí)，為了討論問(wèn)題方便，需將線性規(guī)劃模型化為統(tǒng)一的標(biāo)準(zhǔn)形式。2.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型為:1．目標(biāo)函數(shù)求最大值（或求最小值）2．約束條件都為等式方程3．變量xj非負(fù)4．常數(shù)bi非負(fù)現(xiàn)在是35頁(yè)\一共有120頁(yè)\編輯于星期一max(或min)Z=c1x1+c2x2+…+cnxn2.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP注：本教材默認(rèn)標(biāo)準(zhǔn)型中目標(biāo)函數(shù)是

max現(xiàn)在是36頁(yè)\一共有120頁(yè)\編輯于星期一或?qū)懗上铝行问剑?/p>

或用矩陣形式2.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP現(xiàn)在是37頁(yè)\一共有120頁(yè)\編輯于星期一通常X記為：

,稱Ａ為約束方程的系數(shù)矩陣，m是約束方程的個(gè)數(shù)，n是決策變量的個(gè)數(shù)，一般情況m≤n，且r(Ａ)＝m。其中:2.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP現(xiàn)在是38頁(yè)\一共有120頁(yè)\編輯于星期一一般形式線性規(guī)劃模型的標(biāo)準(zhǔn)化準(zhǔn)則:（前提bi

≥0

）5.xj≤0令xj

=－x'j,x'j≥0

現(xiàn)在是39頁(yè)\一共有120頁(yè)\編輯于星期一【例1】將下列線性規(guī)劃化為標(biāo)準(zhǔn)型

【分析】(１)因?yàn)閤3無(wú)符號(hào)要求，即x3可取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以令2.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP現(xiàn)在是40頁(yè)\一共有120頁(yè)\編輯于星期一

(3)第二個(gè)約束條件是“≥”號(hào)，在“≥”號(hào)左端減去剩余變量(surplusvariable)x5，x5≥0，也稱松馳變量；2.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP(2)第一個(gè)約束條件是“≤”號(hào)，在“≤”號(hào)左端加入松馳變量

(slackvariable)x4，x4≥0,化為等式；(4)第三個(gè)約束條件是“≤”號(hào)且常數(shù)項(xiàng)為負(fù)數(shù)，因此在“≤”左邊加入松馳變量x6，x6≥0，同時(shí)兩邊乘以－1。

(5)目標(biāo)函數(shù)是最小值，為了化為求最大值，令Z′=－Z,得到maxZ′=－Z，即當(dāng)Z達(dá)到最小值時(shí)Z′達(dá)到最大值?，F(xiàn)在是41頁(yè)\一共有120頁(yè)\編輯于星期一綜合起來(lái)得到下列標(biāo)準(zhǔn)型2.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP現(xiàn)在是42頁(yè)\一共有120頁(yè)\編輯于星期一當(dāng)某個(gè)約束是絕對(duì)值不等式時(shí)，將絕對(duì)值不等式化為兩個(gè)不等式，再化為等式，例如約束將其化為兩個(gè)不等式

再加入松馳變量化為等式。

2.3線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP現(xiàn)在是43頁(yè)\一共有120頁(yè)\編輯于星期一2.4線性規(guī)劃的有關(guān)概念BasicConceptsofLP現(xiàn)在是44頁(yè)\一共有120頁(yè)\編輯于星期一

設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型

maxZ=CX(2.1)AX=b(2.2)X≥0(2.3)式中A是m×n矩陣，m≤n并且r(A)=m，顯然A中至少有一個(gè)m×m子矩陣B，使得r(B)=m。2.4基本概念BasicConcepts

基

(basis)：A中m×m子矩陣B并且有r(B)=m，則稱B是線性規(guī)劃的一個(gè)基(或基矩陣basismatrix)。注：基矩陣B必為非奇異矩陣即|B|≠0。當(dāng)m=n時(shí)，基矩陣惟一，當(dāng)m<n時(shí)，基矩陣就可能有多個(gè)，但數(shù)目不超過(guò)現(xiàn)在是45頁(yè)\一共有120頁(yè)\編輯于星期一【例2】線性規(guī)劃

求所有基矩陣。

【解】約束方程的系數(shù)矩陣為2×5矩陣

2.4基本概念BasicConcepts

現(xiàn)在是46頁(yè)\一共有120頁(yè)\編輯于星期一容易看出r(A)=2，2階子矩陣有C52=10個(gè)，其中第1列與第3列構(gòu)成的2階矩陣不是一個(gè)基，基矩陣只有9個(gè)，即現(xiàn)在是47頁(yè)\一共有120頁(yè)\編輯于星期一當(dāng)確定某一矩陣為基矩陣時(shí)，則基矩陣對(duì)應(yīng)的列向量稱為基向量(basicvector)，其余列向量稱為非基向量;

基向量對(duì)應(yīng)的變量稱為基變量(basicvariable)，非基向量對(duì)應(yīng)的變量稱為非基變量；在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基變量，x2、x3、x5是非基變量。基變量、非基變量是針對(duì)某一確定基而言的，不同的基對(duì)應(yīng)的基變量和非基變量也不同。2.4基本概念BasicConcepts

現(xiàn)在是48頁(yè)\一共有120頁(yè)\編輯于星期一

可行解(feasiblesolution):

滿足式(2.2)及(2.3)的解X=（x1,x2…,xn)T稱為可行解；基本可行解(basic

feasiblesolution):若基本解是可行解則稱為是基本可行解（也稱基可行解）?；窘?basicsolution):對(duì)某一確定的基B，令非基變量等于零，利用式(2.2)解出基變量，則這組解稱為基Ｂ的基本解。最優(yōu)解(optimalsolution):滿足式(1.1)的可行解稱為最優(yōu)解，即使得目標(biāo)函數(shù)達(dá)到最大值的可行解就是最優(yōu)解；非可行解(infeasiblesolution)

無(wú)界解

(unboundedsolution)2.4基本概念BasicConcepts

現(xiàn)在是49頁(yè)\一共有120頁(yè)\編輯于星期一顯然，只要基本解中的基變量的解滿足式(2.3)的非負(fù)要求，那么這個(gè)基本解就是基本可行解。

在上例中，對(duì)Ｂ１來(lái)說(shuō)，x1,x2是基變量，x3,x4，x5是非基變量，令x3=x4=x5=0，則式(2.2)為

因|B1|≠０，由克萊姆法則知，x1、x2有惟一解x1＝2/5,x2=1,從而基本解為2.4基本概念BasicConcepts

現(xiàn)在是50頁(yè)\一共有120頁(yè)\編輯于星期一對(duì)B2來(lái)說(shuō)，x1,x4,為基變量，令非變量x2,x3,x5為零，由式(2.2)得

，x4=4，則基本解為反之，可行解不一定是基本可行解，如滿足式(2.2)~(2.3)，但不是任何基矩陣的基本解。在中x1<0,不是可行解，因此也不是基本可行解。

現(xiàn)在是51頁(yè)\一共有120頁(yè)\編輯于星期一可行基:

基可行解對(duì)應(yīng)的基稱為可行基；最優(yōu)基:基本最優(yōu)解對(duì)應(yīng)的基稱為最優(yōu)基；如上述B3就是最優(yōu)基，最優(yōu)基肯定是可行基。2.4基本概念BasicConcepts

基本最優(yōu)解:

最優(yōu)解是基本解稱為基本最優(yōu)解。例如滿足式(2.1)~(2.3)是最優(yōu)解,又是B3的基本解,因此它是基本最優(yōu)解。注：當(dāng)最優(yōu)解惟一時(shí)，最優(yōu)解亦是基本最優(yōu)解，當(dāng)最優(yōu)解不惟一時(shí)，則最優(yōu)解不一定是基本最優(yōu)解?，F(xiàn)在是52頁(yè)\一共有120頁(yè)\編輯于星期一基本最優(yōu)解、最優(yōu)解、基本可行解、基本解、可行解的關(guān)系:基本最優(yōu)解基本可行解可行解最優(yōu)解基本解2.4基本概念BasicConcepts

現(xiàn)在是53頁(yè)\一共有120頁(yè)\編輯于星期一凸集(Convexset):設(shè)K是n維空間Rn的一個(gè)點(diǎn)集，對(duì)任意兩點(diǎn)

時(shí)，則稱K為凸集。

就是以X(1)、X(2)為端點(diǎn)的線段方程,點(diǎn)X的位置由α的值確定,當(dāng)α=0時(shí),X=X(2),當(dāng)α=1時(shí)X=X(1)。凸組合(Convexcombination)

:設(shè)是Rn中的點(diǎn)，若存在使得成立，稱X為的凸組合。2.4基本概念BasicConcepts

現(xiàn)在是54頁(yè)\一共有120頁(yè)\編輯于星期一極點(diǎn)(Extremepoint)::

設(shè)K是凸集，，若X不能用K中兩個(gè)不同的點(diǎn)的凸組合表示為<)10()1()2()1(<-+=aaaXXX則稱X是K的一個(gè)極點(diǎn)或頂點(diǎn)。X是凸集K的極點(diǎn)，即X不可能是K中某一線段的內(nèi)點(diǎn)，只能是K中某一線段的端點(diǎn)。O2.4基本概念BasicConcepts

現(xiàn)在是55頁(yè)\一共有120頁(yè)\編輯于星期一【定理2.1】若線性規(guī)劃可行解集K非空,則K是凸集。

【定理2.2】線性規(guī)劃的可行解集合K的點(diǎn)X是極點(diǎn)的充要條件為X

是基本可行解。【定理2.3】若線性規(guī)劃有最優(yōu)解,則最優(yōu)值一定可以在可行解集合的某個(gè)極點(diǎn)上達(dá)到,最優(yōu)解就是極點(diǎn)的坐標(biāo)向量。注：定理2.2刻劃了可行解集的極點(diǎn)與基本可行解的對(duì)應(yīng)關(guān)系，極點(diǎn)是基本可行解，反之，基本可行解一定是極點(diǎn)，但它們并非一一對(duì)應(yīng)，有可能兩個(gè)或幾個(gè)基本可行解對(duì)應(yīng)于同一極點(diǎn)(退化基本可行解時(shí))。線性規(guī)劃的基本定理2.4基本概念BasicConcepts

現(xiàn)在是56頁(yè)\一共有120頁(yè)\編輯于星期一

定理2.3描述了最優(yōu)解在可行解集中的位置，它也表明若線性規(guī)劃問(wèn)題有最優(yōu)解，則必有基本最優(yōu)解，且若最優(yōu)解惟一，則最優(yōu)解只能在某一極點(diǎn)上達(dá)到；若具有多重最優(yōu)解，則最優(yōu)解是某些極點(diǎn)的凸組合，從而最優(yōu)解是可行解集的極點(diǎn)或界點(diǎn)，不可能是可行解集的內(nèi)點(diǎn)。

若線性規(guī)劃的可行解集非空且有界，則一定有最優(yōu)解；若可行解集無(wú)界，則線性規(guī)劃可能有最優(yōu)解，也可能沒(méi)有最優(yōu)解；若線性規(guī)劃具有無(wú)界解，則可行域一定無(wú)界。

定理2.2及2.3還給了我們一個(gè)啟示，尋求最優(yōu)解可不在無(wú)限個(gè)可行解中去找，而是去有限個(gè)基本可行解中去找。下一節(jié)將介紹一種有效地尋找最優(yōu)解的方法。2.4基本概念BasicConcepts

現(xiàn)在是57頁(yè)\一共有120頁(yè)\編輯于星期一2.5單純形法SimplexMethod現(xiàn)在是58頁(yè)\一共有120頁(yè)\編輯于星期一

考慮到如下線性規(guī)劃問(wèn)題

其中Ａ一個(gè)m×n矩陣，且秩為m，ｂ總可以被調(diào)整為一個(gè)m維非負(fù)列向量，Ｃ為n維行向量，Ｘ為n維列向量。根據(jù)線性規(guī)劃基本定理：如果可行域Ｄ={Ｘ∈Ｒn/ＡＸ=ｂ，Ｘ≥0}非空有界，則Ｄ上的最優(yōu)目標(biāo)函數(shù)值Ｚ=ＣＸ一定可以在Ｄ的一個(gè)頂點(diǎn)上達(dá)到。這個(gè)重要的定理啟發(fā)了Dantzig的單純形法，即將尋優(yōu)的目標(biāo)集中在D的各個(gè)頂點(diǎn)上。單純形法的一般原理

現(xiàn)在是59頁(yè)\一共有120頁(yè)\編輯于星期一

Dantzig的單純形法把尋優(yōu)的目標(biāo)集中在所有基本可行解（即可行域頂點(diǎn)）中。其基本思路是從一個(gè)初始的基本可行解出發(fā)，尋找一條達(dá)到最優(yōu)基本可行解的最佳途徑。單純形法的一般步驟如下：（1）尋找一個(gè)初始的基本可行解。（2）檢查現(xiàn)行的基本可行解是否最優(yōu)，如果為最優(yōu)，則停止迭代，已找到最優(yōu)解，否則轉(zhuǎn)一步。（3）移至目標(biāo)函數(shù)值有所改善的另一個(gè)基本可行解，然后轉(zhuǎn)到步驟（2）。現(xiàn)在是60頁(yè)\一共有120頁(yè)\編輯于星期一確定初始的基本可行解

確定初始的基本可行解等價(jià)于確定初始的可行基，一旦初始的可行基確定了，那么對(duì)應(yīng)的初始基本可行解也就唯一確定

為了討論方便，不妨假設(shè)在標(biāo)準(zhǔn)型線性規(guī)劃中，系數(shù)矩陣Ａ中前m個(gè)系數(shù)列向量恰好構(gòu)成一個(gè)可行基，即Ａ=（ＢＮ），其中Ｂ=（Ｐ1，Ｐ2，…Ｐm）為基變量x1，x2，…xm的系數(shù)列向量構(gòu)成的可行基，Ｎ=(Ｐm+1，Pm+2,…,Pn)為非基變量xm+1,xm+2,…,xn的系數(shù)列向量構(gòu)成的矩陣。現(xiàn)在是61頁(yè)\一共有120頁(yè)\編輯于星期一所以約束方程就可以表示為

用可行基Ｂ的逆陣Ｂ-1左乘等式兩端，再通過(guò)移項(xiàng)可推得：若令所有非基變量,則基變量由此可得初始的基本可行解現(xiàn)在是62頁(yè)\一共有120頁(yè)\編輯于星期一問(wèn)題：要判斷m個(gè)系數(shù)列向量是否恰好構(gòu)成一個(gè)基并不是一件容易的事?；上禂?shù)矩陣Ａ中m個(gè)線性無(wú)關(guān)的系數(shù)列向量構(gòu)成。但是要判斷m個(gè)系數(shù)列向量是否線性無(wú)關(guān)并非易事。即使系數(shù)矩陣Ａ中找到了一個(gè)基B，也不能保證該基恰好是可行基。因?yàn)椴荒鼙ＷC基變量ＸB=Ｂ-1b≥0。為了求得基本可行解，必須求基Ｂ的逆陣Ｂ-1。但是求逆陣Ｂ-1也是一件麻煩的事。結(jié)論：在線性規(guī)劃標(biāo)準(zhǔn)化過(guò)程中應(yīng)設(shè)法得到一個(gè)m階單位矩陣I作為初始可行基Ｂ，現(xiàn)在是63頁(yè)\一共有120頁(yè)\編輯于星期一若在化標(biāo)準(zhǔn)形式前，約束方程中有“≥”不等式，那么在化標(biāo)準(zhǔn)型時(shí)除了在方程式左端減去剩余變量使不等式變成等式以外，還必須在左端再加上一個(gè)非負(fù)新變量，稱為人工變量．若在化標(biāo)準(zhǔn)形式前，約束方程中有等式方程，那么可以直接在等式左端添加人工變量。為了設(shè)法得到一個(gè)m階單位矩陣I作為初始可行基Ｂ，可在性規(guī)劃標(biāo)準(zhǔn)化過(guò)程中作如下處理：

若在化標(biāo)準(zhǔn)型前，m個(gè)約束方程都是“≤”的形式，那么在化標(biāo)準(zhǔn)型時(shí)只需在一個(gè)約束不等式左端都加上一個(gè)松弛變量xn+i(i=1,2,…,m)。現(xiàn)在是64頁(yè)\一共有120頁(yè)\編輯于星期一判斷現(xiàn)行的基本可行解是否最優(yōu)

假如已求得一個(gè)基本可行解將這一基本可行解代入目標(biāo)函數(shù)，可求得相應(yīng)的目標(biāo)函數(shù)值

其中分別表示基變量和非基變量所對(duì)應(yīng)的價(jià)值系數(shù)子向量?，F(xiàn)在是65頁(yè)\一共有120頁(yè)\編輯于星期一

要判定是否已經(jīng)達(dá)到最大值，只需將代入目標(biāo)函數(shù)，使目標(biāo)函數(shù)用非基變量表示，即：

其中稱為非基變量ＸN的檢驗(yàn)向量，它的各個(gè)分量稱為檢驗(yàn)數(shù)。若σN的每一個(gè)檢驗(yàn)數(shù)均小于等于0，即σN≤0，那么現(xiàn)在的基本可行解就是最優(yōu)解。現(xiàn)在是66頁(yè)\一共有120頁(yè)\編輯于星期一定理1最優(yōu)解判別定理對(duì)于線性規(guī)劃問(wèn)題若某個(gè)基本可行解所對(duì)應(yīng)的檢驗(yàn)向量，則這個(gè)基本可行解就是最優(yōu)解。定理2

無(wú)窮多最優(yōu)解判別定理若是一個(gè)基本可行解，所對(duì)應(yīng)的檢驗(yàn)向量，其中存在一個(gè)檢驗(yàn)數(shù)σm+k=0，則線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。現(xiàn)在是67頁(yè)\一共有120頁(yè)\編輯于星期一基本可行解的改進(jìn)

如果現(xiàn)行的基本可行解Ｘ不是最優(yōu)解，即在檢驗(yàn)向量中存在正的檢驗(yàn)數(shù)，則需在原基本可行解Ｘ的基礎(chǔ)上尋找一個(gè)新的基本可行解，并使目標(biāo)函數(shù)值有所改善。具體做法是：先從檢驗(yàn)數(shù)為正的非基變量中確定一個(gè)換入變量，使它從非基變量變成基變量（將它的值從零增至正值），再?gòu)脑瓉?lái)的基變量中確定一個(gè)換出變量，使它從基變量變成非基變量（將它的值從正值減至零）。由此可得一個(gè)新的基本可行解，由可知，這樣的變換一定能使目標(biāo)函數(shù)值有所增加。現(xiàn)在是68頁(yè)\一共有120頁(yè)\編輯于星期一換入變量和換出變量的確定：換入變量的確定—最大增加原則假設(shè)檢驗(yàn)向量，若其中有兩個(gè)以上的檢驗(yàn)數(shù)為正，那么為了使目標(biāo)函數(shù)值增加得快些，通常要用“最大增加原則”，即選取最大正檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量為換入變量，即若

則選取對(duì)應(yīng)的為換入變量，由于且為最大，因此當(dāng)由零增至正值，可使目標(biāo)函數(shù)值最大限度的增加?，F(xiàn)在是69頁(yè)\一共有120頁(yè)\編輯于星期一換出變量的確定—最小比值原則如果確定為換入變量，方程

其中為Ａ中與對(duì)應(yīng)的系數(shù)列向量?，F(xiàn)在需在中確定一個(gè)基變量為換出變量。當(dāng)由零慢慢增加到某個(gè)值時(shí)，的非負(fù)性可能被打破。為保持解的可行性，可以按最小比值原則確定換出變量：若則選取對(duì)應(yīng)的基變量為換出變量。現(xiàn)在是70頁(yè)\一共有120頁(yè)\編輯于星期一

定理3無(wú)最優(yōu)解判別定理若是一個(gè)基本可行解，有一個(gè)檢驗(yàn)數(shù)，但是，則該線性規(guī)劃問(wèn)題無(wú)最優(yōu)解。證：令，則得新的可行解將上式代入

因?yàn)?故當(dāng)λ→+∞時(shí)，Z→+∞。現(xiàn)在是71頁(yè)\一共有120頁(yè)\編輯于星期一用初等變換求改進(jìn)了的基本可行解

假設(shè)Ｂ是線性規(guī)劃的可行基，則令非基變量，則基變量?？傻没究尚薪狻Ｓ媚骊囎蟪思s束方程組的兩端，等價(jià)于對(duì)方程組施以一系列的初等“行變換”。變換的結(jié)果是將系數(shù)矩陣Ａ中的可行基Ｂ變換成單位矩陣I，把非基變量系數(shù)列向量構(gòu)成的矩陣Ｎ變換成，把資源向量b變換成。現(xiàn)在是72頁(yè)\一共有120頁(yè)\編輯于星期一

且改進(jìn)了的基本可行解只是在Ｘ的基變量的基礎(chǔ)上用一個(gè)換入變量替代其中一個(gè)換出變量，其他的基變量仍然保持不變。這些基變量的系數(shù)列向量是單位矩陣I中的單位向量。為了求得改進(jìn)的基本可行解，只需對(duì)增廣矩陣施行初等行變換，將換入變量的系數(shù)列向量變換成換出變量所對(duì)應(yīng)的單位向量即可。

由于行初等變換后的方程組與原約束方程組或同解現(xiàn)在是73頁(yè)\一共有120頁(yè)\編輯于星期一例1解：(１)確定初始的基本可行解。，基變量，非基變量。現(xiàn)在是74頁(yè)\一共有120頁(yè)\編輯于星期一(2)檢驗(yàn)是否最優(yōu)。檢驗(yàn)向量

因?yàn)棣?=3，σ3=4均大于零，所以不是最優(yōu)解?，F(xiàn)在是75頁(yè)\一共有120頁(yè)\編輯于星期一（3）基本可行解的改進(jìn)①

選取換入變量因?yàn)閙ax{3，4}=4，取x3為換入變量。②

選取換出變量且，選取x4為換出變量.現(xiàn)在是76頁(yè)\一共有120頁(yè)\編輯于星期一（4）求改進(jìn)了的基本可行解對(duì)約束方程組的增廣矩陣施以初等行變換，使換入變量x3所對(duì)應(yīng)的系數(shù)列向量變換成換出變量x4所對(duì)應(yīng)的單位向量,注意保持基變量x5的系數(shù)列向量為單位向量不變。第一行除以２第二行減去第一行現(xiàn)在是77頁(yè)\一共有120頁(yè)\編輯于星期一——————————————————————————可得改進(jìn)的基本可行解。，基變量，非基變量。

基本可行解

目標(biāo)函數(shù)值易見(jiàn)目標(biāo)函數(shù)值比原來(lái)的Z=-1增加了，再轉(zhuǎn)向步驟(2)現(xiàn)在是78頁(yè)\一共有120頁(yè)\編輯于星期一（2）檢驗(yàn)是否最優(yōu)。檢驗(yàn)向量

因?yàn)椋匀圆皇亲顑?yōu)解?，F(xiàn)在是79頁(yè)\一共有120頁(yè)\編輯于星期一（3）基本可行解的改進(jìn)①

選取換入變量因?yàn)椋閾Q入變量。②

選取換出變量且，選取為換出變量.現(xiàn)在是80頁(yè)\一共有120頁(yè)\編輯于星期一（4）求改進(jìn)了的基本可行解對(duì)約束方程組的增廣矩陣施以初等行變換，使換入變量所對(duì)應(yīng)的系數(shù)列向量變換成換出變量所對(duì)應(yīng)的單位向量

第二行乘以２/５第一行減以第二行的１/２倍現(xiàn)在是81頁(yè)\一共有120頁(yè)\編輯于星期一——————————————————————————可得改進(jìn)的基本可行解。，基變量，非基變量

基本可行解

目標(biāo)函數(shù)值比Z=15增加了，再轉(zhuǎn)向步驟(2)現(xiàn)在是82頁(yè)\一共有120頁(yè)\編輯于星期一（2）檢驗(yàn)是否最優(yōu)。檢驗(yàn)向量

因?yàn)樗袡z驗(yàn)數(shù)均小于零，所以是最優(yōu)解，現(xiàn)在是83頁(yè)\一共有120頁(yè)\編輯于星期一表格單純形法

通過(guò)例１我們發(fā)現(xiàn)，在單純形法的求解過(guò)程中，有下列重要指標(biāo)：每一個(gè)基本可行解的檢驗(yàn)向量根據(jù)檢驗(yàn)向量可以確定所求得的基本可行解是否為最優(yōu)解。如果不是最優(yōu)又可以通過(guò)檢驗(yàn)向量確定合適的換入變量。每一個(gè)基本可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值通過(guò)目標(biāo)函數(shù)值可以觀察單純形法的每次迭代是否能使目標(biāo)函數(shù)值有效地增加，直至求得最優(yōu)目標(biāo)函數(shù)為止。

在單純形法求解過(guò)程中，每一個(gè)基本可行解Ｘ都以某個(gè)經(jīng)過(guò)初等行變換的約束方程組中的單位矩陣Ι為可行基。當(dāng)Ｂ=Ｉ時(shí)，Ｂ-1=Ｉ，易知：現(xiàn)在是84頁(yè)\一共有120頁(yè)\編輯于星期一

可將這些重要結(jié)論的計(jì)算設(shè)計(jì)成如下一個(gè)簡(jiǎn)單的表格，即單純形表來(lái)完成：C

CBCN

θ

CB

XB

b

X1X2···Xm

Xm+1Xm+2···Xn

C1C2..Cm

X1X2.

.Xm

b1b2..bm

IN

θ1θ2..θm

Z

CBb

0

CN-CBN

現(xiàn)在是85頁(yè)\一共有120頁(yè)\編輯于星期一

例2試?yán)脝渭冃伪砬罄?中的最優(yōu)解解：

得初始的單純形表：初始基本可行解，Z=-1，122108x4-130400-1Z341017x51x1x2x3x4x5bXBCBΘ523-11C現(xiàn)在是86頁(yè)\一共有120頁(yè)\編輯于星期一

換入變量，換出變量，２為主元進(jìn)行旋轉(zhuǎn)變換基本可行解，Z=15，1/2111/204x331-40-2015Z5/230-1/213x51

x1x2x3x4x5bXBCBΘ523-11C122108x4-130400-1Z341017x51x1x2x3x4x5bXBCBΘ523-11C8/27/1現(xiàn)在是87頁(yè)\一共有120頁(yè)\編輯于星期一

最優(yōu)解最優(yōu)值

換入變量，換出變量，５/２為主元進(jìn)行旋轉(zhuǎn)變換4/1/21/2111/204x331-40-2015Z3/5/25/230-1/213x51

x1x2x3x4x5bXBCBΘ523-11C02/513/5-1/517/5x330-26/50-9/5-2/581/5Z16/50-1/52/56/5x15x1x2x3x4x5bXBCBΘ523-11C現(xiàn)在是88頁(yè)\一共有120頁(yè)\編輯于星期一例3用單純形方法求解線性規(guī)劃問(wèn)題解：本題的目標(biāo)函數(shù)是求極小化的線性函數(shù)，可以令則這兩個(gè)線性規(guī)劃問(wèn)題具有相同的可行域和最優(yōu)解，只是目標(biāo)函數(shù)相差一個(gè)符號(hào)而已。

現(xiàn)在是89頁(yè)\一共有120頁(yè)\編輯于星期一010103x220012-12x30-010103x224/1101004x303/1010103x40_101004x300000-18Z’100-212x11100-206Z’2/1100-212x50120000Z’8/2120018x50x1x2x3x4x5bXBCBΘ12000C最優(yōu)解最優(yōu)值2/23/1-現(xiàn)在是90頁(yè)\一共有120頁(yè)\編輯于星期一

因?yàn)榉腔兞縳4的檢驗(yàn)數(shù)σ4=0，由無(wú)窮多最優(yōu)解判別定理，本例的線性規(guī)劃問(wèn)題存在無(wú)窮多最優(yōu)解。事實(shí)上若以x4為換入變量，以x3為換出變量，再進(jìn)行一次迭代，可得以下單純形表：最優(yōu)解最優(yōu)值最優(yōu)解的一般表示式C12000ΘCBXBbx1x2x3x4x5021x4x2x1124001/21-1/201-1/201/210100Z’80000-1現(xiàn)在是91頁(yè)\一共有120頁(yè)\編輯于星期一對(duì)于極小化的線性規(guī)劃問(wèn)題的處理：先化為標(biāo)準(zhǔn)型，即將極小化問(wèn)題變換為極大化問(wèn)題，然后利用單純形方法求解．直接利用單純形方法求解，但是檢驗(yàn)是否最優(yōu)的準(zhǔn)則有所不同，即：若某個(gè)基本可行解的所有非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)（而不是≤０），則基本可行解為最優(yōu)解．否則采用最大減少原則（而非最大增加原則）來(lái)確定換入變量，即：若則選取對(duì)應(yīng)的非基變量xm+k為換入變量．確定了換入變量以后，換出變量仍采用最小比值原則來(lái)確定?，F(xiàn)在是92頁(yè)\一共有120頁(yè)\編輯于星期一借助人工變量求初始的基本可行解

若約束方程組含有“≥”不等式，那么在化標(biāo)準(zhǔn)形時(shí)除了在方程式左端減去剩余變量，還必須在左端加上一個(gè)非負(fù)的人工變量。因?yàn)槿斯ぷ兞渴窃诩s束方程已為等式的基礎(chǔ)上，人為的加上去的一個(gè)新變量，因此加入人工變量后的約束方程組與原約束方程組是不等價(jià)的。加上人工變量以后，線性規(guī)劃的基本可行解不一定是原線性規(guī)劃的問(wèn)題的基本可行解。只有當(dāng)基本可行解中所有人工變量都為取零值的非基變量時(shí)，該基本可行解對(duì)原線性規(guī)劃才有意義。因?yàn)榇藭r(shí)只需去掉基本可行解中的人工變量部分，剩余部分即為原線性規(guī)劃的一個(gè)基本可行解．而這正是我們引入人工變量的主要目的?，F(xiàn)在是93頁(yè)\一共有120頁(yè)\編輯于星期一借助人工變量求初始的基本可行解

若約束方程組含有“≥”不等式，那么在化標(biāo)準(zhǔn)形時(shí)除了在方程式左端減去剩余變量，還必須在左端加上一個(gè)非負(fù)的人工變量。因?yàn)槿斯ぷ兞渴窃诩s束方程已為等式的基礎(chǔ)上，人為的加上去的一個(gè)新變量，因此加入人工變量后的約束方程組與原約束方程組是不等價(jià)的。加上人工變量以后，線性規(guī)劃的基本可行解不一定是原線性規(guī)劃的問(wèn)題的基本可行解。只有當(dāng)基本可行解中所有人工變量都為取零值的非基變量時(shí)，該基本可行解對(duì)原線性規(guī)劃才有意義。因?yàn)榇藭r(shí)只需去掉基本可行解中的人工變量部分，剩余部分即為原線性規(guī)劃的一個(gè)基本可行解．而這正是我們引入人工變量的主要目的?，F(xiàn)在是94頁(yè)\一共有120頁(yè)\編輯于星期一考慮線性規(guī)劃問(wèn)題：為了在約束方程組的系數(shù)矩陣中得到一個(gè)m階單位矩陣作為初始可行基，在每個(gè)約束方程組的左端加上一個(gè)人工變量

可得到：

現(xiàn)在是95頁(yè)\一共有120頁(yè)\編輯于星期一

————————————————————————

添加了m個(gè)人工變量以后，在系數(shù)矩陣中得到一個(gè)m階單位矩陣，以該單位矩陣對(duì)應(yīng)的人工變量為基變量，即可得到一個(gè)初始的基本可行解這樣的基本可行解對(duì)原線性規(guī)劃沒(méi)有意義的。但是我們可以從X(0)出發(fā)進(jìn)行迭代，一旦所有的人工變量都從基變量迭代出來(lái)，變成只能取零值的非基變量，那么我們實(shí)際上已經(jīng)求得了原線性規(guī)劃問(wèn)題的一個(gè)初始的基本可行解。此時(shí)可以把所有人工變量剔除，開(kāi)始正式進(jìn)入求原線性規(guī)劃最優(yōu)解的過(guò)程。現(xiàn)在是96頁(yè)\一共有120頁(yè)\編輯于星期一大M法

大M法首先將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型。如果約束方程組中包含有一個(gè)單位矩陣I，那么已經(jīng)得到了一個(gè)初始可行基。否則在約束方程組的左邊加上若干個(gè)非負(fù)的人工變量，使人工變量對(duì)應(yīng)的系數(shù)列向量與其他變量的系數(shù)列向量共同構(gòu)成一個(gè)單位矩陣。以單位矩陣為初始基，即可求得一個(gè)初始的基本可行解。為了求得原問(wèn)題的初始基本可行解，必須盡快通過(guò)迭代過(guò)程把人工變量從基變量中替換出來(lái)成為非基變量。為此可以在目標(biāo)函數(shù)中賦予人工變量一個(gè)絕對(duì)值很大的負(fù)系數(shù)-Ｍ。這樣只要基變量中還存在人工變量，目標(biāo)函數(shù)就不可能實(shí)現(xiàn)極大化。以后的計(jì)算與單純形表解法相同，Ｍ只需認(rèn)定是一個(gè)很大的正數(shù)即可。假如在單純形最優(yōu)表的基變量中還包含人工變量，則說(shuō)明原問(wèn)題無(wú)可行解。否則最優(yōu)解中剔除人工變量的剩余部分即為原問(wèn)題的初始基本可行解。現(xiàn)在是97頁(yè)\一共有120頁(yè)\編輯于星期一例4用大M法求解下面的線性規(guī)劃問(wèn)題:解：首先將原問(wèn)題化為標(biāo)準(zhǔn)型添加人工變量，并在目標(biāo)函數(shù)中分別賦予-Ｍ

現(xiàn)在是98頁(yè)\一共有120頁(yè)\編輯于星期一-01-1/2-1/201/21/23/2X2210-1/21/201/2-1/21/2X1-1--110-10011X221/220-1101-11X6-M1/1-110-10011X7-M2/111-100102X6-M001/23/20-1/2-M-3/2-M5/2Z001/21/21-1/2-1/23/2X501+2M0-M2+M00-2-2M2-MZ2/1100110-12X50-12+2M-M-M000-3MZ3/101001003X50

X1X2X3X4X5X6X7bXBCBθ

-12000-M-MC現(xiàn)在是99頁(yè)\一共有120頁(yè)\編輯于星期一01001003X22100110-12X4011-100102X2220-1101-11X40-01-1/2-1/201/21/23/2X221/2/1/210-1/21/201/2-1/21/2X1-1-1000-2-M-M6Z-10101-101X30-30200-2-M-M4Z-10101-101X50001/23/20-1/2-M-3/2-M5/2Z3/2/1/2001/21/21-1/2-1/23/2X50X1X2X3X4X5X6X7bXBCBθ-12000-M-MC最優(yōu)解最優(yōu)值現(xiàn)在是100頁(yè)\一共有120頁(yè)\編輯于星期一兩階段法

兩階段法引入人工變量的目的和原則與大M法相同，所不同的是處理人工變量的方法。兩階段法的步驟：求解一個(gè)輔助線性規(guī)劃。目標(biāo)函數(shù)取所有人工變量之和，并取極小化；約束條件為原問(wèn)題中引入人工變量后包含一個(gè)單位矩陣的標(biāo)準(zhǔn)型的約束條件。如果輔助線性規(guī)劃存在一個(gè)基本可行解，使目標(biāo)函數(shù)的最小值等于零，則所有人工變量都已經(jīng)“離基”。表明原問(wèn)題已經(jīng)得了一個(gè)初始的基本可行解，可轉(zhuǎn)入第二階段繼續(xù)計(jì)算；否則說(shuō)明原問(wèn)題沒(méi)有可行解，可停止計(jì)算。求原問(wèn)題的最優(yōu)解。在第一階段已求得原問(wèn)題的一個(gè)初始基本可行解的基礎(chǔ)上，繼續(xù)用單純形法求原問(wèn)題的最優(yōu)解現(xiàn)在是101頁(yè)\一共有120頁(yè)\編輯于星期一例5用兩階段法求解例4中的線性規(guī)劃問(wèn)題。解：首先將問(wèn)題化為標(biāo)準(zhǔn)型添加人工變量x6,x7,并建立輔助線性規(guī)劃如下：由于輔助線性規(guī)劃的目標(biāo)函數(shù)是極小化，因此最優(yōu)解的判別準(zhǔn)則應(yīng)為：現(xiàn)在是102頁(yè)\一共有120頁(yè)\編輯于星期一01-1/2-1/201/21/23/2X2010-1/21/201/2-1/21/2X10--110-10011X201/220-1101-11X611/1-110-10011X712/111-100102X6100000110W001/21/21-1/2-1/23/2X50-201-10021W2/1100110-12X500-2110003W3/101001003X50X1X2X3X4X5X6X7bXBCBθ0000011C輔助規(guī)劃所有檢驗(yàn)數(shù)：,原問(wèn)題已得一個(gè)初始基本可行解，現(xiàn)在是103頁(yè)\一共有120頁(yè)\編輯于星期一由上表可知，通過(guò)若干次旋轉(zhuǎn)變換，原問(wèn)題的約束方程組已變換成包含一個(gè)單位矩陣的約束方程組該約束方程組可作為第二階段初始約束方程組，將目標(biāo)函數(shù)則還原成原問(wèn)題的目標(biāo)函數(shù)，可繼續(xù)利用單純形表求解?，F(xiàn)在是104頁(yè)\一共有120頁(yè)\編輯于星期一-1000-26Z1001101001-10101231X4X2X3020-302004Z20-11011-100-10101121X4X2X5020

001/23/205/2Z1/2/1/2-3/2/1/2

10-1/21/2001-1/2-1/21

001/21/211/23/23/2X1X2X5-120

X1X2X3X4X5

bXBCBθ-12000

0C可得最優(yōu)解，目標(biāo)函數(shù)值maxZ=6，與用大M法的結(jié)果完全相同。現(xiàn)在是105頁(yè)\一共有120頁(yè)\編輯于星期一單純形表與線性規(guī)劃問(wèn)題的討論

無(wú)可行解

通過(guò)大Ｍ法或兩階段法求初始的基本可行解。但是如果在大Ｍ法的最優(yōu)單純形表的基變量中仍含有人工變量，或者兩階段法的輔助線性規(guī)劃的目標(biāo)函數(shù)的極小值大于零，那么該線性規(guī)劃就不存在可行解。人工變量的值不能取零，說(shuō)明了原線性規(guī)劃的數(shù)學(xué)模型的約束條件出現(xiàn)了相互矛盾的約束方程。此時(shí)線性規(guī)劃問(wèn)題的可行域?yàn)榭占，F(xiàn)在是106頁(yè)\一共有120頁(yè)\編輯于星期一例6求解下列線性規(guī)劃問(wèn)題解：首先將問(wèn)題化為標(biāo)準(zhǔn)型令，則

故引入人工變量，并利用大M法求解現(xiàn)在是107頁(yè)\一共有120頁(yè)\編輯于星期一C

-3-2-1000-M-M

CB

XB

b

X1X2X3X4X5X6X7X8

θ

0-M-M

X4X7X8

643

1111000010-10-101001-100-101

6/1-3/1

Z’

-7M

-6-4M

-15-M

-3+M-2+M-1-2M0-M-M00

0-M-2

X4X7x2

343

1021010-110-10-1