programación lineal Archivos - Gestión de Operaciones

Programación Lineal (Método Gráfico)

El Método Gráfico (resolución gráfica) constituye una excelente alternativa de representación y resolución de modelos de Programación Lineal que tienen 2 variables de decisión. Para estos efectos existen herramientas computacionales que facilitan la aplicación del método gráfico como los softwares TORA, IORTutorial y Geogebra, los cuales se pueden consultar en detalle en Cómo Resolver Gráficamente un Modelo de Programación Lineal con TORA, Cómo Resolver Gráficamente un Modelo de Programación Lineal con IORTutorial y Cómo Resolver Gráficamente un modelo de Programación Lineal con Geogebra, respectivamente. En este contexto a continuación presentamos un compendio de ejercicios de Programación Lineal resueltos a través del método gráfico.

Ejercicios Resueltos del Método Gráfico en Programación Lineal

Ejercicio N°1: Una empresa vitivinícola ha adquirido recientemente un terreno de 110 hectáreas. Debido a la calidad del sol y el excelente clima de la región, se puede vender toda la producción de uvas Sauvignon Blanc y Chardonay. Se desea conocer cuánto plantar de cada variedad en las 110 hectáreas, dado los costos, beneficios netos y requerimientos de mano de obra según los datos que se muestran a continuación:

Suponga que se posee un presupuesto de US$10.000 y una disponibilidad de 1.200 días hombre durante el horizonte de planificación. Formule y resuelva gráficamente un modelo de Programación Lineal para este problema. Detalle claramente el dominio de soluciones factibles y el procedimiento utilizado para encontrar la solución óptima y valor óptimo.

Variables de Decisión:

$X_{1}$ : Hectáreas destinadas al cultivo de de Sauvignon Blanc
$X_{2}$ : Hectáreas destinadas al cultivo de Chardonay

Función Objetivo:

Maximizar $50X_{1}+120X_{2}$

Restricciones:

$X_{1}+X_{2}\leq 110$
$100X_{1}+200X_{2}\leq 10.000$
$10X_{1}+30X_{2}\leq 1.200$
$X_{1},X_{2}\geq 0$

Donde las restricciones están asociadas a la disponibilidad máxima de hectáreas para la plantación, presupuesto disponible, horas hombre en el período de planificación y no negatividad, respectivamente.

El siguiente gráfico muestra la representación del problema de la empresa vitivinícola. El área achurada corresponde al dominio de soluciones factibles, donde la solución básica factible óptima se alcanza en el vértice C, donde se encuentran activas las restricciones de presupuestos y días hombre. De esta forma resolviendo dicho sistema de ecuaciones se encuentra la coordenada de la solución óptima donde $X_{1}=60$ y $X_{2}=20$ (hectáreas). El valor óptimo es $V(P)=50(60)+120(20)=5.400$ (dólares).

Ejercicio N°2: Un taller tiene tres (3) tipos de máquinas A, B y C; puede fabricar dos (2) productos 1 y 2, todos los productos tienen que ir a cada máquina y cada uno va en el mismo orden: Primero a la máquina A, luego a la B y luego a la C. La siguiente tabla muestra:

Las horas requeridas en cada máquina, por unidad de producto
Las horas totales disponibles para cada máquina, por semana
La ganancia por unidad vendida de cada producto

Formule y resuelva a través del método gráfico un modelo de Programación Lineal para la situación anterior que permite obtener la máxima ganancia para el taller.

Variables de Decisión:

$X_{1}$ : Unidades a producir del Producto 1 semanalmente
$X_{2}$ : Unidades a producir del Producto 2 semanalmente

Función Objetivo:

Maximizar $X_{1}+1,5X_{2}$

Restricciones:

$2X_{1}+2X_{2}\leq 16$
$X_{1}+2X_{2}\leq 12$
$4X_{1}+2X_{2}\leq 28$
$X_{1},X_{2}\geq 0$

Las restricciones representan la disponibilidad de horas semanales para las máquinas A, B y C, respectivamente, además de incorporar las condiciones de no negatividad.

Para la resolución gráfica de este modelo utilizaremos el software GLP cual abordamos en el artículo Problema de Planificación Forestal resuelto con Graphic Linear Optimizer (GLP). El área de color verde corresponde al conjunto de soluciones factibles y la curva de nivel de la función objetivo que pasa por el vértice óptimo se muestra con una línea punteada de color rojo.

La solución óptima es $X_{1}=4$ y $X_{2}=4$ con valor óptimo $V(P)=1(4)+1,5(4)=10$ que representa la ganancia para el taller.

Ejercicio N°3: Una compañía elabora dos productos diferentes. Uno de ellos requiere por unidad 1/4 de hora en labores de armado, 1/8 de hora en labores de control de calidad y US$1,2 en materias primas. El otro producto requiere por unidad 1/3 de hora en labores de armado, 1/3 de hora en labores de control de calidad y US$0,9 en materias primas. Dada las actuales disponibilidades de personal en la compañía, existe a lo más un total de 90 horas para armado y 80 horas para control de calidad, cada día. El primer producto descrito tiene un valor de mercado (precio de venta) de US$9,0 por unidad y para el segundo este valor corresponde a US$8,0 por unidad. Adicionalmente se ha estimado que el límite máximo de ventas diarias para el primer producto descrito es de 200 unidades, no existiendo un límite máximo de ventas diarias para el segundo producto.

Formule y resuelva gráficamente un modelo de Programación Lineal que permita maximizar las utilidades de la compañía.

Variables de Decisión:

$X_{1}$ : Unidades a producir diariamente del Producto 1
$X_{2}$ : Unidades a producir diariamente del Producto 2

Función Objetivo:

