什么情况下不能用对偶单纯形法?
因为对偶问题的约束方程中加入了松弛变量,而且松弛变量的系数矩阵都是负的,不能构成单位矩阵。如果用人工变量法,这个问题可以解决,但是太麻烦了。两端乘以-1,就可以变成单位数组,非常简单。
灵敏度分析中原问题和对偶问题是否仍为可行解如何判断?
测试数是正则对偶问题的不可行解,用简单线法迭代,如果bamplt;0,用对偶单纯形法迭代原问题的不可行解。
什么是互补解?
互补解是运筹学中的一个概念。
定义:在每次迭代中,单纯形法为原问题生成一个角点解X,为对偶问题生成一个互补解Y。并且满足cxby。
特征:如果X不是原问题的最优解,那么Y不是对偶问题的可行解。
单纯形计算c是什么?
对偶单纯形法1954年,美国数学家c·莱姆克提出了对偶单纯形法。单纯形法是通过迭代从原问题的一个可行解到另一个可行解,直到测试数满足最优性条件。
对偶单纯形规则是从满足对偶可行条件开始,通过迭代逐步搜索原问题的最优解。在迭代过程中,基本解的对偶可行性始终保持,不可行性逐渐消失。设原问题为min{cx|axb,x≥0},其对偶问题为max{yb|ya≤c}。当...的时候
当原问题的一个基本解满足最优性条件时,其检验数CB-1A-C≤0。即ycbb-1(称为单纯形算子)是对偶问题的可行解。所谓对偶可行性满足,即其测试数满足最优性条件。所以在保持双重可行的前提下,一旦基本解变得可行,也是最优解。
单纯形法与对偶单纯形法的区别?
单纯形法是求解线性规划问题的主要方法,对偶单纯形法将单纯形法应用于对偶问题的计算,对偶单纯形法提高了求解线性规划问题的效率,具有以下优点:
初始基础解可能不可行。当检验数均为负数时,可以不添加人工变量进行基变换,从而简化计算。对于变量多于约束的线性规划问题,对偶单纯形法可以减少计算量,在灵敏度分析中使用对偶单纯形法和求解整数规划的割平面法有时是合适的。
问题标准化后,价值系数根本不是正的;所有的约束都是不等式。