2016运筹学复习资料

《2016运筹学复习资料》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、运筹学复习一、单纯形方法（表格、人工变量、基础知识）线性规划解的情况：唯一最优解、多重最优解、无界解、无解。其中，可行域无界，并不意味着目标函数值无界。无界可行域对应着解的情况有：唯一最优解、多重最优解、无界解。有界可行域对应唯一最优解和多重最优解两种情况。线性规划解得基本性质有：满足线性规划约束条件的可行解集（可行域）构成一个凸多边形；凸多边形的顶点（极点）与基本可行解一一对应（即一个基本可行解对应一个顶点）；线性规划问题若有最优解，则最优解一定在凸多边形的某个顶点上取得。单纯形法解决线性规划问题时，在换基迭代过程中，进基

2、的非基变量的选择要利用比值法，这个方法是保证进基后的单纯型依然在解上可行。换基迭代要求除了进基的非基变量外，其余非基变量全为零。检验最优性的一个方法是在目标函数中，用非基变量表示基变量。要求检验数全部小于等于零。“当x1由0变到45/2时，x3首先变为0，故x3为退出基变量。”这句话是最小比值法的一种通俗的说法，但是很有意义。这里，x1为进基变量，x3为出基变量。将约束方程化为每个方程只含一个基变量，目标函数表示成非基变量的函数。单纯型原理的矩阵描述。在单纯型原理的表格解法中，有一个有趣的现象就是，单纯型表中的某一列的组成的

3、列向量等于它所在的单纯型矩阵的最初的基矩阵的m*m矩阵与其最初的那一列向量的乘积。最初基变量对应的基矩阵的逆矩阵。这个样子：所有的检验数均小于或等于零，有最优解。但是如果出现非基变量的检验数为0，则有无穷多的最优解，这时应该继续迭代。解的结果应该是：X*=aX1*+(1-a)X2*　　　（0<=a<=1）说明：最优解有时不唯一，但最优值唯一；在实际应用中，有多种方案可供选择；当问题有两个不同的最优解时，问题有无穷多个最优解。无最优解的情况就是：应该进基的变量所对应的列的系数全部小于零。若存在某个λj>0,且所有的aij<0，

4、则不存在有界最优解。人为地构造一个单位矩阵来充当初始可行基，再通过单纯形迭代将它们逐个地从基变量中替换出来。若经过基的变换，基变量中不再含有非零的人工变量，这表示原问题有解。若在最终表中当所有Cj-zj≤0，而在其中还有某个非零人工变量，这表示无可行解。大M法原理核心：打破原来的约束，再设法恢复。大M法基本思想：假定人工变量在基变量中的价值系数为一个绝对值很大的-M(M>>0,对于极小化问题用+M),这样只要基变量中还存在人工变量,目标函数就不可能实现极值。两阶段法原理：第一阶段是据给定的问题构造其辅助问题，为原问题求初始基

5、本可行解。加上人工变量后，要求的就是人工变量退出，辅助问题是人工变量之和的最小值必须为零。第二阶段是将第一阶段求出的最优解，作为第二阶段的初始基本可行解，然后在原问题的目标函数下进行优化，以决定原问题的最优解。注意：单纯形法中1．每一步运算只能用矩阵初等行变换；2．表中第3列(b列)的数总应保持非负（≥0）；3．当所有检验数均非正（≤0）时，得到最优单纯形表。若直接对目标求最h，要求所有检验数均非负；4．当最优单纯形表存在非基变量对应的检验数为零时，可能存在无穷多解；5．关于退化和循环。如果在一个基本可行解的基变量中至少有一

6、个分量xBi=0(i=1,2,…,m)，则称此基本可行解是退化的基本可行解。一般情况下，退化的基本可行解（极点）是由若干个不同的基本可行解（极点）在特殊情况下合并成一个基本可行解（极点）而形成的。退化的结构对单纯形迭代会造成不利的影响。可能出现以下情况：①进行进基、出基变换后，虽然改变了基，但没有改变基本可行解（极点），目标函数当然也不会改进。进行若干次基变换后，才脱离退化基本可行解（极点），进入其他基本可行解（极点）。这种情况会增加迭代次数，使单纯形法收敛的速度减慢。②在特殊情况下，退化会出现基的循环，一旦出现这样的情况，

7、单纯形迭代将永远停留在同一极点上，因而无法求得最优解。二、对偶问题和灵敏度分析对偶问题的基本性质：对偶问题(D)的对偶问题，是原问题(P)；若X/是问题(P)的一可行解，Y/是问题(D)的一个可行解，则有:CX/≤Y/b。若X*,Y*分别为问题(P)和问题(D)的可行解，且CX*=Y*b；则X*和Y*分别为问题(P)和问题(D)的最优解。若问题(P)的目标函数值Z无上界，则问题(D)无可行解；若问题(D)的目标函数值W无下界，则问题(P)无可行解。对偶定理：若问题(P)和问题（D）之一有最优解，则另一个问题也一定有最优解，且

8、目标函数值相等。由对偶定理可知，从原问题的最终单纯表中可直接得到其对偶问题的最优解。在两个互为对偶的线性规划中，可任选一个进行求解。若X*,Y*分别为问题(P)和问题(D)的可行解，且CX*=Y*b；则，X*和Y*分别为问题(P)和问题(D)的最优解。用对偶性质重新解释单纯形法。单纯形法：