17-LinProgSimplex/Seminar17.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Семинар 17.\n",
    "\n",
    "# Линейное программирование. Симплекс-метод"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Текущее место в программе\n",
    "\n",
    "- Безусловная оптимизация\n",
    "    - ~~Одномерная минимизация~~\n",
    "    - ~~Градиентный спуск~~\n",
    "    - ~~Метод Ньютона и квазиньютоновские методы~~\n",
    "    - ~~Метод сопряжённых градиентов~~\n",
    "- Условная оптимизация\n",
    "    - <span style=\"color:red\">Линейное программирование: симплекс-метод</span>\n",
    "    - Линейное программирование: прямой барьерный метод\n",
    "    - Методы проекции градиента и условного градиента\n",
    "    - Методы штрафов и барьеров\n",
    "    - Метод модифицированной функции Лагранжа\n",
    "    - Последовательное квадратичное программирование\n",
    "- Разные темы\n",
    "    - ~~Задача наименьших квадратов~~\n",
    "    - Проксимальные методы\n",
    "    - Оптимальные методы и нижние оценки\n",
    "    - Зеркальный спуск\n",
    "    - Обзор стохастических методов"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Постановка задачи\n",
    "Даны векторы $c \\in \\mathbb{R}^n$, $b \\in \\mathbb{R}^m$ и матрица $A \\in \\mathbb{R}^{m \\times n}$ такая что $m < n$ и $\\mathrm{rank}(A) = m$ \n",
    "- Стандартная форма\n",
    "\\begin{align*}\n",
    "&\\min_x c^{\\top}x \\\\\n",
    "\\text{s.t. } & Ax \\leq b\\\\\n",
    "& x_i \\geq 0, \\; i = 1,\\dots, n\n",
    "\\end{align*}\n",
    "- Каноническая форма (везде далее рассматривается именно она)\n",
    "\\begin{align*}\n",
    "&\\min_x c^{\\top}x \\\\\n",
    "\\text{s.t. } & Ax = b\\\\\n",
    "& x_i \\geq 0, \\; i = 1,\\dots, n\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Преобразование постановок"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- $Ax = b \\equiv \n",
    "\\begin{cases}\n",
    "Ax \\leq b\\\\\n",
    "Ax \\geq b\n",
    "\\end{cases}\n",
    "$\n",
    "- $Ax \\leq b \\equiv \n",
    "\\begin{cases}\n",
    "Ax + z =  b\\\\\n",
    "z \\geq 0\n",
    "\\end{cases}$ \n",
    "- свободная переменная $x \\equiv \n",
    "\\begin{cases}\n",
    "x = u - v\\\\\n",
    "u \\geq 0, \\; v \\geq 0\n",
    "\\end{cases}$\n",
    "- смена знака достигается умножением на $-1$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Приложения\n",
    "\n",
    "- Производство оптимального количества товара при ресурсных ограничениях:\n",
    "\\begin{align*}\n",
    "&\\max_x c^{\\top}x \\\\\n",
    "\\text{s.t. } & Ax \\leq b\\\\\n",
    "& x_i \\geq 0, \\; i = 1,\\dots, n,\n",
    "\\end{align*}\n",
    "где $x_i$ - количество $i$-го товара, $c_i$ - прибыль от производства $i$-го товара, $b_i$ - доступное количество $i$-го материала, $a_{ij}$ - количество $i$-го материала, который требуется для производства единицы $j$-го товара.\n",
    "\n",
    "- Потоки в сетях: транспортная задача, задача о максимальном потоке, выбор пути в коммуникационной сети для передачи сообщения с минимальной стоимостью\n",
    "\n",
    "- Задача регрессии в нормах $\\ell_1$ и $\\ell_{\\infty}$ может быть сведена к задаче линейного программирования"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Какой ответ может дать алгоритм?\n",
    "\n",
    "- Задача разрешима и точка минимума $x^*$\n",
    "- Задача неограничена и минимальное значение равно $-\\infty$\n",
    "- Задача неразрешима, то есть допустимое множество пусто"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Предварительные соображения\n",
    "\n",
    "- Задача линейного программирования - это поиск минимума линейной функции на многомерном многоугольнике"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Вопросы:**\n",
    "\n",
    "- при каких условиях есть решение?\n",
    "- среди каких точек искать решение?\n",
    "- как именно искать решение?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Определения\n",
    "\n",
    "1. Tочка из допустимого множества называется *вершиной многоугольника*, если она не лежит на отрезке между двумя другими точками многоугольника.\n",
    "2. Точка $x$ называется *угловой точкой* многоугольника, если\n",
    "    - она лежит в множестве\n",
    "    - существует такое множество $\\mathcal{B} \\subset \\{1, \\dots, n \\}$, что \n",
    "        - $|\\mathcal{B}| = m$\n",
    "        - $i \\notin \\mathcal{B} \\Rightarrow x_i = 0$\n",
    "        - матрица $B = [a_i]_{i \\in \\mathcal{B}}$ невырождена, где $a_i$ - $i$-ый столбец матрицы $A$. Матрица $B$ называется *матрицей базиса*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Теорема** Все угловые точки являются вершинами соответствующего многоугольника."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Фундаментальная теорема линейного программирования\n",
    "\n",
    "1. Если в задаче линейного програмирования допустимое множество непусто, тогда оно имеет как минимум одну угловую точку.\n",
    "2. Если задача линейного программирования имеет решения, тогда хотя бы одно из них является угловой точкой.\n",
    "3. Если задача линейного программирования ограничена и допустимое множество непусто, тогда она имеет оптимальное решение."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Симплекс-метод\n",
    "\n",
    "- Симплекс-метод [предложил](https://www.rand.org/pubs/reports/R366.html) Дж. Данциг в 1947.\n",
    "- Его появление совпало с развитием компьютеров и явилось одним из первых доказательств их полезности\n",
    "- Имел большой успех в связи с многочисленными приложениями в экономике и планировании производства\n",
    "- Включён в [список](http://www.uta.edu/faculty/rcli/TopTen/topten.pdf) лучших алгоритмов XX века по версии редакторов SIAM"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Общая схема\n",
    "\n",
    "1. Находим произвольную угловую точку допустимого множества\n",
    "2. Переходим в сопряжённую ей угловую точку так, чтобы целевая функция уменьшалась\n",
    "3. Если можно продолжить уменьшение значения целевой функции, переходим в следующую угловую точку\n",
    "\n",
    "**Вопрос:** как формализовать и выполнить эти шаги?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Псевдокод итерации симплекс-метода\n",
    "\n",
    "Дана угловая точка $x$, соответствующая ей матрица базиса $B$ и множество индексов $\\mathcal{B}$.\n",
    "\n",
    "1. Вычислить *оценки замещения* (reduced costs) $\\overline{c}_j = c_j - c^{\\top}_{\\mathcal{B}}B^{-1}a_j$ для всех $j \\not\\in \\mathcal{B}$.\n",
    "    - если $\\overline{c}_j \\geq 0$ для всех $j$, то текущее значение является оптимальным и уменьшить целевую функцию нельзя\n",
    "    - иначе <span style=\"color:red\"> выбрать </span> индекс $j^*$, для которого $\\overline{c}_{j^*} < 0$\n",
    "2. Вычислить $u = B^{-1}a_{j^*}$\n",
    "    - если все компоненты $u$ неположительны, то задача неограничена, оптимальное значение равно $-\\infty$\n",
    "    - если есть положительные компоненты, то \n",
    "    $$\n",
    "    \\theta^* = \\min_{\\{i | u_i > 0\\}} \\frac{x_{\\mathcal{B}(i)}}{u_i}\n",
    "    $$\n",
    "3. Пусть $\\ell$ <span style=\"color:red\"> такой </span> индекс, что \n",
    "    $$\n",
    "    \\theta^* = \\frac{x_{\\mathcal{B}(\\ell)}}{u_{\\ell}}.\n",
    "    $$\n",
    "    Формируем новую матрицу базиса $\\hat{B}$ с помощью замены столбца $a_{\\mathcal{B}(\\ell)}$ на столбец $a_{j^*}$. Новая угловая точка $\\hat{x}$, соответствующая матрице базиса $\\hat{B}$, определяется так\n",
    "    $$\n",
    "    \\begin{align*}\n",
    "    & \\hat{x}_{j^*} = \\theta^*\\\\\n",
    "    & \\hat{x}_{\\mathcal{B}(k)} = x_{\\mathcal{B}(k)} - \\theta^*u_k, \\text{если } k \\neq \\ell\n",
    "    \\end{align*}\n",
    "    $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Существующие реализации симплекс-метода\n",
    "\n",
    "- Наивная реализация\n",
    "- <span style=\"color:red\"> Табличная реализация </span>\n",
    "- Модифицированная реализация"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Теорема корректности\n",
    "\n",
    "Пусть допустимое множество непусто и каждая угловая точка *невырождена*. Тогда симплекс-метод останавливается за конечное число итераций:\n",
    "- либо найдена оптимальная угловая точка $x^*$\n",
    "- либо показано, что оптимальное значение равно $-\\infty$\n",
    "\n",
    "**Определение.** Угловая точка называется *вырожденной*, если она содержит больше $n - m$ нулевых компонент.\n",
    "\n",
    "**Вопрос:** что геометрически означает вырожденность?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Проблема вырожденности угловой точки\n",
    "\n",
    "Если одна из угловых точек является *вырожденной*, то это может привести к **зацикливанию** симплекс-метода!\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Решение\n",
    "\n",
    "- Лексикографический порядок выбора $\\ell$\n",
    "- Правило Бланда - выбор наименьшего $j^*$ и $\\ell$\n",
    "\n",
    "Р. Бланд - американский математик, один из создателей теории [ориентированных матроидов](https://en.wikipedia.org/wiki/Oriented_matroid)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Как искать начальную угловую точку?\n",
    "\n",
    "- Двухфазный симплекс-метод\n",
    "- M-метод"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Двухфазный симплекс метод\n",
    "\n",
    "Для поиска начальной угловой точки составим следующую вспомогательную задачу при условии, что $b_i \\geq 0, \\; i =1, \\dots,m$. Этого легко добиться умножение строк матрицы $A$ и соответствующих элементов $b$ на $-1$.\n",
    "\\begin{equation}\n",
    "\\begin{split}\n",
    "& \\min_{z, y} y_1 + \\ldots + y_m \\\\\n",
    "\\text{s.t. } & Az + y = b\\\\\n",
    "& z \\geq 0, \\; y \\geq 0\n",
    "\\end{split}\n",
    "\\end{equation}\n",
    "\n",
    "- Начальная точка для этой задачи очевидна $z = 0, \\; y = b$\n",
    "- Если оптимальное значение функции в этой задаче **не равно** $0$, то допустимое множество исходной задачи пусто\n",
    "- Если оптимальное значение функции в этой задаче **равно** $0$, то $y^* = 0$ и $x_0 = z^*$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Какая начальная матрица базиса?\n",
    "\n",
    "**Проблема:** в базисе, соответствующем $x_0$, может оказаться вспомогательная переменная равная 0.\n",
    "\n",
    "**Решение:** процедура вывода вспомогательной переменной из базиса"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Вывод вспомогательной переменной из базиса\n",
    "\n",
    "1. Выбираем вспомогательную переменную $x_k = 0$, но входящую в базис, найденный при решении вспомогательной задачи.\n",
    "2. Смотрим на строчку в таблице, которая соответствует $x_k$\n",
    "    - если в этой строке все элементы для столбцов, соответствующих изначальным переменным равны 0, то эту строку можно исключить, так как она является линейно зависимой от остальных строк в матрице\n",
    "    - если найдётся ненулевой элемент в этой строке и в столбце, соответствущем изначальной переменной, то выбираем этот элемент ведущим и вводим в базис соответствующую этому столбцу переменную. Разница с обычным шагом симплекс-метода в том, что этот элемент может быть отрицательным."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Итог\n",
    "- Первая фаза - поиск начальной угловой точки, вторая фаза - решение исходной задачи с использованием решения и базиса от первой фазы.\n",
    "- Так как значение переменной останется равно 0, процедра вывода вспомогательной переменной не повляет на значение целевой функции\n",
    "- Базис, полученный после решения вспомогательной задачи и исключения вспомогательных переменных, следует использовать на первой итерации симплекс-метода при решении исходной задачи"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### М-метод\n",
    "\n",
    "**Идея:** объединить двухфазный симплекс-метод в однофазный\n",
    "\n",
    "\\begin{equation}\n",
    "\\begin{split}\n",
    "& \\min_{z, y} c^{\\top}z + M(y_1 + \\ldots + y_m) \\\\\n",
    "\\text{s.t. } & Az + y = b\\\\\n",
    "& z \\geq 0, \\; y \\geq 0\n",
    "\\end{split}\n",
    "\\end{equation}\n",
    "\n",
    "$M$ - произвольное большое положительное число, можно оставить параметр и при необходимости сделать достаточно большим"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Примеры решения задач табличным симплекс-методом\n",
    "\n",
    "Примеры приведены [здесь](./examples.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Пример использования"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "     fun: -5098.4141534318\n",
      " message: 'Optimization terminated successfully.'\n",
      "     nit: 43\n",
      "   slack: array([ 6.12855608,  0.        , 32.34842617,  0.        , 18.63652142,\n",
      "        9.35365269,  9.4816442 ,  0.92247547, 15.54184317,  0.        ])\n",
      "  status: 0\n",
      " success: True\n",
      "       x: array([-1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        ,  4.68125825,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , 35.95968599, -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , 15.88795192, -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ,\n",
      "       -1.        , -1.        , -1.        , -1.        , -1.        ])\n"
     ]
    }
   ],
   "source": [
    "import scipy.optimize as scopt\n",
    "import numpy as np\n",
    "n = 1000\n",
    "m = 10\n",
    "c = 10 * np.random.rand(n)\n",
    "b = np.random.rand(m)\n",
    "A = np.random.randn(m, n)\n",
    "res = scopt.linprog(c, A, b, bounds=[(-1, None) for i in range(n)])\n",
    "print(res)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Сложность"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- Было показано, что в худшем случае время работы симплекс-метода <span style=\"color:red;font-weight:bold\"> экспоненциально</span> зависит от размерности задачи!\n",
    "- Однако на практике сложность чаще всего пропорциональна количеству ограничений и симплекс-метод сходится быстро\n",
    "- Почему это так, неясно до сих пор"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Пример Klee, Minty (1972) [[1]](https://en.wikipedia.org/wiki/Klee–Minty_cube)\n",
    "\n",
    "В задаче\n",
    "\\begin{align*}\n",
    "& \\max_{x \\in \\mathbb{R}^n} 2^{n-1}x_1 + 2^{n-2}x_2 + \\dots + 2x_{n-1} + x_n\\\\\n",
    "\\text{s.t. } & x_1 \\leq 5\\\\\n",
    "& 4x_1 + x_2 \\leq 25\\\\\n",
    "& 8x_1 + 4x_2 + x_3 \\leq 125\\\\\n",
    "& \\ldots\\\\\n",
    "& 2^n x_1 + 2^{n-1}x_2 + 2^{n-2}x_3 + \\ldots + x_n \\leq 5^n\\\\\n",
    "& x \\geq 0\n",
    "\\end{align*}\n",
    "начиная с точки $x_0 = 0$ и следуя симплекс-методу, необходимо обойти $2^n - 1$ вершину.\n",
    "\n",
    "**Упражнение**: решите эту задачу для $n = 2$ и $n = 3$, и обобщите результат, получив решение для произвольного $n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def generate_KleeMinty_test_problem(n):\n",
    "    c = np.array([2**i for i in range(n)])\n",
    "    c = c[::-1]\n",
    "    bounds = [(0, None) for i in range(n)]\n",
    "    b = np.array([5**(i+1) for i in range(n)])\n",
    "    a = np.array([1] + [2**(i+1) for i in range(1, n)])\n",
    "    A = np.zeros((n, n))\n",
    "    for i in range(n):\n",
    "        A[i:, i] = a[:n-i]\n",
    "    return -c, A, b, bounds"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-16  -8  -4  -2  -1]\n",
      "[[ 1.  0.  0.  0.  0.]\n",
      " [ 4.  1.  0.  0.  0.]\n",
      " [ 8.  4.  1.  0.  0.]\n",
      " [16.  8.  4.  1.  0.]\n",
      " [32. 16.  8.  4.  1.]]\n",
      "[   5   25  125  625 3125]\n",
      "[(0, None), (0, None), (0, None), (0, None), (0, None)]\n"
     ]
    }
   ],
   "source": [
    "n = 5\n",
    "c, A, b, bounds = generate_KleeMinty_test_problem(n)\n",
    "print(c)\n",
    "print(A) \n",
    "print(b)\n",
    "print(bounds)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "     fun: -3125.0\n",
      " message: 'Optimization terminated successfully.'\n",
      "     nit: 31\n",
      "   slack: array([  5.,  25., 125., 625.,   0.])\n",
      "  status: 0\n",
      " success: True\n",
      "       x: array([   0.,    0.,    0.,    0., 3125.])\n"
     ]
    }
   ],
   "source": [
    "res = scopt.linprog(c, A, b, bounds=bounds)\n",
    "print(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.78 ms ± 77.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "5.86 ms ± 298 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "11.5 ms ± 166 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "23.3 ms ± 1.08 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n",
      "48.3 ms ± 1.82 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n",
      "94.6 ms ± 1.04 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n",
      "191 ms ± 3.04 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "401 ms ± 18.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "791 ms ± 21.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "1.6 s ± 73.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "3.4 s ± 157 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "6.79 s ± 82.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "13.3 s ± 204 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "n_list = range(3, 16)\n",
    "n_iters = np.zeros(len(n_list))\n",
    "times = np.zeros(len(n_list))\n",
    "for i, n in enumerate(n_list):\n",
    "    c, A, b, bounds = generate_KleeMinty_test_problem(n)\n",
    "    res = scopt.linprog(c, A, b, bounds=bounds, options={\"maxiter\": 2**max(n_list)})\n",
    "    time = %timeit -o scopt.linprog(c, A, b, bounds=bounds, options={\"maxiter\": 2**max(n_list) + 1})\n",
    "    n_iters[i] = res.nit\n",
    "    times[i] = time.best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAABLkAAAFRCAYAAACYFH+FAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvNQv5yAAAIABJREFUeJzs3Xl8lfWd9//3h32ThABiBREOYdGqSDiotdpaTbS25deqgE7t3VWSLjNdphW0v7l/M/fdaTFBbZ22CkG7zNydjhDb/oa2igSU1tqFELS1lS0HEHBBCId9S/K5/zhXIIST5OTkJFdOeD0fjzySXNt5Y9Vefq7P9fmauwsAAAAAAADIZr3CDgAAAAAAAAB0FEUuAAAAAAAAZD2KXAAAAAAAAMh6FLkAAAAAAACQ9ShyAQAAAAAAIOtR5AIAAAAAAEDWo8gFAAAAAACArEeRCwAAAAAAAFmPIhcAAAAAAACyXp+wA/QkI0aM8HHjxoUdAwAAdJJ169btcfeRYefAmbgHAwCgZ0v1HowiVwaNGzdOVVVVYccAAACdxMy2h50BZ+MeDACAni3VezBeVwQAAAAAAEDWo8gFAAAAAACArEeRCwAAAAAAAFmPIhcAAAAAAACyHkUuAAAAAAAAZD2KXAAAAAAAAMh6FLkAAAAAAACQ9fqEHQAAgM504MAB7d69WydPngw7Crqpvn376vzzz9fQoUPDjgIAAIAOoMgFAOixDhw4oLfeekujR4/WwIEDZWZhR0I34+46evSodu3aJUkUugAAALIYrysCAHqs3bt3a/To0Ro0aBAFLiRlZho0aJBGjx6t3bt3hx0HkswsYmalYecAAACpOXjspL67arN+Vr0z7Ch0cgEAeq6TJ09q4MCBYcdAFhg4cCCvtHYDZjZLUlHYOQAAQNsOHjupH7+4TUt+u1X7j57Ux64Zq9sLxoSaiSIXAKBHo4MLqeDvk+7B3SvMLC5pdthZAABAcoeO1wXFrZjiR06q8JLz9aWbJunyMTlhR6PIBQAAAAAAgNYdPl6nH/9+m5b8JqZ9R07qxinn68uFE3XFmNywo53CTC4AAHqIeDyu+fPna9iwYTIzlZSUqLq6+oxj5s+fLzPThAkTVFFRQU50CjMrMLNlLewrNrNZwde8rs4GAADa5/DxOj32fI2uK12tsmc26sqLcvWLL7xbP/jkjG5V4JLo5AIAoMfIzc1VaWmpKioqVFxcrNLS5LO7161bp4KCgi5Od1q25ET7mVmBpDuDXyNJ9hdLidcSg98jZrbY3Uu6LiUAAEjFkRN1+vffb1f5b2KqPXxCN0weqS/dNFHTxg4LO1qLKHIBANCDxONxxWIxFRUVnbW9vLxc999/v3Jzw3/ili050T7uXi2pOih2FSY5pMTdpzc5PmZmyY4DAAAhOXKiTv/nD9u1eE1Mew+f0HsmjdSXCyeqoBsXtxpR5AIAoAeprKyUJBUWFp6xLR6Pa9687vNmWLbkROaYWa6kZK15cTMrdPfKrs4EAABOO3qiPlHc+k2N9hw6oesnjtCXCydp+sXdv7jViCIXAAA9yMqVK894xa+srEyFhYVnFJO6g2zJiYyKSIon2V6rRPGrMujqKpFUYGbF7l7elQEBADgXHT1Rr5/8cbsWrWla3Jqo6RfnhR2t3ShyAQDQgyxdulTFxcWKx+NasGCBysrKtG7durBjnSVbciKj8pQoaDUXlzRckoJurpQ6uoL5XsWSNHbs2AxFBADg3HHsZL1+8sfXtGhNjd4+eFzvzh+uxwonaca47CtuNWJ1RQAAeohYLKZ4PK7hw4ersrJSpaWlikQiWrBgQavnNb462FXSzQk05e7l7h519+jIkSPDjgMAQNY4drJeP3hhq64ve07f+OXfNPH8IVpa8i795J5rsrrAJdHJBQBAj9F0zlXjq4Dz589XSUmJ4vF4i4Pc58+f32oXVXl5uZYtW5ZShmXLlrU5MD7dnOgRkt0550ra29VBAAA41xw7Wa+f/uk1PfZ8jXYfPK53RYbre383TVdHhocdLWNaLXKZ2WPu/rmuCgMAQFf4X8v/qr+9fiDsGGe49MKh+ueZ7+zQNRrnXDWddVVcXKySkhItWLBApaWlZ50Tj8eVl9f6E7vi4mIVFxd3KFtHc6JHqFKioNVcnqTqdC5oZjMlzczPz+9ILgAAerRjJ+v15NodevT5LXrrwHFdPT5Pj9w1Te+a0HOKW43a6uQqlkSRCwCALFBZWan777//rO3z5s1TeXn5WcWj6upqLV68WLm5uaqoqNCsWbO6ZU4pUYxbunSp8vLyVFtbe6roVl1drVgsprVr16qoqEgrV67UnXfeqUgkoqVLlyoej6ugoEDxeGLeeVf9GXE2d4+bWczMct296QD63HRXVnT35ZKWR6PRuZlJCQBAz3G8LihuPVejNw8c01Xj8/SdO3tmcatRW0UuM7PPuPsTXZIGAIAu0NGOqe6occ5V0+6oRiUlJSorK1N5efkZHVkFBQXKzc1VSUlJ0vO6S05Jmjt3rpYsWaLc3FyVl5+54N6sWbO0ePFilZSUqKioSJFIRFVVVSouLtaECRNUU1MjSSoqKqLI1XVaag8slXS/pPmSZGYFSnHQPAAASM3xunotrdqpR5/bojf2H9OMccP08JypeteE4TKzsON1qlRmcpWZWaW7b2/vxc1snLtva38sAACQqvnz56uiokKStHjxYkmJeVdSogNq/vz5p46Lx+OaN2/eqXMbB79355zV1dWKx+OqqqqSJM2ZM+fUNRuLZbW1tYpEIopEIqeuW11dfaqo1fR8dB4zi0gqkVQoqcDMFkta5+7lUmJYvJkVm1mhEq8uRty9pAOfx+uKAAAEjtfVa1lQ3Hp9/zFFLx6mB2dP1bXnQHGrUVtFrjJJCyQtkTSnjWOTWSZpRhrnAQCAFJWWlrZYqMrNzU15aHxnSzdnVVWVioqKThXEmovFYqeKW01VVlaqqKjo1M8tnY/McfeYgi6tVo4pb21/Oz+P1xUBAOe8E3UNWrZuh76/OlHcmn7xMJXNmqp35587xa1GvVrb6e73uft+SXPNrF3repvZvZK65t0HAADQbtXV1YpGo5JOr3jYHTUvYFVXV5/6HovFVFFRoRkzEs/UGjvFpMSA+8Y/38qVKxloDwAAepQTdQ366Z9e0/sefF7/789f0aicAfr3T1+lis++S9dNHHHOFbik1F5XlLvvN7OlZnaPuz/e0nFmdqUSLeqZW4IJAAB0isaZXN29y6mwsFArV65URUWFcnNzTxW9Gl8/LCgoOLW/+ayvyspK1dbWavbs2Um7vQAAALLNyfoGPbVup7733Bbt3HdUV16Uq2/dfrnec44WtppKqcglSe6+3swiZnalu7/UdJ+Z3aNEcatAUuNf0UpJN2UsKQAAyLhs6W5KlrPpcPrmRbpYLKbc3FwGzfdwzOQCAJxL6uob9FT1Tn13daK4NfWiXP3rRy7TeyeNPOeLW41SLnJJkrs/ZWb3mlnjss/zdbpryyTFJJW6+xJJMjMmvAIAgC5XXV19ah4Xei5mcgEAzhVrNr2tb/7qb9r01iFNHZOjb3z4Mt0wmeJWc60WuZJ1bbn7QjN7Vokurca/mhWSFrj7+maXmJ2xpC1nLJZUG/wacfeyTJ5jZsvcvdP/HAAAIDNisZgWLFhwah4XAABAttr81kH9669e1ZpNb2vc8EFa9LHpuuWdoyhutaCtTq4lSr464hxJVZIWSVoSDKc/i7tv7Vi81gXFKrl7RfB7xMwWt7YUdXvOMbMCSbznAABAFolEIlq3bl3YMQAAANJWe/iEvr1yk/7zT69pUL/e+qcPXqKPv2uc+vVpdf3Ac15bRa6kE1rdPW5msyVNb6nA1UVK3H16k1wxM2trcm57zsnLREgAAABkHjO5AAA9zYm6Bv34xW36t9WbdeREve6+eqy+XDhJeYP7hR0tK7RVAhxmZnvM7L/M7B4zG9e4I3g1cZ+Z3diZAVtiZrlKDLpvLt5S0ao955jZLHfvvuupAwAAnOPcfbm7F+fk5IQdBQCADnF3PfPKmyr69hp989evavrFw/TMl67X//7wZRS42iGVwfN5SryeOFuSgqHzlZKelbRK0iwzi7n7tuYnmtmN7r46c3HPEJEUT7K9VolCVrICVUrnBK8pVmcmJgAAAAAAQHKv7Nqvb/zyb/rj1lpNGjVEP/70VXrvpJFhx8pKbRW5Yu6eHxR9bpJ0c/B9dvDlwXElZrZI0qpmg+pLlXymVybk6fTw+KbikoZ38JxI48yutgQzvoolaezYsamcAgDoQu7OYE60yd3bPggAACCDdh84poUrNqqieqeGDeqnf/3IZbprxkXq05u5W+lqq8hVLUnuXh38vFCSzGyapKhOF70mBPs8+A+JdUp0eSV7NbBbC15TTKnAJUnuXi6pXJKi0Sh3yADQjfTp00d1dXXq27dv2FHQzdXV1alPn1Qa3AEAADrm6Il6LfltTIvW1Kiu3lV8fURfuDFfQwdwz9pRrd7NufucFravl7ReidUXZWbjJRVKKlKisBUNvjq76JNsMHyupL3pnGNmEUmxTAQDAIRvwIABOnTokIYNGxZ2FHRzBw8e1IABA8KOAQAAerCGBtd/v/y6Sp/ZoDf2H9Otl12g+26doouHDw47Wo+RkUeW7r5ViYJXY9ErR1KJpAWZuH4LqpQoTjWXp5bnabV1TqGk3CRD6OdJigddWwCALDFy5Ei99tpr6t+/vwYOHMhriziLu+vo0aPas2cPYweyEKsrAgCyxbrttfrfv3xVL++I6/LROfrOnVfq6khLk5aQLuvMGRRmtsXdO+2uw8xqJE1393jTbe4+IVPnmJm7e0r/VRSNRr2qqir1PwAAoNPt379fe/fu1fHjx8OOgm6qf//+Gj58uFJZoc/M1rl7tAtioR24BwMAdFc7ao+o9JkN+uWf39Coof117y1TdPu00erVi4ev7ZHqPVhnD59ItsJhJpVKul/SfOnUqoinPjN4/bBU0twmRa1WzwEA9Cw5OTkpFS8AAACATDl47KQefb5GT7ywVb1M+uJNE/XZ90Y0qB8zQDtTp/7VdffPdvL1y82sOHi9MFeJVRFLmhwSUeIVxDwlVlBM5RxJUrC/JPh5maTF7k4xDAAAAAAAJFXf4FpatUMPPbtRew6d0G3TRmve+yfrHTkDw452Tsj6EmJrc7KCotRZ04ZTma0VnEtRCwAAAAAAtOl3W/boG7/8mza8eVDRi4fp8U/M0JUXJRsLjs6S9UUuAAAAAACAsMTePqRv/fpVVb66W2OGDdT3P1qgD1x+AYsehYAiFwAAALISqysCAMIUP3JCj6zarP/4/XYN6Ntb898/RZ969zgN6Ns77GjnLIpcAAAAyEruvlzS8mg0OjfsLACAc8fJ+gb9nz9s13cqN+vgsZO6c8ZY/WPRJI08r3/Y0c55FLkAAAAAAADa4O5a9epufevXryq257Cuyx+hf/rQJZpywdCwoyFAkQsAAAAAAKAVr75xQP/6q7/pd1v2KjJysJ74RFQ3TjmfuVvdDEUuAAAAAACAJN4+eFwPr9yoJ9fu0NCBffUvMy/V3ddcrL69e4UdDUlQ5AIAAAAAAGji2Ml6/eB3W/XoczU6drJen7x2vL54U75yB/ULOxpaQZELAAAAAABAUkOD61d/eUOlz2zQzn1HVXjJKH39A1MUGTkk7GhIQacVucxsqCS5+4HO+gwAAAC0zszGSYpIqmq8Lwvu0/LcfVt4yQAA6F5e3LJHC57eoL/s2q8pF5ynn9xztd6dPyLsWGiHzuzk2idJZhaXtFTSYnd/qRM/DwAAAAEzu13S/ZIKgk1FklYHP5dIesDMIu6+PYx8AAB0F397/YBKn9mgNZve1oU5A/TQ7Kn6yLTR6t2LofLZpjMnpW2TtFVSsSSTtKQTPwsAAAABM7tJUoWkYZLuU+Je7BR3Xyhpv6TSrk+XOWY208zK9+/fH3YUAEAW2rnviP7xyZf0we/+Vi/tiOvrH5ii1V+7QXdMH0OBK0t1WieXu09o8utTnfU5AAAAOMt8SfvcPd/McpW8mFUpaXrXxsosd18uaXk0Gp0bdhYAQPbYd/iEHn1+i3784nbJpOL3RPT59+YrZ1DfsKOhgxg8DwAA0PMUSloc/OwtHFOrxKwuAADOCcdO1uuHv9umR5/fokPH6zSrYIy+UjRJF+YODDsaMoQiFwAAQM9TLSnaxjGFwXEAAPRo9Q2up9bt1MMrN+nNA8d005TzNe/9UzT5gvPCjoYMS2sml5ndZGYLGldQDLaNM7MVZlYffH0rczEBAADQDkslFZjZZ5LtNLNFksbrdLcXAAA9jrtr1atv6dZHfqN5T/1Zo3IG6L+Kr9ETn5xBgauHSreTq0TSTe5+f5NtlUrcLK2SNFzSfDPb6+4PdTAjAAAA2sHdy8ysSFK5EoPnXdJsM5staY4SA+mXufvjIcYEAKDTVL+2Tw88vUF/2lqr8SMG69G7C3TrZRfIjIHyPVm6Ra5CSSsbfzGzO5SY6bDM3e8Mtm2R9FlJFLkAAAC6mLsXmdk8nV5dsSTYFZdU4u6sfA0A6HFq3j6kB1ds1NOvvKkRQ/rrGx+5THfNuEh9e6f1IhuyTLpFrlxJsSa/FynxhPDJJtuqJd2R5vUBAADQQe5eJqnMzHKUeCAZc/f9IccCACDjdh88pkcqN+u/1u7QgD699JXCSbrn+vEa3J9R5OeSdP/XjitR6GpUGHyvbLItNzgOAAAAIQoKW+vDzgEAQKYdOl6n8jU1WvLbrTpZ36C7rx6rf7hxokae1z/saAhBukWuZZKKzWyfpAk6/arigSbHRCWt7WA+AAAAAACAM5yoa9BP//Sa/m3VZu09fEIfvOId+trNkzV+xOCwoyFE6Ra55ilRxLov+L1a0tzGnWY2V4lOrtIOpQMAAEBazGyBpGKd2X3fnLs773EAALJGQ4PrV395Qw8+u1Hb9x7RNZE8/eDWSzT1otb+7w7nirRuaoKW9+lmNj74fWuzQ5YqMfNhdQfzAQAAoJ3MbJESDyBNZ85R7VHMbKakmfn5+WFHAQB0gRdr9uiBpzfozzv3a8oF5+mHn5qhGyaNZMVEnNKhJ3dJiluN2/dLWtWRawMAACBtc5SYjRpt6X6tJ3D35ZKWR6PRuW0eDADIWq++cUAPPL1Baza9rQtzBujB2VN127TR6t2L4hbORHs6AABAz7S0Jxe4AAA93859R/Twyk36+fpdGjqgr77+gSn6+LvGaUDf3mFHQzeVdpHLzG6XdKcSQ+db4u5+VbqfAQAAgLRUSsoLOwQAAOmIHzmh7z+3RT/+/XZJUvH1EX3+hnzlDOobcjJ0d2kVuczsXkkPKDHnoTWezvUBAADQIfdJqjKzz7j7E2GHAQAgFcdO1uuHv9umR5/fokPH63RHwRj9Y9EkXZg7MOxoyBLpdnKVBN9nS6oMZnABAACgG3D3mJmVSyoPvseUmNGV5FC67gEA4apvcD1VvVPfXrlJb+w/pvdNHqn5t07RlAuGhh0NWSbdIldE0jJ3fyqTYQAAANBxZvaApHt1uut+QguH0nUPAAiNu2v1ht0qfWaDNr11SFMvytXDc67UuyYMDzsaslS6Ra71kmozGQQAAAAZUxx8n+XuPws1CQAASazbvk+lz2zQn7bWatzwQfr+Rwv0gcsvkBkrJiJ96Ra57pFUaWaL3P3lTAYCAABAh+Uq0XVPgQsA0K28+sYBPfTsRlW+ulsjhvTTNz78Tt111Vj17d0r7GjoAdItcs2RtFVStZmtk7SuhePc3T+f5mcAAAAgPevDDgAAQFPb9x7Wwys36b9ffl1D+vfRvbdM1qfePU6D+qVblgDOlu7fTfOb/BwNvpJxSRS5AAAAulZj1/1Uuu4BAGF668Ax/duqzXpy7Q716W367Hsn6LPvmaCcQX3DjoYeKN0i1/SMpgAAAEAm0XUPAAjVvsMntGhNjX704jbVN7j+7qqx+ocb83X+0AFhR0MPllaRy91pgQcAAOi+srLr3swKlZgnJkly94oQ4wAA0nD4eJ1+8MJWlf8mpkMn6vSRK0frK4WTNHb4oLCj4RzQ4ZdfzWycpAJJMyTVSKpy95c6el0AAACkLVu77kvcfbYkmdkyM6t093jYoQAAbTteV6///ONr+v5zW7Tn0AkVXTpKX715kqZcMDTsaDiHpF3kMrOhkpZImtW4KfjuZrZMUrG7H+hgPgAAALRTNnbdB11ctU02rVXitcvycBIBAFJRV9+gn63fpUcqN2tX/KjeFRmu8o9PVsHYYWFHwzmoI51cq5Xo4KqQtFJSTFJEiZuROcG+SR0N2BYzK9bpG6KIu5d19Jxgv3T6Keh8niICAAB0qoikpvdbcUkTQsoCAGiDu+uZV97Ug89uVM3bh3XFmBw9cMflui5/hMys7QsAnSCtIpeZPSBpmqRCd1/dZNcqSUuCItEiM/uWu389AzlbylEsnZ7XYGYRM1vs7iXpnmNmxe5e3uz4deImCwAAdDNmlqNEp5O7+11Nti9I8RLeGfdqZlYg6f7GVw+b7WvpYWOupL3NDs8VAKBbcXe9sGWPFq7YqD/v3K8JIwfrsbsL9P7LLqC4hdCl28lVKKmyWYHrFHcvD25giiR1WpFLibkNp2ZOuHssaHVP6xwzO+tGKvizlJpZobtXZiw5AABAZsxWYoD8XU22zW/h2OZcGbxXC4pbdwa/RpLsb+1hY7LOLTrpAaAbqX5tn8qe2aA/xGo1OnegFs66QrdNG60+vXuFHQ2QlH6Rq0DS4jaOiUm6I83rtykoSBUk2RVvqSDV1jlKPFVcbGZLm72e2PgqJgAAQLfh7vvN7KxuKYU0eN7dqyVVB8WuZA8eW3tAGdOZuXOVmMsFAAjZxjcPauGKjap89S2NGNJP/zzzUn306rHq36d32NGAM6Rb5KpUy0tRNyqQVJ3m9VPRfG5Do9rgs5N1XbV6jruXmdn0JPO3IkrceAEAAHQr7v5Ukm3dbvB8Kg8ozazpyIkJYug8AITqtb1H9O3KTfrFS7s0pF8ffe3mSfrUu8drcP+OjPcGOk+6f2dWKDFz66vu/lDznWa2SNJ4SQ90JFwb8nTmCjyN4pKGp3tO8ATyFDObJSnW0quKQdt9sSSNHTs2peAAAACdycyGtrXKtZndrsT4ia5aDTuVB5QLgnuvuKSVLPwDAOHYfeCYvrt6i376p9fUu5ep+D0Rfe69E5Q7qF/Y0YBWpVXkCuZUFUlaGDxxWyWpRoknbnMkDVPixuTxjCUNQfDE8X5JN7V0TDCkvlySotGod1E0AACA1uwzs3nJHkZKpwbWPy7pm5KSHtMJUn3YmNKbADxoBIDM23/kpB5bU6MfvbhVdfWuO2dcpC/eNFGjhg4IOxqQkrR7DN19duMqipLym+2e7+4LO5QsNXlJtiVbmSfdc0olzeYpIgAAyDIWfCUVzPKqVGJYfVcVuTKKB40AkDlHTtTph7/bpkVranToeJ0+PPVCfaVoki4ePjjsaEC7dOhF2sabCzMbr0SbeawLZ0BUKfmy0nlq+QlgyueY2TxJpe7OLC4AAJCNWiz8mNk4Je7dxndVmEA6DygBAJ3keF29/utPO/Td1Vu059BxFV5yvr5682Rd8o6hYUcD0pKRaXHuvlXS1kxcqx2fGTezmJnlNuu0ym1pflaq5wQdahVNC1wtrdgIAADQHZhZg84sbJWZWVlrp0ha17mpzpDOA8pWmdlMSTPz85u/VAAAaE19g+vn63fpO5WbtHPfUV09Pk+L/0eBpl+c7FkEkD1aLXIF8xrKJbm739Vk+4IUr+/u/vUO5GtLqRIzs+ZLUrBcddNiVSQ4Zm6TolZb5xRKqmoscAVzudpaSRIAACBsq3S6yFWoxAPIlkYuxCStVReuXpjOA8oUrrlc0vJoNDo3MykBoGdzd63461t66NmN2rz7kC4bPVTfvO1yvWfiCJm1+JY7kDVS6eSarcQN011Nts1P8fouqdOKXMEA/OKgMJUrKeLuTZeejihxk5en4CavtXOCotjK4OfmHzess/4cAAAAHeXuRY0/B11di9z9wZDitNQK0OrDRgBA5/ndlj0qW7FRL++IKzJysB69u0C3XnYBxS30KK0WuYKhpLOT7JreSXnaLZgL1tK+SiUpTrV0TtC9xT/hAAAg25UrzVcAOyJ4YFiixEPGAjNbLGld471XCg8o2/t5vK4IAG14eUdcZSs26Hdb9urCnAEqu+MK3V4wWn169wo7GpBx5s5iNJkSjUa9qqoq7BgAAKCTmNk6d2eMQTfDPRgAnG3L7kN66NmNevqVN5U3uJ++8L583X31WA3o2zvsaEC7pXoPltbgeTMb6u4H2jjmdkmVbR0HAAAAAAAy4439R/VI5WYtrdqhgX1768uFE3XP9REN6Z+RdeeAbi3dv8v3mdk8d38o2c5gYP3jkr4pKekxAAAAAAAgM+JHTuix52v0oxe3yV36xLXj9Pfvy9fwIf3DjgZ0mXSLXKZWZlcFs7wqlRhWT5ELAAAAGcdMLgCQjpyo0w9/t02L1tTo0PE63TZttL5SOEkX5Q0KOxrQ5TrSr9jiMC8zGyepQNL4DlwfAAAAaJG7L5e0PBqNzg07CwB0tZP1DXpy7Q49smqz3j54XIWXnK97b5miyRecF3Y0IDQpF7mCpaibFrbKzKystVMkrUs3GAAAAAAAOFNDg+tXf3lDDz27Udv2HtGMccP02N0Fio7LCzsaELr2dHKt0ukiV6GkrZLiLRwbk7RWieWrAQAAAABAB7i7frt5j8pWbNAruw5o8qjz9MQnorpxyvkya3GaEHBOSbnI5e5FjT8HXV2L3P3BTkkFAAAAAAAkSS/tiKv06Q36fWyvxgwbqIfnTNWHrxyt3r0obgFNpTuTq1xSdSaDAAAAAO3B4HkAPd2W3Yf04IqNeuavb2r44H7655mX6qNXj1X/Pr3DjgZ0S2kVudz9s5kOAgAAgMwxs9sl3Skp0sph7u5XdVGkjGPwPICe6o39R/WdlZu1bN0ODezbW18unKh7ro9oSP+OrB0H9Hz8EwIAANDDmNm9kh5QYiGg1rS4WjYAoOvFj5zQo8/X6EcvbpNc+sS14/R7rXi+AAAgAElEQVT378vX8CH9w44GZIW0i1xmNk7SYklRSbktHObuTiENAACga5UE32dLqnT3/WGGAQC07siJOv3wd9u0aE2NDh2v023TRusrhZN0Ud6gsKMBWSWtApSZTZNUpcTTwbgSKy1GlFhVUTrdFr++owEBAADQbhFJy9z9qbCDAABadrK+Qf+1dof+bdVmvX3wuAovOV/33jJFky84L+xoQFZKt8uqVNJ+STe5+3rp1IqLxe6+2swiShTBvpWZmAAAAGiH9ZJqww7R2Rg8DyBbNTS4fvmXN/TQsxu1fe8RzRg3TI/dXaDouLywowFZrVea5xVKWtxY4ArEFby26O4xSUt1ulUeAAAAXeceSXPMbGrYQTqTuy939+KcnJywowBAStxdaza9rZnfe0Ff/Ol6DejTW098IqqlJe+iwAVkQLqdXKcKWk3EJM2Q9LMmx0TTvD4AAADSN0eJcRLVZrZO0roWjnN3/3zXxQKAc9f61/ap9JkN+kOsVmOGDdTDc6bqw1eOVu9eba0RAiBV6Ra5qnR2AWuppLmS7g9+n6WWB9IDAACg88xv8nNULT94dEkUuQCgE23ZfVALV2zUir++peGD++mfZ16qj149Vv379A47GtDjpFvkKpe01MyudPeXgm3LJD1gZpuD3yOSVnY0IAAAANptetgBAOBc93r8qB6p3Kxl63ZoYN/e+nLhRN1zfURD+qf7n+EA2pLWP13uXmFm05Vog2/cttXM5khaIilHUoUSnV0AAADoQs3mpgIAutC+wyf02Joa/ejFbZJLn7x2vL7wvgkaPqR/2NGAHi/tEnKymyd3r1CiuAUAAIBuwMzGSSpQYnZqjaSqJp34WY3VFQF0J0dO1OmHv9umRc/X6NCJOt0+bYy+XDhRF+UNCjsacM5Iq8hlZjdKqu0pN0gAAAA9jZkNVaLDflbjpuC7m9kyScXufiCUcBni7sslLY9Go7w9ACA0J+sb9OTaHXpk1Wa9ffC4Ci8ZpXtvmazJF5wXdjTgnJNuJ1eFpC2SrspgFgAAAGTOaiU6uCqUmJMaU2Jm6pzgq0DSpNDSAUCWc3c988qbWrhio2J7Dit68TA9dneBouPywo4GnLPSLXItk3SPmV3s7tszGQgAAAAdY2YPSJomqdDdVzfZtUrSEjMrlrTIzL7l7l8PJSQAZLE/xvZqwdMb9NKOuPLPH6IlH4+q8JLzZWZtnwyg06Rb5JonabaklWZWRKELAACgWymUVNmswHWKu5cHha4iSRS5ACBFG948oLJnNmr1ht0aNbS/Su+4XHcUjFGf3r3CjgZA6Re55kpaKqlYUszMqiVVJTnO3f3z6YYDAABAWgokLW7jmJikO7ogCwBkvV3xo/r2yk16qnqnhvTvo3nvn6xPXTteA/v1DjsagCbSLXKVNfnZJE0PvppzSRS5AAAAulalpGgbxxRIqu6CLACQteJHTuix52v0wxe3SS7dc914ff6GfA0b3C/saACSSLfIlaygBQAAgO6hQomZW19194ea7zSzRZLGS3qgy5MBQBY4drJeP3pxmx59bosOHq/TbdNG6x+LJmnMsEFhRwPQirSKXO6+PtNBAAAAkBnBzK0iSQvNrESJgfM1kiYosbLiMEkr3f3xEGMCQLdT3+B6qnqnvr1yk97Yf0w3TB6p+e+fokveMTTsaABSkG4n1ylmNk6J5air3P1AsG2opDx339bR6wMAAKD93H124yqKkvKb7Z7v7gtDiJVRZjZT0sz8/OZ/PABoH3fX6g27VfrMBm1665CmjsnRQ3Om6toJI8KOBqAd0l4CwsxuN7O1SjwVXKkz5z6USKoxs4s7mA8AAABpcvdyd++lRAfXbEnT3b1XTyhwSZK7L3f34pycnLCjAMhi67bv052L/6DP/LhKJ+oa9P2PFugXX3g3BS4gC6XVyWVmNykx6yEm6T5JpU33u/tCM7s/2H5XR0MCAAAgfe6+VdLWsHMAQHdS8/YhLXxmo57565saMaS/vvGRy3TXjIvUt3favSAAQpbu64rzJe1z93wzy1WzIlegUgyoBwAA6DRmliOpXJK7+11Nti9I8RLu7l/vlHAA0E3tPnBM31m1WU+u3aEBfXrpK4WTdM/14zW4f4en+QAIWbr/FBdKWhz87C0cU6vErC4AAAB0ntlK3I817Z6fn+K5LokiF4BzwoFjJ1W+JqYnXtiqk/UN+tjVY/UPN03UiCH9w44GIEPSLXJV68wZXMkUBscBAACgE7j7fjObnWQX3fQAEDheV6+f/OE1fXf1Zu07clIfuuIduveWybp4+OCwowHIsHSLXEslLTCzzygxm+sMZrZI0nhJD3QgGwAAANrg7k8l2bY+jCwA0J00NLiW//l1PfjsRu2oPaprJwzXfbdO0RVjcsOOBqCTpFXkcvcyMytSYgbEfUq0us8OniTOkTRM0jJ3fzxjSQEAAJASMxvq7gfaOOZ2SZVtHQcA2eg3m97WA09v0N/eOKBL3zFU//7py3X9xBEys7CjAehEaU/Wc/ciM5unRJHLJJUEu+KSStx9SQbyAQAAoP32mdk8d38o2c5gYP3jkr4pKekxAJCN/rJzv0qf2aAXtuzRmGED9Z07r9T/M/VC9epFcQs4F3Ro+Qh3L5NUFtwoRSTF3H1/RpKlyMyKlRhyL0mRIFOHzknnmgAAAN2IBV9JBbO8KpUYVk+RC0DWe23vET347Eb998uva9igvvqfH7pUH7tmrPr36R12NABdKK0iV/MW+KCwtb7ZMZ3eAh8Uo+TuFcHvETNb7O4l6Z6TzjUBAAC6oZZWwJaZjZNUoMQMVQDIWnsOHdf3Vm/RT/64Xb17mf7+ffkqfm9EQwf0DTsagBCk28nVXVrgS9z91OpB7h4zs8IOnpPONQEAAEJlZg06s7BVZmatdaObpHWdmwoAOsfh43V64oWtWrymRsfqGjQnepG+XDhRo4YOCDsagBClW+QKvQXezHKVeALZXNzMCt29sr3nSKpq7zUBAAC6iVU6XeQqlLRViVmpycQkrVViEaGsZWYzJc3Mz88POwqALnKyvkFPrt2h71Ru1p5Dx3XLO0fp3lumKP/8IWFHA9ANdGQmV9gt8BElv3GrDT47WUGqrXNq07hmp/tfy/+qv73OwkcAAKTi0guH6p9nvjPsGF3O3Ysafw66uha5+4MhRup07r5c0vJoNDo37CwAOldDg+tXf3lDDz27Udv2HtGMccO0+H9M1/SLh4UdDUA3knKRqxu2wOfp9HD4puKShqd5TruvGczwKpaksWPHtp4YAACga5RLqg47BAB0lLvrN5v3qOyZDfrr6wc0edR5WvLxqAovOV9mrJgI4Ezt6eQ651rgU+Hu5Qr+nNFotMXuto44F59GAwCA9Ln7Z8POAAAdtf61fSp9ZoP+EKvVmGED9fCcqfrwlaPVuxfFLQDJpVzk6qYt8HlJtuVK2tuBc9K5JgAAAAAgA7bsPqiFKzZqxV/f0vDB/fQvMy/V3109Vv379A47GoBuLt2ZXN2hBb5KieJTc3lqOVtb56RzTQAAgG4nmJG6WFJUye9vJMndvSMzWgEgY3bFj+o7KzfpqeqdGtSvj/6xaJI+fd14DenPv6YApCatf1t0hxZ4d4+bWczMct296WuTuS2tgpjKOe29JgAAQHdjZtOUeHhnSoyX2KrEAjyx4JBI8H1916cDgDPVHj6h7z+3Rf/x++2SpE+9e7y+8L585Q3uF3IyANmm1SKXmeUo0bXl7n5Xk+0LUry+u/vXO5CvLaWS7pc0X5LM7IwVEM0sEhwzt0nRqtVzUtgPAADQ3ZVK2i/pJndfL50aN1Hs7quDe6QqSd8KMSOAc9zh43V64oWtKv9NTEdO1OmOgjH6ctEkjc4dGHY0AFkqlU6u2UoMnL+rybb5KV7fJXVakcvdy82s2MwKlWjDj7h7SZNDIkoMyc9TMCS/rXNSuCYAAEB3VyiptLHAFYgreG3R3WNmtlRSiaSfhZAPwDnseF29fvrH1/S957Zoz6ETuuWdo/S1mydr4qjzwo4GIMu1WuRy9/1mNjvJrumdlKfdgtUNW9pXKWlYe85JZT8AAEA3d6qg1URM0gydLmrFlZjXBQBdor7B9f+/tEsPr9yknfuO6ppInso/PkUFY8/6TzYASEubnVzu/lSSbcxvAAAA6L6qdHYBa6mkuUqMZZCkWWp5ID0AZIy7a/WG3Vq4YqM2vHlQ77xwqL552+V6z8QRMrOw4wHoQVimAgAAoOcpl7TUzK5095eCbcskPWBmm4PfI5JWhpKuFcG8sBJ3T3U8BoBubO22WpU+vUFV2/dp3PBB+u7fTdMHL3+HevWiuAUg8yhyAQAA9DDuXmFm05VYVbFx21YzmyNpiaQcSRVKdHZ1G2Y2S1JR2DkAdNyrbxzQwhUbtXrDbp1/Xn9987bLNCd6kfr27hV2NAA9GEUuAACAHijZeAl3r1CiuNUtBcW5uBILHwHIQq/tPaJvV27SL17apfP699H890/RJ68dp4H9eocdDcA5gCIXAABAD2NmQ939QBvH3C6psq3jACAVbx88ru+t3qz//NNr6mWmkvdM0OfeO0E5g/qGHQ3AOYQiFwAAQM+zz8zmuftDyXaaWY6kxyV9U1LSY1o4r0DS/e5+VqeVmRVLqg1+jbh7WftjA8g2B46d1JLfxPTEC1t1vK5Bd864SF+8caIuyBkQdjQA5yCKXAAAAD2PBV9Juft+M6uUdJdSKHIFxa07g18jSfYXB9etCH6PmNlidy8Jfp8naXgLl1/p7pVtZQDQvRw7Wa//+P12ff/5LYofOakPXfEOffXmyRo/YnDY0QCcw1otcpnZk5Jq3f1zXZQHAAAAmeEt7TCzcZIKJI1P6ULu1ZKqg2JXYZJDStx9epPjY2ZW2OR3urqAHqKuvkE/q96lb1du0hv7j+k9k0Zq3i2TddnonLCjAUCbnVyzJS1uvtHM7pFU1WRJagAAAITIzBp0ZmGrzMxaKy6ZpHUZ+NxcJQpmzcXNrJAuLaBncHet+OubWrhio2rePqypF+XqoTlTde2EEWFHA4BT2ipyxSXlJdleLmmeJIpcAAAA3cMqnS5yFUraqsS9XDIxSWuVuKfrqEgLn1OrRPEr5SJX0P1VIqnAzIrdPRP5AHTQi1v2qHTFRr28I64JIwdr0cem65Z3jpJZi29FA0Ao2ipyrZJUaGZT3f3lZvtabIEHAABA13L3osafg66uRe7+YBd8dJ5OD5xvKq6W53AlFXR9pVQUC+aAFUvS2LFj2/MxAFL0l537VbZig367eY8uzBmgsllX6PZpo9Wnd6+wowFAUm0Vue6RtE2JGQxNt7vaboGXJHd3htsDAAB0rXJJ1WGH6ExBl1e5JEWjUR6+AhkUe/uQHlq5Sb/68xsaNqiv/umDl+hj11ysAX17hx0NAFrVagHK3fdLGhasiFOo068uTlPrLfAAAAAIibt/tos/Mtl4i1xJe7s4B4AOeGP/UT1SuVnL1u1U/z699A835mvueyIaOqBv2NEAICUpdVkFK+Kc6trq4hZ4AAAAdF9VShS0mstTJ3eTmdlMSTPz8/M782OAHm/f4RN69Pkt+vHvt0su/Y9rLtbf35ivEUP6hx0NANol3VcJS5QYVgoAAIBuxsxSvU9zd7+qI5/l7nEzi5lZrrs37fLP7eyVFd19uaTl0Wh0bmd+DtBTHT5epyde2Kolv4np8Ik63TZtjL5cOFEX5Q0KOxoApCWtIpe7L2n82czGKbFyzgxJNZKq3J1VFwEAAMIzvZOum+y1REkqlXS/pPmSZGbtWlURQNc6Xlev//zja/re6i3ae/iEbnnnKH3t5smaOOq8sKMBQIekPRTezIZKWiJpVuOm4Lub2TJJxe5+oIP5AAAA0E7u3uLSZ2Y2XtJnJd3u7hNTuZ6ZRZTo5C+UVGBmiyWtC4a/y93LzazYzAqVeHUx4u4lHf1zpJCL1xWBdqhvcP18/S59e+Um7Yof1bsiwzXv/ZM1beywsKMBQEaYe3qL0ZhZlRIdXBWSVkqKSYpImiPpJklb3H1ShnJmhWg06lVVVWHHAAAAncTM1rl7NOwcmWBmz0pa4e4PhZ2lo7gHA1rn7lrx17f00LMbtXn3IV0+Okfz3j9Z1+WPkJm1fQEACFmq92BpdXKZ2QNKrLBY6O6rm+xaJWmJmRVLWmRm33L3r6fzGQAAAOhUKyXdJSnri1wAWvbilj0qXbFRL++IKzJysB67u0Dvv+wCilsAeqR0X1cslFTZrMB1SmPLuqQiSRS5AAAAup8JSnTlA+iB/rwzroUrNuq3m/foHTkDVHbHFbq9YLT69G7xbWYAyHrpFrkKJC1u45iYpDvSvD4AAADSZGaPtXFIRImHlvE2juvWmMkFnG3L7kN66NmNevqVN5U3uJ/+6YOX6GPXXKwBfXuHHQ0AOl26Ra5KSW29C1kgqTrN6wMAACB9qQ59n9+pKTqZuy+XtDwajc4NOwsQtl3xo3qkcpMq1u3UwL699aWbJuqe68frvAF9w44GAF0m3SJXhRIzt76abFipmS2SNF7SAx0JBwAAgLRMT+GYmLvv7/QkADrV3kPH9ejzNfqPP2yXXPrkteP1hfdN0PAh/cOOBgBdLq0iVzBzq0jSQjMrUWLgfI0Ssx3mSBomaaW7P56xpAAAAEiJu68POwOAznXoeJ0e/21MS34T09GT9Zo1fYy+VDhJo3MHhh0NAEKTbieX3H124yqKkpoPQpjv7gs7lAwAAAAAcIZjJ+v1kz++pu8/t0W1h0/o1ssu0FdvnqT8888LOxoAhC7tIpeU6OiSVG5m45WYwRXjySEAAED3YGbjJM2SNENSrhILA1W5+xMhxsoYBs/jXFJX36CfVe/Sdyo36fX9x3Rd/gjde8tkTb0oN+xoANBtdKjI1cjdt0ramolrAQAAoOOCFRaLG39tsqvYzEqV6LzP6mIXg+dxLnB3PfPKm3rw2Y2qefuwpo7J0cLZU/Xu/BFhRwOAbicjRS4AAAB0H8EiQI0FrjJJTyrRxRWR9FlJc5Xoxq9195+HkxJAW17YvEcLV2zQyzv3K//8IVr0sem65Z2jZGZtnwwA5yCKXAAAAD3PHEkuqcjdVzfZvl5SiZktk/SspPslUeQCupmXdsRV9swGvVizV6NzB2rhrCt0e8EY9e5FcQsAWkORCwAAoOeplbS2WYHrFHevNLNVkm7s2lgAWrP5rYN68NmNWvHXtzR8cD/9fx+6VHdfM1b9+/QOOxoAZAWKXAAAAD1PtRKdXK2pkTSsC7J0GgbPo6fYue+IvlO5WT+r3qlB/froK4WT9Jnrx2tIf/5zDQDag39rAgAA9DwLJFWa2XnufrD5TjPLkTQ7+MpaDJ5Httt76Li+99wW/eQPr0kmfea68frcDfnKG9wv7GgAkJUocgEAAPQ8xUqsqFhtZpVJ9s8Jvs82s+aFLnf3z3dqOuAcd+xkvZ54YasWPV+jwyfqNCd6kb5400RdmDsw7GgAkNUocgEAAPQ8JcH3XEkTUjiuKZdEkQvoBPUNrp9V79TDKzfpjf3HVHjJKN1362Tln39e2NEAoEdIq8hlZjdKqnX3lzKcBwAAAB03PewAAM60ZtPbWvDrV7XhzYOaOiZH377zSl0TGR52LADoUdLt5KqQtEXSVRnMAgAAgAxw9/VhZwCQ8LfXD2jB06/qt5v36KK8gfru303TBy9/h3r1srCjAUCPk26Ra5mke8zsYnffnslAAAAAAJDtXo8f1YPPbtTP1+9SzsC++p8fulQfu2as+vfpHXY0AOix0i1yzVNiNZ6VZlZEoQsAAABdzcxmSpqZn58fdhTglAPHTuqx52v0gxe2yiUVXx/R52/IV86gvmFHA4AeL90i11xJS5VYuSdmZtWSqpIc16mr85hZsaTa4NeIu5d19Jxgv3R6lsV8d49nIi8AAEBXMbMFStyr5bZymLt71i5E5O7LJS2PRqNzw84CnKhr0E/+uF3/tmqz9h05qdumjdZXb56kMcMGhR0NAM4Z6d7UNC0MmRIFoWQDTjttdZ7GYpS7VwS/R8xssbsnWyUopXPMrNjdy5sdv06tr0oEAADQrZjZIiUeSpqkWMhxgB7N3fXrv7ypshUbtH3vEV07Ybi+/oFLdNnonLCjAcA5J90iV3dYsafE3U/lcPeYmRWme46ZnfWU093LzazUzArdvTJjyQEAADrXHElxSVF33xp2GKCnWrutVt/81at6aUdck0edpx9+aoZumDRSZgyVB4AwpFXkCnvFnqAgVZBkV7ylglRb5yjxCuNiM1va7PXEmKRIK1mKlXgVQGPHjm3HnwIAAKBTLaXABXSOmrcPqfTpDXr2b29p1ND+KrvjCt0xfYx6s2IiAISqwzMYzGycEkWgKnc/EGwbKinP3bd19PotiCjxdLK5WiUKWcm6rlo9x93LzGx6kvlbEbXS5h+83lguSdFo1FPIDgAA0NkqJeWFHQLoad4+eFyPrNqkn/5phwb06aWv3TxJn75uvAb1y9rRdgDQo6T9b2Mzu13S/TrdHVUkaXXwc4mkB8ws0kkrL+bp9PD4puKShqd7jrtXN91hZrMkxXhVEQAAZJn7JFWZ2Wfc/YmwwwDZ7siJOj3x261atKZGx+oa9NGrxupLhRM1Ykj/sKMBAJpIq8hlZjdJqlCiw+k+SaVN97v7QjO7P9h+V0dDhiF4vfF+STeFnQUAAKA9grmj5ZLKg+8xJe9od3e/qmvTAdmjvsFVsW6HHl65SW8dOK5b3jlK894/RRNGDgk7GgAgiXQ7ueZL2ufu+UExqDTJMZVKYUB9MNNqdoqfO7vJ64TJWvBzJe1t5fz2nFPa7PMAAACygpk9IOleJVZXlFpeKTqrRy2Y2UxJM/Pz88OOgh7G3fX8xre14OlXtemtQ5o2Nlff+2iBZozjLWAA6M7SLXIVSloc/NzSzVGtWhnY3qjpTKt2qFKiONVcnqTqJNvbdY6ZzZNU6u4suQ0AALJRcfB9lrv/LNQkncjdl0taHo1G54adBT3HK7v261u/flUv1uzVxcMH6dG7C3TrZRewYiIAZIF0i1zVkqJtHFOolgtOHeLucTOLmVlus06r3JbmZ6V6TtBZVtG0wNXSio0AAADdVK6kZT25wAVk2s59R/Tgio36xUuva9igvvqXmZfqo1dfrH59eoUdDQCQonT/jb1UUoGZfSbZTjNbJGm8Tnd7dYZSJWZmNX7mGasqmlnEzJYFr1Omek6hEqtExoLfc4NtAAAA2WR92AGAbLH/yEl969ev6sYH1+jpV97U52+YoDXz3qdPvns8BS4AyDJpdXK5e5mZFSnxmuF9SryyONvMZkuaI2mYEk8PH89Y0rMzlJtZcVCEypUUcfeSJodElOgmy1MwaLW1c8wsImll8HPzjxvWWX8OAACATnCPpEozm+ruL4cdBuiOjtfV6z9+v13fXb1FB46d1O3TxuirN0/ShbkDw44GAEhTuq8ryt2LgtlV9ykx1LSxwBSXVOLuSzKQr60MLc7yCl4vPKs41dI5QfcWL9oDAICeYI6krZKqzWydpHUtHOfu/vmuiwWEr6HB9cu/vKGFKzZoR+1RXT9xhO6/9RJdeuHQsKMBADoo7SKXlOjoklRmZjlKdE7F3H1/RpIBAAAgXfOb/BxVy7NUXRJFLpwz/hDbqwW/flUv79yvKRecp3//9FV6z6SRYccCAGRIh4pcZjZO0ixJM5R4/a8meFq4zN0PdDgdAAAA0jE97ABAd7L5rYN64OkNWrVht96RM0APzp6q26aNVu9evMgBAD1J2kUuM3tMp5enbvx/h6Lge5mZzXP3JzoSDgAAAO3n7gyeByTtqD2ib1du0i/W79Kgfn107y2T9ZnrxmtA395hRwMAdIK0ilxm9oASM7jikhYosUJhTIlXFmcosYphuZnVuvvPM5QVAAAA7RR03hcocY9Wo8RK0i+FmQnobG8dOKbvrt6sJ9fuUC8zfea68frcDfnKG9wv7GgAgE6UbidXsRIzHArcfVuT7eslrTezpUoUve6XRJELAACgi5nZUElLlBgtIZ3uvHczWyapmPES6Gn2HT6hRWtq9KMXt6m+wXXnjIv0DzdO1AU5A8KOBgDoAukWuWolrWxW4DrF3eNBt9eCdIMBAID/297dR8dV33ce/3yNwTzZjGXzDAaPbBxIiYOs0NAsbQJSYNs6bRMbkt2E9qSxlM3Z7MkDWHHP7jl7zp4DyJBCmnQXidBtd7PZgpWe7no3sZEgpbC7SbBFkgZiY3uMeUoMRpaNDX7Ud/+4v8HDeJ7uHWmuRnq/zrnHmjv34Ts/NLpfvvd3fz+gLo8r6sE1IGlQJ3rd3xKWNklXpBYdMI7ePHRUDz21U99+cqcOHjmmP3z/xfpSx2JdNu+stEMDADRQ0iLXcA3b7FA0dTUAAAAaKNxsvEZSh7s/XvDWY5IeNLMuSQ+Y2Z3u/mepBDkOzGy5pOWLFi1KOxSk5NDR4/qv/2+X/uM/bNfet47qpveer690LtGSC2anHRoAIAVJi1x3SRoys9nu/maZbbok3Z3w+AAAAEiuQ9JQUYHrHe7eHwpdnZKatsjl7uslrW9vb1+VdixorKPHx/Tw0y/pm49v0+79h3X94vm6/aNLtPTSTNqhAQBSVLHIFWZQLPu2pGEzGyrxXoei7vB7JX07eXgAAABIoE1SX5VtcpI+0YBYgHFzfMz1P3/2iu4b3KYXR97Sssvm6v5br9F1rfPSDg0AMAlU68nVXeX9jKTWCu+vlPTJWBEBAACgXkOS2qts06bahqAAUufu2vjsbv354FY9v/uArrpwjv7zn3xAH15yrsys+gEAANNCtSLXsoZEAQAAgPE0oGjMra+6+9eL3zSzByQtFENLYJJzdz21fY/u3bhVP3t5n7Lzz9K3/sU1+t3fuFAzZlDcAgC8W8Uil7s/06hAAAAAMD7CmFudkg0oSDYAABnuSURBVO4xs25FA87vUNQD/xZJcxXNlM2wEpi0Nu8a0T0bt+pHuRFdnDlDa1e8Tx+/5mLNPGVG2qEBACappAPPAwAAYBJz95X5WRQlFU8/2OPu96QQFlDVs6/u09cffV6Pb3lN888+Tf9++VX61G8u0KyZp6QdGgBgkqPIBQAAMEW5e7+kfjNbqGgMrhw99TFZ5V4/oD8ffF7/6+e/0pzTZ2r1zUv0J791uc48jf9lAQDUJvEVw8zuktSlaPD5ctzduSoBAACkyN13StqZf21mcyS1uPsLqQUFBK+Mvq2/GNqmgeGXNWvmDP3rjyzSqt/O6pwzTk07NABAk0lUgAqDla6SZIqmnwYAAECDmdmNih5H7HP3e2PsOiDpBjNrcff9ExMdUNnrbx7WX/5wu7774xclSX983eX6wkdaNf/sWSlHBgBoVkl7Wd0iaVRSe7gzCAAAgMbrlpSVNBRzv89L2i7pa5L+bLyDAirZ99ZR9T+5Q3/11As6cnxMK5ddoi/euFgXZ85IOzQAQJOr51HCRyhwAQAApCo/ztZP4+zk7jkzy0laqUlU5DKzFZJaFM0CuSOMKYYp4uDhY/rr//uC+p7Yof2HjuljSy/Slzuv0ML5Z6UdGgBgikha5BpSlIAAAAAgPVlJgwn3HZZ04zjGUhczy0oadfeB8HqzmW1y9+GUQ0OdDh87ru/++EX95Q+3a8+BI+q48jx9pXOJrrpoTtqhAQCmmKRFrq9J2mRmf+ruD41nQAAAAIhltI59K00g1Ghtkm7ViUcvN0nqUFSMQxM6dnxM3xt+Wd8Y2qZX9x3Sddl56r9tidoWzE07NADAFJWoyBW6uOenpO5XNPh8qQTL3f3aegIEAABAWTlFxaEk2jSJJhBy9wEzKxxbrF3SurTiQXJjY67//U+/0n2Dzyu356CWXprRPSuX6kOL5qcdGgBgiks6u+Ldku5QNLuiFI2bUIonOT4AAABq8j1Jt5vZR9z9h7XuFGZlzErqjXMyM2uTtMbdV5Z4r0vSSHiZdfe1cY4tSe4+Go6VlTTi7nEH1EeK3F2Pb3lN9z76vH75q/1acv5s9X9mmTqvOl9mVv0AAADUKenjil3h3xXu/nfjFQwAAABiuVPRjcd1Znaju/+s2g5mdrmiHlIuqa+Wk4Ti1q3hZbbE+11S1BsrvM6aWZ+7d4fXqyXNK3P4wRLFrB5376wlNkwOz7y4V3d9f4t+8sKILpt3pr7xyffr9993kU6ZQXELANA4SYtcGUnrKHABAACkx933mdktkh6RNGxmvZLudvf9xdua2RxJayStVtQbf6W7v1DjeYbD8dsUjZNVrNvdlxVsnzOzjoLXNffqCgWxnvBzJt+7C5PTzj0Hdc/GLfr+P/1a88+epf/wh7+hT37gUp16yoy0QwMATENJi1zPjGsUAAAASCSMZZUvdPVI6jGzYUXjbeUU9bzK6sTYXfkC1/fG4/xmllHpccFGzawjziOHoTDWX1DY6pA0MA5hYpztOXBYf/HYNn33xy/qtJkz9KWOxVp1fVZnzUr6vxcAANQv6VXoc5KGzGxpLd3iAQAAMHFCoatV0QzYqyQtC0uxAUWPAu4cx9NnVXoCohFFxa+ailyhl9hg+Dm/utRnQIreOnJM335yp/qe2KFDx8b0qWsv1b+5cbHOm3162qEBAJC4yHWLpJ2Kuq1vlrS5zHbu7l9IeA4AAADUKBSuuiV1Fwwsn1FUgMq5+2MTdOoWnRhwvtCoyo/DdZLwSGTNAziFccC6JGnBggW17oaEjh0f0yObXtZ9Q8/r9TcP6+b3XqA7bl6i1nPPTjs0AADekbTI1VPwc3tYSnFJFLkAAAAaKBS0JqqoNSm4e7+kfklqb29nRu8J4u4afG63ejds0Y7XD6r9srl64NNtWnZZS9qhAQBwkqRFLrqOAwAAIK9UxSMj6Y1GB4Lxs3nXXt31/V9q0669yp57lvo/s0ydV51f+DgpAACTSqIil7sz8DwAAAAkaZOiglaxFknDE3liM1suafmiRYsm8jTTTu71A1q7Yas2PPtrnTt7lu78o6t1S/slmsmMiQCASY7pTwAAAJCYu4+aWc7MMgWzIkpSJs7MignPvV7S+vb29lUTeZ7p4vU3D+sbjz2v//6Tl3T6zBn6cscV+tz1C5kxEQDQNLhiAQAAoFblBmLqlbRGYdzWMFPihBa4MH4OHj6mB5/Mqf8fczpybEz/8jcX6Is3LNa5s2elHRoAALEkKnKZ2dM1burufm2ScwAAAGByMLOsopkbOyS1mVmfpM1h8He5e7+ZdZlZh6JHF7Pu3t2AuHhcsQ5Hj4/p4adf0v1D27TnwGH97tUX6I6b3qOF889KOzQAABJh4HkAAABU5O45vXt27VLb9DconMJz8rhiAu6ujc/u1tqNW5R7/aCuvbxF/bctU9uCuWmHBgBAXZIOPF921EkzWyjp85I+7u6LkwYGAAAAYHxt3jWiO7+/RZt37dWi887Wg7e1q+PK85gxEQAwJYz7mFzuvlNSj5ldY2Zfdfevj/c5AAAAANRu+2sHtHbDFj363G6dN3uW7vr41Vq5jBkTAQBTy0QOPD8o6ZOSJqzIZWZdkkbCy6y7rx3PfcxsnbuvrD9SAAAAjDfG5KrutTcP6f6hbXr46Zd0xqmn6PaPXqHP/rOFOvM05p8CAEw9E3l1a5XUNlEHD8UquftAeJ01s75Kg5zG2SfMCrRiQoIHAABA3RiTq7wDh4+p/x9z+vaT0YyJn/ngZfriDYs072xmTAQATF1JZ1f8T1U2ySqafWc0yfFr1O3u7wyA7+65MKPPeO1TbopsAAAAYFI6enxMf/uTF/WNx7Zpz4Ej+r2rL9QdNy3R5cyYCACYBpL25Kp1SuiKs/AkZWYZle4lNmpmHe4+VM8+ZrbC3QcYgBMAAADNwN214Re/1tqNW7Vzz0Fdu7BFD972Hl3DjIkAgGkkaZFrWfVNlHP3fQmPX01WpXuJjSgqZJ1U5Kp1n/CY4nCtgYRHILskacGCBbXuBgAAAIyLn+wc0V0/+KWeeXFUi887Ww/9cbtueA8zJgIApp9ERS53f2a8A4mpRScGjy80Kmlenftk82N21cLd+yX1S1J7e7vXuh8AAADqM90Hnt/+2pvq3bBVg8/t1vlzZqn3E1frE23MmAgAmL6YVqVA/jHFtOMAAABAddN14PnX9h/SfUPb9PDTL+rM02bqjpuW6LMfWqgzTjsl7dAAAEhV6kWu8Ljfyho3X+nu+UcOSw0Mn5H0RoX9y+5jZllJuRrjAAAAABrqzUNH1fdETg89tVPHxsZ023WXM2MiAAAFKha5zGxjncd3d7+5ygbvPO4XwyZFxaliLSo/nla1fTokZYpnWzSz1ZJGQ5wAAABAQx05Nqb/9uNd+ubj2zVy8IiWL71It3/0Cl02jxkTAQAoVK0nV2edx5+QMarcfdTMcmaWKejZJUmZUjMrJt3HzHrdfe14xg4AAADUYmzMtf7nr+reR7fqpZG39Vut8/S1f/4eve+SUvdtAQBAtSJXa4JjZiX1KOoZNZF6Ja0J58rPivhOsSo8ftgraVVBUaviPgAAAGgeU3ng+ae27dHdG36pX7yyX1deOEd/89mr9duL5zNjIgAAFVQscrn7zloPZGbvV1RAWiHJFM1aeFdd0VXg7v1m1hUeL8womhWxu2CTrKJCW0uIpZZ98p+lQ1J3+HmdpL5yvb0AAACQjqk48PwvXtmn3g1b9OS2Pbo4c4buu3Wp/mDpxZoxg+IWAADV1D3wvJl9XFFxq01RcSsnqdfdH6z32NVUGicrFKXmxtmnaF+KWgAAAGiIl0be0tcf3aq//+mrypx5qv7t712pT3/wMp1+KjMmAgBQq8RFLjP7nKLH/rKKiltDiopbj41TbAAAAMCUNnLwiL71+HZ950e7ZCb9qw+36vO/06pzzjg17dAAAGg6sYpcZjZHUa+tLkWP+5mimRF74zzaCAAAAExnbx85rr/6Pzv1wD/s0MEjx7Ry2aX6cucVuuCc09MODQCAplVTkavMeFv3SLrL3fdNXHgAAADA1HHs+JgGNr+s+4ae1+79h9Vx5fnquXmJFp8/O+3QAABoehWLXGZ2g07MlNjQ8bYAAACAqcLdNfjcbq3duFXbXzugtgUZffNTbbp2YUvaoQEAMGVU68k1JMl1Yrytxyc+JAAAAKA6M1suafmiRYvSDqWiTS+M6O4fbNGmXXuVPfcsPfDpZbrpvefLjBkTAQAYT7WOydUhqSPBhdjdve4ZHAEAAIBi7r5e0vr29vZVacdSyvbX3lTvhq0afG63zp09S3f+0dW6pf0SzTxlRtqhAQAwJVUrQO1T1JMLAAAAQA127z+k+4ee18NPv6QzT5upr3ZeoT+9fqHOPI17vwAATKSKV1p3n9uoQAAAAIBmtv/QUfU9sUMPPbVTx8dct113ub54wyLNO3tW2qEBADAtcDsJAAAAqMPhY8f1nR+9qG89vk173zqqjy29SLd/dIkWzDsz7dAAAJhWKHIBAAAACYyNudb//FXds3GrXt77tj60aJ6+dvOVuvqSc9IODQCAaYkiFwAAABDTk9te190/2KJnX92vqy6co//y2at1/eL5zJgIAECKKHIBAAAANfrFK/vUu2GLnty2R5fMPUP33/p+fWzpRZoxg+IWAABpo8gFAACApmRmyyUtX7Ro0YSf66WRt3Tvo1v1P376quaeear+3e9fpU9/cIFmzTxlws8NAABqQ5ELAAAATcnd10ta397evmqizvHGgcP61g+36zs/2qVTZpi+8OFWff7DrZpz+qkTdUoAAJAQRS4AAACgyNtHjuuhp3J64Imc3jpyTLe0X6ovdVyhC845Pe3QAABAGRS5AAAAgCJHx8b00FM7dV3rPK2+aYkWnz877ZAAAEAVFLkAAACAInNOP1WDX/kdzT97VtqhAACAGs1IOwAAAABgMqLABQBAc6HIBQAAAAAAgKZHkQsAAAAAAABNjyIXAAAAAAAAmh5FLgAAAAAAADQ9ilwAAAAAAABoehS5AAAAAAAA0PQocgEAAKApmdlyM+vft29f2qEAAIBJgCIXAAAAmpK7r3f3rnPOOSftUAAAwCRAkQsAAAAAAABNjyIXAAAAAAAAmp65e9oxTBlm9rqkXWnH0WDzJe1JO4gmQ5vFR5vFR5vFR5vFNx3b7DJ3PzftIPBu5GCoEW0WH20WH20WH20Wz3Rtr5pyMIpcqIuZbXL39rTjaCa0WXy0WXy0WXy0WXy0GZAevn/x0Wbx0Wbx0Wbx0Wbx0F6V8bgiAAAAAAAAmh5FLgAAAAAAADQ9ilyoV3/aATQh2iw+2iw+2iw+2iw+2gxID9+/+Giz+Giz+Giz+GizeGivChiTCwAAAAAAAE2PnlwAAAAAAABoehS5AAAAAAAA0PRmph0Amp+ZrXP3lWnH0QzMbLWkUUkjkuTuA+lGNLmZWVf4MSNpnqS73H00xZAmHTNrk7Sm1HcwtN9IeJl197UNDW6SqqHNJGlZ+LeH37nKbVa0HdcDoIH4ztWOHCwecrDqyMHiIf+Kj/wrGYpcqEv44q1IO45mYGbrFP3BzoXXbmZz+QNeWkhG+wvbJ7Qhf8D1znfv1vAyW+L9LulEEm9mWTPrc/fuxkU5udTSZu7eX/ha0mZJrY2JcPKp1mYltuV6ADQI37nakYPFQw5WGTlYPORf8ZF/1YfHFVGvlrQDaAbhj/XT+eQqaCW5qugDJdonZ2aZVKKZZNx92N17JD1cZpPuwoQh/O51NCS4SapSm5X6vQrt12Jm07bdavg9K8T1AGgsvnM1IAdLhBysAnKweMi/4iP/qg9FLiRmZivcfSjtOJpEr6R3dYsvSrZwsmy4M1EoQ1JaXUgYittOkkanc8JQRVZSX4lkK6cqd9DA9QBoNL5zsZCDxUcOlhA5WGzkX3XgWlAaRS4kEi58w2nH0QzCH+1M+HmFmXWY2WruhlW1StLm0GVeITHoSzekppFVNO5IsRGVTrymPXcflrSsRAKfVZRooQyuB0Bj8Z2rHTlYYuRgyZGDxUD+lRzXgvIociGpLHfBapa/2GXcfSBU2/slPZZuWJNbuOi1SlpjZnsL1qG6Fp0Y7LTQqKLBY1FC8e+Xma2QlOMOWVVcD4DG4jtXO3KwBMjB6kIOFhP5V2JcC8qgyIXYQrdIZqSpXYuiu4jv/BHK362g23J5ZpZVNIjiQkUJ6WDBzCvAhAp3+ddIujHtWCYzrgdAY/Gdi40cLAFyMKSF/Ks2XAsqo8iFWMJFj4pxPDnpRFJVgG7LlfW4+1p3Hw0DLy6T1EtSWrNSg1BmJL3R6ECaVK+klYw/Uh7XA6Cx+M4lQg6WDDlYfcjBkiP/qoJrQXUz0w4ATadDUqb4Ihee2R8tnEkEEXfPmVm5t/kDXkL4/RosXOfuw2a2UlKnJLovV7ZJYQySIi3i2f2qwt+zXrqAV8X1AGgsvnMxkYPFRw5WN3KwhMi/asa1oAqKXIil1JfGzHrdfW0a8TSRYTMrfm46q+hCiNrlxF2wqtx91MxyZlY8E1KG8Q0qC49jDBR+V82sg3Y7GdcDoLH4ziVGDjY+yMFqQA6WDPlX7bgWVMfjikBj9IRF0juzYeQYxLO0cEG7tcRbKxSNDYETSnWJl6Lu3mvyL8LvHIlCpGSbhTtim/IJlpmddJdsGiv3ewYAkx05WAzkYLGQg8VD/hUf+VcC5u5px4AmFf74dCu66A1I6qPaXl6YKSQbXs4LYxygjIKBJ99QmBlJRXd4prPwPH63oi7LbYoSz82Fd3fCXbGcorbLTvc7PJXaLLy3o8yuc6fr2BC1/J6F7bgeAA3Edy4ecrB4yMEqIweLh/wrPvKv+lDkAgAAAAAAQNPjcUUAAAAAAAA0PYpcAAAAAAAAaHoUuQAAAAAAAND0KHIBAAAAAACg6VHkAgAAAAAAQNOjyAUAAAAAAICmR5ELQN3MbK+ZeZlls5l1Vdk/Y2aZRsXbKFP1cwEAgMmBHKy0qfq5AFRHkQvAeOqR1F2wrJWUkdQXEq2Tkg0zWyFpr6QHGxnoRJuqnwsAAExK5GDBVP1cAGozM+0AAEwp/e4+WrSux8x6Ja2WtFlSa+PDAgAAmNLIwQBAkrl72jEAaHJmtlfR3cK5JRKs/DZ9krokrXX3nkbGBwAAMBWRgwHAu1HkAlC3GhOsjKKu46q0HQAAAGpDDgYA78aYXAAaIiRU/eFlxUFQAQAAMD7IwQBMJxS5ADTSYPi3M7/CzNrCDEC9pdaFnzeH13vz25lZ1szWhXV7Q1f8ksxsdcExBs2so+j9cufbYWarSxwvY2Z9BTMa7Q2xdJQ6Zon9u0Ic+ZmPSm0TK6YkwufoDbF0FZy3NyzrSsUGAACaDjmYyMGA6YAiF4BGyoV/szVu3yHpsbDfgKLu+KvDRX9z2OaR8G9XmURlUFJ+fb+kdkmDFs28U+58m8L5spJ6S2z7mKI7oY8omr1oKOzbqSrMbJ2kPkktIZ6R8JlKznwUI6Yk1oSxOXoVzb7UIanD3XvC+lUhto6KRwEAAJMdORg5GDA9uDsLCwtLXYuicR5cUqbKdpmw3d6CdW1hXW+JdS6prWD9ioL1XQXrs8XHDetXF28b1u+QtDnG+daVOFdvqc9X5XN1hXWri/brKHGemmOq479bb1FcfSW2KflZWVhYWFhYWNJfyMFOfL4qn4scjIVlmiz05ALQSC3h35Eatx929+H8C3cfKPi5v+DnnKI7jcV34daE9Y+EbuGZcKeuT1KbmRXfzXzX+RTdHZRK3/U8aZ1XH8i1T1LO3dcW7Tek6A7hijpjqpmZtYV4JGlZiKO7aJv8OZ6u51wAACB15GDkYMC0MDPtAABMK/kLdq7iVidsKrO+6v4hkcove8tsli061rvO5+6jZqaidTkzG1aUDO1QlPAMFiZ/ZeLJf/ahMpsMKrpD2BY3piSKkrb2MnG1hX+HS7wHAACaBzkYORgwLVDkAtBI+fES6r1g1zL1dT6h6Ze0rsw25RK4am6U9KCihKhL0VgUOUmd4Y5mKflkZUeZ9/P7fUDRHcVGapPUU2J9p6TRCp8JAAA0B3IwcjBgWqDIBaCR8tNWl52FZxy9kxSErujjJnSJXxnuVHZIulVRstWn8gOf5uNpLfN+PiEsl4BNiIIBTUu10S06MagsAABoXuRg5GDAtMCYXAAaIsy6k5E00Ii7UiEJGlWUJEzYOdx9wN1X6sTsPuW2zd85LRfPyvBv0jubSXVKJ3Wdzyde+bEzZGYdJcaqAAAAkxw5GDkYMJ1Q5AIw4cxstaJZdnKKpkRulB5JGTM76a6lma0uM110RWHg1K4Sb7WUWFdTPOF4HYqSz0aPvdCh0ncQixOvSo8BAACASYgcrHI85GDA1MPjigDGU5eZFY7V0KqoC3l+cNFlNcx+M27cvd/MOkNc+USiRVFSkVE07kLceNol9YW7opvC/m2KPuPaSju6+9qieIbDfvmBTutKPsMgrFlJc2O0c7mxIDIKiVeYBYjZfQAAmLzIwSrHQw4GTBP05AIwnnoVda3OL6sVJSDd7t7ayOQqL3Rj7w5xdClKKIYktSa5KxbGluhUlFy1K0ogJanH3UslKsX7dxbEk993bRrtE+6ijqr0IKu9YZteSe3VZi4CAACpIgervj85GDANmLunHQMAYByY2QpJD7r73LRjAQAAmC7IwYDJg55cADB1dIqZeAAAABqNHAyYJBiTCwCmjnY1dlBZAAAAkIMBkwaPKwIAAAAAAKDp8bgiAAAAAAAAmh5FLgAAAAAAADQ9ilwAAAAAAABoehS5AAAAAAAA0PQocgEAAAAAAKDpUeQCAAAAAABA06PIBQAAAAAAgKb3/wHyhV+aVMqejwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10d080b70>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "plt.rc(\"text\", usetex=True)\n",
    "plt.figure(figsize=(20,5))\n",
    "plt.subplot(1, 2, 1)\n",
    "plt.plot(n_list, n_iters - np.array([2**n - 1 for n in n_list]), label=\"$K_t - K_{exp}$\")\n",
    "# plt.semilogy(n_list, [2**n - 1 for n in n_list], label=\"Theory\")\n",
    "plt.xlabel(\"Dimension, $n$\", fontsize=24)\n",
    "plt.ylabel(\"Number of iterations, $K$\", fontsize=24)\n",
    "plt.xticks(fontsize=18)\n",
    "plt.yticks(fontsize=18)\n",
    "plt.legend(fontsize=18)\n",
    "\n",
    "plt.subplot(1, 2, 2)\n",
    "plt.semilogy(n_list, times)\n",
    "plt.xlabel(\"Dimension, $n$\", fontsize=24)\n",
    "plt.ylabel(\"Computation time\", fontsize=24)\n",
    "plt.xticks(fontsize=18)\n",
    "_ = plt.yticks(fontsize=18)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Резюме\n",
    "\n",
    "- Задача линейного программирования\n",
    "- Приложения\n",
    "- Симплекс-метод и его сложность"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3 (cvxpy)",
   "language": "python",
   "name": "cvxpy"
  },
  "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}