第一讲 运筹学-模型 理论 算法_运筹算法

运筹学的基本概念

1、筹—算筹 （古代用于简单计算的小木棍）。

2、运筹学：主要研究人类对各种有限资源的运用以及筹划活动，以期通过发现其中的数学问题和规律，提出相应的求解方法，并应用于实际活动中，以发挥资源的最大效益，达到总体最优的目标。

运筹学相关问题

1、中国邮路问题、戈尼斯堡七桥问题、旅行商问题、欧拉对以上问题进行了研究并且得出结论

2、欧拉对以上问题研究得出的结论：
（1）一个图是欧拉图，当且仅当该图是不含奇数度结点的无向连通图，即可以一笔画，即经过每条边一次并且最后能回到该结点。
（2）欧拉通路：当且仅当有零个或两个奇度数的结点，则称为欧拉通路，可以一笔画但是不可以回到出发结点。
（3）有向连通图为欧拉图，当且仅当该图为连通图并且每个结点的入度等于出度。

最短网络问题

问题：将若干个定点连接起来，使连线的总长度最短 ？
求解：目前还没有找到最短网络问题的最优解，但是通过证明得出最小生成树为该问题的近似最优解。

在线问题和在线算法

在线问题：在处理实际问题时，问题的变量和参数没有提前告诉，需要即时做出决策的问题

例子：滑雪问题，每次租用滑雪用具为1元，买一套滑雪用具为T元，现在不知道滑雪次数的前提下，需要做出决策，买还是租 ？

在线算法：首先租K次，当去滑K+1次的时候，再买，问题关键在于求解K是多少

（1）算法1：第一天就买花费了T元，如果最后发现 L = 1，那么竞争比为T，不是一个常数，因此该算法不可取

（2）算法二：如果 L<T,即使事先知道滑雪次数，那么最优策略也为租。若 L>=T，那么在线算法花费了（2T-1）元，如果事先知道滑雪次数，那么花费为T，竞争比为（2T-1）/T < 2 事实证明这是一个最优在线策略，称为竞争算法

竞争算法：就是假如你知道最后结果的条件下，你做出的决策与最优决策相比，相差也不会太大