第三版运筹学总复习1课件

2023/8/91⒉求解LP问题时可能出现哪几种结果？求解LP问题有可能出现4种结果，即：⑴有唯一最优解；⑵有无穷多最优解；⑶有无界解；⑷无可行解。⒊什么是LP问题的标准型式，如何将非标准型的LP问题转化为标准型？LP问题的标准型是：⑴目标函数取极大值；⑵约束条件取“=”号；2023/8/21⒉求解LP问题时可能出现哪几种结果？求解12023/8/92⑶资源系数必须≥0；⑷决策变量必须≥0

对于任意一个非标准的LP问题，可采取如下方法，将其变换为标准型：⑴若目标函数为求极小值minz=CX，则令z’=－z，便可得到maxz’=－CX；⑵如果某约束条件的右端项（资源系数）<0，则该约束条件两端同时乘“－1”，使其≥0；⑶如果约束条件为“≤”不等式，则在不等式的左端加入一个非负的松弛变量，使其变为等式；2023/8/22⑶资源系数必须≥0；对于任22023/8/93⑷如果约束条件为“≥”不等式，则在不等式的左端减去一个非负的剩余变量，使其变为等式；⑸若xj≤0，则令x’j=－xj，代入标准型，则有x’j≥0；⑹若xj的正负不限，则令xj=x’j－x”j，而x’j≥0，x”j≥0。⒋试述LP问题的基解、基可行解、可行解、最优解的概念以及上述解之间的相互关系。2023/8/23⑷如果约束条件为“≥”不等32023/8/94⑴基解：在约束方程组②中，令所有非基变量Xm+1=xm+2=…=xn=0，此时，方程组②有唯一解XB=(x1,x2,…,xm)T，将此解加上非基变量取0的值有X=(x1,x2,…xm,0,0,…,0)T，称X为LP问题的基解。2023/8/24⑴基解：在约束方程组②中，令所有非基变量42023/8/95⑵基可行解：满足非负约束条件③的解；⑵可行解：满足约束条件②和③的解；⑷最优解：使目标函数①达到最大值的可行解；⒌试述单纯形法的计算步骤，如何在单纯形表上判别问题是具有唯一最优解、无穷多最优解、无界解或无可行解。在单纯形表中，如果所有检验数σj≤0，基变量中不存在非零的人工变量，非基变量中也不存在等于零的检验数，此时的解为唯一最优解；如果在单纯形表中，虽然所有检验数σj≤0，但存在某非基变量的检验数等于零，此时的解为无穷多最优解；2023/8/25⑵基可行解：满足非负约束条件③的解；52023/8/96如果在单纯形表中，所有检验数σj≤0，基变量中存在非零的人工变量，此时的解为无可行解；如果在单纯形表中，某检验数σj>0，而对应的Pj≤0，此时的解为无界解。⒍如果LP问题的标准型式变换为求目标函数的极小化minz，则用单纯形法计算时，如何判别问题已得到最优解。2023/8/26如果在单纯形表中，所有检验数σj≤0，62023/8/97

如果LP问题的标准型式变换为求目标函数的极小化minz，则在用单纯形法计算时，用检验数σj≥0判断问题是否得到最优，方法同极大化。⒎在确定初始可行基时，什么情况下要在约束条件中增添人工变量，在目标函数中假定人工变量前的系数为（-M），其作用是什么？2023/8/27如果LP问题的标准型式变换72023/8/98当规划模型化为标准型后，当其约束条件的系数矩阵中不存在单位矩阵时，需再添加新的人工变量。在一个LP问题的约束条件中加入人工变量后，要求人工变量对目标函数取值不受影响，假定人工变量在目标函数中的系数为（-M，M为任意大正数），这样目标函数在实现最大化的过程中，必须把人工变量换出，否则目标函数不可能实现最大化。2023/8/28当规划模型化为标准型82023/8/99⒏什么是单纯形法计算的两阶段法，为什么要将计算分两个阶段进行，以及如何根据第一阶段的计算结果来判定第二阶段的计算是否需继续进行。MaxZ=-Mx6-Mx7MinZ=Mx6+Mx7因为“M”是一个很大的正数，是人们的一种想象，而计算机却不知道这个很大的正数到底有多大，为避免计算发生错误，对添加人工变量后的LP问题分两阶段来计算，称两阶段法。第一阶段：求解一个目标函数仅含人工变量，且为最小化的LP问题，其两种可能结果：2023/8/29⒏什么是单纯形法计算的92023/8/910目标函数最优值为0，如果是这一结果，则去掉人工变量转入第二阶段；如果目标函数最优值不为0，则原问题无可行解，停止计算。第二阶段：去掉第一阶段中的人工变量，将第一阶段得到的最优解作为初始可行解，利用单纯型法继续迭代，直至终止。2023/8/210目标函数最优值为0，如果是这一102023/8/911

