用對偶單純形法求對偶問題的最優(yōu)解

-PAGE.z.用對偶單純形法求對偶問題的最優(yōu)解摘要：在線性規(guī)劃的應(yīng)用中，人們發(fā)現(xiàn)一個線性規(guī)劃問題往往伴隨著與之配對的另一個線性規(guī)劃問題.將其中一個稱為原問題，另一個稱為對偶問題.對偶理論深刻提醒了原問題與對偶問題的內(nèi)在聯(lián)系.由對偶問題引申出來的對偶解有著重要的經(jīng)濟(jì)意義.本文主要介紹了對偶問題的根本形式以及用對偶單純形法求解對偶問題的最優(yōu)解.關(guān)鍵詞：線性規(guī)劃；對偶問題；對偶單純形UsingDualSimple*MethodToGetTheOptimalSolutionOfTheDualProblemAbstract：Intheapplicationofthelinearprogramming，peoplefindthatalinearprogrammingproblemisoftenaccompaniedbyanotherpairedlinearprogrammingproblem.Oneiscalledoriginalproblem.Anotheriscalledthedualproblem.Dualitytheoryrevealstheinternalrelationsbetweenthedualproblemandtheoriginalproblem.Thesolutionofthedualproblemisofagreateconomicsignificance.Inthispaper，wemainlydiscussthebasicformofthedualproblemandhowtousedualsimple*methodtogettheoptimalsolutionofthedualproblem.Keywords:linearprogramming；dualproblem；dualsimple*method1引言首先我們先引出什么是線性規(guī)劃中的對偶問題.任何一個求極大化的線性規(guī)劃問題都有一個求極小化的線性規(guī)劃問題與之對應(yīng)，反之亦然，如果我們把其中一個叫原問題，則另一個就叫做它的對偶問題，并稱這一對互相聯(lián)系的兩個問題為一對對偶問題.每個線性規(guī)劃都有另一個線性規(guī)劃(對偶問題)與它密切相關(guān)，對偶理論提醒了原問題與對偶問題的內(nèi)在聯(lián)系.下面將討論線性規(guī)劃的對偶問題的根本形式以及用對偶單純形法求最優(yōu)解.在一定條件下，對偶單純形法與原始單純形法相比有著顯著的優(yōu)點.2對偶問題的形式對偶問題的形式主要包括對稱形對偶問題和非對稱性對偶問題.2.1對稱形對偶問題設(shè)原線性規(guī)劃問題為Ma*〔2.1〕則稱以下線性規(guī)劃問題Ma*〔2.2〕為其對偶問題，其中稱其為對偶變量，并稱〔2.1〕和〔2.2〕式為一對對稱型對偶問題.原始對偶問題〔2.1〕和對偶問題〔2.2〕之間的對應(yīng)關(guān)系可以用表2-1表示.表2-1…原始約束MinW對偶約束Ma*Z這個表從橫向看是原始問題，從縱向看使對偶問題.用矩陣符號表示原始問題〔2.1〕和對偶問題〔2.2〕為原問題〔2.3〕對偶問題〔2.4〕其中是一個行向量.2.2非對稱對偶問題線性規(guī)劃有時以非對稱形式出現(xiàn)，則如何從原始問題寫出它的對偶問題，我們從一個具體的例子來說明這種非對稱形式的線性規(guī)劃問題的對偶問題的建立方法.例1寫出以下原始問題的對偶問題解：第一約束不等式等價與下面兩個不等式約束第二個約束不等式照寫第三個不等式變成以分別表示這四個不等式約束對應(yīng)的對偶變量，則對偶問題為令，則上式的對偶問題變?yōu)椋阂话憧梢宰C明，假設(shè)原問題中的*個變量無非負(fù)限制，則對偶問題中的相應(yīng)約束為等式.3對偶單純形法對偶問題求解具有重要的意義，有多種方法解決對偶問題.下面介紹用對偶單純形法來解決線性規(guī)劃的對偶問題.先介紹以下幾個線性規(guī)劃的根本概念：基：是約束條件的系數(shù)矩陣，其秩為.假設(shè)是中階非奇異子矩陣〔即可逆矩陣〕，則稱是線性規(guī)劃問題中的一個基.基向量：基中的一列即稱為一個基向量.基中共有個基向量.非基向量：在中除了基B之外的一列則稱之為基的非基向量.基變量：與基向量相應(yīng)的變量叫基變量，基變量有個.非基變量：與非基向量相應(yīng)的變量叫非基變量，非基變量有個.由線性代數(shù)的知識知道，如果我們在約束方程組系數(shù)矩陣中找到一個基，令這個基的非基變量為零，再求解這個元線性方程組就可得到唯一的解了，這個解我們稱之為線性規(guī)劃的根本解.首先重新回憶一下單純形法的根本思想，其迭代的根本思路是：先找出一個基可行解，判斷其是否為最優(yōu)解，如果不是，則轉(zhuǎn)換到另一更優(yōu)的基可行解，并使目標(biāo)函數(shù)值不斷優(yōu)化，直到找到最優(yōu)解為止.我們可以用另一種思路，使在單純形法每次迭代的根本解都滿足最優(yōu)檢驗，但不一定滿足非負(fù)約束，迭代時使不滿足非負(fù)約束的變量個數(shù)逐步減少.當(dāng)全部基變量都滿足非負(fù)約束條件時，就得到了最優(yōu)解，這種算法就是對偶單純形法.因此，單純形法是從一個可行解通過迭代轉(zhuǎn)到另一個可行解，直到檢驗數(shù)滿足最優(yōu)條件為止.對偶單純形法是從滿足對偶可行性條件出發(fā)通過迭代逐步搜索出最優(yōu)解.在迭代過程中始終保持基解的對偶可行性，而使不可行性逐步消失.現(xiàn)把對偶單純形法的根本步驟總結(jié)如下:第一，把所給的線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)型；第二，找出一個初始正則基，要求對應(yīng)的單純形表中的全部檢驗數(shù)，但"右邊〞列中允許有負(fù)數(shù)；第三，假設(shè)"右邊〞列中各數(shù)均非負(fù)，則已是最優(yōu)基，于是，已求得最優(yōu)解，計算終止.否則轉(zhuǎn)為第四步；第四，換基："右邊〞列中取值最小〔即負(fù)的最多〕的數(shù)所對應(yīng)的變量為出基變量.計算最小比值.最小比值出現(xiàn)在末列，則該列所對應(yīng)的變量即為進(jìn)基變量，換基后得新基，以出基變量的行和進(jìn)基變量列交點處的元素為主元進(jìn)展單純形迭代，再轉(zhuǎn)入第三步.下面用一個例子具體說明用對偶單純形法求線性規(guī)劃問題最優(yōu)解的步驟：例1求解線性規(guī)劃問題min;添加松弛變量以后的標(biāo)準(zhǔn)型min將每個等式兩邊乘以-1，則上述問題轉(zhuǎn)化為min;如果取作為初試基變量，有如下初試單純形表〔表〕表3-1右邊0-3-2-210-50-5-1-201-4-15-5-1100由此可見，兩個基變量均取負(fù)值，所以，所確定的根本解不是基可行解，從而也就不能用單純形法求解.下面我們用一種新的方法對偶單純形法求解此題，并通過例題來說明方法步驟.對偶單純形法的根本思想：是保證檢驗數(shù)行全部非正的條件下，逐步使得"右邊〞一列各數(shù)變成非負(fù).一旦"右邊〞一列各數(shù)均滿足了非負(fù)條件〔即可行性條件〕，則就獲得最優(yōu)解.現(xiàn)在，不是可行基〔稱為正則基〕，為保證上述方法的實現(xiàn)，可按下面的方法確定出基變量和進(jìn)基變量.出基變量確實定可以取任意一個具有負(fù)值的基變量〔一般可取最小的〕為出基變量.在上例中，兩個基變量都取負(fù)值，且最小，故為出基變量.現(xiàn)在考慮出基變量所對應(yīng)的負(fù)所有元素，對每個這樣的元素作比值，令〔3.1〕則為進(jìn)基變量.在表2-4中，基變量所在的行有三個取負(fù)值，其值分別為-3，-2，-2.它們對應(yīng)的檢驗數(shù)分別為-15，-5，-11.于是由此可知，為進(jìn)基變量.主元素為，對表2-1進(jìn)展一次迭代便得表2-2，在表2-2的〔1〕中，基變量所取之值，故為出基變量.又故是進(jìn)基變量；，主元為.對〔1〕再作單純形變換，得表3-1之〔2〕.由于它的"右邊〞已列出全部非負(fù)，故它就是最優(yōu)表.最優(yōu)解為：，，；最優(yōu)值.表3-1右邊〔1〕000〔2〕011000然而在有些問題中，我們很容易找到初始根本解，因此使用對偶單純形法求解線性規(guī)劃問題是有一定條件的，其條件是：(1)單純形表的b列中至少有一個負(fù)數(shù).(2)單純形表中的根本解都滿足最優(yōu)性檢驗.對偶單純形法與原始單純形法相比有兩個顯著的優(yōu)點：(1)初始解可以是不可行解，當(dāng)檢驗數(shù)都非正時，即可進(jìn)展基的變換，這時不需要引入人工變量，因此簡化了計算.(2)對于變量個數(shù)多于約束方程個數(shù)的線性規(guī)劃問題，采用對偶單純形法計算量較少.因此對于變量較少、約束較多的線性規(guī)劃問題，可以先將其轉(zhuǎn)化為對偶問題，然后用對偶單純形法求解.對變量多于約束條件的線性規(guī)劃問題，用對偶單純形法進(jìn)展計算可以減少計算的工作量.因此對變量較少，而約束條件很多的線性規(guī)劃問題，可先將此問題轉(zhuǎn)化為對偶問題，然后用對偶單純形法求解.用對偶單純形法求解線性規(guī)劃問題的標(biāo)準(zhǔn)型，要求初始單純形表檢驗數(shù)行的檢驗數(shù)必須全部非正，假設(shè)不能滿足這一條件，則不能運用對偶單純形法求解.對偶單純形法的局限性主要是，對大多數(shù)線性規(guī)劃問題來說，很難找到一個初始可行基，因此這種方法在求解線性規(guī)劃問題時，很少單獨應(yīng)用.參考文獻(xiàn)：[1]吳祈宗．運籌學(xué)學(xué)習(xí)指導(dǎo)及習(xí)題集[M]．：機(jī)械工業(yè)出版社，2006．[2]孫君曼，馮巧玲，孫慧君，等．線性規(guī)劃中原問題與對偶問題轉(zhuǎn)化方法探討[J]．:工業(yè)學(xué)院學(xué)報〔自然科學(xué)版〕，2001，16(2):44~46．[3]何堅勇．運籌學(xué)根底．：清華大學(xué)出版社，2000．[4]周漢良，范玉妹.數(shù)學(xué)規(guī)劃及其應(yīng)用．：冶金工業(yè)出版社．[5]陳寶林．最優(yōu)化理論與算法(第二版)．：清華大學(xué)出版社，2005．[6]張建中，許紹吉.線性規(guī)劃.：科學(xué)出版社，1999.[7]姚恩瑜，何勇，陳仕平．?dāng)?shù)學(xué)規(guī)劃與組合優(yōu)化．：浙江大學(xué)出版社，2001．[8]盧開澄．組合數(shù)學(xué)算法與分析．清華大學(xué)出版社，1982．[9]Even．Shimon．AlgzithmicCombinatorial．TheMacmillanCompany，NewYork，1973．[10]J．P．Tremblay，R．Manohar．DiscreteMathematicalStructureswithApplicationstoComputerScience，1980．[11]李修睦．圖論．華中工學(xué)院出版社，1982．[12]PranavaRG．Essaysonoptimizationandincentivecontracts[C]．MassachusettsInstituteofTechnology，SloanSchoolofManagement:OperationsResearchCenter，2007:57-65．[13]Schechter，M．ASubgradientDualityTheorem，J．MathAnalAppl．，61(1977)，850-855．[14]Ma*imsSA．Noteonma*imizingasubmodularsetfunctionsubj