線性規(guī)劃的二階段法

關于線性規(guī)劃的二階段法

線性規(guī)劃的人工變量法目前有兩種方法：大M法和二階段法。人工變量法在討論單純形法時，我們總是假定AX＝b的系數(shù)矩陣A的秩r(A)=m<n,或者已有一個可行基。但是，在許多問題中，初始可行基是不容易找到的，或者A不滿秩。這樣單純形法就很難進行。所以，我們要探討如何尋找第一個可行基？第2頁,共32頁，2024年2月25日，星期天大M法（1）把原問題化為下列形式：其中M是任意大的正數(shù)第3頁,共32頁，2024年2月25日，星期天大M法（2）關于大M法的幾點注釋：(1)在引入人工變量之前，約束條件已是等式，為了這些等式得到滿足，因此在最優(yōu)解中人工變量取值必須為零；為此在目標函數(shù)中人工變量的取值為充分小的負數(shù)，用“-M”代表；(2)若在單純形表中有λj≤0，且存在非零人工變量，則原問題無可行解；若基變量中不再含有非零的人工變量，這表示原問題有解；(3)引入的人工變量個數(shù)越少越好，只要出現(xiàn)單位矩陣作為基陣即可。第4頁,共32頁，2024年2月25日，星期天大M法舉例（1）例解：將原問題化為標準形為：第5頁,共32頁，2024年2月25日，星期天大M法舉例（2）引入的人工變量個數(shù)越少越好引入人工變量y2,y3≥0,由大M法得輔助問題為：其中大M為任意大的正數(shù)得上述輔助問題的單純形初表為：第6頁,共32頁，2024年2月25日，星期天大M法舉例（3）

T(B1)XBb

x1x2x3x4x5y2y3x4y2y3419-z’10M1111000-21-10-1100310001-2M-34M10-M00

T(B2)x4

x2

y3

-z’330211-101-21-10-110660403-31

6M6M-304M+1

03M-4M0人工變量優(yōu)先出基第7頁,共32頁，2024年2月25日，星期天大M法舉例（4）

T(B3)XBb

x1x2x3x4x5y2y3x4x2x1031-z’30001-1/21/2-1/2011/30001/3102/301/2-1/21/600303/2-M-3/2-M+1/2

T(B4)x4

x2

x3

-z’00001-1/21/2-1/25/2-1/2100-1/41/41/43/23/20103/4-3/41/4

-3/2-9/200

0-3/4-M+3/4-M-1/4第8頁,共32頁，2024年2月25日，星期天大M法舉例（5）原線性規(guī)劃問題的最優(yōu)解為因為在單純形表T(B4)中，非基變量檢驗數(shù)均小于等于零，且人工變量均為非基變量，取值為零，故原線性規(guī)劃問題達到最優(yōu)。第9頁,共32頁，2024年2月25日，星期天線性規(guī)劃的二階段法(1)原線性規(guī)劃問題為第一階段:y1，y2，…，ym稱為人工變量構造原(LP)的輔助問題第10頁,共32頁，2024年2月25日，星期天線性規(guī)劃的二階段法(2)原(LP)的輔助問題的標準形式為：輔助問題必有最優(yōu)解第11頁,共32頁，2024年2月25日，星期天線性規(guī)劃的二階段法(初始單純形表1)輔助問題的標準形式的系數(shù)矩陣為：第12頁,共32頁，2024年2月25日，星期天線性規(guī)劃的二階段法(初始單純形表2)用單純形法求解,最終得到輔助問題的最優(yōu)單純形表T(B*)第13頁,共32頁，2024年2月25日，星期天二階段法的計算步驟:第二步若w*＞0,則原線性規(guī)劃無可行解,停止求解,

否則轉第三步.第一步用單純形法求輔助問題的最優(yōu)單純形表T(B*)和最優(yōu)值w*.

第三步

T(B*)中基變量中不含人工變量y,則把T(B*)中人工變量所在列劃去,把檢驗數(shù)行用原規(guī)劃的目標函數(shù)的系數(shù)替代再把基變量的檢驗數(shù)化為0,即得原規(guī)劃的一個可行基的單純形表.再用單純形法迭代,直到終止.否則轉第四步.第四步

w*=0,T(B*)中基變量中含有人工變量yr,若yr所在行的對應的X系數(shù)全為0,則劃去T(B*)中yr所在行和所在的列,轉第三步。否則以某變量xS的系數(shù)

brs

