第3版运筹学总复习.pptVIP

2017-5-17 1 第一章复习思考题 ⒈ 试述LP数学模型的组成要素及各要素的特征。 LP数学模型组成三要素： 一是决策变量； 二目标函数； 三是约束条件。 各要素特征： ⑴决策变量是连续的； ⑵决策变量是目标函数的线性函数； ⑶约束条件是含有决策变量的线性不等式。 2017-5-17 2 ⒉ 求解LP问题时可能出现哪几种结果？ 求解LP问题有可能出现4种结果，即： ⑴有唯一最优解； ⑵有无穷多最优解； ⑶有无界解； ⑷无可行解。 ⒊ 什么是LP问题的标准型式，如何将非标准型 的LP问题转化为标准型？ LP问题的标准型是： ⑴目标函数取极大值； ⑵约束条件取“=”号； 2017-5-17 3 ⑶资源系数必须≥0； ⑷决策变量必须≥0 对于任意一个非标准的LP问题，可采取如下方法， 将其变换为标准型： ⑴若目标函数为求极小值minz=CX，则令z’=－z，便可得到maxz’=－CX； ⑵如果某约束条件的右端项（资源系数）0，则该约束条件两端同时乘“－1”，使其≥0； ⑶如果约束条件为“≤”不等式，则在不等式的左端加入一个非负的松弛变量，使其变为等式； 2017-5-17 4 ⑷如果约束条件为“≥”不等式，则在不等式的左端减去一个非负的剩余变量，使其变为等式； ⑸若xj≤0，则令x’j=－xj，代入标准型，则有x’j≥0； ⑹若xj的正负不限，则令xj=x’j－x”j，而x’j≥0，x”j≥0。 ⒋试述LP问题的基解、基可行解、可行解、最优解的概念以及上述解之间的相互关系。 2017-5-17 5 ⑴基解：在约束方程组②中，令所有非基变量 Xm+1=xm+2=…=xn=0，此时，方程组②有唯一 解XB=(x1,x2,…,xm)T，将此解加上非基变量取 0的值有X=(x1,x2,…xm,0,0,…,0)T，称X为LP问 题的基解。 2017-5-17 6 ⑵基可行解：满足非负约束条件③的解； ⑵可行解：满足约束条件②和③的解； ⑷最优解：使目标函数①达到最大值的可行解； ⒌ 试述单纯形法的计算步骤，如何在单纯形表上判别问题是具有唯一最优解、无穷多最优解、无界解或无可行解。 在单纯形表中，如果所有检验数σj≤0，基变量中不存在非零的人工变量，非基变量中也不存在等于零的检验数，此时的解为唯一最优解；如果在单纯形表中，虽然所有检验数σj≤0，但存在某非基变量的检验数等于零，此时的解为无穷多最优解； 2017-5-17 7 如果在单纯形表中，所有检验数σj≤0， 基变量中存在非零的人工变量，此时的 解为无可行解；如果在单纯形表中，某 检验数σj0，而对应的Pj≤0，此时的 解为无界解。 ⒍如果LP问题的标准型式变换为求目标函数的极小化min z，则用单纯形法计算时，如何判别问题已得到最优解。 2017-5-17 8 如果LP问题的标准型式变换为求目标函数的极小化min z，则在用单纯形法计算时，用检验数σj≥0判断问题是否得到最优，方法同极大化。 ⒎ 在确定初始可行基时，什么情况下要在约束条件中增添人工变量，在目标函数中假定人工变量前的系数为（-M），其作用是什么？ 2017-5-17 9 当规划模型化为标准型后，当其约束条件的系数矩阵中不存在单位矩阵时，需再添加新的人工变量。 在一个LP问题的约束条件中加入人工变量后，要求人工变量对目标函数取值不受影响，假定人工变量在目标函数中的系数为（-M，M为任意大正数），这样目标函数在实现最大化的过程中，必须把人工变量换出，否则目标函数不可能实现最大化。 2017-5-17 10 ⒏ 什么是单纯形法计算的两阶段法，为什么要将计算分两个阶段进行，以及如何根据第一阶段的计算结果来判定第二阶段的计算是否需继续进行。MaxZ=-Mx6-Mx7 MinZ=Mx6+Mx7 因为“M”是一个很大的正数，是人们的一种想象，而计算机却不知道这个很大的正数到底有多大，为避免计算发生错误，对添加人工变量后的LP问题分两阶段来计算，称两阶段法。 第一阶段：求解一个目标函数仅含人工变量，且为最小化的LP问题，其两种可能结果： 2017-5-17 11 目标函数最优值为0，如果是这一结果，则去掉人工变量转入第二阶段； 如果目标函数最优值不为0，则原问题无可行解，停止计算。 第二阶段：去掉第一阶段中的人工变量，将第一阶段得到的最优解作为