Maximizar $(9-1,2)X_{1}+(8-0,9)X_{2}=7,8X_{1}+7,1X_{2}$

Restricciones:

$\frac{X_{1}}{4}+\frac{X_{2}}{3}\leq 90$
$\frac{X_{1}}{8}+\frac{X_{2}}{3}\leq 80$
$X_{1}\leq 200$
$X_{1},X_{2}\geq 0$

La primera restricción representa las limitantes de horas de armado diariamente. La segunda restricción la disponibilidad de horas para labores de control de calidad (también diariamente). La tercera restricción establece una cota superior para la producción y ventas diarias del Producto 1. Adicionalmente se incluyen las condiciones de no negatividad para las variables de decisión.

El dominio de soluciones factibles tiene 5 vértices que corresponden a los candidatos a óptimos del problema. En particular el vértice óptimo es D de modo que la solución óptima es $X_{1}=200$ y $X_{2}=120$ con valor óptimo $V(P)=7,8(200)+7,1(120)=2.412$ que corresponde a la utilidad máxima para la empresa.

Importante: A la fecha de esta publicación disponemos de más de 70 artículos relativos a la Programación Lineal los cuales recomendamos revisar, donde se aborda la resolución gráfica de este tipo de modelos como también la resolución a través de algoritmos como el Método Simplex y la implementación computacional con herramientas como Solver, What’sBest! y OpenSolver, entre otras.

En el siguiente tutorial de nuestro canal de Youtube se explica un ejemplo adicional con todos los elementos del método gráfico en Programación Lineal:

Método de Descomposición de Benders

La Descomposición de Benders es, como su nombre lo dice, un Método de Descomposición. La idea de este método es bastante simple: dividir para conquistar. El objetivo es literalmente descomponer el problema en dos partes: El Master Problem (Problema Maestro) y el Subproblem (Subproblema) (también llamado Slave Problem o Problema Esclavo). En el siguiente artículo revisaremos de qué se trata el Método de Descomposición de Benders, en conjunto con la presentación de su uso en un pequeño ejemplo.

Esta metodología fue propuesta por J.F. Benders en 1962, su nombre original es Partitioning procedures for solving mixed-variables programming problems, y como su nombre bien lo dice el método está pensado originalmente para problemas de Programación Entera Mixta. Sin embargo, también se puede aplicar en problemas de Programación Lineal.

El Método de Descomposición de Benders trabaja bajo el concepto de las “variables complicadas”, es decir las variables que hacen que nuestro problema se «complique». Si estas variables no existieran (o más bien, conociéramos su valor de forma anticipada) entonces el problema resultante se supone que es considerablemente más fácil de resolver.

En Programación Entera Mixta, se espera que estas variables “complicadas” sean las enteras, las cuales al fijar su valor, dejan un problema resultante que cumple con una característica muy conveniente: es lineal. Y como cumple con esto, entonces podemos hacer uso de todo lo que conocemos sobre Programación Lineal para realizar la optimización de las variables que (en un principio) fijamos.

Veamos entonces brevemente de que se trata el Método de Descomposición de Benders. Supongamos que tenemos un problema que tiene la siguiente estructura:

Como mencionamos al principio, entonces podemos separar este problema en dos partes. A continuación se muestra el Master Problem (Problema Maestro) a la izquierda y el Subproblem (Subproblema) a la derecha:

Como se puede ver, el Master Problem contiene las variables que son enteras, y el Subproblem contiene las variables continuas, por lo que este último cumple con ser un problema de Programación Lineal.

Notar que el lado derecho de las restricciones del problema esclavo son números, ya que los valores de las variables enteras están fijos.

Iniciamos este artículo diciendo que el concepto central es dividir para conquistar: en este caso lo que se hace es resolver el Problema Maestro para obtener los valores de y; con esto, podemos resolver entonces el Subproblema. Se puede observar que el valor de la función objetivo del Subproblema se encuentra en la función objetivo del Problema Maestro, lo anterior se reformulará más adelante.

Una nota relevante: Si te das cuenta, el Problema Maestro para esta formulación no tiene ninguna restricción más que las de dominio. Nada impide que el Problema Maestro también tenga restricciones. Esto estará dado por la estructura del problema que estemos estudiando.

Recuerda siempre: ambos problemas están conectados, por lo que el resultado de uno influye directamente en el resultado del otro. Con esto en consideración, se cumple la siguiente propiedad:

Si el Subproblema es no acotado, entonces el Problema Maestro también lo es, resultando en que el problema original es no acotado.

Si tenemos un problema de Programación Lineal, entonces tenemos que aprovecharlo. ¿Qué es lo primero que se nos viene a la mente con un problema lineal? La respuesta es dualidad. Cada problema lineal (primal) tiene su problema dual asociado, el cual para el caso del problema esclavo enunciado anteriormente, tiene la siguiente estructura:

¿Qué es lo que podemos ver en este problema dual?: Que la región factible (es decir el sub-espacio definido por las restricciones y el dominio del problema) no depende del valor que tomen las variables enteras, y sólo influye en el valor de la función objetivo (notar que están en ella).

Lo anterior entonces nos lleva a la siguiente pregunta: ¿Qué sucede cuando la región factible del problema es vacía? (recuerda que al ser vacía estamos diciendo que nuestro problema dual es infactible). Dos cosas pueden ocurrir:

Al ser el problema dual infactible, entonces su primal es no acotado para algún valor de las variables enteras, en cuyo caso el problema original también es no acotado, o bien
La región factible del problema primal es también infactible para todo valor de las variables enteras, llevando a la conclusión de que el problema original es infactible.

