对偶与对偶单纯形法的应用.ppt

1、第2章7节大邱和大邱简单法，1，大邱问题的提出2，原文制和大邱问题的转换3，大邱问题的性质4，大邱问题的经济意义影子价格5，大邱简单法，1，双重问题的提出，各逐线性规划问题都有与之密切相关的线性计划的所有问题。我们对此有原文：一家工厂在计划期间，生产两种产品，生产单位产品所需的设备A，B，C台，如表所示，该工厂每生产一个单位能赚50元，每生产一个单位能赚100元，询问工厂需要生产的产品和产品数量，工厂能获得最多的利益吗？了解：如果将x1设置为产品I的计划生产，将x2产品的计划生产设置为x2产品的计划生产，则存在max z=50x 1 100 x2 x2 x2 300 2x1 x2 400 x2

2、 250 x1，x20。如果其他工厂需要租赁该工厂的设备a、b、c，那么工厂厂长应该怎么办：租赁进口自组织生产的进口对租赁工厂：总租赁最低变量变更产品设备不再是限制。必须从产品开始。y1、y2、y3是A、B和C小时租赁价格。产品I:每个I的自身生产收益为50韩元，租赁收入为y1 2y2韩元。以产品为例，自己的生产收入为100元，租赁收入为y1 y2 y3元，Minw=300y1 400y2 250y3(设备租赁总收入)S.T y1 2y2 50 y1 y2 y3 100中的y1、y2、y3都比较0与原始线性计划问题不同1生成的两个线性模型是一对对偶问题。一个是原来的问题，另一个是双重问题。矩阵

3、格式比较：解算1: maxz=cxaxbx0解算2: minw=b y a y c y 0，2，原始问题和对偶问题转换，1，目标函数MAXMin 2，约束变量约束n个变量n个约束0变量0约束0变量0约束=0变量约束变量约束变量m个约束变量m个约束变量0个约束变量0 0个约束0个变量无约束0个变量约束=0 4，目标函数中的变量，记住要点：1，“三个元素”，目标函数，约束变量，C-b的切换。 2、掌握核心变量和约束之间的关系。(1)如果约束=0，则变量没有约束。(2)查看约束0中的原始问题目标函数。1)最大值：约束变量，反转；变量约束，正数。(无论如何)2)分钟：约束变量，正向；变量约束，反转。(

4、正和傅晶)，记忆码：1，MaxMin 2，C b 3，无限等于0，数M变量N. 4，max反正，民是正和负的。(约束变量)，例如，转换为对偶问题，第一种方法：根据定义，第三个条件由两个方程代替。用学过的原则写一次？示例2:minz=7 x1 4x 2-3x 3s . t-4x 1 2x 2-6x 3 24-3x 1-6x 2-4x 3 15x 2 3x 3=30写入双重问题其中x1 0，x Maxz=24y1 15 y2(类似于“负正数”)MINW=300 y1 400 y2 250 y3 s . t Y1 2 Y2 50 Y1 Y2 Y3 100其中Y1、Y2、Y3都是0的双重问题是？max

5、Z=50x 1 100 x2 x1 x2 300 2 x1 x2 400 x2 250 x1，x20，(2)原始问题为(弱对偶定理)maxZ=CX AX b X 0时，对偶问题为Minw=Yb YA C Y 0相反：对偶问题为认识：(1)许多边界。(2)查看目标函数的类型判断。(3)原始问题是(无限定理)maxZ=CX AX b X 0的对偶问题是Minw=Yb YA C Y 0，如果存在原始问题的可行解，那么目标函数是无限解的先决条件是没有对偶问题的可行解。(4) X和Y分别是原始问题和对偶问题的可解决方案，如果CX=Yb(目标函数值相同)，则X和Y分别是原始问题和对偶问题的最佳解决方案。(

6、优化定理)通常，取CXYb，=表示Yb最小，CX最大。(5)原始问题和对偶问题有可行的解决方案，原始问题或对偶问题中有最优解决方案，其他对偶问题也必须有最优解决方案，最优值必须相同。(主对偶定理)证明意义：如果原始问题具有与主B相对应的最优解，则CBB-1是对偶问题的最优解。(6)如果X，Y是原始问题和对偶问题的可行解，则X，Y是最佳解的必要条件，并且V*X=0，Y*U=0。其中v是对偶问题的剩余变量，u是原始问题的李莞变量。(补正松弛性定理)，(7)在单纯形法迭代过程中，原始问题的检验数等于对偶问题的基本解。(对应清理)原始问题XB XN XS相应的默认b检查数0 CN-CBB-1BN CB

