Markovske_retezce_a_hromadna_obsluha.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "surprising-daniel",
   "metadata": {},
   "source": [
    "# Markovské řetězce a hromadná obsluha"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "minimal-today",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "import math\n",
    "\n",
    "from IPython.display import Image\n",
    "import numpy as np\n",
    "from numpy.linalg import inv\n",
    "import scipy.linalg as la\n",
    "import scipy.stats as st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "liquid-interface",
   "metadata": {},
   "outputs": [],
   "source": [
    "from fractions import Fraction\n",
    "# pozor může být nepřesné\n",
    "def vystup_zlomky(matrix):\n",
    "    for i in range(matrix.shape[0]):\n",
    "        row = \"\"\n",
    "        for j in range(matrix.shape[1]):\n",
    "            row += str(Fraction(matrix[i, j]).limit_denominator())\n",
    "            row += \"\\t\"\n",
    "        print(row)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "referenced-karen",
   "metadata": {},
   "source": [
    "# Markovský řetězec\n",
    "\n",
    "Náhodný proces ${Xn | n ∈ N0}$ s nejvýše spočetnou množinou stavů $S$ nazýváme markovský řetězec s diskrétním časem, pokud splňuje markovskou podmínku, tj. pokud $∀n ∈ N, a ∀s, s_0, . . . , s_{n−1} \\in S$ platí\n",
    "\n",
    "$$P(X_n = s|X_{n−1} = s_{n−1}, \\cdots, X_1 = s_1, X_0 = s_0) = P(X_n = s|X_{n−1} = s_{n−1})$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "efficient-kingdom",
   "metadata": {},
   "source": [
    "## Stacionární rozdělení\n",
    "\n",
    "https://marast.fit.cvut.cz/cs/problems/10180\n",
    "\n",
    "Buď ${X_n | n \\in \\mathbb{N}_0}$ homogenní markovský řetězec s maticí přechodu $\\textbf{P}$.\n",
    "\n",
    "Pokud existuje vektor $\\pi$ takový, že\n",
    "\n",
    "- $\\forall i \\in S: \\pi_i \\ge 0$,\n",
    "- $\\sum{i \\in S}{\\pi_i = 1}$,\n",
    "\n",
    "pro který platí, že\n",
    "\n",
    "$$\\pi * \\textbf{P} = \\pi$$\n",
    "\n",
    "nazýváme jej *stacionárním rozdělením řetězce*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "swiss-fossil",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Stacionární rozdělení =\n",
      "20/41\t10/41\t8/41\t1/41\t1/41\t1/41\t\n"
     ]
    }
   ],
   "source": [
    "# DATA\n",
    "\n",
    "# TODO: NASTAVIT\n",
    "matice = np.matrix([\n",
    "    [0.95,0.05,0,0,0,0],\n",
    "    [0,0.9,0.1,0,0,0],\n",
    "    [0,0,0.875,0.125,0,0],\n",
    "    [0,0,0,0,1,0],\n",
    "    [0,0,0,0,0,1],\n",
    "    [1,0,0,0,0,0],\n",
    "])\n",
    "\n",
    "# PROGRAM\n",
    "def stacionarni_rozdeleni(matrix):\n",
    "    W = np.transpose(matrix - np.eye(matrix.shape[0])) \n",
    "    pi = la.null_space(W)\n",
    "    pi = np.transpose(pi/sum(pi))\n",
    "    return pi\n",
    "\n",
    "_res = stacionarni_rozdeleni(matice)\n",
    "print(\"Stacionární rozdělení =\")\n",
    "vystup_zlomky(_res)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "described-pickup",
   "metadata": {},
   "source": [
    "## Fundamentální matice\n",
    "\n",
    "Matice $N = (I - T)^{-1}$ se nazývá *fundamentální matice řetězce*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "divine-vehicle",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Fundamentální matice =\n",
      "4/3\t2/3\t\n",
      "2/3\t4/3\t\n"
     ]
    }
   ],
   "source": [
    "# DATA\n",
    "\n",
    "# TODO: NASTAVIT\n",
    "# matice T\n",
    "matice_t = np.matrix([\n",
    "    [0, 1/2],\n",
    "    [1/2, 0],            \n",
    "])\n",
    "\n",
    "# PROGRAM\n",
    "def fundamentalni_matice(matrix_t):\n",
    "    return inv(np.eye(matrix_t.shape[0]) - matrix_t)\n",
    "\n",
    "_res = fundamentalni_matice(matice_t)\n",
    "print(\"Fundamentální matice =\")\n",
    "vystup_zlomky(_res)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "opposed-sense",
   "metadata": {},
   "source": [
    "## Pravděpodobnost pohlcení\n",
    "\n",
    "Pro matici pravděpodobností pohlcení platí\n",
    "\n",
    "$$U = N \\cdot R = (I - T)^{-1}R$$\n",
    "\n",
    "Matice přechodu $\\textbf{P}$ má tvar\n",
    "\n",
    "$$\\textbf{P} = \n",
    "\\begin{pmatrix}\n",
    "\\textbf{T} & \\textbf{R} \\\\\n",
    "\\textbf{0} & \\textbf{C}\n",
    "\\end{pmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "reduced-count",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Pravděpodobnost pohlcení =\n",
      "2/3\t1/3\t\n",
      "1/3\t2/3\t\n"
     ]
    }
   ],
   "source": [
    "# DATA\n",
    "\n",
    "# TODO: NASTAVIT\n",
    "# matice T\n",
    "matice_t = np.matrix([\n",
    "    [0, 1/2],\n",
    "    [1/2, 0],            \n",
    "])\n",
    "# matice R\n",
    "matice_r = np.matrix([\n",
    "    [1/2, 0],\n",
    "    [0, 1/2],            \n",
    "])\n",
    "\n",
    "# PROGRAM\n",
    "def pravdepodobnost_pohlceni(matrix_t, matrix_r):\n",
    "    return fundamentalni_matice(matrix_t) * matrix_r\n",
    "\n",
    "_res = pravdepodobnost_pohlceni(matice_t, matice_r)\n",
    "print(\"Pravděpodobnost pohlcení =\")\n",
    "vystup_zlomky(_res)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "minimal-gathering",
   "metadata": {},
   "source": [
    "## Střední doba kroků do pohlcení\n",
    "\n",
    "Pro matici $N = (I - T)^{-1}$ platí $N_{ik} := E(W_k|X_0=i)$, tj. $N_{ik}$ označuje *střední počet návštěv* stavu $k \\in T$, jestliže řetězec startuje v $i \\in T$. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "laughing-sword",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Fundamentální matice\n",
      "2\t4\t4\t\n",
      "2\t8\t20/3\t\n",
      "2\t8\t8\t\n",
      "None\n",
      "vektor středních dob kroků do pohlcení =\n",
      "[[10.        ]\n",
      " [16.66666667]\n",
      " [18.        ]]\n",
      "Hezky:\n",
      "10\t\n",
      "50/3\t\n",
      "18\t\n"
     ]
    }
   ],
   "source": [
    "# DATA\n",
    "\n",
    "# TODO: NASTAVIT\n",
    "# matice T\n",
    "matice_t = np.matrix([\n",
    "    [0, 0,1/2],\n",
    "    [1/4, 1/4, 1/2],\n",
    "    [0, 3/4, 1/4],            \n",
    "])\n",
    "\n",
    "# PROGRAM\n",
    "def stredni_doba_kroku_do_pohlceni(matrix_t):\n",
    "    N = fundamentalni_matice(matrix_t)\n",
    "    print(\"Fundamentální matice\")\n",
    "    print(vystup_zlomky(N))\n",
    "    return N * np.ones((matrix_t.shape[0],1))\n",
    "\n",
    "_res = stredni_doba_kroku_do_pohlceni(matice_t)\n",
    "print(\"vektor středních dob kroků do pohlcení =\")\n",
    "print(_res)\n",
    "print(\"Hezky:\")\n",
    "vystup_zlomky(_res)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "junior-makeup",
   "metadata": {},
   "source": [
    "## Matice skokových intenzit na matici přechodů\n",
    "\n",
    "$$ P'(t) = P(t)Q$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "provincial-transcription",
   "metadata": {},
   "source": [
    "## Matice přechodů na matici skokových intenzit\n",
    "\n",
    "$$ Q = P'(0)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "responsible-token",
   "metadata": {},
   "source": [
    "## Pravděpodobnostní rozdělení v čase t\n",
    "\n",
    "https://marast.fit.cvut.cz/cs/problems/10788\n",
    "\n",
    "$$ p'(t) = p(t)Q$$\n",
    "$$ p(0) = p_{initial}$$\n",
    "p(0) je zadaný"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bacterial-africa",
   "metadata": {},
   "source": [
    "## Formulace diskrétní řetězec na spojitý a naopak\n",
    "\n",
    "$$ D := I + \\frac{1}{\\lambda}Q$$\n",
    "\n",
    "$$ Q = \\lambda(D-I)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "statutory-behavior",
   "metadata": {},
   "source": [
    "## Podmínky detailní rovnováhy\n",
    "\n",
    "https://marast.fit.cvut.cz/cs/problems/10791\n",
    "\n",
    "\n",
    "$$ \\pi_i Q_{ij} = \\pi_j Q_{ji}$$\n",
    "\n",
    "$$ \\sum_{i=0} \\pi = 1$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "entertaining-bookmark",
   "metadata": {},
   "source": [
    "# Systém hromadné obsluhy"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "statewide-watch",
   "metadata": {},
   "source": [
    "## Littleho věta a střední doby\n",
    "\n",
    "\n",
    "\n",
    "$EN$ = střední počet zákazníků v systému\n",
    "\n",
    "$ET$ = střední doba strávená zákazníkem v systému\n",
    "\n",
    "$\\lambda$ intenzita procesu příchodů\n",
    "\n",
    "### Littleho věta\n",
    "\n",
    "$$ EN = \\lambda ET$$\n",
    "\n",
    "### Další střední hodnoty\n",
    "\n",
    "$$ET = E_\\pi W + E_\\pi S_j $$ \n",
    "\n",
    "$EW = $ Střední doba času stráveného zákazníkem ve frontě\n",
    "\n",
    "$ES_j = \\frac{1}{\\mu} $ Střední doba obsluhy $j$-tého požadavku\n",
    "\n",
    "Index $\\pi$ znamená, vzhledem k stacionárnímu rozdělení\n",
    "\n",
    "$$EN = EN_s + EN_f$$\n",
    "\n",
    "$EN_s = $ střední počet zákazníků na serveru\n",
    "\n",
    "$EN_f =$ střední počet zákazníků ve frontě"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "systematic-radius",
   "metadata": {},
   "source": [
    "### Systém M|M|1\n",
    "\n",
    "Stacionární rozdělení, existuje, pokud $\\lambda < \\mu$ \n",
    "$$ \\pi_n = (1 - \\frac{\\lambda}{\\mu})(\\frac{\\lambda}{\\mu})^n$$\n",
    "\n",
    "$EN = \\frac{\\rho}{1-\\rho}$\n",
    "\n",
    "$EN_s = \\rho$\n",
    "\n",
    "$EN_f = \\frac{\\rho^2}{1-\\rho}$\n",
    "\n",
    "Pravděpodobnost, že zákazník bude hned odbaven a nebude čekat.\n",
    "\n",
    "$P(W = 0) = P(X_t = 0) = \\pi_0 = 1-\\rho = 1-\\frac{\\lambda}{\\mu}$\n",
    "\n",
    "Pravděpodobnost, že zákazník bude čekat alespoň dobu w, pokud bude čekat.\n",
    "\n",
    "$P(W > w | W > 0) \\sim Exp(\\mu - \\lambda)$\n",
    "\n",
    "$P(W > w | W > 0) = e^{-(\\mu - \\lambda)w}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "educational-excitement",
   "metadata": {},
   "source": [
    "### Systém $M|M|\\infty$\n",
    "\n",
    "Podmínka detailní rovnováhy:\n",
    "$$ n\\mu\\pi_n = \\lambda \\pi_{n-1}$$\n",
    "\n",
    "Stacionární rozdělení \n",
    "\n",
    "$$\\pi_n = \\frac{1}{n!}\\left(\\frac{\\lambda}{\\mu}\\right)^n e^{-\\frac{\\lambda}{\\mu}}$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "agreed-spirituality",
   "metadata": {},
   "source": [
    "### Systém M|M|c\n",
    "\n",
    "Stacionární rozdělení\n",
    "\n",
    "Pokud $n \\le c$\n",
    "$$\\pi_n  = \\frac{1}{n!}\\left(\\frac{\\lambda}{\\mu}\\right)^n \\pi_0$$\n",
    "jinak\n",
    "$$\\pi_n  = \\frac{c^c}{c!}\\left(\\frac{\\lambda}{c\\mu}\\right)^n \\pi_0$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "younger-smile",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}