線性規(guī)劃的圖解法與單純形解法(參考版)
2024-08-12 17:27本頁面
【正文】 。 （ 2 ） 應(yīng)用圖解法，對1?a 的一切值，求線性規(guī)劃以a表示的最優(yōu)值。 66 勃蘭特 (Bland)法 1974 年由勃蘭特 ( B l a nd) 提出了一個避免出現(xiàn)循環(huán)現(xiàn)象的簡便規(guī)則： （ 1 ）選取0?σ j 中下標最小的非基變量x k為換入變量，即取m i n ( | 0 )jkj ???； （ 2 ）按? 規(guī)則計算時，若出現(xiàn)兩個和兩個以上的最小比值時，選取下標最小的基變量為換出變量。 ?為防止出現(xiàn)循環(huán)現(xiàn)象，先后有人提出了一些方法。 (2) 當?shù)谝浑A段的最優(yōu)值 w≠0時 ， 則原問題無可行解 。 無界解的判斷 : 某個 λk0且 aik≤０ （ i=1， 2,… ,m） 則線性規(guī)劃具有無界解 退化基本可行解的判斷 :存在某個基變量為零的基本可行解 。 ????????????0,426385m i n21212121xxxxxxxxZ62 【 解 】 第一階段問題為 ???????????????5,2,1,04263m i n54213215?jxxxxxxxxxwj用單純形法計算如下表： 63 Cj 0 0 0 0 1 b CB XB x1 x2 x3 x4 x5 0 1 x3 x5 [3] 1 1 － 2 1 0 0 － 1 0 1 6→ 4 λj － 1↑ 2 0 1 0 0 1 x1 x5 1 0 1/3 － 7/3 1/3 － 1/3 0 － 1 0 1 2 2 λj 0 7/3 1/3 1 0 λj≥0,得到第一階段的最優(yōu)解 X=(2,0,0,0,2)T,最優(yōu)目標值 w=2≠0,x5仍在基變量中 ,從而原問題無可行解。 ???????????????????????012210243423m ax321321321321321xxxxxxxxxxxxxxxZ、57 【 解 】 標準型為 ????????????????????????5,2,1,012210243423m ax32153214321321?jxxxxxxxxxxxxxxxZj在第一 、 三約束方程中加入人工變量 x x7后 ， 第一階段問題為 ?????????????????????????7,2,1,0122102434m i n732153216432176?jxxxxxxxxxxxxxxxxwj用單純形法求解，得到第一階段問題的計算表如下： 58 Cj 0 0 0 0 0 1 1 b CB XB x1 x2 x3 x4 x5 x6 x7 1 0 1 x6 x5 x7 － 4 1 2 3 － 1 － 2 1 2 [1] － 1 0 0 0 1 0 1 0 0 0 0 1 4 10 1→ λj 2 － 1 － 2↑ 1 0 0 0 1 0 0 x6 x5 x3 － 6 － 3 2 [5] 3 － 2 0 0 1 － 1 0 0 0 1 0 1 0 0 3→ 8 1 λj 6 － 5↑ 0 1 0 0 0 0 0 x2 x5 x3 － 6/5 3/5 － 2/5 1 0 0 0 0 1 － 1/5 3/5 － 2/5 0 1 0 3/5 31/5 11/5 λj 0 0 0 0 0 59 最優(yōu)解為 最優(yōu)值 w=0。 第二階段 ，單純形法求解原問題 第一階段計算得到的最終單純形表中除去人工變量，將目標函數(shù)行的系數(shù)，換成原問題的目標函數(shù)后，作為第二階段計算的初始表，繼續(xù)求解。也就是，給原問題加入人工變量，構(gòu)造僅含人工變量的目標函數(shù)，并要求最小化。 但最優(yōu)解中含有人工變量 x5≠0說明這個解是偽最優(yōu)解 ， 是不可行的 ， 因此原問題無可行解 。 ???????????????????????????7,2,1,012210243423m ax732153216432176321?jxxxxxxxxxxxxxxMxMxxxxZj－49 Cj 3 2 － 1 0 0 － M － M b CB XB x1 x2 x3 x4 x5 x6 x7 － M 0 － M x6 x5 x7 － 4 1 2 3 － 1 － 2 1 2 [1] － 1 0 0 0 1 0 1 0 0 0 0 1 4 10 1→ λj 32M 2+M 1+2M↑ － M 0 0 0 － M 0 － 1 x6 x5 x3 － 6 － 3 2 [5] 3 － 2 0 0 1 － 1 0 0 0 1 0 1 0 0 3→ 8 1 λj 56M 5M↑ 0 － M 0 0 2 0 － 1 x2 x5 x3 － 6/5 [3/5] － 2/5 1 0 0 0 0 1 － 1/5 3/5 － 2/5 0 1 0 3/5 31/5→ 11/5 λj 5↑ 0 0 0 0 2 3 － 1 x2 x1 x3 0 1 0 1 0 0 0 0 1 1 1 0 2 5/3 2/3 13 31/3 19/3 λj 0 0 0 － 5 25/3 50 （ 1） 初始表中的檢驗數(shù)有兩種算法 ， 第一種算法是利用第一 、 三約束將 x x7的表達式代入目標涵數(shù)消去 x6和 x7， 得到用非基變量表達的目標函數(shù) ， 其系數(shù)就是檢驗數(shù)；第二種算法是利用公式計算 ， 如 （ 2） M是一個很大的抽象的數(shù) ， 不需要給出具體的數(shù)值 ，可以理解為它能大于給定的任何一個確定數(shù)值； ? ? MMM 232)(10)4()(31 ?????????????最優(yōu)解 X＝（ 31/3， 13， 19/3， 0， 0)T；最優(yōu)值 Z＝ 152/3 注意： 51 【 例 】 求解線性規(guī)劃 ????????????0,426385m i n21212121xxxxxxxxZ52 【 解 】 加入松馳變量 x x4化為標準型 ???????????????4,2,1,0426385m i n42132121?jxxxxxxxxxZj在第二個方程中加入人工變量 x5，目標函數(shù)中加上 M x5一項，得到 ?????????????????5,2,1,0426385m i n5421321521?jxxxxxxxxMxxxZj53 用單純形法計算如下表所示。 ?這種方法我們通常稱其為大 M法。 43 線性規(guī)劃求解的人工變量法 對于如下線性規(guī)劃問題 m a x z =c1 x1+ c2 x2+ …+ cn xn a11 x1+ a12 x2+ …+ a
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1