【文章內(nèi)容簡介】 6y1+3y2+5y3y5=10 yi≥0(i=1,2,…,5) 40 cj 4 10 0 0 0 CB XB b x1 x2 x3 x4 x5 θ 0 x3 5 3 6 1 0 0 0 x4 2 1 3 0 1 0 0 x5 4 2 5 0 0 1 cjzj 4 10 0 0 0 初始單純形表為： 此時對偶問題的解為 Y＝（ 0， 0， 0，－ 4，－ 10）代入 Minw=5y1+2y2+4y3 . 3y1+ y2+2y3y4=4 6y1+3y2+5y3y5=10 yi≥0(i=1,2,…,5) 不是對偶問題的可行解 41 cj 4 10 0 0 0 CB XB b x1 x2 x3 x4 x5 θ 0 x3 5 3 6 1 0 0 5/6 0 x4 2 1 3 0 1 0 2/3 0 x5 4 2 5 0 0 1 4/5 cjzj 4 10 0 0 0 初始單純形表為： 此時對偶問題的解為 Y＝（ 0， 0， 0，－ 4，－ 10）代入 Minw=5y1+2y2+4y3 . 3y1+ y2+2y3y4=4 6y1+3y2+5y3y5=10 yi≥0(i=1,2,…,5) 不是對偶問題的可行解 42 對原問題進(jìn)行迭代得： cj 4 10 0 0 0 CB XB b x1 x2 x3 x4 x5 θ 0 x3 1 1 0 1 2 0 10 x2 2/3 1/3 1 0 1/3 0 0 x5 2/3 1/3 0 0 5/3 1 cjzj 2/3 0 0 10/3 0 此時對偶問題的解為 Y＝（ 0， 10/3， 0， 2/3， 0）代入 Minw=5y1+2y2+4y3 . 3y1+ y2+2y3y4=4 6y1+3y2+5y3y5=10 yi≥0(i=1,2,…,5) 不是對偶問題的可行解 43 對原問題進(jìn)行迭代得： cj 4 10 0 0 0 CB XB b x1 x2 x3 x4 x5 θ 0 x3 1 1 0 1 2 0 1 10 x2 2/3 1/3 1 0 1/3 0 2 0 x5 2/3 1/3 0 0 5/3 1 2 cjzj 2/3 0 0 10/3 0 此時對偶問題的解為 Y ＝（ 0， 10/3， 0， 2/3， 0 ）代入 Minw=5y1+2y2+4y3 . 3y1+ y2+2y3y4=4 6y1+3y2+5y3y5=10 yi≥0(i=1,2,…,5) 不是對偶問題的可行解 44 對原問題進(jìn)行迭代得： cj 4 10 0 0 0 CB XB b x1 x2 x3 x4 x5 θ 4 x1 1 1 0 1 2 0 10 x2 1/3 0 1 1/3 1 0 0 x5 1/3 0 0 1/3 1 1 cjzj 0 0 2/3 2 0 此時對偶問題的解為 Y＝（ 2/3， 2， 0， 0， 0）代入 Minw=5y1+2y2+4y3 . 3y1+ y2+2y3y4=4 6y1+3y2+5y3y5=10 yi≥0(i=1,2,…,5) 是對偶問題的可行解 45 單純形法求解的過程，從對偶的觀點(diǎn)來看，是在始終保持原始可行解的條件下，不斷改進(jìn)對偶可行性的過程。一個從對偶不可行的解，經(jīng)過幾次疊代，逐步向?qū)ε伎尚薪饪繑n，一旦得到的解既是原始可行的，又是對偶可行的，這個解就分別是原始問題和對偶問題的最優(yōu)解。 46 第 6節(jié) 對偶單純形法 對于對偶單純形法剛好和單純形法的思路相反，就是在始終保持對偶問題可行的條件下，不斷改進(jìn)原問題可行性的過程。一個從原問題不可行的解，經(jīng)過幾次疊代，逐步向原問題可行解靠攏，一旦得到的解既是原始可行的，又是對偶可行的，這個解就分別是原始問題和對偶問題的最優(yōu)解。 47 步驟： 一般設(shè)松弛變量為初時基可行解 若所有的基變量值均 ≥0，則此解為線性規(guī)劃問題的最優(yōu)解，若存在基變量的值 ≤0，則問題還沒有達(dá)到最優(yōu)解，需要進(jìn)行改進(jìn)。 選擇換出變量 min{ bi’/ bi≤0}假設(shè)選取 xk為換出變量 選擇換入變量 θ＝ min{(cjzj)arj|arj＜ 0,cjzj＜ 0}則假設(shè)選取 xl為換出變量 。使得 alk＝ 1，其余 aik為 0 48 Minw=5y1+2y2+4y3 . 3y1+ y2+2y3≥4 6y1+3y2+5y3≥10 y1,y2,y3≥0 舉例： Maxw’=5y12y24y3 . 3y1 y22y3≤4 6y13y25y3≤10 y1,y2,y3≥0 Maxw’=5y12y24y3 . 3y1 y22y3+y4=4 6y13y25y3+y5=10 yi≥0(i=1,2,…,5) 49 cj 5 2 4 0 0 CB XB b y1 y2 y3 y4 y5 θ 0 y4 4 3 1 2 1 0 0 y5 10 6 3 5 0 1 cjzj 5 2 4 0 0 50 cj 5 2 4 0 0 CB XB b y1 y2 y3 y4 y5 θ 0 y4 4 3 1 2 1 0 0 y5 10 6 3 5 0 1 cjzj 5 2 4 0 0 51 cj 5 2 4 0 0 CB XB b y1 y2 y3 y4 y5 θ 0 y4 4 3 1 2 1 0 0 y5 10 6 3 5 0 1 5/6 2/3 4/5 cjzj 5 2 4 0 0 52 cj 5 2 4 0 0 CB XB b y1 y2 y3 y4 y5 θ 0 y4 4 3 1 2 1 0 0 y5 10 6 3 5 0 1 5/6 2/3 4/5 cjzj 5 2 4 0 0 2 y2 10/3 2 1 5/3 0 1/3 53 cj 5 2 4 0 0 CB XB b y1 y2 y3 y4 y5 θ 0 y4 4 3 1 2 1 0 0 y5 10 6 3 5 0 1 5/6 2/3 4/5 cjzj 5 2 4 0 0 0 y4 2/3 1 0 1/3 1 1/3 2 y2 10/3 2 1 5/3 0 1/3 54 cj 5 2 4 0 0 CB XB b y1 y2 y3 y4 y5 θ 0 y4 4 3 1 2 1 0 0 y5 10 6 3 5 0 1 5/6 2/3 4/5 cjzj 5 2 4 0 0 0 y4 2/3 1 0 1/3 1 1/3 2 y2 10/3 2 1 5/3 0 1/3 cjzj 1 0 2/3 0 2/3 55 cj 5 2 4 0 0 CB XB b y1 y2 y3 y4 y5 θ 0 y4 4 3 1 2 1 0 0 y5 10 6 3 5 0 1 5/6 2/3 4/5 cjzj 5 2 4 0 0 0 y4 2/3 1 0 1/3 1 1/3 1 2 2 2 y2 10/3 2 1 5/3 0 1/3 cjzj 1 0 2/3 0 2/3 56 cj 5 2 4 0 0 CB XB b y1 y2 y3 y4 y5 θ 0 y4 4 3 1 2 1 0 0 y5 10 6 3 5 0 1 5/6 2/3 4/5 cjzj 5 2 4 0 0 0 y4 2/3 1 0 1/3 1 1/3 1 2 2 2 y2 10/3 2 1 5/3 0 1/3 cjzj 1 0 2/3 0 2/3 5 y1 2/3 1 0 1/3 1 1/3 57 cj 5 2 4 0 0 CB XB b y1 y2 y3 y4 y5 θ 0 y4 4 3 1 2 1 0 0 y5 10 6 3 5 0 1 5/6 2/3 4/5 cjzj 5 2 4 0 0 0 y4 2/3 1 0 1/3 1 1/3 1 2 2 2 y2 10/3 2 1 5/3 0 1/3 cjzj 1 0 2/3 0 2/3 5 y1 2/3 1 0 1/3 1 1/3 2 y2 2 0 1 1 2 1 58 cj 5 2 4 0 0 CB XB b y1 y2 y3 y4 y5 θ 0 y4 4 3 1 2 1 0 0 y5 10 6 3 5 0 1 5/6 2/3 4/5 cjzj 5 2 4 0 0 0 y4 2/3 1 0 1/3 1 1/3 1 2 2 2 y2 10/3 2 1 5/3 0 1/3 cjzj 1 0 2/3 0 2/3 5 y1 2/3 1 0 1/3 1 1/3 2 y2 2 0 1 1 2 1 cjzj 0 0 1/3 1 1/3 此時對偶問題和原問題都達(dá)到可行，所以均達(dá)到了最優(yōu)解 Y＝（ 2/,0,0,0) W’=22/3 W=22/3 59 Minw=2x1+3x2+4x3 . x1+2x2+ x3≥3 2x1 x2+3x3≥4 x1,x2,x3≥0 練習(xí) :用對偶單純形法求解并求出對偶變量的最優(yōu)解 Maxw’=2x13x24x3 . x1 2x2x3≤3 2x1 +x23x3≤4 x1,x2,x3≥0 Maxw’=2x13x24x3 . x12x2x3+x4=3 2x1 +x23x3 +x5=4 xi≥0(i=1,2,…,5) Maxz=3y1+4y2 . y1+2y2≤2 2y1 y2≤3 y1+3y2≤4 y1,y2≥0 對偶問題為 60 cj 2 3 4 0 0 CB XB b x1 x2 x3 x4 x5 θ 0 x4 3 1 2 1 1 0 0 x5 4 2 1 3 0 1 1 － 4/3 cjzj 2 3 4 0 0 0 x4 1 0 5/2 1/3 1 1/2 8/5 3 2 2 x1 2 1 1/2 2/3 0 1/2 cjzj 0 4 1 0 1 3 x2 2/5 1 0 1/5 2/5 1/5 2 x1 11/5 0 1 7/5 1/5 2/5 cjzj 0 0 3/5 8/5 1/5 此時對偶問題和原問題都達(dá)到可行， 所以均達(dá)到了最優(yōu)解 Y＝（ 11/,0,0,0) W’=28/5 W=28/5 61 Maxz=3y1+4y2 . y1+2y2≤2 2y1 y2≤3 y1+3y2≤4 y1,y2≥0 Maxz=3y1+2y2 . y1+2y2+y3＝ 2 2y1 y2+y4＝ 3 y1+3y2+y5＝ 4 yi≥0 cj 2 3 4 0 0 3 x2 2/5 1 0 1/5 2/5 1/5 2 x1 11/5 0 1 7/5 1/5 2/5 cjzj 0 0 3/5 8/5 1/5 y3 y4 y5 y1 y2 62 對偶單純形法的特點(diǎn)： ? 當(dāng)約束條件為 “ ≥” 時，不需要引入人工變量，從而使計算更為簡便。 ? 用對偶單純形法求解時，目標(biāo)函數(shù)必須是求極大化的。 63 Maxz=3x14x2 . x1+2x2≥2 3x1+ x2≥4 x1 x2≤1 x1+ x2≤3 x1,x2≥0 Maxz=3x14x2 . x12x2≤2 3x1 x2≤4