solución básica factible Archivos - Página 2 de 4

Método de la M Grande (o Gran M) en Programación Lineal

En el contexto de la aplicación del Método Simplex no siempre es inmediata la obtención de una solución básica factible inicial, en las variables originales del modelo. Para conseguir esto existen varios procedimientos como son el Método Simplex de 2 Fases y el Método de la M Grande (o Gran M) el cual abordaremos en este artículo. Para ello consideremos el siguiente modelo de Programación Lineal en 2 variables:

A continuación agregamos las variables no negativas $x_{3}$ (holgura restricción 1), $r_{1}$ (auxiliar restricción 2), $x_{4}$ (exceso restricción 3) y $r_{2}$ (auxiliar restricción 3). El modelo ahora es:

Donde el parámetro M es una constante positiva suficientemente grande para representar una penalización adecuada en la función objetivo. La tabla inicial del método esta dada por:

Antes de continuar con las iteraciones se debe procurar que el costo reducido de las variables $r_{1}$ y $r_{2}$ sean ceros. Para ello multiplicamos por -M la fila 2 y la fila 3 y luego sumamos a la fila 4, obteniendo lo siguiente:

Ahora debemos seleccionar que variable no básica ingresa a la base. El menor costo reducido corresponde a la variable $x_{1}$ en consecuencia dicha variable ingresa a la base. Luego calculamos el mínimo cuociente en dicha columna: $Min \begin{Bmatrix}{\frac{27/10}{3/10}, \frac{6}{1/2}, \frac{6}{3/5}}\end{Bmatrix}=9$ , el cual se alcanza en la fila 1, por tanto la variable $x_{3}$ deja la base. Se actualiza la tabla:

Siguiendo con las iteraciones ahora la variable $x_{2}$ entra a la base. El criterio de factibilidad indica que: $Min \begin{Bmatrix}{\frac{9}{1/3}, \frac{3/2}{1/3}, \frac{3/5}{1/5}}\end{Bmatrix}=3$ la variable $r_{2}$ abandona la base (el pivote se encuentra en la fila 3). Actualizamos la tabla:

Una nueva iteración indica que $x_{3}$ ingresa a la base. El mínimo cuociente en la respectiva columna es: $Min \begin{Bmatrix}{\frac{8}{20/3}, \frac{1/2}{5/3}}\end{Bmatrix}=3/10$ (recordar que se omiten denominadores menores a cero). Ahora el pivote se encuentra en la fila 2 y en consecuencia $x_{4}$ deja la base. Se actualiza la tabla:

Se ha alcanzado la solución óptima con $x_{1}=15/2$ y $x_{2}=9/2$ . Notar que las variables auxiliares (r1 y r2) son no básicas en el óptimo. El valor óptimo es 21/4 (notar que el signo esta cambiado).

Para una mejor comprensión de los resultados alcanzados a continuación se presenta la resolución gráfica del problema haciendo uso del software Geogebra. El dominio de soluciones factibles corresponde a la recta que une los vértices A y B. Adicionalmente se muestra la curva de nivel que pasa por la solución óptima (vértice B).

Teóricamente se espera que en la aplicación del Método de la M Grande las variables auxiliares sean no básicas en el óptimo. Si el modelo de Programación Lineal es infactible (es decir, si las restricciones no son consistentes), la iteración del Método Simplex final incluirá al menos una variable artificial como básica.

Adicionalmente la aplicación de la técnica de la M Grande implica teóricamente que M tiende a infinito. Sin embargo al usar la computadora M debe ser finito, pero suficientemente grande. En específico M debe ser lo bastante grande como para funcionar como penalización, al mismo tiempo no debe ser tan grande como para perjudicar la exactitud de los cálculos del Método Simplex, al manipular una mezcla de números muy grandes y muy pequeños.

Problema de Producción de Trajes y Vestidos resuelto con el Método Simplex

La empresa Trajes y Vestidos tiene en un momento dado que tomar una decisión sobre cómo maximizar el ingreso en la confección y venta de un tipo de traje y un tipo de vestido específico, que está teniendo demanda por la clientela. Al momento se tiene 80 yardas de tela de algodón y 120 yardas de tela de lana para la confección de los trajes y de los vestidos. Para la confección del traje se necesita 1 yarda de tela de algodón y 3 yardas de tela de lana. Mientras que para el vestido se necesita 2 yardas de tela de algodón y 2 yardas de tela de lana.

Para tomar la decisión de la mezcla de producto óptima para el Problema de Producción de Trajes y Vestidos, hace 3 tipos de escenarios:

