运筹学考试重点

运筹学考试重点题型概述：单选、判断、填空、建模、计算分析第一章线性规划与单纯形法例1．某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原料的消耗，如下图所示。产品III设备原料A原料B1402048台时16kg12kg该工厂每生产一件产品I可获利2元，生产一件产品II可获利3元，若用Z表示利润，X1、X2表示产量，该计划问题的数学模型可以表示为：目标函数maxZ=2X1+3X2满足约束条件｛X1+2X2=8{4X1=16X1,X2=0{4X2=12最优解是唯一的，但对于一般线性规划问题，求解结果还可能出现以下几种情况：1.无穷多最优解（多重最优解）2.无界解3.无可行解线性规划问题的标准形式为：(M1)maxZ=c1x1+c2x2+…….+cnxn下面讨论如何变换为标准型的问题。（1）若要求目标函数实现最小化，即minZ=CX。这时只需将目标函数最小化变换求目标函数最大化，即令Z’=-Z,于是得到maxZ’=-CX.（2）约束方程为不等式。这里有两种情况：一种是约束方程为“=”不等式，则可在“=”不等式的左端加上非负松弛变量，把原“=”不等式变为等式；另一种是约束方程为“=”不等式，则可在“=”不等式的左端减去一个非负剩余变量（也可称松弛变量），把不等式变为等式。例将例1的数学模型化为标准型。解.maxZ=2x1+3x2｛X1+2X2=8{4X1=16X1,X2=0{4X2=12在各不等式中分别加上一个松弛变量x3,x4,x5,使不等式变为等式，这时得到标准型：maxZ=2x1+3x2+0x3+0x4+0x5｛X1+2X2+x3=8{4X1+x4=16X1,X2=0{4X2+x5=12X3,X4,X5=0其中松弛变量x3,x4,x5表示没有被利用的资源，当然也没有利润。（3）若存在取值无约束的变量Xk，可令Xk=X’k-X’’k,其中X’k,X’’k=0。线性规划问题解的概念1.可行解2.基3.基可行解4.可行基线性规划问题的几个定理：定理1若线性规划问题存在可行域，则其可行域D是凸集。定理2线性规划问题的基可行解X对应于可行域D的顶点。（1）若X不是基可行解，则它一定不是可行域D的顶点（2）若X不是可行域D的顶点，则它一定不是基可行解定理3若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。初始基可行解的确定：为了确定初始基可行解，要首先找出初始可行基，其方法如下：（1）直接观察法（2）对所有约束条件是“=”的不等式，可以利用化为标准型的办法，在每个约束条件左端加上一个松弛变量。（3）对所有约束条件是“=”的不等式,若不存在单位矩阵时，就采用人造基方法。（即减非负剩余变量，再加上一个非负人工变量）最优性检验与解的判别（闭回路法、位势法），包括最优解的判别、无穷多最优解的判别、无界解判别。（对应书上P37页图1-9）单纯形法的计算步骤：见书上P30页4.2（重点掌握）用人工变量法可以得到初始基可行解。基变量中不再含有非零的人工变量，这表示原问题有解。若在最终表中当所有Cj-Zj=0，而在其中还有某个非零人工变量，这表示无可行解。用所有Cj-Zj=0来判别目标函数是否实现了最小化。人工变量法包括大M法和两阶段法例题见书上P33-34页线性规划问题的应用举例见书上P38页P46页1.91.10第二章对偶理论和灵敏度分析概念（了解）书上P48页表2-1（重点）P56页表2-4（重点-大题）P56页例3对偶问题的基本性质（前四个较重要，第六个互补松弛性-重点）58页表2-5（重点）无界----》无可行解（顺推）原问题松弛变量对应检验数=对偶问题最优解相反数（用于理解表2-5）对偶问题的对偶是原问题P59页例4、例5（考察互补松弛性）影子价格Y*=CbB-1=@z*/@b变量yi*的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。对偶单纯形法的计算步骤P61页P62页例6对偶单纯形法的优点P63页灵敏度分析p64若碰到原问题和对偶问题均为非可行解时，就需要引进人工变量后重新求解。P74页表2-272.3第一、第二小题2.4判断题2.7对应互补松弛性2.8对偶单纯形法求解问题第三章运输问题模型最多有m+n-1个独立约束方程P79例题（多看）第四章目标规划正负偏差的相关概念P101-102建模例题（P102）正负偏差的使用原则：至少有一个为0、=0第六章动态规划概念、基本方程（P135开始）逆推法P145顺推法P147P148例5第七章图与网络优化基本概念（P177开始）树（P180开始）最短路问题（P185开始）网络最大流问题（P193开始）最小费用最大流问题（P198开始）