运筹学

定义

Operations Research。运用科学的方法，如分析/试验/量化，对问题进行定量分析，为决策者提供最优方案，以实现最有效的管理。

线性规划（LP）

线性规划是指已多个线性约束条件，求多项式最值问题。

一般可以化为以下一般形式

plan-lineplan

通过加入松弛变量转化为标准式

plan-lineplanstandard

可行解

• 如果问题存在可行解，则可行域必然是凸集
• 基可行解对应于可行域的顶点
• 如果可行域有界，最优解一定在顶点处

单纯形解法

假设有max z = ax1 + bx2

基变量为x3,x4,x5

通过在非基变量寻找最大因子，并进行换基运算

最终化为z = c - dxn - fxm得最优解c

• 可以通过单纯形表格法将上述过程转换为表格，便于计算机运算

基可行解的意义？

大M法

问题有可能在加入松弛变量后，没有基解

此时通过再加入松弛变量和剩余变量，再通过单纯形求解

如果剩余变量M得x不为0，则无解，否则存在最优解

plan-m

两阶段法

对于大M法，计算机非常难计算M，所以先通过构造w，在原有约束的条件下，求min(w)，若为0，则去掉人工变量，通过单纯形求解，否则无解

w=x(n+1) + ... + x(n+m)

x为m的人工变量

整数规划（IP）

plan-ip

分支定界解法

• 通过单纯形求解得X
• 如果不是全部x都为整数，则任意选择一个x，进行x<[x] or x>[x]+1分割
• 然后分别对分支进行单纯形求解，直到遇到最优解

0-1整数规划

plan-0-1

通过枚举所有X的排列组合得最优解

可以通过增加过滤条件和动态改善过滤条件，来加速计算过程

例如z = 3x1 - 4 x2 + 8*x3

可得 3x1-4x2+8*x3>=8过滤条件

指派问题

如下图，求指派代价最小

plan-xiong

匈牙利解法

通过不断的从各行或各列中，减去最小的数，得到矩阵

plan-xiong-re

进行试分配，如果成功，得到最优解

例如，对没有0的行打勾，对此列打勾，对列对应0的行打勾

plan-xiong-2

对这两行，进行减最小值运算，并对第一列加最小值运算

plan-xiong-3

再进行试分配

直到得到解

动态规划

通过对N维问题简化成多个一维问题来解决

例如f(n) = f(n-1) + f(n-2)

网络计划

例如可以把问题描述成

plan-network

参数计算

• 最早开始时间
• 最迟开始时间
• 最早结束时间
• 最迟结束时间
• 关键路径--最长路径

非确定性网络计划

pending

优化

• 减少关键路径时间
• 支援关键路径

plan-time

• 向非关键路径要资源

对策论

假设

• 参与人是理性的
• 有这些理性的共同知识
• 直到对策规则

要素

• 局中人
• 策略集
• 支付赢得函数

最优纯策略

通过最小最大策略树，搜索出利己最优解

如果双方的最优解处于同一个，则为纳什均衡，也称为鞍点

混合策略

如果通过最大最小策略不能得到鞍点，则需要通过引入xi概率选择i，并计算概率的期望，当最优期望时，xi的取值，则为最优解