極大極小對(duì)偶理論分析

1、編號(hào):_ 最 優(yōu) 化 方 法課 程 設(shè) 計(jì)題 目： 極大極小對(duì)偶理論分析 院 系： 專 業(yè)： 姓名學(xué)號(hào)： 指導(dǎo)教師： 日 期： 2014 年 01 月 02 日摘 要在極大極小對(duì)偶理論中，我們尋求原問(wèn)題和對(duì)偶問(wèn)題之間的求解，對(duì)偶單純形法是非常重要的一種解法。本文主要介紹的對(duì)偶單純形法，對(duì)偶單純形法算法結(jié)構(gòu)簡(jiǎn)單, 容易使用matlab編程實(shí)現(xiàn)。在本次實(shí)驗(yàn)中,我首先分析對(duì)偶單純形法，了解對(duì)偶單純形法解對(duì)偶問(wèn)題的步驟，進(jìn)行實(shí)例求解，再運(yùn)用對(duì)偶單純形法的思路編寫代碼，進(jìn)行matlab實(shí)例求解，加以分析，總結(jié)。進(jìn)行算法比較。我把對(duì)偶單純形法與單純形法進(jìn)行比較，先了解單純形法解決問(wèn)題的步驟，和實(shí)例求解過(guò)程

2、，再編寫代碼，進(jìn)行實(shí)例分析，最后和對(duì)偶單純形法進(jìn)行比較。通過(guò)比較，我發(fā)現(xiàn)單純形法是從原始問(wèn)題的一個(gè)可行解通過(guò)迭代轉(zhuǎn)到另一個(gè)可行解，直到檢驗(yàn)數(shù)滿足最優(yōu)性條件為止。對(duì)偶單純形法則是從滿足對(duì)偶可行性條件出發(fā)通過(guò)迭代逐步搜索原始問(wèn)題的最優(yōu)解。在迭代過(guò)程中始終保持基解的對(duì)偶可行性，而使不可行性逐步消失。關(guān)鍵詞：極大極小；對(duì)偶單純形法；單純形法；AbstractIn Minimax duality theory , we seek between the original problem and the dual problem of solving the dual simplex method is

3、a very important one solution. This paper describes the dual simplex method, dual simplex method algorithm structure is simple , easy to use matlab programming.In this experiment , I first analysis of the dual simplex method , understanding of the dual simplex method for solving the dual problem in

4、steps and examples to solve , and then apply to the idea of dual simplex method of writing code , conduct matlab examples solved analyze , summarize .For algorithm comparison. I put the dual simplex method are compared with the simplex method , the first step to understand the simplex method to solv

5、e the problem solving process and examples , and then write code to analyze an example , last and dual simplex method for comparison.By comparison, I found the simplex method is feasible to the original problem from one iteration to another feasible solution by solution , until the number of test op

6、timality condition is satisfied. Dual simplex rule of thumb is to satisfy the dual feasibility conditions from the gradual departure of the original problem through an iterative search for the optimal solution . Remain in an iterative process based solutions for dual feasibility , leaving the infeas

7、ibility gradually disappear.Key words: minimax；Dual simplex method；simplex method；目 錄1、引言12、極大極小對(duì)偶理論的描述12.1 對(duì)偶問(wèn)題的描述12.2 對(duì)偶問(wèn)題的性質(zhì)22.3 對(duì)偶單純形法33、數(shù)值實(shí)驗(yàn)43.1 代碼實(shí)現(xiàn)43.2 算法測(cè)試53.3 結(jié)果分析74、算法比較74.1 單純形法74.2 算法實(shí)現(xiàn)74.3 算法測(cè)試94.4算法比較105、總結(jié)105.1 總結(jié)概括105.2 個(gè)人感言116、參考文獻(xiàn)111、引言在計(jì)算對(duì)偶問(wèn)題的各種算法中，對(duì)偶單純形法（Dual Simplex Method）和單純形法

