《运筹学复习资料(1)》由会员分享，可在线阅读，更多相关《运筹学复习资料(1)（11页珍藏版）》请在金锄头文库上搜索。
1、运筹学复习一、单纯形方法（表格、人工变量、基础知识）线性规划解的情况：唯一最优解、多重最优解、无界解、无解。其中，可行 域无界，并不意味着目标函数值无界。无界可行域对应着解的情况有：唯一最优解、多重最优解、无界解。有界可 行域对应唯一最优解和多重最优解两种情况。线性规划解得基本性质有：满足线性规划约束条件的可行解集（可行域）构 成一个凸多边形；凸多边形的顶点（极点）与基本可行解一一对应（即一个基本 可行解对应一个顶点）；线性规划问题若有最优解，则最优解一定在凸多边形的 某个顶点上取得。单纯形法解决线性规划问题时，在换基迭代过程中，进基的非基变量的选择 要利用比值法，这个方法是保证进基后的单纯型
2、依然在解上可行。换基迭代要求 除了进基的非基变量外，其余非基变量全为零。检验最优性的一个方法是在目标函数中，用非基变量表示基变量。要求检验 数全部小于等于零。“当X由0变到45/2时，x首先变为0,故X为退出基变量。”这句话是最 133小比值法的一种通俗的说法，但是很有意义。这里，X为进基变量，x3为出基变 量。将约束方程化为每个方程只含一个基变量,目标函数表示成非基变量的函数。单纯型原理的矩阵描述。在单纯型原理的表格解法中,有一个有趣的现象就是,单纯型表中的某一列 的组成的列向量等于它所在的单纯型矩阵的最初的基矩阵的 m*m 矩阵与其最初 的那一列向量的乘积。最初基变量对应的基矩阵的逆矩阵。
3、这个样子：1 0P 二 B -1P 二 0 12 2 20 0所有的检验数均小于或等于零，有最优解。但是如果出现非基变量的检验数为0，则有无穷多的最优解，这时应该继续迭代。解的结果应该是：X*= aX *+（1-a）X * （0=a0,且所有的a 0,对于极小化问题用+M）,这样只要基变量中还存在人工变量，目标函数就不可能实现极值。两阶段法原理：第一阶段是据给定的问题构造其辅助问题，为原问题求初始基本可行解。加上人工变量后，要求的就是人工变量退出，辅助问题是人工变量 之和的最小值必须为零。第二阶段是将第一阶段求出的最优解，作为第二阶段的初始基本可行解，然后在原问题的目标函数下进行优化，以决定原
4、问题的最优解。注意：单纯形法中1每一步运算只能用矩阵初等行变换2表中第3列(b列)的数总应保持非负($0)；3当所有检验数均非正(W0)时，得到最优单纯形表。若直接对目标求最 h,要求所有检验数均非负；4当最优单纯形表存在非基变量对应的检验数为零时，可能存在无穷多解； 5关于退化和循环。如果在一个基本可行解的基变量中至少有一个分量xB=0 (i=1,2,m)，则称此基本可行解是退化的基本可行解。一般情况下，退 化的基本可行解(极点)是由若干个不同的基本可行解(极点)在特殊情况下合 并成一个基本可行解(极点)而形成的。退化的结构对单纯形迭代会造成不利的 影响。可能出现以下情况：进行进基、出基变换
5、后，虽然改变了基，但没有改变 基本可行解(极点)，目标函数当然也不会改进。进行若干次基变换后，才脱离 退化基本可行解(极点)，进入其他基本可行解(极点)。这种情况会增加迭代次 数，使单纯形法收敛的速度减慢。在特殊情况下，退化会出现基的循环，一旦 出现这样的情况，单纯形迭代将永远停留在同一极点上，因而无法求得最优解。 二、对偶问题和灵敏度分析对偶问题的基本性质：对偶问题(D)的对偶问题，是原问题(P)；若X/是问题 (P)的一可行解，丫/是问题(D)的一个可行解，则有:CX/WY/b。若X*,Y*分别为问 题(P)和问题(D)的可行解，且CX*=Y*b；则X*和Y*分别为问题(P)和问题(D)的
6、最 优解。若问题(P)的目标函数值Z无上界，则问题(D)无可行解；若问题(D)的目 标函数值W无下界，则问题(P)无可行解。对偶定理：若问题(P)和问题(D) 之一有最优解，则另一个问题也一定有最优解，且目标函数值相等。由对偶定理可知，从原问题的最终单纯表中可直接得到其对偶问题的最优 解。在两个互为对偶的线性规划中，可任选一个进行求解。若X*, Y*分别为问题(P)和问题(D)的可行解，且CX*=Y*b；则，X*和Y*分别为 问题(P)和问题(D)的最优解。用对偶性质重新解释单纯形法。单纯形法：在整个迭代过程中，始终保持该问题解的可行性（即满足b，= B-1b 0），而其对偶问题的互补解初始时
7、并不满足可行性条件（即检验数不 完全部小于等于0）;当不可行性完全消失（即满足勺=-C产p W0）时，原问题 和对偶问题同时达到最优。对偶单纯形法：在整个迭代过程中，始终保持其对偶问题解的可行性（即 尢之-CBB-iP W0）,而该问题的初始解并不满足可行性条件（即不完全部大于等于 j j B j0）;当不可行性完全消失（即满足b，= B-ib 0 ）时，原问题和对偶问题同时达 到最优。对偶单纯形法步骤：列出初始单纯形表，保证所有的检验数尢=C -CbB-iPj 0，则获得最优解，否则下一步；基变换首先确定退出基变量，其次决定进入基变量， 然后求新的基本可行 解。返回到（2）。影子价格（对偶问
8、题的经济解释）三种资源A、B、C,价格为丫*=（7/2,0,1/2）,三种资源剩余量分别为 （0,25/2,0）,目标函数：W =7/2X45 +0X80 +1/2X90 = 405/2。经济意义：反映了资源与总收益之间的关系，即当第i种资源每增加一个单 位时，在其他条件不变的情况下，该资源对目标值的贡献就是y。i灵敏度分析研究线性规划中，aCj的变化对最优解的影响。目标函数系数C （价格）变化的灵敏度分析：C的变化导致检验数的变化， 如果新的检验数小于等于零，则原来的解依然是最优解；如果新的检验数大于零， 那么新的问题还没有取到最优解，还需要进一步运算才行。CN-CBb-in 0是判断 是否继续的标准。结论1：若C是非基变量的系数，则 当c的改变量iiAc在范围Ac 0, p g N Ac min-j | a b划去第t列，第k行的产量调整为a-b ；k tk t如果a 0,d-=0表明超额完成预定指标； d-0, d+=0表明未达到预定指标；d+ =d- =0表明恰好完成预定指标。在新的规划问题中，需要添加一个目标约束，目标约束的形式由其具体要完成的目标表示，比如，原来的线性规划的目标函数是MaxZ=8x + 6x，现在的新12的线性规
