極大極小對偶理論分析

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

2、，再編寫代碼，進行實例分析，最后和對偶單純形法進行比較。通過比較，我發(fā)現(xiàn)單純形法是從原始問題的一個可行解通過迭代轉(zhuǎn)到另一個可行解，直到檢驗數(shù)滿足最優(yōu)性條件為止。對偶單純形法則是從滿足對偶可行性條件出發(fā)通過迭代逐步搜索原始問題的最優(yōu)解。在迭代過程中始終保持基解的對偶可行性，而使不可行性逐步消失。關(guān)鍵詞：極大極?。粚ε紗渭冃畏?；單純形法；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、極大極小對偶理論的描述12.1 對偶問題的描述12.2 對偶問題的性質(zhì)22.3 對偶單純形法33、數(shù)值實驗43.1 代碼實現(xiàn)43.2 算法測試53.3 結(jié)果分析74、算法比較74.1 單純形法74.2 算法實現(xiàn)74.3 算法測試94.4算法比較105、總結(jié)105.1 總結(jié)概括105.2 個人感言116、參考文獻111、引言在計算對偶問題的各種算法中，對偶單純形法（Dual Simplex Method）和單純形法

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

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

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

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

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

13、 3.迭代 使得1，其余為0。3、數(shù)值實驗3.1 代碼實現(xiàn)對偶單純形法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：對偶單純形法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或使用對偶單純形法的M文件都可以得到最優(yōu)解。4、

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

17、，求出典式和檢驗數(shù)step3 求step4 如果則該基可行解就是最優(yōu)解停止；否則轉(zhuǎn)step5；step5 如果，則問題無最優(yōu)解，停止；否則轉(zhuǎn)step6step6 求step7 以替代得到一個新的基，轉(zhuǎn)step2；4.2 算法實現(xiàn)function x,f=DCmin(c,A,b,AR,y0,d)% x: 最優(yōu)解% f: 目標函數(shù)最優(yōu)值% c: 目標函數(shù)系數(shù)向量% A: 系數(shù)矩陣% b: m維列向量% AR: 松弛變量系數(shù)矩陣% y0: 基矩陣初始向量% d: 補充向量（非目標系數(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);%檢驗數(shù) end t; f=y*z; %=選取主元=% %-選取主列-% alpha,q=max(t); q; W(k)=q;%x下標矩陣 %-% %-選取主元-% 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) 運行結(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，通過轉(zhuǎn)軸，使得檢驗數(shù)0來求得最優(yōu)解，而使用對偶單純形法的前提是0，通過轉(zhuǎn)軸，使得達到0。二者都是0, 0同時滿足時達到最優(yōu)。在靈敏度分析時，對的靈敏度分析用單純形法來考察，因為此時變動導(dǎo)致檢驗數(shù)變動。而的變動則是用到對偶單純形法來求解檢驗。5、總結(jié)5.1 總結(jié)概括求解最優(yōu)問題是一個艱難而具有挑戰(zhàn)性的過程，最優(yōu)化方法是近幾十年形成的一門運用數(shù)學方法研究各種系統(tǒng)的優(yōu)化途徑及方案，為決策