{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Gradnja hiše\n",
    "\n",
    "Gradbinec in samooklicani arhitekt Brezzobec se je odločil,\n",
    "da bo postavil zelo posebno hišo.\n",
    "Gradnja bo imela sedem glavnih faz:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "faze = {\n",
    "#   faza  opis                            trajanje  pogoji    min  cena\n",
    "    'A': ('gradnja kleti',                      10, [],         7, 200),\n",
    "    'B': ('gradnja pritličja',                  6,  ['A'],      5, 100),\n",
    "    'C': ('gradnja prvega nadstropja',          7,  ['B', 'F'], 5, 150),\n",
    "    'D': ('gradnja strehe',                     8,  ['C', 'E'], 6, 160),\n",
    "    'E': ('gradnja desnega podpornega stebra',  13, ['A'],      9, 250),\n",
    "    'F': ('gradnja glavnega podpornega stebra', 14, [],        11, 240),\n",
    "    'G': ('gradnja baročnega stolpa pred hišo', 30, [],        25, 300),\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Brezzobčev bratranec ima podjetje, ki lahko pomaga pri gradnji, vendar za vsak dan krajšanja posamezne faze zahteva ustrezno plačilo (stolpec `cena`), pri čemer je v stolpcu `min` podano najkrajše možno trajanje opravila. Brezzobca zanima način, kako bi s čim manjšimi stroški čas gradnje zmanjšal na $27$ dni."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linearni program\n",
    "\n",
    "Problem bomo modelirali z linearnim programom s sledečimi spremenljivkami:\n",
    "* $x_i$: trajanje faze $i$\n",
    "* $y_i$: začetni čas faze $i$\n",
    "\n",
    "Naj bo $t_i$ privzeto trajanje opravila $i$, $P_i$ množica pogojev za začetek opravila $i$, $m_i$ minimalno trajanje opravila $i$, $c_i$ cena za skrajšanje opravila $i$ za en dan in $T$ želeno trajanje projekta. Potem lahko zapišemo sledeči linearni program:\n",
    "\n",
    "\\begin{align*}\n",
    "\\min \\sum_i c_i (t_i - x_i) & \\\\\n",
    "\\text{p. p.} \\quad\n",
    "\\forall i. m_i \\le x_i &\\le t_i \\\\\n",
    "\\forall i. 0 \\le y_i &\\le T - x_i \\\\\n",
    "\\forall i \\forall j \\in P_i. y_i &\\ge y_j + x_j\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "p = MixedIntegerLinearProgram(maximization=False)\n",
    "x = p.new_variable(real=True)\n",
    "y = p.new_variable(real=True)\n",
    "T = 27"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "p.set_objective(sum(c * (t-x[i]) for i, (_, t, P, m, c) in faze.items()))\n",
    "for i, (_, t, P, m, c) in faze.items():\n",
    "    p.add_constraint(x[i] >= m)\n",
    "    p.add_constraint(x[i] <= t)\n",
    "    p.add_constraint(y[i] >= 0)\n",
    "    p.add_constraint(y[i] <= T - x[i])\n",
    "    for j in P:\n",
    "        p.add_constraint(y[i] >= y[j] + x[j])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Z metodo `solve` dobimo optimalno vrednost ciljne funkcije."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1620.0"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p.solve()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Izpišimo še začetne čase in trajanja opravil."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A': (0.0, 8.0),\n",
       " 'B': (8.0, 6.0),\n",
       " 'C': (14.0, 7.0),\n",
       " 'D': (21.0, 6.0),\n",
       " 'E': (8.0, 13.0),\n",
       " 'F': (0.0, 14.0),\n",
       " 'G': (0.0, 27.0)}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X = p.get_values(x)\n",
    "Y = p.get_values(y)\n",
    "{i: (Y[i], X[i]) for i in faze}"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 8.9.beta2",
   "language": "sage",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}