8、（Simplex Method）是非常重要的兩種。1954年美國(guó)數(shù)學(xué)家C.萊姆基提出對(duì)偶單純形法。單純形法是從原始問(wèn)題的一個(gè)可行解通過(guò)迭代轉(zhuǎn)到另一個(gè)可行解，直到檢驗(yàn)數(shù)滿足最優(yōu)性條件為止。對(duì)偶單純形法則是從滿足對(duì)偶可行性條件出發(fā)通過(guò)迭代逐步搜索原始問(wèn)題的最優(yōu)解。在迭代過(guò)程中始終保持基解的對(duì)偶可行性，而使不可行性逐步消失。設(shè)原始問(wèn)題為，則其對(duì)偶問(wèn)題（Dual Problem）為。在原來(lái)的單純形表中進(jìn)行迭代時(shí)，前提要求右端項(xiàng)(基可行解)，迭代過(guò)程中在列中得到的是原問(wèn)題的基可行解，在檢驗(yàn)數(shù)行得到的是對(duì)偶問(wèn)題的基解。當(dāng)檢驗(yàn)數(shù)行也是對(duì)偶問(wèn)題的基可行解時(shí)，原問(wèn)題與對(duì)偶問(wèn)題都得到最優(yōu)解?？芍瑢?duì)偶單純形法原理

9、：根據(jù)對(duì)偶問(wèn)題的對(duì)稱性，保持對(duì)偶問(wèn)題的解是基可行解，即，同時(shí)取消對(duì)解答列元素非負(fù)的限制，在原問(wèn)題非可行解的基礎(chǔ)上, 通過(guò)逐步迭代得到基可行解，這樣就得到了最優(yōu)解。2、極大極小對(duì)偶理論的描述2.1對(duì)偶的描述一、對(duì)偶問(wèn)題的提出 現(xiàn)有甲乙兩種原材料生產(chǎn)A,B兩種產(chǎn)品，所需的原料，甲乙兩種原料的可供量，以及生產(chǎn)A,B兩種產(chǎn)品可得的單位利潤(rùn)見表。問(wèn)如何安排生產(chǎn)資源使得總利潤(rùn)最大？解:設(shè)生產(chǎn)A為單位，生產(chǎn)B為單位,則線性規(guī)劃問(wèn)題為： s.t. 另一方面，假設(shè)另一公司想把資源買過(guò)來(lái)，它至少應(yīng)付出多大代價(jià)才能使原來(lái)公司放棄生產(chǎn)，出讓資源？解：設(shè)甲資源的出讓單價(jià)為,乙資源的出讓單價(jià)為 s.t. 二、對(duì)稱形式下對(duì)

10、偶問(wèn)題的一般形式 定義：變量均為非負(fù)約束的情況下，約束條件在目標(biāo)函數(shù)取極大值時(shí)均取“”號(hào)；當(dāng)目標(biāo)函數(shù)求極小值時(shí)均取“”號(hào)，稱此線性規(guī)劃問(wèn)題具有對(duì)稱形式結(jié)論：對(duì)偶問(wèn)題的對(duì)偶就是原始問(wèn)題。兩個(gè)問(wèn)題中的任一個(gè)都可以作為原始問(wèn)題，另一個(gè)就是它的對(duì)偶問(wèn)題。2.2 對(duì)偶問(wèn)題的性質(zhì)單純形法是從原始問(wèn)題的一個(gè)可行解通過(guò)迭代轉(zhuǎn)到另一個(gè)可行解，直到檢驗(yàn)數(shù)滿足最優(yōu)性條件為止。對(duì)偶單純形法則是從滿足對(duì)偶可行性條件出發(fā)通過(guò)迭代逐步搜索原始問(wèn)題的最優(yōu)解。在迭代過(guò)程中始終保持基解的對(duì)偶可行性，而使不可行性逐步消失?？紤]如下對(duì)偶問(wèn)題：原始問(wèn)題 對(duì)偶問(wèn)題 1.弱對(duì)偶性推論：（1）原問(wèn)題任一可行解的目標(biāo)函數(shù)是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值

11、的下界；反之對(duì)偶問(wèn)題任一可行解的目標(biāo)函數(shù)是其原問(wèn)題目標(biāo)函數(shù)的上界。（2）如原問(wèn)題有可行解且目標(biāo)函數(shù)值無(wú)界，則其對(duì)偶問(wèn)題無(wú)可行解；反之對(duì)偶問(wèn)題有可行解且目標(biāo)函數(shù)無(wú)界，則原問(wèn)題無(wú)可行解。（對(duì)偶問(wèn)題無(wú)可行解時(shí)，其原問(wèn)題無(wú)界解或無(wú)可行解。（3）若原問(wèn)題有可行解而其對(duì)偶問(wèn)題無(wú)可行解時(shí)，原問(wèn)題目標(biāo)函數(shù)無(wú)界。（4）若對(duì)偶問(wèn)題有可行解而其原問(wèn)題無(wú)可行解時(shí)，對(duì)偶問(wèn)題目標(biāo)函數(shù)無(wú)界。2.最優(yōu)性3.強(qiáng)對(duì)偶性（對(duì)偶性定理）若原問(wèn)題和對(duì)偶問(wèn)題均具有可行解，則二者均具有最優(yōu)解，且它們的最優(yōu)解的目標(biāo)值相等。4.互補(bǔ)松弛定理在線性規(guī)劃的最優(yōu)解中如果對(duì)應(yīng)某一約束條件的對(duì)偶變量的值為非零，遮蓋月初條件去嚴(yán)格等式；反之如果約束條件取

