《极大极小对偶理论分析》由会员分享，可在线阅读，更多相关《极大极小对偶理论分析（15页珍藏版）》请在金锄头文库上搜索。
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 simp
3、lex method is 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 du
4、al problem in 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
5、method to solve 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 num
6、ber of test optimality 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 , leav
7、ing the infeasibility 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、参考文献 .1
8、11、引言在计算对偶问题的各种算法中，对偶单纯形法（Dual Simplex Method）和单纯形法（Simplex Method）是非常重要的两种。1954 年美国数学家 C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为 ，则其对偶问题（Dual Problem）为min,0cxAb。ayb在原来的单纯形表中进行迭代时，前提要求右端项 (基可行解)，迭代0b过程中在 列中得到的是
9、原问题的基可行解，在检验数行得到的是对偶问题的基解。当检验数行也是对偶问题的基可行解时，原问题与对偶问题都得到最优解。可知，对偶单纯形法原理：根据对偶问题的对称性，保持对偶问题的解是基可行解，即 ，同时取消对解答列元素非负的限制，在原问题非1-0jBcC可行解的基础上, 通过逐步迭代得到基可行解，这样就得到了最优解。2、极大极小对偶理论的描述2.1 对偶的描述一、对偶问题的提出现有甲乙两种原材料生产 A,B 两种产品，所需的原料，甲乙两种原料的可供量，以及生产 A,B 两种产品可得的单位利润见表。问如何安排生产资源使得总利润最大？解:设生产 A 为 单位，生产 B 为 单位,则线性规划问题为：1x2x2max4.5Zs.t. 134x201,x另一方面，假设另一公司想把资源买过来，它至少应付出多大代价才能使原来公司放弃生产，出让资源？解：设甲资源的出让单价为 ,乙资源的出让单价为1y2y12min540wy s.t. 1234.5y12,0y二、对称形式下对偶问题的一般形式 定义：变量均为非负约束的情况下，约束条件在目标函数取极大值时均取“”号；当目标函数求极小值时均取“”号，称此线性规划问题具有对称形式max.0TZCXstAb1212212in.
