線性規(guī)劃圖解法幾何意

關(guān)于線性規(guī)劃圖解法幾何意1.3．線性規(guī)劃問題的標(biāo)準(zhǔn)形式(其中bi≥0(i=1,2,...,m)稱下列形式為線性規(guī)劃問題的標(biāo)準(zhǔn)形式:目標(biāo)函數(shù)求極大,約束條件為等式,決策變量及右邊常數(shù)項(xiàng)為非負(fù)第2頁,共59頁，2024年2月25日，星期天線性規(guī)劃問題的幾種表示形式第3頁,共59頁，2024年2月25日，星期天用向量表示為：第4頁,共59頁，2024年2月25日，星期天則標(biāo)準(zhǔn)形式的矩陣表示：若令A(yù)－－稱為系數(shù)矩陣b－－稱為資源向量C－－稱為價(jià)值向量X－－稱為決策變量向量用矩陣表示為：第5頁,共59頁，2024年2月25日，星期天非標(biāo)準(zhǔn)形式化為標(biāo)準(zhǔn)形式的方法1.當(dāng)目標(biāo)函數(shù)為求極小值,即

minz=c1x1+c2x2+...+cnxn因?yàn)榍髆inz等價(jià)于max(-z)

故可令則目標(biāo)函數(shù)化為:2.當(dāng)右端項(xiàng)bi<0時(shí)只需將等式或不等式兩端同乘(-1),則右端項(xiàng)必大于03.當(dāng)約束條件為ai1x1+ai2x2+...+ainxn≤bi引入一個(gè)變量xn+i≥0

可使成為等式即ai1x1+ai2x2+...+ainxn＋xn+i＝bi變量xn+i稱為松弛變量第6頁,共59頁，2024年2月25日，星期天4.

當(dāng)約束條件為ai1x1+ai2x2+...+ainxn≥bi時(shí)則引入一個(gè)變量xn+i≥0可使不等式成為等式,即

ai1x1+ai2x2+...+ainxn－xn+i＝bi變量xn+i稱為剩余變量5.當(dāng)變量xi為無約束的變量時(shí)則我們引入兩個(gè)變量令:將其代入線性規(guī)劃模型中6.當(dāng)變量xi≤0時(shí)則令再代入線性規(guī)劃模型中第7頁,共59頁，2024年2月25日，星期天

例3

將例1的數(shù)學(xué)模型化為標(biāo)準(zhǔn)形

該線性規(guī)劃問題加入三個(gè)松馳變量x3,x4,x5≥0后：第8頁,共59頁，2024年2月25日，星期天例4

將下述線性規(guī)劃問題化為標(biāo)準(zhǔn)形

解：分以下步驟進(jìn)行處理(1)令z′=-z，把求minz改為求maxz′;(2)在第一個(gè)約束不等式≤號的左端加入松弛變量x4；(3)在第二個(gè)約束不等式≥號的左端減去剩余變量x5；(4)用x’3-x”3替換x3，其中x’3，x”3≥0,即可得到該問題的標(biāo)準(zhǔn)形.第9頁,共59頁，2024年2月25日，星期天得原問題的標(biāo)準(zhǔn)形為：

第10頁,共59頁，2024年2月25日，星期天1.4線性規(guī)劃問題的解的概念1.可行解2.基3.基可行解4.可行基第11頁,共59頁，2024年2月25日，星期天一.線性規(guī)劃問題解的概念線性規(guī)劃問題1.可行解:滿足線性規(guī)劃問題的約束條件的解X=(x1，x2，...，xn)

T稱為線性規(guī)劃問題的可行解。2.可行域:

全部可行解構(gòu)成的集合稱為可行域。3.最優(yōu)解:

使目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解稱為最優(yōu)解。4.基:

設(shè)系數(shù)矩陣Am×n(n>m)其秩為m,B是矩陣A中的一個(gè)m×m階的滿秩子矩陣,稱B是線性規(guī)劃問題的一個(gè)基。第12頁,共59頁，2024年2月25日，星期天一.線性規(guī)劃問題解的概念（2）=(P1,P2,...,Pm)

B中的每一列向量Pj(j=1,2,...m)稱為基向量

基向量：

與基向量Pj的對應(yīng)的變量xj

稱為基變量

基變量：

非基變量：

線性規(guī)劃中的其余變量稱為非基向量

5.基解

