运筹学1复习提纲

《运筹学1》复习提纲
第一章 线性规划和单纯形法
1、 规划问题的三要素:1,决策变量。

2，目标函数。

3，约束条件。

2、 线性规划问题的条件：决策变量为可控连续变量，目标函数和约束条件都是线性的。

3、 线性规划问题的标准形式：1，目标函数极大化，2，约束条件全为等式，且右端常数全
为bi 全为非负值。

3，变量取值全为非负。

4、 标准化方法：1，极小化极大，极大值前加负号；2，约束条件不等式化为等式，当为《=
时需加一个松弛变量，》=时需减一个剩余变量。

3，取值无约的变量：可令x=x ’-x ”.其中x ’x ”>=0。

4，变量Xj<=0;可令Xj ’=-Xj 显然Xj 》=0。

5、 松弛变量和剩余变量是在实际问题中未被充分利用的资源和超用的资源数。

均为转化为
价值和利润，故它们在目标函数中的系数均为零。

5、
5可行解:满足标准约束条件的解，X=（x1,x2,x3…）称为线性规划问题的可行解。

6、 可行域;全部可行解的集合为可行域。

7、 最优解:使目标函数达到最大值的可行解称为最优解。

8、 基：A 为约束方程组mxn 阶系数矩阵。

秩为m 。

B 为矩阵A 中一个mxm 满秩子矩阵。

称B
是线性规划问题的一个基，
9、 基向量：基中的每一个列向量Pj(j=1,…m)称为基向量。

10、 基变量：与基向量对应的变量Xi 称为基变量。

11、 非基变量：线性规划中除基变量以外的其他变量称为非基变量。

12、 基解:令所有非基变量为零，求出m 个变量的唯一解，再加上非基变量取零的值，
有X=（x1,x2,x3…xm,0,0,0）称X 为基解。

13、
、基可行解：满足变量非负的约束条件的基解称为基可行解。

14、
（基解总数至多m n C 个）、可行基：对应基可行解的基为可行基。

15、
、最优基;与基最优解对应的基。

16、
各种解之间的关系 17、
图解法 18、
检验数 1
m j j j j i ij i c z c c a σ==-=-∑ 10、
11、单纯形表的结构：前两行（1价值行2变量行），最后一行（检验数行），前三列（1基价值列2基变量列3基解列），后一列O 列，主体部分。

12、单纯形法的步骤1.求出线性规划的初始基可行解，列出初始单纯形表，
2，进行最优性检验。

3，从一个基可行解转换到另一个目标函数值更大的基可行解。

如：确定换入基的变量，确定换出基的变量，得到新基。

13、人工变量法（1）大M法
（2）两阶段法
14、单纯形法的向量矩阵描述（不考）
初始表中的基变量在最终表中的矩阵是B-1
最终表中的基变量在初始表中的矩阵是B
课后练习
1.1,1.2(b),1.3(a),1.6(a),1.7(a),1.8,1.12,1.14
第二章线性规划的对偶理论
1、原问题的基本形式LP1 max z=2*x1+3*x2
2*x2+2*x2<=12
4*x1<=16
5*x2<=15 x1,x2>=0;
对偶问题的基本形式LP2 min w=12*y1+16*y2+15*y3
2*y1+4*y2>=2
2*y1+5*y3>=3 y1,y2,y3>=0
2、原问题与对偶问题的互化:原问题（对偶问题）对偶问题（原问题）
目标函数max 目标函数min
变量
3、对偶问题的基本性质
1)弱对偶性
2)最优性
3)无界性
4)强对偶性
5)互补松弛性（由松得紧性）
6)互补的基解
4、利用对偶理论求最优解的方法
5、影子价格
6、灵敏度分析
，可使最优解不变
1)分析C
j
2)分析b
，可使最优基不变
i
3)增加一个变量的分析
课后练习
2.1(a,b),2.2,2.4,2.9(a,b,c)
第三章运输问题
1、运输问题的已知条件：产销平衡表，单位运价表
运输问题有最优解的条件：产销平衡
2、m产n销的运输问题有mn个决策变量，有m+n个约束条件，有m+n-1个基变量（有数字格），有mn-(m+n-1)个非基变量（空格）
3、调运方案表（基可行解）：有数字格，空格
4、空格的闭回路的构成
闭回路的作用：
1)计算检验数
2)改进方案
5、利用检验数判断调运方案的最优性
若有负检验数，则此方案要改进；
若无负检验数，则此方案为最优方案。

6、表上作业法的步骤
1)确定初始方案：最小元素法或沃格尔法
2)求检验数：闭回路法或位势法
3)判断最优性
4)改进方案
7、产销不平衡的运输问题的处理
若产大于销，则增加虚拟的销地，其销量为总产量-总销量，从各产地至该销地的单价为0；若销大于产，则增加虚拟的产地，其产量为总销量-总产量，从该产地至刚性销地的单价为M，至弹性销地的单价为0.
课后练习
3.1,3.5(a,b,c),3.6,3.7,3.10
第四章整数规划与分配问题
1、整数规划
2、整数规划的分类：纯整数规划和混合整数规划
3、整数规划的松弛问题
4、松弛问题的最优解与整数规划最优解的关系
5、0-1变量（逻辑变量）
0-1规划
6、0-1变量在建模中的作用
7、分配问题
已知条件：m阶的效率矩阵
M阶标准分配问题有m2个0-1变量，有2m个约束条件，是特殊的LP/IP/AP/0-1规划，一定有最优分配方案
8、匈牙利法
1)适用范围
2)步骤：造0，画直线，打破僵局
3)两个说明：
对于目标极大化的分配问题；
当人数大于工作数时，增加虚拟的工作，每个人完成虚拟工作的时间为0；
当工作数大于人数时，增加虚拟的人，虚拟的人完成各项工作的时间为0或M或其它。

课后练习
4.1，4.2，4.3，4.5，4.6，4.13，4.16
第六章图与网络分析
1.(无向)图G={V,E},点,边,点与边之间的关联关系
2.图的阶
3.网络图(赋权图)
4.简单图
5.连通图
6.零图,完全图,完全偶图,树
7.点的次,孤立点,悬挂点
8.子图,部分图,部分树
9.树的相关结论
10.最小部分树的求法:避圈法,破圈法
11.最短路或最短距离的求法:狄克斯屈拉(dijkstra)标号算法
12.有向图D=｛V,A｝，点的分类，弧的容量，弧的流量，可行流的条件，总流量，网络的
最大流，割，割的容量，前向弧，后向弧，增广链的条件，
重要结论：最小割的容量=最大流的流量；
最大流的判断方法：是否有增广链
13.最大流的求法：标号算法
14.最小割的求法：标号中断时，从已标点指向未标点的前向弧
课后练习
6.1,6.2,6.3,6.4,6.5,6.7,6.14。