7、B-1双重问题变量-YS1 -YS2 -Y，原始问题：maxz=12 x1 8x 2 5x 3 x1 20x 1 x2 x3 112 x x33 minw=20 y1 11 y2 5 y3 3 y1 y2 12 y3 12 y1 4 y3 8 y2 y3 5 y1，y2，y30 maxf=-20 y1-11 y2-5y 3 y1 y2 12y 3 Y4=12 y1 4 y2 y3 y3 Y4，y3 资源对生产的贡献。(影子价格)是实现现有资源最大效果的评价，称为机会成本。5，双单纯形法，想法：简单方法的故障诊断思想：从可执行域的一个顶点(默认可执行解决方案)通过迭代(默认行转换)到另一个顶点(

8、默认可执行解决方案)，按原样裴珉姬顶点的最优性(从每个顶点获得的目标函数值增加(max)，)当对偶问题得到基本解的同时，是可行解的时候，原始问题的检验数都是0，即原始问题得到最佳解。作业问题的原始问题和双重问题解决的关系。x1 x2 x3 x4 X5 X6 y2 y2 y3 y4 y5 0 20 11 48 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0-4-4 0 0 1 4/3 8 0 5/3 0 0 0-1 4 0 2 0 0 0 0 0 0 0 0 12/5 12/5 1/5从顶点1重复到顶点4，双重简易法的思想：根据原文制对偶问题的

9、特点(主对偶定理、优化定理、对应定理)，用简易法解决线性规划问题(简易法的一种)。解决问题的想法：在每次迭代中保持双重性问题是可行的解决方案。无论原始问题的基本解释是否是基本的可行解决方案，当原始问题得到基本的可行解决方案时，该解决方案是原始问题的最佳解决方案。(David aser，Northern Exposure(TM)，2，yes，以双重简单性解决线性规划问题。minw=12 y1 16 y2 15 y3 2 y1 4 y2 2 y1 5y33 y1，y2，y30在使用双重法之前，您希望如何写初始简单表？请使用“大m”方法或两步方法。(必须使用人工变量法)maxz=-12 y1-16

10、y2-15 y3 0y4 0y5-my6-my7 2 y1 4y2-y4 y5=2 y1 5y3-y6 y7=3 y1；双重简单性解决问题：步骤1:“标准”maxz=-12 Y1-16 Y2-15y 3 0y4 0y5-2 Y1-4 Y2 Y4=-2-2 Y1-5 Y3 Y5=-3 Y1确定基本变量：=min/akj，akj0=-15/-5围绕主元素akr确定初等行变换。双简单表2 ci-12-16-15 0 CB y1 y3 y4 y5 0 y4-2-4 0-15 y3 3 3/5 2/5 0 1 0-1/5-6-16 0确定输入基本变量，双简单表3 ci-12-16-15 0 CB b y

11、1 y2 y3 y4 y5-12 y1 1 1 2 0-1/2 0-15 y3 1/5 0-4/5 1 1/5-1/5 0差异：想法不同，步骤不同。一般简易法：原问题保持基本可行解，直到大邱问题通过基本解得到基本可行解为止。(威廉莎士比亚，温斯顿，核电站，核电站，核电站，核电站，核电站)，双重简易法的要点，1，简易法的一个(利用原文制对偶问题的性质解决)不是解决原文制对偶问题的简易法。(或针对原始问题)2，适用范围(适用条件非常苛刻):(1)原始问题约束0；(2)目标函数价值系数max函数和Ci0(原始问题的双重问题基本上是可行的解决方案)。无需引入人工变量，简化计算。双精简方法：将双问题保持

12、为基本可执行解决方案，直到原始问题从基本解决方案转变为基本可执行解决方案。解决问题的想法正好相反。2、具体故障诊断步骤(1)最佳标准一般简易性：当前表中所有变量的检查数(主要是非标准变量)0。得到对应于大邱问题的基本可行解法。双重简单方法：当前表中的所有bi0。就像获得原始问题的基本可行解决方案一样。(2)主要因素的确定(基本变量内外)1)顺序不同。一般简易方法：首先确定基本变量，然后确定基本变量。(先进先出后纵向后横向)双简单方法：先确定基本变量，然后确定基本变量。(先进先出后纵向)2)确定基本变量的一般简单方法：确定max(j0)=k，xk作为主变量。(第一水平对比度)双精简方法：将min/akj、akj0=、akj确定为主变量。(两阶段横向对比)，3)确定基本变量的一般简单性：确定minbi/aik、aik0=、ajk作为主变量。(垂直对比的第二阶段)双重简单方法：确认min bj0=bk，bk是主要变数。(首先垂直对比)穿着都是水平对比，基础都是垂直对比，双重简易法阶段记忆的要点，1，最佳BI (0)。2、先进先出后出；3、基本纵横比bi；入口水平比率(aik 0)