Cuando ambas confecciones tienen un precio unitario de $30.
Cuando los trajes valen $40 y los vestidos $20.
Cuando los trajes valen $30 y los vestidos $20.

¿Cuántos vestidos y trajes hay que hacer para maximizar los ingresos?. Esto es, ¿con cuál mezcla de productos se maximiza los ingresos?. Resuelva el problema de Programación Lineal utilizando el Método Simplex.

Sea $x_{1}$ la cantidad de trajes a fabricar y $x_{2}$ la cantidad de vestidos a fabricar, se formulan los siguientes modelos de optimización para los 2 primeros escenarios (notar que por simple inspección se descarta inmediatamente el escenario 3 dado que de todos modos no podrá reportar ingresos mayores que el escenario 1 o 2).

En primera instancia resolveremos por el Método Simplex el problema correspondiente al escenario 1. Para ello agregamos las variables de holgura $x_{3}, x_{4}$ para la restricción de disponibilidad de yardas de algodón y disponibilidad de yardas de lana, respectivamente. De esta forma el problema en su forma estándar es:

El cual da origen a la siguiente tabla inicial del algoritmo:

Tanto la variable no básica $x_{1}$ como la variable no básica $x_{2}$ tienen costo reducido negativo de la misma magnitud. En este caso seleccionaremos de forma arbitraria la variable $x_{1}$ como aquella que ingresa a la base. Luego calculamos el cuociente mínimo en dicha columna: $Min \begin{Bmatrix}{\frac{80}{1}, \frac{120}{3}}\end{Bmatrix}=40$ , en consecuencia la variable $x_{4}$ deja la base.

Ahora ingresa a la base la variable $x_{2}$ . Calculamos nuevamente el criterio de factibilidad o mínimo cuociente en la columna de la variable $x_{2}$ obteniendo: $Min \begin{Bmatrix}{\frac{40}{4/3}, \frac{40}{2/3}}\end{Bmatrix}=30$ que determina que la variable $x_{3}$ deja la base.

La solución óptima es $x_{1}=20, x_{2}=30$ con valor óptimo (ingreso) de $1.500.

A continuación resolvemos el problema del escenario 2. Para ello llevamos el modelo a su forma estándar lo que da origen a la siguiente tabla inicial del Método Simplex:

Naturalmente la variable no básica $x_{1}$ ingresa a la base al tener ésta el costo reducido más negativo. Por otra parte la variable que deja la base de obtiene de $Min \begin{Bmatrix}{\frac{80}{1}, \frac{120}{3}}\end{Bmatrix}=40$ , por tanto $x_{4}$ deja la base y se actualiza la tabla.

Notar que estamos frente a la tabla óptima del segundo escenario donde la política de producción de trajes y vestidos que maximiza los ingresos es $x_{1}=40, x_{2}=0$ con valor óptimo (ingreso) de $1.600. En consecuencia se propone implementar la solución del escenario 2 que desde el punto de vista de los ingresos es la que logra una mayor recaudación dado los datos del problema.

Problema de Producción y Ensamblaje resuelto con el Método Simplex

El siguiente problema de Programación Lineal fue enviado por uno de nuestros lectores desde Puerto Rico. Consiste en determinar la política óptima de producción y ensamblaje de una empresa que se dedica a fabricar componentes para computadoras. A continuación los detalles de dicho problema el cual luego de su formulación (definición de las variables de decisión, función objetivo y restricciones) será resuelto a través del Método Simplex:

Problema de Producción y Ensamblaje

Una pequeña compañía fábrica tres componentes electrónicos de computadoras. Componente A requiere 2 horas de fabricación, 1 hora de ensamblaje y 1 hora de finalización; Componente B requiere 3 horas de fabricación, 1 hora de ensamblaje y 1 hora de finalización; y el Componente C requiere 2 horas de fabricación, 2 horas de ensamblaje y 1 hora de finalización. La compañía tiene a lo sumo 1.000 horas de labor en la fabricación, 800 horas de labor en el ensamblaje y 100 horas de finalización disponibles cada semana. Las ganancias de cada componente A, B y C, son $7, $8 y $10, respectivamente.

¿Cuántos componentes de cada tipo debe la compañía fabricar cada semana de manera que pueda maximizar sus ganancias? ¿Cuál es la ganancia máxima?. Resuelva el problema de Programación Lineal utilizando el Método Simplex.

