{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Este es un ejemplo de un problema de programación lineal que es dual de sí mismo" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}{===================================}$ " ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}{===================================}$$" ], "text/plain": [ "ry" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}{===================================}$ " ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}{===================================}$$" ], "text/plain": [ "ry" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\begin{array}{l}\n", "\\begin{array}{lcrcrcrcl}\n", " \\min \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} 0 \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\\\\n", " \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} - \\mspace{-6mu}&\\mspace{-6mu} x_{2} \\mspace{-6mu}&\\mspace{-6mu} + \\mspace{-6mu}&\\mspace{-6mu} x_{3} \\mspace{-6mu}&\\mspace{-6mu} \\geq \\mspace{-6mu}&\\mspace{-6mu} 0 \\\\\n", " \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} x_{1} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} - \\mspace{-6mu}&\\mspace{-6mu} x_{3} \\mspace{-6mu}&\\mspace{-6mu} \\geq \\mspace{-6mu}&\\mspace{-6mu} 0 \\\\\n", " \\mspace{-6mu}&\\mspace{-6mu} - \\mspace{-6mu}&\\mspace{-6mu} x_{1} \\mspace{-6mu}&\\mspace{-6mu} + \\mspace{-6mu}&\\mspace{-6mu} x_{2} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\geq \\mspace{-6mu}&\\mspace{-6mu} 0 \\\\\n", "\\end{array} \\\\\n", "x_{1}, x_{2}, x_{3} \\geq 0\n", "\\end{array}$ " ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\begin{array}{l}\n", "\\begin{array}{lcrcrcrcl}\n", " \\min \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} 0 \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\\\\n", " \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} - \\mspace{-6mu}&\\mspace{-6mu} x_{2} \\mspace{-6mu}&\\mspace{-6mu} + \\mspace{-6mu}&\\mspace{-6mu} x_{3} \\mspace{-6mu}&\\mspace{-6mu} \\geq \\mspace{-6mu}&\\mspace{-6mu} 0 \\\\\n", " \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} x_{1} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} - \\mspace{-6mu}&\\mspace{-6mu} x_{3} \\mspace{-6mu}&\\mspace{-6mu} \\geq \\mspace{-6mu}&\\mspace{-6mu} 0 \\\\\n", " \\mspace{-6mu}&\\mspace{-6mu} - \\mspace{-6mu}&\\mspace{-6mu} x_{1} \\mspace{-6mu}&\\mspace{-6mu} + \\mspace{-6mu}&\\mspace{-6mu} x_{2} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\geq \\mspace{-6mu}&\\mspace{-6mu} 0 \\\\\n", "\\end{array} \\\\\n", "x_{1}, x_{2}, x_{3} \\geq 0\n", "\\end{array}$$" ], "text/plain": [ "LP problem (use 'view(...)' or '%display typeset' for details)" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}0$ " ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}0$$" ], "text/plain": [ "0" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(0,\\,0,\\,0\\right)$ " ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(0,\\,0,\\,0\\right)$$" ], "text/plain": [ "(0, 0, 0)" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}{===================================}$ " ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}{===================================}$$" ], "text/plain": [ "ry" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}{===================================}$ " ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}{===================================}$$" ], "text/plain": [ "ry" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "n=3 # número de variables x's\n", "m=3 # número de restricciones (distintas de las de signo)\n", "\n", "c=matrix(QQ,1,n,[0,0,0] ) # vector de costos\n", "\n", "A=matrix(QQ,m,n,[ # coeficientes de las variables x's\n", "[0,-1,1],\n", "[1,0,-1],\n", "[-1,1,0]\n", "])\n", "\n", "\n", "\n", "b=matrix(QQ,m,1,[0,0,0]) # vector de la derecha\n", "\n", "\n", "######################################################\n", "############### VARIABLES DE HOLGURA ################\n", "\n", "\n", "h=matrix(ZZ,1,m,[-1,-1,-1]) # variables de holgura: \n", " # Pon 1 si va sumando, \n", " # -1 si va restando y \n", " # 0 si no hay variable de holgura.\n", "\n", "#######################################################\n", "# Signo de las variables x's ###\n", "\n", "signvars=[\">=\",\">=\",\">=\"]\n", "\n", "#######################################################\n", "\n", "\n", "\n", "\n", "######################################################\n", "######### Problemas Paramétricos ###########\n", " \n", "prmtr_b=0 # 1 si quieres usar un parámetro en b\n", " # 0 en caso contrario\n", "\n", "bp=matrix(QQ,m,1,[0,0,0]) # vector de la derecha para problemas paramétricos.\n", "\n", "###################################################### \n", " \n", "prmtr_c=0 # 1 si quieres usar un parámetro en c\n", " # 0 en caso contrario\n", "\n", " \n", "cp=matrix(QQ,1,n,[0,0,0] ) # vector de costos adicional para problemas paramétricos.\n", "\n", "######################################################\n", "\n", "Aori=A\n", "cori=c\n", "bori=b\n", "\n", "##############################################################################\n", "####### Usando el paquete de programación lineal Pinteractive de Sage ########\n", "##############################################################################\n", "signos=[]\n", "for i in range(m):\n", " if h[0,i] == -1:\n", " signos.append(\">=\")\n", " elif h[0,i] == 1:\n", " signos.append(\"<=\")\n", " elif h[0,i] == 0:\n", " signos.append(\"==\")\n", "\n", " \n", "signosvduales=signos\n", "\n", "\n", "var_nam = []\n", "for i in range(n):\n", " k=i+1\n", " var_nam.append('x_%s' %k)\n", "\n", "\n", "\n", " \n", " \n", "PPL = InteractiveLPProblem(A, b, c, var_nam, \n", "constraint_type=signos, variable_type=signvars, problem_type=\"min\") \n", "\n", "\n", "##############################################################################\n", "##############################################################################\n", "\n", "\n", "####################################################################\n", "############ HASTA AQUÍ LOS DATOS ################################\n", "####################################################################\n", "\n", "\n", "raya=var('ry', latex_name='===================================')\n", "show(ry)\n", "show(ry)\n", "show(PPL)\n", "show(PPL.optimal_value())\n", "show(PPL.optimal_solution())\n", "show(ry)\n", "show(ry)\n", "\n" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "scrolled": false }, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}{===================================}$ " ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}{===================================}$$" ], "text/plain": [ "ry" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}{===================================}$ " ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}{===================================}$$" ], "text/plain": [ "ry" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\begin{array}{l}\n", "\\begin{array}{lcrcrcrcl}\n", " \\max \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} 0 \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\\\\n", " \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\pi_{2} \\mspace{-6mu}&\\mspace{-6mu} - \\mspace{-6mu}&\\mspace{-6mu} \\pi_{3} \\mspace{-6mu}&\\mspace{-6mu} \\leq \\mspace{-6mu}&\\mspace{-6mu} 0 \\\\\n", " \\mspace{-6mu}&\\mspace{-6mu} - \\mspace{-6mu}&\\mspace{-6mu} \\pi_{1} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} + \\mspace{-6mu}&\\mspace{-6mu} \\pi_{3} \\mspace{-6mu}&\\mspace{-6mu} \\leq \\mspace{-6mu}&\\mspace{-6mu} 0 \\\\\n", " \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\pi_{1} \\mspace{-6mu}&\\mspace{-6mu} - \\mspace{-6mu}&\\mspace{-6mu} \\pi_{2} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\leq \\mspace{-6mu}&\\mspace{-6mu} 0 \\\\\n", "\\end{array} \\\\\n", "\\pi_{1}, \\pi_{2}, \\pi_{3} \\geq 0\n", "\\end{array}$ " ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\begin{array}{l}\n", "\\begin{array}{lcrcrcrcl}\n", " \\max \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} 0 \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\\\\n", " \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\pi_{2} \\mspace{-6mu}&\\mspace{-6mu} - \\mspace{-6mu}&\\mspace{-6mu} \\pi_{3} \\mspace{-6mu}&\\mspace{-6mu} \\leq \\mspace{-6mu}&\\mspace{-6mu} 0 \\\\\n", " \\mspace{-6mu}&\\mspace{-6mu} - \\mspace{-6mu}&\\mspace{-6mu} \\pi_{1} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} + \\mspace{-6mu}&\\mspace{-6mu} \\pi_{3} \\mspace{-6mu}&\\mspace{-6mu} \\leq \\mspace{-6mu}&\\mspace{-6mu} 0 \\\\\n", " \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\pi_{1} \\mspace{-6mu}&\\mspace{-6mu} - \\mspace{-6mu}&\\mspace{-6mu} \\pi_{2} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\mspace{-6mu}&\\mspace{-6mu} \\leq \\mspace{-6mu}&\\mspace{-6mu} 0 \\\\\n", "\\end{array} \\\\\n", "\\pi_{1}, \\pi_{2}, \\pi_{3} \\geq 0\n", "\\end{array}$$" ], "text/plain": [ "LP problem (use 'view(...)' or '%display typeset' for details)" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}0$ " ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}0$$" ], "text/plain": [ "0" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(0,\\,0,\\,0\\right)$ " ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(0,\\,0,\\,0\\right)$$" ], "text/plain": [ "(0, 0, 0)" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}{===================================}$ " ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}{===================================}$$" ], "text/plain": [ "ry" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}{===================================}$ " ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}{===================================}$$" ], "text/plain": [ "ry" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "c=bori.transpose(); \n", "b=cori.transpose(); \n", "A=Aori.transpose(); \n", "nn=n; n=m; m=nn; \n", "\n", "restduales=[]\n", "hd=[]\n", "for i in range(m):\n", " if signvars[i] == \"\":\n", " restduales.append(\"==\")\n", " hd.append(0)\n", " elif signvars[i] == \">=\": \n", " restduales.append(\"<=\")\n", " hd.append(-1)\n", " elif signvars[i] == \"<=\":\n", " restduales.append(\">=\")\n", " hd.append(1)\n", "\n", "\n", " \n", "h=matrix(ZZ,1,m,hd) \n", "\n", "\n", "\n", " \n", "\n", "pi = var('pi', latex_name='\\\\pi')\n", "pi = matrix(SR,1,1, pi) \n", "var_nam_duales = []\n", "for i in range(n):\n", " k=i+1\n", " var_nam_duales.append('pi_%s' %k)\n", " \n", " \n", "PPL = InteractiveLPProblem(A, b, c, var_nam_duales,\n", "constraint_type=restduales, variable_type=signosvduales, problem_type=\"max\") \n", "\n", "raya=var('ry', latex_name='===================================')\n", "show(ry)\n", "show(ry)\n", "show(PPL)\n", "show(PPL.optimal_value())\n", "show(PPL.optimal_solution())\n", "show(ry)\n", "show(ry)\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.5", "language": "sage", "name": "sagemath" }, "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.11.2" } }, "nbformat": 4, "nbformat_minor": 4 }