《2016运筹学复习资料》由会员分享，可在线阅读，更多相关《2016运筹学复习资料（9页珍藏版）》请在金锄头文库上搜索。
1、运筹学复习运筹学复习一、单纯形方法（表格、人工变量、基础知识）一、单纯形方法（表格、人工变量、基础知识）线性规划解的情况：唯一最优解、多重最优解、无界解、无解唯一最优解、多重最优解、无界解、无解。其中，可可行域无界，并不意味着目标函数值无界行域无界，并不意味着目标函数值无界。无界可行域对应着解的情况有：唯一最优解、多重最优解、无界解。有界可行域对应唯一最优解和多重最优解两种情况。线性规划解得基本性质有：满足线性规划约束条件的可行解集（可行域）构成一个凸多边形；凸多边形的顶点（极点）与基本可行解一一对应（即一个基本可行解对应一个顶点） ；线性规划问题若有最优解，则最优解一定在凸多边形的某个顶点上
2、取得。单纯形法解决线性规划问题时，在换基迭代过程中，进基的非基变量的选择要利用比值法，这个方法是保证进基后的单纯型依然在解上可行。换基迭代要求除了进基的非基变量外，其余非基变量全为零。检验最优性的一个方法是在目标函数中，用非基变量表示基变量。要求检验数全部小于等于零。“当 x1由 0 0 变到变到 45/245/2 时，x3首先首先变为 0，故 x3为退出基变量。 ”这句话是最小比值法的一种通俗的说法，但是很有意义。这里，x1为进基变量，x3为出基变量。将约束方程化为每个方程只含一个基变量，目标函数表示成非基变量的函数。单纯型原理的矩阵描述。在单纯型原理的表格解法中，有一个有趣的现象就是，单纯
3、型表中的某一列的组成的列向量等于它所在的单纯型矩阵的最初的基矩阵的 m*m 矩阵与其最初的那一列向量的乘积。最初基变量对应的基矩阵的逆矩阵。这个样子：1 2221 0 -3 825 8 0 1 01 0 0 1 85 8PB P 所有的检验数均小于或等于零，有最优解。但是如果出现非基变量的检验数为 0，则有无穷多的最优解，这时应该继续迭代。解的结果应该是：X*= aX1*+(1-a)X2* （00,且所有的 aij 0,对于极小化问题用+M),这样只要基变量中还存在人工变量,目标函数就不可能实现极值。两阶段法原理：第一阶段是据给定的问题构造其辅助问题，为原问题求初始基本可行解。加上人工变量后，
4、要求的就是人工变量退出，辅助问题是人工变量之和的最小值必须为零。第二阶段是将第一阶段求出的最优解，作为第二阶段的初始基本可行解，然后在原问题的目标函数下进行优化，以决定原问题的最优解。注意：单纯形法中1每一步运算只能用矩阵初等行变换；2表中第 3 列(b列)的数总应保持非负（0） ；3当所有检验数均非正（0）时，得到最优单纯形表。若直接对目标求最 h，要求所有检验数均非负；4 当最优单纯形表存在非基变量对应的检验数为零时，可能存在无穷多解；5关于退化和循环关于退化和循环。如果在一个基本可行解的基变量中至少有一个分量xBi=0 (i=1,2,m)，则称此基本可行解是退化的基本可行解。一般情况下，
5、退化的基本可行解（极点）是由若干个不同的基本可行解（极点）在特殊情况下合并成一个基本可行解（极点）而形成的。退化的结构对单纯形迭代会造成不利的影响。可能出现以下情况：进行进基、出基变换后，虽然改变了基，但没有改变基本可行解（极点） ，目标函数当然也不会改进。进行若干次基变换后，才脱离退化基本可行解（极点） ，进入其他基本可行解（极点） 。这种情况会增加迭代次数，使单纯形法收敛的速度减慢。在特殊情况下，退化会出现基的循环，一旦出现这样的情况，单纯形迭代将永远停留在同一极点上，因而无法求得最优解。二、对偶问题和灵敏度分析二、对偶问题和灵敏度分析对偶问题的基本性质：对偶问题(D)的对偶问题，是原问题
6、(P)；若 X/是问题(P)的一可行解， Y/是问题(D)的一个可行解，则有:CX/Y/b。若 X*,Y*分别为问题(P)和问题(D)的可行解，且 CX*=Y*b；则 X*和 Y*分别为问题(P)和问题(D)的最优解。若问题若问题(P)(P)的目标函数值的目标函数值 Z Z 无上界，则问题无上界，则问题(D)(D)无可行解；若问题无可行解；若问题(D)(D)的目标函数值的目标函数值 W W 无下界，则问题无下界，则问题(P)(P) 无可行解。无可行解。对偶定理：若问题若问题(P)(P)和问题和问题（D D）之一有最优解，则另一个问题也一定有最优解，且目标函数值相等。）之一有最优解，则另一个问题
7、也一定有最优解，且目标函数值相等。由对偶定理可知，从原问题的最终单纯表中可直接得到其对偶问题的最优解。在两个互为对偶的线性规划中，可任选一个进行求解。若X*,Y*分别为问题(P)和问题(D)的可行解，且CX*=Y*b；则，X*和 Y*分别为问题(P)和问题(D)的最优解。 用对偶性质重新解释单纯形法。用对偶性质重新解释单纯形法。单纯形法：在整个迭代过程中，始终保持该问题解的可行性（即满足 ） ，而其对偶问题的互补解初始时并不满足可行性条件（即检验数01bBb不完全部小于等于 0） ；当不可行性完全消失（即满足 0）时，原问1 jjBjcC B P题和对偶问题同时达到最优。对偶单纯形法：在整个迭
8、代过程中，始终保持其对偶问题解的可行性（即0） ，而该问题的初始解并不满足可行性条件（即不完全部大于等1 jjBjcC B P于 0） ；当不可行性完全消失（即满足）时，原问题和对偶问题同01bBb时达到最优。对偶单纯形法步骤：列出初始单纯形表，保证所有的检验数;01 jBjjPBCc检验：若满足，则获得最优解，否则下一步;01bBb基变换首先确定退出基变量，其次决定进入基变量， 然后求新的基本可行解。返回到（2） 。影子价格（对偶问题的经济解释）三种资源 A、B、C，价格为Y*=(7/2,0,1/2)，三种资源剩余量分别为（0,25/2,0） ，目标函数：W =7/245 +080 +1/2
9、90 = 405/2。经济意义：反映了资源与总收益之间的关系，即当第 i 种资源每增加一个单位时，在其他条件不变的情况下，该资源对目标值的贡献就是 yi。灵敏度分析研究线性规划中，的变化对最优解的影响。jiijcba,目标函数系数 C（价格）变化的灵敏度分析：C 的变化导致检验数的变化，如果新的检验数小于等于零，则原来的解依然是最优解；如果新的检验数大于零，那么新的问题还没有取到最优解，还需要进一步运算才行。 01NBCCBN是判断是否继续的标准。内时，最优解不变在范围的改变量当是非基变量的系数，则：若1结论iiiii cccc内时，最优解不变,0|min,0|max在范围的改变量是基变量的系
10、数，则当：若2结论 NPaacNPaacccjij ijj ijij ijjiii对于基变量的变化，变化值如果小于检验数的相反数，则最优解不变。基便量系数发生改变将改变所有变量检验数。增加一个新变量的灵敏度分析：如果该行的检验数为小于等于零，那么新变量为非基变量，此表达到最优。反之，就要迭代求解。如何求检验数很重要，要用到第一章中的知识。这里要了解各项的含义。比较。0与11 1 nBnPBCc增加一个新约束的灵敏度分析，将最优解代入新的约束中，若满足新约束，则原最优解不变；若不满足新约束，则原最优解改变，将新增的约束条件添入最终的单纯形表中，并增加一个基变量，继续迭代。添加新约束后，有时要对原
11、问题所对偶单纯形法，并且要消元构造单位阵，基矩阵。新约束条件的常数新约束条件的常数项至少为多少时不影响原最优解？项至少为多少时不影响原最优解？对偶单纯形法非常重要！对偶单纯形法非常重要！三三. .运输问题运输问题运输问题的一般描述：设某种物资有 m 个产地 A1 A2,Am ,其产量分别为 a1 a2,am ,另外有 n 个销地 B1 B2,Bn ,其销量分别为 b1 b2,bn ,已知从 Ai 到 Bj 的单位运费为 Cij(i=1,2,m;j=1,2,n)，试问应如何组织调运才能使总运费最低。产销平衡运输问题模型特点：由平衡条件易知：m+n 个方程线性相关，而任意 m+n 1 个方程线性无
12、关；基变量的个数为 m+n 1，非基变量的个数为mn-（m+n1）=（m1） （n 1）1，有无限多方案；系数矩阵只包括 1 和0。有产销不平衡问题，a 的和大于 b 的和，为产大于销的问题。解决运输问题应该运用运输单纯型法，步骤是：（1）确定初始基本可行解（初始方案） ，这里有最小元素法和元素差额法。最小元素法：列出运输表，表中 xij位置暂先空着，在表中找出单位运价最小者 Ckt，取 xkt=minak，bt把 xkt的值填在相应的格内(若有几个单位运价同时达到最小，就任取其中之一） ；如果 akbt划去第 t 列，第 k 行的产量调整为ak-bt；如果 ak0,d-=0 表明超额完成预定
13、指标；d-0,d+=0 表明未达到预定指标；d+ =d- =0 表明恰好完成预定指标。在新的规划问题中，需要添加一个目标约束，目标约束的形式由其具体要完成的目标表示，比如，原来的线性规划的目标函数是 MaxZ=8x1 + 6x2，现在的新的线性规划中就要添加这样的目标约束：8x1 + 6x2+d-d+=140。意思就是：尽量达到这个目标，如果达不到，加上一个便可以达到了。目标规划中，重要特征如下：增加了目标约束；目标中只出现偏差变量且为求极小化问题；d+d-=0。单目标规划求解：用单纯形法求满意解,注意求极小化问题最优性条件是检验数全部大于等于零。多目标规划求解中级别相同的多目标规划的数学模型
14、：实现利润目标122（百元），产品 A 的产量不多于 10，这时设：di+,di-(i=1,2)分别为超过目标值的部分，及未完成目标值的部分。目标函数是 minZ=d1-+d2+目标约束是：8x1 + 6x2+d1- d1+=122 和 x1+d2-d2+=10。这里，分析一下语句，实现目标利润为 122 百元，但是有可能达不到这个数，所以，尽量达不到的负偏差变量要小。A 的产量不多于 10，即便多于 10，也没关系，但是正偏差变量要尽量小。因此，得目标函数。多目标规划求解中具有优先级的多目标规划数学模型：P1:充分利用设备有效台时，不加班；P2:产品 B 的产量不多于 4；P3:实现利润 1
15、30（百元） 。最重要的是 1 号，在 2 号和 3 号完不成的情况下，也要优先保证 1 号完成。但是，并不是说，1 号完成之后，2 号和 3 号才能完成。在实际生活中，也有 1号未完成但是 2 号和 3 号完成的情况。模型约束：4x1 + 2x2+ d1- - d1+ = 60 x2 + d2- - d2+ = 4 8x1 + 6x2+ d3- - d3+ = 130 2x1 + 4x2 48 x1，x2，di+,di-(i=1,2,3) 0目标函数：MIN Z(x)= P1（d1- + d1+）+ P2 d2+ P3d3-在这里，1 号目标是正负偏差量之和，就是取要恰好达到之意。图解法求解目标规划：按照上面的规划，可以有下列步骤：（1）根据系统约束，确定可行域；（2）不考虑偏差，即：di+=di-=0（i=1,2,3)，然后按顺序作出目标约束相应的直线，并标出di+0,di-0 的方向；（3）按优先顺序找出该目标的满意解。目标规划的目标：（1）决策人希望恰好实现预定的第 i 个目标，Min Z= di+ + di-；（2）决策人不希望超过预定的第 i 个目标，MinZ= di+；（3）决策人希望超过预定的第 i 个目标，minZ=di-。整数规划：线性规划中要求决策变量全部或部分为整数。分为以下，纯整数规划:所有决策变量 xj(j=1,2,n)均
