运筹学复习资料

1、. .运筹学复习一、单纯形方法表格、人工变量、根底知识线性规划解的情况：唯一最优解、多重最优解、无界解、无解。其中，可行域无界，并不意味着目标函数值无界。无界可行域对应着解的情况有：唯一最优解、多重最优解、无界解。有界可行域对应唯一最优解和多重最优解两种情况。线性规划解得根本性质有：满足线性规划约束条件的可行解集可行域构成一个凸多边形；凸多边形的顶点极点与根本可行解一一对应即一个根本可行解对应一个顶点；线性规划问题假设有最优解，那么最优解一定在凸多边形的某个顶点上取得。单纯形法解决线性规划问题时，在换基迭代过程中，进基的非基变量的选择要利用比值法，这个方法是保证进基后的单纯型依然在解上可行。换

2、基迭代要求除了进基的非基变量外，其余非基变量全为零。检验最优性的一个方法是在目标函数中，用非基变量表示基变量。要求检验数全部小于等于零。“当x1由0变到45/2时，x3首先变为0，故x3为退出基变量。这句话是最小比值法的一种通俗的说法，但是很有意义。这里，x1为进基变量，x3为出基变量。将约束方程化为每个方程只含一个基变量，目标函数表示成非基变量的函数。单纯型原理的矩阵描述。在单纯型原理的表格解法中，有一个有趣的现象就是，单纯型表中的某一列的组成的列向量等于它所在的单纯型矩阵的最初的基矩阵的m*m矩阵与其最初的那一列向量的乘积。最初基变量对应的基矩阵的逆矩阵。这个样子：所有的检验数均小于或等于

3、零，有最优解。但是如果出现非基变量的检验数为0，那么有无穷多的最优解，这时应该继续迭代。解的结果应该是：X*= aX1*+(1-a)X2*0<=a<=1说明：最优解有时不唯一，但最优值唯一；在实际应用中，有多种方案可供选择；当问题有两个不同的最优解时，问题有无穷多个最优解。无最优解的情况就是：应该进基的变量所对应的列的系数全部小于零。假设存在某个j>0,且所有的aij <0，那么不存在有界最优解。人为地构造一个单位矩阵来充当初始可行基，再通过单纯形迭代将它们逐个地从基变量中替换出来。假设经过基的变换，基变量中不再含有非零的人工变量，这表示原问题有解。假设在最终表中当所有

4、Cj-zj 0 ，而在其中还有某个非零人工变量，这表示无可行解。大M法原理核心：打破原来的约束，再设法恢复。大M法根本思想：假定人工变量在基变量中的价值系数为一个绝对值很大的-M (M>>0,对于极小化问题用+M),这样只要基变量中还存在人工变量,目标函数就不可能实现极值。两阶段法原理：第一阶段是据给定的问题构造其辅助问题，为原问题求初始根本可行解。加上人工变量后，要求的就是人工变量退出，辅助问题是人工变量之和的最小值必须为零。第二阶段是将第一阶段求出的最优解，作为第二阶段的初始根本可行解，然后在原问题的目标函数下进展优化，以决定原问题的最优解。注意：单纯形法中1每一步运算只能用矩

5、阵初等行变换；2表中第3列(b列)的数总应保持非负0；3当所有检验数均非正0时，得到最优单纯形表。假设直接对目标求最h，要求所有检验数均非负；4当最优单纯形表存在非基变量对应的检验数为零时，可能存在无穷多解；5关于退化和循环。如果在一个根本可行解的基变量中至少有一个分量xBi=0 (i=1,2,m)，那么称此根本可行解是退化的根本可行解。一般情况下，退化的根本可行解极点是由假设干个不同的根本可行解极点在特殊情况下合并成一个根本可行解极点而形成的。退化的构造对单纯形迭代会造成不利的影响。可能出现以下情况：进展进基、出基变换后，虽然改变了基，但没有改变根本可行解极点，目标函数当然也不会改进。进展假

6、设干次基变换后，才脱离退化根本可行解极点，进入其他根本可行解极点。这种情况会增加迭代次数，使单纯形法收敛的速度减慢。在特殊情况下，退化会出现基的循环，一旦出现这样的情况，单纯形迭代将永远停留在同一极点上，因而无法求得最优解。二、对偶问题和灵敏度分析对偶问题的根本性质：对偶问题(D)的对偶问题，是原问题(P)；假设X/是问题(P)的一可行解， Y/是问题(D)的一个可行解，那么有:CX/Y/b。假设X*,Y*分别为问题(P)和问题(D)的可行解，且CX*=Y*b；那么X*和Y*分别为问题(P)和问题(D)的最优解。假设问题(P)的目标函数值Z无上界，那么问题(D)无可行解；假设问题(D)的目标函