12、嚴(yán)格不等式則其對(duì)偶變量一定為零。2.3 對(duì)偶單純形法對(duì)偶單純形法適用的情況：設(shè)有問(wèn)題： 又設(shè)B是其一個(gè)基，當(dāng)非基變量都為0時(shí)，可以得到XB=B-1b。若在B-1b中至少有一個(gè)負(fù)分量，并且在單純形表的檢驗(yàn)數(shù)行中的檢驗(yàn)數(shù)都為非正，這種情況就可以用對(duì)偶單純形法來(lái)進(jìn)行求解。對(duì)偶單純形法的計(jì)算步驟：step1.確定初始解 求初時(shí)基可行解,列出初始單純性表(一般取松弛變量為基變量)；若所有檢驗(yàn)數(shù)0，且所有的基變量值均0，則此解為線性規(guī)劃問(wèn)題的最優(yōu)解；若存在基變量的值0，則問(wèn)題還沒(méi)有達(dá)到最優(yōu)解，則進(jìn)行如下計(jì)算；step 2.改進(jìn) 選擇換出變量：,假設(shè)選取為換出變量； 選擇換入變量：,假設(shè)為換入變量；step

13、 3.迭代 使得1，其余為0。3、數(shù)值實(shí)驗(yàn)3.1 代碼實(shí)現(xiàn)對(duì)偶單純形法M文件functionx,z=dsimplex(A0,b0,c0)m,n=size(A0);p=n+1:n+m;nb=n+m+1;Ab=-A0,eye(m),-b0;c=c0,zeros(1,m);w=-c;iter=0;br,r=min(Ab(:,nb);while(br0)iter=iter+1;ar=Ab(r,:);xs=inf;f1ag=0;fori=1:nifar(i)0t=w(i)/ar(i);ift=60;35*x1+42*x2+18*x3+31*x4+56*x5+49*x6=150;37*x1+53*x2+2

14、8*x3+24*x4+29*x5+20*x6=125;其中x0,x=1回答解法1：調(diào)用linprogf=8;10;7;6;11;9;lb=zeros(6,1);ub=ones(6,1);Aeq1=12925201713;Aeq2=354218315649;Aeq3=375328242920;Aeq=-Aeq1;-Aeq2;-Aeq3;beq=-60;-150;-125;x,fval=linprog(f,Aeq,beq,lb,ub)結(jié)果為:x=1.00000.62270.34351.00000.04761.0000fval=32.1546解法2：對(duì)偶單純形法1將3.1代碼保存為M文件；2再在命令

15、窗口輸入：f=8;10;7;6;11;9;lb=zeros(6,1);ub=ones(6,1);Aeq1=12925201713;Aeq2=354218315649;Aeq3=375328242920;Aeq4=eye(6);Aeq=-Aeq1;-Aeq2;-Aeq3;Aeq4;beq=-60;-150;-125;ub;A=Aeq;c0=f;A0=-A;b0=-beq;x,z=dsimplex(A0,b0,c0)結(jié)果為:x=1.00000.62270.34351.00000.04761.0000z=32.15463.3 結(jié)果分析調(diào)用linprog或使用對(duì)偶單純形法的M文件都可以得到最優(yōu)解。4、

16、算法比較4.1 單純形法單純形法，求解線性規(guī)劃問(wèn)題的通用方法。單純形是美國(guó)數(shù)學(xué)家G.B.丹齊克于1947年首先提出來(lái)的。它的理論根據(jù)是：線性規(guī)劃問(wèn)題的可行域是 n維向量空間Rn中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點(diǎn)處達(dá)到。頂點(diǎn)所對(duì)應(yīng)的可行解稱為基本可行解。單純形法的基本思想是：先找出一個(gè)基本可行解，對(duì)它進(jìn)行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)換到另一改進(jìn)的基本可行解，再鑒別；若仍不是，則再轉(zhuǎn)換，按此重復(fù)進(jìn)行。因基本可行解的個(gè)數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問(wèn)題的最優(yōu)解。如果問(wèn)題無(wú)最優(yōu)解也可用此法判別。單純形法計(jì)算步驟step1 將所給問(wèn)題化為標(biāo)準(zhǔn)形式step2找一個(gè)初始可行基

