El Método Símplex Lineal

El Método Símplex Lineal

El Método Símplex como herramienta de programación lineal fue desarrollado para la época de los años cuarenta por George Dantzing, un joven matemático. El método constituye una forma sistemática y de búsqueda intensiva a través de todas las posibles soluciones para obtener una solución óptima. Ello resulta de gran utilidad debido a su eficiencia. Además es fácil programarlo en una computadora. En contraste con el análisis gráfico, este método permite el uso de muchas variables. También permite la aplicación de cantidades de restricciones lineales con signos; mayores e igual, menores e igual y de igualdad. En comparación con el método gráfico, el método símplex tiene como punto de partida el origen siendo este la solución inicial al problema. El método prueba todos los puntos extremos gráficos aunque no necesariamente se detiene en todos los vértices. Por otro lado utiliza el concepto de álgebra de matrices en una serie de tablones.

EL PROBLEMA DE MAXIMIXACIÓN SÍMPLEX

FORMULACIÓN INICIAL

Utilizando el siguiente ejemplo estableceremos la formulación inicial símplex y demostraremos la mecánica del método y su interpretación. El gerente de la Relojería la Torre desea conocer la ganancia máxima que se puede obtener de la producción y venta de dos clases de relojes económicos digitales de pulsera. La ganancia que se obtiene por la producción y venta de un reloj de hombre es de $4 y de $6 para un reloj de mujer. La empresa cuenta con 120 horas semanales para la producción de los relojes y 100 horas para la inspección y empaque de estos. La fabricación de un reloj de hombre requiere 2 horas de producción y 2 horas de inspección y empaque. Mientras que un reloj de mujer requiere 4 horas de producción y 3 horas de inspección y empaque. La formulación del problema para esta situación es la siguiente:

Maximizar Z = $4X1+ $6X2

Sujeto a: 2X1+ 4X2≤120 (horas de producción)

2X1+ 3X2≤100 (horas de inspección y empaque)

(X1, X2≥0)

Donde X1= cantidad de relojes de hombre que se producen semanalmente.

X2= cantidad de relojes de mujer que se producen semanalmente.

3

Luego de formular el problema procedemos a trabajar primero con las restricciones y luego con la función objetivo. Comenzamos cambiando los signos de las restricciones de desigualdades a igualdades. El método símplex requiere la conversión de las restricciones con signos de desiguales a igualdades estrictas. Esto se debe a que el método usa álgebra de matrices en donde todas las relaciones matemáticas serán a base de ecuaciones lineales y que a su vez deben contener todas las variables. Llamaremos a este procedimiento como aumento de las restricciones y de la función objetivo.

AUMENTO DE LAS RESTRICCIONES Y DE LA FUNCIÓN OBJETIVO

El aumento de las restricciones y de la función obj etivo surge porque el método símplex comienza por definición en el origen es decir en el punto (0,0) y de este punto al valor de las restricciones existe una diferencia. Esta diferencia se conoce como holgura y por cada restricción que tenga el problema tendremos una o más variables las cuales el método tomará en consideración.

Comencemos con la primera restricción: 2X1+ 4X2≤120 (horas de producción)

Al analizar la restricción hallamos que el lado izquierdo es menor que el lado derecho. Para poder hacer el cambio de la desigualdad a igualdad tendremos que añadir una variable que absorba la diferencia entre ambos lados. En este caso la variable representa recursos no utilizados o recursos disponibles. Esta variable se conoce como variable de holgura o "Slack".

La primera restricción se reformula asignándole una variable de holgura positiva conocida como S1, la que aparecerá de la siguiente forma: 2X1+ 4X2+ S1= 120. La variable S1 se relaciona con la primera restricción. De manera parecida procedemos a reformular la segunda restricción: 2X1+ 3X2≤100 (horas de inspección y empaque).

Encontramos que esta restricción también posee un signo de desigualdad que es menor o igual por lo tanto el lado izquierdo es menor que el derecho. Para poder llevar la ecuación a igualdad tendremos que también añadir una variable de holgura positiva que absorba la desigualdad. De tal manera la segunda restricción se reformula de la siguiente forma: 2X1+ 3X2+ S2= 100 en donde S2 se relaciona con la segunda restricción. Tenemos que ambas restricciones se presentan de la siguiente forma:2X1+ 4X2+ S1= 1202X1+ 3X2+ S2= 100