判断下列说法是否正确图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。LP模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，，可行域的范围一般将扩大。LP问题的每一个基解对应可行域的一个顶点。如LP问题存在最优解，则最优解一定对应可行域边界上的一个点。√×√√2023/8/211√×√√112023/8/912e)对取值无约束的变量xj，通常xj=x’j-x”j，其中x’j≥0，x”j≥0

√，在用单纯形法求得的最优解有可能同时出现x’j>0，x”j>0。×为什么说是错误的?请看下面的例题：将下列的LP问题变换成标准型，并用单纯形法求解。MaxZ=-2x1-x2+3x3st.x1+x2+x3+x4=7x1-x2+x3-x5=2-3x1+x2+2x3+x6=5x3=x3'-x3''x3'>=0x3''>=02023/8/212e)对取值无约束的变量xj，通常xj=x122023/8/913解：⑴用x3’-x3”替换x3，其中x3’，x3”≥0；⑵第一个约束条件左端加入一松弛变量x4；⑶第二个约束条件左端减去一剩余变量x5，再加上一个人工变量x6；⑸令z’=-z，把minz改为maxz’，即可得到该问题的标准型（规范型）：⑷第三个约束条件左端加上一个人工变量x7；2023/8/213解：⑴用x3’-x3”替换x3，其中x3132023/8/914解：用两阶段法求解第一阶段的LP问题为：用单纯形法求解，先将其化为标准型2023/8/214解：用两阶段法求解第一阶段的LP问题为：142023/8/915用两阶段法求解，第一阶段求解过程如下：cj000000-1-1cBxBbx1x2x3’x3”x4x5x6x70x47111-11000-1x621-1[1]-10-110-1x75-312-20001cj-zj-203-30-1000x45020011-100x3’21-11-10-110-1x71-5[3]0002-21cj-zj-530002-300x413/310/30001-1/31/3-2/30x3’7/3-2/301-10-1/31/34/30x21/3-5/31000[2/3]-2/31/3cj-zj000000-1-12023/8/215用两阶段法求解，第一阶段求解过程如下：c152023/8/916第二阶段，去掉人工变量，回归到原问题：cj-2-13-300cBxBbx1x2x3’x3”x4x50x413/310/30001-1/33x3’7/3-2/301-10-1/3-1x21/3-5/31000[2/3]cj-zj-5/310007/30x49/2[5/2]1/200103x3’5/2-3/21/21-1000x51/2-5/23/20001cj-zj11/2-7/20000-2x19/511/5002/503x3’37/404/51-13/500x547/4020011cj-zj0-23/500-11/502023/8/216第二阶段，去掉人工变量，回归到原问题：c162023/8/917从上述最后一单纯形表知，所有σj≤0，基变量中也不存在人工变量，故为最优解，即X*=(x1,x2,x3’,x3”)=(1.8,0,37/4,0)，可以证明，对取值无约束的变量xj，如果令xj=x’j-x”j，其中x’j≥0，x”j≥0，在用单纯形法求得的最优解不可能同时出现x’j>0，x”j>0。2023/8/217从上述最后一单纯形表知，所有σj≤0，基172023/8/918f)用单纯形法求解标准型式的LP问题时，与σj>0对应的变量都可以被选作换入变量。g)单纯形法计算中，如不按最小比值原则选取换出变量，则在下一步解中至少有一个基变量的值为负。h)单纯形法计算中，选项取最大正检验数σk对应的变量xk作为换入变量，将使目标函数值得到最快√√2023/8/218√√182023/8/919的增长。i)一旦一个人工变量在迭代中变为非基变量后，该变量及相应的数字可以从单纯形表中删除，而不影响计算结果。j)LP问题的任一可行解都可以用全部基可行解的线性组合表示。n)单纯形法的迭代过程是从一个可行解转换到目标函数值更大的另一个可行解。×√×√因为当目标函数取minz时就不是得到最快的增长。只有当该LP问题有唯一最优解时才成立。2023/8/219的增长。192023/8/920O)线性规划问题的可行解如为最优解，则该可行解一定是基可行解；×

