极大极小对偶理论分析

1、编号:_ 最 优 化 方 法课 程 设 计题 目： 极大极小对偶理论分析 院 系： 专 业： 姓名学号： 指导教师： 日 期： 2014 年 01 月 02 日摘 要在极大极小对偶理论中，我们寻求原问题和对偶问题之间的求解，对偶单纯形法是非常重要的一种解法。本文主要介绍的对偶单纯形法，对偶单纯形法算法结构简单, 容易使用matlab编程实现。在本次实验中,我首先分析对偶单纯形法，了解对偶单纯形法解对偶问题的步骤，进行实例求解，再运用对偶单纯形法的思路编写代码，进行matlab实例求解，加以分析，总结。进行算法比较。我把对偶单纯形法与单纯形法进行比较，先了解单纯形法解决问题的步骤，和实例求解过程

2、，再编写代码，进行实例分析，最后和对偶单纯形法进行比较。通过比较，我发现单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。关键词：极大极小；对偶单纯形法；单纯形法；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 对偶问题的性质22.3 对偶单纯形法33、数值实验43.1 代码实现43.2 算法测试53.3 结果分析74、算法比较74.1 单纯形法74.2 算法实现74.3 算法测试94.4算法比较105、总结105.1 总结概括105.2 个人感言116、参考文献111、引言在计算对偶问题的各种算法中，对偶单纯形法（Dual Simplex Method）和单纯形法

8、（Simplex Method）是非常重要的两种。1954年美国数学家C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为，则其对偶问题（Dual Problem）为。在原来的单纯形表中进行迭代时，前提要求右端项(基可行解)，迭代过程中在列中得到的是原问题的基可行解，在检验数行得到的是对偶问题的基解。当检验数行也是对偶问题的基可行解时，原问题与对偶问题都得到最优解。可知，对偶单纯形法原理

9、：根据对偶问题的对称性，保持对偶问题的解是基可行解，即，同时取消对解答列元素非负的限制，在原问题非可行解的基础上, 通过逐步迭代得到基可行解，这样就得到了最优解。2、极大极小对偶理论的描述2.1对偶的描述一、对偶问题的提出 现有甲乙两种原材料生产A,B两种产品，所需的原料，甲乙两种原料的可供量，以及生产A,B两种产品可得的单位利润见表。问如何安排生产资源使得总利润最大？解:设生产A为单位，生产B为单位,则线性规划问题为： s.t. 另一方面，假设另一公司想把资源买过来，它至少应付出多大代价才能使原来公司放弃生产，出让资源？解：设甲资源的出让单价为,乙资源的出让单价为 s.t. 二、对称形式下对

10、偶问题的一般形式 定义：变量均为非负约束的情况下，约束条件在目标函数取极大值时均取“”号；当目标函数求极小值时均取“”号，称此线性规划问题具有对称形式结论：对偶问题的对偶就是原始问题。两个问题中的任一个都可以作为原始问题，另一个就是它的对偶问题。2.2 对偶问题的性质单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。考虑如下对偶问题：原始问题 对偶问题 1.弱对偶性推论：（1）原问题任一可行解的目标函数是其对偶问题目标函数值

11、的下界；反之对偶问题任一可行解的目标函数是其原问题目标函数的上界。（2）如原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之对偶问题有可行解且目标函数无界，则原问题无可行解。（对偶问题无可行解时，其原问题无界解或无可行解。（3）若原问题有可行解而其对偶问题无可行解时，原问题目标函数无界。（4）若对偶问题有可行解而其原问题无可行解时，对偶问题目标函数无界。2.最优性3.强对偶性（对偶性定理）若原问题和对偶问题均具有可行解，则二者均具有最优解，且它们的最优解的目标值相等。4.互补松弛定理在线性规划的最优解中如果对应某一约束条件的对偶变量的值为非零，遮盖月初条件去严格等式；反之如果约束条件取

12、严格不等式则其对偶变量一定为零。2.3 对偶单纯形法对偶单纯形法适用的情况：设有问题： 又设B是其一个基，当非基变量都为0时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，并且在单纯形表的检验数行中的检验数都为非正，这种情况就可以用对偶单纯形法来进行求解。对偶单纯形法的计算步骤：3、数值实验3.1 代码实现对偶单纯形法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(

13、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+28*x3+24*x4+29*x5+20*x6=125;其中x0,x=1回答解法1：调用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;be

14、q=-60;-150;-125;x,fval=linprog(f,Aeq,beq,lb,ub)结果为:x=1.00000.62270.34351.00000.04761.0000fval=32.1546解法2：对偶单纯形法1将3.1代码保存为M文件；2再在命令窗口输入：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=

15、f;A0=-A;b0=-beq;x,z=dsimplex(A0,b0,c0)结果为:x=1.00000.62270.34351.00000.04761.0000z=32.15463.3 结果分析调用linprog或使用对偶单纯形法的M文件都可以得到最优解。4、算法比较4.1 单纯形法单纯形法，求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；

16、若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。单纯形法计算步骤4.2 算法实现function x,f=DCmin(c,A,b,AR,y0,d)% x: 最优解% f: 目标函数最优值% c: 目标函数系数向量% A: 系数矩阵% b: m维列向量% AR: 松弛变量系数矩阵% y0: 基矩阵初始向量% d: 补充向量（非目标系数向量, 为一零向量）N=10000;B=A,AR,b;m,n=size(B);C=c,d;y=y0;x=zeros(1,lengt

17、h(c);for k=1:N k; z=B(:,end);%右端 for j=1:n-1 t(j)=y*B(:,j)-C(j);%检验数 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,:)-B(

18、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) 运行结果: 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 10.00

19、00 -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，通过转轴，使得检验数0来求得最优解，而使用对偶单纯形法的前提是0，通过转轴，使得达到0。二者都是0, 0同时满足时达到最优。在灵敏度分析时，对的灵敏度分析用单纯形法来考察，因为此时变动导致检验数变动。而的变动则是用到对偶单纯形法来求解检验。5、总结5.1 总结概括求解最优问题是一个艰难而具有挑战性的过程，最优化方法是近几十年形成的一门运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据的学科，它涵盖了无约束最优化问题、凸集与