aula-01-intro-po.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Introdução a Pesquisa Operacional\n",
    "Pesquisa Operacional (PO) é o uso do métodos científicos para auxiliar a tomada de decisões. \n",
    "\n",
    "## Caracteriza-se por:\n",
    "- emprego de matemática “avançada”\n",
    "- aplicação em problemas reais\n",
    "- multidisciplinaridade, envolve conceitos vindos de várias áreas, incluindo:\n",
    "    - Matemática e Estatística\n",
    "    - Engenharia e Computação\n",
    "    - Administração e Economia"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Outras Definições\n",
    "“Operations research is the application of advanced analytical methods to help make better decisions.”\n",
    "\n",
    "    Informs: http://www.informs.org/About-INFORMS/About-Operations-Research\n",
    "\n",
    "“A Pesquisa Operacional é uma ciência aplicada voltada para a resolução de problemas reais.\"\n",
    "- Tendo como foco a tomada de decisões, aplica conceitos e métodos de várias áreas científicas na concepção, planejamento ou operação de sistemas. \n",
    "- A Pesquisa Operacional é usada para avaliar linhas de ação alternativas e encontrar as soluções que melhor servem aos objetivos dos indivíduos ou organizações.\n",
    "\n",
    "    SOBRAPO: https://www.sobrapo.org.br/o-que-e-pesquisa-operacional"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Precursores da Pesquisa Operacional\n",
    "\n",
    "A partir do século XVII, muitos matemáticos clássicos criaram ferramentas que podem ser aplicadas no auxílio à decisão:\n",
    "\n",
    "- Newton, Leibniz, Taylor, Lagrange: **Cálculo diferencial para achar mínimos/máximos de funções**.\n",
    "- Cardano, Pascal, Huygens, Bayes, Poisson: **Cálculo de probabilidades**.\n",
    "- Euler, Kirchhoff, Hamilton: **Teoria dos grafos, fluxos em redes, Otimização combinatória**.\n",
    "- Gauss, Fourier: **Sistemas de equações lineares**.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Histórico da Pesquisa Operacional\n",
    "\n",
    "- 1936 criação da Bawdsey Manor Research Station em Suffolk, Inglaterra: **estudo do uso de radares para interceptar aeronaves inimigas**\n",
    "- 1937 o termo **Operations Research** foi cunhado por A. P. Rowe na BMRS\n",
    "- 1939 Leonid V. Kantorovich modelou e propôs métodos de solução para diversos problemas de planejamento na União Soviética\n",
    "- 1940 (WWII) criado **The Anti-Aircraft Research Group** na força aérea britânica (3 fisiologistas, 1 físico geral, 2 físicos matemáticos, 2 matemáticos, 1 astrofísico, 1 oficial do exército e 1 topógrafo)\n",
    "- 1941 primeira definição formal do **Problema Clássico de Transporte** por Frank L. Hitchcock\n",
    "- 1942 formação da **U.S. Navy Antisubmarine Warfare Operations Research Group** (ASWORG)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- 1943-1945 diversos grupos apoiando o planejamento logístico (abastecimento) das tropas aliadas, estratégias de ataque e defesa aérea e marítima, etc.\n",
    "- 1945 ao final da WWII é criado o projeto **RAND** para trabalhar no planejamento militar e em problemas do governo norte americano\n",
    "- 1947 George B. Dantzig formalizou a **Otimização Linear** e criou o método **Simplex** para solução de problemas deste tipo na USAF\n",
    "- 1951 ocorreu o primeiro uso de **um modelo de otimização linear na indústria**: problema da mistura (blend) ótima nas refinarias de petróleo.\n",
    "- 1950-1960 estabelecimento das primeiras sociedades de profissionais de PO nos EUA e na Europa e o começo do ensino de PO nas universidades."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## A PO na Atualidade\n",
    "\n",
    "- Usada rotineiramente por empresas e organizações nos mais diversos setores da indústria, serviços, finanças ou governo.\n",
    "\n",
    "- A PO contribui significativamente para a eficiência da economia mundial\n",
    "    - Tradicionalmente a PO tem sido usada para minimizar custos e/ou maximizar lucros\n",
    "\n",
    "- Atualmente também existem outras preocupações:\n",
    "    - minimizar impactos ecológicos e riscos de acidentes\n",
    "    - maximizar benefícios sociais"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Entretanto, a PO ainda é muito menos usada do que poderia!**\n",
    "\n",
    "- Conflitos com outras culturas empresariais\n",
    "\n",
    "- Disputas políticas (decisão = poder)\n",
    "\n",
    "- Dificuldades em obter dados confiáveis\n",
    "\n",
    "- Dificuldades em aplicar adequadamente as técnicas de PO aos problemas complexos do mundo real!\n",
    "\n",
    "    - O uso avançado de PO é uma técnica, mas também é uma arte.\n",
    "\n",
    "    - Existe escassez de profissionais experientes com essa competência."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## No que consiste a PO?\n",
    "\n",
    "**A PO está baseada na construção de modelos matemáticos para representar de forma simplificada os sistemas reais.**\n",
    "\n",
    "<img src=\"img/Picture1.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Para que serve um modelo?\n",
    "\n",
    "- Um modelo é útil quando permite que se chegue a conclusões adequadas sobre o sistema real, dentro de seu limite de aplicabilidade.\n",
    "\n",
    "- Como a PO trabalha com modelos matemáticos, a utilidade de um modelo também depende da existência de métodos matemático-computacionais capazes de resolver o modelo.\n",
    "\n",
    "- Um modelo de otimização matemática é definido por um sistema de equações/inequações.\n",
    "    - As **variáveis** representam as decisões a serem tomadas.\n",
    "    - As equações/inequações representam as **restrições** que existem sobre essas decisões, refletindo as características do sistema real.\n",
    "    - Uma **função objetivo** indica qual dentre as possíveis decisões é a mais desejável (solução ótima).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## O que é um problema de otimização?\n",
    "\n",
    "O objetivo da otimização é encontrar a melhor solução para um problema dentre um grande conjunto de soluções possíveis. \n",
    "\n",
    "```Às vezes, você ficará satisfeito em encontrar qualquer solução viável; Mas será bem melhor se o COMPUTADOR puder fazer isso para você.```\n",
    "\n",
    "### Aqui está um problema típico de otimização. \n",
    "\n",
    "    Suponha que uma empresa de remessa entregue pacotes a seus clientes usando uma frota de caminhões. Todos os dias, a empresa deve atribuir pacotes aos caminhões e, em seguida, escolher uma rota para cada caminhão entregar seus pacotes. Cada atribuição possível de pacotes e rotas tem um custo, com base na distância total de viagem dos caminhões e possivelmente em outros fatores. O problema é escolher as atribuições de pacotes e rotas com o menor custo."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Como todos os problemas de otimização, esse problema possui os seguintes elementos:\n",
    "\n",
    "- O objetivo - a quantidade que você deseja otimizar. No exemplo acima, o objetivo é minimizar o custo. \n",
    "\n",
    "    Para configurar um problema de otimização, você precisa definir uma função que calcule o valor do objetivo para qualquer solução possível. Isso é chamado de função objetivo . No exemplo anterior, a função objetivo calcularia o custo total de qualquer atribuição de pacotes e rotas. \n",
    "\n",
    "```Uma solução ideal é aquela para a qual o valor da função objetivo é o melhor. (\"Melhor\" pode ser no máximo ou no mínimo.)```\n",
    "\n",
    "- As restrições - restrições ao conjunto de soluções possíveis, com base nos requisitos específicos do problema. Por exemplo, se a transportadora não puder atribuir pacotes acima de um determinado peso aos caminhões, isso imporia uma restrição às soluções. Uma solução viável é aquela que satisfaz todas as restrições dadas para o problema, sem necessariamente ser ideal.\n",
    "\n",
    "    O primeiro passo para resolver um problema de otimização é identificar o objetivo e as restrições."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Resolvendo um problema de otimização em C ++\n",
    "\n",
    "A seguir, damos um exemplo de um problema de otimização e mostramos como configurá-lo e resolvê-lo em C++.\n",
    "\n",
    "#### Um exemplo de otimização linear\n",
    "\n",
    "Uma das áreas de otimização mais antigas e mais usadas é a otimização linear, na qual a função objetivo e as restrições podem ser escritas como expressões lineares. Aqui está um exemplo simples desse tipo de problema.\n",
    "\n",
    "#### Maximize $3x + y$, sujeito às seguintes restrições:\n",
    "$\n",
    "\\begin{align}\n",
    "\\\\0 \\le x \\le 1\n",
    "\\\\0 \\le y \\le 2\n",
    "\\\\x + y \\le2\n",
    "\\end{align}\n",
    "$\n",
    "\n",
    "A função objetivo neste exemplo é $3x + y$ . Tanto a função objetivo quanto as restrições são dadas por expressões lineares, o que torna um problema linear.\n",
    "\n",
    "As restrições definem a região viável, que é o triângulo mostrado abaixo, incluindo seu interior.\n",
    "<img style=\"float: center;\" src=\"https://developers.google.com/optimization/images/lp/feasible_region.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Principais etapas na solução do problema\n",
    "\n",
    "As etapas básicas para configurar e resolver um problema de otimização são as seguintes:\n",
    "\n",
    "1. Escolha o solver.\n",
    "2. Crie as variáveis.\n",
    "3. Defina as restrições.\n",
    "4. Defina a função objetivo.\n",
    "5. Execute o solver e exiba os resultados."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Exemplo de Programa C++\n",
    "\n",
    "Vamos começar mostrando como montar o problema em C++ passo-a-passo. \n",
    "\n",
    "Aqui estão as etapas para montar e resolver o problema no C++:\n",
    "\n",
    "**0. Incluir as bibliotecas**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "#include \"setup.h\"\n",
    "#include \"ortools/linear_solver/linear_solver.h\"\n",
    "#include \"ortools/linear_solver/linear_solver.pb.h\"\n",
    "\n",
    "using namespace operations_research;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**1. Escolha o solver.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "MPSolver solver(\"programa_simples\", MPSolver::GLOP_LINEAR_PROGRAMMING);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**2. Crie as variáveis.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Número de variáveis = 2\n"
     ]
    }
   ],
   "source": [
    "auto const x = solver.MakeNumVar(0.0, 1, \"x\");\n",
    "auto const y = solver.MakeNumVar(0.0, 2, \"y\");\n",
    "std::cout << \"Número de variáveis = \" << solver.NumVariables() << std::endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**3. Defina as restrições.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Número de restrições = 1\n"
     ]
    }
   ],
   "source": [
    "auto const ct = solver.MakeRowConstraint(0.0, 2.0, \"ct\");\n",
    "ct->SetCoefficient(x, 1);\n",
    "ct->SetCoefficient(y, 1);\n",
    "\n",
    "std::cout << \"Número de restrições = \" << solver.NumConstraints() << std::endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**4. Defina a função objetivo.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "auto const objective = solver.MutableObjective();\n",
    "objective->SetCoefficient(x, 3);\n",
    "objective->SetCoefficient(y, 1);\n",
    "objective->SetMaximization();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**5. Execute o solver e exiba os resultados.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solução:\n",
      "Valor da função objetivo = 4\n",
      "x = 1\n",
      "y = 1\n"
     ]
    }
   ],
   "source": [
    "solver.Solve();\n",
    "\n",
    "std::cout << \"Solução:\" << std::endl;\n",
    "std::cout << \"Valor da função objetivo = \" << objective->Value() << std::endl;\n",
    "std::cout << \"x = \" << x->solution_value() << std::endl;\n",
    "std::cout << \"y = \" << y->solution_value() << std::endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## O programa completo\n",
    "\n",
    "O programa completo é mostrado abaixo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "#include \"setup.h\"\n",
    "#include \"ortools/linear_solver/linear_solver.h\"\n",
    "#include \"ortools/linear_solver/linear_solver.pb.h\"\n",
    "\n",
    "using namespace operations_research;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Número de variáveis = 2\n",
      "Número de restrições = 1\n",
      "Solução:\n",
      "Valor da função objetivo = 4\n",
      "x = 1\n",
      "y = 1\n"
     ]
    }
   ],
   "source": [
    "{\n",
    "  // 1. Escolha o solver.\n",
    "  MPSolver solver(\"programa_simples\", MPSolver::GLOP_LINEAR_PROGRAMMING);\n",
    "\n",
    "  // 2. Crie as variáveis: x e y.\n",
    "  auto const x = solver.MakeNumVar(0.0, 1, \"x\");\n",
    "  auto const y = solver.MakeNumVar(0.0, 2, \"y\");\n",
    "\n",
    "  std::cout << \"Número de variáveis = \" << solver.NumVariables() << std::endl;\n",
    "\n",
    "  // 3. Defina as restrições: 0 <= x + y <= 2.\n",
    "  auto const ct = solver.MakeRowConstraint(0.0, 2.0, \"ct\");\n",
    "  ct->SetCoefficient(x, 1);\n",
    "  ct->SetCoefficient(y, 1);\n",
    "\n",
    "  std::cout << \"Número de restrições = \" << solver.NumConstraints() << std::endl;\n",
    "\n",
    "  // 4. Defina a função objetivo: 3 * x + y.\n",
    "  auto const objective = solver.MutableObjective();\n",
    "  objective->SetCoefficient(x, 3);\n",
    "  objective->SetCoefficient(y, 1);\n",
    "  objective->SetMaximization();\n",
    "\n",
    "  // 5. Execute o solver e exiba os resultados.\n",
    "  solver.Solve();\n",
    "\n",
    "  std::cout << \"Solução:\" << std::endl;\n",
    "  std::cout << \"Valor da função objetivo = \" << objective->Value() << std::endl;\n",
    "  std::cout << \"x = \" << x->solution_value() << std::endl;\n",
    "  std::cout << \"y = \" << y->solution_value() << std::endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Otimização Linear\n",
    "\n",
    "Como você acabou de aprender, um problema de otimização linear é aquele em que a função objetivo e as expressões das restrições são lineares nas suas variáveis. O solucionador primário no OR-Tools para esse tipo de problema é o solucionador de otimização linear, que na verdade é um invólucro para várias bibliotecas diferentes de otimização linear e de otimização inteira, incluindo bibliotecas de terceiros.\n",
    "\n",
    "> Métodos de solução extremamente eficazes, problemas com milhões de variáveis e restrições podem ser resolvidos num laptop\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Otimização Inteira\n",
    "\n",
    "Um problema de otimização inteira, além de linear, é aquele em que algumas ou todas as variáveis **precisam ser números inteiros**. Um exemplo é o problema de alocação, no qual um grupo de trabalhadores precisa ser alocado a um conjunto de tarefas. Para cada trabalhador e tarefa, você define uma variável cujo valor é 1 se o trabalhador especificado estiver atribuído à tarefa especificada e 0 no caso contrário. Nesse caso, as variáveis **podem assumir apenas os valores 0 ou 1**.\n",
    "\n",
    "> Métodos de solução bem menos eficazes, problemas com alguns milhares de variáveis e restrições já podem ser intratáveis\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Otimização Não-Linear\n",
    "\n",
    "Na Otimização Não-Linear as restrições e/ou a função objetivo podem ser funções não-lineares.\n",
    "\n",
    "> Métodos de solução eficazes apenas para alguns casos particulares (ex: funções quadráticas, funções convexas). Problemas envolvendo funções mais complicadas com algumas dezenas de variáveis e restrições já podem ser intratáveis.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Empacotamento\n",
    "\n",
    "O problema de empacotamento (ou da mochila) é o problema de embalar um conjunto de objetos de tamanhos diferentes em recipientes com diferentes capacidades. O objetivo é embalar o maior número possível de objetos, de acordo com as capacidades dos compartimentos. Um caso especial disso é o problema da mochila, no qual há apenas um compartimento."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Fluxos de rede\n",
    "\n",
    "Muitos problemas de otimização podem ser representados por um grafo direcionado que consiste em nós conectados por arcos direcionados. Por exemplo, problemas de transporte, nos quais as mercadorias são enviadas através de uma rede ferroviária, podem ser representados por um grafo no qual os arcos são linhas ferroviárias e os nós são centros de distribuição. No problema de fluxo máximo, cada arco possui uma capacidade máxima que pode ser transportada através dele. O problema é atribuir a quantidade de mercadorias a serem transportadas em cada arco, para que a quantidade total sendo transportada seja a maior possível."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Atribuição de Tarefa\n",
    "\n",
    "Os problemas de atribuição envolvem a atribuição de um grupo de agentes (digamos, trabalhadores ou máquinas) a um conjunto de tarefas, onde existe um custo fixo para atribuir cada agente a uma tarefa específica. O problema é encontrar a atribuição com o menor custo total. Os problemas de atribuição são, na verdade, um caso especial de problemas de fluxo de rede."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Agendamento\n",
    "\n",
    "Os problemas de agendamento envolvem a atribuição de recursos para executar um conjunto de tarefas em horários específicos. Um exemplo importante é o problema da oficina, no qual vários trabalhos são processados em várias máquinas. Cada trabalho consiste em uma sequência de tarefas, que devem ser executadas em uma determinada ordem, e cada tarefa deve ser processada em uma máquina específica. O problema é atribuir uma agenda para que todos os trabalhos sejam concluídos no menor intervalo de tempo possível."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Roteamento\n",
    "\n",
    "Os problemas de roteamento envolvem encontrar as rotas ideais para uma frota de veículos atravessar uma rede, definida por um gráfico direcionado. O problema de atribuir pacotes a caminhões de entrega, descrito acima, é um exemplo de um problema de roteamento. Outro exemplo famoso é o problema do vendedor ambulante."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++14",
   "language": "C++14",
   "name": "xcpp14"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}