1、第一章 線性規(guī)劃與單純形法,第5節(jié) 單純形法的進(jìn)一步討論,線性規(guī)劃的二階段法,目前有兩種方法：大M法和二階段法。,人工變量法,在討論單純形法時(shí)，我們總是假定AXb的系數(shù)矩陣A的秩r(A)=mn,或者已有一個(gè)可行基。但是，在許多問題中，初始可行基是不容易找到的，或者A不滿秩。這樣單純形法就很難進(jìn)行。,所以，我們要探討如何尋找第一個(gè)可行基？,大M法（1）,把原問題化為下列形式：其中M是任意大的正數(shù),大M法（2）,例,大M法（3）,的輔助問題也可表示成,線性規(guī)劃的二階段法(1),原線性規(guī)劃問題為,第一階段:,y1， y2， ym稱為人工變量,構(gòu)造原(LP)的輔助問題,線性規(guī)劃的二階段法(初始單純形表

2、1),輔助問題的系數(shù)矩陣,線性規(guī)劃的二階段法(初始單純形表2),用單純形法求解,最終得到輔助問題的最優(yōu)單純形表T(B*),線性規(guī)劃的二階段法(2),情況1 若最優(yōu)值 W*0,則原線性規(guī)劃無可行解,停止求解.,情況2 若最優(yōu)值 W*=0,則原線性規(guī)劃有基本可行解, 此時(shí)有兩種可能:,(1)最優(yōu)單純形表T(B*)中基變量中不含人工變量y, 則把T(B*)中 人工變量所在列劃去,把檢驗(yàn)數(shù)行用 原規(guī)劃的目標(biāo)函數(shù)的系數(shù)替代再把基變量的檢驗(yàn)數(shù) 化為0,即得原規(guī)劃的一個(gè)可行基的單純形表. 再用 單純形法迭代,直到終止.,(2)最優(yōu)單純形表T(B*)中基變量中含有人工變量y, 此時(shí)又有兩種可能: 設(shè)yr為基變

3、量,線性規(guī)劃的二階段法(3),(ii)yr所在行的對(duì)應(yīng)的X系數(shù)有不為0 ,比如XS的系數(shù) brs0,則強(qiáng)迫 XS入基,yr出基,進(jìn)行換基迭代.,(2)最優(yōu)單純形表T(B*)中基變量中含有人工變量y, 此時(shí)又有兩種可能: 設(shè)yr為基變量,(i)yr所在行的對(duì)應(yīng)的X系數(shù)全為0 ,則表明原規(guī)劃的 第R個(gè)約束條件是 多余的,劃掉yr所在行.,二階段法的計(jì)算步驟:,第二步 若 W*0,則原線性規(guī)劃無可行解,停止求解, 否則轉(zhuǎn)第三步.,第一步 用單純形法求輔助問題的最優(yōu)單純形表T(B*) 和最優(yōu)值W*.,第三步 T(B*)中基變量中不含人工變量y,則把T(B*)中人 工變量所在列劃去,把檢驗(yàn)數(shù)行用原規(guī)劃的

4、目標(biāo)函 數(shù)的系數(shù)替代再把基變量的檢驗(yàn)數(shù)化為0,即得原 規(guī)劃的一個(gè)可行基的單純形表.再用單純形法迭 代,直到終止.否則轉(zhuǎn)第四步.,第四步 W*=0,T(B*)中基變量中含有人工變量yr,若yr所在 行的對(duì)應(yīng)的X系數(shù)全為0 ,則劃去T(B*)中yr所在行 和所在的列,轉(zhuǎn)第三步。否則以某變量XS的系數(shù) brs0為軸心項(xiàng)進(jìn)行換基迭代后轉(zhuǎn)第三步。,Yes,Yes,NO,NO,Yes,NO,二階段法的框圖表示為如下:,開始,w*=0是否成立？,構(gòu)造輔助問題的 初始單純形表,無可行解,單純形法 換基迭代,得到輔助問題的最優(yōu)單純形表,構(gòu)造輔助問題L,輸入標(biāo)準(zhǔn)形式,結(jié)束,基變量中含有y？,劃去基變量所在列可得

