大学生运筹学期末复习框架

本思维导图系通过个人所学运筹学知识以及个人期末考试要求绘制，存在作者个人对于运筹学复习的侧重点，可能有些部分与其他同学的运筹学学习范围有所不同，但还是希望通过这个框架导图能让同学们更通俗易懂地学习与理解运筹学的相关知识，形成复习框架，提高复习效率。

运筹学

一、 线性规划

线性规划标准型

标准型模板

标准条件

（1） 目标函数为Max

（2） 约束方程符号都为=号

（3） 变量Xi都非负，即都要大于等于0

（4） 右端常数项bi为非负，即大于等于0

建模

一维

二维

单纯形法

最大最小值单纯形法求解规则

步骤

大入小出（都>0），检验非正

将线性规划模型化为标准型

列出初始单纯形表

注意！列表时，基变量要跟其所在的系数方程对应，并不完全按照从小到大的顺序，重要的是按照系数方程的顺序才不会写错

确定入基变量

确定出基变量

标出主元素进行单位矩阵的迭代

标注主元素[入基变量与出基变量的交点数值]

迭代时注意算法，勿懵

看检验数，若检验数全部非正（即<=0），则停止计算得出最优解；若有正数，则继续迭代直到全部检验数非正

若求解最后非基变量（非单位矩阵的向量）的检验数为0，则表示有无穷多个解

人工变量法（大M法）

由于化为标准型过后线性规划模型可能不含单位（跨列）矩阵，就是就要创造人工变量，形成单位矩阵

创造变量时需注意

在目标函数中人工变量的系数：求Max时，系数为-M；Min时为+M

在约束中创造的人工变量为+1Xi

M为极大极大的正数

根据新得到的目标函数和约束条件列出单纯形表，用单纯形法进行计算

直到迭代出所有的检验数<=0全都小于等于0（非正），得到最优解，将其代入目标函数得到最优值

两阶段法

在大M法的基础上，第一阶段：列出只有系数为-1的人工变量的模型，进行单纯形法运算，运算到检验数都小于等于0

第二阶段：在大M模型的基础上，将目标函数中的人工变量去除去，再从第一阶段的最后一个表出发（目标系数跟变量改变），继续进行单纯形表的计算

注意！用最后一个表时，它的目标函数的系数即CB列要变成原目标函数的取值，而不是照抄最后一个表的CB列

直到迭代出所有的检验数<=0全都小于等于0（非正），得到最优解，将其代入目标函数得到最优值

二、 对偶问题

原问题与对偶问题

max变＝min约（等于）

min变≠max约（不等于）

无约束与‘＝’等号互换

对偶单纯形法

适用条件

1||| 右端常数项即b列至少有一个负数

2||| 单纯形表的检验数行（Cj-Zj）<=0的全部元素均小于等于零，即非正

步骤

将线性规划模型化为标准型

若b列无负数，则每个等式左右两边都要乘以（-1），打造出适用条件

列出初始单纯形表

注意！列表时，基变量要跟其所在的系数方程对应，并不完全按照从小到大的顺序，重要的是按照系数方程的顺序才不会写错

先确定出基变量

再确定入基变量

标出主元素进行单位矩阵的迭代

标注主元素[入基变量与出基变量的交点数值]

迭代时注意算法，勿懵

看检验数与b列，若在检验数全部非正<=0的基础上且b列数字>=0全部非负，需两个同时满足，则停止计算得出最优解；否则继续迭代直到全部检验数非正和b列全部非负

若求解最后非基变量（非单位矩阵的向量）的检验数为0，则表示有无穷多个解

与单纯形法的区别

单纯：大入小出（都>0），检验非正

对偶：小出小入（都<0），检验非正，b列非负

灵敏度分析

好像是不考的

大大大前提:化为标准型，然后进行单纯形法计算，求出最优解，关键是灵敏度的分析就算需要用到原题最终的单纯形表

B-1的含义：是指单纯形表中初始基变量在单纯形表计算的最终表中的系数矩阵

注意

类型

（1） 右端常数bi的变化

b'=B-1*b

