哈爾濱工業(yè)大學(xué)運(yùn)籌學(xué)大作業(yè)-對偶單純形法對比-在線瀏覽
2025-08-14 23:42本頁面
【正文】 實(shí)質(zhì)、原理、流程和適用條件等。將對偶單純形法與單純形法的基本思想進(jìn)行對比分析，從而說明對偶單純形法的優(yōu)點(diǎn)和適用范圍。這個(gè)發(fā)現(xiàn)指出，對于任何一個(gè)線性規(guī)劃問題都具有對應(yīng)的稱為對偶問題的線性規(guī)劃問題。（一）教學(xué)目標(biāo)：通過對偶單純形法的學(xué)習(xí)，加深對對偶問題的理解。二、對偶問題的實(shí)質(zhì)下面是原問題的標(biāo)準(zhǔn)形式以及其對應(yīng)的對偶問題：原問題對偶問題Max Z=j=1ncjxj. j=1naijxj≤bi i=1,2,?,mxj≥0 j=1,2,?,nMin W=j=1mbiyi. j=1naijyi≥cj j=1,2,?,nyi≥0 i=1,2,?,m從而可以發(fā)現(xiàn)如下規(guī)律：。為了理解對偶單純形法為什么能夠解出原方程的最優(yōu)解，我們需要對對偶理論的幾個(gè)基本原理有所了解。如果xj(j=1,?,n)是原問題的可行解，yi(i=1,?,m)是其對偶問題的可行解，且有j=1ncjxj=i=1mbiyi則xj(j=1,?,n)是原問題的最優(yōu)解，yi(i=1,?,m)是其對偶問題的最優(yōu)解。如果原問題有最優(yōu)解，那么其對偶問題也有最優(yōu)解，且有maxz=minw.證明：設(shè)B為原問題式(1)的最優(yōu)基，那么當(dāng)基為B時(shí)的檢驗(yàn)數(shù)為，其中為由基變量的價(jià)值系數(shù)組成的價(jià)值向量。令，那么有，從而是對偶問題式(2)的可行解。由于，而，從而有。，其中原問題的松弛變量對應(yīng)對偶問題的變量，對偶問題的剩余變量對應(yīng)原問題的變量；這些相互對應(yīng)的變量如果在一個(gè)問題中是基變量，則在另一問題中是非基變量；將這對互補(bǔ)的基解分別代入原問題和對偶問題的目標(biāo)函數(shù)有z=w。單純形法的基本思想是保持原問題為可行解的基礎(chǔ)上，通過迭代增大目標(biāo)函數(shù)，當(dāng)其對偶問題也為可行解時(shí)，就達(dá)到了目標(biāo)函數(shù)的最優(yōu)值。故我們可以得到對偶單純形法求解過程如下： ，找到一個(gè)檢驗(yàn)數(shù)都小
高考資料相關(guān)推薦
鄂ICP備17016276號-1