運籌學對偶單純形法

關于運籌學對偶單純形法方法：設原問題maxz=CXAX=bX≥0

設B是一個基，令B=(P1,P2,…,Pm)，它對應的變量為

XB=(

x1,x2,…,xm)

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

，xm的檢驗數(shù)是

σi=ci–zi=ci-CBB-1Pi=0，i=1,2,…,m2、對應非基變量xm+1，…

，xn的檢驗數(shù)是

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

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

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

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

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

當jT時，alj0，從而jnew=j-alj/alk

k<0，滿足可行性。當jT時，

jnew=j-alj/alk

k=alj[

j

/alj-

k

/alk]

由于

j，k，

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

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

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

maxz=-2x1-3x2-4x3

-x1-2x2-x3+x4

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

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

建立這個問題的初始單純形表例：用對偶單純形法求解：

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)解。同時Y*=（y1*，y2*）=（8/5，1/5）第12頁,共14頁，2024年2月25日，星期天對偶單純形法特點:(1)

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

適于變量多于約束條件：當變量少于約束方程的個數(shù)時，