第一章 线性规划及单纯形法
-
图解法 单纯形法 大m法 看案例（综合题）
-
化标准形式
-
目标函数的转换
-
min z变为max z
-
-
变量的变换
-
变量取值无约束
-
-
约束方程的转换
-
≤：加一个松弛变量
-
≥：减一个剩余变量
-
-
变量符号≤0的变换
-
保持变量≥0
-
-
-
图解法
-
作图的关键有三点：
-
(1) 可行解区域要画正确
-
(2) 目标函数增加的方向不能画错
-
(3) 目标函数的直线怎样平行移动
-
-
单纯形法
-
1、化为标准形
-
2、初始基可行解 （单纯性表）
-
单纯性表：（松弛/剩余）变量系数Cb,基变量x,基变量值b 基变量系数a,检验数，比值
-
-
3、最优性检验
-
只有检验数为负数或0时才有最优解
-
-
4、新单纯性表
-
换入基变量 （检验数）
-
选择检验数最大的对应基变量 （若最大检验数相同，任选）
-
-
换出基变量 （比值θ = b/a）
-
选择比值较小的对应基变量换出 （比值非负，相同换角标最小，人工变量优先换）
-
-
构造单位阵
-
换入换出交叉处
-
a变1
-
a所在列的其余元素变0
-
（ps：行变换包括基变量值b）
-
-
-
-
-
人工变量法 （大M法）
-
方法
-
1、先将线性规划问题化为标准形 （看是否有单位矩阵，如果没有，继续）
-
2、化为人工变量单纯形法数学模型
-
目标函数：加入人工变量，令其系数为（-M）
-
约束：在存在“≥”或“＝”型的约束中添加人工变量，系数为1
-
-
3、单纯性表
-
cxb，a同上
-
按照约束顺序写基变量x
-
-
检验数：不用算可能换出基变量的检验数，均为0，不用写在表中。
-
-
4、最优性检验
-
只有检验数为负数或0时才有最优解
-
-
5、新单纯性表
-
换入基变量（检验数）
-
换出基变量（比值θ = b/a）
-
-
构造单位阵
-
换出的基变量不再将其系数（初始基）a填入表中
-
-
-
-
-
第二章 线性规划的对偶理论
-
对偶问题
-
转换方法（上c下b变上bt下ct，a变at）
-
通用做法 （max->min：先相同后取反） （min->max：先取反后相同）
-
约束条件看变量符号（相同） 变量符号看约束条件（取反） 无约束和＝总是互换的
-
-
-
第三章 运输问题
-
产销平衡 表上作业法 应用
-
表上作业法 （产销平衡）
-
1、找出初始基本可行解； （给出原方案）
-
最小元素法
-
找最小元素变值（产销运算） （最小相同找产销平衡的元素）
-
当产量或销量为0时，划去对应行列 （产销相等任选划去行列格添一个0保证m+n-1）
-
-
-
2、检验数表 （检查空格的检验数是否为负）
-
位势法 行Ui列Vj
-
先用已知格的原数据求位势
-
空格原数据减位势得其检验数
-
-
-
3、新方案 （检验数有负，闭回路调整运量）
-
（1）确定调整量θ
-
回路中找出所有偶数顶点的调运量取最小值
-
-
（2）调整方法
-
顶点：偶减奇加
-
-
-
4、位势法再检验
-
若检验数没有负值，说明新方案为最优解。
-
-
-
产销不平衡问题
-
可转化为平衡问题 增加一个假想产地
-
总产量＜总销量
-
其产量是（总销量－总产量)
-
到各销地的单位运费
-
M：刚性需求（最低需求）
-
0：弹性需求（最高需求）
-
-
-
-
-
第四章 整数规划与分配问题
-
分配问题与匈牙利法（熟练）
-
分配问题
-
1、效率矩阵[aij]：表中数字
-
2、定义逻辑变量
-
-
3、建立数学模型
-
-
4、匈牙利法
-
1、分别减去矩阵行列中的最小元素 （先行后列）
-
2、圈0划的行列数是否满足m（行列数）
-
0元素打（），行有划列，列有划行 （行列中两个0跳行列）
-
-
3、划去的直线数不满足m
-
找最小元素k
-
确定位势
-
无直线：ukv0
-
有直线：u0v-k
-
-
-
减去位势得新矩阵
-
-
4、再看m是否满足
-
若满足则令打（）的0元素变1得到最优解
-
-
-
-
-
第六章 图论与网络分析
-
（重点，熟练掌握三算法） 树图和图的最小部分树 最短路问题 网络的最大流
-
图的最小部分树
-
避圈法
-
法一
-
添加相邻最小边
-
-
法二
-
添加最小边
-
-
-
破圈法
-
删除回路最大边
-
-
注意：
-
1. 一个图的最小部分树不唯一
-
2. 每个最小部分树中所有边权的总和一定都是相同的，即都达到了最小。
-
-
-
最短路问题
-
狄克斯屈拉( Dijkstra )算法 （标号算法）
-
起始点s标0，找与s相邻点距离最小的点
-
一直标号为该点与s的距离，加粗边
-
直到标号t
-
-
矩阵算法
-
建立距离矩阵
-
设 dij 表示图中两相邻点 i 与 j 的距离，若 i 与 j 不相邻，令 dij =∞，显然 dii =0。
-
-
-
-
网络的最大流
-
标号算法 （Ford-Fulkerson）
-
1、发点标号（0，∞）
-
2、相邻点标号 （前一点代号， ε(s)或ε( h )）
-
正向弧用ε(s) ε( j ) = min{ε( i ) ,(cij -fij)}
-
流量f＜容量c （有增长空间，f-c标号）
-
f = c （无增长空间，不标号）
-
-
反向弧用ε( h ) ε( h ) = min{ε( i ) , fhi)}
-
直接选流量最小的
-
-
-
3、找增广链
-
t未标号，说明无增广链，给定流量为最大流量。
-
t有标号，反向追踪法（从t开始连接标号点）得增广链。
-
-
4、修改原流量（正加反减）
-
正向弧+1，反向弧-1
-
-
5、再标号（标号中断）得到可行流
-
-
-
-
