線性規(guī)劃的圖解法與單純形解法-展示頁
2024-08-16 17:27本頁面
【正文】 數(shù)看出。 ? 單純形算法必須解決三個(gè)方面的問題： 1. 如何確定初始的基可行解？ 2. 如何進(jìn)行解的最優(yōu)性判別？ 3. 如何尋找改進(jìn)的基可行解？ 12 確定初始的基可行解 ? 標(biāo)準(zhǔn)型的線性規(guī)劃問題 ??????????0m a x1XbxPCXznjjj???????????????100000100001),( 21????? mPPP系數(shù)矩陣中存在一個(gè)單位陣 以單位陣為一初始可行基。 ? 如果某一線性規(guī)劃問題有最優(yōu)解，我們可以按照這樣的思路來求解：先找可行域中的一個(gè)頂點(diǎn)，計(jì)算頂點(diǎn)處的目標(biāo)函數(shù)值，然后判別是否有其它頂點(diǎn)處的目標(biāo)函數(shù)值比這個(gè)頂點(diǎn)處的目標(biāo)函數(shù)值更大，如有，轉(zhuǎn)到新的頂點(diǎn)，重復(fù)上述過程，直到找不到使目標(biāo)函數(shù)值更大的新頂點(diǎn)為止。尋找線性規(guī)劃問題的最優(yōu)解只需比較有限個(gè)頂點(diǎn)處的目標(biāo)函數(shù)值。 ? 用圖解法求解實(shí)際線性規(guī)劃問題，一般按照如下基本步驟： Step1 畫直坐標(biāo)系； Step2 根據(jù)約束條件畫出可行域； Step3 畫過坐標(biāo)原點(diǎn)的目標(biāo)函數(shù)線； Step4 確定目標(biāo)函數(shù)值的增大方向 (目標(biāo)函數(shù)線法線方向 ) Step5 目標(biāo)函數(shù)線沿著增大方向平行移動，與可行域相交且有最大目標(biāo)函數(shù)值的頂點(diǎn)，即為線性規(guī)劃問題的最優(yōu)解 。1 線性規(guī)劃的圖解法與單純形解法 ? 線性規(guī)劃問題的圖解法 ? 線性規(guī)劃單純形解法的原理 ? 線性規(guī)劃單純形解法的計(jì)算步驟 ? 單純形法計(jì)算的矩陣描述 ? 線性規(guī)劃單純形求解的大 M法 ? 線性規(guī)劃單純形求解的兩階段法 ? 線性規(guī)劃單純形求解可能的循環(huán)現(xiàn)象 2 線性規(guī)劃問題的圖解法 ? 圖解法，就是用作圖的方法求解線性規(guī)劃問題。 ? 簡單、直觀的圖解法一般只適用于具有 兩個(gè)決策變量 的線性規(guī)劃問題。 3 x1 x2 O 10 20 30 40 10 20 30 40 (15,10) 最優(yōu)解 X=(15,10) 最優(yōu)值 Z=85 402 21 ?? xx 21 ?? xx0,0402212121??????xxxxxx例 21 43m a x xxZ ??4 2 4 6 x1 x2 2 4 6 最優(yōu)解 X=(3,1) 最優(yōu)值 Z=5 (3,1) ???????????????006346321212121xxxxxxxx、min Z=x1+2x2 例 5 2 4 6 x1 x2 2 4 6 X（ 2） ＝（ 3,1） X（ 1） ＝（ 1,3） ???????????????006346321212121xxxxxxxx、min Z=5x1+5x2 例 有無窮多個(gè)最優(yōu)解 即具有多重解 ,通解為 0≤α≤1 當(dāng) α= Ｘ =(x1,x2)=(1,3)+(3,1)=(2,2) 6 2 4 6 x1 x2 2 4 6 ???????????????006346321212121xxxxxxxx、無界解 (無最優(yōu)解 ) max Z=x1+2x2 例 7 x1 x2 O 10 20 30 40 10 20 30 40 50 50 0,05040221212121????????xxxxxxxx無可行解 即無最優(yōu)解 max Z=10x1+4x2 例 8 由以上例題可知，線性規(guī)劃的解有 4種形式： (例 ) (例 ) (例 ) (例 ) 2情形為有最優(yōu)解 4情形為無最優(yōu)解 9 由圖解法得到的啟示 ? 線性規(guī)劃問題求解的基本依據(jù)是：線性規(guī)劃問題的最優(yōu)解總可在可行域的頂點(diǎn)中尋找。 ? 線性規(guī)劃問題求解時(shí)可能出現(xiàn)四種結(jié)局： 唯一最優(yōu)解 、無窮多個(gè)最優(yōu)解 、 有無界解 、 無解或無可行解 。 10 (1)可行解區(qū)域要畫正確 (2)目標(biāo)函數(shù)增加的方向不能畫錯(cuò) (3)目標(biāo)函數(shù)的直線怎樣平行移動 11 線性規(guī)劃單純形解法的原理 ? 單純形方法的基本思想 從可行域中的一個(gè)基可行解出發(fā)，判別它是否已經(jīng)是最優(yōu)解，如不是，尋找下一個(gè)基可行解，并且同時(shí)努力使目標(biāo)函數(shù)得到改進(jìn)，如此迭代下去，直到找到最優(yōu)解或判定問題無解為止。令非基變量取值為零，便得到一基可行解。目標(biāo)函數(shù) Z=3x1+4x2中 x1的系數(shù)大于零，如果 x1為一正數(shù)，則 Z的值就會增大，同樣若 x2不為零為一正數(shù)，也能使 Z的值增大；因此只要目標(biāo)函數(shù)中非基變量的系數(shù)大于零，那么目標(biāo)函數(shù)就沒有達(dá)到最大值，即沒有找到最優(yōu)解，判別線性規(guī)劃問題是否達(dá)到最優(yōu)解的數(shù)稱為檢驗(yàn)數(shù)，記作 σ j , j=1,2…, n。 最優(yōu)解判斷標(biāo)準(zhǔn) 當(dāng)所有檢驗(yàn)數(shù) σ j≤0（ j=1， … ， n）時(shí)，基本可行解為最優(yōu)解。 檢驗(yàn)數(shù) 目標(biāo)函數(shù)用非基變量表達(dá)時(shí)的變量系數(shù) 16 進(jìn)基列 出基行 bi /ai2， ai20 θi 表 14 (1) XB x1 x2 x3 x4 b x3 2 1 1 0 40 x4 1 3 0 1 30 σ j 3 4 0 0 (2) x3 x2 σ j (3) x1 x2 σ j 基變量 1 10 0 0 1/3 0 1/3 10 5/3 1 1/3 40 5/3 0 4/3 30 1 0 3/5 1/5 18 0 1 1/5 2/5 4 0 0 1 1 將 3化為 1 乘以1/3后得到 30 18 17 最優(yōu)解 X=(18， 4， 0， 0)T，最優(yōu)值 Z=70 O 20 30 10 40 (3,4) X(3)=(18,4) 最優(yōu)解 X=(18,4) 最優(yōu)值 Z=70 402 21 ?? xx 21 ?? xx??????????????0,30340243m a x432142132121xxxxxxxxxxxxZX(1)=(0,0) 20 10 x2 x1 30 0,0402212121??????xxxxxxX(2)=(0,10) 18 單純形表 c j c 1 c 2 … c m c m +1 … c m + k … c n c B X B x 1 x 2 … x m x m +1 … x m + k … x n b θ i c 1 c 2 ? c m x 1 x 2 ? x m 1 0 ? 0 0 1 ? 0 … … … … 0 0 ? 1 a 1 , m +1 a 2 , m +1 ? a m , m +1 … … … a 1 , m + k a 2 , m + k ? a m , m + k … … ?… a 1n a 2n ? a mn b 1 b 2 ? b m θ 1 θ 2 ? θ m ????miijijj acc1? 0 0 … 0 σm +1 … σ m + k … σ n ???miii bcz1 單純形法全過程的計(jì)算 ， 可以用列表的方法計(jì)算更為簡潔 ， 這種表格稱為單純形表 。 ②找出或構(gòu)造一個(gè) m階單位矩陣作為初始可行基，建立初始單純形表。建立新的單純形表，此時(shí)基變量中 xk取代了 xl ⑥以 aik為主元素進(jìn)行迭代，把 xk所對應(yīng)的列向量變?yōu)閱挝涣邢蛄?，即aik變?yōu)?1，同列中其它元素為 0，轉(zhuǎn)第③ 步。
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1