（2） 目标系数Cj的变化

最终表的检验数=Cj'－Cb*Pj'

（3） 系数（列）向量Pj的变化

Pj'=B-1*Pj

最终表的检验数=Cj'－Cb*Pj'

（4） 增加一个新的约束条件（方程）

①添加到模型中去，进行相应的目标函数与系数方程的变化

②进行直接反映到大前提的最终表中去，增加新的行或（新的列）

注意关键！特殊之处

反映到最终表后时，因为新加了约束条件，故导致变化后的基变量对应的矩阵可能不是单位矩阵，故需要对表中包括b列的系数矩阵进行行初等变换，使得基变量的系数矩阵化为为单位矩阵

在进行迭代计算前注意b列是否有负数和检验数行是否全部非正，再决定用对偶单纯形法还是单纯形法进行计算

（5） 改变某一个约束条件

根据新的约束条件重新列出新的规划模型，重新列表计算即可

三、 运输问题

表上作业法

1. 列出产销平衡表和运价运量表

一般都是求目标最小值Min

2. 确定初始调运方案

最小元素法

在单位运价表中找到最小的运价（若有多个最小，则任选其一），对照着行与列的产销量填相应的数量，然后将已满足条件的行或列的其他格子打×划掉

注意！基变量（解）的个数＝【m(行数）＋n（列数）】－1

补基：当一个数字同时满足行与列的数量要求时，要在该行列任选一个空处X将其改为0

在剩下的未被划掉的运价中找最小数字，进行填数量与打×

重复上述步骤，直到所有的数量都被填写完或者是打×完，全部需求都被满足为止，即可得到一个初始调运方案

元素差额法（沃格尔法）

在单位运价表中找出每一行和每一列的最小元素和次小元素的差额

差值一样时，选择有最小运价的那一个

在行差额和列差额中选出最大者，并选择其所对应的行或列中的最小元素来安排调运方案，进行填数量与打×

补基：当确定最小元素后，发现在产销平衡表中最小元素所对应的行的产量等于所在列的需求量，这时单位运价表中要同时划去一行和一列，需要在划去的行和列的任一空格X处补“0”

在剩下未划去即未打×的元素中继续计算每一行每一列最小元素与次小元素的差额，然后重复第②步

由此继续计算未打×元素的行差和列差

重复上述步骤，直到所有的需求表格都被填满为止，即可得到初始调运方案

例子

3. 求检验数

闭合回路法

在给出调运方案的产销平衡表中，从每一个空格（非基变量X）出发找一条闭回路，以某个空格（非基变量）为起点，用水平或垂直线向前划，遇到数字后可转角90°，然后继续向前划，直到回到出发点为止。

注意拐角必须是数字才行

每个非基变量X都只有一条闭合回路

所有的闭合回路的检验数都大于等于0，即>=0为止（非负）

当检验数有多个负数，则选择最小的负数进行数量（运量）的优先调整

闭合回路的检验数计算：等于闭合回路拐角处的正负号对应的运价的相加减得到的最后的数

闭合回路法的调整

从检验数为负数对于的非基变量（X）处，依次在其闭合回路拐角处填＋号与－号

在该（X）闭合回路的负号（－）处，选择最小运量min，在该闭合回路各个拐角处根据其正负号对应地加上或者减去这个最小运量

当某个运量加减后为0时，改成X；若多个0，则任选其一变成X

调整后得到新的运量，后根据新的运量表重新画出所有的闭合回路，再进行检验

若所有检验数计算后的检验数>=0（非负），则停止计算，得出最优方案

位势法

列出运价运量表（主要是运价）

位势法的关键就是围绕基变量（数字）与非基变量X运价进行计算

在运价表的后面增加行Ui与列Vj，根据公式对带有数字运量（基变量）的运价进行计算，一步步求出Ui与Vj

子主题

求出所有的Ui与Vj后进行检验

检验数公式（运价）

检验数是用（非基变量）X的运价计算的

若所有位势法计算后的检验数>=0（非负），则停止计算，得出最优方案

若检验数中有多个负数，则选其中最小的负数，对该处运量进行闭合回路的调整，后根据调整后的运价表重新进行Ui与Vj的计算与公式检验，直到所有检验数都>=0

4. 所有检验数>=0

若满足，则可得到最优方案，对照运价表算出最小总运价

否则找出最小的负检验数用闭合回路调整，得出新的调运方案，后继续进行检验（建议用位势法）

5. 注意事项

产销不平衡

（1） 产大于销

增加一列虚拟销地，该列虚拟销地的总销量为产量－销量，填写在表中是该列某一处运量填写为（产量－销量的值），其余运量打×，虚拟销地的运价都为0

原问题

调整后

（2） 销大于产

增加一列虚拟产地，该行虚拟产地的总销量为销量－产量，填写在表中是该行某一处运量填写为（销量－产量的值），其余运量打×，虚拟产地的运价都为0

（3） 产销浮动

实际的填M，虚拟与浮动部分填0

若其最低需求为0，则也填0

（4） 求最大值问题

常用的

在得到最优运量方案时，再算最后的最大盈利时，要用最初始的的运价表去计算，而不是后面创造的新的运价表

不常用的

四、 整数规划与分配问题

分配问题的数学模型

假设X时，X的取值只有0或1

匈牙利法

适用条件

1||| 求最小值

2||| 所有元素都非负，即>=0

3||| 系数矩阵为M阶方阵

4|||

步骤

变换系数矩阵，使各行各列都出现0元素

（1） 先对系数矩阵所有行减去各自行中最小的数min

（2） 在上一步的基础上再对系数矩阵所有列减去各自列中最小的数min列（0），或者在没有0列减去该列的最小值列min

圈零o

（1） 先从行开始，对只有一个0元素的行（列）开始对这个0加圈o，将同行（列）的其他0划掉，记作Ø；

（2） 然后再从列开始，对只有一个0元素的列（行）加圈o，将同列（行）的其他0划掉，记作Ø；

（3） 重复上步，直到所有的0元素都被圈o出来或被划掉

进行试指派，以寻求最优解

打勾√

无圈行打√

横看空∅画列（√）

在打√行含∅的列打√

列看圈o画行（√）

在打√列含o的列打√

重复上述步骤，直到找不出要打√的行和列

画线

对没有打√的行划线

对打了√的列划线

若K=n(矩阵阶数)，但m<n(矩阵阶数)，则需回到圈0那一步进行试探，画圈

设直线数为K，若K<n(矩阵阶数)，说明必须再变换当前系数矩阵，才能找到n个独立的0元素，为此转到第5步

由此得到覆盖所有0元素的最少直线数

做最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多的独立0元素

继续调整

（1） 在矩阵未被直线覆盖的地方，找出最小值min（未覆盖）

（2） 在未被直线覆盖的所有元素都减去－min（未覆盖）

（3） 直线交叉的元素加上＋min（未覆盖）

（4） 被直线覆盖但不是交叉处的元素照写不变

设法使每一个行/列都要一个独立0元素

调整前

调整后

分配的特殊类型

1. 求最大值

2. 人数和任务数不相等

（1） 人多任务少

（2） 人少任务多

3. 一个人可完成多个任务的分配

4. 某人一定不能做某事

五、 目标规划

目标规划的数学模型

组成元素

（1） 目标函数

在目标规划中，常见问题中目标规划求解的一般都是Min

目标函数由优先级P和可调整的偏差变量d+与d-组成

目标函数中的偏差变量之间都是加＋号，即P*（＋d+＋d-）的形式，但是偏差变量有所取舍

其优先级的重要性决定优先级P的系数

（2） 约束条件方程

绝对约束：不可以修改；目标约束：可以通过调整偏差变量的方式进行调整

约束条件中填写所有的偏差变量时都是（＋d+－d-）的形式，所有的di+与di-都列出来

目标规划模型的约束条件方程都是等号＝

（3） 决策变量

刚性需求：Xj>=0

偏差变量：d+、d->=0

（4） 偏差变量

子主题

子主题

用单纯形法求解目标规划

老师最后没有教，可能不考