設(shè)X是（LP）的約束方程AX=b的一個(gè)解，B是一個(gè)基，若X中對應(yīng)基B的非基變量取值全為零，則稱X為(LP)關(guān)于基B的基解，記作X(B)

不妨設(shè)基為

基解的個(gè)數(shù)不會超過個(gè)第13頁,共59頁，2024年2月25日，星期天一.線性規(guī)劃問題解的概念（3）可證明:一個(gè)基唯一地確定一個(gè)基解.

6.基可行解：若基解X(B)滿足非負(fù)條件X(B)≥0，則稱基解X(B)為基可行解

7.基最優(yōu)解：若基可行解X(B)是(LP)的最優(yōu)解,則稱X(B)為(LP)的基最優(yōu)解.

最優(yōu)基：基最優(yōu)解對應(yīng)的可行基B稱為最優(yōu)基.

可行基：基可行解對應(yīng)的基B稱為可行基.

注:基解沒有X≥0的限制,故基解不一定是可行解.

X(B)=第14頁,共59頁，2024年2月25日，星期天一.線性規(guī)劃問題解的概念（4）8.退化解：若基本可行解X的所有基變量的值均大于0，則稱X是非退化的，否則稱X為退化的。若(LP)的所有基本可行解都是非退化的,則稱線性規(guī)劃問題是非退化的.

第15頁,共59頁，2024年2月25日，星期天二.例題考慮線性規(guī)劃問題：

約束方程的系數(shù)矩陣A很顯然A中的后3列是線性無關(guān)的，它們構(gòu)成一個(gè)基基B1對應(yīng)的變量x3,x4,x5是基變量,x1,x2是非基變量第16頁,共59頁，2024年2月25日，星期天二.例題（2）若令：

得該解是對應(yīng)B1的基解，它是基可行解，B1是可行基；如取是（LP）的一個(gè)基，若令：

基B2對應(yīng)的變量x1,x2,x3是基變量，,x4,x5是非基變量得該解是對應(yīng)B2的基解，它不是基可行解，B2不是可行基；第17頁,共59頁，2024年2月25日，星期天三.線性規(guī)劃問題解的關(guān)系圖AX=b的解

基解若非基變量為0

基可行解

基最優(yōu)解B是A的m階子矩陣基B若|B|

0可行基B當(dāng)B-1b

0最優(yōu)基B若基變量取非負(fù)若對應(yīng)目標(biāo)函數(shù)值最優(yōu)第18頁,共59頁，2024年2月25日，星期天非可行解三.線性規(guī)劃問題解的關(guān)系圖（2）可行解基可行解基解基可行基最優(yōu)基第19頁,共59頁，2024年2月25日，星期天第2節(jié)線性規(guī)劃問題的幾何意義2.1基本概念2.2幾個(gè)定理第20頁,共59頁，2024年2月25日，星期天一.凸集與頂點(diǎn)凸集:

如果集合K中任意兩個(gè)點(diǎn)X(1),X(2),其連線上的所有點(diǎn)也都是集合K中的點(diǎn),則稱集合K為凸集.或K={X|X=αX(1)+(1-α)X(2),X(1)

K,X(2)

K,0≤α≤1}

定理:D＝｛x∈Rn|Ax=b,x≥0}是凸集頂點(diǎn):凸集K中滿足下列條件的點(diǎn)X稱為頂點(diǎn):如果K中不存在任何兩個(gè)不同的點(diǎn)X1,X2,使X成為這兩個(gè)點(diǎn)連線上的一個(gè)點(diǎn).定理:

有限個(gè)凸集的交集還是凸集凸組合:設(shè)是n維歐氏空間中的k個(gè)點(diǎn)則稱X是的凸組合第21頁,共59頁，2024年2月25日，星期天凸集的概念：凸集凸集不是凸集頂點(diǎn)不是凸集第22頁,共59頁，2024年2月25日，星期天二.幾個(gè)基本定理定理1若線性規(guī)劃問題存在可行解,則問題的可行域是凸集.定理2若線性規(guī)劃問題有非零可行解，則其必有基可行解。定理4若線性規(guī)劃問題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解。定理3線性規(guī)劃問題的基可行解X對應(yīng)線性規(guī)劃問題可行域(凸集)的頂點(diǎn).引理1線性規(guī)劃的可行解X＝(x1,x2,…,xn)T為基可行解的充要條件是X的正分量所對應(yīng)的系數(shù)列向量是線性無關(guān)的。第23頁,共59頁，2024年2月25日，星期天第3節(jié)單純形法第24頁,共59頁，2024年2月25日，星期天一.單純形法迭代的基本思想