¿Por qué revisamos todo esto?: Porque es importante tenerlo en consideración, ya que como mencionamos anteriormente, al tener un problema esclavo lineal, entonces podemos hacer el uso de los conceptos de dualidad.

¿Para qué la usaremos?: Para reformular nuestro Problema Maestro, y transformarlo en lo que usualmente se conoce como Relaxed Master Problem (RMP). Esta reformulación utiliza las variables duales asociadas a las restricciones del Slave Problem primal.

El Relaxed Master Problem (Problema Maestro Relajado) se puede escribir de la siguiente forma:

A las restricciones (1) y (2) se les conoce como restricciones de factibilidad y optimalidad, respectivamente. Además, existe una variable auxiliar z, la cual permite es la responsable de hacer la “conexión” entre el Problema Maestro y el Subproblema (esto se puede ver en las restricciones del tipo (1) y (2)).

Al resolver el RMP vamos a obtener los valores de las variables enteras, las cuales utilizaremos para resolver el Subproblema, como resultado podemos obtener dos cosas:

El sub-problema es infactible, lo cual implica que el problema dual es no acotado. Si esto ocurre, debemos agregar un corte de factibilidad al RMP.
El sub-problema tiene una solución óptima, lo cual implica que el problema dual también la tiene. Si esto ocurre, entonces hay que agregar un corte de optimalidad al RMP.

La última pregunta que nos queda por responder es: ¿Cuántas veces iterar?. Para responder lo anterior debemos definir la cota superior e inferior.

La cota superior corresponde al valor de la función objetivo original de nuestro problema; la cota inferior corresponde a la función objetivo del Master Problem, por lo tanto, debemos continuar hasta que ambos valores sean iguales.

Como la teoría de esta descomposición puede ser un poco compleja, veamos un ejemplo.

Ejemplo Método de Descomposición de Benders (Programación Lineal)

El ejemplo que veremos a continuación corresponde a un problema de Programación Lineal. La aplicación es similar para los problemas de Programación Entera Mixta.

Supongamos que tenemos que resolver el siguiente problema:

La solución óptima para este problema es: $x_{1}=0$ , $x_{2}=0,714$ e $y=1,571$ con un valor para la función objetivo (valor óptimo) de 5,285. La solución óptima del problema anterior se puede alcanzar de forma sencilla a través del Método Simplex Dual o el Método Simplex de 2 Fases (y por cierto a través de otros procedimientos y herramientas computacionales como Solver de Excel).

Vamos a descomponer el problema de la siguiente forma: recuerda que utilizaremos el RMP (Problema Maestro Relajado). Sea esta la primera iteración, K=1.

Al resolver el RMP de la primera iteración, obtenemos como solución óptima $y=0$ y $z=0$ ; lo cual utilizaremos para resolver el Subproblema. Con $y=0$ , el resultado del Subproblema es: $x_{1}=2,2$ y $x_{2}=0,4$ con un valor en la función objetivo de 5,6.

Ahora debemos calcular la cota superior (UB) y cota inferior (LB):

Como difieren el valor de las cotas, debemos continuar. Gracias a la herramienta “Análisis de Sensibilidad” del Solver en Excel, podemos obtener el valor de las variables duales asociadas a las restricciones del Subproblema (también podríamos obtener el valor de las variables duales óptimas al utilizar el Teorema de Holguras Complementarias). Esos valores son: $\lambda_{1}=-1,6$ y $\lambda_{2}=-0,2$ .

Estos valores nos permiten crear el siguiente corte de optimalidad: $-1,6(-3+y)-0,2(-4+3y)\leq z$ , el cual agregamos al Problema Maestro:

Hacemos K=2 (contador de iteraciones) y resolvemos el Problema Maestro nuevamente. Este corte nos permite encontrar una nueva solución óptima: $y=2,545$ y $z=0$ . Con este valor de y, el resultado del Subproblema es: $x_{1}=0$ y $x_{2}=0,227$ con un valor en la función objetivo de 0,68.

Ahora debemos calcular la cota superior (UB) y cota inferior (LB):

Al ver las variables duales para las restricciones del Subproblema tenemos que: $\lambda_{1}=-1,5$ y $\lambda_{2}=0$ , lo cual permite crear el siguiente corte de optimalidad el cual agregamos al Problema Maestro:

Hacemos K=3 y resolvemos el Problema Maestro nuevamente. La nueva solución óptima para el Problema Maestro es $y=1,571$ y $z=2,142$ con un valor óptimo de 5,285. Con $y=1,571$ la solución del Subproblema es: $x_{1}=0$ y $x_{2}=0,714$ con un valor en la función objetivo de 2,148.

Ahora debemos calcular la cota superior e inferior:

Como ambas cotas (superior e inferior) son iguales, podemos detenernos. Hemos encontrado la solución óptima para nuestro problema de Programación Lineal. (Mis sinceros agradecimientos a mi amigo Javier Maturana Ross por su contribución con este detallado tutorial y los créditos correspondientes al profesor Yuping Huang por el ejemplo presentado en este artículo).

Ejemplo del Método Simplex (Tutorial y Cómo Funciona)

En el siguiente artículo detallaremos cómo funciona el Método Simplex a través de un ejemplo sencillo correspondiente a un modelo de Programación Lineal que considera 3 variables de decisión.

El Método Simplex corresponde a un algoritmo iterativo publicado por George Bernard Dantzig en el año 1947 en donde se busca alcanzar el máximo (o mínimo) de una función lineal compuesta por un conjunto de variables que deben satisfacer condiciones impuestas por restricciones lineales en forma de inecuaciones.

En este contexto, el objetivo de este artículo es definir en detalle distintas aproximaciones para la resolución de un modelo de Programación Lineal utilizando el Método Simplex, además de discutir sobre sus principales características.

