對(duì)偶單純形法

《對(duì)偶單純形法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、一、對(duì)偶單純形法的思路對(duì)偶單純形法不是解對(duì)偶問題的，而是在單純形表上進(jìn)行對(duì)偶運(yùn)算的方法。為了了解對(duì)偶單純形法的實(shí)質(zhì)，我們回顧一下單純形法。單純形法開始于初始基可行解。如果不滿足最優(yōu)性條件，則要轉(zhuǎn)到能使目標(biāo)函數(shù)值得到改善的鄰近頂點(diǎn)上。在這個(gè)轉(zhuǎn)換過程中，存在兩個(gè)原則，一是保持原問題的解仍是可行的，另一個(gè)是要求目標(biāo)函數(shù)值有改善。當(dāng)目標(biāo)函數(shù)值無法改善時(shí)（因退化出現(xiàn)循環(huán)的情況除外），所有的檢驗(yàn)數(shù)都≤0（求極大時(shí)≤0，求極小時(shí)，檢驗(yàn)數(shù)≥0）。“檢驗(yàn)數(shù)≤0”意味著在獲得原問題最優(yōu)解的同時(shí)，也獲得了對(duì)偶問題的一個(gè)可行解。因?yàn)樵瓎栴}與對(duì)偶問題

2、的解都可行，并且目標(biāo)函數(shù)值相同，根據(jù)對(duì)偶理論，這個(gè)對(duì)偶可行解就是對(duì)偶問題的最優(yōu)解。單純形法迭代過程的實(shí)質(zhì)是：在保持原問題可行性的前提下，驅(qū)使對(duì)偶問題從不可行轉(zhuǎn)變?yōu)榭尚械陌l(fā)展歷程。把上述思想移植到對(duì)偶問題上。對(duì)偶單純形法迭代過程的實(shí)質(zhì)是：保持對(duì)偶問題的可行性（只要檢驗(yàn)數(shù)≤0即可），通過改變對(duì)偶問題的可行基，使原問題由不可行變?yōu)榭尚?。根?jù)對(duì)偶理論，這兩個(gè)可行解就是原始和對(duì)偶問題的最優(yōu)解。二、對(duì)偶單純形法的計(jì)算步驟使用對(duì)偶單純形法必須滿足兩個(gè)條件：（1）單純形表中的所有檢驗(yàn)數(shù)必須符合最優(yōu)性要求（即對(duì)偶可行）；（2）右端常數(shù)項(xiàng)列向量

3、必須有負(fù)分量（如果原問題可行，則直接用單純形法）。對(duì)偶單純形法計(jì)算步驟：（1）把線性規(guī)劃問題化為標(biāo)準(zhǔn)形式，找出對(duì)偶問題的初始可行基，列出單純形表。表的格式與第一章的單純形表完全相同。（2）確定換出基的變量。這一點(diǎn)與單純形法正好相反，那里是先確定換入變量。因?yàn)槌?shù)項(xiàng)有負(fù)分量，所以令br=min{bi},第r行對(duì)應(yīng)的基變量xr作為換出變量。（3）確定換入基的變量。這里要注意：單純形法確定換出變量時(shí)用的是換入變量列向量與常數(shù)項(xiàng)列的最小比值；對(duì)偶單純形法確定換入變量時(shí)則用檢驗(yàn)數(shù)行與換出變量所在行的最小比值。1）如果所有的arj≥0，

4、則原問題沒有可行解。停止計(jì)算。2）如果存在arj＜0，則計(jì)算最小比值。??cj?zj??cs?zs求極大為標(biāo)準(zhǔn)形式時(shí)??min?arj?0??（2-22a）j??a??arjrs??zj?cj??zs?cs求極小為標(biāo)準(zhǔn)形式時(shí)??min?arj?0??（2-22b）j??a??arjrs第s列所在的變量xs作為換入變量。(4)選擇a為主元素，把該列向量變?yōu)閱挝涣邢蛄?。rs這里的旋轉(zhuǎn)運(yùn)算和單純形法一樣，主元素處變?yōu)?，其余變?yōu)?即可。（5）重復(fù)步驟（2）—（4），直至原問題變?yōu)榭尚薪鉃橹?。?.4.1用對(duì)偶單純形法求解下列線性規(guī)

5、劃問題。minz=15x1+24x2+5x36x2+x3≥2st.5x1+2x2+x3≥1x1,x2,x3≥0解：把線性規(guī)劃問題化為標(biāo)準(zhǔn)形式。maxz′=－15x1－24x2－x3+0x4+0x56x2+x3－x4=2st.5x1+2x2+x3－x5=1x1,x2,x3,x4,x5≥0在標(biāo)準(zhǔn)形式里，目標(biāo)函數(shù)系數(shù)滿足使用對(duì)偶單純形法的一個(gè)條件，但是，約束條件的右端常數(shù)項(xiàng)非負(fù)，且沒有單位矩陣。為此，把約束方程兩邊都乘以-1，得maxz′=－15x1－24x2－x3+0x4+0x5－6x2－x3+x4=－2st.－5x1－2x2－

6、x3+x5=－1x1,x2,x3,x4,x5≥0以此表達(dá)式列出單純形表并求解。表9cj－15－24－500CBXBbx1x2x3x4x50x4－20[－6]－1100x5－1－5－2－101(cj－zj)或?j-15-24-600根據(jù)對(duì)偶單純形法，首先選擇換出變量：顯然常數(shù)項(xiàng)列最負(fù)的元素是-2，所以第一行的基變量x4作為換出變量。換入變量的確定利用公式（2-22）。第一行與檢驗(yàn)數(shù)行對(duì)應(yīng)分量比值的最小值為：最小比值={—，-24/-6，-6/-1}=4-6是主元素，x是換入變量。2表10cj－15－24－500CBXBbx1x

7、2x3x4x5-24x21/3011/6-1/600x5-1/3－50[-2/3]-1/31(cj－zj)或?j-150-1-40選擇換出變量。顯然負(fù)元素是-1/3，所以第二行的基變量x5作為換出變量。換入變量的確定利用公式（2-22）。第二行與檢驗(yàn)數(shù)行對(duì)應(yīng)分量比值的最小值為：最小比值={-15/-5，-1/（-2/3），-4/（-1/3）}=3/2-2/3是主元素，x是換入變量。3表11cj－15－24－500CBXBbx1x2x3x4x5-24x21/4-5/410-1/41/45x31/215/2011/2-3/2(c

8、j－zj)或?j-15/200-7/2-3/2由于原始，對(duì)偶都已經(jīng)可行，所以，表11對(duì)應(yīng)的解是最優(yōu)解。注意：具有本例題形式的線性規(guī)劃問題在求最優(yōu)解時(shí)，可以不使用人工變量，對(duì)偶單純形法能使求解過程更簡便。返回