開始于某一個(gè)可行基及其對應(yīng)的基可行解，從一個(gè)基可行解迭代到另一個(gè)基可行解，并且使目標(biāo)函數(shù)值不斷增大，經(jīng)過有限步必能求得線性規(guī)劃問題的最優(yōu)解或者判定線性規(guī)劃問題無有界的最優(yōu)解（無界解）。第25頁,共59頁，2024年2月25日，星期天二.單純形法引例考慮線性規(guī)劃問題：

約束方程的系數(shù)矩陣A很顯然A中的后3列是線性無關(guān)的，它們構(gòu)成一個(gè)基基B對應(yīng)的變量x3,x4,x5是基變量，則第26頁,共59頁，2024年2月25日，星期天二.單純形法引例（2）即：

將它們代入目標(biāo)函數(shù)中得令非基變量x1=x2=0,得目標(biāo)值

z＝0

一個(gè)基可行解X(0)＝(0,0,8,16,12)為了使目標(biāo)函數(shù)能更大，讓x2變成基變量，原基變量的x3，x4，x5要有一個(gè)變?yōu)榉腔兞慨?dāng)x1=0,由最上式得從上式可看出，當(dāng)x2=3仍可保證所有變量非負(fù)，并使目標(biāo)函數(shù)增大第27頁,共59頁，2024年2月25日，星期天二.單純形法引例（3）為了得到以x3,x4,x2為基變量的一個(gè)基可行解，則對左邊方程中的x2與x5互換得再令非基變量x1=x5=0,得目標(biāo)值

z＝9

一個(gè)基可行解X(0)＝(0,3,2,16,0)為了使目標(biāo)函數(shù)能更大，讓x1變成基變量，原基變量的x3，x4，x2要有一個(gè)變?yōu)榉腔兞磕繕?biāo)函數(shù)變?yōu)榈?8頁,共59頁，2024年2月25日，星期天二.單純形法引例（4）這樣如此下去，可得X(2)＝(2,3,0,8,0)為了使目標(biāo)函數(shù)能更大，讓x1變成基變量，原基變量的x3，x4，x2要有一個(gè)變?yōu)榉腔兞看藭r(shí)目標(biāo)函數(shù)變?yōu)閄(3)＝(4,2,0,0,4)由于目標(biāo)函數(shù)中的變量系數(shù)都小于等于0，所以X(3)＝（4,2,0,0,4)為最優(yōu)解，最優(yōu)值z＊＝14▲下面從幾何角度分析一下最優(yōu)解的尋求過程：第29頁,共59頁，2024年2月25日，星期天幾何意義：頂點(diǎn)轉(zhuǎn)移，目標(biāo)增大第30頁,共59頁，2024年2月25日，星期天三.單純形法原理1.確定初始基可行解：對標(biāo)準(zhǔn)型的LP問題在約束條件(1.1)的變量的系數(shù)矩陣中總會存在一個(gè)單位矩陣。(2)當(dāng)線性規(guī)劃的約束條件都為≤號時(shí)，其松弛變量對應(yīng)的系數(shù)列向量構(gòu)成的矩陣即為單位陣；(3)當(dāng)線性規(guī)劃的約束條件為≥或＝的情況，引入人工變量后也可實(shí)現(xiàn)。(1)系數(shù)矩陣中可以直接觀察得到一個(gè)單位子矩陣；第31頁,共59頁，2024年2月25日，星期天三.單純形法原理（2）2.從一個(gè)基可行解轉(zhuǎn)換為相鄰的基可行解：定義：兩個(gè)基可行解稱為相鄰的，如果他們之間變換且僅變換一個(gè)基變量。設(shè)初始基可行解為：可知：其對應(yīng)的系數(shù)矩陣的增廣矩陣為：第32頁,共59頁，2024年2月25日，星期天三.單純形法原理（3）易得：(1.3)+(1.4)×θ(θ>0),得令：顯然：為使X(1)成為可行解，令：可證明:將(1.6)式代回到X(1)中,X(1)