Con tal propósito en perspectiva consideremos el siguiente modelo de optimización lineal:

Ejemplo del Método Simplex (Utilizando Diccionarios)

Un paso preliminar consiste en incorporar las denominadas variables de holgura. De modo de comprender este concepto consideremos la primera restricción:

$2x_{1}+3x_{2}+x_{3}\leq 5$

Para cada solución factible $x_{1},x_{2},x_{3}$ , el valor del lado izquierdo será a lo más el valor del lado derecho; o eventualmente existirá una diferencia (holgura) entre estos 2 valores.

De esta forma definimos $x_{4}$ como variable de holgura de dicha restricción, la cual se puede denotar por $x_{4}=5-2x_{1}-3x_{2}-x_{3}$ , donde $x_{4}\geq 0$ . De forma análoga se pueden definir las variables de holgura (no negativas) $x_{5}$ y $x_{6}$ para las restricciones 2 y 3, respectivamente. Finalmente podemos describir la función objetivo $5x_{1}+4x_{2}+3x_{3}$ utilizando $z$ de forma compacta.

En resumen, para cada selección de valores de las variables $x_{1},x_{2}$ y $x_{3}$ podemos definir valores para las variables $x_{4},x_{5},x_{6}$ , y $z$ utilizando las siguientes fórmulas (conocido comúnmente como diccionarios según la terminología utilizada en el libro Linear Programming de Vasek Chvátal):

$x_{4}=5-2x_{1}-3x_{2}-x_{3}$
$x_{5}=11-4x_{1}-x_{2}-2x_{3}$
$x_{6}=8-3x_{1}-4x_{2}-2x_{3}$
$z=5x_{1}+4x_{2}+3x_{3}$

El objetivo del Método Simplex es lograr sucesivas mejoras para el valor de la función objetivo asociada a la selección de alguna solución factible. Repetir dicho procedimiento un numero finito de veces debería permitir eventualmente alcanzar la solución óptima del problema lineal en estudio.

Para inicializar el Método Simplex necesitamos una solución factible. En nuestro ejemplo esto es sencillo y se puede alcanzar simplemente fijando las variables $x_{1},x_{2},x_{3}$ en cero. De esta forma se alcanzan los siguientes resultados:

$x_{1}=0,x_{2}=0,x_{3}=0,x_{4}=5,x_{5}=11,x_{6}=8,z=0$

En el contexto del objetivo planteado anteriormente, debemos buscar una solución factible que permita alcanzar un mayor valor para $z$ . Si, por ejemplo, mantenemos $x_{2}=x_{3}=0$ e incrementamos el valor de $x_{1}$ obtenemos $z=5x_{1}>0$ , de modo que si $x_{1}=1$ se obtiene $z=5$ (y $x_{4}=3,x_{5}=7,x_{6}=5$ ). Mejor aún, si $x_{1}=2$ (manteniendo $x_{2}=x_{3}=0$ ), se obtiene $z=10$ (y $x_{4}=1,x_{5}=3,x_{6}=2$ ).

Sin embargo, si asumimos $x_{1}=3$ (conservando $x_{2}=x_{3}=0$ ) el valor de la función objetivo ahora es $z=15$ , pero $x_{4}=-1,x_{5}=-1,x_{6}=-1$ que claramente no satisface las condiciones de no negatividad para las variables.

Por tanto la pregunta relevante es: ¿cuánto se puede incrementar el valor de $x_{1}$ (manteniendo $x_{2}=x_{3}=0$ al mismo tiempo) y seguir conservando la factibilidad ( $x_{4},x_{5},x_{6}\geq 0$ )?.

La condición $x_{4}=5-2x_{1}-3x_{2}-x_{3}\geq 0$ implica $x_{1}\leq \frac{5}{2}$ ; de forma similar $x_{5}\geq 0$ implica $x_{1}\leq \frac{11}{4}$ y $x_{6}\geq 0$ implica $x_{1}\leq \frac{8}{3}$ . Claramente de estas 3 cotas para la variable $x_{1}$ la más restrictiva es $x_{1}\leq \frac{5}{2}$ , de modo que incrementamos el valor de $x_{1}$ hasta ese valor de modo de obtener una nueva solución:

$x_{1}=\frac{5}{2},x_{2}=0,x_{3}=0,x_{4}=0,x_{5}=1,x_{6}=1/2,z=\frac{25}{2}$

Que claramente constituye una mejora para el valor de la función objetivo en comparación al valor inicial $z=0$ .

A continuación debemos buscar una nueva solución factible que sea aún mejor que la que acabamos de encontrar. Para ello la variable $x_{1}$ que cambió su valor desde cero a un número positivo (12,5), debe cambiar su lugar desde el lado derecho al lado izquierdo del sistema de ecuaciones. De forma análoga, la variable $x_{4}$ que cambio su valor de un número positivo a cero debe cambiar de lugar desde el lado derecho al lado izquierdo.

De esta forma y luego de cierta manipulación algebraica podemos reescribir $x_{1}$ en términos de $x_{2},x_{3},x_{4}$ según se observa a continuación:

$x_{1}=\frac{5}{2}-\frac{3}{2}x_{2}-\frac{1}{2}x_{3}-\frac{1}{2}x_{4}$

Luego, con el objetivo de expresar $x_{5},x_{6}$ y $z$ en términos de $x_{2},x_{3},x_{4}$ , simplemente substituimos el resultado anterior en las filas correspondientes:

$x_{5}=11-4(\frac{5}{2}-\frac{3}{2}x_{2}-\frac{1}{2}x_{3}-\frac{1}{2}x_{4})-x_{2}-2x_{3}$
$x_{5}=1+5x_{2}+2x_{4}$

