哈爾濱工業(yè)大學(xué)運(yùn)籌學(xué)大作業(yè)-對(duì)偶單純形法對(duì)比-資料下載頁(yè)
2025-06-27 23:42本頁(yè)面
【正文】 純形法計(jì)算的。當(dāng)線性規(guī)劃問(wèn)題具備下面條件時(shí)，可以用對(duì)偶單純形法求解：①問(wèn)題標(biāo)準(zhǔn)化后，價(jià)值系數(shù)全非正；②所有約束全是不等式。 六、對(duì)偶單純形法的應(yīng)用，原問(wèn)題是求最小值，并且目標(biāo)函數(shù)各項(xiàng)系數(shù)都不小于零。所以在轉(zhuǎn)化成標(biāo)準(zhǔn)型后各項(xiàng)系數(shù)不大于零，從而以松弛變量為基列出的單純形表滿足檢驗(yàn)數(shù)都不大于零，是其對(duì)偶問(wèn)題的一個(gè)可行解。如果原問(wèn)題的標(biāo)準(zhǔn)形式中各項(xiàng)系數(shù)不都小于零，則不容易找到對(duì)偶問(wèn)題的一個(gè)初始可行解，就不適合使用對(duì)偶單純形法求解。所以對(duì)偶單純形法適用于不易找到原方程的可行解而容易找到其對(duì)偶問(wèn)題的可行解的線性規(guī)劃問(wèn)題。，約束方程的數(shù)量對(duì)單純形法的計(jì)算過(guò)程要遠(yuǎn)遠(yuǎn)大于變量個(gè)數(shù)的影響。如果mn，那么對(duì)偶問(wèn)題有n個(gè)約束方程，而原問(wèn)題有m個(gè)約束方程，所以對(duì)偶問(wèn)題有更少的約束方程數(shù)量，那么通過(guò)對(duì)偶單純形法的運(yùn)用比起直接只用單純形法將會(huì)顯著的減少計(jì)算量。對(duì)偶問(wèn)題可以用來(lái)對(duì)原問(wèn)題的計(jì)劃方案進(jìn)行評(píng)價(jià)。我們可以用一個(gè)對(duì)偶問(wèn)題的可行解和目前原問(wèn)題的計(jì)劃方案進(jìn)行比較，如果兩個(gè)目標(biāo)函數(shù)值相等或比較接近，則可以說(shuō)明原問(wèn)題的計(jì)劃方案已經(jīng)是可以看做最優(yōu)了。七、單純形法和對(duì)偶單純形法的基本思想比較通過(guò)以上的分析可知，對(duì)偶單純形法其實(shí)相當(dāng)于單純形法的一種變形，只不過(guò)在運(yùn)用對(duì)偶單純形法解線性規(guī)劃時(shí)需要將單純形表旋轉(zhuǎn)一下。單純形表中的b列實(shí)際上是對(duì)偶問(wèn)題的非基變量的檢驗(yàn)數(shù), 而原單純形表的檢驗(yàn)數(shù)為對(duì)偶問(wèn)題的基解, 這樣可以理解為通過(guò)旋轉(zhuǎn)90176。運(yùn)用單純形法求解線性規(guī)劃。從求解思路上來(lái)說(shuō)，單純形法是首先保證基解是原問(wèn)題的基可行解（bi不小于零），然后通過(guò)變量的換入換出增大目標(biāo)函數(shù)值，直到其同時(shí)成為對(duì)偶問(wèn)題的可行解，根據(jù)強(qiáng)對(duì)偶性原理，可知這個(gè)解就是最優(yōu)解。而對(duì)偶單純形法則是首先保證基解是對(duì)偶問(wèn)題的可行解（檢驗(yàn)數(shù)都不大于零），然后逐步減小對(duì)偶標(biāo)準(zhǔn)化的目標(biāo)函數(shù)值，使其成為原問(wèn)題的可行解。兩種方法殊途同歸，其本質(zhì)是一樣的。8
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1