7、数值W无下界，那么问题(P) 无可行解。对偶定理：假设问题(P)和问题D之一有最优解，那么另一个问题也一定有最优解，且目标函数值相等。由对偶定理可知，从原问题的最终单纯表中可直接得到其对偶问题的最优解。在两个互为对偶的线性规划中，可任选一个进展求解。假设X*,Y*分别为问题(P)和问题(D)的可行解，且CX*=Y*b；那么，X*和Y*分别为问题(P)和问题(D)的最优解。用对偶性质重新解释单纯形法。单纯形法：在整个迭代过程中，始终保持该问题解的可行性即满足，而其对偶问题的互补解初始时并不满足可行性条件即检验数不完全部小于等于0；当不可行性完全消失即满足0时，原问题和对偶问题同时到达最优。对偶单

8、纯形法：在整个迭代过程中，始终保持其对偶问题解的可行性即0，而该问题的初始解并不满足可行性条件即不完全部大于等于0；当不可行性完全消失即满足时，原问题和对偶问题同时到达最优。对偶单纯形法步骤：列出初始单纯形表，保证所有的检验数;检验：假设满足，那么获得最优解，否那么下一步;基变换首先确定退出基变量，其次决定进入基变量，然后求新的根本可行解。返回到2。影子价格对偶问题的经济解释三种资源A、B、C，价格为Y*=(7/2,0,1/2)，三种资源剩余量分别为0,25/2,0，目标函数：W =7/2×45 +0×80 +1/2×90 = 405/2。经济意义：反映了资源与总

9、收益之间的关系，即当第i种资源每增加一个单位时，在其他条件不变的情况下，该资源对目标值的奉献就是yi。灵敏度分析研究线性规划中，的变化对最优解的影响。目标函数系数C价格变化的灵敏度分析：C的变化导致检验数的变化，如果新的检验数小于等于零，那么原来的解依然是最优解；如果新的检验数大于零，那么新的问题还没有取到最优解，还需要进一步运算才行。是判断是否继续的标准。对于基变量的变化，变化值如果小于检验数的相反数，那么最优解不变。基便量系数发生改变将改变所有变量检验数。增加一个新变量的灵敏度分析：如果该行的检验数为小于等于零，那么新变量为非基变量，此表到达最优。反之，就要迭代求解。如何求检验数很重要，要

