1、际恩陆2022-3-271 求解求解LP问题时可能出现哪几种结果？问题时可能出现哪几种结果？求解求解LP问题有可能出现问题有可能出现4种结果，即：种结果，即：有唯一最优解；有无穷多最优解；有无界解；无可行解。 什么是什么是LP问题的标准型式，如何将非标准型问题的标准型式，如何将非标准型的的LP问题转化为标准型？问题转化为标准型？LP问题的标准型是：问题的标准型是：目标函数取极大值；约束条件取“=”号；际恩陆2022-3-272资源系数必须0；决策变量必须0 对于任意一个非标准的对于任意一个非标准的LP问题，可采取如下方法，问题，可采取如下方法，将其变换为标准型：将其变换为标准型： 若目标函数为
2、求极小值minz=CX，则令z=z，便可得到maxz=CX； 如果某约束条件的右端项（资源系数）0，而对应的Pj0，此时的解为无界解。 如果如果LP问题的标准型式变换为求目标问题的标准型式变换为求目标函数的极小化函数的极小化min z，则用单纯形法计算时，则用单纯形法计算时，如何判别问题已得到最优解。如何判别问题已得到最优解。际恩陆2022-3-277 如果LP问题的标准型式变换为求目标函数的极小化min z，则在用单纯形法计算时，用检验数j0判断问题是否得到最优，方法同极大化。 在确定初始可行基时，什么情况下在确定初始可行基时，什么情况下要在约束条件中增添人工变量，在目标函要在约束条件中增添
3、人工变量，在目标函数中假定人工变量前的系数为（数中假定人工变量前的系数为（-M），其），其作用是什么？作用是什么？际恩陆2022-3-278 当规划模型化为标准型后，当其约束条件的系数矩阵中不存在单位矩阵时，需再添加新的人工变量。 在一个LP问题的约束条件中加入人工变量后，要求人工变量对目标函数取值不受影响，假定人工变量在目标函数中的系数为（-M，M为任意大正数），这样目标函数在实现最大化的过程中，必须把人工变量换出，否则目标函数不可能实现最大化。际恩陆2022-3-279 什么是单纯形法计算的两阶段法，为什么是单纯形法计算的两阶段法，为什么要将计算分两个阶段进行，以及如何根据什么要将计算分两
4、个阶段进行，以及如何根据第一阶段的计算结果来判定第二阶段的计算是第一阶段的计算结果来判定第二阶段的计算是否需继续进行。否需继续进行。MaxZ=-Mx6-Mx7 MinZ=Mx6+Mx7 因为“M”是一个很大的正数，是人们的一种想象，而计算机却不知道这个很大的正数到底有多大，为避免计算发生错误，对添加人工变量后的LP问题分两阶段来计算，称两阶段法。第一阶段：求解一个目标函数仅含人工变量，且为最小化的LP问题，其两种可能结果：际恩陆2022-3-2710 目标函数最优值为0，如果是这一结果，则去掉人工变量转入第二阶段； 如果目标函数最优值不为0，则原问题无可行解，停止计算。 第二阶段：去掉第一阶段
5、中的人工变量，将第一阶段得到的最优解作为初始可行解，利用单纯型法继续迭代，直至终止。际恩陆2022-3-2711 判断下列说法是否正确图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。LP模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。 LP问题的每一个基解对应可行域的一个顶点。如LP问题存在最优解，则最优解一定对应可行域边界上的一个点。 际恩陆2022-3-2712e)对取值无约束的变量xj，通常xj=xj-x”j，其中xj0，x”j0 ，在用单纯形法求得的最优解有可能同时出现xj0，x”j0。为什么说是错误的?请看下面的例题：将下列
6、的LP问题变换成标准型，并用单纯形法求解。无约束321321321321321, 0,52327.32minxxxxxxxxxxxxstxxxzMaxZ=-2x1-x2+3x3st. x1+x2+x3+x4=7 x1-x2+x3-x5=2 -3x1+x2+2x3+x6=5x3=x3-x3 x3=0 x3=0际恩陆2022-3-2713解：用解：用x3-x3”替换替换x3，其中，其中x3，x3”0；第一个约束条件左端加入一松弛变量第一个约束条件左端加入一松弛变量x4； 第二个约束条件左端减去一剩余变量第二个约束条件左端减去一剩余变量x5，再加上一个，再加上一个人工变量人工变量x6； 令令z=-z
7、，把，把min z改为改为max z，即可得到该问题的，即可得到该问题的标准型（规范型）：标准型（规范型）：0,;7 , 2 , 1, 0522327.00332max33733216533214332176543321xxixxxxxxxxxxxxxxxxxstMxMxxxxxxxzi 第三个约束条件左端加上一个人工变量第三个约束条件左端加上一个人工变量x7；际恩陆2022-3-2714解：用两阶段法求解第一阶段的LP问题为：0,;7 , 2 , 1, 0522327.min33733216533214332176xxixxxxxxxxxxxxxxxxxstxxi用单纯形法求解，先将其化为标
8、准型0,;7 , 2 , 1, 0522327.max33733216533214332176xxixxxxxxxxxxxxxxxxxstxxi际恩陆2022-3-2715用两阶段法求解，第一阶段求解过程如下：用两阶段法求解，第一阶段求解过程如下：cj000000-1-1cBxBbx1x2x3x3”x4x5x6x70 x47111-11000-1x621-11-10-110-1x75-312-20001cj-zj-203-30-1000 x45020011-100 x321-11-10-110-1x71-530002-21cj-zj-530002-300 x413/310/30001-1/31
9、/3-2/30 x37/3-2/301-10-1/31/34/30 x21/3-5/310002/3-2/31/3cj-zj000000-1-1际恩陆2022-3-2716第二阶段，去掉人工变量，回归到原问题：第二阶段，去掉人工变量，回归到原问题：cj-2-13-300cBxBbx1x2x3x3”x4x50 x413/310/30001-1/33x37/3-2/301-10-1/3-1x21/3-5/310002/3cj-zj-5/310007/30 x49/25/21/200103x35/2-3/21/21-1000 x51/2-5/23/20001cj-zj11/2-7/20000-2x1
10、9/511/5002/503x337/404/51-13/500 x547/4020011cj-zj0-23/500-11/50际恩陆2022-3-2717从上述最后一单纯形表知，所有从上述最后一单纯形表知，所有j0，基变量中也，基变量中也不存在人工变量，故为最优解，即不存在人工变量，故为最优解，即X*=(x1,x2,x3,x3”)=(1.8,0,37/4,0)，可以证明，对取值无约束的变量可以证明，对取值无约束的变量xj，如果令，如果令xj=xj-x”j，其中，其中xj0，x”j0，在用单纯形法求得的最优解，在用单纯形法求得的最优解不不可能同时出现可能同时出现xj0，x”j0。际恩陆2022
11、-3-2718f)用单纯形法求解标准型式的LP问题时，与j0对应的变量都可以被选作换入变量。 g)单纯形法计算中，如不按最小比值原则选取换出变量，则在下一步解中至少有一个基变量的值为负。 h)单纯形法计算中，选项取最大正检验数k对应的变量xk作为换入变量，将使目标函数值得到最快际恩陆2022-3-2719 的增长。 i)一旦一个人工变量在迭代中变为非基变量后，该变量及相应的数字可以从单纯形表中删除，而不影响计算结果。 j)LP问题的任一可行解都可以用全部基可行解的线性组合表示。 n)单纯形法的迭代过程是从一个可行解转换到目标函数值更大的另一个可行解。因为当目标函数取因为当目标函数取min z时
12、就不是得到最快的增长。时就不是得到最快的增长。只有当该只有当该LP问题有唯一最优解时才成立。问题有唯一最优解时才成立。际恩陆2022-3-2720 O)线性规划问题的可行解如为最优解，则该可行线性规划问题的可行解如为最优解，则该可行解一定是基可行解；解一定是基可行解； 为什么是错误的？因为为什么是错误的？因为基可行解基可行解可行解可行解。见。见P18。际恩陆2022-3-2721第二章复习思考题 试从经济上解释对偶问题及对试从经济上解释对偶问题及对偶变量的含义。偶变量的含义。如果把LP的原问题看作是在现有各项资源条件的限制下，企业如何确定生产方案，使预期目标达到最优。原问题的变量是生产方案的决
13、策变量。对偶问题则是从另一角度提出问题，即如果其他公司想把企业的资源收买过去，他要付出多大的代价，才有可能使得企业放弃生产活动。对偶变量是资源出让的代价。际恩陆2022-3-2722根据原问题同对偶问题之间的对应关系，分别找根据原问题同对偶问题之间的对应关系，分别找出两个问题之间、解以及检验数之间的对应关系。出两个问题之间、解以及检验数之间的对应关系。原问题同对偶问题之间的对应关系见后面两表有唯一解的对偶问题的解是原问题最终单纯形表中非基变量的检验数。际恩陆2022-3-2723zmax原问题目标函数极大min对偶问题目标函数极小量变件条束约个n个n无约束00件条束约量变个m无约束00个m约束
14、条件右边项目标函数变量的系数约束条件右边项目标函数变量的系数原问题与对偶问题间的关系如下表所示:Max z际恩陆2022-3-2724min原问题目标函数极小zmax对偶问题目标函数极大量变件条束约个n个n无约束00件条束约量变个m无约束00个m约束条件右边项目标函数变量的系数约束条件右边项目标函数变量的系数际恩陆2022-3-2725 从第二章对偶问题的基本性质看出，当线性规划原问题求得最优解xj*（j=1，n）时，其对偶问题也得到最优解yi*（i=1，m），且代入各自的目标函数后有： 式中bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量；而对偶变量yi*的意义代表在资源最优利
15、用条件下对第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，它与资源的紧缺度有关，某种资源越紧缺，这种估价便越高，若有剩余，这种估价便为0，为了将其与市场价格相区别，称这种估价为影子价格。*1*1*miiinjjjybxcz 什么是资源的影子价格，同相应的市场价格之间什么是资源的影子价格，同相应的市场价格之间有何区别，以及研究影子价格的意义。有何区别，以及研究影子价格的意义。际恩陆2022-3-2726影子价格的经济解释影子价格的经济解释 资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是随企业生产任务、产品结构等情况的变化而变
16、化的未知数。 影子价格是一种边际价格，对上式z求bi的偏导数得 这说明yi*的值相当于在资源得到最优利用的生产条件下，bi（第i种资源拥有量）每增加一个单位时目标函数z的增量。*iiybz际恩陆2022-3-2727 试述对偶单纯形法的计算步骤，它的优点及应用上的局限性。 对偶单纯形法的计算步骤如下表所示：际恩陆2022-3-2728对偶单纯形法计算步骤对偶单纯形法计算步骤根据线性规划问题根据线性规划问题列出初始单纯形表列出初始单纯形表b列数据均列数据均0?所有检验数所有检验数0?为换出变量基变量原则确定对应的按iliixbBbBbB)(0)( |)(min111为换入变量的非基变量原则确定对
17、应列按klkjjljljjjxaZCaaZC0minxl所在行所有所在行所有alk0?以以alk为主元素为主元素,按原按原单纯形法进行迭代运单纯形法进行迭代运算算,即重复上述步骤即重复上述步骤停止计算停止计算已得到最优解已得到最优解是是否否是是否否际恩陆2022-3-2729对偶单纯形法优缺点分析 初始解可以是非可行解(如原例初始解x4=-3,x5=-4就非可行解),只要检验数为负数,就可进行基变换,不需加人加变量,可简化计算 当变量数多于约束条件数时,用对偶单纯形法计算可减少计算工作量,因此对变量少,而约束条件很多的LP问题,可将其变换为对偶问题求解 在灵敏度分析和整数规划的割平面法求解中用
18、对偶单纯形法可使问题的处理简化 对大多数LP问题,很难找到一个适合用对偶单纯形法的初始可行基对对偶偶单单纯纯法法优优点点此法的此法的局限性局限性际恩陆2022-3-2730将将aij，bi，cj的变化分别直接反映到最终单纯形表的变化分别直接反映到最终单纯形表中，表中原问题和对偶问题的解各自将会出现什中，表中原问题和对偶问题的解各自将会出现什么变化，有多少种不同情况以及如何去处理。么变化，有多少种不同情况以及如何去处理。l 见第2章第五节P63P70。判断下列说法是否正确判断下列说法是否正确 任何LP问题存在并具有唯一的对偶问题。 对偶问题的对偶问题一定是原问题。 根据对偶问题的性质，当原问题为
19、无界解时，其对偶问题无可行解，反之，当对偶问题无可行解际恩陆2022-3-2731 时，其原问题具有无界解。iimiiimijjnjjjnjjjybybxcxcyxyxij:,1*1*11*则恒有分别为其最优解题与对偶问题的可行解分别为标准形式的原问设。iyLPy。LPii种资源已完全耗尽产计划中第说明最优生若的对偶问题的最优解为已知有无穷多最优解则其对偶问题也一定解的原问题有无穷多最优若, 0,*际恩陆2022-3-2732 已知yi*为LP的对偶问题的最优解，若yi*=0，说明在最优生产计划中第i种资源一定有剩余。 若某种资源的影子价格等于k，在其他条件丕变的前提下，当该种资源增加5个单位
20、时，相应的目标函数值将增加5k。 应用对偶单纯形法计算时，若单纯形表中某一基变量xi0，又xi所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解。 若LP问题中的bi，cj值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非际恩陆2022-3-2733 可行解的情况。 在LP问题的最优解中，如某一变量xj为非基变量，则在原问题中，无论改变它在目标函数中的系数cj或在各约束中的相应系数aij，反映到最终单纯形表中，除该列数字有变化外，将不引起其它列数字的变化。 际恩陆2022-3-2734第四章复习思考题 判断 1.T 2.F 3.F第10章复习思考题判断 2-8 F T F T T T F第11章复习思考题判断1-8FTTFTTTF