Sea $x_{1}, x_{2}, x_{3}$ la cantidad de unidades a producir semanalmente del Componente A, B y C, respectivamente, un modelo de Programación Lineal que permite abordar el problema anterior es:

De modo de resolver el modelo a través del Método Simplex llevamos el mismo al formato estándar, agregando $x_{4}, x_{5}, x_{5}$ como variables de holgura de las restricciones 1, 2 y 3, respectivamente (fabricación, ensamblaje y finalización).

Lo que da origen a la siguiente tabla inicial del método:

Por el criterio del costo reducido más negativo ingresa a la base la variable $x_{3}$ . Luego calculamos el mínimo cuociente en dicha columna obteniendo: $Min \begin{Bmatrix}{\frac{1.000}{2}, \frac{800}{2}, \frac{100}{1}}\end{Bmatrix}=100$ , el pivote está en la fila 3 y en consecuencia $x_{6}$ deja la base. Se realiza entonces una iteración:

Notar que luego de una iteración las variables no básicas $x_{1}, x_{2}, x_{6}$ tienen costos reducidos mayores a cero, además las variables básicas cumplen con las condiciones de no negatividad, a saber, $x_{3}=100, x_{4}=800, x_{5}=600$ , lo que corresponde a una solución básica factible óptima. En consecuencia se propone producir exclusivamente 100 unidades del Componente C lo que reporta un valor óptimo (ganancia máxima) de $1.000.

Método de la Esquina Noroeste (Algoritmo de Transporte en Programación Lineal)

El Método de la Esquina Noroeste (o esquina superior izquierda) es una heurística que se aplica a una estructura especial de problemas de Programación Lineal llamada Modelo de Transporte, la cual permite asegurar que exista una solución básica factible inicial (no artificial). Otros métodos para la obtención de una solución básica de inicio son el Método de Costo Mínimo y Método de Aproximación de Vogel. En general, el Método de Vogel produce la mejor solución básica de inicio y el de la Esquina Noroeste la peor, sin embargo, el Método de la Esquina Noroeste implica el mínimo de cálculos.

El Método de la Esquina Noroeste comienza en la celda (ruta) correspondiente a la esquina noroeste, o superior izquierda, de la tabla (variable $x_{11}$ ). A continuación una descripción de los pasos:

Paso 1: Asignar todo lo posible a la celda seleccionada y ajustar las cantidades asociadas de oferta y demanda restando la cantidad asignada.

Paso 2: Salir de la fila o la columna cuando se alcance oferta o demanda cero, y tacharlo, para indicar que no se pueden hacer más asignaciones a esa fila o columna. Si una fila y una columna dan cero al mismo tiempo, tachar sólo uno (la fila o columna) y dejar una oferta (demanda) cero en la fila (columna) que no se tachó.

Paso 3: Si queda exactamente una fila o columna sin tachar, detenerse. En caso contrario, avanzar a la celda de la derecha si se acaba de tachar una columna, o a la de abajo si se tachó un reglón. Seguir con el Paso 1.

Método de la Esquina Noroeste

Para ilustrar la aplicación del Método de la Esquina Noroeste consideremos el siguiente problema balanceado de transporte que considera 3 silos productos (oferta) que satisfacen las necesidades de 4 molinos (demanda). El algoritmo de transporte se basa en la hipótesis que el modelo está balanceado, es decir, que la demanda total es igual a la oferta total (si el modelo no está balanceado siempre se podrá aumentar con una fuente ficticia o un destino ficticio para restaurar el equilibrio o balance).

Los costos unitarios de transporte desde el silo i al molino j $c_{ij}$ se representan en la esquina superior derecha de cada cuadro. Por ejemplo el costo unitario de enviar una unidad de producto desde el silo 1 al molino 1 es de $10. Adicionalmente los silos 1, 2 y 3 tienen capacidad u oferta de 15, 25 y 10 unidades, respectivamente. Por otra parte los molinos 1, 2, 3 y 4 tienen requerimientos o demanda de 5, 15, 15 y 15 unidades, respectivamente. El modelo esta balanceado (suma oferta = suma demanda = 50 unidades).

Al aplicar el Método de la Esquina Noroeste al ejemplo anterior se obtienen los siguientes resultados. Las flechas indican el orden en el que se generan las cantidades asignadas:

