版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
-PAGE.z.用對(duì)偶單純形法求對(duì)偶問(wèn)題的最優(yōu)解摘要:在線(xiàn)性規(guī)劃的應(yīng)用中,人們發(fā)現(xiàn)一個(gè)線(xiàn)性規(guī)劃問(wèn)題往往伴隨著與之配對(duì)的另一個(gè)線(xiàn)性規(guī)劃問(wèn)題.將其中一個(gè)稱(chēng)為原問(wèn)題,另一個(gè)稱(chēng)為對(duì)偶問(wèn)題.對(duì)偶理論深刻提醒了原問(wèn)題與對(duì)偶問(wèn)題的內(nèi)在聯(lián)系.由對(duì)偶問(wèn)題引申出來(lái)的對(duì)偶解有著重要的經(jīng)濟(jì)意義.本文主要介紹了對(duì)偶問(wèn)題的根本形式以及用對(duì)偶單純形法求解對(duì)偶問(wèn)題的最優(yōu)解.關(guān)鍵詞:線(xiàn)性規(guī)劃;對(duì)偶問(wèn)題;對(duì)偶單純形UsingDualSimple*MethodToGetTheOptimalSolutionOfTheDualProblemAbstract:Intheapplicationofthelinearprogramming,peoplefindthatalinearprogrammingproblemisoftenaccompaniedbyanotherpairedlinearprogrammingproblem.Oneiscalledoriginalproblem.Anotheriscalledthedualproblem.Dualitytheoryrevealstheinternalrelationsbetweenthedualproblemandtheoriginalproblem.Thesolutionofthedualproblemisofagreateconomicsignificance.Inthispaper,wemainlydiscussthebasicformofthedualproblemandhowtousedualsimple*methodtogettheoptimalsolutionofthedualproblem.Keywords:linearprogramming;dualproblem;dualsimple*method1引言首先我們先引出什么是線(xiàn)性規(guī)劃中的對(duì)偶問(wèn)題.任何一個(gè)求極大化的線(xiàn)性規(guī)劃問(wèn)題都有一個(gè)求極小化的線(xiàn)性規(guī)劃問(wèn)題與之對(duì)應(yīng),反之亦然,如果我們把其中一個(gè)叫原問(wèn)題,則另一個(gè)就叫做它的對(duì)偶問(wèn)題,并稱(chēng)這一對(duì)互相聯(lián)系的兩個(gè)問(wèn)題為一對(duì)對(duì)偶問(wèn)題.每個(gè)線(xiàn)性規(guī)劃都有另一個(gè)線(xiàn)性規(guī)劃(對(duì)偶問(wèn)題)與它密切相關(guān),對(duì)偶理論提醒了原問(wèn)題與對(duì)偶問(wèn)題的內(nèi)在聯(lián)系.下面將討論線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題的根本形式以及用對(duì)偶單純形法求最優(yōu)解.在一定條件下,對(duì)偶單純形法與原始單純形法相比有著顯著的優(yōu)點(diǎn).2對(duì)偶問(wèn)題的形式對(duì)偶問(wèn)題的形式主要包括對(duì)稱(chēng)形對(duì)偶問(wèn)題和非對(duì)稱(chēng)性對(duì)偶問(wèn)題.2.1對(duì)稱(chēng)形對(duì)偶問(wèn)題設(shè)原線(xiàn)性規(guī)劃問(wèn)題為Ma*〔2.1〕則稱(chēng)以下線(xiàn)性規(guī)劃問(wèn)題Ma*〔2.2〕為其對(duì)偶問(wèn)題,其中稱(chēng)其為對(duì)偶變量,并稱(chēng)〔2.1〕和〔2.2〕式為一對(duì)對(duì)稱(chēng)型對(duì)偶問(wèn)題.原始對(duì)偶問(wèn)題〔2.1〕和對(duì)偶問(wèn)題〔2.2〕之間的對(duì)應(yīng)關(guān)系可以用表2-1表示.表2-1…原始約束MinW對(duì)偶約束Ma*Z這個(gè)表從橫向看是原始問(wèn)題,從縱向看使對(duì)偶問(wèn)題.用矩陣符號(hào)表示原始問(wèn)題〔2.1〕和對(duì)偶問(wèn)題〔2.2〕為原問(wèn)題〔2.3〕對(duì)偶問(wèn)題〔2.4〕其中是一個(gè)行向量.2.2非對(duì)稱(chēng)對(duì)偶問(wèn)題線(xiàn)性規(guī)劃有時(shí)以非對(duì)稱(chēng)形式出現(xiàn),則如何從原始問(wèn)題寫(xiě)出它的對(duì)偶問(wèn)題,我們從一個(gè)具體的例子來(lái)說(shuō)明這種非對(duì)稱(chēng)形式的線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題的建立方法.例1寫(xiě)出以下原始問(wèn)題的對(duì)偶問(wèn)題解:第一約束不等式等價(jià)與下面兩個(gè)不等式約束第二個(gè)約束不等式照寫(xiě)第三個(gè)不等式變成以分別表示這四個(gè)不等式約束對(duì)應(yīng)的對(duì)偶變量,則對(duì)偶問(wèn)題為令,則上式的對(duì)偶問(wèn)題變?yōu)椋阂话憧梢宰C明,假設(shè)原問(wèn)題中的*個(gè)變量無(wú)非負(fù)限制,則對(duì)偶問(wèn)題中的相應(yīng)約束為等式.3對(duì)偶單純形法對(duì)偶問(wèn)題求解具有重要的意義,有多種方法解決對(duì)偶問(wèn)題.下面介紹用對(duì)偶單純形法來(lái)解決線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題.先介紹以下幾個(gè)線(xiàn)性規(guī)劃的根本概念:基:是約束條件的系數(shù)矩陣,其秩為.假設(shè)是中階非奇異子矩陣〔即可逆矩陣〕,則稱(chēng)是線(xiàn)性規(guī)劃問(wèn)題中的一個(gè)基.基向量:基中的一列即稱(chēng)為一個(gè)基向量.基中共有個(gè)基向量.非基向量:在中除了基B之外的一列則稱(chēng)之為基的非基向量.基變量:與基向量相應(yīng)的變量叫基變量,基變量有個(gè).非基變量:與非基向量相應(yīng)的變量叫非基變量,非基變量有個(gè).由線(xiàn)性代數(shù)的知識(shí)知道,如果我們?cè)诩s束方程組系數(shù)矩陣中找到一個(gè)基,令這個(gè)基的非基變量為零,再求解這個(gè)元線(xiàn)性方程組就可得到唯一的解了,這個(gè)解我們稱(chēng)之為線(xiàn)性規(guī)劃的根本解.首先重新回憶一下單純形法的根本思想,其迭代的根本思路是:先找出一個(gè)基可行解,判斷其是否為最優(yōu)解,如果不是,則轉(zhuǎn)換到另一更優(yōu)的基可行解,并使目標(biāo)函數(shù)值不斷優(yōu)化,直到找到最優(yōu)解為止.我們可以用另一種思路,使在單純形法每次迭代的根本解都滿(mǎn)足最優(yōu)檢驗(yàn),但不一定滿(mǎn)足非負(fù)約束,迭代時(shí)使不滿(mǎn)足非負(fù)約束的變量個(gè)數(shù)逐步減少.當(dāng)全部基變量都滿(mǎn)足非負(fù)約束條件時(shí),就得到了最優(yōu)解,這種算法就是對(duì)偶單純形法.因此,單純形法是從一個(gè)可行解通過(guò)迭代轉(zhuǎn)到另一個(gè)可行解,直到檢驗(yàn)數(shù)滿(mǎn)足最優(yōu)條件為止.對(duì)偶單純形法是從滿(mǎn)足對(duì)偶可行性條件出發(fā)通過(guò)迭代逐步搜索出最優(yōu)解.在迭代過(guò)程中始終保持基解的對(duì)偶可行性,而使不可行性逐步消失.現(xiàn)把對(duì)偶單純形法的根本步驟總結(jié)如下:第一,把所給的線(xiàn)性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)型;第二,找出一個(gè)初始正則基,要求對(duì)應(yīng)的單純形表中的全部檢驗(yàn)數(shù),但"右邊〞列中允許有負(fù)數(shù);第三,假設(shè)"右邊〞列中各數(shù)均非負(fù),則已是最優(yōu)基,于是,已求得最優(yōu)解,計(jì)算終止.否則轉(zhuǎn)為第四步;第四,換基:"右邊〞列中取值最小〔即負(fù)的最多〕的數(shù)所對(duì)應(yīng)的變量為出基變量.計(jì)算最小比值.最小比值出現(xiàn)在末列,則該列所對(duì)應(yīng)的變量即為進(jìn)基變量,換基后得新基,以出基變量的行和進(jìn)基變量列交點(diǎn)處的元素為主元進(jìn)展單純形迭代,再轉(zhuǎn)入第三步.下面用一個(gè)例子具體說(shuō)明用對(duì)偶單純形法求線(xiàn)性規(guī)劃問(wèn)題最優(yōu)解的步驟:例1求解線(xiàn)性規(guī)劃問(wèn)題min;添加松弛變量以后的標(biāo)準(zhǔn)型min將每個(gè)等式兩邊乘以-1,則上述問(wèn)題轉(zhuǎn)化為min;如果取作為初試基變量,有如下初試單純形表〔表〕表3-1右邊0-3-2-210-50-5-1-201-4-15-5-1100由此可見(jiàn),兩個(gè)基變量均取負(fù)值,所以,所確定的根本解不是基可行解,從而也就不能用單純形法求解.下面我們用一種新的方法對(duì)偶單純形法求解此題,并通過(guò)例題來(lái)說(shuō)明方法步驟.對(duì)偶單純形法的根本思想:是保證檢驗(yàn)數(shù)行全部非正的條件下,逐步使得"右邊〞一列各數(shù)變成非負(fù).一旦"右邊〞一列各數(shù)均滿(mǎn)足了非負(fù)條件〔即可行性條件〕,則就獲得最優(yōu)解.現(xiàn)在,不是可行基〔稱(chēng)為正則基〕,為保證上述方法的實(shí)現(xiàn),可按下面的方法確定出基變量和進(jìn)基變量.出基變量確實(shí)定可以取任意一個(gè)具有負(fù)值的基變量〔一般可取最小的〕為出基變量.在上例中,兩個(gè)基變量都取負(fù)值,且最小,故為出基變量.現(xiàn)在考慮出基變量所對(duì)應(yīng)的負(fù)所有元素,對(duì)每個(gè)這樣的元素作比值,令〔3.1〕則為進(jìn)基變量.在表2-4中,基變量所在的行有三個(gè)取負(fù)值,其值分別為-3,-2,-2.它們對(duì)應(yīng)的檢驗(yàn)數(shù)分別為-15,-5,-11.于是由此可知,為進(jìn)基變量.主元素為,對(duì)表2-1進(jìn)展一次迭代便得表2-2,在表2-2的〔1〕中,基變量所取之值,故為出基變量.又故是進(jìn)基變量;,主元為.對(duì)〔1〕再作單純形變換,得表3-1之〔2〕.由于它的"右邊〞已列出全部非負(fù),故它就是最優(yōu)表.最優(yōu)解為:,,;最優(yōu)值.表3-1右邊〔1〕000〔2〕011000然而在有些問(wèn)題中,我們很容易找到初始根本解,因此使用對(duì)偶單純形法求解線(xiàn)性規(guī)劃問(wèn)題是有一定條件的,其條件是:(1)單純形表的b列中至少有一個(gè)負(fù)數(shù).(2)單純形表中的根本解都滿(mǎn)足最優(yōu)性檢驗(yàn).對(duì)偶單純形法與原始單純形法相比有兩個(gè)顯著的優(yōu)點(diǎn):(1)初始解可以是不可行解,當(dāng)檢驗(yàn)數(shù)都非正時(shí),即可進(jìn)展基的變換,這時(shí)不需要引入人工變量,因此簡(jiǎn)化了計(jì)算.(2)對(duì)于變量個(gè)數(shù)多于約束方程個(gè)數(shù)的線(xiàn)性規(guī)劃問(wèn)題,采用對(duì)偶單純形法計(jì)算量較少.因此對(duì)于變量較少、約束較多的線(xiàn)性規(guī)劃問(wèn)題,可以先將其轉(zhuǎn)化為對(duì)偶問(wèn)題,然后用對(duì)偶單純形法求解.對(duì)變量多于約束條件的線(xiàn)性規(guī)劃問(wèn)題,用對(duì)偶單純形法進(jìn)展計(jì)算可以減少計(jì)算的工作量.因此對(duì)變量較少,而約束條件很多的線(xiàn)性規(guī)劃問(wèn)題,可先將此問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題,然后用對(duì)偶單純形法求解.用對(duì)偶單純形法求解線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型,要求初始單純形表檢驗(yàn)數(shù)行的檢驗(yàn)數(shù)必須全部非正,假設(shè)不能滿(mǎn)足這一條件,則不能運(yùn)用對(duì)偶單純形法求解.對(duì)偶單純形法的局限性主要是,對(duì)大多數(shù)線(xiàn)性規(guī)劃問(wèn)題來(lái)說(shuō),很難找到一個(gè)初始可行基,因此這種方法在求解線(xiàn)性規(guī)劃問(wèn)題時(shí),很少單獨(dú)應(yīng)用.參考文獻(xiàn):[1]吳祈宗.運(yùn)籌學(xué)學(xué)習(xí)指導(dǎo)及習(xí)題集[M].:機(jī)械工業(yè)出版社,2006.[2]孫君曼,馮巧玲,孫慧君,等.線(xiàn)性規(guī)劃中原問(wèn)題與對(duì)偶問(wèn)題轉(zhuǎn)化方法探討[J].:工業(yè)學(xué)院學(xué)報(bào)〔自然科學(xué)版〕,2001,16(2):44~46.[3]何堅(jiān)勇.運(yùn)籌學(xué)根底.:清華大學(xué)出版社,2000.[4]周漢良,范玉妹.數(shù)學(xué)規(guī)劃及其應(yīng)用.:冶金工業(yè)出版社.[5]陳寶林.最優(yōu)化理論與算法(第二版).:清華大學(xué)出版社,2005.[6]張建中,許紹吉.線(xiàn)性規(guī)劃.:科學(xué)出版社,1999.[7]姚恩瑜,何勇,陳仕平.?dāng)?shù)學(xué)規(guī)劃與組合優(yōu)化.:浙江大學(xué)出版社,2001.[8]盧開(kāi)澄.組合數(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
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 山大網(wǎng)絡(luò)內(nèi)科護(hù)理學(xué)A
- 2022-2027年中國(guó)腫瘤消融設(shè)備行業(yè)市場(chǎng)全景評(píng)估及發(fā)展戰(zhàn)略研究報(bào)告
- 濱州低溫液態(tài)儲(chǔ)氫裝備項(xiàng)目投資分析報(bào)告
- 印楝水分散粒劑行業(yè)深度研究報(bào)告
- 移動(dòng)社交廣告行業(yè)市場(chǎng)深度分析及發(fā)展前景預(yù)測(cè)報(bào)告
- 答辯之道全面解析
- 巧用文章題記
- 巧手靈心之口腔醫(yī)學(xué)院第三屆手工技能大賽的策劃書(shū)
- 巧妙構(gòu)造新函數(shù)解決數(shù)學(xué)問(wèn)題
- 高聚物改性瀝青防水卷材生產(chǎn)建設(shè)項(xiàng)目節(jié)能評(píng)估報(bào)告(節(jié)能專(zhuān))
- 《社會(huì)工作的理論》課件
- 2021電力建設(shè)項(xiàng)目工程總承包管理規(guī)范
- 2024年茂名市高三第一次綜合測(cè)試(一模)化學(xué)試卷(含答案)
- (常州卷)江蘇省常州市2023-2024學(xué)年五年級(jí)上學(xué)期期末考試質(zhì)量調(diào)研數(shù)學(xué)試卷一(蘇教版)
- 教練式溝通培訓(xùn)課件
- 醫(yī)養(yǎng)結(jié)合養(yǎng)老院(養(yǎng)老中心)項(xiàng)目可行性報(bào)告
- 初三語(yǔ)文總復(fù)習(xí)全程計(jì)劃表
- 電子技術(shù)基礎(chǔ)與技能-機(jī)工教案第九章教案555集成定時(shí)器介紹
- 污水處理運(yùn)行質(zhì)量保證措施
- 國(guó)家食源性疾病監(jiān)測(cè)工作標(biāo)準(zhǔn)手冊(cè)
- 食材供貨及質(zhì)量保障措施方案
評(píng)論
0/150
提交評(píng)論