本文目录
大学运筹学考试哪些是重点
运筹学重点内容：第一章 1.掌握LP数学模型的基本特征与形式 根据背景资料建立LP数学模型的方法技巧（例1） （会用图解法求解简单的LP问题 不做重点要求） 2.理解LP问题的解相关概念与判别准则（可行解、基解等） 3.熟悉单纯形表的形式与单纯形表的计算步骤 4.熟练运用普通单纯形表法、人工变量法（包括大M法、两阶段法）求解LP问题 提示：单纯形表的表格线必须正确画出，单纯形表迭代过程要写清楚（如：换入、换出变量（θ值要算出）的确定和主元） 第二章 1.理解与掌握LP原问题与对偶问题的关系（课本中的表），了解LP问题的对偶理论 2.当已知LP问题的原问题及其最优解时，能根据对偶性质直接写出对偶问题和最优解（必须说明具体依据） 3.掌握对偶单纯形法的使用条件，熟练运用对偶单纯形法解适当的LP问题 4.了解影子价格的含义与性质 5.掌握灵敏度分析的方法 ①变量的价值系数Cj ②约束条件右端项bi ③ 第三章 1.了解运输问题数学模型的特点 2.熟悉表上作业法的步骤。掌握初始基可行解的求法，会对求得的或给定的可行解进行最优性检验。掌握解的改进方法 注意：每得到一个基可行解，就应画一张运输表，运输表的画法要规范，检验数和解必须填入表中的适当位置，必须经过检验才能判定最优解 提示：也可能给一个初始基可行解额，要求从第2个步骤往下做 第四章 1.了解目标规划数学模型的特点 2.掌握目标规划问题的建模 3.掌握求解目标规划问题的单纯形法 第五章 1.了解整数规划模型的特点，整数规划的解与其松弛问题的解的关系 2.掌握求解整数规划问题的割平面法 3.掌握0—1型变量的应用和0—1型整数规划问题的建模 4.了解指派问题数学模型的特点，掌握匈牙利算法的步骤，熟练运用匈牙利法求解指派问题 注意：运用匈牙利法求解指派问题时过程要写清楚，关键步骤不能忽略第七章 1.理解动态规划的基本概念和基本原理 2.掌握常见动态规划问题的建模与求解方法 建立DP模型 ① 选定解法 ② 划分阶段（按什么划分为几个阶段） ③ 确定状态变量（说明其意义---表示什么） 状态集合（状态数量的取值范围（所有可能出现的状态）） ④ 确定决策变量（说明其意义----表示什么） ⑤ 允许决策集合（说明决策变量允许的取值范围） ⑥ 状态转移方程（从k阶段转移到k（或前）一阶段的递推式） ⑦ 阶段指标（第k阶段在状态为sk决策为uk 时的效果） ⑧ 最优指标函数（说明其意义---表明什么） ⑨ DP基本方程（递推关系与边界条件） 可重点复习： ①一维资源分配问题（含部分静态规划问题建模与求解 例5 习题7.6 7.9（3）） ②生产与存贮问题的动态规划建模（例8 习题7.3） ③采购与销售问题的动态规模建模（例9） 第八章 1.理解图的有关概念、分类及其性质 2.掌握解最短路问题的Dijkstra标号算法 3.理解网络的基本概念。掌握寻求网络最大流、最小割的Ford—Fulkerson标号算法 注意：用Dijkstra、Ford—Fulkerson算法解题时须简要写出步骤，并在图上作必要的标记（每个可行流画一张图）
匈牙利法没有交点
摘要您好，亲，感谢您的耐心等待，为您查询核实到⑴ 匈牙利算法步骤
① 矩阵规约.
遍历矩阵的行,求得各行的最小值,并对各行上的所有元素减去其最小值.
遍历矩阵的列,求得各列的最小值,并对各列上的所有元素减去其最小值.
② 统计各行列0元素个数
遍历各个行和列的元素,统计出各行和列的0元素个数.
③ 标记0操作.
遍历矩阵的行,找到只含一个0元素的行,将该0元素“画圆“.
再遍历该0元素所在的列,将该列上的0元素“画撇“.
遍历矩阵的列,找到只含一个0元素的列(“画撇“的0元素不看作自由0元素).
再遍历该0元素所在的行,将该行上的0元素“画撇“
④ 如果“画圆“0的个数等于矩阵维数,则输出结果.即调用7.
如果还存在自由0元素,则调用7.
如果不存在自由0元素,且“画圆“0的个数少于矩阵维数,则调用5.
⑤ 用最少直线覆盖.
a．对没有“画圆“0元素的行打√号．
b．对已打√号的行中所有含“画撇“0元素的列打√号．
C．对打√号列上有“画圆“0元素的行打√号．
d．重复(b)(c)直到得不出新的打√号的行列为止．
e．打√号的列画纵线，没打√号的行画横线.
这就是覆盖所有0元素的最少直线集合．
⑥ 增加(转移)0元素.
a．求出未被直线覆盖的元素中的最小值k．
b．对打√行减去k，对打√列加上k
c. 转到第2步骤.
⑦ 剩余自由0元素处理
a.取存在自由0元素的行中的第一行(也可以取自由0元素最少的行)
b.遍历a中所选行,依次取该行中的自由0元素.
执行:
c.对该自由0元素进行画圆操作.
d.将该元素所在行列的其它自由0元素画撇
e.执行标记0操作,即调用③.
f.执行④进行转换.
⑧ 结果输出
咨询记录 · 回答于2021-10-31
匈牙利法没有交点
您好，您的问题我已经看到了，正在整理答案，请稍等一会儿哦~
您好，亲，感谢您的耐心等待，为您查询核实到⑴ 匈牙利算法步骤
① 矩阵规约.
遍历矩阵的行,求得各行的最小值,并对各行上的所有元素减去其最小值.
遍历矩阵的列,求得各列的最小值,并对各列上的所有元素减去其最小值.
② 统计各行列0元素个数
遍历各个行和列的元素,统计出各行和列的0元素个数.
③ 标记0操作.
遍历矩阵的行,找到只含一个0元素的行,将该0元素“画圆“.
再遍历该0元素所在的列,将该列上的0元素“画撇“.
遍历矩阵的列,找到只含一个0元素的列(“画撇“的0元素不看作自由0元素).
再遍历该0元素所在的行,将该行上的0元素“画撇“
④ 如果“画圆“0的个数等于矩阵维数,则输出结果.即调用7.
如果还存在自由0元素,则调用7.
如果不存在自由0元素,且“画圆“0的个数少于矩阵维数,则调用5.
⑤ 用最少直线覆盖.
a．对没有“画圆“0元素的行打√号．
b．对已打√号的行中所有含“画撇“0元素的列打√号．
C．对打√号列上有“画圆“0元素的行打√号．
d．重复(b)(c)直到得不出新的打√号的行列为止．
e．打√号的列画纵线，没打√号的行画横线.
这就是覆盖所有0元素的最少直线集合．
⑥ 增加(转移)0元素.
a．求出未被直线覆盖的元素中的最小值k．
b．对打√行减去k，对打√列加上k
c. 转到第2步骤.
⑦ 剩余自由0元素处理
a.取存在自由0元素的行中的第一行(也可以取自由0元素最少的行)
b.遍历a中所选行,依次取该行中的自由0元素.
执行:
c.对该自由0元素进行画圆操作.
d.将该元素所在行列的其它自由0元素画撇
e.执行标记0操作,即调用③.
f.执行④进行转换.
⑧ 结果输出
什么是匈牙利算法
谈匈牙利算法自然避不开Hall定理，即是：对于二部图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X的任意一个子集A，和A邻接的点集为T(A)，恒有： │T(A)│ 》= │A│ 匈牙利算法是基于Hall定理中充分性证明的思想，其基本步骤为： 1．任给初始匹配M； 2．若X已饱和则结束，否则进行第3步； 3．在X中找到一个非饱和顶点x0，作V1 ← {x0}, V2 ← Φ； 4．若T(V1) = V2则因为无法匹配而停止，否则任选一点y ∈T(V1)\V2； 5．若y已饱和则转6，否则做一条从x0 →y的可增广道路P，M←M?E(P)，转2； 6．由于y已饱和，所以M中有一条边(y,z)，作 V1 ← V1 ∪{z}, V2 ← V2 ∪ {y}， 转4； 设数组up - 表示该条边是否被覆盖 。 首先对读入数据进行处理 ，对于一条边(x，y) ，起点进集合up，终点进集合down。 标记map中对应元素为true。 1. 寻找up中一个未盖点 。 2. 从该未盖点出发 ，搜索一条可行的路线 ，即由细边出发， 由细边结束， 且细粗交错的路线 。 3. 若找到 ，则修改该路线上的点所对应的over1，over2，use的元素。重复步骤1。 4. 统计use中已覆盖的边的条数total，总数n减去total即为问题的解。
KM算法的注意
每一次找匹配时USED都是清0的，这是为了记录什么可以找，什么不可以找，说白了，这个模块就是一个递归的过程，USED的应用就是为了限制递归过程中的寻找范围，从而达到“不好则换，换则最好”，这里的最好是“新换”中最好的。匈牙利算法解题是极为简单的，但是图论的难并不是难在解答，而是建图的过程，也难怪会有牛曰：用匈牙利算法，建图是痛苦的，最后是快乐的。当然，我们这些◎#！◎◎也只能搞搞NOIP了，一般不会太难，所以此算法，极为好用。KM算法：最大流的KM算法，又算的上算法世界中的一朵奇葩了。解决最大流问题可以使用“网络流”，但较为繁琐，没有KM来得痛快，下面是KM算法的核心模块： function find(x:byte):boolean;vary:byte;beginfind:=false;vx,d);end;until false;总结起来便是：有机会就上，没有机会创造机会也要上！