$x_{6}=8-3(\frac{5}{2}-\frac{3}{2}x_{2}-\frac{1}{2}x_{3}-\frac{1}{2}x_{4})-4x_{2}-2x_{3}$
$x_{6}=\frac{1}{2}+\frac{1}{2}x_{2}-\frac{1}{2}x_{3}+\frac{3}{2}x_{4}$

$z=5(\frac{5}{2}-\frac{3}{2}x_{2}-\frac{1}{2}x_{3}-\frac{1}{2}x_{4})+4x_{2}+3x_{3}$
$z=\frac{25}{2}-\frac{7}{2}x_{2}+\frac{1}{2}x_{3}-\frac{5}{2}x_{4}$

De esta forma nuestro sistema de ecuaciones (diccionario) queda definido por:

$x_{1}=\frac{5}{2}-\frac{3}{2}x_{2}-\frac{1}{2}x_{3}-\frac{1}{2}x_{4}$
$x_{5}=1+5x_{2}+2x_{4}$
$x_{6}=\frac{1}{2}+\frac{1}{2}x_{2}-\frac{1}{2}x_{3}+\frac{3}{2}x_{4}$
$z=\frac{25}{2}-\frac{7}{2}x_{2}+\frac{1}{2}x_{3}-\frac{5}{2}x_{4}$

Como lo hicimos en la primera iteración debemos intentar incrementar el valor de la función objetivo ( $z$ ) seleccionando una variable adecuada en el lado derecho, mientras que al mismo tiempo mantenemos las restantes variables del lado derecho en cero. En este sentido se puede observar que aumentar el valor de las variables $x_{2}$ o $x_{4}$ generaría una disminución en el valor de $z$ que va en sentido contrario a nuestro objetivo de maximizar el valor de la función objetivo.

Por tanto, la única selección de una variable en el lado derecho que permitirá aumentar el valor de $z$ es seleccionar la variable $x_{3}$ .

¿Cuánto debemos incrementar el valor de $x_{3}$ ?. La respuesta se puede obtener directamente del sistema de ecuaciones anterior, considerando $x_{2}=x_{4}=0$ , la restricción $x_{1}\geq 0$ implica que $x_{3}\leq 5$ ; la restricción $x_{5}\geq 0$ no impone condiciones adicionales y la restricción $x_{6}\geq 0$ implica $x_{3}\leq 1$ . En consecuencia $x_{3}=1$ es el mejor valor que puede adoptar dicha variable.

La nueva solución corresponde a:

$x_{1}=2,x_{2}=0,x_{3}=1,x_{4}=0,x_{5}=1,x_{6}=0,z=13$

El valor de $z$ paso de 12,5 a 13 al cabo de una iteración del Método Simplex.

A continuación actualizamos el sistema de ecuaciones donde las variables que adoptan valores positivos $x_{1},x_{3},x_{5}$ se encontraran en el lado izquierdo, mientras las variables igual a cero estarán en el lado derecho. De este modo pasamos la variable $x_{3}$ al lado izquierdo, donde $x_{3}=1+x_{2}+3x_{4}-2x_{6}$ que permite substituir en el resto de las ecuaciones:

$x_{3}=1+x_{2}+3x_{4}-2x_{6}$
$x_{1}=2-2x_{2}-2x_{4}+x_{6}$
$x_{5}=1+5x_{2}+2x_{4}$
$z=13-3x_{2}-x_{4}-x_{6}$

Notar que no es posible seguir aumentando el valor de la función objetivo $z$ mediante un incremento de las variables del lado derecho $x_{2},x_{4},x_{6}$ (en efecto, el valor de $z$ decrecería). En consecuencia estamos en presencia de la solución óptima del problema: $x_{1}=2,x_{2}=0,x_{3}=1,x_{4}=0,x_{5}=1,x_{6}=0$ con valor óptimo $z=13$ .

El procedimiento anterior basado en diccionarios favorece una mejor comprensión conceptual de los fundamentos sobre los que se basa el Método Simplex. De forma complementaria a continuación presentaremos a modo de contraste las iteraciones del Método Simplex utilizando tablas (o tableau) que comúnmente corresponde a la forma en la cual se presenta el algoritmo en cursos de pregrado.

Ejemplo del Método Simplex (Utilizando Tableau)

Consideremos nuevamente nuestro problema de Programación Lineal:

A continuación incorporamos las variables de holgura (no negativas) $x_{4},x_{5},x_{6}$ que por definición tienen coeficiente nulo (cero) en la función objetivo. De esta forma obtenemos la forma estándar (*):

(*). Para nuestros efectos consideraremos que la forma estándar de un modelo de Programación Lineal esta dada por $Minimizar[c^{t}x, Ax=b,x\geq 0]$ , siendo este formato el que preferentemente hemos utilizado para desarrollar las iteraciones del Método Simplex en otros artículos relacionados en nuestro sitio. En consecuencia la selección de dicho formato es meramente convencional.

Retomando nuestro ejemplo, el tableau inicial queda definido por:

