制定决策是运筹学应用的核心，而建立模型则是运筹学方法的精髓
2、运筹学研究的基本特征:系统的整体观念;多学科的综合;模型方法的应用
3、线性规划问题的数学模型的组成要素：决策变量;目标函数;约束条件
4、可行域是非空有界或无界的凸多边形,也可能为空集。
5、可行域为有界时，一定有最优解
6、可行域为无界时，可能有最优解，也可能无最优解
7、可行域为空集，一定没有最优解
若线性规划问题存在最优解，它一定可以在可行域的顶点得到。
若两个顶点同时得到最优解，则其连线上的所有点都是最优解。
8、线性规划问题的可行解X为基可行解的充要条件是X的正分量对应的系数列向量是线性独立的。线性规划问题的基可行解X对应于可行域D的顶点。若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。
9、线性规划问题的可行域是凸集。若线性规划问题有最优解，一定存在一个基可行解是最优解。基可行解与可行域的顶点一一对应，可行域有有限多个顶点。最优解必在顶点上得到。
10、对偶问题的基本性质：弱对偶性、最优性、无界性、强对偶性、互补松弛性（在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非0，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为0.）、线性规划的原问题与其对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量
11、运输问题数学模型的特点：
决策变量的个数为m×n个。约束条件的个数为m+n个。
运输问题的解中的基变量数一般为m+n-1个。
运输问题的约束方程组系数矩阵中，变量xij对应的系数列向量可表示为：
12、表上作业法适合于产销平衡的运输问题
13、整数规划最直观的求解方法就是枚举法。
14、分配问题也称指派问题，是一种特殊的整数规划问题
15、匈牙利法：从矩阵未被直线覆盖的数字中找出最小数k；对矩阵的每行，当该行有直线覆盖时，令ui=0，无直线覆盖时，令ui=k；对矩阵中有直线覆盖的列，令vj=-k，对无直线覆盖的列vj=0；每行每列都出现打()的0元素，这时已得到最优解
16、线型规划模型的局限性：严格满足全部约束条件；只能处理单目标的规划问题；各个约束条件都处于同等重要的地位。线性规划寻求的是最优解，而现实中通常找到满意解即可。
17、当希望恰好达到目标值时，目标规划目标函数形式为：
当希望实际值超过目标值时，目标规划目标函数形式为：
18、Pk>>Pk+1权系数是一个具体数字，系数越大，表明该目标越重要
19、
【例】某单位考虑职工的升级调资方案，依次遵循以下规定：
（1）不超过年工资总额60000元；
（2）每级的人数不超过定编规定的人数；
（3）Ⅱ、Ⅲ级的升级面尽可能达到现有人数的20%，且无越级提升；
（4）Ⅲ级不足编制的人数可录用新职工，又Ⅰ级职工中有10%要退休。
有关资料如下表，问如何拟定一个满意方案。
等级 工资额（元/年） 现有人数 编制人数 Ⅰ
Ⅱ
Ⅲ 2000
1500
1000 10
12
15 12
15
15 合计 37 42 解：设x1、x2、x3分别表示提升到Ⅰ、Ⅱ级和录用到Ⅲ级的新职工数。
确定各目标的优先因子P：
P1——不超过年工资总额60000元；
P2——每级的人数不超过定编规定的人数；
P3——Ⅱ、Ⅲ级的升级面尽可能达到现有人数的20%。
分别建立各目标约束。
1.年工资总额不超过60000元：
2000（10-100.1+x1）+1500（12-x1+x2）+1000（15-x2+x3）+d1--d1+=60000
2.每级的人数不超过定编规定的人数：
Ⅰ级：10（1-0.1）+x1+d2--d2+=12
Ⅱ级：12-x1+x2+d3--d3+=15
Ⅲ级：15-x2+x3+d4--d4+=15
3.Ⅱ、Ⅲ级的升级面尽可能达到现有人数的20%。
Ⅱ级：x1+d5--d5+=120.2
Ⅲ级：x2+d6--d6+=150.2
目标函数：minz=P1d1++P2(d2++d3++d4+)+P3(d5-+d6-)
20、图是对现实世界的一种抽象描述，表现为点和线的几何。
21、图的最基本的要素是点以及点与点之间的一些连线，点v表示我们要研究的对象，线e表示对象之间的某种特定关系。记作G={V，E}
22、
23、一个图中，如果每一对顶点之间至少存在一条链，称为连通图
24、一个无圈的连通图称为树，记作T（V，E）
25、
26、求最短路有两种算法：一是求某一点至其他各点之间最短距离的Dijkstra算法；另一种是求任意两点之间最短距离的矩阵算法。
27、所谓网络上的流，是指定义在弧集合上的一个函数f={fij}
28、容量限制条件：0≤fij≤cij，当某条弧满足fij=cij，称为饱和弧
29、截集：把网络中的发点和收点分开，并使s→t的流中断的正向弧的集合，叫做截集，也叫做割。
30、一般包含s点的点集合用V表示，包含t点的点集合用表示
31、截集的容量是指截集中弧的容量之和
32、增广链是从发点到收点的一条链，该链上所有指向为s→t的前向弧，存在f＜c；所有指向为t→s的后向弧，存在f＞0，这样的链叫增广链
33、网络图是网络计划技术的基础，它一般由作业、事项和线路三部分组成
34、作业也称为活动或工序，它是指在工程项目中需要消耗资源并在一定时间内完成的独立作业项目
35、事项也称结点或时点，是箭线之间的交接点，用圆圈“○”表示，并编上号码。它是指一项作业开始或结束的瞬间
36、线路是指从网络始点事项到达网络终点事项的任一条连续的线路
37、它既不消耗资源，又不占用时间，仅仅为了准确地表示作业之间的逻辑关系，在网络图中，一般用虚线箭头表示虚作业
38、网络图的绘制规则：（1）有向性，无回路（2）结点编号，从小到大，从左到右，不能重复（3）两点一线（4）箭线首尾都必须有结点，不能从一条箭线的中间引出另一条箭线来（5）源汇唯一（6）明确工序之间的逻辑关系
39、网络时间参数包括：
各项作业的作业时间；
结点的最早开始时间、结点的最迟结束时间；
作业的最早开始、最早结束时间；作业的最迟开始和最迟结束时间
单时差、总时差。
40、确定作业时间的方法主要靠经验估计，大致有两种方法：
1．单一时间估计法2、三点估计法（这种方法是对各项作业的作业时间，预先估计三个时间值：最乐观的完工时间、最保守的完工时间和最可能的完工时间，然后求出作业时间平均值。）T——作业时间平均值；a——最乐观的完工时间
b——最保守的完工时间；m——最可能的完工时间
41、每项作业的时间参数有四个：
作业的最早开始时间（TES（ij））
作业的最早结束时间（TEF（ij））
作业的最迟结束时间（TLF（ij））
作业的最迟开始时间（TLS（ij））
42、总时差为零的作业称为关键作业，将关键作业连起来就构成某一项计划任务的关键线路，它是网络图上时间最长的线路。
43
|
|
