運籌學-單純形法(編輯修改稿)
2025-09-01 17:04 本頁面
【文章內(nèi)容簡介】 x7 9 0 3 1 0 0 0 1 (第一階段）單純形表 1 σj 2 4 0 0 0 [ ] 3 x2入， x6出 1 0 4 1 [ ] 0 x4 0 x2 1 x7 3 3 0 2 1 1 1 0 σj 6 0 4 0 4 [ ] － x1入， x7出 3 0 1 2 1 1 0 1 1 0 1 6 6 0 4 0 3 3 1 1 [ ] 0 x4 0 x2 0 x1 0 0 0 0 1 1/2 1/2 1/2 σj 0 0 0 0 1 0 1 3 0 1 1/3 0 0 0 1/3 1 1 0 2/3 0 1/2 1/2 1/6 所以：已得最優(yōu)解，且人工變量為非基變量，則可去掉人工變量，得原問題的一個即可行基。 2022/8/28 17 （第二階段）單純形表 2 cj 3 0 1 0 0 CB XB bi x1 x2 x3 x4 x5 θ 0 x4 0 0 0 0 1 1/2 0 x2 3 0 1 1/3 0 0 3 x1 1 1 0 2/3 0 1/2 σj 0 0 3 0 3/2 [ ] 9 3/2 [ ] 0 X4 0 X2 1 x3 5/2 1/2 1 0 0 1/4 0 0 0 0 1 1/2 3/2 3/2 0 1 0 3/4 x3入， x1出 σj 9/2 0 0 0 3/4 所以： X*=(x1,x2,x3)T=(0,5/2, 3/2)T Z*=3/2 2022/8/28 18 單純形法小結 ? 給定 LP問題首先化為標準型，選取或構造一個單位矩陣作為基，求出初始基可行解，并列出初始單純形表。標準化過程按第 7種情況： 取 值 右端項 等式或不等式 極大或極小 新加變量系數(shù) xj無約束 xj ≤ 0 bi 0 ≤ = ≥ minZ xs xa 令 xj = xj′ xj″ xj′ ≥0 xj″ ≥0 令 xj′= xj 約束條件兩端同乘以1 加松弛變量 xs 加入人工變量xa 減去剩余變量 xs 加入人工變量 xa 令 z′= Z minZ =max z′ 0 M 2022/8/28 19 第 5節(jié) 單純形法的進一步討論 人工變量法（大 M法）和兩階段法 約束條件： “ ≤” → 加一個松弛變量 “ ≥” → 減一個剩余變量后，再加一個人工變量 “ ＝ ” → 加一個人工變量 若線性規(guī)劃問題有最優(yōu)解則人工變量必為 0。 2022/8/28 20 ? 目標函數(shù)極小化時解的最優(yōu)性判別； ? 無可行解的判別； ? 無界的判別； ? 無窮多最優(yōu)解的判別； ? 唯一最優(yōu)解的判別 . 三、單純形法計算中的幾個問題 當所有非基變量的 σj≥0時為最優(yōu)解； 最優(yōu)解中人工變量為非 0的基變量時； 存在某個 σk0，且所有的 aik≤0時； 得最優(yōu)解時，有檢驗數(shù)為 0的非基變量； 得最優(yōu)解時，所有非基變量檢驗數(shù)為負； 2022/8/28 21 cj 40 45 25 0 0 CB XB bi x1 x2 x3 x4 x5 θ 0 x4 100 2 3 1 1 0 0 x5 120 3 3 2 0 1 σj 40 45 0 25 100/3 40 [ 3 ] 45 X2 25 x3 80/3 1/3 1 0 2/3 1/3 20 1 0 1 1 1 x2入， x4出 σj 0 0 0 5 因為全 σj ≤ 0,且 σ1=0,則有無窮多最優(yōu)解。 所以：其中一個最優(yōu)解為 X*=(0,80/3,20,0,0) T,Z*=1700 例 1: ???????????????012023310032254540321321321321xxxxxxxxxtsxxxZ,..m ax0 10 …… 思考：無窮多最優(yōu)解的一般形式？ 2022/8/28 22 ?????????????0x,x50xx100x2xs .t .xxm axZ21212121cj 1 1 0 0 CB XB bi x1 x2 x3 x4 θ 0 x3 100 2
環(huán)評公示相關推薦
鄂ICP備17016276號-1