jupyter_russian/tutorials/Optimization.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Обзор библиотек для решения задач оптимизации"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"../../img/Optimization_memes.png\">\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Каждый из нас повседневно сталкивается с задачами оптимизации, часто не замечая этого. В магазине мы стремимся минимизировать затраты, не теряя в количестве и качестве необходимых нам продуктов. Организуя свой день, делаем его максимально продуктивным, стараясь успеть на все мероприятия. И так далее.\n",
    "Обычно мы справляемся с этим интуитивно и самостоятельно. Но в бизнесе и в науке всё должно быть максимально точно. И здесь на помощь приходят алгоритмы оптимизации.\n",
    "В этом тьюториале представлена задача оптимизации и ее решения с помощью 3-х алгоритмов с использованием библиотек python.\n",
    "Итак, начнём."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Если говорить об определениях, то оптимизация – это целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях. \n",
    "Количественная оценка оптимизируемого качества называется  критерием оптимальности  или  целевой функцией."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Условные  задачи оптимизации, или задачи с ограничениями, – это такие задачи, при формулировке которых на значения аргументов налагаются ограничения в виде равенств или неравенств."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"../../img/Optimization_definition.png\">\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задача оптимального планирования"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Задачи оптимизации часто возникают в экономике, при планировании производственных процессов и количественной оценке альтернатив, связанных с принятием управленческих решений. Постановка этих задач обычно основана на анализе и сопоставлении расходуемых ресурсов и полученного результата. Такой подход принято называть методом “затраты - эффективность”. Применение этого подхода приводит, как правило, к двум связанным между собой типам задач: либо максимизировать эффективность при ограниченных затратах, либо обеспечивать эффективность не ниже заданной при минимальных затратах."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Такую задачу также можно назвать задачей линейного программирования (LP)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Рассмотрим пример такой задачи:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Задача взята [отсюда](http://matica.org.ua/primery/primery/zadachi-optimizatcii)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "   Металлургическому заводу требуется уголь с содержанием фосфора не более 0,03% и с долей зольных примесей не более 3,25%. Завод закупает три сорта угля A, B, C с известным содержанием примесей. В какой пропорции нужно смешивать исходные продукты А, B, C  чтобы смесь удовлетворяла ограничениям на содержание примесей и имела минимальную цену? Содержание примесей и цена исходных продуктов приведены в таблице:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"../../img/Optimization_task.png\">\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Решение:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для начала необходимо составить математическую модель задачи. Введем следующие обозначения: x1 – содержание угля A в смеси; x2 – содержание угля B в смеси; x3 – содержание угля C в смеси. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Тогда ограничения примут вид:\n",
    "- 0.06*x1 + 0.04*x2 + 0.02*x3 <= 0.03*(x1 + x2 + x3)\n",
    "- 2.0*x1 + 4.0*x2 + 3.0*x3 <= 3.25*(x1 + x2 + x3)\n",
    "- x1 + x2 + x3 = 1 \n",
    "\n",
    "А целевая функция будет:\n",
    "- f(x) = 30*x1 + 30*x2 + 45*x3 → min"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Перенесём правую часть через равно и упростим выражения, где это возможно. Таким образом, получим математическую модель нашей задачи."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Целевая функция:\n",
    "- f(x) = 30*x1 + 30*x2 + 45*x3 → min\n",
    "\n",
    "Ограничения: \n",
    "- 0.03*x1 + 0.01*x2 - 0.01*x3 <= 0\n",
    "- -1.25*x1 + 0.75*x2 - 0.25*x3 <= 0\n",
    "- x1 + x2 + x3 = 1 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Математическая модель готова, пришло время приступать к алгоритмам оптимизации. Для этого я предлагаю рассмотреть 3 библиотеки Python:\n",
    "* pulp,\n",
    "* scipy.optimize,\n",
    "* cvxopt.modeling. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для того, чтобы убедиться в верной работе алгоритма, сразу дам ответ на эту задачу."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ответ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для получения 1т угля необходимо взять 1/12т (0.0833т) первого компонента, 1/3т (0.333т) второго, 7/12т (0.583т) третьего. При этом его цена будет минимальной и составит 155/4 руб (38.75 руб)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Библиотека PuLP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Устанавливаем библиотеку:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip install pulp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "PuLP – это бесплатное программное обеспечение с открытым исходным кодом, написанное на Python. Оно используется для описания задач оптимизации, как математических моделей. Также PuLP может вызвать любой из многочисленных внешних решателей LP (CBC, GLPK, CPLEX, Gurobi и т. д.) для решения этой модели, а затем использовать команды python для управления и отображения решения."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для начала решения задачи оптимизации необходимо инициализировать переменную (например prob) с помощью функции LpProblem():\n",
    "    - prob = LpProblem(\"The Problem\", LpMinimize)\n",
    " \n",
    "Она имеет два параметра, первый из которых произвольное имя этой проблемы (в виде строки), а второй параметр либо LpMinimize или LpMaximize в зависимости от типа задачи оптимизации (минимизация/максимизация), которую вы пытаетесь решить."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Переменные задачи создаются с помощью класса LpVariable:\n",
    "\n",
    "    - x = LpVariable(\"example\", 0, None, LpInteger)\n",
    "\n",
    "Он имеет четыре параметра:\n",
    " - Первый – произвольное имя того, что представляет эта переменная;\n",
    " - Второй – нижняя граница этой переменной;\n",
    " - Третий – верхняя граница;\n",
    " - Четвертый – тип данных (дискретный или непрерывный). Значения четвертого параметра – LpContinuous или LpInteger, по умолчанию – LpContinuous. Если бы мы моделировали количество банок для производства, нам нужно было бы ввести LpInteger, так как это дискретные данные. \n",
    "\n",
    "Границы могут быть введены непосредственно как число, или None, чтобы не представлять никакой границы (т. е. положительная или отрицательная бесконечность), None стоит по умолчанию. \n",
    "\n",
    "Если первые несколько параметров введены, а остальные игнорируются, они принимают значения по умолчанию. Однако, если вы хотите указать третий параметр, но хотите, чтобы второй был значением по умолчанию, вам нужно будет специально установить второй параметр как значение по умолчанию. То есть, нельзя оставлять запись параметра пустой. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Далее, объявленная переменная prob начинает сбор данных с помощью оператора +=. Сначала вводится целевая функция с важной запятой в конце инструкции и короткой строкой, объясняющей, что это за целевая функция. Пример:\n",
    "\n",
    "    - prob += 0.013*x1 + 0.008*x2, \"Total Cost of Ingredients per can\"\n",
    "\n",
    "Затем точно также вводятся ограничения. Например:\n",
    "    - prob += x1 + x2 == 100, \"PercentagesSum\"\n",
    "    - prob += 0.100*x1 + 0.200*x2 >= 8.0, \"Requirement\"\n",
    "\n",
    "Строка в конце является необязательной."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Далее, решается задача оптимизации с помощью функции:\n",
    "    - prob.solve()\n",
    "\n",
    "Если задача решилась оптимально, то можно выводить значения найденных переменный в цикле. Для вывода на экран результата целевой функции нужно воспользоваться функцией value."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Итак, вернёмся к задачe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Напомним уже найденную математическую модель:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Целевая функция:\n",
    "- f(x) = 30*x1 + 30*x2 + 45*x3 → min\n",
    "\n",
    "Ограничения: \n",
    "- 0.03*x1 + 0.01*x2 - 0.01*x3 <= 0\n",
    "- -1.25*x1 + 0.75*x2 - 0.25*x3 <= 0\n",
    "- x1 + x2 + x3 = 1 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Код с импользованием библиотеки PuLP:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Результат:\n",
      "('x1', '=', 0.083333333)\n",
      "('x2', '=', 0.33333333)\n",
      "('x3', '=', 0.58333333)\n",
      "Цена:\n",
      "38.74999974\n",
      "Время:\n",
      "0.0930559635162\n"
     ]
    }
   ],
   "source": [
    "from pulp import *\n",
    "import time\n",
    "\n",
    "start = time.time()\n",
    "\n",
    "problem = pulp.LpProblem('0', pulp.LpMinimize)\n",
    "x1 = pulp.LpVariable(\"x1\", lowBound=0)\n",
    "x2 = pulp.LpVariable(\"x2\", lowBound=0)\n",
    "x3 = pulp.LpVariable(\"x3\", lowBound=0)\n",
    "\n",
    "problem += 30*x1 + 30*x2 + 45*x3,            'Целевая функция'\n",
    "problem += 0.03*x1 + 0.01*x2 - 0.01*x3 <= 0, '1-е ограничение'\n",
    "problem += -1.25*x1 + 0.75*x2 - 0.25*x3 <=0, '2-е ограничение'\n",
    "problem += x1 + x2 + x3 == 1,                '3-е ограничение'\n",
    "problem.solve()\n",
    "\n",
    "print (\"Результат:\")\n",
    "for variable in problem.variables():\n",
    "    print (variable.name, \"=\", variable.varValue)\n",
    "print (\"Цена:\")\n",
    "print (value(problem.objective))\n",
    "\n",
    "stop = time.time()\n",
    "print (\"Время:\")\n",
    "print(stop - start)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ответ был: Для получения 1т угля необходимо взять 1/12т (0.0833т) первого компонента, 1/3т (0.333т) второго, 7/12т (0.583т) третьего. При этом его цена будет минимальной и составит 155/4 руб (38.75 руб)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ответы сошлись! Успех!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Библиотека SciPy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Устанавливаем библиотеку:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip install scipy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "SciPy – это популярная библиотека для языка программирования Python, предназначенная\n",
    "для выполнения научных и инженерных расчётов. Библиотека включает компоненты для решения\n",
    "дифференциальных уравнений, интегрирования, обработки изображений, визуализации,\n",
    "оптимизации и многих других задач. В частности, для решения задач линейного программирования\n",
    "SciPy предлагает функцию linprog (входящую в компонент optimize)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None,\n",
    "                       bounds=None, method='simplex', callback=None,\n",
    "                       options={'disp': False,\n",
    "                                'bland': False,\n",
    "                                'tol': 1e-12,\n",
    "                                'maxiter': 1000})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Минимальное количество пораметров – один, только параметр с."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Описание параметров:\n",
    "  - c – коэффициенты целевой функции;\n",
    "  - A_ub – двумерный массив ndarray (или список списков) с коэффициентами ограничений – верхних границ («≤»);\n",
    "  - b_ub – правая часть ограничений – верхних границ;\n",
    "  - A_eq – двумерный массив ndarray (или список списков) с коэффициентами ограничений равенства;\n",
    "  - b_eq – правая часть ограничений равенства;\n",
    "  - bounds – ограничения на значения переменных. Этот параметр может принимать одну из трех форм:\n",
    "       - None – все переменные неотрицательны;\n",
    "       - (lb, ub) – если параметр представляет собой один кортеж, то все переменные должны принимать значения в диапазоне [lb; ub] включительно;\n",
    "       - [(lb_0, ub_0), (lb_1, ub_1), …] – если параметр представляет собой список, то в этом списке должно быть столько элементов, сколько переменных, и i-тый элемент списка задает диапазон значений i-той переменной;\n",
    "  - callback – функция обратного вызова, которая должна иметь сигнатуру callback(xk, kwargs), где xk – это вектор с текущим решением, а kwargs – ассоциативный массив, содержащий следующие ключи:\n",
    "       - tableau – текущая симплекс-таблица;\n",
    "       - nit – номер текущей итерации;\n",
    "       - pivot – разрешающий элемент, который будет использован для следующей итерации;\n",
    "       - phase – фаза алгоритма (функция реализует двухфазный симплекс-метод);\n",
    "       - bv – структурированный массив, содержащий строковое представление каждой переменной и ее текущего значения;\n",
    "        \n",
    "Дополнителные опции, задаваемые через параметр options:\n",
    "  - maxiter – лимит на количество итераций;\n",
    "  - disp – если True, то выводить статус в стандартный поток вывода;\n",
    "  - tol – порог, используемый при сравнении с нулем;\n",
    "  - bland – если True, то использовать алгоритм Блэнда для выбора разрешающего элемента, позволяющее избежать возможного зацикливания симплекс-метода. В противном случае, выбирается элемент, который быстрее всего приведет к нахождению решения, однако, в редких случаях не исключается возможность зацикливания."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "То есть, в пареметр A_ub мы записываем коэффиценты неравенства («≤»), в параметр A_eq коэффиценты равенства («=»). Для неравенства («≥») парметров нет, но это легко исправить, поменяв знаки коэффицентов и добавив их в пареметр A_ub."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Возвращаемым значением является объект scipy.optimize.OptimizeResult, содержащий следующие поля:\n",
    "   - fun - значение целевой функции;\n",
    "   - message – строка с описанием статуса;\n",
    "   - nit – количество произведенных итераций;\n",
    "   - slack – значения дополнительных переменных. Каждая переменная соответствует ограничению-неравенству. Нулевое значение переменной означает, что соответствующее ограничение активно.\n",
    "   - status – статус решения:\n",
    "       - 0 – поиск оптимального решения завершился успешно;\n",
    "       - 1 – достигнут лимит на число итераций;\n",
    "       - 2 – задача не имеет решений;\n",
    "       - 3 – целевая функция не ограничена.\n",
    "   - success – True, если функции удалось найти оптимальное решение;\n",
    "   - x – массив значений переменных, доставляющих максимум целевой функции."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Решаем нашу задачу:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Напомню математическую модель задачи."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Целевая функция:\n",
    "- f(x) = 30*x1 + 30*x2 + 45*x3 → min\n",
    "\n",
    "Ограничения: \n",
    "- 0.03*x1 + 0.01*x2 - 0.01*x3 <= 0\n",
    "- -1.25*x1 + 0.75*x2 - 0.25*x3 <= 0\n",
    "- x1 + x2 + x3 = 1 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Код:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "     fun: 38.749999999999993\n",
      " message: 'Optimization terminated successfully.'\n",
      "     nit: 3\n",
      "   slack: array([ 0.,  0.])\n",
      "  status: 0\n",
      " success: True\n",
      "       x: array([ 0.08333333,  0.33333333,  0.58333333])\n",
      "Время :\n",
      "0.00560903549194\n"
     ]
    }
   ],
   "source": [
    "from scipy.optimize import linprog\n",
    "import time\n",
    "\n",
    "start = time.time()\n",
    "\n",
    "c = [30,30,45]                                 # Целевая функция\n",
    "A_ub = [[0.03,0.01,-0.01],[-1.25,0.75,-0.25]]  # Коэффициенты первых 2-х функций ограничения   \n",
    "b_ub = [0,0]                                   # Результат первых 2-х функций ограничения    \n",
    "A_eq = [[1,1,1]]                               # Коэффициенты 3-й функции ограничения   \n",
    "b_eq = [1]                                     # Результат 3-й функции ограничения\n",
    "\n",
    "print (linprog(c, A_ub, b_ub, A_eq, b_eq))     # Оптимизация\n",
    "\n",
    "stop = time.time()\n",
    "print (\"Время :\")\n",
    "print(stop - start)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сравним с ответом задачи: для получения 1т угля необходимо взять 1/12т (0.0833т) первого компонента, 1/3т (0.333т) второго, 7/12т (0.583т) третьего. При этом его цена будет минимальной и составит 155/4 руб (38.75 руб)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Решено верно!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Библиотека CVXOPT"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Устанавливаем:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip install cvxopt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Библиотека CVXOPT предназначена для решения более широкого класса задач – задач\n",
    "выпуклого программирования. Соответственно, в ней используются более универсальные\n",
    "алгоритмы, за счет чего время решения аналогичных задач может оказаться несколько больше, чем\n",
    "у специализированных библиотек, реализующих разновидности симплекс-метода."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Переменные оптимизации представлены объектами, которые являются векторной величиной.\n",
    "    - cvxopt.modeling.variable([size[, name]])\n",
    "    \n",
    " - Первый аргумент – размерность вектора (положительное целое число со значением по умолчанию 1). \n",
    " - Второй аргумент – строка с именем переменной. Имя является необязательным и имеет значение по умолчанию \"\". Оно используется только при отображении переменных (или объектов, зависящих от переменных, таких как функции или ограничения) с помощью инструкций print, при вызове встроенных функций repr или str или при записи линейных программ в файлы MPS."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Целевую функцию и ограничения можно определить с помощью перегруженных операций над переменными и другими функциями. Поддерживаются три типа функций: аффинные, выпуклые кусочно-линейные и вогнутые кусочно-линейные."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Задачи оптимизации строятся вызовом следующей функции.\n",
    "    - cvxopt.modeling.op([objective[, constraints[, name]]])\n",
    "\n",
    " - Первый аргумент определяет целевую функцию, которая должна быть минимизирована. Это может быть аффинная или выпуклая кусочно-линейная функция с длиной 1, переменная с длиной 1 или скалярная константа (целое число, float или 1 на 1 плотная матрица). Значение по умолчанию – 0.0.\n",
    "\n",
    " - Второй аргумент – одно ограничение или список объектов ограничений. Значение по умолчанию – пустой список.\n",
    "\n",
    " - Третий аргумент – строка с именем задачи. Значением по умолчанию является пустая строка.\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Задача оптимизации с выпуклой кусочно-линейной задачей и ограничениями может быть решена путем вызова метода solve. Эта функция преобразует задачу оптимизации в линейную программу в матричном виде, а затем решает ее.\n",
    "\n",
    "    - solve([format[, solver]])\n",
    "\n",
    " - Первый аргумент является либо \"плотным\", либо \"разреженным\" и обозначает типы матриц. Значение по умолчанию – \"плотный\".\n",
    " - Второй аргумент – None, ' glpk 'или' mosek'. Выбирается один из трех доступных решателей LP: решатель по умолчанию, написанный на Python, решатель GLPK (если установлен) или решатель MOSEK LP (если установлен). Значение по умолчанию – None."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Решатель сообщает о результатах оптимизации, задавая атрибут self.status и путем изменения значений атрибутов переменных и множителей ограничений задачи.\n",
    "\n",
    "- Если задача решается оптимально, то self.status = 'optimal'. Значения переменных в задаче устанавливаются в их вычисляемые решения, а значения множителей ограничений задачи – в вычисляемое оптимальное решение.\n",
    " - Если определено, что проблема невыполнима, то self.status = 'primal infeasible'. Значений переменных нет. Множителям ограничений присваивается значение первичной неосуществимости. С опцией 'glpk', solve не предоставляет значений неосуществимости.\n",
    " - Если определено, что проблема двойственна, то self.status установливается в 'dual infeasible'. Значений множителей ограничений нет. Переменным устанавливаются значения двойной неосуществимости. Опять же, с опцией 'glpk', solve не предоставляет значений неосуществимости.\n",
    " - Если проблема не была решена успешно, self.status = 'unknown'. Значения переменных и множители ограничений имеют значение None."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Возвращаемся к задаче:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Исходная математическая модель:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Целевая функция:\n",
    "- f(x) = 30*x1 + 30*x2 + 45*x3 → min\n",
    "\n",
    "Ограничения: \n",
    "- 0.03*x1 + 0.01*x2 - 0.01*x3 <= 0\n",
    "- -1.25*x1 + 0.75*x2 - 0.25*x3 <= 0\n",
    "- x1 + x2 + x3 = 1 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Код с использованием библиотеки cvxopt:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Цена:\n",
      "38.75\n",
      "Результат:\n",
      "[ 8.33e-02]\n",
      "[ 3.33e-01]\n",
      "[ 5.83e-01]\n",
      "\n",
      "Время :\n",
      "0.00599002838135\n"
     ]
    }
   ],
   "source": [
    "from cvxopt.modeling import variable, op\n",
    "import time\n",
    "\n",
    "start = time.time()\n",
    "\n",
    "x = variable(3, 'x')\n",
    "z=(30*x[0] + 30*x[1] + 45*x[2])                   # Целевая функция\n",
    "mass1 = (0.03*x[0] + 0.01*x[1] - 0.01*x[2] <= 0)  # 1-е ограничение\n",
    "mass2 = (-1.25*x[0] + 0.75*x[1] - 0.25*x[2] <= 0) # 2-е ограничение\n",
    "mass3 = (x[0] + x[1] + x[2] == 1)                 # 3-е ограничение\n",
    "problem = op(z,[mass1,mass2,mass3])               # Построение задачи\n",
    "problem.solve(solver='glpk')                      # Оптимизация\n",
    "problem.status\n",
    "\n",
    "print (\"Цена:\")\n",
    "print(abs(problem.objective.value()[0]))\n",
    "print (\"Результат:\")\n",
    "print(x.value)\n",
    "\n",
    "stop = time.time()\n",
    "print (\"Время :\")\n",
    "print(stop - start)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ответ был: Для получения 1т угля необходимо взять 1/12т (0.0833т) первого компонента, 1/3т (0.333т) второго, 7/12т (0.583т) третьего. При этом его цена будет минимальной и составит 155/4 руб (38.75 руб)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Итак, алгоритм с использованием библиотеки CVXOPT также прекрасно справляется с задачей! Решено верно."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Выводы"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "||Данный ответ|Библиотека PuLP|Библиотека SciPy|Библиотека CVXOPT|\n",
    "|----|----|----|----|---|---|\n",
    "|<b>y</b>|38.74|38.74999974|38.749999999999993|38.75|\n",
    "|<b>x1</b>|0.0833|0.083333333|0.08333333|8.33e-02|\n",
    "|<b>x2</b>|0.333|0.33333333|0.33333333|3.33e-01|\n",
    "|<b>x3</b>|0.583|0.58333333|0.58333333|5.83e-01|\n",
    "|<b>Время, сек</b>|-|0.0930559635162|0.00560903549194|0.00599002838135|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как видно из таблицы, все библиотеки справились с задачей. Лучшей по времени оказалась библиотека SciPy. Но решение о применении той или иной библиотеки часто носит субъективный характер, поэтому целесообразно проводить их сравнительный анализ для области решаемых Вами задач."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Заключение"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Умение грамотно строить математическую модель ситуации и знание алгоритмов оптимизации может очень сильно пригодиться даже в бытовых вещах. Будь то планирование маршрута путешествий с наименьшими затратами и наибольшой пользой, или выбор в пользу той или иной работы. \n",
    "Стоит ещё упомянуть, что в своё время Б.А. Березовский занимался этим вопросом и даже написал не одну научную работу. Одну из самых известных Березовский написал с соавторами (с Ю. А. Барышниковым, В. И. Борзенко и Л. М. Кемпнером) \"Многокритериальная оптимизация: математические аспекты\".\n",
    "Кто знает, может быть, умение оптимизировать всё, что оптимизируется, очень сильно пригодиться Вам в жизни!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ссылки:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- [Библиотека PuLP](https://pythonhosted.org/PuLP/)\n",
    "- [Библиотека SciPy](https://docs.scipy.org/doc/scipy/reference/tutorial/optimize.html)\n",
    "- [Библиотека CVXOPT](http://cvxopt.org/userguide/modeling.html)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Если Вы нашли ошибку, или у вас есть замечания, пожалуйста, напишите мне на почту – elizavetazikeeva@gmail.com.<br/>\n",
    "Большое спасибо, что уделили своё время этому тьюториалу! :)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}