搜索
第一章线性规划•建立线性规划模型的基本方法（掌握）•图解法（掌握）–作出可行域–选择一个可行解，做出一条等值线–判断等值线优化的方向–在保证等值线与可行域相交的前提下，按优化方向平移等值线到移不动为止–确定此时交点有哪些边界线相交而得–列出方程，解方程组得最优解–计算最优目标值•求解线性规划问题可能出现的几种结果（掌握）无可行解、唯一最优解、无穷多最优解、无界解第一章线性规划•相关基本概念（理解并能运用）：•可行解，基、基变量、非基变量、基本解，基可行解、可行基，凸集、凸组合、顶点•线性规划的几个基本定理（理解并能运用）•定理1可行域为凸集•引理1可行解为基可行解的充要条件：正分量所对应的系数列向量线性无关•定理2线性规划问题的基可行解对应于可行域的顶点•引理2有界凸集中的任意一点必然可表示为其顶点的凸组合•定理3可行域有界时线性规划问题的最优解必然可在可行域的某个顶点处达到•化为标准形式（熟练掌握）–Min化为Max–非正变量化为非负的变量–大于等于型不等式约束左边减去超出的部分（减剩余变量）–小于等于型不等式约束增加不足的部分（加松弛变量）•单纯形法的计算步骤（能列出初始表，并迭代一次）（熟练掌握）–怎样列初始表（含怎样结算检验数）–怎样判断是否是最优表–怎样确定出基变量（最小检验数）–怎样确定入基变量（最小比值）–怎样迭代到下一张表–唯一解、无穷多最优解、无界解的判定条件•M法（掌握）–什么时候用M法?——化为标准型后系数矩阵中找不全单位阵的各列–怎样构造辅助规划?（熟练掌握）•约束条件中增加人工变量•修改目标函数：–Max问题减去M乘人工变量–Min型问题加上M乘人工变量–计算规则与单纯形法相同（熟练掌握）–在什么条件下原规划无可行解?——最优表中人工变量是基变量）•两阶段法（掌握）–什么时候用两阶段法?化为标准型后系数矩阵中找不全单位阵的各列–怎样构造辅助规划：（熟练掌握）•约束条件中增加人工变量•目标函数修改为人工变量之和•目标函数的优化方向为Min。–计算规则与单纯形法相同（熟练掌握）–在什么条件下原规划无可行解？——最优表中人工变量是基变量–怎样利用辅助规划的最优表得到原规划的初始表第2章对偶规划•怎样写出给定规划的对偶规划：根据对偶关系表（熟练掌握）•影子价格的经济意义（理解）•对偶理论的主要结论–弱对偶定理及其推论（掌握）–强对偶定理（掌握）–互补松弛原理及其应用（熟练掌握）•写出对偶规划•与已知最优解的正分量相对应的约束条件取等号•与代入最优解后取严格不等号相对应最优解的分量为零•求解方程组•对偶单纯形法（掌握）–什么时候用？–怎样判断最优？–怎样确定出基变量？–怎样确定入基变量？•单纯形法和对偶单纯形法的基本特征比较（掌握）–单纯形表和对偶单纯形的基本结构（熟记于心）–以最大化问题为例•单纯形法B-1b始终非负•对偶单纯形法检验数始终非负•最优表中，松弛变量的检验数的相反数就是对偶规划的最优解cBTcNTxBxNxBB-1bEB-1N检验数σj0cNT-cNTB-1N•灵敏度分析（掌握）•目的：(1)确定允许变化范围；(2)当变化超出允许范围时怎样利用原规划的最优表求出新的最优表–单个价值系数变化时的灵敏度分析：最优解不变的允许变化范围•非基变量的价值系数变化•基变量的价值系数变化–单个右端常数变化时的灵敏度分析：最优基不变的允许变化范围–新产品是否投产？新技术是否采用？第三章运输问题•建立模型注意不同产销关系下的模型变化（掌握）•闭回路的定义，闭回路与基变量组之间的关系（掌握）•产销平衡时的解法——表上作业法–求初始基可行解的方法西北角法（理解）、最小元素法和差值法（熟练掌握）–求检验数的方法•闭回路法（理解）•位势法（熟练掌握）基本原理:(1)一个产地Ai引入一个变量ui、一个销地Bj引入一个变量vj、一个基变量xij引入一个方程ui+vj=cij；(2)求出方程组的任意一组解；(3)非基变量xij的检验数=cij–ui–vj计算方法：在表上进行•产销平衡时的解法——表上作业法（续）–调整方法（熟练掌握）•找闭回路：去除多余变量法•确定调整量•在闭回路上调整：–奇顶点处的运量+调整量，然后加圈；–偶顶点处的运量-调整量，选择一个调整后运量为0的顶点处的变量为出基变量，其余顶点处的调整后运量加圈。•重新计算检验数–最优性判别标准（熟练掌握）表上作业法的拓展（理解）•产销不平衡的处理方法–产大于销：增加虚设销地；产小于销：增加虚设产地•有禁运线路：单位运价为M•产量或销量有上下限–一分为二，一个是下限（必须运出，禁止运往虚设的销地或产地），一个是上限减去下限（可以不运出）–增加虚设销地或产地第五章整数规划•建立模型：在线性规划的基础上增加整数限制（掌握）•求解方法–取整法不可取（了解）–分支定界法（理解基本思路，能借助图解法实现算法）–割平面法（理解基本思路，能根据松弛问题的最优表生成切割约束条件）整数规划部分的要求第五章整数规划•用0-1变量建立模型•任务数=工人数问题的求解方法——匈牙利法–第一步，变换效率矩阵，使每行每列都有零元素–第二步，尝试安排任务：从零元素最少的行或列开始，零元素不止一个时任意选一个；对一个零加圈后要划去同行同列的其他零元素–第三步，判断带圈零元素个数=工人数吗？是，算法结束；否，转入第四步指派问题（熟练掌握）–第四步，变换效率矩阵•4.1打勾（1）没有带圈零元素的行右边打勾（2）已打勾的列上被划去的零元素所在列下方打勾（3）已打勾列上带圈零元素所在行右边打勾（4）返回（2），直到打不出钩为止•4.2画线：已打勾的列画垂线，未打勾的行画水平线•4.3确定调整量：未被直线盖住元素中的最小者•4.4变换矩阵：（已打勾的）行减，已打勾的列加–未被直线盖住的元素减去调整量–恰好被一条直线盖住的元素不变–被两条直线盖住的元素加调整量•4.5返回第二步第六章动态规划•基本概念与基本原理（理解）•最短路问题（熟练掌握）–在什么条件下可以使用动态规划法–顺序解法和逆序解法的实现（在图上直接计算，最后写出最短路）•用动态规划方法求解静态规划（熟练掌握）–转换方法：先写成多层优化的形式，确定状态变量和状态转移方程–计算过程（连续型问题，求导后确定最优决策；离散问题，列表计算）第六章动态规划•动态规划应用的一般步骤（掌握）–建立静态规划模型–化为动态规划求解–典型应用一维资源分配问题等第七章图与网络优化•图的基本概念与基本结论（了解）•树的定义与基本性质（理解）•最小支撑树问题及其解法（掌握）–破拳法–避圈法•最短路问题及Dijkstra算法（熟练掌握）–直接在图上计算（注意，一定要保留过程计算中间划去的全部数据）–应用（设备更新问题）：先化为最短路问题，然后用Dijkstra算法求解•最大流问题及标号算法（熟练掌握）•最大流问题及标号算法•最大流问题的线性规划模型（掌握）•基本概念（理解）可行流，零弧、非零弧、饱和弧、非饱和弧，增广链截集、截量•基本定理（掌握定理的意义并能运用）–最大流判定定理：不存在增广链–最大流最小截量定理•标号算法（熟练掌握）题型•单项选择题：5小题，10分•填空题：5小题，10分•简答题：3小题，15分•建模题：1小题，5分•简单计算题：1题，5分•计算题及应用解答题：5题，55分章节分值分布1、线性规划与单纯形法192、对偶理论193、运输问题144、整数规划176、动态规划177、图与网络优化14