廊坊中小企业网站制作,wordpress get cat,app大全,表白网页制作网站一、线性规划对偶问题定义
原问题#xff1a; 对偶问题#xff1a; #xff08;1#xff09;若一个模型为目标求 “极大”#xff0c;约束为“小于等于” 的不等式#xff0c;则它的对偶模型为目标求“极小”#xff0c;约束是“大于等于”的不等式。即“Max#xff0…一、线性规划对偶问题定义
原问题 对偶问题 1若一个模型为目标求 “极大”约束为“小于等于” 的不等式则它的对偶模型为目标求“极小”约束是“大于等于”的不等式。即“Max ≤”和“Min≥”相对应。
2从约束系数矩阵看一 个模型中为则另一个模型中为AT 。一个模型是m个约束、 n个变量则它的对偶模型为 n个约束、m个变量。
3从数据b、c的位置看在两个规划模型中b和c的位置对换。
4两个规划模型中的变量皆非负。 一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。 对于非对称形式的规划可以按照下面的对应关系直接给出其对偶规划。
1将模型统一为“Max≤”或“Min≥” 的形式对 于其中的等式约束按下面2、3中的方法处理。
2若原规划的某个约束条件为等式约束则在对偶规划中与此约束对应的那个变量取值没有非负限制。
3若原规划的某个变量的值没有非负限制则在对偶问题中 与此变量对应的那个约束为等式。 二、对偶定理与影子价格
定理(弱对偶定理 若 x,y 分别为LP) 和DP的可行解 那么。 推论:设LP有可行解那么若LP 无有界最优解则DP无可行解。定理 (最优性准则定理) 若 ,分别(LP),(DP)的可行解,且那么 ,分别为(LP)和(DP) 的最优解。定理(主对偶定理) 若(LP)有最优解则(DP)也有最优解。反之也成立且最优值相等。
影子价格是一个向量它的分量表示最优目标值随相应资源数量变化的变化率。 影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力考虑增加设备就应该从影子价格高的设备入手。这样可以用较少的局部努力获得较大的整体效 益。
三、对偶单纯形法
1、基本思想
从原规划的一个基本解出发此基本解不一定可行但它对应着一个对偶可行解检验数非正所以也可以说是从 一个对偶可行解出发然后检验原规划的基本解是否可行即是否有负的分量如果有小于零的分量则进行迭代求另一个基本解此基本解对应着另一个对偶可行解检验数非正。
如果得到的基本解的分量皆非负则该基本解为最优解。也就是说对偶单纯形法在迭代过程中始终保持对偶解的可行性即检验数非正使原规划的基本解由不可行逐步变为可行当同时得到对偶规划与原规划的可行解时便得到原规划的最优解
什么情况下使用对偶单纯性法呢
在初始计算中即对偶可行但是由于,所以所以原问题不可行。
应用前提有一个基其对应的基满足:
1 单纯形表的检验数行全部非正对偶可行
2 变量取值可有负数非可行解。
注通过矩阵行变换运算使所有相应变量取值均为非负数即得到最优单纯形表。
2、步骤
1建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转 2。
2若,则得到最优解,停止;否则,若有则选k行的基变量为出基变量,转3。
3若所有(j 1,2,…,n)则原问题无可行解,停止(因为以任何为主元做主元消去时都不可能使变为正数); 否则,若有则选 那么为进基变量,转4。
4以为主元,作矩阵行变换使其变为1,该列其他元变为0,利用主元消去计算Ab转(2)。
的选取保证新的检验数,因为 主元消去运算后对偶问题的目标函数值减小至少不增大因为 由于故,即
注由于主元消去前与同为负数因此主元消去后右端列第k个分量变成正数这有利于基本解向着满足可行性的方向转化。 3、例子