5、原問題的單純形表,換基迭代,劃去該Y所在的行和所在的列,強(qiáng)迫X入基,基變量Y所在行X 的系數(shù)是否全為零,線性規(guī)劃的二階段法舉例（1）,例1. 用二階段法求解下列(LP)問題,解:,化原問題為標(biāo)準(zhǔn)形式,則它的輔助問題為,線性規(guī)劃的二階段法舉例（例1-2）,則輔助問題的單純表,T(B1),XB,b,X1 X2 X3 X4 X5 X6 y1 y2 y3,y1 y2 y3,64 3,-w,13,1 1 1 1 0 0 1 0 0 1 0 -1 0 -1 0 0 1 0 0 1 -1 0 0 -1 0 0 1,2 2 -1 1 -1 -1 0 0 0,T(B2),y1,x1,y3,-w,2,0 1 2

6、1 1 0 1 -1 0,4,1 0 -1 0 -1 0 0 1 0,3,0 1 -1 0 0 -1 0 0 1,5,0,2,1,1,1,-1,0,-2,0,二階段法舉例（例1-3）,T(B2),y1,XB,b,X1 X2 X3 X4 X5 X6 y1 y2 y3,x1,y3,-w,2,0 1 2 1 1 0 1 -1 0,4,1 0 -1 0 -1 0 0 1 0,3,0 1 -1 0 0 -1 0 0 1,5,0,2,1,1,1,-1,0,-2,0,x2,T(B3),x1,y3,-w,2,0 1 2 1 1 0 1 -1 0,4,1 0 -1 0 -1 0 0 1 0,1,0 0 -3 -

7、1 -1 -1 -1 1 1,1,0,0,-3,-1,-1,-1,-2,0,0,因?yàn)檩o助問題的最優(yōu)值W=10，則原問題無可行解。,線性規(guī)劃的二階段法 例2-1,例2 用二階段法解 線性規(guī)劃,解:,引進(jìn)人工變量，y1,y2,建立輔助問題,則輔助問題 為,則輔助問題對(duì)人造基的單純形表 為T（B1）,例2-2,T(B1),y1,X1,-w,1,0 1 1/4 -2/3 1 -1/3,2,1 0 1/2 0 0 2/3,1,0,1,1/4,-2/3,0,T(B2),-4/3,例2-3,T(B2),y1,X1,-w,1,0 1 1/4 -2/3 1 -1/3,2,1 0 1/2 0 0 2/3,1,0,

8、1,1/4,-2/3,0,-4/3,XB,b,X1 X2 X3 X4 y1 y2,X2,X1,-w,1,2,0 1 1/4 -2/3 1 0,1 0 1/2 0 0 1,0,0,0,0,0,-1,-1,T(B3),-Z,-4 -3 0 0,-Z,0 -3 2 0,-Z,0 0 11/4 -2,0,8,11,例2-5,則原問題的標(biāo)準(zhǔn)形的一個(gè)初始可行用單純形表如下,X2,X1,1,2,0 1 1/4 -2/3,1 0 1/2 0,-Z,0 0 11/4 -2,X3,X1,-Z,11,4,0 4 1 -8/3,0,1 -2 0 4/3,0,0 -11 0 16/3,X3,X4,-Z,4,0,2 0

9、1 0,3/4 -3/2 0 1,0,-4 -3 0 0,原最優(yōu)解X* =(0,0,4,0)T,最優(yōu)值為Z* =0,例3-1,例3 用二階段法解下 列線性規(guī)劃,解:,引進(jìn)人工變量y1,y2,y3建立輔助問題,例3-2,T(B1),X2,y2,-w,1,-1 1 1 0 1 0 0,1,2 0 -1 1 -1 1 0,2,4,0,-2,2,-2,T(B2),0,y3,1,2 0 -1 1 -1 0 1,0,例3-3,T(B2),X2,X1,-w,3/2,0 1 1/2 1/2 1/2 1/2 0,1/2,1 0 -1/2 1/2 -1/2 1/2 0,0,0,0,0,0,0,T(B3),-2,y3,0,0 0 0 0 0 -1 1,0,-Z,2,1,0,0,0,例3-4,T(B3),-1,T(B4),-Z,0,1,1,-1,-Z,0,0,-5/2,1/2,-3/2,例4-1,用二階段法解下列線性規(guī)劃,解:,引進(jìn)人工變量，y1,y2,y3建立輔助問題,例4-2,T(B1),y1,y2,-w,8/3,-2 2 0 2/3 1 0 2/3,4/3,-2 1 0 1/3 0 1 -2/3,4,-4,3,0,1,0,T(B2),0,X3,4/3,1 0 1 1/3 0 0 1/3,0,