10、用到第一章中的知识。这里要了解各项的含义。增加一个新约束的灵敏度分析，将最优解代入新的约束中，假设满足新约束，那么原最优解不变；假设不满足新约束，那么原最优解改变，将新增的约束条件添入最终的单纯形表中，并增加一个基变量，继续迭代。添加新约束后，有时要对原问题所对偶单纯形法，并且要消元构造单位阵，基矩阵。新约束条件的常数项至少为多少时不影响原最优解？对偶单纯形法非常重要！三.运输问题运输问题的一般描述：设某种物资有m个产地 A1 A2,Am ,其产量分别为 a1 a2,am ,另外有n个销地 B1 B2,Bn ,其销量分别为 b1 b2,bn ,从Ai到Bj的单位运费为Cij(i=1,2,m;j

11、=1,2,n)，试问应如何组织调运才能使总运费最低。产销平衡运输问题模型特点：由平衡条件易知：m+n个方程线性相关，而任意m+n 1个方程线性无关；基变量的个数为m+n 1，非基变量的个数为mn-m+n1=m1n 11，有无限多方案；系数矩阵只包括1和0。有产销不平衡问题，a的和大于b的和，为产大于销的问题。解决运输问题应该运用运输单纯型法，步骤是：1确定初始根本可行解初始方案，这里有最小元素法和元素差额法。最小元素法：列出运输表，表中xij位置暂先空着，在表中找出单位运价最小者Ckt，取xkt=minak，bt把xkt的值填在相应的格内(假设有几个单位运价同时到达最小，就任取其中之一；如果a

12、k>bt划去第t列，第k行的产量调整为ak-bt；如果 ak<bt划去第k行，第t列的销量调整为bt-ak；如果 ak=bt划去第t列，第k行的产量调整为0，或划去第k行，第t列的销量调整为0。2检验计算所有非基变量xij的检验数位势法。位势法：首先将数字格基变量的单价Cij分解为行位ui和列位vj即：ui+vj=Cij数字格。根据方程组解出ui和vj；然后通过ui和vj计算出非基变量的检验数。通常令u1=0解方程组，得行列的位势值。其中，非基变量检验数为Cij-ui+vj。最优性条件：所有的非基变量检验数均大于等于0，假设不满足此条件转入3。3基变换方案改进。闭回路几何法：从空格

13、非基变量所在格出发，沿垂直或水平方向前进；在前进的过程中可穿过数字格、也可穿过空格，在某个适当的数字格内转弯900，经过这样假设干次转向后回到出发点，形成一个闭回路。可以证明*：每一个空格都有并且只有一条闭回路存在且唯一，其形状可能是矩形、也可能是曲折的多边形。然后确定进基变量和退基变量，进基变量就是检验数小于0的空格，退基变量是从该进基变量出发，运用闭回路法，在转角处，从起点开场标“+、“-、“+、“-，标“-的量中，最小的一个退基，减去运输量值，其余的标“+的加上该运输量值，标“-的减去该运输量值。产销不平衡问题：要虚设一个行或列，这里，(1)有数字格基变量的个数为m+n-1,如果缺少数字

14、必须添0补救；(2)当最终表中某个非基变量检验数为0时，说明该问题有两个根本可行解均为最优解。四.目标规划和整数规划目标规划分为单目标规划、多目标规划。多目标规划中有级别一样的目标规划和具有优先级目标规划。假设利润目标为140百元，此目标称之为预定目标，实际完成的量与预定目标之间可能出现偏差，通常用d+、d-d+、d-0表示，称为偏差变量。其中：d+表示超过预定指标的局部，d-表示未到达预定指标的局部。在客观条件下，最终完成的结果可能出现以下三种情况：d+>0,d-=0说明超额完成预定指标；d->0,d+=0说明未到达预定指标；d+ =d- =0说明恰好完成预定指标。在新的规划问题

15、中，需要添加一个目标约束，目标约束的形式由其具体要完成的目标表示，比方，原来的线性规划的目标函数是MaxZ=8x1 + 6x2，现在的新的线性规划中就要添加这样的目标约束：8x1 + 6x2+d-d+=140。意思就是：尽量到达这个目标，如果达不到，加上一个便可以到达了。目标规划中，重要特征如下：增加了目标约束；目标中只出现偏差变量且为求极小化问题；d+×d-=0。单目标规划求解：用单纯形法求满意解,注意求极小化问题最优性条件是检验数全部大于等于零。多目标规划求解中级别一样的多目标规划的数学模型：实现利润目标122百元，产品A的产量不多于10，这时设：di+,di-(i=1,2)分别

16、为超过目标值的局部，及未完成目标值的局部。目标函数是minZ=d1-+d2+目标约束是：8x1 + 6x2+d1- d1+=122和x1+d2-d2+=10。这里，分析一下语句，实现目标利润为122百元，但是有可能达不到这个数，所以，尽量达不到的负偏差变量要小。A的产量不多于10，即便多于10，也没关系，但是正偏差变量要尽量小。因此，得目标函数。多目标规划求解中具有优先级的多目标规划数学模型：P1:充分利用设备有效台时，不加班；P2:产品B的产量不多于4；P3:实现利润130百元。最重要的是1号，在2号和3号完不成的情况下，也要优先保证1号完成。但是，并不是说，1号完成之后，2号和3号才能完成

17、。在实际生活中，也有1号未完成但是2号和3号完成的情况。模型约束：4x1 + 2x2+ d1- d1+= 60 x2 + d2- d2+= 4 8x1 + 6x2+ d3- d3+= 130 2x1 + 4x248 x1，x2，di+,di-(i=1,2,3) 0目标函数：MIN Z(x)= P1d1- + d1+ P2 d2+ P3d3-在这里，1号目标是正负偏差量之和，就是取要恰好到达之意。图解法求解目标规划：按照上面的规划，可以有以下步骤：1根据系统约束，确定可行域；2不考虑偏差，即：di+=di-=0i=1,2,3)，然后按顺序作出目标约束相应的直线，并标出di+>0,di-&g

