運(yùn)籌學(xué)對(duì)偶單純形法

關(guān)于運(yùn)籌學(xué)對(duì)偶單純形法方法：設(shè)原問題maxz=CXAX=bX≥0

設(shè)B是一個(gè)基，令B=(P1,P2,…,Pm)，它對(duì)應(yīng)的變量為

XB=(

x1,x2,…,xm)

當(dāng)非基變量都為零時(shí)，可以得到XB=B-1b。若在B-1b中至少有一個(gè)負(fù)分量，設(shè)(B-1b)i<0,并且在單純形表的檢驗(yàn)數(shù)行中的檢驗(yàn)數(shù)都為非正，即對(duì)偶問題保持可行解，它的各分量是1、對(duì)應(yīng)基變量x1，x2，…

，xm的檢驗(yàn)數(shù)是

σi=ci–zi=ci-CBB-1Pi=0，i=1,2,…,m2、對(duì)應(yīng)非基變量xm+1，…

，xn的檢驗(yàn)數(shù)是

σj=cj–zj=cj-CBB-1Pj

0，j=m+1,…,n第2頁,共14頁，2024年2月25日，星期天每次迭代時(shí)，將基變量中的負(fù)分量xl取出（換出變量）,去替換非基變量中的xk，要求在所有檢驗(yàn)數(shù)仍保持非正（對(duì)偶問題可行性）的前提下，進(jìn)行基變換。從原問題來看，經(jīng)過每次迭代,原問題由非可行解往可行解更靠近，當(dāng)原問題得到可行解時(shí)，便得到了最優(yōu)解（原問題、對(duì)偶問題）。注意：1.對(duì)偶單純形法不是解對(duì)偶問題的單純形法，而是應(yīng)用對(duì)偶原理求解原問題最優(yōu)解的一種方法。當(dāng)然，當(dāng)求解得到原問題的最優(yōu)解的同時(shí)，也就得到對(duì)偶問題的最優(yōu)解。2.在具體計(jì)算中，不另外構(gòu)造單純形表格，而是在原始問題的單純形表格基礎(chǔ)上進(jìn)行對(duì)偶處理。第3頁,共14頁，2024年2月25日，星期天對(duì)偶單純形法的計(jì)算步驟:(1)根據(jù)線性規(guī)劃問題，列出初始單純形表，檢查b列的數(shù)值，若都為非負(fù)，并且檢驗(yàn)數(shù)都為非正，則已得到最優(yōu)解。停止計(jì)算；若b列的數(shù)值至少還有一個(gè)負(fù)分量，檢驗(yàn)數(shù)保持非正，那么進(jìn)行計(jì)算。(3)

確定換入變量：檢查xl所在行的各系數(shù)alj(j=1,2,…,n)。若所有的alj

0,則無可行解，停止計(jì)算。(2)先確定換出變量：若

min{(B-1b)i|(B-1b)i<0}=(B-1b)l對(duì)應(yīng)的基變量xl為換出變量。（實(shí)際上，可取任何一個(gè)取負(fù)值的基變量作為換出變量。取最小的含義是盡快）第4頁,共14頁，2024年2月25日，星期天若存在alj<0,(j=1,2,…,n)，計(jì)算按θ規(guī)則所對(duì)應(yīng)的非基變量xk為換入變量(保持對(duì)偶問題解的可行性)。(4)以alk為主元素，進(jìn)行迭代，即進(jìn)行矩陣行變換。得新的單純形表。重復(fù)（1）-（4）步，直到求出最優(yōu)解為止。為什么要用下式來確定換入變量呢？原因如下：第5頁,共14頁，2024年2月25日，星期天第6頁,共14頁，2024年2月25日，星期天第l行變成：行變換將Pk變成單位向量，因?yàn)閎l<0，一定要求bl/alk0,要選主元素alk<0。檢驗(yàn)數(shù)變成（行變換）要保證可行性，就要有

jnew0，j=1,…,n),,1,,,0,,0,1,...

0,,0,(ln1lklklmlklklaaaaaabLLLL+),,0,,,0,,0,,0,,0(ln11klknklklmmlkkaaaaasssss---++LLLL第7頁,共14頁，2024年2月25日，星期天令T={j|alj<0}

當(dāng)jT時(shí)，alj0，從而jnew=j-alj/alk

k<0，滿足可行性。當(dāng)jT時(shí)，

jnew=j-alj/alk

k=alj[

j

/alj-

k

/alk]

由于

j，k，

alk，alj均小于0，從而上述括號(hào)內(nèi)的比值均大于0。又由于alj<0，為保證jnew0，（jT）故只要選取就能有方括號(hào)內(nèi)大于等于0，從而

jnew0。第8頁,共14頁，2024年2月25日，星期天

解:先將這問題轉(zhuǎn)化（此時(shí)b可以是負(fù)的）,以便得到對(duì)偶問題的初始可行基

maxz=-2x1-3x2-4x3

-x1-2x2-x3+x4

=-3-2x1+x2-3x3+x5

=-4xj≥0,j=1,2,3,4,5

建立這個(gè)問題的初始單純形表例：用對(duì)偶單純形法求解：

minω=2x1+3x2+4x3

x1+2x2+x3

≥32x1-x2+3x3

≥4

x1,x2,x3

≥0第9頁,共14頁，2024年2月25日，星期天第10頁,共14頁，2024年2月25日，星期天第11頁,共14頁，2024年2月25日，星期天則

X*=（11/5，2/5，0，0，0）T為原問題的最優(yōu)解。同時(shí)Y*=（y1*，y2*）=（8/5，1/5）第12頁,共14頁，2024年2月25日，星期天對(duì)偶單純形法特點(diǎn):(1)

簡化計(jì)算：不引入人工變量將線性規(guī)劃化成標(biāo)準(zhǔn)型,構(gòu)造初始單純形表(初始解是非可行解),只要檢驗(yàn)數(shù)非負(fù)(最優(yōu)檢驗(yàn)數(shù)),就可以進(jìn)行基的轉(zhuǎn)換；(2)

適于變量多于約束條件：當(dāng)變量少于約束方程的個(gè)數(shù)時(shí)，