大家好，小編來(lái)為大家解答對(duì)偶單純形法這個(gè)問(wèn)題，對(duì)偶單純形法解最大化線(xiàn)性規(guī)劃問(wèn)題時(shí)很多人還不知道，現(xiàn)在讓我們一起來(lái)看看吧！
對(duì)偶單純形法的基本思想：從對(duì)偶問(wèn)題出發(fā)，先設(shè)法找出一個(gè)基本可行解，并由此開(kāi)始逐次施行從一個(gè)基本可行解到另外一個(gè)基本可行解的轉(zhuǎn)換，這樣的轉(zhuǎn)換將使原始問(wèn)題的基本解由不可行變?yōu)榭尚?，從而求得原始?wèn)題的最優(yōu)解。
單純形法是是保證b=0，通過(guò)轉(zhuǎn)軸，使得檢驗(yàn)數(shù)r=0來(lái)求得最優(yōu)解，而使用對(duì)偶單純形法的前提是r=0，通過(guò)轉(zhuǎn)軸，使得達(dá)到b=0。
再看看別人怎么說(shuō)的。
對(duì)偶單純形法 1954年美國(guó)數(shù)學(xué)家C.萊姆基提出對(duì)偶單純形法。單純形法是從原始問(wèn)題的一個(gè)可行解通過(guò)迭代轉(zhuǎn)到另一個(gè)可行解，直到檢驗(yàn)數(shù)滿(mǎn)足最優(yōu)性條件為止。對(duì)偶單純形法則是從滿(mǎn)足對(duì)偶可行性條件出發(fā)通過(guò)迭代逐步搜索原始問(wèn)題的最優(yōu)解。在迭代過(guò)程中始終保持基解的對(duì)偶可行性，而使不可行性逐步消失。設(shè)原始問(wèn)題為min{cx|Ax=b，x≥0}，則其對(duì)偶問(wèn)題為max{yb|yA≤c}。當(dāng)原始問(wèn)題的一個(gè)基解滿(mǎn)足最優(yōu)性條件時(shí),其檢驗(yàn)數(shù)cBB-1A-c≤0。即知y＝cBB-1（稱(chēng)為單純形算子）為對(duì)偶問(wèn)題的可行解。所謂滿(mǎn)足對(duì)偶可行性，即指其檢驗(yàn)數(shù)滿(mǎn)足最優(yōu)性條件。因此在保持對(duì)偶可行性的前提下，一當(dāng)基解成為可行解時(shí)，便也就是最優(yōu)解。
可以不過(guò)要注意的是兩種***都有好和不好權(quán)你交替的時(shí)候注意取舍
在求解常數(shù)項(xiàng)小于零的線(xiàn)性規(guī)劃問(wèn)題時(shí)，使用對(duì)偶單純形法，可以把原始問(wèn)題的常數(shù)項(xiàng)視為對(duì)偶問(wèn)題的檢驗(yàn)數(shù)，原始問(wèn)題的檢驗(yàn)數(shù)視為對(duì)偶問(wèn)題的常數(shù)項(xiàng)。使用對(duì)偶單純形法，在計(jì)算過(guò)程中每一步都保證了檢驗(yàn)系數(shù)一定大于零。所以不需要再使用單純形法計(jì)算。
因?yàn)樵趯?duì)偶問(wèn)題的約束方程里添加的是松弛變量，松弛變量的系數(shù)矩陣都是負(fù)數(shù)，不能構(gòu)成單位矩陣。如果用人工變量法是可以解決這個(gè)問(wèn)題的，但是太麻煩。兩端乘以-1，可以化為單位陣，很簡(jiǎn)單。
擴(kuò)展資料：
對(duì)偶單純形法的優(yōu)點(diǎn)：不需要人工變量；
當(dāng)變量多于約束時(shí)，用對(duì)偶單純形法可減少迭代次數(shù)；
在靈敏度分析中，有時(shí)需要用對(duì)偶單純形法處理簡(jiǎn)化。
對(duì)偶單純形法缺點(diǎn)：在初始單純形表中對(duì)偶問(wèn)題是基可行解，這點(diǎn)對(duì)多數(shù)線(xiàn)性規(guī)劃問(wèn)題很難做到。因此，對(duì)偶單純形法一般不單獨(dú)使用。
所謂滿(mǎn)足對(duì)偶可行性，即指其檢驗(yàn)數(shù)滿(mǎn)足最優(yōu)性條件。只要保持檢驗(yàn)數(shù)滿(mǎn)足最優(yōu)性條件前提下，一旦基解成為可行解時(shí)，對(duì)偶問(wèn)題和原問(wèn)題均可行，由強(qiáng)對(duì)偶性證明，二者均有最優(yōu)解。
參考資料來(lái)源：百度百科-對(duì)偶單純形法
單純形法是求解線(xiàn)性規(guī)劃問(wèn)題的主要***，而對(duì)偶單純形***是將單純形***應(yīng)用于對(duì)偶問(wèn)題的計(jì)算，對(duì)偶單純性***則提高了對(duì)求解線(xiàn)性規(guī)劃問(wèn)題的效率。
初始基解可以是非可行解，當(dāng)檢驗(yàn)數(shù)都為負(fù)值時(shí)，就可以進(jìn)行基的變換，不需加入人工變量，從而簡(jiǎn)化計(jì)算。
對(duì)于變量多于約束條件的線(xiàn)性規(guī)劃問(wèn)題，用對(duì)偶單純形法可以減少計(jì)算量，在靈敏度分析及求解整數(shù)規(guī)劃的割平面法中，有時(shí)適宜用對(duì)偶規(guī)劃單純形法。
文章到此結(jié)束，希望可以幫助到大家。
