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