Las variables de holgura definen una Solución Básica Factible Inicial, con $x_{4}=5,x_{5}=11,x_{6}=8$ (las variables no básicas inicialmente corresponden a las variables originales del modelo, es decir, $x_{1},x_{2},x_{3}$ que por definición adoptan un valor igual a cero.

¿Cómo verificar que el tableau inicial representa una solución básica factible óptima para el problema?.

Criterio de Optimalidad: Si en una iteración del Método Simplex se dispone de una solución básica factible y adicionalmente todos los costos reducidos son mayores o iguales que cero, parar ya que la actual solución básica factible es óptima.

En el ejemplo propuesto si bien nos encontramos frente a una solución básica factible el costo reducido de las variables no básicas son negativos, por tanto no se cumple el criterio de optimalidad, es decir, se puede seguir mejorando el valor de la función objetivo.

En este sentido consideraremos arbitrariamente $x_{1}$ como la variable que ingresa a la base, aun cuando no hay certeza que la selección de la variable no básica con el costo reducido más negativo contribuya necesariamente a la Rapidez de Convergencia del Método Simplex.

La variable que deja la base para dar lugar a $x_{1}$ se obtiene del criterio de factibilidad:

Criterio de Factibilidad: Para decidir que variable básica deja la base, es necesario calcular el mayor valor que puede tomar la variable no básica que entra a la base que garantice la factibilidad de la nueva solución básica. Para ello se considera un cuociente entre el valor de la solución básica factible actual y los coeficientes mayores a cero en la columna de la variable entrante. Si todos los cuocientes son negativos el Problema es No Acotado y por tanto no existe solución óptima.

En el ejemplo el criterio de factibilidad para la presente iteración esta dado por:

$Min[\frac{5}{2},\frac{11}{4},\frac{8}{3}]=\frac{5}{2}$

El menor cuociente se alcanza en la primera fila (restricción) que determina la variable que debe abandonar la base, en este caso, la variable $x_{4}$ . Luego se actualiza la tabla realizando operaciones filas considerando el denominador del mínimo cuociente como pivote. El objetivo es alcanzar en la columna de la variable $x_{1}$ lo que actualmente disponemos en la columna de la variable $x_{4}$ .

Por ejemplo, podemos dividir la fila 1 por 2 de modo de obtener un 1 en la posición del pivote. Luego sobre esta nueva fila 1 podemos multiplicarla por -4 y sumarla a la fila 2. También se puede alcanzar un cero para la variable $x_{1}$ en la fila 3 multiplicando por -3 la nueva fila 1 y sumándola a la fila 3. Finalmente para lograr un cero en el costo reducido de $x_{1}$ se multiplica por 5 la nueva fila 1 y se suma a la fila 4.

De este modo el tableau del Método Simplex al cabo de una iteración queda de la siguiente forma:

La solución básica factible actual corresponde a: $x_{1}=\frac{5}{2},x_{2}=0,x_{3}=0,x_{4}=0,x_{5}=1,x_{6}=1/2$ con valor en la función objetivo $z=\frac{25}{2}$ . Se puede apreciar que dicho resultado es consistente con el enfoque de diccionarios utilizado inicialmente.

Claramente no se satisface el criterio de optimalidad dado que la variable no básica $x_{3}$ tiene costo reducido negativo. Por ello $x_{3}$ ingresa a la base y por tanto debemos calcular nuevamente el criterio de factibilidad para determinar la variable que deberá dejar la base:

$Min[\frac{5/2}{1/2},\frac{1/2}{1/2}]=1$

El pivote ahora se encuentra en la fila 3 y en consecuencia la variable básica $x_{6}$ debe dejar la base. Notar que no se ha considerado para el cálculo del criterio de factibilidad el coeficiente de la variable $x_{3}$ correspondiente a la fila 2 del tableau anterior (cuyo valor es cero y por tanto el cuociente se indefine).

Actualizamos el tableau del Método Simplex obteniendo los siguientes resultados:

Los valores que adoptan las variables básicas correspondientes a esta nueva iteración es $x_{1}=2,x_{2}=0,x_{3}=1,x_{4}=0,x_{5}=1,x_{6}=0$ que además representa la solución óptima del modelo de Programación Lineal (dado el cumplimiento del criterio de optimalidad). Luego el valor óptimo corresponde a $z=13$ .

Importante: Existen herramientas computacionales y aplicaciones que permiten resolver online un problema de Programación Lineal mediante el Método Simplex. A continuación se presenta un extracto de los resultados alcanzados para nuestro ejemplo utilizando la aplicación disponible en http://www.programacionlineal.net/simplex.html.

Método Simplex (Conclusiones)

El ejemplo que hemos desarrollado en este artículo busca presentar de forma sencilla y didáctica los principales fundamentos asociados al Método Simplex. Cabe destacar que ha sido necesario para la aplicación del algoritmo llevar el modelo original a su forma estándar que como se discutió anteriormente puede tener distintas representaciones según la bibliografía que se consulte.

En este contexto, cada problema de Programación Lineal en su forma estándar cumple con las siguientes propiedades establecidas en el Teorema Fundamental de la Programación Lineal:

Si el problema no tiene solución óptima entonces es no-acotado o infactible.
Si tiene una solución factible, tiene una solución básica factible.
Si el problema tiene solución óptima, tiene una solución básica factible óptima.

Cabe destacar que no siempre se dispone de una solución básica factible en las variables originales del modelo (luego de llevar el problema a su forma estándar). Si bien existen diversas estrategias algorítmicas para enfrentar esta dificultad, se propone al lector revisar los tutoriales que hemos desarrollado sobre esta problemática, en particular respecto al Método Simplex de 2 Fases, Método de la M Grande y Método Simplex Dual.

Adicionalmente con el objetivo de resumir algunas ideas principales del algoritmo hemos preparado una infografía que hemos llamado 10 Cosas que Necesitas saber sobre el Método Simplex.

Finalmente quisiéramos recordar a nuestros usuarios que en el Blog de Gestión de Operaciones se pueden encontrar a la fecha más de 80 publicaciones relativas a la Programación Lineal y la Investigación de Operaciones. De modo de favorecer una rápida búsqueda ingresa al menú Cómo Comenzar. Por último agradeceríamos compartir y difundir este material en la medida que haya sido considerado útil y evaluar este tutorial utilizando las estrellas al final de esta publicación.

Informes de Sensibilidad en Premium Solver Pro (Interpretación)

Las ventajas que ofrece la utilización de una herramienta de optimización profesional como Premium Solver Pro son múltiples y son rápidamente identificadas por quienes comienzan a formarse en el apasionante mundo de la Investigación de Operaciones. Respecto a este tema en particular he tenido el honor de publicar un artículo (en inglés) en el Blog del prestigioso sitio de FrontlineSolvers (desarrolladores del complemento Solver para Excel) llamado How to Correctly Interpret Sensitivity Reports in Premium Solver. En este contexto a continuación presentamos la traducción del mismo a español teniendo en cuenta que parte mayoritaria de nuestros lectores son de países de habla hispana.

En mi experiencia como profesor de Investigación de Operaciones he constatado de forma directa los beneficios de implementar computacionalmente modelos de optimización de distinta complejidad en un ambiente de aprendizaje intuitivo y al mismo tiempo confiable. En este sentido los alumnos adquieren rápidamente las destrezas suficientes para resolver problemas de optimización de distinto tamaño en una plataforma conocida como resulta ser Excel.

Cabe destacar adicionalmente que Premium Solver Pro no solo nos permite resolver modelos de optimización, también ofrece la oportunidad de generar Informes de Sensibilidad una vez alcanzada la solución óptima y valor óptimo de un modelo base. En este contexto el análisis de sensibilidad o postoptimal buscar analizar el impacto que tiene en los resultados de un modelo la modificación de uno o varios parámetros del mismo.

Un Informe de Sensibilidad de Premium Solver Pro se divide en 3 partes:

Función objetivo
Celdas variables
Restricciones

A continuación presentamos un sencillo modelo de Programación Lineal el cual será implementado computacionalmente, obteniendo el Informe de Sensibilidad que analizaremos en detalle con el objetivo de interpretarlo de forma correcta.

Luego de utilizar Premium Solver Pro para resolver el modelo anterior se alcanza la solución óptima $x_{1}=3$ y $x_{2}=6$ , con valor óptimo $V(PL)=342$ .

A continuación podemos obtener el Informe de Sensibilidad accediendo al módulo Reports > Optimization > Sensitivity, tal cual se muestra a continuación:

Una vez que solicitemos el Informe de Sensibilidad se generará una nueva hoja en el archivo Excel que estemos trabajando con el reporte de los resultados. Para el ejemplo propuesto en este artículo los resultados son los siguientes:

A continuación detallaremos cómo interpretar cada una de las 3 partes que nos ofrece el Informe de Sensibilidad de Solver.

Objective Cell (Max): Se observa que el valor óptimo, es decir, el valor de la función objetivo del problema de maximización al ser evaluada en la solución óptima alcanzada es de 342. Dicho valor se obtiene de: $V(PL)=(34)*3+(40)*6=342$ .

Decision Variable Cells: En esta sección se puede identificar la solución óptima (valores bajo la columna etiquetada como Final Value), los coeficientes o parámetros en la función objetivo (valores en la columna Objective Coefficient), el aumento permisible y la disminución permisible para cada uno de los coeficientes de forma individual en la función objetivo que permite garantizar que se conserva la actual solución óptima.

Por ejemplo, consideremos el coeficiente $c_{1}=34$ asociado a la variable de decisión $x_{1}$ en la función objetivo de maximización. La disminución permisible para dicho parámetro es de 7,333 aprox (equivalente a 22/3) unidades y el aumento permisible de 6, de modo que si $c_{1}\epsilon [34-\frac{22}{3},34+6]$ ==> $c_{1}\epsilon [26,\bar{6},40]$ se conserva la solución óptima original (notar que se asume para este análisis que el resto de los parámetros del modelo mantienen sus valores iniciales). De forma análoga recomendamos al lector verificar que el intervalo de variación para $c_{2}$ que conserva la actual solución óptima es $c_{2}\epsilon [34,51]$ .

Constraints: Un primer aspecto a observar es si una restricción se encuentra activa al ser evaluada en la solución óptima. Una restricción activa es aquella que se satisface en igualdad. Por ejemplo, se puede ver que para las Restricciones 1 y 2 el valor bajo la columna Final Value es idéntico al lado derecho de la restricción o Constraint R.H. Side. Dicho de otra forma, dado que las Restricciones 1 y 2 son activas en el óptimo, la solución óptima del problema propuesto se puede obtener mediante la resolución de un sistema de ecuaciones con 1 y 2 activas. Notar que adicionalmente la Restricción 3 si bien se satisface no se cumple en igualdad.

También resulta de interés interpretar lo que se conoce como Precio Sombra de una restricción.

El Precio Sombra corresponde a la tasa de cambio del valor óptimo de un modelo de Programación Lineal ante la modificación marginal del lado derecho de una restricción. Se entiende por una modificación marginal aquella que permite conservar la base óptima del problema (idénticas variables básicas originales en el caso del Método Simplex) o la geometría del problema (mantener las restricciones activas originales).

Dada la definición anterior es natural comprender que el Precio Sombra de la Restricción 3 sea cero. Si el lado derecho representa la disponibilidad de un recursos (por ejemplo, horas hombre, unidades de materia prima, etc), en la solución óptima original se utiliza 12 de las 16 unidades disponibles (que es consistente con una disminución permisible de 4 unidades y un aumento permisible de 1E+30 o infinito) para el recurso. Adicionalmente como la Restricción 3 no es activa, cualquier variación del lado derecho de dicha restricción en el intervalo $b_{3}\epsilon [12,+\infty[$ no solo conserva el valor óptimo, sino también la solución óptima original.

El caso de las Restricciones 1 y 2 es diferente. Por ejemplo, si aumenta en una unidad el lado derecho de la Restricción 1, pasando de 48 a 49 unidades (notar que el aumento permisible para dicho parámetro es de 6 unidades) el valor óptimo aumentará de forma proporcional al Precio Sombra de dicha restricción: $V(\bar{P})=V(P)+\Delta b_{1}*\pi _{1}=342+(49-48)*3=345$ . De forma análoga si, por ejemplo, en vez de aumentar el lado derecho de la Restricción 1, disminuye de 48 a 45 (disminución de 3 unidades que está dentro del rango permitido), el nuevo valor óptimo será: $V(\bar{P})=V(P)+\Delta b_{1}*\pi _{1}=342+(45-48)*3=333$ . Recomendamos al lector verificar directamente estos resultados luego de reoptimizar ante los cambios propuestos.

En síntesis queda en evidencia que la utilidad de Premium Solver Pro va más allá de implementar y resolver computacionalmente un modelo de optimización. En este sentido interpretar de forma correcta el análisis de sensibilidad que nos ofrece genera un ahorro de tiempo frente al escenario de reoptimizar que muchas veces es evitable, además de que nos permitir comprender de mejor forma la estructura de una solución óptima, que no sólo se limita a identificar cuál es el valor que alcanzan las variables de decisión en la resolución computacional.

Qué es la Programación Entera

¿Qué es la Programación Entera?: Un modelo de Programación Entera es aquel cuya solución óptima tiene sentido solamente si una parte o todas las variables de decisión toman valores restringidos a números enteros, permitiendo incorporar en el modelamiento matemático algunos aspectos que quedan fuera del alcance de los modelos de Programación Lineal.

En este sentido los algoritmos de resolución de los modelos de Programación Entera difieren a los utilizados en los modelos de Programación Lineal, destacándose entre ellos el Algoritmo de Ramificación y Acotamiento (o Branch & Bound), Branch & Cut, Planos Cortantes, Relajación Lagrangeana, entre otros.

Los modelos de Programación Entera se pueden clasificar en 2 grandes áreas: Programación Entera Mixta (PEM) y Programación Entera Pura (PEP).

Programación Entera Mixta (PEM)

A esta categoría pertenecen aquellos problemas de optimización que consideran variables de decisión enteras o binarias pero no de forma exclusiva. De esta forma un problema de PEM puede considerarse como un híbrido entre distintas categorías de modelamiento, siendo un caso típico aquel que considera la mezcla de variables enteras y variables continuas (estas últimas características de los modelos de Programación Lineal). A modo de ejemplo los siguientes artículos que hemos abordado en el Blog dan cuenta de modelos de Programación Entera Mixta:

Programación Entera Pura (PEP)

En esta categoría encontramos aquellos modelos de Programación Entera que consideran exclusivamente variables de decisión que adoptan valores enteros o binarios. Un ejemplo de ello son las siguientes aplicaciones:

Problema de Asignación
Problema de Corte de Rollos
Selección de Invitados a una Boda
Programación de la Explotación Forestal
Problema de la Mochila

Notar que en los problemas anteriores (PEP) el conjunto de las soluciones factibles (o dominio de soluciones factibles) es finito. Esto ocurrirá generalmente con los problemas de Programación Entera (puros).

Adicionalmente resulta interesante hacer un contrastes entre las propiedades de un modelo de Programación Lineal (PL) y uno de Programación Entera (PE). A continuación se presentan 2 modelos de optimización que se diferencian únicamente en que al segundo de ellos (PE) se le exige que las variables de decisión adopten valores enteros.

Para los problemas propuestos realizamos una representación gráfica haciendo uso del software Geogebra. El dominio de soluciones factibles del Problema Lineal (PL) corresponde al área achurada de color verde. Por otro lado el dominio de soluciones factibles del Problema Entero (PE) es enumerable y corresponde a las coordenadas denotadas por A, E, F, B, G, H, I, J, K, C, L, M, D (que es un subconjunto del dominio de factibilidad del PL). En este caso en particular la solución óptima de ambos problemas coincide (en el vértice C), no obstante, perfectamente podrían ser distintas (bastaría con modificar los parámetros del problema).

En este contexto y dada la naturaleza de los problemas propuestos, el valor óptimo del Problema Lineal (PL) será una cota superior del valor óptimo del Problema Entero (PE). También se concluye que el dominio de soluciones factibles de un modelo de Programación Lineal (cuando existe) representa un conjunto convexo (los problemas de Programación Lineal son convexos) y en el caso del problema de Programación Entera Pura su conjunto de soluciones factibles es discreto.

Adicionalmente según tratamos en el artículo Por qué no aparece el Informe de Confidencialidad (o Informe de Sensibilidad) en Solver de Excel se debe tener en cuenta que en la utilización de software para la resolución computacional del modelos de Programación Entera no tendremos acceso a los reportes de sensibilidad como en el caso de la implementación de modelos de Programación Lineal. De esta forma ante la necesidad de analizar el impacto en los resultados ante la modificación de los parámetros del problema será necesario reoptimizar ante la información que brinde el o los nuevos escenarios.

Es importante destacar que las aplicaciones de la Programación Entera no reemplaza la versatilidad que ofrece el disponer de modelos de Programación Lineal. Más aún, se pueden considerar estas categorías de modelamiento matemático como complementarias en el ámbito de la Investigación de Operaciones.

En este sentido en términos abstractos los modelos de Programación Entera imponen un desafío mayor al momento de la resolución en comparación a las propiedades simplificadoras que están asociadas a los problemas de Programación Lineal. De esta forma se espera que el tomador de decisiones sea capaz de evaluar la relación rigurosidad del modelado con el costo (complejidad) de la resolución del mismo.