為基可行解，此時(shí)完成了從一個(gè)基可行解到另一個(gè)與其相鄰的基可行解的轉(zhuǎn)換。第33頁,共59頁，2024年2月25日，星期天三.單純形法原理（4）證明：將與變量x1,…,xl-1,xl+1…,xm,xj對應(yīng)的列向量，經(jīng)重新排列后加上b列有如下形式：因?yàn)镻1,P2,…,Pl-1，Pj,Pl+1,…Pm線性無關(guān)，故X(1)為基可行解。第34頁,共59頁，2024年2月25日，星期天三.單純形法原理（5）3.最優(yōu)性檢驗(yàn)與解的判別：將2中的基可行解X(0)與X(1)分別代入目標(biāo)函數(shù)，得

稱為檢驗(yàn)數(shù)第35頁,共59頁，2024年2月25日，星期天三.單純形法原理（6）(1)當(dāng)所有的λj≤0時(shí)，現(xiàn)行基可行解為最優(yōu)解；①當(dāng)所有的λj<0時(shí)，該線性規(guī)劃問題有唯一最優(yōu)解；②當(dāng)所有的λj≤0，且對某個(gè)非基變量xk，有λk=0,該線性規(guī)劃問題有無窮多最優(yōu)解。(2)當(dāng)存在某個(gè)λj>0且對應(yīng)的列向量Pj≤0時(shí)，該線性規(guī)劃問題有無界解；(4)對線性規(guī)劃問題無可行解的判別將在后面討論。(2)當(dāng)存在某個(gè)λj>0且對應(yīng)的列向量Pj

中有正分量時(shí)，說明目標(biāo)函數(shù)值還可以增大，需要進(jìn)行基變換；第36頁,共59頁，2024年2月25日，星期天第4節(jié)

單純形法的計(jì)算步驟第37頁,共59頁，2024年2月25日，星期天一.單純形法的計(jì)算步驟第一步：求初始基可行解，列出初始單純形表XB

bx1x2...xmxm+1

...xj...xnx1x2...xmb1b2...bm

10...0a1,m+1...a1j...a1n01...0a2,m+1...a2j...a2n...........................00...1am,m+1...amj...amnc

c1c2...cm

cm+1

...cj

...cn首先寫出關(guān)于價(jià)值系數(shù)的表：（非單純形表）第38頁,共59頁，2024年2月25日，星期天一.單純形法的計(jì)算步驟（2）將基變量下方的價(jià)值系數(shù)通過變換化為零，得初始單純形表XB

bx1x2...xmxm+1

...xj...xnx1x2...xm

b1b2...bm

10...0a1,m+1...a1j...a1n01...0a2,m+1...a2j...a2n...........................00...1am,m+1...amj...amn

-z

00...0

......

第39頁,共59頁，2024年2月25日，星期天一.單純形法的計(jì)算步驟（3）第二步：最優(yōu)性檢驗(yàn)(1)當(dāng)所有的λj≤0時(shí)，現(xiàn)行基可行解為最優(yōu)解；①當(dāng)所有的λj<0時(shí)，該線性規(guī)劃問題有唯一最優(yōu)解；②當(dāng)所有的λj≤0，且對某個(gè)非基變量xk，有λk=0,該線性規(guī)劃問題有無窮多最優(yōu)解。(2)當(dāng)存在某個(gè)λj>0且對應(yīng)的列向量Pj≤0時(shí)，該線性規(guī)劃問題有無界解；(3)當(dāng)存在某個(gè)λj>0且對應(yīng)的列向量Pj

中有正分量時(shí)，說明目標(biāo)函數(shù)值還可以增大，需要進(jìn)行基變換。第40頁,共59頁，2024年2月25日，星期天一.單純形法的計(jì)算步驟(4)第三步：換基迭代

(1)確定進(jìn)基變量選擇檢驗(yàn)數(shù)最大的非基變量為進(jìn)基變量λk=max{λj|λj>0,j=1,2,...,n}則xk為進(jìn)基變量

(2)確定出基變量

根據(jù)下列原則確定出基變量則λl所對應(yīng)的基變量xl為出基變量元素alk為軸心項(xiàng)(或稱為主元素)(3)以alk為軸心項(xiàng)進(jìn)行換基迭代

即利用矩陣的初等行變換把元素alk所在的列化為單位向量.得到新的單純形表第41頁,共59頁，2024年2月25日，星期天一.單純形法的計(jì)算步驟（5）第四步：重復(fù)第二、三步，一直到計(jì)算結(jié)束為止。第42頁,共59頁，2024年2月25日，星期天二．單純形法例1(1)例用單純形法解下列線性規(guī)劃

