«运筹学»笔记

Little 公式 设 $\lambda_{e}$ 为顾客到达系统中速率的平均值，则在很宽的条件下有： $W=\dfrac{L}{\lambda_{e}}, W_{q}=\dfrac{L_{q}}{\lambda_{e}},$ 在 $M / M / 1 / \infty / \infty / F C F S$ 系统中，顾客到达的速率是常数 $\lambda,$ 即 $\lambda_{e}=\lambda,$ 因此： $W=\dfrac {L}{\lambda}, W_{q}=\dfrac {L_{q}}{\lambda},$ 称为利特尔公式. 例题 【例子】服务台全天服务，假设顾客到达的时间间隔服从均值为 1 的负指数分布。现在有一位顾客正好中午 12:00 到达，试求: (1）下一个顾客将在下午 1:00 前到达的概率； (2）在下午 1:00 与 2:00 之间到达的概率: (3）在下午 2:00 以后到达的概率。 【分析与解答】 （1）由已知，t 时间至少有一个顾客到达的概率是 $F_T (t) = 1 - e^{-t}$，当 $t = 1$ 时 $P = 1-e^{-1} = 0.6321$，所以概率是 $63.21\%$. （2）在 2:00 内到达的概率是 $1-e^{-2} = 0.

感受： 【例子】效率矩阵为 $$ <br /> \begin{bmatrix}<br /> 12 & 7 & 9 & 7 & 9 \\<br /> 8 & 9 & 6 & 6 & 6 \\<br /> 7 & 17 & 12 & 14 & 9 \\<br /> 15 & 14 & 6 & 6 & 10 \\<br /> 4 & 10 & 7 & 10 & 9<br /> \end{bmatrix}<br /> $$ 试求效率最高的解。 （1）系数矩阵简化 对于每行，分别减去其行的最小值。之后对列同样操作。

原问题化对偶问题 例子： $$ \max z=5 x_{1}+3 x_{2}+6 x_{3} \\ \left\{\begin{array}{l} x_{1}+2 x_{2}+x_{3} \leq 18 \\ 2 x_{1}+x_{2}+3 x_{3}=16 \\ x_{1}+x_{2}+x_{3}=10 \\ x_{1}, x_{2} \geq 0, x_{3} \text {无约束} \end{array}\right. $$ 原问题求 max，那么我们先写出 min z' 目标函数 原问题有三个约束条件，那么对偶问题变量就有三个，记为 $\begin {bmatrix} y1\\y2\\y3\end {bmatrix}$，点乘以三个常数。则目标函数为： $$ \min z = 18y_1+16y_2+10y_3 $$ 约束条件 用 $x_1$ 的系数向量点乘以 $\begin {bmatrix} y1\\y2\\y3\end {bmatrix}$，得到约束条件 $y_1 + 2y_2 + y_3$，结合原函数 $\max z$ 中 $x_1$ 的系数。列出： $$ y_1 + 2y_2 + y_3\ ?

第一次迭代： Cj -1 -1 theta_i cb xb b x1 x2 x3 x4 x5 a1 a2 x4 4 1 1 1 1 4 -1 a1 1 -2 1 -1 -1 1 1 V -1 a2 9 3 1 1 3 ci-zj -2 4 -1 V 第二次迭代：