18、t;0的方向；3按优先顺序找出该目标的满意解。目标规划的目标：1决策人希望恰好实现预定的第i个目标，MinZ= di+ di-；2决策人不希望超过预定的第i个目标，MinZ= di+；3决策人希望超过预定的第i个目标，minZ=di-。整数规划：线性规划中要求决策变量全部或局部为整数。分为以下，纯整数规划:所有决策变量xj(j=1,2,n)均取整数；混合整数规划:局部决策变量取整数；0-1整数规划:所有决策变量只取0或1，这类变量又称为逻辑变量。经典方法是分支定界法和割平面法。分支定界法步骤：先不考虑变量的整数约束，求解相应的线性规划；分支：如果求解某一个值并非整数，那么就予以分支，比方，由于

19、x1，x2均不满足整数条件，故可由x1或x2进展分枝，使x1满足：x13 或 x14，将3< x1<4 的非整数局部割掉，于是问题B0分成了两个子问题B1,B2，然后分别求出其最优解，B1最优解:X1*=3，8/3，Z1=141/3，B2最优解X2*=4，1，Z2=14；定界：问题B2已获得整数最优解，可将Z2=14作为问题A的下界，同时将Z0=143/4作为问题A的上界。可以断定Z2=14 Z < Z0=143/4；返回到2继续对B1中的x2进展分枝，使x2满足：x22或x23将2< x2< 3之间的非整数局部割掉。于是问题B2又分成了两个子问题B3和B4再分别

20、求出其最优解。割平面法步骤：不考虑其整数条件,用单纯形法求解相应的线性规划问题，求出最终单纯形表；构造Gomory约束割平面：在最终单纯形表中，任意选择一个非整数变量如x2，写出该变量所在行的方程式：x2 + 1/2x31/2x4=5/2，将各变量的系数及常数项分解为整数与非负真分数之和；再将系数为整数的变量移到方程式左端，系数为分数的变量移到方程式右端，x2x4-2=1/2-1/2x3+1/2x4。求得Gomory约束为：1/2-1/2x3+1/2x40将Gomory约束化为方程，填入到最终单纯形表中，继续求问题的最优解。用对偶单纯性法求解。分派问题使用0-1整数规划的一种特殊类型，但是由于

21、它的形式比较特殊，所以有自己特殊的解法。有n项任务,指派n个人(广义)去完成,第i个人完成第j项任务的效率为Cij(i=1,2,n;j=1,2,n)；要求每个人只能承担一项任务,并且每一项任务都有一个人个来承担；问如何分派可以使总的效率到达最高。Cij为效率矩阵。建立数学模型：1，分派第i个人去承担第j项任务；0，不分派第i个人去承担第j项任务。要求每人只能承担一项工作，每项工作只能由一个人来承担。它是特殊的0-1规划；它是m=n，ai=bj=1的特殊运输问题；它的所有可行解的个数为n！。同解性原理：如果在效率矩阵Cij的第ii=1,2,n行列加减一个常数ki，那么新效率矩阵与原效率矩阵有一样

22、的最优解。匈牙利解法：化简效率矩阵：使其每行、每列至少有一个零元素；检验：用尽可能少的直线去覆盖所有的零元素，当覆盖线的条数n0=n 时,可转入4确定最优方案,当 n0<n 时转入下一步(3)继续化简；移动零元素：在未被直线覆盖的元素中找出最小元，对不在覆盖线上的元素减去这个最小元，在两覆盖线交点上加上这个最小元，其他元素不变。具体步骤：变换指派问题的费用矩阵，使其在各行各列都出现0元素，首先每行元素减去该行的最小元素，然后每列减去该列的最小元素；进展试指派画，从含0元素最少的行或列开场，圈出一个0元素，用表示，然后划去该所在的行和列中的其余0元素，用×表示，依次类推。假设矩阵中的的个数等于n，那么得最优解，假设矩阵中的的个数<n，那么进展第三步；做能复盖所有0元素的最小直线集合：对没有的行打号、对打号的行上所有0元素的列打号、再对打号的列上所有的行打号、重复以上步骤直到得不出新的打号为止，对没有打号的行画横线，所有打号的列画纵线，所得到的直线既是复盖所有0元素的最小直线集合；在没有被直线复盖的元素中找出最小元素，让打号的列加上这个元素，打号的行减去这个元素。求最大效率的问题，求最小效率的问题，都很重要。五.矩阵对策我们称具