aula-02-intro-pl-padrao.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6b96a254-7f8f-41f0-b964-5eb11555d928",
   "metadata": {},
   "source": [
    "# Introdução a Programação Linear\n",
    "\n",
    "Considere o seguinte problema:\n",
    "\n",
    "<img src=\"img/modelo-pl.png\" width=\"100%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "24622bc8-02d6-46d6-9f98-bb83ac5f35f5",
   "metadata": {},
   "source": [
    "## Formas \n",
    "\n",
    "- **padrão**: todas as restrições são igualdades e todas as variáveis são não-negativas\n",
    "\n",
    "- **canônica**: todas as restrições são do tipo ≥ (se for minimização) ou do tipo ≤ (se for maximização); todas as variáveis são não-negativas\n",
    "\n",
    "<img src=\"img/forma-padrao.png\" width=\"100%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b1d00832-4407-466e-beed-922bb46f913d",
   "metadata": {},
   "source": [
    "## Transformações\n",
    "\n",
    "### Transformar equações em inequações: \n",
    "\n",
    "<img src=\"img/inequacao.png\" width=\"50%\">\n",
    "\n",
    "    Uma equação equivale a duas inequações \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c6608f12-b648-477e-b1cd-ad8af44fde2f",
   "metadata": {},
   "source": [
    "**Exemplo**\n",
    "\n",
    "<img src=\"img/inequacao-exemplo.png\" width=\"50%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b595065-0773-4166-80ef-1142135e1c67",
   "metadata": {},
   "source": [
    "#### Variáveis de Folga\n",
    "\n",
    "<img src=\"img/variavel-folga.png\" width=\"50%\">\n",
    "\n",
    "    Adicionar uma nova variável não-negativa, conhecida como variável de folga. \n",
    "    \n",
    "**Exemplo**\n",
    "\n",
    "$x_1 <= 4$\n",
    " \n",
    "$\\Downarrow$\n",
    "\n",
    "$x_1 + x_3 = 4$ e $x_3 >= 0$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee66bc49-364d-4076-a896-04100232ac00",
   "metadata": {},
   "source": [
    "#### Variáveis de Excesso\n",
    "\n",
    "<img src=\"img/variavel-excesso.png\" width=\"50%\">\n",
    "\n",
    "    Adicionar uma nova variável não-negativa, conhecida como variável de excesso. \n",
    "    \n",
    "**Exemplo**\n",
    "\n",
    "$x_1 >= 4$\n",
    " \n",
    "$\\Downarrow$\n",
    "\n",
    "$x_1 - x_3 = 4$ e $x_3 >= 0$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "846b83c1-f7ea-4e40-b731-71c12fd9bf27",
   "metadata": {},
   "source": [
    "### Transformar equações em inequações: \n",
    "\n",
    "<img src=\"img/inequacao-trasnformada.png\" width=\"50%\">\n",
    "\n",
    "    Cada inequação transformada exige uma variável de folga ou de excesso diferente.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "1dfe1fd8-433d-4ce3-b5b4-dc7dc6b84eb4",
   "metadata": {},
   "outputs": [],
   "source": [
    "// Resolva o problema de minimização acima na forma padrão utilizando o OR-Tools\n",
    "\n",
    "// Solução: x = [1.67 0 0 8.33 0] e Z = 5"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e2e342c-cc39-4cfc-be98-178c959ed84a",
   "metadata": {},
   "source": [
    "### Transformar minimização em maximização: \n",
    "\n",
    "<img src=\"img/min-max.png\" width=\"100%\">\n",
    "\n",
    "    Não esquecer que o valor da função objetivo do novo problema de maximização deve ser multiplicada por -1 para obter o valor da função objetivo do problema de minimização original.  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ee3343d-0d5f-4acf-8a56-988d9bbfb69f",
   "metadata": {},
   "source": [
    "### Transformar maximização em minimização: \n",
    "\n",
    "<img src=\"img/max-min.png\" width=\"100%\">\n",
    "\n",
    "    Não esquecer que o valor da função objetivo do novo problema de minimização deve ser multiplicada por -1 para obter o valor da função objetivo do problema de maximização original.  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9bc4e1c9-0696-47f0-854d-fe824faac055",
   "metadata": {},
   "source": [
    "### Transformar equações em inequações: \n",
    "\n",
    "<img src=\"img/inequacao-trasnformada-2.png\" width=\"50%\">\n",
    "\n",
    "    Cada inequação transformada exige uma variável de folga ou de excesso diferente.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "6b99fda5-b806-4cc4-b89b-393ada8943ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "// Resolva o problema de maximização acima na forma padrão utilizando o OR-Tools\n",
    "\n",
    "// Solução: x = [1.67 0 0] e Z' = -5"
   ]
  }
 ],
 "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": 5
}