對(duì)偶單純形法則是從滿足對(duì)偶可行性條件出發(fā)通過(guò)迭代逐步搜索原始問(wèn)題的最優(yōu)解。單純形法是從原始問(wèn)題的一個(gè)可行解通過(guò)迭代轉(zhuǎn)到另一個(gè)可行解，直到檢驗(yàn)數(shù)滿足最優(yōu)性條件為止。在迭代過(guò)程中始終保持基解的對(duì)偶可行性，而使不可行性逐步消失。即知y=cBB-1（稱為單純形算子）為對(duì)偶問(wèn)題的可行解。

對(duì)偶單純形法_對(duì)偶單純形法 -基本內(nèi)容

（Dual SIMPLEX Method）1954年美國(guó)數(shù)學(xué)家C.萊姆基提出對(duì)偶單純形法。單純形法是從原始問(wèn)題的一個(gè)可行解通過(guò)迭代轉(zhuǎn)到另一個(gè)可行解，直到檢驗(yàn)數(shù)滿足最優(yōu)性條件為止。對(duì)偶單純形法則是從滿足對(duì)偶可行性條件出發(fā)通過(guò)迭代逐步搜索原始問(wèn)題的最優(yōu)解。在迭代過(guò)程中始終保持基解的對(duì)偶可行性，而使不可行性逐步消失。設(shè)原始問(wèn)題為min{cx|Ax=b，x≥0}，則其對(duì)偶問(wèn)題（Dual Problem）為 max{yb|yA≤c}。當(dāng)原始問(wèn)題的一個(gè)基解滿足最優(yōu)性條件時(shí),其檢驗(yàn)數(shù)cBB-1A-c≤0。即知y=cBB-1（稱為單純形算子）為對(duì)偶問(wèn)題的可行解。所謂滿足對(duì)偶可行性，即指其檢驗(yàn)數(shù)滿足最優(yōu)性條件。因此在保持對(duì)偶可行性的前提下，一當(dāng)基解成為可行解時(shí)，便也就是最優(yōu)解。

愛(ài)華網(wǎng)本文地址 » http://www.klfzs.com/a/8103320103/56591.html