离散数学的应用（排队论与最优化）
標準约 16 分钟2 个术语过去问 2 题
本单元目标
- 能够说明排队模型是用来估算什么的
- 能够说明利用率与等待时间之间的关系
- 能够把最优化问题拆分为约束条件和目标函数来建立，并求出小规模问题的最优解
术语总表（2 个）
术语
排队 待ち行列是根据到达与处理的情况，对为接受服务而依次等候的队列进行定量分析的模型。
到达的间隔和每件的处理时间都有波动，因此要用概率与统计来估算平均等待时间和队列长度。基本形式是只有一个窗口，按先到先处理的顺序服务。窗口处于处理状态的时间所占的比例称为利用率，用平均处理时间除以平均到达间隔求得。
类比就像在医院挂号处取号，然后在候诊室等到叫号为止。越是人多的日子，候诊室里的人越多，等的时间也越长。
记法排队论起源于研究电话交换机线路会拥挤到什么程度的工作。
考点
- 易混利用率 利用率上升时，等待时间并不是按比例慢慢增加。利用率越接近 1，等待时间就会急剧变长。
- 易混排队 待ち行列模型是估算拥挤程度的工具，与按存入顺序取出数据的数据结构“队列”キュー目的不同。
最优化问题 最適化問題是在满足必须遵守的条件（约束条件）的解中，求出使衡量优劣的标准（目标函数）达到最好的解（最优解）的问题，例如利润最大或成本最小。
候选解较少时，把所有候选列出来比较目标函数的值，就能找到最优解。候选较多时，则使用线性规划这类把条件和目标写成式子来求解的方法。决定按什么顺序推进作业、按什么顺序走访多个地点，也都是最优化问题的例子。
类比就像在旅行箱装得下的范围内挑选要带的东西，让有用的物品尽可能多。
记法英语 optimization 源自拉丁语 optimus，意思是“最好的”。无论追求最大还是最小，都统称为“最好”。
考点
- 常考在最优化问题 最適化問題中，要把解必须满足的约束条件 制約条件和需要最小化或最大化的目标函数 目的関数分开写。约束条件要从问题的前提中推出，如果加上前提中没有的条件，原本的最优解 最適解可能会被排除在候选之外。
- 常考途经顺序可以自由选择的路线，其最短时间的求法是：按每种候选顺序算出所需时间的合计，再选出最小的那个。包含无法通行区间的顺序要从候选中剔除。
- 常考要把按相同顺序使用两台机器的作业排成全部完成时间最短的顺序，就看最短的使用时间：若它在前一台机器上，就把该作业排在最前，若在后一台机器上，就排在最后，然后对剩下的作业重复这一步（约翰逊法 ジョンソン法）。
该术语的过去问 2 题 最適化問題 →
要点
- 排队模型根据到达与处理的波动，估算平均等待时间和队列长度。
- 只有一个窗口时，利用率等于平均处理时间除以平均到达间隔，越接近 1，等待时间增长得越急剧。
- 最优化问题是在满足约束条件的解中，寻找目标函数最好的最优解。
- 候选较少的最优化问题，算出所有候选的值加以比较即可求解。
查看这个领域的全部过去问 →