管理運(yùn)籌學(xué)演示線性與單純形

34x1=16484Q4Q1Q2(4,2)x1x24x2

=12x1+2x2=8o.建立坐標(biāo)系,繪制約束條件.

確定可行域.

繪制和平移目標(biāo)函數(shù)等值線,確定最優(yōu)解、最優(yōu)值Q3可行域C步驟:線性規(guī)劃圖解法X*=(4,2)TZ*=144o34x1=164Q4Q1Q2(4,2)x1x24x2

=12x1+2x2=8Q3(2,3)可行域82x1+4x2=zC線性規(guī)劃求解的幾種結(jié)果

(無窮多解或多重解)－2x1+x2=44ox2x1x1－x2=22可行域無界x1+x2=zc目標(biāo)值

z趨于無窮大線性規(guī)劃求解的幾種結(jié)果(無界解或無有限最優(yōu)解)目標(biāo)值

z趨于無窮大目標(biāo)值

z趨于無窮大目標(biāo)值

z趨于無窮大目標(biāo)值

z趨于無窮大1466ox2線性規(guī)劃求解的幾種結(jié)果(無可行解)x1x1+2x2=142x1+2x2=12可行域是空集7可行域是空集可行域是空集可行域是空集可行域是空集可行域是空集單純形表結(jié)構(gòu)例1：用單純形法求線性規(guī)劃問題：解：引人松弛變量、和，將上述線性規(guī)劃模型化為標(biāo)準(zhǔn)形式。

松弛變量、和前的系數(shù)列向量構(gòu)成單位陣，作為初始可行基。43000000000040032320000121008161240010000140031601001/44001011010-1/231010-1/201001/4800-41222230004322412-92000-3/4200-201/4111-130233000最優(yōu)解:最優(yōu)值:2最優(yōu)解:最優(yōu)值:最優(yōu)解:最優(yōu)值:最優(yōu)解:最優(yōu)值:最優(yōu)解:最優(yōu)值:2300041001/40400-21/21011/2-1/8020300-1.5-1/80-14例2:用大M法求線性規(guī)劃模型:解：為構(gòu)造一個初始可行基，引入松弛變量、剩余變量和人工變量和，并在目標(biāo)函數(shù)中給人工變量加上“＋M”，變量、、和前的單位向量構(gòu)成單位陣，可作為初始可行基。由于目標(biāo)函數(shù)為求最小化，最優(yōu)判別條件為。-31100M0MMM111-2110003-4120-1101-2010001-3+6M1-3M0M001-M0113/21100[

]01M10113-20100-10100-11-2-2010001-11-M00M03-M001100[

]01112113001-22-5000-11-2-2010001-10001M-1M+10140[

]-311419001/3-2/32/3-5/3000-11-20012/3-4/34/3-7/31100001/3M-1/3M-2/32最優(yōu)解:最優(yōu)值:-31100MM最優(yōu)解:最優(yōu)值:最優(yōu)解:最優(yōu)值:最優(yōu)解:最優(yōu)值:最優(yōu)解:最優(yōu)值:最優(yōu)解:最優(yōu)值:例3:用兩階段法求線性規(guī)劃模型:解:

兩階段是將整個問題的求解過程分為兩個階段來處理：第一階段：構(gòu)造一個僅含有人工變量的輔助線性規(guī)劃問題，并求解和判斷原線性規(guī)劃是否存在基可行解。如果w=0，原問題存在基可行解，可以進(jìn)行第二階段計算；否則，應(yīng)停止計算。輔助線性規(guī)劃的構(gòu)成：目標(biāo)函數(shù)取所有的人工變量之和，并求最小化；約束條件仍為原問題的約束條件，并以人工變量形成的單位陣作為可行基。0000010111111-2110003-4120-1101-20100016-30100-10113/21100[

]00110113-20100-10100-11-2-20100010-100103001100[

]01112113001-22-5000-11-2-2010001000001114-31100011001-100-31112113001-2000-1-2010001401/31/304191001/3-2/3000-10012/3-4/3010[

]第二階段：在第一階段的最終表中，去掉人工變量，并將目標(biāo)函數(shù)系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù)，繼續(xù)迭代。在第一階段最優(yōu)表中，w=0，人工變量從基變量中換出，得到原問題的一個可行基和基可行解X（0〕=(0,1,1,12,0)T，可轉(zhuǎn)入第二階段：434x2

=12Q2(4,2)84x1=164Q1(4,0)x1+2x2=8圖解法與單純形法的聯(lián)系可行域可行域666x1x2o6666666單純形法C對偶單純形法例：用對偶單純形法求解解：建立該問題的初始單純形表，先將其化為標(biāo)準(zhǔn)形式，并找出對偶問題的初始可行基；-2-3-4-3-40000-1-2-110-21-301cj-2-3-400-4-2-21-3-3-4[]解：建立該問題的初始單純形表，先將其化為標(biāo)準(zhǔn)形式，并找出對偶問題的初始可行基；解：建立該問題的初始單純形表，先將其化為標(biāo)準(zhǔn)形式，并找出對偶問題的初始可行基；0-20-1/21-1/23/221-1/20-5/21/2-10-10-4-1-1-4-5/2-11/2-1-1/2-5/2[-5/2]-3-22/501-1/5-2/51/511/5107/5-1/5-2/5-8/5-1/500-3/52/511/5原問題的最優(yōu)解