對偶單純形法

對偶單純形法第一頁，共三十一頁，編輯于2023年，星期六本節(jié)內(nèi)容安排對偶單純形法的求解思路對偶單純形法的求解步驟第二頁，共三十一頁，編輯于2023年，星期六

對偶單純形法是根據(jù)對偶原理和單純形法的原理而設(shè)計出來求解原LP的一種方法。采用的技術(shù)是在原問題的單純形表格上進(jìn)行對偶處理。注意:對偶單純形法不是求解對偶問題的單純形法。一對偶單純形法的求解思路（一）什么是對偶單純形法第三頁，共三十一頁，編輯于2023年，星期六1單純形法中原問題(max)的最優(yōu)解滿足的條件:

（1）是基本解（2）可行解（XB=B-1b≥0);

（3)檢驗(yàn)數(shù)C－CBB-1A0，-CBB-1≤0

即YAC，Y0即對偶解可行

（二）普通單純形法第四頁，共三十一頁，編輯于2023年，星期六2普通單純形法的求解思路:

從滿足（1），（2）的一個初始基本可行解出發(fā)

(此時原LP問題中，b列保持≥0，對偶的解一般為非可行基解），通過逐步迭代，增大原目標(biāo)函數(shù)值，每一步迭代，都得到一個基本可行解，并且逐步迭代實(shí)現(xiàn)檢驗(yàn)數(shù)行≤0(對偶解可行)。0迭代到（3）得到滿足，即所有檢驗(yàn)數(shù)≤0，此時，原問題的基可行解達(dá)到最優(yōu)時，對偶的基解由不可行達(dá)到可行，得到的這個基可行解也是對偶問題的最優(yōu)解。第五頁，共三十一頁，編輯于2023年，星期六3普通單純型法的求解過程：對原問題的一個基可行解，判別是否所有檢驗(yàn)數(shù)非正

cj-zj0(j=1,…,n)；若是，又基變量中無非零人工變量，即找到問題最優(yōu)解，基變量中含有非零人工變量，則無最優(yōu)解；若否，再迭代，找出相鄰的目標(biāo)函數(shù)值更大的基可行解，并繼續(xù)判別，只要最優(yōu)解存在，就一直迭代下去，直到找出最優(yōu)解為止.第六頁，共三十一頁，編輯于2023年，星期六

1對偶單純形法求解思路：換個角度考慮LP求解過程從滿足（1）（3）的一個非可行基解（檢驗(yàn)數(shù)行保持≤0）出發(fā)，（此時對偶問題的解一般為可行解），通過逐步迭代直至（2）得到滿足，即直到實(shí)現(xiàn)到b列所有的值≥0，原問題的解在迭代過程中從非可行解變成可行解，最終達(dá)到最優(yōu)解，此時，對偶問題也達(dá)到最優(yōu)解。單純形法中原問題的最優(yōu)解滿足的條件:（1）是基本解；（2）可行解（XB=B-1b≥0);（3)檢驗(yàn)數(shù)C－CBB-1A0，-CBB-1≤0

即YAC，Y0即對偶解可行（三）對偶單純形法第七頁，共三十一頁，編輯于2023年，星期六普通單純形法對偶單純形法前提是原問題可行

優(yōu)化條件兩種方法都從原問題的基解出發(fā)前提是對偶可行

優(yōu)化條件2兩種方法的聯(lián)系：YAC，Y0第八頁，共三十一頁，編輯于2023年，星期六原問題基可行解最優(yōu)解判斷對偶問題的可行解對偶問題最優(yōu)解判斷對偶單純形法基本思路普通單純形法基本思路第九頁，共三十一頁，編輯于2023年，星期六3對偶單純形法的使用條件：①原問題的初始基解的檢驗(yàn)數(shù)全部≤0；②b列至少一個元素<0；

4實(shí)施對偶單純形法的基本原則：

在保持對偶可行的前提下進(jìn)行基變換——

每一次迭代過程中取出基變量中的一個負(fù)分量作為換出變量去替換某個非基變量(作為換入變量),

使原始問題的非可行解向可行解靠近。第十頁，共三十一頁，編輯于2023年，星期六

第一步：構(gòu)造初始單位陣，確定原問題（max)的初始基B，使所有檢驗(yàn)數(shù)

Cj-Zj=σj=Cj-CBB-1Pj≤0，即Y=CBB-1

（b列的值）是對偶可行解，建立初始單純形表。第二步：可行性檢驗(yàn)。檢驗(yàn)b列和σj行（即檢查基變量的取值）若bi≥0

（XB=B-1b≥0）,σj≤0,

則原問題得到最優(yōu)解，計算停;

若bi<0,σj≤0,

則用對偶單純形法進(jìn)行換基迭代.

二對偶單純形法的步驟：第十一頁，共三十一頁，編輯于2023年，星期六

第三步

先確定換出變量解答列（b列）中的負(fù)元素對應(yīng)的基變量出基，相應(yīng)的行為主元行。一般選最小的負(fù)元素出基，即若min{(B-1b)i|(B-1b)I<0}=(B–1b)l

則選取xl為換出變量.

檢驗(yàn)第l

行中非基變量xj的系數(shù)αlj,

