{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Kukavica\n",
    "\n",
    "Kukavica bo izlegla $16$ jajc in jih podtaknila v $12$ gnezd, ki pripadajo dvema taščicama, štirim vrtnim penicam, trem travniškim cipam, dvema belima pastiricama in eni sovi. V vsako gnezdo lahko izleže največ tri jajca, pri čemer je verjetnost, da mladiči v gnezdu $i$ preživijo, enaka $p_{ij}$, kjer je $j$ število podtaknjenih jajc v gnezdu $i$ (preživijo bodisi vsi ali noben mladič v posameznem gnezdu). Pri vsaki od petih vrst ptic želi izleči vsaj eno jajce, pri taščicah pa želi izleči strogo več jajc kot pri belih pastiricah. Poleg tega pri drugi beli pastirici ne bo odložila jajca, če bo pri prvi taščici odložila dve jajci ali več. Kukavica želi maksimizirati pričakovano število preživelih mladičev."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parametri\n",
    "\n",
    "Pripravimo matriko (seznam seznamov) z verjetnostmi preživetja mladičev v odvisnosti od števila podtaknjenih jajc v gnezdu - velja torej `pr[i][j] =` $p_{ij}$ ($0 \\le i \\le 11$, $0 \\le j \\le 3$)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "pr = [\n",
    "    [1, 0.8, 0.7, 0.4], # 0:  taščica 1\n",
    "    [1, 0.8, 0.6, 0.4], # 1:  taščica 2\n",
    "    [1, 0.9, 0.8, 0.5], # 2:  vrtna penica 1\n",
    "    [1, 0.8, 0.8, 0.6], # 3:  vrtna penica 2\n",
    "    [1, 0.8, 0.8, 0.5], # 4:  vrtna penica 3\n",
    "    [1, 0.9, 0.7, 0.6], # 5:  vrtna penica 4\n",
    "    [1, 0.8, 0.7, 0.4], # 6:  travniška cipa 1\n",
    "    [1, 0.8, 0.8, 0.4], # 7:  travniška cipa 2\n",
    "    [1, 0.7, 0.7, 0.5], # 8:  travniška cipa 3\n",
    "    [1, 0.7, 0.5, 0.4], # 9:  bela pastirica 1\n",
    "    [1, 0.7, 0.7, 0.4], # 10: bela pastirica 2\n",
    "    [1, 0.6, 0.4, 0.1]  # 11: sova\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = len(pr)    # število gnezd\n",
    "m = len(pr[0]) # maksimalno število jajc v gnezdu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Celoštevilski linearni program\n",
    "\n",
    "Zapisali bomo sledeči celoštevilski linearni program:\n",
    "\n",
    "\\begin{align*}\n",
    "\\max \\sum_{i=0}^{11} \\sum_{j=1}^3 j \\ p_{ij} \\ x_{ij} & \\\\\n",
    "\\text{p. p.} \\quad\n",
    "\\forall i \\in \\{0, 1, \\dots, 11\\} \\ \\forall j \\in \\{1, 2, 3\\}. \\ 0 \\le x_{ij} &\\le 1, \\ x_{ij} \\in \\mathbb{Z} \\\\\n",
    "\\forall i \\in \\{0, 1, \\dots, 11\\}. \\sum_{j=1}^3 x_{ij} &\\le 1 \\\\\n",
    "\\sum_{i=0}^{11} \\sum_{j=1}^3 j \\ x_{ij} &= 16 \\\\\n",
    "\\sum_{i=0}^1 \\sum_{j=1}^3 x_{ij} &\\ge 1 \\\\\n",
    "\\sum_{i=2}^5 \\sum_{j=1}^3 x_{ij} &\\ge 1 \\\\\n",
    "\\sum_{i=6}^8 \\sum_{j=1}^3 x_{ij} &\\ge 1 \\\\\n",
    "\\sum_{i=9}^{10} \\sum_{j=1}^3 x_{ij} &\\ge 1 \\\\\n",
    "\\sum_{j=1}^3 x_{11,j} &\\ge 1 \\\\\n",
    "\\sum_{i=0}^1 \\sum_{j=1}^3 j \\ x_{ij} - \\sum_{i=9}^{10} \\sum_{j=1}^3 j \\ x_{ij} &\\ge 1 \\\\\n",
    "\\sum_{j=2}^3 x_{0j} + \\sum_{j=1}^3 x_{10,j} &\\le 1 \\\\\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "p = MixedIntegerLinearProgram(maximization=True)\n",
    "x = p.new_variable(binary=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "p.set_objective(sum(j * pr[i][j] * x[i, j] for j in range(1, m) for i in range(n)))\n",
    "p.add_constraint(sum(j * x[i, j] for j in range(1, m) for i in range(n)) == 16)\n",
    "p.add_constraint(sum(x[i, j] for j in range(1, m) for i in [0, 1]) >= 1)\n",
    "p.add_constraint(sum(x[i, j] for j in range(1, m) for i in [2, 3, 4, 5]) >= 1)\n",
    "p.add_constraint(sum(x[i, j] for j in range(1, m) for i in [6, 7, 8]) >= 1)\n",
    "p.add_constraint(sum(x[i, j] for j in range(1, m) for i in [9, 10]) >= 1)\n",
    "p.add_constraint(sum(x[11, j] for j in range(1, m)) >= 1)\n",
    "p.add_constraint(sum(j * x[i, j] for j in range(1, m) for i in [0, 1]) >=\n",
    "                 sum(x[i, j] for j in range(1, m) for i in [9, 10]) + 1)\n",
    "p.add_constraint(x[0, 2] + x[0, 3] + x[10, 1] + x[10, 2] + x[10, 3] <= 1)\n",
    "\n",
    "for i in range(n):\n",
    "    p.add_constraint(sum(x[i, j] for j in range(1, m)) <= 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Z metodo `solve` dobimo optimalno vrednost ciljne funkcije."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12.399999999999999"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p.solve()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Z metodo `get_values` dobimo vrednosti spremenljivk pri najdeni optimalni rešitvi."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(0, 1): 1,\n",
       " (1, 1): 1,\n",
       " (2, 1): 0,\n",
       " (3, 1): 0,\n",
       " (4, 1): 0,\n",
       " (5, 1): 1,\n",
       " (6, 1): 1,\n",
       " (7, 1): 0,\n",
       " (8, 1): 0,\n",
       " (9, 1): 1,\n",
       " (10, 1): 0,\n",
       " (11, 1): 1,\n",
       " (0, 2): 0,\n",
       " (1, 2): 0,\n",
       " (2, 2): 1,\n",
       " (3, 2): 1,\n",
       " (4, 2): 1,\n",
       " (5, 2): 0,\n",
       " (6, 2): 0,\n",
       " (7, 2): 1,\n",
       " (8, 2): 1,\n",
       " (9, 2): 0,\n",
       " (10, 2): 0,\n",
       " (11, 2): 0,\n",
       " (0, 3): 0,\n",
       " (1, 3): 0,\n",
       " (2, 3): 0,\n",
       " (3, 3): 0,\n",
       " (4, 3): 0,\n",
       " (5, 3): 0,\n",
       " (6, 3): 0,\n",
       " (7, 3): 0,\n",
       " (8, 3): 0,\n",
       " (9, 3): 0,\n",
       " (10, 3): 0,\n",
       " (11, 3): 0}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "res = p.get_values(x)\n",
    "res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Izpišimo, v katera gnezda naj kukavica odloži jajca."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 1, 1: 1, 5: 1, 6: 1, 9: 1, 11: 1, 2: 2, 3: 2, 4: 2, 7: 2, 8: 2}"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kuk = {i: j for (i, j), v in res.items() if v == 1}\n",
    "kuk"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.2.rc2",
   "language": "sage",
   "name": "sagemath"
  },
  "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}