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

1、關(guān)于運(yùn)籌學(xué)對(duì)偶單純形法第一張，PPT共十四頁(yè)，創(chuàng)作于2022年6月方法：設(shè)原問(wèn)題 max z = CX AX = b X 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ì)偶問(wèn)題保持可行解，它的各分量是 1、對(duì)應(yīng)基變量x1，x2， ，xm的檢驗(yàn)數(shù)是 i = ci zi = ci - CB B-1Pi = 0，i = 1 ,2 , ,m 2、對(duì)應(yīng)非基變量xm+1， ，xn的檢驗(yàn)數(shù)是 j

2、 = cj zj = cj - CB B-1Pj 0，j = m+1 , ,n第二張，PPT共十四頁(yè)，創(chuàng)作于2022年6月每次迭代時(shí)，將基變量中的負(fù)分量xl取出（換出變量）, 去替換非基變量中的xk，要求在所有檢驗(yàn)數(shù)仍保持非正（對(duì)偶問(wèn)題可行性）的前提下，進(jìn)行基變換。從原問(wèn)題來(lái)看，經(jīng)過(guò)每次迭代, 原問(wèn)題由非可行解往可行解更靠近，當(dāng)原問(wèn)題得到可行解時(shí)，便得到了最優(yōu)解（原問(wèn)題、對(duì)偶問(wèn)題）。注意：1. 對(duì)偶單純形法不是解對(duì)偶問(wèn)題的單純形法，而是應(yīng)用對(duì)偶原理求解原問(wèn)題最優(yōu)解的一種方法。當(dāng)然，當(dāng)求解得到原問(wèn)題的最優(yōu)解的同時(shí)，也就得到對(duì)偶問(wèn)題的最優(yōu)解。2.在具體計(jì)算中，不另外構(gòu)造單純形表格，而是在原始問(wèn)題的

3、單純形表格基礎(chǔ)上進(jìn)行對(duì)偶處理。第三張，PPT共十四頁(yè)，創(chuàng)作于2022年6月對(duì)偶單純形法的計(jì)算步驟:(1) 根據(jù)線性規(guī)劃問(wèn)題，列出初始單純形表，檢查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)。 若所有的 alj0,則無(wú)可行解，停止計(jì)算。(2) 先確定換出變量：若 min(B-1b)i|(B-1b)i 0 = (B-1b)l對(duì)應(yīng)的基變量xl為換出變量。（實(shí)際上，可取任何一個(gè)取負(fù)值的基變量作為換出變量。取最小的含義是盡快）第四張，PPT

4、共十四頁(yè)，創(chuàng)作于2022年6月若存在alj 0,(j = 1,2,n)，計(jì)算按規(guī)則所對(duì)應(yīng)的非基變量xk為換入變量(保持對(duì)偶問(wèn)題解的可行性)。(4) 以alk為主元素，進(jìn)行迭代，即進(jìn)行矩陣行變換。得新的單純形表。重復(fù)（1）-（4）步，直到求出最優(yōu)解為止。為什么要用下式來(lái)確定換入變量呢？原因如下：第五張，PPT共十四頁(yè)，創(chuàng)作于2022年6月第六張，PPT共十四頁(yè)，創(chuàng)作于2022年6月第l行變成：行變換將Pk變成單位向量，因?yàn)閎l0，一定要求bl/alk0, 要選主元素alk0。檢驗(yàn)數(shù)變成（行變換）要保證可行性，就要有jnew 0，j=1,n),1,0,0,1, . 0,0,(ln1lklklmlk

5、lklaaaaaabLLLL+),0,0,0,0,0(ln11klknklklmmlkkaaaaasssss-+LLLL第七張，PPT共十四頁(yè)，創(chuàng)作于2022年6月令T=j|alj0 當(dāng)jT時(shí)， alj 0，從而jnew= j-al j/al kk 0，滿足可行性。 當(dāng)jT時(shí)， jnew= j-al j/al kk = al jj /al j- k /al k 由于j ，k， al k ，al j均小于0，從而上述括號(hào)內(nèi)的比值均大于0。 又由于alj0，為保證jnew 0， （ jT） 故只要選取就能有方括號(hào)內(nèi)大于等于0，從而jnew 0。第八張，PPT共十四頁(yè)，創(chuàng)作于2022年6月 解: 先

6、將這問(wèn)題轉(zhuǎn)化（此時(shí)b可以是負(fù)的）,以便得到對(duì)偶問(wèn)題的初始可行基 max z = -2x1 - 3x2 - 4x3 -x1 - 2x2 - x3 + x4 = -3 -2x1 + x2 - 3x3 + x5 = -4 xj 0,j = 1,2,3,4,5 建立這個(gè)問(wèn)題的初始單純形表例：用對(duì)偶單純形法求解： min = 2x1 + 3x2 + 4x3 x1 + 2x2 + x3 3 2x1 - x2 + 3x3 4 x1 , x2 , x3 0 第九張，PPT共十四頁(yè)，創(chuàng)作于2022年6月第十張，PPT共十四頁(yè)，創(chuàng)作于2022年6月第十一張，PPT共十四頁(yè)，創(chuàng)作于2022年6月則 X*=（11/5，2/5，0，0，0）T為原問(wèn)題的最優(yōu)解。同時(shí) Y*=（y1*，y2*）=（8/5，1/5）第十二張，PPT共十四頁(yè)，創(chuàng)作于2022年6月對(duì)偶單純形法特點(diǎn):(1) 簡(jiǎn)化計(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í)，可考慮變成對(duì)偶問(wèn)題后，再用對(duì)偶單純形