La cantidad asignada a la celda $x_{11}$ son 5 unidades, dado que si bien el silo 1 tiene capacidad de 15 unidades, el molino 1 sólo necesita (demanda) 5 unidades (no se realizan más asignaciones a la columna 1 correspondiente al molino 1).
A continuación nos movemos a la derecha y asignamos lo máximo posible (10 unidades remanentes) a la celda $x_{12}$ (con lo cual se completa la capacidad del silo 1 y en consecuencia no es posible seguir realizando asignaciones en la fila 1).
Luego asignamos 5 unidades a la celda $x_{22}$ lo cual es por cierto menor que la capacidad del silo 2 pero lo suficiente para satisfacer los requerimientos del molino 2 (ahora no es posible generar asignaciones adicionales a la columna 2).
Nos movemos a la derecha y se asignan 15 unidades del silo 2 al molino 3 ( $x_{23}=15$ ) lo que cubre inmediatamente los requerimientos del molino 3 (no es necesario asignar más en la columna 3).
Nuevamente nos movemos a la derecha y asignamos lo máximo posible (5 unidades que es la capacidad remanente del silo 2, es decir, $x_{24}=5$ ) con lo cual el silo 2 opera a máxima capacidad (ahora ya no es posible nuevas asignaciones en la fila 2).
Finalmente se asignan 10 unidades del silo 3 al molino 4 ( $x_{34}=10$ ) cubriendo la demanda de dicho molino (y la capacidad del correspondiente silo).

En consecuencia la solución básica factible inicial es: $x_{11}=5, x_{12}=10, x_{22}=5, x_{23}=15, x_{24}=5, x_{34}=10$ que reporta un costo del programa (valor en la función objetivo) de: Z=5(10)+10(2)+5(7)+15*(9)+5(20)+10*(18)=$520. Notar que si se implementa computacionalmente el problema anterior haciendo uso de Solver de Excel y utilizando como motor de resolución Simplex_LP se alcanza la siguiente solución óptima (celdas amarillas) con costo mínimo (valor óptimo) de $435.

Qué es una Solución Óptima Degenerada en Programación Lineal

En la aplicación del Método Simplex al hacer el cálculo del mínimo cuociente o condición de factibilidad, se puede romper un empate en la razón o cuociente mínimo en forma arbitraria. En este caso, al menos una variable básica será cero en la siguiente iteración, afirmándose en este caso que la nueva solución es degenerada. La implicancia práctica de dicha condición indica que el modelo tiene al menos una restricción redundante.

Solución Óptima Degenerada

Consideremos el siguiente modelo de Programación Lineal el cual resolveremos a través del Método Simplex y que de forma complementaria representaremos gráficamente con Geogebra:

Llevamos el problema anterior a su forma estándar de minimización, agregando $x_{3}$ y $x_{4}$ , como variables de holgura de las restricciones 1 y 2, respectivamente.

Que da origen a la siguiente tabla inicial del Método Simplex:

Para favorecer la rapidez de convergencia del algoritmo seleccionamos $x_{2}$ como la variable que ingresa a la base. A continuación calculamos el criterio de factibilidad (mínimo cuociente): $Min \begin{Bmatrix}{\frac{8}{4}, \frac{4}{2}}\end{Bmatrix}=2$ (al existir empate seleccionaremos arbitrariamente la variable $x_{3}$ como aquella que deja la base. Luego se actualiza la tabla:

Ahora $x_{1}$ ingresa a la base. El criterio de factibilidad determina que: $Min \begin{Bmatrix}{\frac{2}{1/4}, \frac{0}{1/2}}\end{Bmatrix}=0$ $x_{4}$ deja la base. Se realiza entonces una nueva iteración:

Se alcanza la solución óptima degenerada del problema lineal. Notar que $x_{1}=0, x_{2}=2, x_{3}=0, x_{4}=0, V(P)=18$ . Como éste es un problema bidimensional, la solución está sobredeterminada y una de las restricciones es redundante tal como se corrobora en la representación gráfica:

En la práctica conocer que algunos recursos (como los asociados a una restricción) son superfluos puede ser valioso durante la implementación de la solución. Desde el punto de vista teórico, la degeneración tiene dos implicaciones: se genera el fenómeno de ciclos o círculos (es posible que el Método Simplex repita una serie de iteraciones sin mejorar el valor de la función objetivo, tal como se observo en el ejemplo anterior e incluso eventualmente nunca terminar los cálculos); el segundo aspecto teórico surge al examinar las iteraciones 1 y 2. Las dos, aunque difieren en la clasificación de las variables básicas y no básicas, producen valores idénticos para todas las variables y el valor objetivo ( $x_{1}=0, x_{2}=2, x_{3}=0, x_{4}=0, V(P)=18$ ).