解:將原問題化為標(biāo)準(zhǔn)形為：得單純形初表為:第43頁,共59頁，2024年2月25日，星期天

XB

b

x1x2x3x4x5

x3x4x5

81612

121004001004001

－z

0

23000二．單純形法例1(2)

T(B1)x3x4x2-z21010-1/21640010301001/4-92000-3/4

T(B2)第44頁,共59頁，2024年2月25日，星期天

XB

b

x1x2x3x4x5

x3x4x2

2163

1010-1/24001001001/4

-z

-9

2000-3/4

T(B2)x1x4x2-z21010-1/2800-412301001/4-1300-201/4

T(B3)二．單純形法例1(3)第45頁,共59頁，2024年2月25日，星期天

XB

b

x1x2x3x4x5

x1x4x2

283

1010-1/200-41201001/4

-z

-13

00-201/4

T(B3)x1x5x2-z41001/40400-21/212011/2-1/80-1400-3/2-1/80

T(B4)二．單純形法例1(4)第46頁,共59頁，2024年2月25日，星期天二．單純形法例1(4)在單純形終表中，x3,x4為非基變量，所有非基變量檢驗(yàn)數(shù)均小于零，故該線性規(guī)劃問題有唯一最優(yōu)解X*=(4,2,0,0,4)T

，最優(yōu)值為

Z*=14。第47頁,共59頁，2024年2月25日，星期天二．單純形法例2(1)例2:用單純形法解下列線性規(guī)劃

解:將原問題化為標(biāo)準(zhǔn)形為：得單純形初表為:第48頁,共59頁，2024年2月25日，星期天

XB

b

x1x2x3x4x5

x3x4x5

438

101000101012001

-z

012000

T(B1)x3x2x5-z4101003010102100-21-6100-20

T(B2)二．單純形法例2(2)第49頁,共59頁，2024年2月25日，星期天

XB

b

x1x2x3x4x5

x3x2x5

432

1010001010100-21

-z-6

100-20

T(B2)x3x2x1-z2001221-80000-1

T(B3)二．單純形法例2(3)第50頁,共59頁，2024年2月25日，星期天二．單純形法例2(4)在單純形終表中，x4,x5為非基變量，非基變量檢驗(yàn)數(shù)均小于等于零，且λ4=0,λ5=-1<0;故該線性規(guī)劃問題有無窮多最優(yōu)解。注：在上述單純形終表中，以x4為進(jìn)基變量，按照極小化原則確定出基變量x3，進(jìn)行基變換，可得該線性規(guī)劃問題的另一個(gè)最優(yōu)解。第51頁,共59頁，2024年2月25日，星期天

XB

b

x1x2x3x4x5

x3x2x1

232

0012-101010100-21-z-8

0000-1

T(B3)x4x2x1-z1001/21-1/2201-1/201/2410100-80000-1

T(B4)最優(yōu)解X*=(2,3,2,0,0)T

最優(yōu)值Z*=8六．單純形法舉例2(5)

最優(yōu)值Z*=8最優(yōu)解X*=(4,2,0,1,0)T第52頁,共59頁，2024年2月25日，星期天開始判斷所有檢驗(yàn)數(shù)是否小于等于0得到最優(yōu)解構(gòu)造單純形表NO

輸入結(jié)束Yes

是否存在某個(gè)大于0的檢驗(yàn)數(shù)所對應(yīng)的列的元素全小于等于0？原問題為無界解換基迭代選擇出基變量Yes

選擇進(jìn)基變量NO

單純形法的框圖表示為如下:第53頁,共59頁，2024年2月25日，星期天注：㈠退化情形的處理為避免出現(xiàn)計(jì)算的循環(huán)，1947年勃蘭特（Bland）提出了一個(gè)簡單有效的規(guī)則：(1)當(dāng)存在多個(gè)λj>0時(shí)，始終選取下標(biāo)值為最小的變量為進(jìn)基變量；(2)當(dāng)計(jì)算θ值出現(xiàn)兩個(gè)以上相同的最小比值時(shí)，始終選取下標(biāo)值為最小的變量為出基變量。按最小比值θ來確定出基變量時(shí)，有時(shí)會出現(xiàn)兩個(gè)以上相同的最小比值，從而使下一個(gè)單純形表中出現(xiàn)一個(gè)或多個(gè)基變量