若所有的αlj≥0，則LP問題無可行解，（下面進(jìn)行說明），此時計算結(jié)束。否則轉(zhuǎn)下步第十二頁，共三十一頁，編輯于2023年，星期六當(dāng)bl<0，而對所有j=1,…,n，有alj0，則原問題無可行解。證明：xl+al,m+1xm+1+…+al,nxn=bl

因alj0(j=m+1,…,n)，又bl<0，故有xl<0，即不可能存在xj0(j=1,…,n)的解，故原問題無可行解，此時對偶問題的目標(biāo)函數(shù)值無界。第十三頁，共三十一頁，編輯于2023年，星期六若有：Min{cj–zj/αlj|αlj<0,xj為非基變量}=ck–zk/αlk則確定xk為換入變量，相應(yīng)的列為主元列，標(biāo)出主元素αlk

,

應(yīng)用矩陣的初等行變換得到新的單純形表。第四步：若對于bl<0,且有alj<0,

則確定換入變量應(yīng)用最小比值原則目的：是在保持下一個對偶問題的基解可行的前提下，減少原始問題的不可行性。下面進(jìn)行說明根據(jù)最小比值原則：第十四頁，共三十一頁，編輯于2023年，星期六alk為主元素xk為進(jìn)基變量［］設(shè)下一個表中的檢驗(yàn)數(shù)為(cj-zj)，則第十五頁，共三十一頁，編輯于2023年，星期六(1)對alj0，因cj－zj0，故，又因主元素alk<0，故有，所以(cj－zj)

0；(2)對alj<0，因，故有(cj－zj)

0；所以，(cj－zj)0(j=1，…，n)則有：第十六頁，共三十一頁，編輯于2023年，星期六

第五步：用換入變量替換換出變量，得到一個新的基，對新的基再檢查是否所有

如果是，得原問題的最優(yōu)解；如果否，回到第一步再重復(fù)計算，直到檢驗(yàn)數(shù)行非正，基列非負(fù)，得到最終表.第十七頁，共三十一頁，編輯于2023年，星期六例6

應(yīng)用對偶單純型法求解下面的線性規(guī)劃問題第十八頁，共三十一頁，編輯于2023年，星期六CBXBbx1x2x3x4x5cj-2-3-400-1-2-110-21-301x4x500-2-3-400cj-zj-3-4min{σj/αlj|αlj<0}x5換出變量x1換入變量0-5/21/21-1/21-1/23/20-1/2x4x10-20-4-10-1-12bx5x4x3x2x1XBCBcj00-4-3-2cj-zjmin{σj/αlj|αlj<0}x2換入變量8/52x4換出變量第十九頁，共三十一頁，編輯于2023年，星期六bx5x4x3x2x1XBCBcj00-4-3-2-2/5-1/57/5011/5-2/5-1/510x1x2-2-3-1/5-8/5-3/500cj-zj11/52/5bi≥0,σj≤0得到最優(yōu)解為：X*=(11/5,2/5,0,0,0）T對偶問題最優(yōu)解為：第二十頁，共三十一頁，編輯于2023年，星期六例:

用對偶單純形法求解下面線性規(guī)劃

解:

構(gòu)造對偶單純形表進(jìn)行迭代，第二十一頁，共三十一頁，編輯于2023年，星期六從最后的表可以看到，B-1b列元素中有-2<0，并且，-2所在行各元素皆非負(fù)，因此，原問題沒有可行解。第二十二頁，共三十一頁，編輯于2023年，星期六原問題可以從非可行解開始（即初始解可以是非可行解），在構(gòu)造初始單位陣時,不需要加人工變量，簡化計算．

對偶單純形法的特點(diǎn)：靈敏度分析和整數(shù)規(guī)劃常借助于對偶單純形法分析.使問題處理簡單.變量多，約束條件少的問題,在迭代過程中計算工作量小,

因此,可以把變量少，約束條件多的LP問題轉(zhuǎn)化成變量多，約束條件少的對偶問題,再用對偶單純形法求解.第二十三頁，共三十一頁，編輯于2023年，星期六

對偶單純形法的局限性:很難找到初始可行基,很少單獨(dú)使用.初始單純形表的檢驗(yàn)數(shù)行很難滿足小于或等于零的要求，即滿足檢驗(yàn)數(shù)行對應(yīng)的對偶問題的解是可行解．第二十四頁，共三十一頁，編輯于2023年，星期六對于原問題為最小化時,選取換出變量的原則不變,選取換入變量時作相應(yīng)改變:

σj≥0

min{σj/αlj|αlj>0,xj為非基變量}=σk/αlk注意：若xl為換出變量，所有αlj≤0，則原問題無可行解。第二十五頁，共三十一頁，編輯于2023年，星期六初始可行基例:

用對偶單純形法求解線性規(guī)劃問題：對偶問題的初始可行基第二十六頁，共三十一頁，編輯于2023年，星期六

換出換出min{σj/αlj|αlj<0}45y2換入變量第二十七頁，共三十一頁，編輯于2023年，星期六第二十八頁，共三十一頁，編輯于2023年，星期六最優(yōu)解第二十九頁，共三十一頁，編輯于2023年，星期六對偶單純形法與原始單純形法內(nèi)在的對應(yīng)關(guān)系原始單純形法對偶單純形法前提條件所有bi≥0所有bi≥0?最優(yōu)性檢驗(yàn)所有所有換入、出基變量的確定先確定換入基變量