《版运筹学总复习》PPT课件.ppt

2019/7/31,1,第一章复习思考题, 试述LP数学模型的组成要素及各要素的特征。,LP数学模型组成三要素： 一是决策变量； 二目标函数； 三是约束条件。,各要素特征： 决策变量是连续的； 决策变量是目标函数的线性函数； 约束条件是含有决策变量的线性不等式。,2019/7/31,2, 求解LP问题时可能出现哪几种结果？,求解LP问题有可能出现4种结果，即： 有唯一最优解； 有无穷多最优解； 有无界解； 无可行解。, 什么是LP问题的标准型式，如何将非标准型 的LP问题转化为标准型？,LP问题的标准型是： 目标函数取极大值； 约束条件取“=”号；,2019/7/31,3,资源系数必须0； 决策变量必须0,对于任意一个非标准的LP问题，可采取如下方法， 将其变换为标准型：,若目标函数为求极小值minz=CX，则令z=z，便可得到maxz=CX； 如果某约束条件的右端项（资源系数）0，则该约束条件两端同时乘“1”，使其0； 如果约束条件为“”不等式，则在不等式的左端加入一个非负的松弛变量，使其变为等式；,2019/7/31,4,如果约束条件为“”不等式，则在不等式的左端减去一个非负的剩余变量，使其变为等式； 若xj0，则令xj=xj，代入标准型，则有xj0； 若xj的正负不限，则令xj=xjx”j，而xj0，x”j0。,试述LP问题的基解、基可行解、可行解、最优解的概念以及上述解之间的相互关系。,2019/7/31,5,基解：在约束方程组中，令所有非基变量 Xm+1=xm+2=xn=0，此时，方程组有唯一 解XB=(x1,x2,xm)T，将此解加上非基变量取 0的值有X=(x1,x2,xm,0,0,0)T，称X为LP问 题的基解。,2019/7/31,6,基可行解：满足非负约束条件的解； 可行解：满足约束条件和的解； 最优解：使目标函数达到最大值的可行解；, 试述单纯形法的计算步骤，如何在单纯形表上判别问题是具有唯一最优解、无穷多最优解、无界解或无可行解。 在单纯形表中，如果所有检验数j0，基变量中不存在非零的人工变量，非基变量中也不存在等于零的检验数，此时的解为唯一最优解；如果在单纯形表中，虽然所有检验数j0，但存在某非基变量的检验数等于零，此时的解为无穷多最优解；,2019/7/31,7,如果在单纯形表中，所有检验数j0， 基变量中存在非零的人工变量，此时的 解为无可行解；如果在单纯形表中，某 检验数j0，而对应的Pj0，此时的 解为无界解。,如果LP问题的标准型式变换为求目标函数的极小化min z，则用单纯形法计算时，如何判别问题已得到最优解。,2019/7/31,8,如果LP问题的标准型式变换为求目标函数的极小化min z，则在用单纯形法计算时，用检验数j0判断问题是否得到最优，方法同极大化。, 在确定初始可行基时，什么情况下要在约束条件中增添人工变量，在目标函数中假定人工变量前的系数为（-M），其作用是什么？,2019/7/31,9,当规划模型化为标准型后，当其约束条件的系数矩阵中不存在单位矩阵时，需再添加新的人工变量。 在一个LP问题的约束条件中加入人工变量后，要求人工变量对目标函数取值不受影响，假定人工变量在目标函数中的系数为（-M，M为任意大正数），这样目标函数在实现最大化的过程中，必须把人工变量换出，否则目标函数不可能实现最大化。,2019/7/31,10, 什么是单纯形法计算的两阶段法，为什么要将计算分两个阶段进行，以及如何根据第一阶段的计算结果来判定第二阶段的计算是否需继续进行。MaxZ=-Mx6-Mx7 MinZ=Mx6+Mx7 因为“M”是一个很大的正数，是人们的一种想象，而计算机却不知道这个很大的正数到底有多大，为避免计算发生错误，对添加人工变量后的LP问题分两阶段来计算，称两阶段法。 第一阶段：求解一个目标函数仅含人工变量，且为最小化的LP问题，其两种可能结果：,2019/7/31,11,目标函数最优值为0，如果是这一结果，则去掉人工变量转入第二阶段； 如果目标函数最优值不为0，则原问题无可行解，停止计算。 第二阶段：去掉第一阶段中的人工变量，将第一阶段得到的最优解作为初始可行解，利用单纯型法继续迭代，直至终止。,2019/7/31,12,判断下列说法是否正确 图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。 LP模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。 LP问题的每一个基解对应可行域的一个顶点。 如LP问题存在最优解，则最优解一定对应可行域边界上的一个点。,2019/7/31,13,e)对取值无约束的变量xj，通常xj=xj-x”j，其中xj0，x”j0 ，在用单纯形法求得的最优解有可能同时出现xj0，x”j0。,为什么说是错误的?请看下面的例题：,将下列的LP问题变换成标准型，并用单纯形法求解。,MaxZ=-2x1-x2+3x3 st. x1+x2+x3+x4=7 x1-x2+x3-x5=2 -3x1+x2+2x3+x6=5 x3=x3-x3 x3=0 x3=0,2019/7/31,14,解：用x3-x3”替换x3，其中x3，x3”0；,第一个约束条件左端加入一松弛变量x4；,第二个约束条件左端减去一剩余变量x5，再加上一个人工变量x6；,令z=-z，把min z改为max z，即可得到该问题的标准型（规范型）：,第三个约束条件左端加上一个人工变量x7；,2019/7/31,15,解：用两阶段法求解,第一阶段的LP问题为：,用单纯形法求解，先将其化为标准型,2019/7/31,16,用两阶段法求解，第一阶段求解过程如下：,2019/7/31,17,第二阶段，去掉人工变量，回归到原问题：,2019/7/31,18,从上述最后一单纯形表知，所有j0，基变量中也不存在人工变量，故为最优解，即X*=(x1,x2,x3,x3”)=(1.8,0,37/4,0)， 可以证明，对取值无约束的变量xj，如果令xj=xj-x”j，其中xj0，x”j0，在用单纯形法求得的最优解不可能同时出现xj0，x”j0。,2019/7/31,19,f)用单纯形法求解标准型式的LP问题时，与j0对应的变量都可以被选作换入变量。 g)单纯形法计算中，如不按最小比值原则选取换出变量，则在下一步解中至少有一个基变量的值为负。 h)单纯形法计算中，选项取最大正检验数k对应的变量xk作为换入变量，将使目标函数值得到最快,2019/7/31,20,的增长。 i)一旦一个人工变量在迭代中变为非基变量后，该变量及相应的数字可以从单纯形表中删除，而不影响计算结果。 j)LP问题的任一可行解都可以用全部基可行解的线性组合表示。 n)单纯形法的迭代过程是从一个可行解转换到目标函数值更大的另一个可行解。,因为当目标函数取min z时就不是得到最快的增长。,只有当该LP问题有唯一最优解时才成立。,2019/7/31,21,O)线性规划问题的可行解如为最优解，则该可行解一定是基可行解；,为什么是错误的？因为基可行解可行解。见P18。,2019/7/31,22,第二章复习思考题 试从经济上解释对偶问题及对偶变量的含义。 如果把LP的原问题看作是在现有各项资源条件的限制下，企业如何确定生产方案，使预期目标达到最优。原问题的变量是生产方案的决策变量。 对偶问题则是从另一角度提出问题，即如果其他公司想把企业的资源收买过去，他要付出多大的代价，才有可能使得企业放弃生产活动。对偶变量是资源出让的代价。,2019/7/31,23,根据原问题同对偶问题之间的对应关系，分别找出两个问题之间、解以及检验数之间的对应关系。 原问题同对偶问题之间的对应关系见后面两表 有唯一解的对偶问题的解是原问题最终单纯形表中非基变量的检验数。,2019/7/31,24,原问题与对偶问题间的关系如下表所示: Max z,2019/7/31,25,2019/7/31,26,从第二章对偶问题的基本性质看出，当线性规划原问题求得最优解xj*（j=1，n）时，其对偶问题也得到最优解yi*（i=1，m），且代入各自的目标函数后有： 式中bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量；而对偶变量yi*的意义代表在资源最优利用条件下对第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，它与资源的紧缺度有关，某种资源越紧缺，这种估价便越高，若有剩余，这种估价便为0，为了将其与市场价格相区别，称这种估价为影子价格。, 什么是资源的影子价格，同相应的市场价格之间 有何区别，以及研究影子价格的意义。,2019/7/31,27,影子价格的经济解释,资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是随企业生产任务、产品结构等情况的变化而变化的未知数。 影子价格是一种边际价格，对上式z求bi的偏导数得 这说明yi*的值相当于在资源得到最优利用的生产条件下，bi（第i种资源拥有量）每增加一个单位时目标函数z的增量。,2019/7/31,28, 试述对偶单纯形法的计算步骤，它的优点及应用上的局限性。 对偶单纯形法的计算步骤如下表所示：,2019/7/31,29,对偶单纯形法计算步骤,根据线性规划问题 列出初始单纯形表,b列数据均0? 所有检验数0?,xl所在行所有 alk0?,以alk为主元素,按原 单纯形法进行迭代运 算,即重复上述步骤,停止计算,已得到最优解,是,否,是,否,2019/7/31,30,对偶单纯形法优缺点分析,初始解可以是非可行解(如原例初始解x4= -3,x5=-4就非可行解),只要检验数为负数,就可进 行基变换,不需加人加变量,可简化计算,当变量数多于约束条件数时,用对偶单纯形 法计算可减少计算工作量,因此对变量少,而约束 条件很多的LP问题,可将其变换为对偶问题求解,在灵敏度分析和整数规划的割平面法求解 中用对偶单纯形法可使问题的处理简化,对大多数LP问题,很难找到一个适合用对偶 单纯形法的初始可行基,对 偶 单 纯 法 优 点,此法的 局限性,2019/7/31,31,将aij，bi，cj的变化分别直接反映到最终单纯形表中，表中原问题和对偶问题的解各自将会出现什么变化，有多少种不同情况以及如何去处理。 见第2章第五节P63P70。 判断下列说法是否正确 任何LP问题存在并具有唯一的对偶问题。 对偶问题的对偶问题一定是原问题。 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解,2019/7/31,32,时，其原问题具有无界解。,2019/7/31,33,已知yi*为LP的对偶问题的最优解，若yi*=0，说明在最优生产计划中第i种资源一定有剩余。 若某种资源的影子价格等于k，在其他条件丕变的前提下，当该种资源增加5个单位时，相应的目标函数值将增加5k。 应用对偶单纯形法计算时，若单纯形表中某一基变量xi0，又xi所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解。 若LP问题中的bi，cj值同时发生