algorithms/linear_programiing_optimization.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Линейное программирование. Практика решения задач оптимизации на Python\n",
    "\n",
    "Рассмотрим на примере максимизации прибыли характерные особенности задач линейного программирования. В качестве высокоуровневых инструментов – Python, библиотеки SciPy и PuLP.\n",
    "\n",
    "---\n",
    "\n",
    "Данная публикация представляет собой сокращенный перевод руководства Мирко Стожилковича [Hands-On Linear Programming: Optimization With Python](https://realpython.com/linear-programming-python/).\n",
    "\n",
    "---\n",
    "\n",
    "[Линейное программирование](https://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5) – это набор методов, используемых в [математическом программировании](https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5), также называемых математической оптимизацией. Эти методы используются для решения систем линейных уравнений и неравенств, перед которыми стоит цель максимизации или минимизации некоторой линейной функции – в научных вычислениях, экономике, технических науках, производстве, транспорте, военном деле, логистике, энергетике и т. д.\n",
    "\n",
    "Экосистема Python включает несколько мощных инструментов линейного программирования. Из этого туториала вы узнаете:\n",
    "- что такое линейное программирование и чем оно важно;\n",
    "- какие инструменты Python подходят для линейного программирования;\n",
    "- как построить модель и решить задачу линейного программирования на Python.\n",
    "\n",
    "\n",
    "# Что собой представляет линейное программирование\n",
    "Системы линейных уравнений и неравенств часто имеют множество возможных решений.\n",
    "\n",
    "**Линейное программирование** – это набор математических и вычислительных инструментов, позволяющих найти конкретное решение системы, которое соответствует максимуму или минимуму какой-либо другой линейной функции.\n",
    "\n",
    "**Смешанно-целочисленное линейное программирование** – это вид линейного программирования, которое фокусируется на обработке задач, где хотя бы одна переменная принимает дискретные целые, а не непрерывно меняющиеся значения.\n",
    "\n",
    "**Целочисленные переменные** важны для правильного представления количеств, естественным образом выражаемых целыми числами, таких как количество выпущенных самолетов или количество обслуженных клиентов.\n",
    "\n",
    "Особенно важным видом целочисленных переменных являются **бинарные переменные**, имеющие лишь значения `0` или `1`, и полезные при принятии решений вида **«да»** или **«нет»**. Например, следует ли строить завод, включить или выключить машину. Также их можно использовать для имитации логических ограничений.\n",
    "\n",
    "\n",
    "# В чем польза линейного программирования\n",
    "Линейное программирование – это фундаментальный метод оптимизации, десятилетиями применяемый в областях, требующих большого объема математических вычислений. Эти методы точны, сравнительно быстры и подходят для [множества практических приложений](https://www.gurobi.com/resources/?category-filter=case-study).\n",
    "\n",
    "Смешанно-целочисленное линейное программирование позволяет преодолеть многие ограничения линейного программирования. Можно аппроксимировать нелинейные функции кусочно-линейными, использовать полунепрерывные переменные, логические ограничения модели и многое другое. Это требовательный к ресурсам инструмент, но достижения в области компьютерного оборудования и программного обеспечения делают его [всё более доступным](https://sciencing.com/five-application-linear-programming-techniques-7789072.html).\n",
    "\n",
    "\n",
    "# Линейное программирование на Python\n",
    "Базовый метод решения задач линейного программирования называется [симплекс-методом](https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81-%D0%BC%D0%B5%D1%82%D0%BE%D0%B4), другой популярный подход – [метод внутренней точки](https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B2%D0%BD%D1%83%D1%82%D1%80%D0%B5%D0%BD%D0%BD%D0%B5%D0%B9_%D1%82%D0%BE%D1%87%D0%BA%D0%B8). Задачи смешанного целочисленного линейного программирования решаются с помощью более сложных и ресурсоемких методов, таких как [метод ветвей и границ](https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B2%D0%B5%D1%82%D0%B2%D0%B5%D0%B9_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86). \n",
    "\n",
    "Заметим, что почти все широко используемые библиотеки линейного программирования и смешанно-целочисленного линейного программирования написаны на языках Fortran, C или C++, так как линейное программирование требует интенсивной вычислительной работы с матрицами, часто очень большими. Соответствующие инструменты Python – это просто удобные интерфейсы для работы с низкоуровневыми библиотеками – **солверами**.\n",
    "\n",
    "В этом руководстве  для определения и решения задач линейного программирования мы будем использовать Python-библиотеки [SciPy](https://realpython.com/python-scipy-cluster-optimize/) и [PuLP](https://coin-or.github.io/pulp/).\n",
    "\n",
    "\n",
    "# 1. Примеры задач линейного программирования\n",
    "## 1.1. Небольшой показательный пример\n",
    "\n",
    "Рассмотрим следующую задачу максимизации:\n",
    "\n",
    "<img src=\"https://files.realpython.com/media/lp-py-eq-1.4c56e85a1874.png\" width=250>\n",
    "\n",
    "Нам нужно найти такие `x` и `y`, чтобы выполнялись красное, синее и желтое неравенства, а также ограничения `x ≥ 0` и `y ≥ 0`. При этом наше решение должно соответствовать максимально возможному значению `z`.\n",
    "\n",
    "Независимые переменные, которые нам нужно найти (`x` и `y`) называют **переменными решения** (decision variables). Функция, которую необходимо максимизировать или минимизировать (`z`) – это **целевая функция** (objective function), **функция стоимости** (cost function) или просто **цель** (goal). Неравенства (или уравнения), которым необходимо удовлетворять, называются **ограничениями** (inequality constraints или equality constraints для обычных уравнений).\n",
    "\n",
    "Проблему можно визуализировать следующим образом.\n",
    "\n",
    "<img src=\"https://files.realpython.com/media/lp-py-fig-1.00f609c97aec.png\" width=300>\n",
    "\n",
    "Красная линия представляет функцию `2x + y = 20`, а красная область над ней показывает, где красное неравенство не выполняется. Аналогично синяя линия – это `−4x + 5y = 10`, желтая линия – это `−x + 2y = −2`, окрашенные области – та часть плоскости, где неравенство не выполняется.\n",
    "\n",
    "Если не обращать внимания на красную, синюю и желтую области, останется только серая область. Каждая точка серой области удовлетворяет всем ограничениям и является потенциальным решением задачи. Эта область называется [областью допустимых решений](https://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D0%BB%D0%B0%D1%81%D1%82%D1%8C_%D0%B4%D0%BE%D0%BF%D1%83%D1%81%D1%82%D0%B8%D0%BC%D1%8B%D1%85_%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B9) (feasible region), а ее точки – допустимыми решениями (feasible solutions).\n",
    "\n",
    "Мы хотим максимизировать $z$. Решение, соответствующее максимальному значению $z$, называют **оптимальным решением**.\n",
    "\n",
    "Обратите внимание, что функция $z$ линейна. Оптимальное решение должно находиться в одной из вершин области допустимых решений. Иногда весь край допустимой области или даже вся область может соответствовать одному и тому же значению $z$. В этом случае у вас есть много оптимальных решений.\n",
    "\n",
    "Представим, что в задачу введено дополнительное ограничение в виде равенства, окрашенного зеленым:\n",
    "\n",
    "<img src=\"https://files.realpython.com/media/lp-py-eq-2.2984ea2b89df.png\" width=250>\n",
    "\n",
    "Его можно визуализировать, добавив соответствующую зеленую прямую:\n",
    "\n",
    "<img src=\"https://files.realpython.com/media/lp-py-fig-2.3d21c2b24205.png\" width=300>\n",
    "\n",
    "Теперь область допустимых решений не соответствует всей серой зоне. Это лишь часть зеленой линии, проходящей через серую область от точки пересечения с синей линией до точки пересечения с красной линией.\n",
    "\n",
    "Если же добавляется требование, что все значения `x` должны быть целыми числами, то мы получим задачу линейного программирования со смешанными целыми числами, и набор возможных решений снова изменится:\n",
    "\n",
    "<img src=\"https://files.realpython.com/media/lp-py-fig-3.c13d0660ce57.png\" width=300>\n",
    "\n",
    "Больше нет зеленой линии – только дискретные точки, где значение $x$ является целым числом. Возможные решения – это зеленые точки на сером фоне.\n",
    "\n",
    "Эти три примера иллюстрируют задачи линейного программирования – они имеют ограниченные допустимые области решений и конечные решения.\n",
    "\n",
    "Когда ни одно решение не может удовлетворить все ограничения сразу, задача в рамках линейного программирования неразрешима. \n",
    "\n",
    "\n",
    "## 1.2. Проблема распределения ресурсов\n",
    "В предыдущих разделах мы рассмотрели абстрактную задачу линейного программирования, не связанную с каким-либо реальным приложением. В этом разделе речь пойдет о более практической задачи оптимизации, связанной с распределением ресурсов на производстве.\n",
    "\n",
    "Предположим, что фабрика производит четыре различных продукта, ежедневное количество первого продукта составляет `x_1`, второго продукта – `x_2` и т. д. Цель – определить максимальную прибыль ежедневного объема производства для каждого продукта с учетом следующих условий:\n",
    "\n",
    "1. Прибыль (profit) на единицу продукта составляет 20, 12, 40 и 25 долларов для каждого из четырех продуктов соответственно.\n",
    "2. Из-за нехватки рабочей силы (manpower) общее количество единиц, производимых в день, не может превышать 50.\n",
    "3. На каждую единицу 1-го продукта расходуется 3 единицы сырья A. Каждая единица 2-го продукта требует 2 единиц сырья A и 1 единицы сырья B. Каждой единице 3-го продукта требуется 1 единица A и 2 единицы B. Наконец, каждая единица 4-го продукта требует трех единиц. B.\n",
    "4. Из-за ограничений по транспортировке и хранению фабрика может потреблять до 100 единиц сырья A и 90 единиц B в день.\n",
    "\n",
    "Математическую модель можно определить так:\n",
    "\n",
    "<img src=\"https://files.realpython.com/media/lp-py-eq-4.0178c4cfe357.png\" width=300>\n",
    "\n",
    "Целевая функция (прибыль) определяется в условии 1. Ограничение рабочей силы следует из условия 2. Ограничения на сырье A и B могут быть получены из условий 3 и 4 путем суммирования потребностей в сырье для каждого продукта. Наконец, количество продуктов не может быть отрицательным.\n",
    "\n",
    "В отличие от предыдущего примера, эту задачу не так удобно визуализировать, потому как она имеет четыре переменных. Однако принципы остаются теми же.\n",
    "\n",
    "\n",
    "# 2. Линейное программирование на Python. Практическая реализация\n",
    "\n",
    "В этом руководстве мы будем использовать для решения описанной выше задачи линейного программирования два пакета Python :\n",
    "\n",
    "- `SciPy` – универсальный пакет для научных вычислений с Python. Его внутренний пакет [scipy.optimize](https://docs.scipy.org/doc/scipy/reference/optimize.html) можно использовать как для линейной, так и для нелинейной оптимизации.\n",
    "- `PuLP` –  API линейного программирования Python для определения задачи и вызова солверов. По умолчанию в качестве солвера используется [COIN-OR Branch and Cut Solver](https://github.com/coin-or/Cbc) (CBC). Еще один отличный солвер с открытым исходным кодом – [GNU Linear Programming Kit (GLPK)](https://www.gnu.org/software/glpk/).\n",
    "\n",
    "## 2.1. Установка SciPy и PuLP\n",
    "\n",
    "Чтобы следовать этому руководству, вам необходимо установить SciPy и PuLP. В приведенных примерах используется версия SciPy `1.4.1` и PuLP `2.1`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already up-to-date: scipy in /home/leo/anaconda3/lib/python3.7/site-packages (1.5.4)\n",
      "Requirement already up-to-date: pulp in /home/leo/anaconda3/lib/python3.7/site-packages (2.3.1)\n",
      "Requirement already satisfied, skipping upgrade: numpy>=1.14.5 in /home/leo/anaconda3/lib/python3.7/site-packages (from scipy) (1.19.4)\n",
      "Requirement already satisfied, skipping upgrade: amply>=0.1.2 in /home/leo/anaconda3/lib/python3.7/site-packages (from pulp) (0.1.4)\n",
      "Requirement already satisfied, skipping upgrade: docutils>=0.3 in /home/leo/anaconda3/lib/python3.7/site-packages (from amply>=0.1.2->pulp) (0.15.2)\n",
      "Requirement already satisfied, skipping upgrade: pyparsing in /home/leo/anaconda3/lib/python3.7/site-packages (from amply>=0.1.2->pulp) (2.4.7)\n"
     ]
    }
   ],
   "source": [
    "!python -m pip install -U scipy pulp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Возможно, вам потребуется запустить `pulptest` или `sudo pulptest`, чтобы включить солверы PuLP, особенно если вы используете Linux или Mac:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solver <class 'pulp.apis.coin_api.PULP_CBC_CMD'> available\n",
      "Solver <class 'pulp.apis.cplex_api.CPLEX_DLL'> unavailable\n",
      "Solver <class 'pulp.apis.cplex_api.CPLEX_CMD'> unavailable\n",
      "Solver <class 'pulp.apis.cplex_api.CPLEX_PY'> unavailable\n",
      "Solver <class 'pulp.apis.coin_api.COIN_CMD'> unavailable\n",
      "Solver <class 'pulp.apis.coin_api.COINMP_DLL'> unavailable\n",
      "Solver <class 'pulp.apis.glpk_api.GLPK_CMD'> unavailable\n",
      "Solver <class 'pulp.apis.xpress_api.XPRESS'> unavailable\n",
      "Solver <class 'pulp.apis.gurobi_api.GUROBI'> unavailable\n",
      "Solver <class 'pulp.apis.gurobi_api.GUROBI_CMD'> unavailable\n",
      "Solver <class 'pulp.apis.glpk_api.PYGLPK'> unavailable\n",
      "Solver <class 'pulp.apis.coin_api.YAPOSIB'> unavailable\n",
      "Solver <class 'pulp.apis.choco_api.PULP_CHOCO_CMD'> available\n",
      "Solver <class 'pulp.apis.choco_api.CHOCO_CMD'> unavailable\n",
      "Solver <class 'pulp.apis.mipcl_api.MIPCL_CMD'> unavailable\n",
      "Solver <class 'pulp.apis.mosek_api.MOSEK'> unavailable\n",
      "Solver <class 'pulp.apis.scip_api.SCIP_CMD'> unavailable\n",
      "\t Testing invalid status\n",
      ".\t Testing continuous LP solution - export dict\n",
      ".\t Testing MIP solution\n",
      ".\t Testing maximize continuous LP solution\n",
      ".\t Testing continuous LP solution - export JSON\n",
      ".\t Testing continuous LP solution - export solver dict\n",
      ".\t Testing continuous LP solution - export solver JSON\n",
      "..\t Testing makeDict general behavior\n",
      ".\t Testing makeDict default value behavior\n",
      ".\t Testing the availability of the function pulpTestAll\n",
      ".\t Testing zero subtraction\n",
      ".\t Testing inconsistent lp solution\n",
      ".\t Testing continuous LP solution\n",
      ".\t Testing maximize continuous LP solution\n",
      ".\t Testing unbounded continuous LP solution\n",
      ".\t Testing Long Names\n",
      ".\t Testing repeated Names\n",
      ".\t Testing zero constraint\n",
      ".\t Testing zero objective\n",
      ".\t Testing LpVariable (not LpAffineExpression) objective\n",
      ".\t Testing Long lines in LP\n",
      ".\t Testing LpAffineExpression divide\n",
      ".\t Testing MIP solution\n",
      ".\t Testing MIP solution with floats in objective\n",
      ".\t Testing MIP solution\n",
      ".\t Testing MIP solution\n",
      ".\t Testing MIP relaxation\n",
      ".\t Testing feasibility problem (no objective)\n",
      ".\t Testing an infeasible problem\n",
      ".\t Testing an integer infeasible problem\n",
      ".\t Testing another integer infeasible problem\n",
      ".\t Testing column based modelling\n",
      "..\t Testing dual variables and slacks reporting\n",
      "...\t Testing fractional constraints\n",
      ".\t Testing elastic constraints (no change)\n",
      ".\t Testing elastic constraints (freebound)\n",
      ".\t Testing elastic constraints (penalty unchanged)\n",
      ".\t Testing elastic constraints (penalty unbounded)\n",
      "..\t Testing invalid status\n",
      ".\t Testing continuous LP solution - export dict\n",
      ".\t Testing MIP solution\n",
      ".\t Testing maximize continuous LP solution\n",
      ".\t Testing continuous LP solution - export JSON\n",
      ".\t Testing continuous LP solution - export solver dict\n",
      ".\t Testing continuous LP solution - export solver JSON\n",
      "..\t Testing makeDict general behavior\n",
      ".\t Testing makeDict default value behavior\n",
      ".\t Testing the availability of the function pulpTestAll\n",
      ".\t Testing zero subtraction\n",
      ".\t Testing inconsistent lp solution\n",
      ".\t Testing continuous LP solution\n",
      ".\t Testing maximize continuous LP solution\n",
      ".\t Testing unbounded continuous LP solution\n",
      ".\t Testing Long Names\n",
      ".\t Testing repeated Names\n",
      ".\t Testing zero constraint\n",
      ".\t Testing zero objective\n",
      ".\t Testing LpVariable (not LpAffineExpression) objective\n",
      "..\t Testing LpAffineExpression divide\n",
      ".\t Testing MIP solution\n",
      ".\t Testing MIP solution with floats in objective\n",
      ".\t Testing MIP solution\n",
      ".\t Testing MIP solution\n",
      ".\t Testing MIP relaxation\n",
      "/home/leo/anaconda3/lib/python3.7/site-packages/pulp/apis/choco_api.py:83: UserWarning: CHOCO_CMD cannot solve the relaxation of a problem\n",
      "  warnings.warn(\"CHOCO_CMD cannot solve the relaxation of a problem\")\n",
      ".\t Testing feasibility problem (no objective)\n",
      ".\t Testing an infeasible problem\n",
      ".\t Testing an integer infeasible problem\n",
      ".\t Testing another integer infeasible problem\n",
      ".\t Testing column based modelling\n",
      ".....\t Testing fractional constraints\n",
      ".\t Testing elastic constraints (no change)\n",
      ".\t Testing elastic constraints (freebound)\n",
      ".\t Testing elastic constraints (penalty unchanged)\n",
      ".\t Testing elastic constraints (penalty unbounded)\n",
      "...................{'a': 53.0, 'b': 45.3, 'c': 459.2}\n",
      "..........................\n",
      "----------------------------------------------------------------------\n",
      "Ran 129 tests in 21.977s\n",
      "\n",
      "OK\n"
     ]
    }
   ],
   "source": [
    "!pulptest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "---\n",
    "\n",
    "**Примечание переводчика**. При желании вы можете таже использовать GLPK. Это бесплатный солвер с открытым исходным кодом, который работает в Windows, MacOS и Linux. О том, как с ним работать в PuLP рассказано в [оригинальной публикации](https://realpython.com/linear-programming-python/). В переводе мы ограничимся доступным по умолчанию солвером CBC.\n",
    "\n",
    "---\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.2. Использование SciPy\n",
    "\n",
    "В этом разделе мы рассмотрим, как использовать библиотеку SciPy [по оптимизации и поиску корней](https://docs.scipy.org/doc/scipy/reference/optimize.html) для линейного программирования. Начнём с импорта `scipy.optimize.linprog()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.optimize import linprog"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.3. Решение первого примера c помощью SciPy\n",
    "\n",
    "Начнём с решения первого (дополненного) примера\n",
    "\n",
    "<img src=\"https://files.realpython.com/media/lp-py-eq-2.2984ea2b89df.png\" width=250>\n",
    "\n",
    "`linprog()` решает только задачи минимизации (не максимизации) и не допускает ограничений-неравенств со знаком больше или равно (`≥`). Чтобы обойти эти проблемы, нам необходимо изменить описание задачи перед запуском оптимизации:\n",
    "\n",
    "- Вместо максимизации `z = x + 2y` минимизируем отрицательное значение (`−z = −x − 2y`).\n",
    "- Вместо знака `≥` мы можем умножить «желтое» неравенство на `-1` и получить противоположный знак (ограничения по осям рассмотрим далее).\n",
    "\n",
    "<img src=\"https://files.realpython.com/media/lp-py-eq-3.65b2e6d529bc.png\" width=250>\n",
    "\n",
    "На следующем шаге определяем входные значения:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "obj = [-1, -2]\n",
    "#      ─┬  ─┬\n",
    "#       │   └┤ Коэффициент для y\n",
    "#       └────┤ Коэффициент для x\n",
    "\n",
    "lhs_ineq = [[ 2,  1],  # левая сторона красного неравенства\n",
    "            [-4,  5],  # левая сторона синего неравенства\n",
    "            [ 1, -2]]  # левая сторона желтого неравенства\n",
    "\n",
    "rhs_ineq = [20,  # правая сторона красного неравенства\n",
    "            10,  # правая сторона синего неравенства\n",
    "             2]  # правая сторона желтого неравенства\n",
    "\n",
    "lhs_eq = [[-1, 5]]  # левая сторона зеленого равенства\n",
    "rhs_eq = [15]       # правая сторона зеленого равенства"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Мы поместили значения из системы в соответствующие списки:\n",
    "- `obj` содержит коэффициенты целевой функции,\n",
    "- `lhs_ineq` и `rhs_ineq` содержат коэффициенты из ограничений-неравенств,\n",
    "- `lhs_eq` и `rhs_eq` содержат коэффициенты из ограничивающего уравнения.\n",
    "\n",
    "---\n",
    "**Примечание**. Будьте осторожны с порядком строк и столбцов!\n",
    "\n",
    "Порядок строк для левой и правой сторон ограничений должен быть одинаковым. Каждая строка представляет одно ограничение. Порядок коэффициентов целевой функции и левых частей ограничений должен совпадать. Каждый столбец соответствует одной переменной решения.\n",
    "\n",
    "---\n",
    "\n",
    "Следующим шагом является определение границ каждой переменной. В данном случае они находятся между нулем и положительной бесконечностью:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "bnd = [(0, float(\"inf\")),  # Границы x\n",
    "       (0, float(\"inf\"))]  # Границы y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Однако эти границы совпадают с установленными по умолчанию в `linprog()`.\n",
    "\n",
    "Наконец, пришло время оптимизировать и решить интересующую нас проблему:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "     con: array([0.])\n",
       "     fun: -16.818181818181817\n",
       " message: 'Optimization terminated successfully.'\n",
       "     nit: 3\n",
       "   slack: array([ 0.        , 18.18181818,  3.36363636])\n",
       "  status: 0\n",
       " success: True\n",
       "       x: array([7.72727273, 4.54545455])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "opt = linprog(c=obj, A_ub=lhs_ineq, b_ub=rhs_ineq,\n",
    "              A_eq=lhs_eq, b_eq=rhs_eq, bounds=bnd,\n",
    "              method=\"revised simplex\")\n",
    "\n",
    "opt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Параметр `c` относится к коэффициентам из целевой функции. `A_ub` и `b_ub` соответственно связаны с коэффициентами из левой и правой частей ограничений-неравенств. Точно так же `A_eq` и `b_eq` относятся к ограничениям уравнений. Параметр `bounds` служит для указания нижней и верхней границ переменных решения.\n",
    "\n",
    "Параметр `method` определяет используемый алгоритм линейного программирования. Доступны три варианта:\n",
    "- по умолчанию используется метод внутренней точки: [method = \"inner-point\"](https://docs.scipy.org/doc/scipy/reference/optimize.linprog-interior-point.html),\n",
    "- измененный двухфазный симплекс-метод [method=\"revised simplex\"](https://docs.scipy.org/doc/scipy/reference/optimize.linprog-revised_simplex.html)\n",
    "- симплекс-метод [method=\"simplex\"](https://docs.scipy.org/doc/scipy/reference/optimize.linprog-simplex.html)\n",
    "\n",
    "`linprog()` возвращает структуру данных со следующими атрибутами:\n",
    "- `.con` – остатки ограничения-равенства;\n",
    "- `.fun` – оптимальное значение целевой функции (если найдено);\n",
    "- `.message` – словесный статус решения;\n",
    "- `.nit` – количество итераций, необходимых для завершения расчета;\n",
    "- `.slack` – значения так называемых дополнительных переменных – разниц между значениями левой и правой сторонами ограничений;\n",
    "- `.status` – целое число от 0 до 4, отражающих результат решения: например, 0, когда было найдено оптимальное решение;\n",
    "- `.success` – логическое значение, показывающее, найдено ли оптимальное решение;\n",
    "- `.x` – массив NumPy, содержащий оптимальные значения переменных решения.\n",
    "\n",
    "Доступ к атрибутам можно получить по отдельности:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-16.818181818181817"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "opt.fun"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "opt.success"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([7.72727273, 4.54545455])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "opt.x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Графически результат можно отобразить следующим образом.\n",
    "\n",
    "<img src=\"https://files.realpython.com/media/lp-py-fig-5.11f20dcc5d6b.png\" width=400>\n",
    "\n",
    "Вначале наша задача органичивалась только неравенствами. Если удалить параметры зеленого уравнения `A_eq` и `b_eq` из вызова `linprog()`, получим следующий результат:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "     con: array([], dtype=float64)\n",
       "     fun: -20.714285714285715\n",
       " message: 'Optimization terminated successfully.'\n",
       "     nit: 2\n",
       "   slack: array([0.        , 0.        , 9.85714286])\n",
       "  status: 0\n",
       " success: True\n",
       "       x: array([6.42857143, 7.14285714])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "opt = linprog(c=obj, A_ub=lhs_ineq, b_ub=rhs_ineq, bounds=bnd,\n",
    "              method=\"revised simplex\")\n",
    "\n",
    "opt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://files.realpython.com/media/lp-py-fig-4.8a846634edca.png\" width=400>\n",
    "\n",
    "## 2.4. Решение задачи о производстве с помощью SciPy\n",
    "\n",
    "Рассмотрим теперь решение второй задачи – о продуктах, рабочей силе и используемом сырье.\n",
    "\n",
    "<img src=\"https://files.realpython.com/media/lp-py-eq-4.0178c4cfe357.png\" width=300>\n",
    "\n",
    "Как и в предыдущем примере, нам нужно извлечь необходимые векторы и матрицу из задачи, передать их в качестве аргументов в `linprog()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "     con: array([], dtype=float64)\n",
       "     fun: -1900.0\n",
       " message: 'Optimization terminated successfully.'\n",
       "     nit: 2\n",
       "   slack: array([ 0., 40.,  0.])\n",
       "  status: 0\n",
       " success: True\n",
       "       x: array([ 5.,  0., 45.,  0.])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "obj = [-20, -12, -40, -25]\n",
    "\n",
    "lhs_ineq = [[1, 1, 1, 1],  # Рабочая сила\n",
    "            [3, 2, 1, 0],  # Материал A\n",
    "            [0, 1, 2, 3]]  # Материал B\n",
    "\n",
    "rhs_ineq = [ 50,  # Рабочая сила\n",
    "            100,  # Материал A\n",
    "             90]  # Материал B\n",
    "\n",
    "opt = linprog(c=obj, A_ub=lhs_ineq, b_ub=rhs_ineq,\n",
    "              method=\"revised simplex\")\n",
    "\n",
    "opt\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Максимальная прибыль составляет `1900` и соответствует `x_1 = 5` и `x_3 = 45`. В данных условиях производить второй и четвертый продукты невыгодно. Результат позволяет сделать несколько интересных выводов:\n",
    "1. Третий продукт приносит наибольшую прибыль.\n",
    "2. Первая дополнительная переменная (`slack`) равна 0. Это означает, что равны значения левой и правой сторон ограничения для рабочей силы. Завод производит 50 единиц в день, и это его полная мощность.\n",
    "3. Вторая дополнительная переменная равна 40: фабрика потребляет 60 единиц сырья A (15 единиц для первого продукта и 45 для третьего) из возможных 100 единиц.\n",
    "4. Третья дополнительная переменная равен 0: фабрика потребляет все 90 единиц сырья B. При этом все это количество потребляется для производства третьего продукта. Вот почему фабрика вообще не может производить второй или четвертый товар и не может произвести более 45 единиц третьего товара. Cырья B просто не хватает.\n",
    "\n",
    "Возможности линейного программирования SciPy полезны в основном для небольших задач. Для более крупных и сложных проблем разумно использовать другие библиотеки:\n",
    "- SciPy не поддерживает работу с целочисленными переменными решения.\n",
    "- SciPy не подразумевает запуск внешних солверов.\n",
    "- SciPy не предоставляет классы или функции для построения моделей. Определять массивы и матрицы вручную для крупных задач слишком утомительно.\n",
    "- Также вручную приходится переопределять задачи, как мы это сделали выше.\n",
    "\n",
    "\n",
    "## 2.5. Решение первой задачи на линейное программирование с помощью PuLP\n",
    "\n",
    "PuLP имеет более удобный API линейного программирования, чем SciPy. Начнем с импорта."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pulp import LpMaximize, LpProblem, LpStatus, lpSum, LpVariable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Первый шаг – инициализировать экземпляр `LpProblem` для описания модели:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "model = LpProblem(name=\"small-problem\", sense=LpMaximize)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Параметр `sense` определяет, решаем ли мы задачу минимизации (параметр `LpMinimize` или `1`, установлен по умолчанию) или максимизации (`LpMaximize` или `-1`).\n",
    "\n",
    "Создав модель, мы можем определить переменные решения как экземпляры класса `LpVariable`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = LpVariable(name=\"x\", lowBound=0)\n",
    "y = LpVariable(name=\"y\", lowBound=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Значения границ по умолчанию – отрицательная и положительная бесконечности, поэтому в нашем случае необходимо указать нижнюю границу (`lowBound = 0`).\n",
    "\n",
    "Необязательный параметр `cat` определяет категорию переменной решения. При работе с непрерывными переменными можно использовать значение по умолчанию `\"Continuous\"`.\n",
    "\n",
    "Переменные `x` и `y` теперь можно использовать для создания других PuLP-объектов, представляющих линейные выражения и ограничения:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'pulp.pulp.LpAffineExpression'>\n",
      "<class 'pulp.pulp.LpConstraint'>\n"
     ]
    }
   ],
   "source": [
    "expression = 2 * x + 4 * y\n",
    "print(type(expression))\n",
    "constraint = 2 * x + 4 * y >= 8\n",
    "print(type(constraint))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Построив линейную комбинацию нескольких переменных решения, мы получаем экземпляр `pulp.LpAffineExpression`, представляющий линейное выражение. Выражения можно комбинировать с операторами `==`, `<=` и `>=` и получать экземпляры `pulp.LpConstraint` – линейные ограничения вашей модели.\n",
    "\n",
    "Опишем теперь ограничения. В отличие от SciPy, с PuLP не нужно создавать списки и матрицы. Просто записываем выражения Python и добавляем в модель с помощью оператора `+=`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "model += (2 * x + y <= 20, \"red_constraint\")\n",
    "model += (4 * x - 5 * y >= -10, \"blue_constraint\")\n",
    "model += (-x + 2 * y >= -2, \"yellow_constraint\")\n",
    "model += (-x + 5 * y == 15, \"green_constraint\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`LpProblem` позволяет добавлять ограничения в модель, определяя их как кортежи. Первый элемент кортежа – `экземпляр LpConstraint`, второй – его удобочитаемое имя.\n",
    "\n",
    "Аналогично описывается целевая функция:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "obj_func = x + 2 * y\n",
    "model += obj_func"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Теперь можно посмотреть полное определение модели:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "small-problem:\n",
       "MAXIMIZE\n",
       "1*x + 2*y + 0\n",
       "SUBJECT TO\n",
       "red_constraint: 2 x + y <= 20\n",
       "\n",
       "blue_constraint: 4 x - 5 y >= -10\n",
       "\n",
       "yellow_constraint: - x + 2 y >= -2\n",
       "\n",
       "green_constraint: - x + 5 y = 15\n",
       "\n",
       "VARIABLES\n",
       "x Continuous\n",
       "y Continuous"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Строковое представление модели содержит все соответствующие данные: цель, переменные, ограничения и их имена.\n",
    "\n",
    "Теперь мы готовы решить проблему. Достаточно лишь вызвать метод `.solve()` для объекта модели."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "status = model.solve()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Метод `.solve()` вызывает базовый солвер, изменяет объект модели и возвращает целочисленный статус решения, равный `1`, если найден оптимум. Остальные коды состояний описаны в [документации](https://www.coin-or.org/PuLP/constants.html#pulp.constants.LpStatus).\n",
    "\n",
    "Результаты оптимизации доступны в виде атрибутов модели:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "status: 1, Optimal\n",
      "objective: 16.8181817\n",
      "x: 7.7272727\n",
      "y: 4.5454545\n",
      "red_constraint: -9.99999993922529e-08\n",
      "blue_constraint: 18.181818300000003\n",
      "yellow_constraint: 3.3636362999999996\n",
      "green_constraint: -2.0000000233721948e-07\n"
     ]
    }
   ],
   "source": [
    "print(f\"status: {model.status}, {LpStatus[model.status]}\")\n",
    "\n",
    "print(f\"objective: {model.objective.value()}\")\n",
    "\n",
    "for var in model.variables():\n",
    "    print(f\"{var.name}: {var.value()}\")\n",
    "    \n",
    "for name, constraint in model.constraints.items():\n",
    "    print(f\"{name}: {constraint.value()}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`model.objective` содержит значение целевой функции, `model.constraints` – значения дополнительных переменных, а объекты `x` и `y` имеют оптимальные значения переменных решения.\n",
    "\n",
    "Результаты получились примерно такие же, как у SciPy.\n",
    "\n",
    "Чтобы получить смешанно-целочисленное решение, достаточно обозначить это при помощи параметра `cat`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Создаем модель\n",
    "model = LpProblem(name=\"small-problem\", sense=LpMaximize)\n",
    "\n",
    "# Инициализируем переменные решения: x - целое число, y меняется непрерывно\n",
    "x = LpVariable(name=\"x\", lowBound=0, cat=\"Integer\")\n",
    "y = LpVariable(name=\"y\", lowBound=0)\n",
    "\n",
    "# Добавляем ограничения\n",
    "model += (2 * x + y <= 20, \"red_constraint\")\n",
    "model += (4 * x - 5 * y >= -10, \"blue_constraint\")\n",
    "model += (-x + 2 * y >= -2, \"yellow_constraint\")\n",
    "model += (-x + 5 * y == 15, \"green_constraint\")\n",
    "\n",
    "# Добавляем целевую функцию\n",
    "# Вариант добавления через lpSum\n",
    "model += lpSum([x, 2 * y])\n",
    "\n",
    "# Решаем задачу оптимизации\n",
    "status = model.solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "status: 1, Optimal\n",
      "objective: 15.8\n",
      "x: 7.0\n",
      "y: 4.4\n",
      "red_constraint: -1.5999999999999996\n",
      "blue_constraint: 16.0\n",
      "yellow_constraint: 3.8000000000000007\n",
      "green_constraint: 0.0\n"
     ]
    }
   ],
   "source": [
    "print(f\"status: {model.status}, {LpStatus[model.status]}\")\n",
    "\n",
    "print(f\"objective: {model.objective.value()}\")\n",
    "\n",
    "for var in model.variables():\n",
    "    print(f\"{var.name}: {var.value()}\")\n",
    "    \n",
    "for name, constraint in model.constraints.items():\n",
    "    print(f\"{name}: {constraint.value()}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<pulp.apis.coin_api.PULP_CBC_CMD at 0x7f48363b3710>"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "model.solver"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Теперь `x` – целое число, как указано в модели. Этот факт меняет решение. Покажем это на графике:\n",
    "\n",
    "<img src=\"https://files.realpython.com/media/lp-py-fig-6.a415a074213b.png\" width=400>\n",
    "\n",
    "Как видите, оптимальным решением является крайняя правая зеленая точка на сером фоне. Это решение с наибольшими значениями как `x`, так и `y`, дающее максимальное значение целевой функции.\n",
    "\n",
    "## 2.6. Решение задачи о производстве с помощью PuLP\n",
    "\n",
    "Подход к определению и решению проблемы такой же, как и в предыдущем примере:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "status: 1, Optimal\n",
      "objective: 1900.0\n",
      "x1: 5.0\n",
      "x2: 0.0\n",
      "x3: 45.0\n",
      "x4: 0.0\n",
      "manpower: 0.0\n",
      "material_a: -40.0\n",
      "material_b: 0.0\n"
     ]
    }
   ],
   "source": [
    "# Определяем модель\n",
    "model = LpProblem(name=\"resource-allocation\", sense=LpMaximize)\n",
    "\n",
    "# Описываем переменные\n",
    "x = {i: LpVariable(name=f\"x{i}\", lowBound=0) for i in range(1, 5)}\n",
    "\n",
    "# Добавляем ограничения\n",
    "model += (lpSum(x.values()) <= 50, \"manpower\")\n",
    "model += (3 * x[1] + 2 * x[2] + x[3] <= 100, \"material_a\")\n",
    "model += (x[2] + 2 * x[3] + 3 * x[4] <= 90, \"material_b\")\n",
    "\n",
    "# Описываем цель\n",
    "model += 20 * x[1] + 12 * x[2] + 40 * x[3] + 25 * x[4]\n",
    "\n",
    "# Решаем задачу оптимизации\n",
    "status = model.solve()\n",
    "\n",
    "# Выводим результаты решения\n",
    "print(f\"status: {model.status}, {LpStatus[model.status]}\")\n",
    "print(f\"objective: {model.objective.value()}\")\n",
    "\n",
    "for var in x.values():\n",
    "    print(f\"{var.name}: {var.value()}\")\n",
    "\n",
    "for name, constraint in model.constraints.items():\n",
    "    print(f\"{name}: {constraint.value()}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как видите, решение согласуется с тем, что мы молучили с помощью SciPy. Наиболее выгодное решение – производить в день 5 единиц первого продукта и 45 единиц третьего.\n",
    "\n",
    "Давайте сделаем задачу более сложной и интересной. Допустим, из-за проблем с оборудованием, фабрика не может производить первую и третью продукцию параллельно. Какое решение  наиболее выгодно в этом случае?\n",
    "\n",
    "Теперь у нас есть еще одно логическое ограничение: если `x_1` положительно, то `x_3` должно равняться нулю, и наоборот. Здесь очень полезны переменные бинарного решения. Введем две двоичные переменные решения `y_1` и `y_3`, которые будут обозначать, генерируются ли вообще первый или третий продукты:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "status: 1, Optimal\n",
      "objective: 1800.0\n",
      "x1: 0.0\n",
      "x2: 0.0\n",
      "x3: 45.0\n",
      "x4: 0.0\n",
      "y1: 0.0\n",
      "y3: 1.0\n",
      "manpower: -5.0\n",
      "material_a: -55.0\n",
      "material_b: 0.0\n",
      "x1_constraint: 0.0\n",
      "x3_constraint: -55.0\n",
      "y_constraint: 0.0\n"
     ]
    }
   ],
   "source": [
    "model = LpProblem(name=\"resource-allocation\", sense=LpMaximize)\n",
    "\n",
    "x = {i: LpVariable(name=f\"x{i}\", lowBound=0) for i in range(1, 5)}\n",
    "y = {i: LpVariable(name=f\"y{i}\", cat=\"Binary\") for i in (1, 3)}\n",
    "\n",
    "model += (lpSum(x.values()) <= 50, \"manpower\")\n",
    "model += (3 * x[1] + 2 * x[2] + x[3] <= 100, \"material_a\")\n",
    "model += (x[2] + 2 * x[3] + 3 * x[4] <= 90, \"material_b\")\n",
    "\n",
    "M = 100\n",
    "model += (x[1] <= y[1] * M, \"x1_constraint\")\n",
    "model += (x[3] <= y[3] * M, \"x3_constraint\")\n",
    "model += (y[1] + y[3] <= 1, \"y_constraint\")\n",
    "\n",
    "model += 20 * x[1] + 12 * x[2] + 40 * x[3] + 25 * x[4]\n",
    "\n",
    "status = model.solve()\n",
    "\n",
    "print(f\"status: {model.status}, {LpStatus[model.status]}\")\n",
    "print(f\"objective: {model.objective.value()}\")\n",
    "\n",
    "for var in model.variables():\n",
    "    print(f\"{var.name}: {var.value()}\")\n",
    "\n",
    "for name, constraint in model.constraints.items():\n",
    "    print(f\"{name}: {constraint.value()}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "При таких условиях оказывается, что оптимальный подход – исключить первый продукт вовсе и производить только третий.\n",
    "\n",
    "# Заключение\n",
    "Теперь вы в общих чертах представляете, с какими задачами имеет дело линейное программирование и как использовать Python для решения подобных задач. \n",
    "\n",
    "Теперь – после прохождения этого руководства – вы умеете:\n",
    "- определить модель, которая описывает вашу задачу в SciPy и PuLP;\n",
    "- создать программу Python для оптимизационной задачи;\n",
    "- запустить программу оптимизации, чтобы найти решение задачи;\n",
    "- получить результат оптимизации.\n",
    "\n",
    "Если вы хотите узнать больше о линейном программировании, вот несколько отправных точек, с которых можно начать:\n",
    "-   [Русскоязычная](https://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5) и [анлоязычная](https://en.wikipedia.org/wiki/Linear_programming) вики-страницы \n",
    "-   [Русскоязычная](https://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BB%D0%BE%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5) и [англоязычная](https://en.wikipedia.org/wiki/Integer_programming) вики-страницы о целочисленном программировании\n",
    "-   [Туториал на Brilliant.org](https://brilliant.org/wiki/linear-programming/)\n",
    "-   Вводный курс MIT [о математическом программировании](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-251j-introduction-to-mathematical-programming-fall-2009/)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}