运筹学的简易总结，死亡排版与多图警告

使用书籍：《系统工程与运筹学》，焦爱英，机械工业，ISBN：9787111731627

第一章 系统与系统科学方法论

系统定义与四个条件

系统的定义：系统是由相互联系、相互依赖、相互制约、相互作用的若干部分，是按照一定的方式、为了一定的目的组合而成的存在于特定环境之中并具有一定功能的有机整体。这个整体本身又是它所从属的更大整体的组成部分。

系统存在所必须的四个条件：

1. 系统和要素
2. 系统和环境
3. 系统的结构
4. 系统的功能

系统的属性

1. 整体性：表现在系统目标、功能、行为和演化规律等的整体性。系统的整体性是识别不同系统和区分系统整体与部分的重要标志
2. 层次性：系统按规则被划分为各大子系统，它们之间就会因此形成一定层次结构
3. 集合性：系统都是由两个或两个以上可识别的部分（或子系统）所构成的多层次集合体。
4. 涌现性：不同层次的系统之间相互影响而产生不同层次之间存在不同的特性与行为
5. 关联性：系统各组成部分相互关联，一变则多变
6. 目的性：系统按照统一的目的将各组成部分组织起来的性质称为系统的目的性
7. 环境适应性：系统处于特定环境时会表现出主动适应与被动适应并因此而产生演化且趋于复杂

系统的分类

可分为单一标志分类与综合分类

单一标志分类如字面所示；

• 按照属性可以划分成自然系统、人造系统和符合系统
• 按与环境关系可以划分成封闭系统和开放系统
• 按状态可以划分成静态系统和动态系统
• 按形态可以划分成实体系统和概念系统

综合分类则是按研究目的将某些分类标志加以组合形成组合分类标志，并以该组合分类标志对系统进行分类或按系统的某些特征值，以某种数学方法（如聚类分析、判别分析等）对系统进行分类的方法。

实体系统和概念系统

• 由物质实体组成的系统称之为实体系统，物质实体包括矿物、生物、能量、机械、建筑物等各种自然物和人造物，又叫"硬系统"；人是具有主观能动性的物质实体
• 由概念、原理、方法、制度、规定、、习俗、传统等非物质组成的系统称之为概念系统，是人脑和习惯的产物，是实体系统在人类头脑中的反映，又叫“软系统“
• 两者是紧密结合在一起的，实体系统是概念系统的基础，概念系统为实体系统提供指导和服务

系统科学体系五大原则

• 整体论与还原论相结合
• 定性描述与定量描述相结合
• 局部描述与整体描述相结合
• 分析与综合相结合
• 确定性描述与非确定性描述相结合

第二章 系统工程与系统工程方法论

系统工程是一个从总体出发，合理开发、运行和革新一个大规模系统所需的思想理论、方法论、方法与技术的总称；是一门综合性的工程技术，是跨越许多学科的边缘科学，是一门战略科学

霍尔三维结构

如图所示：工作进程或工作阶段叫做时间维；把在系统各阶段中的思维过程叫作逻辑维；把每个思想过程中所涉及的专业知识叫作专业维。这就组成了包括时间、逻辑、专业三维度结构的空间

系统模型和系统模型化分类

模型是采用抽象、归纳、演绎、类比等方法，以适当形式描述系统结构或行为的仿制品

系统模型是对系统某一方面本质属性的描述，它一某种确定的形式（文字、符号、图表、实物等）提供关于系统的知识

系统模型的分类：

• 按形态分为实体模型、抽象模型
• 按对象分为经济模型、社会模型等
• 按研究问题分为宏观模型、微观模型等
• 按用途分为预测模型、结构模型、过程模型、决策模型等

实体模型和抽象模型

实体模型是把实体系统的功能和结构以原型为要素进行描述使其与系统原型基本相似的模型

抽象模型是用概念、原理、方法等非物质形态对系统进行描述得到的模型

抽象系统又可划分以下几类

• 数学模型
• 逻辑模型
• 模拟模型
• 分析模型

黑、白、灰箱理论