La variable de holgura S1representa las horas de producción no utilzazas y la variable S2 representa las horas de inspección y empaque no utilizadas. Si por definición el método símplex comienza en el origen (0,0) donde X1= 0 y X2= 0,entonces esto significa que por ahora no hay producción de relojes de ninguna clase (X1=relojes de hombre y X2= relojes de mujer). El no tener producción significa que los recursos disponibles son 120 horas de producción y100 horas de inspección y empaque. Esta situación la representamos de la siguiente forma para la primera restricción: 2X1+44X2+ S1= 120 donde X1= 0 y X2= 0. Al sustituir los valores de X1y X2en la primera restricción tendremos el siguiente resultado: 2(0)+ 4(0) + S1= 120 por lo tanto S1= 120 horas disponibles es decir tenemos 120 horas de producción disponibles porque no hay producción alguna.

CUADRO INICIAL

Colocamos todos los coeficientes y constantes en un tablón. Esto simplifica el manejo de las ecuaciones y de la función objetivo. Veamos el siguiente modelo para un cuadroinicial.

X1 X2 S1 S2 Cj/bi

Cj= forma aumentada de los coeficientes de la función objetivo

Ci= coeficientes de las variables básicasa

ij= forma aumentada de los coeficientes de las restricciones o tasa de sustitución

bi= valores del lado derecho de las restricciones

z = valor de la función objetivo

Zj= reducción de ganancias, aumento en costos asociados con la introducción de una de sus valores en las columnas respectivas

Zj= Cj- Zj= índice de mejoramiento o renglón de criterio símplex

Ratio = límites introductorios

Busquemos ahora los valores para Zj. Si no se están fabricando relojes entonces los costos o la reducción en las ganancias tiene que ser cero así como el valor final de la función objetivo Z. Por ejemplo la producción de la variable de decisión real X1 (relojes de hombres) consume 2 horas de producción y 2 horas de inspección y empaque según lo indica sus coeficientes a ij o tasa de sustitución. Como no hay producción, la variable básica para la primera restricción o primer recurso será S1= 120 con un coeficiente C1=0, es decir 0 aportación a las ganancias. De igual forma sucede con la segunda restricción en donde C2= 0.

En conclusión no se están fabricando relojes de hombre ni de mujer (variables no básicas X1= 0 y X2= 0). Se tienen disponible 120 horas semanales de producción y 100 horas semanales de inspección y empaque (variables básicas S1y S2 respectivamente) para una ganancia semanal de $0.

MEJORANDO EL CUADRO INICIAL

Siempre selecciona el mejor coeficiente.

Como se está maximizando, el método escogerá el valor que otorgue el mayor

rendimiento, es decir el más positivo y el más negativo para casos de minimización.

Utilizando la solución del cuadro inicial, seleccionamos el mejor cambio en Zj , entre _Z1= 4 para la columna X1 y el _Z2= 6 para X2 y lo circulamos. Este mejor cambio nos

indicará qué variable no básica en la columna se convertirá en variable básica. Es decir,

qué variable se va a producir y que a su vez provea un mejor rendimiento o una nueva y

mejor solución al problema. También el mejor cambio en Zj, _Z2= 6 en este caso,

aumentará la ganancia actual de $0 por seis veces el numero de unidades entrantes,

relojes de mujer. El método seleccionará la variable X2 porque esta posee el mejor

cambio en Zj, circulamos la columna X2 y a esta columna se le conoce como la columna

pivote.

El método ha seleccionado la producción de relojes de damas, (X2) pero queremos

conocer cuántos relojes de mujer se van a manufacturar. Existen dos restricciones que

limitan la producción de los relojes de damas (X2) estas son: 2X1 + 4X2 + 1S1 + 0S2 =

120 (horas de producción) y 2X1 + 3X2 + 0S1 + 1S2 = 100 (horas de inspección y

empaque). Al analizar la primera restricción, 2X1 + 4X2 + 1S1 + 0S2 = 120 (horas de

producción) encontramos que todas las horas de producción se utilizan para fabricar la

variable X2 por lo tanto si la producción de una unidad de X2 toma 2 horas y se tienen en

existencia 120 horas entonces se manufacturarán 30 relojes, (120 horas ÷ 4 horas por

unidad = 30 relojes de damas). No obstante, para poder completar el proceso de

producción, debemos inspeccionar y luego empaquetar los relojes donde la cantidad

disponible de horas para el anterior proceso mencionado es de 100 horas.

11

El estudio de la segunda restricción, 2X1 + 3X2 + 0S1 + 1S2 = 100, demuestra que el

proceso de inspección toma 3 horas donde solo se pueden inspeccionar 33.33 relojes de

damas.2 Por lo tanto a pesar de que la segunda restricción indica que se puede

inspeccionar y empaquetar más relojes (33.33) de los que se pueden producir (30), en

realidad solo hay recursos para hacer 30 relojes. Si por error se decide manufacturar

33.33 relojes entonces habrá una deficiencia de 13.32 horas necesarias para completar

...