为什么是错误的？因为基可行解≠可行解。见P18。2023/8/220O)线性规划问题的可行解202023/8/921第二章复习思考题⒉试从经济上解释对偶问题及对偶变量的含义。如果把LP的原问题看作是在现有各项资源条件的限制下，企业如何确定生产方案，使预期目标达到最优。原问题的变量是生产方案的决策变量。对偶问题则是从另一角度提出问题，即如果其他公司想把企业的资源收买过去，他要付出多大的代价，才有可能使得企业放弃生产活动。对偶变量是资源出让的代价。2023/8/221第二章复习思考题⒉试从经济上解释对偶问212023/8/922⒊根据原问题同对偶问题之间的对应关系，分别找出两个问题之间、解以及检验数之间的对应关系。原问题同对偶问题之间的对应关系见后面两表有唯一解的对偶问题的解是原问题最终单纯形表中非基变量的检验数。2023/8/222⒊根据原问题同对偶问题之间的对应关系，分222023/8/923原问题与对偶问题间的关系如下表所示:Maxz2023/8/223原问题与对偶问题间的关系如下表所示:232023/8/9242023/8/224242023/8/925从第二章对偶问题的基本性质看出，当线性规划原问题求得最优解xj*（j=1，…，n）时，其对偶问题也得到最优解yi*（i=1，…，m），且代入各自的目标函数后有：式中bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量；而对偶变量yi*的意义代表在资源最优利用条件下对第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，它与资源的紧缺度有关，某种资源越紧缺，这种估价便越高，若有剩余，这种估价便为0，为了将其与市场价格相区别，称这种估价为影子价格。⒋什么是资源的影子价格，同相应的市场价格之间有何区别，以及研究影子价格的意义。2023/8/225从第二章对偶问题的基本性质看出，当线性规252023/8/926影子价格的经济解释⑴资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是随企业生产任务、产品结构等情况的变化而变化的未知数。⑵影子价格是一种边际价格，对上式z求bi的偏导数得这说明yi*的值相当于在资源得到最优利用的生产条件下，bi（第i种资源拥有量）每增加一个单位时目标函数z的增量。2023/8/226影子价格的经济解释⑴资源的市场价格是已知262023/8/927⒌试述对偶单纯形法的计算步骤，它的优点及应用上的局限性。对偶单纯形法的计算步骤如下表所示：2023/8/227⒌试述对偶单纯形法的计算步骤，它的优点272023/8/928对偶单纯形法计算步骤根据线性规划问题列出初始单纯形表b列数据均≥0?所有检验数＜0?xl所在行所有alk≥0?以alk为主元素,按原单纯形法进行迭代运算,即重复上述步骤停止计算已得到最优解是否是否2023/8/228对偶单纯形法计算步骤根据线性规划问题b列282023/8/929对偶单纯形法优缺点分析

初始解可以是非可行解(如原例初始解x4=-3,x5=-4就非可行解),只要检验数为负数,就可进行基变换,不需加人加变量,可简化计算

当变量数多于约束条件数时,用对偶单纯形法计算可减少计算工作量,因此对变量少,而约束条件很多的LP问题,可将其变换为对偶问题求解

在灵敏度分析和整数规划的割平面法求解中用对偶单纯形法可使问题的处理简化

对大多数LP问题,很难找到一个适合用对偶单纯形法的初始可行基对偶单纯法优点此法的局限性2023/8/229对偶单纯形法优缺点分析初292023/8/930⒍将aij，bi，cj的变化分别直接反映到最终单纯形表中，表中原问题和对偶问题的解各自将会出现什么变化，有多少种不同情况以及如何去处理。见第2章第五节P63～P70。⒎判断下列说法是否正确任何LP问题存在并具有唯一的对偶问题。