17、，求出典式和檢驗(yàn)數(shù)step3 求step4 如果則該基可行解就是最優(yōu)解停止；否則轉(zhuǎn)step5；step5 如果，則問(wèn)題無(wú)最優(yōu)解，停止；否則轉(zhuǎn)step6step6 求step7 以替代得到一個(gè)新的基，轉(zhuǎn)step2；4.2 算法實(shí)現(xiàn)function x,f=DCmin(c,A,b,AR,y0,d)% x: 最優(yōu)解% f: 目標(biāo)函數(shù)最優(yōu)值% c: 目標(biāo)函數(shù)系數(shù)向量% A: 系數(shù)矩陣% b: m維列向量% AR: 松弛變量系數(shù)矩陣% y0: 基矩陣初始向量% d: 補(bǔ)充向量（非目標(biāo)系數(shù)向量, 為一零向量）N=10000;B=A,AR,b;m,n=size(B);C=c,d;y=y0;x=zeros(1

18、,length(c);for k=1:N k; z=B(:,end);%右端 for j=1:n-1 t(j)=y*B(:,j)-C(j);%檢驗(yàn)數(shù) end t; f=y*z; %=選取主元=% %-選取主列-% alpha,q=max(t); q; W(k)=q;%x下標(biāo)矩陣 %-% %-選取主元-% for p=1:m if B(p,q)=0 r(p)=N; else r(p)=z(p)/B(p,q); end end beta,p=min(r); p; y(p)=C(q); %-% %=% B(p,:)=B(p,:)/B(p,q); for i=1:m if i=p B(i,:)=B(i

19、,:)-B(p,:)*B(i,q); end end if max(t) c=1 -2 1;A=1 1 -2 1;2 -1 4 0;-1 2 -4 0;b=10;8;4;AR=0 0;1 0;0 1;y0=0 0 0;d=0 0 0; x,f=DCmin(c,A,b,AR,y0,d)(ii) 運(yùn)行結(jié)果: B = 1 1 -2 1 0 0 10 2 -1 4 0 1 0 8 -1 2 -4 0 0 1 4k = 1t = -1 2 -1 0 0 0f = 0B = 1.5000 0 0 1.0000 0 -0.5000 8.0000 1.5000 0 2.0000 0 1.0000 0.5000

20、 10.0000 -0.5000 1.0000 -2.0000 0 0 0.5000 2.0000k = 2t = 0 0 3 0 0 -1f = -4B = 1.5000 0 0 1.0000 0 -0.5000 8.0000 0.7500 0 1.0000 0 0.5000 0.2500 5.0000 1.0000 1.0000 0 0 1.0000 1.0000 12.0000k = 3t = -2.2500 0 0 0 -1.5000 -1.7500f = -19x = 0 12 5f = -194.4算法比較單純形法是是保證0，通過(guò)轉(zhuǎn)軸，使得檢驗(yàn)數(shù)0來(lái)求得最優(yōu)解，而使用對(duì)偶單純形法的前提是0，通過(guò)轉(zhuǎn)軸，使得達(dá)到0。二者都是0, 0同時(shí)滿足時(shí)達(dá)到最優(yōu)。在靈敏度分析時(shí)，對(duì)的靈敏度分析用單純形法來(lái)考察，因?yàn)榇藭r(shí)變動(dòng)導(dǎo)致檢驗(yàn)數(shù)變動(dòng)。而的變動(dòng)則是用到對(duì)偶單純形法來(lái)求解檢驗(yàn)。5、總結(jié)5.1 總結(jié)概括求解最優(yōu)問(wèn)題是一個(gè)艱難而具有挑戰(zhàn)性的過(guò)程，最優(yōu)化方法是近幾十年形成的一門運(yùn)用數(shù)學(xué)方法研究各種系統(tǒng)的優(yōu)化途徑及方案，為決策