<commit_before>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(DUALIDAD)="
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4.4 Dualidad"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Notas para contenedor de docker:\n",
    "\n",
    "Comando de docker para ejecución de la nota de forma local:\n",
    "\n",
    "nota: cambiar `<ruta a mi directorio>` por la ruta de directorio que se desea mapear a `/datos` dentro del contenedor de docker.\n",
    "\n",
    "`docker run --rm -v <ruta a mi directorio>:/datos --name jupyterlab_optimizacion_2 -p 8888:8888 -p 8787:8787 -d palmoreck/jupyterlab_optimizacion_2:3.0.0`\n",
    "\n",
    "password para jupyterlab: `<PASSWORD>`\n",
    "\n",
    "Detener el contenedor de docker:\n",
    "\n",
    "`docker stop jupyterlab_optimizacion_2`\n",
    "\n",
    "Documentación de la imagen de docker `palmoreck/jupyterlab_optimizacion_2:3.0.0` en [liga](https://github.com/palmoreck/dockerfiles/tree/master/jupyterlab/optimizacion_2).\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Al final de esta nota el y la lectora:\n",
    ":class: tip\n",
    "\n",
    "*\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ejemplo prototipo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Considérese el problema planteado en {ref}`ejemplo prototipo <EJPROTOTIPO>` con sus suposiciones. El objetivo es elegir los valores de $x_1, x_2$ que maximicen $f_o$, la ganancia total, sujeta a las restricciones impuestas sobre sus valores por las capacidades de producción limitadas disponibles en las tres plantas. Esto es, resolver el PL siguiente:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\displaystyle \\max_{x \\in \\mathbb{R}^2} 3x_1 + 5x_2$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\text{sujeto a: }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$x_1 \\leq 4$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$2x_2 \\leq 12$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$3x_1 + 2x_2 \\leq 18$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$x_1 \\geq 0, x_2 \\geq 0$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El término $3x_1$ representa la ganancia generada (en miles de pesos) cuando se fabrica el producto 1 a una tasa de $x_1$ lotes por semana. Se tienen contribuciones individuales de cada producto a la ganancia. Se desea determinar cuáles tasas de producción (no negativas) deben tener los dos productos con el fin de maximizar la ganancia total sujeta a las restricciones impuestas por las capacidades de producción limitadas disponibles en las tres plantas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La región factible y el valor óptimo del PL anterior es:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "tags": [
     "hide-input"
    ]
   },
   "outputs": [
    {
     "data": {
      "image/png": "<KEY>//<KEY>",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "#x_1 ≤ 4\n",
    "\n",
    "point1_x_1 = (4,0)\n",
    "\n",
    "point2_x_1 = (4, 10)\n",
    "\n",
    "point1_point2_x_1 = np.row_stack((point1_x_1, point2_x_1))\n",
    "\n",
    "#x_1 ≥ 0\n",
    "point3_x_1 = (0,0)\n",
    "\n",
    "point4_x_1 = (0, 10)\n",
    "\n",
    "point3_point4_x_1 = np.row_stack((point3_x_1, point4_x_1))\n",
    "\n",
    "#2x_2 ≤ 12 or x_2 ≤ 6\n",
    "\n",
    "point1_x_2 = (0, 6)\n",
    "\n",
    "point2_x_2 = (8, 6)\n",
    "\n",
    "point1_point2_x_2 = np.row_stack((point1_x_2, point2_x_2))\n",
    "\n",
    "#x_2 ≥ 0\n",
    "\n",
    "point3_x_2 = (0, 0)\n",
    "\n",
    "point4_x_2 = (8, 0)\n",
    "\n",
    "point3_point4_x_2 = np.row_stack((point3_x_2, point4_x_2))\n",
    "\n",
    "#3x_1 + 2x_2 ≤ 18\n",
    "\n",
    "x_1_region_1 = np.linspace(0,4, 100)\n",
    "\n",
    "x_2_region_1 = 1/2*(18 - 3*x_1_region_1)\n",
    "\n",
    "\n",
    "x_1 = np.linspace(0,6, 100)\n",
    "\n",
    "x_2 = 1/2*(18 - 3*x_1)\n",
    "\n",
    "plt.plot(point1_point2_x_1[:,0], point1_point2_x_1[:,1],\n",
    "         point3_point4_x_1[:,0], point3_point4_x_1[:,1],\n",
    "         point1_point2_x_2[:,0], point1_point2_x_2[:,1],\n",
    "         point3_point4_x_2[:,0], point3_point4_x_2[:,1],\n",
    "         x_1, x_2)\n",
    "plt.scatter(2, 6, marker='o', s=150,\n",
    "            facecolors='none', edgecolors='b')\n",
    "plt.legend([\"$x_1 = 4$\", \"$x_1 = 0$\", \n",
    "            \"$2x_2 = 12$\", \"$x_2 = 0$\",\n",
    "            \"$3x_1+2x_2 = 18$\", \"(óptimo, valor óptimo)\"], bbox_to_anchor=(1, 1))\n",
    "\n",
    "plt.fill_between(x_1_region_1, 0, x_2_region_1, where=x_2_region_1<=6, color=\"plum\")\n",
    "x_1_region_2 = np.linspace(0,2, 100)\n",
    "plt.fill_between(x_1_region_2, 0, 6, color=\"plum\")\n",
    "plt.title(\"Región factible del PL\")\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Definición\n",
    "\n",
    "Asociado a todo problema de programación lineal existe otro problema lineal con nombre **dual**. Al problema \"original\" se le nombra **primal**.\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Observación\n",
    ":class: tip\n",
    "\n",
    "Realmente no importa a cuál de los problemas se le dé el nombre primal y a cuál el de dual. La convención es que el modelo que se formula para representar el problema real recibe el nombre de problema primal no importando la forma que tiene (estándar u otra).\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El problema **primal** anterior escrito en notación vectorial y matricial es:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\displaystyle \\max_{x \\in \\mathbb{R}^2} (-c)^Tx$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\text{sujeto a: }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$Ax \\leq b$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$x \\geq 0$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "donde: $\n",
    "A= \n",
    "\\left [\n",
    "\\begin{array}{cc}\n",
    "1 & 0 \\\\\n",
    "0 & 2 \\\\\n",
    "3 & 2 \\\\\n",
    "\\end{array}\n",
    "\\right ], x=\n",
    "\\left [\n",
    "\\begin{array}{c}\n",
    "x_1 \\\\\n",
    "x_2 \\\\\n",
    "\\end{array}\n",
    "\\right ], b=\n",
    "\\left[\n",
    "\\begin{array}{c}\n",
    "4 \\\\\n",
    "12 \\\\\n",
    "18\n",
    "\\end{array}\n",
    "\\right ]$ y \n",
    "$c = \\left [ \\begin{array}{c} -3 \\\\ -5 \\end{array}\\right]$ representa al vector de costos unitarios o equivalentemente $-c$ el vector de ganancias unitarias. La última desigualdad se refiere a que todas las componentes del vector $x$ son mayores o iguales a cero. El PL busca maximizar $f_o(x) = -c^Tx$, la ganancia total."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{margin}\n",
    "$\n",
    "\\displaystyle \\max_{x \\in \\mathbb{R}^2} 3x_1 + 5x_2 \\\\\n",
    "\\text{sujeto a: }       \\\\\n",
    "x_1 \\leq 4 \\nonumber    \\\\\n",
    "2x_2 \\leq 12            \\\\\n",
    "3x_1 + 2x_2 \\leq 18     \\\\\n",
    "x_1 \\geq 0              \\\\\n",
    "x_2 \\geq 0              \\\\\n",
    "$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Comentario\n",
    "\n",
    "En el contexto del PL ejemplo se tiene:\n",
    "\n",
    "$f_o$: ganancia total debida a todas las actividades (función objetivo). En el ejemplo es la ganancia semanal total (en miles de pesos) que generan los productos $1$ y $2$.\n",
    "\n",
    "$x_j$: nivel de la actividad $j$ con $j=1, 2, \\dots, n$ (variables de optimización primales). En el ejemplo $n=2$. $x_1$ es el número de lotes del producto $1$ que se fabrican por semana (análogamente $x_2$).\n",
    "\n",
    "$c_j$: costo unitario debido a la actividad j con $j=1, 2, \\dots, n$ ($-c_j$ es la ganancia unitaria).\n",
    "\n",
    "$b_i$: cantidad disponible del recurso $i$ para asignarse a las actividades con $i=1, 2, \\dots, m$. En el ejemplo $m=3$. $b_1=4$ representa el número de horas de producción disponibles por semana en la planta $1$ para fabricar los lotes de los productos $1$ y $2$.\n",
    "\n",
    "$a_{ij}$: cantidad del recurso $i$ consumido por cada unidad de la actividad $j$ con $i=1, 2, \\dots n$, $j=1, 2, \\dots m$. En el ejemplo se consumen $3$ horas para producir el producto $1$ y $2$ horas para el $2$ de las $18$ horas disponibles en la planta $3$.\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El problema **dual** asociado al problema anterior es:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{margin}\n",
    "\n",
    "Por ahora tómese como válida la expresión del problema dual, en esta primera parte se busca señalar las relaciones existentes con el problema primal y no la forma matemática de obtenerlo.\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\displaystyle \\min_{\\lambda \\in \\mathbb{R}^3} (-\\lambda)^T b$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\text{sujeto a: }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$A^T(-\\lambda) \\geq -c$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$-\\lambda \\geq 0$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Que escrito con escalares es:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\displaystyle \\min_{\\lambda \\in \\mathbb{R}^3} -4\\lambda_1 -12 \\lambda_2 -18 \\lambda_3$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\text{sujeto a: }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$-\\lambda_1 -3 \\lambda_3 \\geq 3$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$-2 \\lambda_2 - 2 \\lambda_3 \\geq 5$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$-\\lambda_1 \\geq 0, -\\lambda_2 \\geq 0, -\\lambda_3 \\geq 0$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{margin}\n",
    "\n",
    "Forma estándar de un PL:\n",
    "\n",
    "$\n",
    "\\displaystyle \\min_{x \\in \\mathbb{R}^n} c^Tx\\\\\n",
    "\\text{sujeto a:} \\\\\n",
    "Ax=b\\\\\n",
    "x \\geq 0\n",
    "$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En su forma aumentada (que en este ejemplo corresponde a la estándar de los PL) es:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\displaystyle \\min_{\\lambda \\in \\mathbb{R}^3} -4\\lambda_1 -12 \\lambda_2 -18 \\lambda_3$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$-\\lambda_1 -3 \\lambda_3 + \\lambda_4 = 3$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$-2 \\lambda_2 - 2 \\lambda_3 + \\lambda_5 = 5$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$-\\lambda_1 \\geq 0, -\\lambda_2 \\geq 0, -\\lambda_3 \\geq 0, -\\lambda_4 \\geq 0, -\\lambda_5 \\geq 0$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{margin}\n",
    "$\n",
    "\\displaystyle \\max_{x \\in \\mathbb{R}^2} 3x_1 + 5x_2       \\\\\n",
    "x_1 \\leq 4 \\nonumber    \\\\\n",
    "2x_2 \\leq 12            \\\\\n",
    "3x_1 + 2x_2 \\leq 18     \\\\\n",
    "x_1 \\geq 0              \\\\\n",
    "x_2 \\geq 0              \\\\\n",
    "$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{margin}\n",
    "\n",
    "$\n",
    "\\displaystyle \\min_{\\lambda \\in \\mathbb{R}^3} -4\\lambda_1 -12 \\lambda_2 -18 \\lambda_3\\\\\n",
    "\\text{sujeto a: } \\\\\n",
    "-\\lambda_1 -3 \\lambda_3 \\geq 3\\\\\n",
    "-2 \\lambda_2 - 2 \\lambda_3 \\geq 5 \\\\\n",
    "-\\lambda_1 \\geq 0 \\\\\n",
    "-\\lambda_2 \\geq 0 \\\\\n",
    "-\\lambda_3 \\geq 0\n",
    "$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Comentarios\n",
    "\n",
    "* El problema dual usa exactamente los mismos parámetros del problema primal pero en diferentes lugares:\n",
    "\n",
    "    * Los coeficientes de la función objetivo del problema primal son los lados derechos de las restricciones funcionales del problema dual.\n",
    "    \n",
    "    * Los lados derechos de las restricciones funcionales del problema primal son los coeficientes de la función objetivo del problema dual.\n",
    "    \n",
    "    * Los coeficientes de una variable de las restricciones funcionales del problema primal son los coeficientes de una restricción funcional del problema dual. Por ejemplo: de las restricciones funcionales $x_1 \\leq 4$, $2x_2 \\leq 12$ y $3x_1 + 2x_2 \\leq 18$ del problema primal los coeficientes de $x_1$ son $1, 0, 3$ respectivamente, en el problema dual se tienen estos mismos coeficientes para la restricción funcional:$-\\lambda_1 -3 \\lambda_3 \\geq 3$ (recuérdese que la variable del problema dual en su forma no estándar es $-\\lambda$). \n",
    "\n",
    "\n",
    "* Las variables $-\\lambda_4, -\\lambda_5$ son variables consideradas de **superávit**, ***surplus variables***, (obsérvese la diferencia con las variables de holgura).\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Interpretación del problema dual"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Considérese las siguientes formas de los modelos de optimización primal-dual para el problema del inicio:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\begin{align*}\n",
    "\\displaystyle \\max_{x \\in \\mathbb{R}^2} 3x_1 + 5x_2 \n",
    "&& &&\n",
    "\\displaystyle \\min_{\\lambda \\in \\mathbb{R}^3} -4\\lambda_1 -12 \\lambda_2 -18 \\lambda_3\\\\\n",
    "\\text{sujeto a: }       && &&  \\text{sujeto a: }\\\\\n",
    "x_1 \\leq 4 \\nonumber    && &&  -\\lambda_1 -3 \\lambda_3 \\geq 3\\\\\n",
    "2x_2 \\leq 12            && && -2 \\lambda_2 - 2 \\lambda_3 \\geq 5 \\\\\n",
    "3x_1 + 2x_2 \\leq 18     && && -\\lambda_1 \\geq 0 \\\\\n",
    "x_1 \\geq 0              && && -\\lambda_2 \\geq 0 \\\\\n",
    "x_2 \\geq 0              && && -\\lambda_3 \\geq 0\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Observación\n",
    ":class: tip\n",
    "\n",
    "Para la interpretación del problema dual en esta primera parte no utilizamos una forma estándar del mismo.\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{margin}\n",
    "\n",
    "La forma aumentada recuérdese es:\n",
    "\n",
    "$\\displaystyle \\max_{x \\in \\mathbb{R}^2} 3x_1 + 5x_2 \\\\\n",
    "\\text{sujeto a: }\\\\\n",
    "x_1 + x_3 = 4 \\\\\n",
    "2x_2 + x_4 = 12 \\\\\n",
    "3x_1 + 2x_2 + x_5 = 18 \\\\\n",
    "x_1 \\geq 0, x_2 \\geq 0, x_3 \\geq 0, x_4 \\geq 0, x_5 \\geq 0\n",
    "$\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recordemos algunos resultados que obtuvimos en el {ref}`ejemplo del método gráfico <EJMETGRAFICOPL>` y en el {ref}`ejemplo del método símplex <EJMETSIMPLEX>` para el problema primal en su forma **aumentada**:\n",
    "\n",
    "* La solución óptima es $x^* = \\left [ \\begin{array}{c} 2 \\\\ 6\\end{array} \\right ]$ con valor de la función objetivo $f_o(x) = (-c)^Tx^* = 36$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* La relación entre $f_o(x)$ y el vector $\\nu$ en el método símplex es: $f_o(x) = - \\nu^Tb$. **Sin embargo** recuérdese que el vector $\\nu$ surgió por el uso de la función Lagraniana para restricciones de igualdad en la forma aumentada."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{margin}\n",
    "\n",
    "Recuérdese que los multiplicadores de Lagrange $\\nu, \\lambda$ se asocian a igualdades y desigualdades respectivamente, ver {ref}`la función Lagrangiana <FUNLAGRANGIANA>`.\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* En esta sección consideramos una forma del PL **no estándar, pues sólo tiene desigualdades**. Por tanto sólo tenemos al multiplicador $\\lambda$. Entonces se cumple que **no** tenemos vector $\\nu$ y más bien $\\lambda$ es el **único** vector multiplicador de Lagrange que tenemos y se cumple: $f_o(x) = (- \\lambda) ^Tb$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Para la forma aumentada del PL se obtuvo que el valor del vector óptimo $\\nu$ es: $\\nu^* = \\left [ \\begin{array}{c} 0 \\\\ -1.5 \\\\ -1 \\end{array} \\right ]$ y por el punto anterior: $\\lambda^* = \\left [ \\begin{array}{c} 0 \\\\ -1.5 \\\\ -1 \\end{array} \\right ]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* El valor óptimo de la función objetivo entonces se puede calcular a partir de $\\lambda^*$: $f_o(x) = (-\\lambda^*)^Tb = -[0 \\quad -1.5 \\quad -1] \\left [ \\begin{array}{c} 4 \\\\ 12 \\\\ 18 \\end{array} \\right ] = - (-36) = 36$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La interpretación del problema dual podemos realizarla por partes, siendo las primeras las relacionadas con la función objetivo de éste: $-(\\lambda)^Tb$ y su variable de optimización: $-\\lambda$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Función objetivo y variable de optimización del problema dual"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La función objetivo del problema dual es:\n",
    "\n",
    "$$-\\lambda^T b = b_1(-\\lambda_1) + b_2(-\\lambda_2) + \\dots + b_m(-\\lambda_m)$$\n",
    "\n",
    "con $b_i$ $i$-ésima componente del vector $b$ que representa al recurso $i=1, 2, \\dots, m$. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{margin}\n",
    "\n",
    "$\n",
    "\\displaystyle \\min_{\\lambda \\in \\mathbb{R}^3} -4\\lambda_1 -12 \\lambda_2 -18 \\lambda_3\\\\\n",
    "\\text{sujeto a: } \\\\\n",
    "-\\lambda_1 -3 \\lambda_3 \\geq 3\\\\\n",
    "-2 \\lambda_2 - 2 \\lambda_3 \\geq 5 \\\\\n",
    "-\\lambda_1 \\geq 0 \\\\\n",
    "-\\lambda_2 \\geq 0 \\\\\n",
    "-\\lambda_3 \\geq 0\n",
    "$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Como se vio arriba en el método símplex los valores de las funciones objetivo de cada problema son iguales de modo que cada término $b_i (-\\lambda_i)$ puede interpretarse como la contribución a la ganancia por consumir $b_i$ unidades del recurso $i$ en el problema primal.\n",
    "\n",
    "Así, la variable de optimización $-\\lambda_i$ se interpreta como la contribución a la ganancia por unidad del recurso $i$ y minimizar $-\\lambda^T b$ es minimizar el valor total de los recursos consumidos por las actividades. En el ejemplo los recursos recuérdese que son el número de horas de producción disponibles por semana en las plantas para producir los productos $1$ y $2$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Comentario\n",
    "\n",
    "En Economía se conocen a las variables del vector $-\\lambda$ como [shadow prices](https://en.wikipedia.org/wiki/Shadow_price) e indican que un incremento individual de una unidad en cualquier $b_i$ aumentará en $-\\lambda_i^*$ el valor óptimo de la función objetivo (ganancia total semanal en miles de pesos).\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{margin}\n",
    "$\n",
    "\\displaystyle \\max_{x \\in \\mathbb{R}^2} 3x_1 + 5x_2       \\\\\n",
    "x_1 \\leq 4 \\nonumber    \\\\\n",
    "2x_2 \\leq 12            \\\\\n",
    "3x_1 + 2x_2 \\leq 18     \\\\\n",
    "x_1 \\geq 0              \\\\\n",
    "x_2 \\geq 0              \\\\\n",
    "$\n",
    "```"
   ]<commit_msg>missing astherisc in shadow prices vector for 4.4 nbook<commit_after>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(DUALIDAD)="
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4.4 Dualidad"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Notas para contenedor de docker:\n",
    "\n",
    "Comando de docker para ejecución de la nota de forma local:\n",
    "\n",
    "nota: cambiar `<ruta a mi directorio>` por la ruta de directorio que se desea mapear a `/datos` dentro del contenedor de docker.\n",
    "\n",
    "`docker run --rm -v <ruta a mi directorio>:/datos --name jupyterlab_optimizacion_2 -p 8888:8888 -p 8787:8787 -d palmoreck/jupyterlab_optimizacion_2:3.0.0`\n",
    "\n",
    "password para jupyterlab: `<PASSWORD>`\n",
    "\n",
    "Detener el contenedor de docker:\n",
    "\n",
    "`docker stop jupyterlab_optimizacion_2`\n",
    "\n",
    "Documentación de la imagen de docker `palmoreck/jupyterlab_optimizacion_2:3.0.0` en [liga](https://github.com/palmoreck/dockerfiles/tree/master/jupyterlab/optimizacion_2).\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Al final de esta nota el y la lectora:\n",
    ":class: tip\n",
    "\n",
    "*\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ejemplo prototipo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Considérese el problema planteado en {ref}`ejemplo prototipo <EJPROTOTIPO>` con sus suposiciones. El objetivo es elegir los valores de $x_1, x_2$ que maximicen $f_o$, la ganancia total, sujeta a las restricciones impuestas sobre sus valores por las capacidades de producción limitadas disponibles en las tres plantas. Esto es, resolver el PL siguiente:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\displaystyle \\max_{x \\in \\mathbb{R}^2} 3x_1 + 5x_2$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\text{sujeto a: }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$x_1 \\leq 4$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$2x_2 \\leq 12$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$3x_1 + 2x_2 \\leq 18$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$x_1 \\geq 0, x_2 \\geq 0$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El término $3x_1$ representa la ganancia generada (en miles de pesos) cuando se fabrica el producto 1 a una tasa de $x_1$ lotes por semana. Se tienen contribuciones individuales de cada producto a la ganancia. Se desea determinar cuáles tasas de producción (no negativas) deben tener los dos productos con el fin de maximizar la ganancia total sujeta a las restricciones impuestas por las capacidades de producción limitadas disponibles en las tres plantas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La región factible y el valor óptimo del PL anterior es:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "tags": [
     "hide-input"
    ]
   },
   "outputs": [
    {
     "data": {
      "image/png": "<KEY>",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "#x_1 ≤ 4\n",
    "\n",
    "point1_x_1 = (4,0)\n",
    "\n",
    "point2_x_1 = (4, 10)\n",
    "\n",
    "point1_point2_x_1 = np.row_stack((point1_x_1, point2_x_1))\n",
    "\n",
    "#x_1 ≥ 0\n",
    "point3_x_1 = (0,0)\n",
    "\n",
    "point4_x_1 = (0, 10)\n",
    "\n",
    "point3_point4_x_1 = np.row_stack((point3_x_1, point4_x_1))\n",
    "\n",
    "#2x_2 ≤ 12 or x_2 ≤ 6\n",
    "\n",
    "point1_x_2 = (0, 6)\n",
    "\n",
    "point2_x_2 = (8, 6)\n",
    "\n",
    "point1_point2_x_2 = np.row_stack((point1_x_2, point2_x_2))\n",
    "\n",
    "#x_2 ≥ 0\n",
    "\n",
    "point3_x_2 = (0, 0)\n",
    "\n",
    "point4_x_2 = (8, 0)\n",
    "\n",
    "point3_point4_x_2 = np.row_stack((point3_x_2, point4_x_2))\n",
    "\n",
    "#3x_1 + 2x_2 ≤ 18\n",
    "\n",
    "x_1_region_1 = np.linspace(0,4, 100)\n",
    "\n",
    "x_2_region_1 = 1/2*(18 - 3*x_1_region_1)\n",
    "\n",
    "\n",
    "x_1 = np.linspace(0,6, 100)\n",
    "\n",
    "x_2 = 1/2*(18 - 3*x_1)\n",
    "\n",
    "plt.plot(point1_point2_x_1[:,0], point1_point2_x_1[:,1],\n",
    "         point3_point4_x_1[:,0], point3_point4_x_1[:,1],\n",
    "         point1_point2_x_2[:,0], point1_point2_x_2[:,1],\n",
    "         point3_point4_x_2[:,0], point3_point4_x_2[:,1],\n",
    "         x_1, x_2)\n",
    "plt.scatter(2, 6, marker='o', s=150,\n",
    "            facecolors='none', edgecolors='b')\n",
    "plt.legend([\"$x_1 = 4$\", \"$x_1 = 0$\", \n",
    "            \"$2x_2 = 12$\", \"$x_2 = 0$\",\n",
    "            \"$3x_1+2x_2 = 18$\", \"(óptimo, valor óptimo)\"], bbox_to_anchor=(1, 1))\n",
    "\n",
    "plt.fill_between(x_1_region_1, 0, x_2_region_1, where=x_2_region_1<=6, color=\"plum\")\n",
    "x_1_region_2 = np.linspace(0,2, 100)\n",
    "plt.fill_between(x_1_region_2, 0, 6, color=\"plum\")\n",
    "plt.title(\"Región factible del PL\")\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Definición\n",
    "\n",
    "Asociado a todo problema de programación lineal existe otro problema lineal con nombre **dual**. Al problema \"original\" se le nombra **primal**.\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Observación\n",
    ":class: tip\n",
    "\n",
    "Realmente no importa a cuál de los problemas se le dé el nombre primal y a cuál el de dual. La convención es que el modelo que se formula para representar el problema real recibe el nombre de problema primal no importando la forma que tiene (estándar u otra).\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El problema **primal** anterior escrito en notación vectorial y matricial es:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\displaystyle \\max_{x \\in \\mathbb{R}^2} (-c)^Tx$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\text{sujeto a: }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$Ax \\leq b$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$x \\geq 0$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "donde: $\n",
    "A= \n",
    "\\left [\n",
    "\\begin{array}{cc}\n",
    "1 & 0 \\\\\n",
    "0 & 2 \\\\\n",
    "3 & 2 \\\\\n",
    "\\end{array}\n",
    "\\right ], x=\n",
    "\\left [\n",
    "\\begin{array}{c}\n",
    "x_1 \\\\\n",
    "x_2 \\\\\n",
    "\\end{array}\n",
    "\\right ], b=\n",
    "\\left[\n",
    "\\begin{array}{c}\n",
    "4 \\\\\n",
    "12 \\\\\n",
    "18\n",
    "\\end{array}\n",
    "\\right ]$ y \n",
    "$c = \\left [ \\begin{array}{c} -3 \\\\ -5 \\end{array}\\right]$ representa al vector de costos unitarios o equivalentemente $-c$ el vector de ganancias unitarias. La última desigualdad se refiere a que todas las componentes del vector $x$ son mayores o iguales a cero. El PL busca maximizar $f_o(x) = -c^Tx$, la ganancia total."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{margin}\n",
    "$\n",
    "\\displaystyle \\max_{x \\in \\mathbb{R}^2} 3x_1 + 5x_2 \\\\\n",
    "\\text{sujeto a: }       \\\\\n",
    "x_1 \\leq 4 \\nonumber    \\\\\n",
    "2x_2 \\leq 12            \\\\\n",
    "3x_1 + 2x_2 \\leq 18     \\\\\n",
    "x_1 \\geq 0              \\\\\n",
    "x_2 \\geq 0              \\\\\n",
    "$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Comentario\n",
    "\n",
    "En el contexto del PL ejemplo se tiene:\n",
    "\n",
    "$f_o$: ganancia total debida a todas las actividades (función objetivo). En el ejemplo es la ganancia semanal total (en miles de pesos) que generan los productos $1$ y $2$.\n",
    "\n",
    "$x_j$: nivel de la actividad $j$ con $j=1, 2, \\dots, n$ (variables de optimización primales). En el ejemplo $n=2$. $x_1$ es el número de lotes del producto $1$ que se fabrican por semana (análogamente $x_2$).\n",
    "\n",
    "$c_j$: costo unitario debido a la actividad j con $j=1, 2, \\dots, n$ ($-c_j$ es la ganancia unitaria).\n",
    "\n",
    "$b_i$: cantidad disponible del recurso $i$ para asignarse a las actividades con $i=1, 2, \\dots, m$. En el ejemplo $m=3$. $b_1=4$ representa el número de horas de producción disponibles por semana en la planta $1$ para fabricar los lotes de los productos $1$ y $2$.\n",
    "\n",
    "$a_{ij}$: cantidad del recurso $i$ consumido por cada unidad de la actividad $j$ con $i=1, 2, \\dots n$, $j=1, 2, \\dots m$. En el ejemplo se consumen $3$ horas para producir el producto $1$ y $2$ horas para el $2$ de las $18$ horas disponibles en la planta $3$.\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El problema **dual** asociado al problema anterior es:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{margin}\n",
    "\n",
    "Por ahora tómese como válida la expresión del problema dual, en esta primera parte se busca señalar las relaciones existentes con el problema primal y no la forma matemática de obtenerlo.\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\displaystyle \\min_{\\lambda \\in \\mathbb{R}^3} (-\\lambda)^T b$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\text{sujeto a: }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$A^T(-\\lambda) \\geq -c$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$-\\lambda \\geq 0$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Que escrito con escalares es:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\displaystyle \\min_{\\lambda \\in \\mathbb{R}^3} -4\\lambda_1 -12 \\lambda_2 -18 \\lambda_3$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\text{sujeto a: }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$-\\lambda_1 -3 \\lambda_3 \\geq 3$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$-2 \\lambda_2 - 2 \\lambda_3 \\geq 5$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$-\\lambda_1 \\geq 0, -\\lambda_2 \\geq 0, -\\lambda_3 \\geq 0$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{margin}\n",
    "\n",
    "Forma estándar de un PL:\n",
    "\n",
    "$\n",
    "\\displaystyle \\min_{x \\in \\mathbb{R}^n} c^Tx\\\\\n",
    "\\text{sujeto a:} \\\\\n",
    "Ax=b\\\\\n",
    "x \\geq 0\n",
    "$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En su forma aumentada (que en este ejemplo corresponde a la estándar de los PL) es:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\displaystyle \\min_{\\lambda \\in \\mathbb{R}^3} -4\\lambda_1 -12 \\lambda_2 -18 \\lambda_3$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$-\\lambda_1 -3 \\lambda_3 + \\lambda_4 = 3$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$-2 \\lambda_2 - 2 \\lambda_3 + \\lambda_5 = 5$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$-\\lambda_1 \\geq 0, -\\lambda_2 \\geq 0, -\\lambda_3 \\geq 0, -\\lambda_4 \\geq 0, -\\lambda_5 \\geq 0$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{margin}\n",
    "$\n",
    "\\displaystyle \\max_{x \\in \\mathbb{R}^2} 3x_1 + 5x_2       \\\\\n",
    "x_1 \\leq 4 \\nonumber    \\\\\n",
    "2x_2 \\leq 12            \\\\\n",
    "3x_1 + 2x_2 \\leq 18     \\\\\n",
    "x_1 \\geq 0              \\\\\n",
    "x_2 \\geq 0              \\\\\n",
    "$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{margin}\n",
    "\n",
    "$\n",
    "\\displaystyle \\min_{\\lambda \\in \\mathbb{R}^3} -4\\lambda_1 -12 \\lambda_2 -18 \\lambda_3\\\\\n",
    "\\text{sujeto a: } \\\\\n",
    "-\\lambda_1 -3 \\lambda_3 \\geq 3\\\\\n",
    "-2 \\lambda_2 - 2 \\lambda_3 \\geq 5 \\\\\n",
    "-\\lambda_1 \\geq 0 \\\\\n",
    "-\\lambda_2 \\geq 0 \\\\\n",
    "-\\lambda_3 \\geq 0\n",
    "$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Comentarios\n",
    "\n",
    "* El problema dual usa exactamente los mismos parámetros del problema primal pero en diferentes lugares:\n",
    "\n",
    "    * Los coeficientes de la función objetivo del problema primal son los lados derechos de las restricciones funcionales del problema dual.\n",
    "    \n",
    "    * Los lados derechos de las restricciones funcionales del problema primal son los coeficientes de la función objetivo del problema dual.\n",
    "    \n",
    "    * Los coeficientes de una variable de las restricciones funcionales del problema primal son los coeficientes de una restricción funcional del problema dual. Por ejemplo: de las restricciones funcionales $x_1 \\leq 4$, $2x_2 \\leq 12$ y $3x_1 + 2x_2 \\leq 18$ del problema primal los coeficientes de $x_1$ son $1, 0, 3$ respectivamente, en el problema dual se tienen estos mismos coeficientes para la restricción funcional:$-\\lambda_1 -3 \\lambda_3 \\geq 3$ (recuérdese que la variable del problema dual en su forma no estándar es $-\\lambda$). \n",
    "\n",
    "\n",
    "* Las variables $-\\lambda_4, -\\lambda_5$ son variables consideradas de **superávit**, ***surplus variables***, (obsérvese la diferencia con las variables de holgura).\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Interpretación del problema dual"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Considérese las siguientes formas de los modelos de optimización primal-dual para el problema del inicio:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\begin{align*}\n",
    "\\displaystyle \\max_{x \\in \\mathbb{R}^2} 3x_1 + 5x_2 \n",
    "&& &&\n",
    "\\displaystyle \\min_{\\lambda \\in \\mathbb{R}^3} -4\\lambda_1 -12 \\lambda_2 -18 \\lambda_3\\\\\n",
    "\\text{sujeto a: }       && &&  \\text{sujeto a: }\\\\\n",
    "x_1 \\leq 4 \\nonumber    && &&  -\\lambda_1 -3 \\lambda_3 \\geq 3\\\\\n",
    "2x_2 \\leq 12            && && -2 \\lambda_2 - 2 \\lambda_3 \\geq 5 \\\\\n",
    "3x_1 + 2x_2 \\leq 18     && && -\\lambda_1 \\geq 0 \\\\\n",
    "x_1 \\geq 0              && && -\\lambda_2 \\geq 0 \\\\\n",
    "x_2 \\geq 0              && && -\\lambda_3 \\geq 0\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Observación\n",
    ":class: tip\n",
    "\n",
    "Para la interpretación del problema dual en esta primera parte no utilizamos una forma estándar del mismo.\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{margin}\n",
    "\n",
    "La forma aumentada recuérdese es:\n",
    "\n",
    "$\\displaystyle \\max_{x \\in \\mathbb{R}^2} 3x_1 + 5x_2 \\\\\n",
    "\\text{sujeto a: }\\\\\n",
    "x_1 + x_3 = 4 \\\\\n",
    "2x_2 + x_4 = 12 \\\\\n",
    "3x_1 + 2x_2 + x_5 = 18 \\\\\n",
    "x_1 \\geq 0, x_2 \\geq 0, x_3 \\geq 0, x_4 \\geq 0, x_5 \\geq 0\n",
    "$\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recordemos algunos resultados que obtuvimos en el {ref}`ejemplo del método gráfico <EJMETGRAFICOPL>` y en el {ref}`ejemplo del método símplex <EJMETSIMPLEX>` para el problema primal en su forma **aumentada**:\n",
    "\n",
    "* La solución óptima es $x^* = \\left [ \\begin{array}{c} 2 \\\\ 6\\end{array} \\right ]$ con valor de la función objetivo $f_o(x) = (-c)^Tx^* = 36$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* La relación entre $f_o(x)$ y el vector $\\nu$ en el método símplex es: $f_o(x) = - \\nu^Tb$. **Sin embargo** recuérdese que el vector $\\nu$ surgió por el uso de la función Lagraniana para restricciones de igualdad en la forma aumentada."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{margin}\n",
    "\n",
    "Recuérdese que los multiplicadores de Lagrange $\\nu, \\lambda$ se asocian a igualdades y desigualdades respectivamente, ver {ref}`la función Lagrangiana <FUNLAGRANGIANA>`.\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* En esta sección consideramos una forma del PL **no estándar, pues sólo tiene desigualdades**. Por tanto sólo tenemos al multiplicador $\\lambda$. Entonces se cumple que **no** tenemos vector $\\nu$ y más bien $\\lambda$ es el **único** vector multiplicador de Lagrange que tenemos y se cumple: $f_o(x) = (- \\lambda) ^Tb$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Para la forma aumentada del PL se obtuvo que el valor del vector óptimo $\\nu$ es: $\\nu^* = \\left [ \\begin{array}{c} 0 \\\\ -1.5 \\\\ -1 \\end{array} \\right ]$ y por el punto anterior: $\\lambda^* = \\left [ \\begin{array}{c} 0 \\\\ -1.5 \\\\ -1 \\end{array} \\right ]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* El valor óptimo de la función objetivo entonces se puede calcular a partir de $\\lambda^*$: $f_o(x) = (-\\lambda^*)^Tb = -[0 \\quad -1.5 \\quad -1] \\left [ \\begin{array}{c} 4 \\\\ 12 \\\\ 18 \\end{array} \\right ] = - (-36) = 36$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La interpretación del problema dual podemos realizarla por partes, siendo las primeras las relacionadas con la función objetivo de éste: $-(\\lambda)^Tb$ y su variable de optimización: $-\\lambda$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Función objetivo y variable de optimización del problema dual"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La función objetivo del problema dual es:\n",
    "\n",
    "$$-\\lambda^T b = b_1(-\\lambda_1) + b_2(-\\lambda_2) + \\dots + b_m(-\\lambda_m)$$\n",
    "\n",
    "con $b_i$ $i$-ésima componente del vector $b$ que representa al recurso $i=1, 2, \\dots, m$. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{margin}\n",
    "\n",
    "$\n",
    "\\displaystyle \\min_{\\lambda \\in \\mathbb{R}^3} -4\\lambda_1 -12 \\lambda_2 -18 \\lambda_3\\\\\n",
    "\\text{sujeto a: } \\\\\n",
    "-\\lambda_1 -3 \\lambda_3 \\geq 3\\\\\n",
    "-2 \\lambda_2 - 2 \\lambda_3 \\geq 5 \\\\\n",
    "-\\lambda_1 \\geq 0 \\\\\n",
    "-\\lambda_2 \\geq 0 \\\\\n",
    "-\\lambda_3 \\geq 0\n",
    "$\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Como se vio arriba en el método símplex los valores de las funciones objetivo de cada problema son iguales de modo que cada término $b_i (-\\lambda_i)$ puede interpretarse como la contribución a la ganancia por consumir $b_i$ unidades del recurso $i$ en el problema primal.\n",
    "\n",
    "Así, la variable de optimización $-\\lambda_i$ se interpreta como la contribución a la ganancia por unidad del recurso $i$ y minimizar $-\\lambda^T b$ es minimizar el valor total de los recursos consumidos por las actividades. En el ejemplo los recursos recuérdese que son el número de horas de producción disponibles por semana en las plantas para producir los productos $1$ y $2$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Comentario\n",
    "\n",
    "En Economía se nombra al vector $-\\lambda^*$ como [shadow prices](https://en.wikipedia.org/wiki/Shadow_price). Sus componentes indican que un incremento individual de una unidad en cualquier $b_i$ aumentará en $-\\lambda_i^*$ el valor óptimo de la función objetivo (ganancia total semanal en miles de pesos).\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{margin}\n",
    "$\n",
    "\\displaystyle \\max_{x \\in \\mathbb{R}^2} 3x_1 + 5x_2       \\\\\n",
    "x_1 \\leq 4 \\nonumber    \\\\\n",
    "2x_2 \\leq 12            \\\\\n",
    "3x_1 + 2x_2 \\leq 18     \\\\\n",
    "x_1 \\geq 0              \\\\\n",
    "x_2 \\geq 0              \\\\\n",
    "$\n",
    "```"
   ]
{'fraction_non_alphanumeric': 0.2185080439519681, 'fraction_numerical': 0.027585887152858268, 'mean_word_length': 2.257002642506606, 'pattern_counts': {'":': 426, '<': 24, '<?xml version=': 0, '>': 22, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '143387', 'n_tokens_mistral': 17851, 'n_tokens_neox': 16996, 'n_words': 4388}