黑箱理论是指对内部结构和不清楚的系统，依据可控的输入引起可观察因素的变化，通过观察和实验来确定系统状态、行为和运行规律的理论；采用辨识法（研究不清楚结构系统所用的方法）

白箱理论是指对系统内部结构和行为清楚的系统，应用各种已知的知识进行描述而建立系统的理论;采用推理法（研究已知结构系统所用的方法）

灰箱理论是对系统内部结构和行为部分已知的系统，采用已知的科学知识建立模型，然后模拟所建模型进行补充和修正，从而建立系统模型的理论;采用模拟法（研究部分已知系统的理论）

第三章 系统工程的主要方法

系统综合评价

系统综合评价是利用多指标进行综合评价的一系列有效方法的总称。

可行方案比较、评价、选择

为了对可行方案进行排序，必须将各方案实现目标的程度量化为无量纲的综合指标

实现比选的技术路径如下

1. 确定各指标的重要性（权重）

   a.采用对比法；菲尔德法、专业评分法（定性），两两对比法、连环比率法（定量）

2. 确定指标值以及评价标准
3. 指标标准化
4. 计算方案的综合评价值
5. 按综合评价值对方案排序

指标标准化

指标的标准化是指将不同量纲、不同数量级和不同评价标准的指标，通过适当的变换、化为无量纲的标准化指标的过程称之为指标的标准化

分为以下三种类型

AHP法（层次分析法）

概念如下所示:

其基本做法分为以下四点

1. 建立分层递阶结构模型
2. 构建判断矩阵
3. 单排序
4. 总排序

建立分层递阶结构模型

构建判断矩阵

使用上层某元素对下层元素之间进行两两对比,并按照九级评分标准评分并用矩阵描述，这样得到的矩阵就是判断矩阵

在得到判断矩阵后还需要验证其准确度

单排序

包括和法与方根法

总排序

模糊综合评价

模糊综合评价法是一种基于模糊数学的综合评价方法，该综合方法根据模糊数学的隶属度理论把定性评价转化为定量评价

该方法具有结果清晰、系统性强的特点，能较好地解决模糊的、难以量化的问题，适合各种非确定性问题的解决。

第四章 静态线性系统最优化模型及求解方法

最优化

系统最优化是在系统目标分析、环境分析和系统预测的基础上，通过建立最优化模型实现系统的定量化，通过模型的求解，为系统运行在最有状态提供科学决策依据的过程和方法的总称。

（在一定限制条件下实现系统收入最大(小)化的过程）

标准型

图解法

图解法就是利用约束方程找出可行域，再用等Z值线确定使目标函数达到极大或极小的顶点，该顶点的坐标就是最优解

最优解一定在顶点上达到

图解法一般会出现以下四种情况

单纯形法

人工变量引入原因

当线性规划模型的约束条件中包含等式和“>=”类不等式时，很难一下找出第一组可行解，为了仍然能使用单纯型法，故需要引入人工变量。当人工变量全为0时，所求的解就是原问题最优解

包括两阶段法和大M法

灵敏度分析

• 参考视频

灵敏度分析是对线性规划求解结果进行分析的一种方法，用以研究参数A，C，b受到客观条件影响时最优解的变化情况

对偶理论

• 参考视频

使用对偶问题的情况：

1. 所建模型变量不多，但约束很多
2. 处理问题时需要从不同角度观察研究
3. 处理问题是需要分析某种资源的增加或减少对目标值的影响程度

对偶理论：

1. 若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等；若原问题解无界，对偶问题无最优解
2. 原问题的检验数对应于其对偶问题的一组基解，基矩阵B为最优基，则最优基下的检验数对应于对偶问题的最优解
3. 对偶问题的最优解对应原问题最优基下的检验数(与2相同)
4. 在线性规划最优解中，若对应的某一约束条件的对偶变量值非零，则该约束条件取严格等式；如果约束条件取严格不等式，则对应的对偶变量一定为零

求一个线性规划的对偶问题：大同小异

max大同，即min的约束条件与max变量符号相同，min的变量符号与max的约束条件的符号相反
min小异，即max的约束条件与min的变量符号相反，max的变量符号与main的约束条件符号相同

运输问题

