运筹学基础与应用(简洁版总复习)
第一章 线性规划及单纯形法
图解法 单纯形法 大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、再标号(标号中断)得到可行流