0為軸心項進行換基迭代后轉第三步。

第14頁,共32頁，2024年2月25日，星期天線性規(guī)劃的二階段法舉例（1）例1.用二階段法求解下列(LP)問題

解:化原問題為標準形式則第一階段的輔助問題為第15頁,共32頁，2024年2月25日，星期天線性規(guī)劃的二階段法舉例（1-2）

輔助問題的標準形式為第16頁,共32頁，2024年2月25日，星期天線性規(guī)劃的二階段法舉例（例1-3）則輔助問題的單純表

T(B1)XBb

x1x2x3x4x5x6y2y3x4y2y3643w71111000010-10-101001-100-10111-20-1-100

T(B2)x4

x1

y3

w2012110-10410-10-1010301-100-101301-100-1-10第17頁,共32頁，2024年2月25日，星期天二階段法舉例（例1-4）

T(B2)x4

XBb

x1x2x3x4x5x6y2y3x1

y3

w2012110-10410-10-1010301-100-101301-100-1-10x2

T(B3)x1y3w2012110-10410-10-1010100-3-1-1-111

100-3-1-1-100

因為輔助問題的最優(yōu)值W*=1＞0，則原問題無可行解。第18頁,共32頁，2024年2月25日，星期天線性規(guī)劃的二階段法例2-1例2用二階段法解線性規(guī)劃

解:引進人工變量y2≥0，建立第一階段的輔助問題為

第19頁,共32頁，2024年2月25日，星期天線性規(guī)劃的二階段法舉例（例2-2）

輔助問題的標準形式為

則第一階段的初始單純形表

為T（B1）第20頁,共32頁，2024年2月25日，星期天

XB

b

x1x2x3x4y2

x2y2

231/211/2-2/303/203/401

w

33/203/400例2-3

T(B1)x2x1w1011/4-2/3-1/32101/202/300000

T(B2)-1第21頁,共32頁，2024年2月25日，星期天例2-4得w*=0，且基變量中不含有人工變量，則劃去T(B2)中y2所在列,把檢驗數(shù)行用原問題的目標函數(shù)的系數(shù)替代再把基變量的檢驗數(shù)化為0,即得第二階段的初始單純形表.

T(B2)c-4-300

XB

b

x1x2x3x4y2

x2x1

12011/4-2/3-1/3101/202/3

w

00

000-1-z110011/4-2第22頁,共32頁，2024年2月25日，星期天例2-5則原問題的一個初始單純形表如下x2

x1

12011/4-2/3101/20-z0011/4-2XBbx1x2x3x4

x2

x3

-z110-1/210-2/3420100-11/200-2原問題最優(yōu)解X*=(0,0,4,0)T原問題最優(yōu)值為z*=0第23頁,共32頁，2024年2月25日，星期天例3-1例3用二階段法解下列線性規(guī)劃

解:該問題的標準形式為：第24頁,共32頁，2024年2月25日，星期天線性規(guī)劃的二階段法舉例（例3-2）

輔助問題的標準形式為則第一階段的單純形初表為T（B1）引進人工變量y1,y2,y3，建立第一階段的輔助問題為：第25頁,共32頁，2024年2月25日，星期天例3-3

XB

bx1x2x3x4y1y2y3

y1y2y3

121-1110100110101020-11001

w

4

2

202000

T(B1)y1y2w3/2011/21/2101/23/2011/21/201-1/2302110

T(B2)0x11/210-1/21/2001/2-1第26頁,共32頁，2024年2月25日，星期天例3-4

XB

bx1x2x3x4y1y2y3

y1y2x1

3/23/21/2011/21/2101/2011/21/201-1/210-1/21/2001/2

w

3

021100-1

T(B2)x2y2w3/2011/21/2101/200000-11-1000000

T(B3)0x11/210-1/21/2001/2-2第27頁,共32頁，2024年2月25日，星期天例3-5x2y2w3/2011/21/2101/200000-11-1000000

T(B3)0x11/210-1/21/2001/2-2c2100得w*=0，T(B3)中基變量中含有人工變量y2,且y2所在行的對應的X系數(shù)全為0,則劃去T(B3)中y2所在行，此時，基變量中不再含有人工變量，則劃去T(B3)中人工變量所在列,把檢驗數(shù)行用原問題的標準形式的目標函數(shù)的系數(shù)替代再把基變量的檢驗數(shù)化為0,即得第二階段的初始單純形表.XBbx1x2x3x4y