• [参考视频]()(https://www.bilibili.com/video/BV1Rz4y1X7D8)

使用最小元素法+位势法

指派问题

• 参考视频

使用试指派+圈0法

1. 减行列最小值(如果是max型则先用矩阵中最大值减原矩阵作为初始矩阵)
2. 在0元素最少的行优先选择0元素并将其圈出
3. 标记无圈出0元素的行、在标记的行中标记未选择的0元素所在列、在标记的列中选择有标记0元素的行（无、有、有）
4. 在未划线的行中找到最小值min
5. 令行-min、列+min
6. 重复以上步骤

第六章 图与网络最优化方法

树的定义和性质

定义

树是指连通且不含圈的图

性质

1. 树的人一两顶点之间存在且仅存在一条链，如果去掉树中任意一条弧，则图是不连通图
2. 如果用弧把任意不相邻的顶点连接起来，仅存在一个圈，再去掉该圈的另一个弧，则又可得到另一颗树
3. 若树的顶点和边数分别为n和m，则m=n-1

最小部分树

在一个图中，包含所有顶点的树叫做部分树，属于部分树的边叫做内边，不属于部分树的边叫做外边

内边权值总和最小的部分树为最小部分树

一笔画问题

定理一：若图G的每个顶点所关联的边数是偶数条，则图G是欧拉回路，这样的图能够一笔画出

定理二：若除链的端点以外的每个端点所关联的边数是偶数条，则图是欧拉链，若想走过该图的所有的边而不走重复路，就只能从一个奇点出发走到另一奇点

最短路问题

使用狄克斯特拉法

最大流问题

可行流

可行流是网络上的一个流，它应满足两个条件

• 每一条弧上的实际流量小于等于弧的容量
• 中间点的流入量和流出量相等

对于一个网络，其所有可行流中流量最大的可行流称之为最大流

饱和弧

对可行流上的某一条弧，若该弧上的实际流量=容量，则称其为饱和弧，否则为非饱和弧

若某弧上的实际流量为零，则称其为零流弧

增广链

设f是网络上的一可行流，若在起点S与终点T之间有一条链u，规定其方向为S-T。链上相应弧按u方向分成两类，与u方向一致的为前向弧，相反的弧为后向弧

若f上的弧的流量满足：

• 前向弧不饱和
• 后向弧非零流

则称该链为增广链

割集

用一条线将一个图分为两个集合的线叫做割集（不会概括了）

最大流-最小割定理

在一个网络中，从源点S到汇点T的最大流量等于把S和T分开的最小割集的容量

在一个连通图中，称容量最小的割集为最小割集

画最小割集的技巧：前向饱和后向零流的弧

第九章 系统决策

系统决策是指在一定的条件下，根据系统的状态，在可以采取的各种策略中，依据系统目标选取一个最优策略并付诸实施的过程

决策目标是指决策者希望达到的状态，工作努力的目标，一般而言，决策者追求的是利益最大化

风险型决策

风险型决策是指在不确定因素概率已知的情况下，无论选择哪种决策都要承担一定风险的决策

这种决策具有以下特征：

• 决策者有明确的决策目标
• 有两种以上决策者无法控制的不确定因素
• 有两个以上方案可以供决策者选择
• 可估计出不同方案在各种不确定因素下的损益值
• 可估计出各种不确定因素出现的概率

收益矩阵法

决策树

决策树是一种由节点和分支构成的由左向右横向展开的树状图形

不确定决策

不确定决策与风险型决策的区别在于对不确定因素的发生概率不能作出估计。因此这类决策有完全的不确定性，故称为不确定决策

六种决策方法：

目标规划

注：凡在目标约束中描述过的，在绝对约束中不再重复出现

第十章 网络计划技术

关键线路法和计划评审技术的区别与联系

区别：

联系：两者的网络图形和计算方法基本相似

网络计划图的优点

• 利用网络图模型，能够清楚的表达各工作之间的逻辑关系
• 通过网络图的时间参数计算，可以找出网络计划的关键工作和关键线路
• 利用网络计划可计算出除了关键工作外其他工作的机动时间，进行资源合理分配
• 可利用计算机辅助手段，进行绘图、计算和跟踪管理

图上作业法