METODO SIMPLEX EJEMPLOS

METODO SIMPLEX

El método simplex está basado fundamentalmente en este concepto. Careciendo de la ventaja visual asociada con la representación gráfica del espacio de soluciones, el método simplex emplea un proceso iterativo que principia en un punto extremo factible, normalmente el origen, y se desplaza sistemáticamente de un punto extremo factible a otro, hasta que se llega por último al punto óptimo. 

Existen reglas que rigen la selección del siguiente punto extremo del método simplex:

1.  El siguiente punto extremo debe ser adyacente al actual.
2. La solución no puede regresar nunca a un punto extremo considerado con la anterioridad. 

El algoritmo simplex da inicio en el origen, que suele llamarse solución inicial. Después se desplaza a un punto extremo adyacente. La elección específica de uno a otro punto depende de los coeficientes de la función objetivo hasta encontrar el punto óptimo.

Al aplicar la condición de optimidad a la tabla inicial  seleccionamos a Xi como la variable que entra. En este punto la variable que sale debe ser una de las variables artificiales. 

Los pasos del algoritmo simplex son: 

1. Determinar una solución básica factible inicial.

2. Prueba de optimidad: determinar si la solución básica factible inicial es óptima y sólo si todos los coeficientes de la ecuación son no negativos ( >= 0 ). Si es así, el proceso termina; de otra manera se lleva a cabo otra interacción para obtener la nueva solución básica factible inicial.

3.  Condición de factibilidad.- Para todos los problemas de maximización y minimización, variable que sale es la variable básica que tiene la razón más pequeña (positiva). Una coincidencia se anula arbitrariamente.

4.  Seleccionar las variables de holgura como las variables básicas de inicio.

5.  Selecciona una variable que entra de entre las variables no básicas actuales que, cuando se incrementan arriba de cero, pueden mejorar el valor de la función objetivo. Si no existe la solución básica es la óptima, si existe pasar al paso siguiente.

6.  Realizar el paso iterativo.

a) Se determina la variable básica entrante mediante la elección de la variable con el coeficiente negativo que tiene el valor mayor valor absoluto en la ecuación. Se enmarca la columna correspondiente a este coeficiente y se le da el nombre de columna pivote.

b)  Se determina la variable básica que sale; para esta, se toma cada coeficiente  positivo (>0) de la columna enmarcada, se divide el lado derecho de cada renglón entre estos coeficientes, se identifica la ecuación con el menor cociente y se selecciona la variable básica para esta ecuación.

c)  Se determina la nueva solución básica factible construyendo una nueva tabla en la forma apropiada de eliminación de Gauss, abajo de la que se tiene. Para cambiar el coeficiente de la nueva variable básica en el renglón pivote a 1, se divide todo el renglón entre el número pivote, entonces 

renglón pivote nuevo  = renglón pivote antiguo
                                       número pivote 

para completar la primera iteración es necesario seguir usando la eliminación de Gauss para obtener coeficientes de 0 para la nueva variable básica Xj en los otros renglones, para realizar este cambio se utiliza la siguiente fórmula: 

renglón nuevo = renglón antiguo - ( coeficiente de la columna pivote X renglón pivote  nuevo)

cuando el coeficiente es negativo se utiliza la fórmula:

renglón nuevo = renglón antiguo + (coeficiente de la columna pivote X renglón pivote nuevo) 

EJERCICIO DE MAXIMIZACION SIMPLEX 

La mejor manera de aprender el método simplex es resolviendo problemas de programación lineal Para esto realicemos el siguiente ejercicio. 

Una fábrica productora de embalajes plásticos, elabora dos tipos de containers de 3.750 c.c. y 4.000 c.c. Los datos de producción se presentan en la tabla adjunta. La persona encargada del termo-formado no puede trabajar más de 40 horas a la semana y los recursos económicos de la fábrica no permiten inversiones mayores de US$1.000 de materiales por semana ¿cuántos containers de cada tipo debería fabricar la industria, para obtener la utilidad máxima? 

TIPO DE TRABAJO POR COSTO POR UTILIDAD POR CONTAINER ,CONTAINER, CONTAINER, CONTAINER 

3750 (A) 6 HORAS $200 $240 4000 (B) 5 HORAS $100 $160 

 PASO 1: Establezca el modelo: 

Cómo es posible que haya más de dos variables, es usual representarlas como X1 X2 X3, etc. 

Variables independientes 

X1: Cantidad de container tipo A

X2: Cantidad de container tipo B 

Restricciones 

C1: 6X1 + 5X2 Restricción de tiempo

C2: 200X1 + 100X2 Restricción de dinero

C3: X1

C4: X2 

Función objetivo: 

Z= 240X1 + 160X2 (Z es la utilidad) 

PASO 2: Convierta las desigualdades de restricciones en ecuaciones 

6X1+5X2=40 

Observe que si el número total de horas es menor que 40, implica que algunas horas no se aprovecharon, esto significa que C1 se podría escribir como: 

C1=6X1+5X2+S1=40 

S1 corresponde a la cantidad de horas no utilizadas, S1 

S1 se denomina variable de holgura, de holgura debido a que establece el período libre entre las horas empleadas (pueden ser menos de 40) y las horas disponibles (exactamente 40). El introducir la variable de holgura convierte las desigualdades de restricción en ecuaciones, lo que implica que se puedan utilizar matrices y el método de Gauss Jordán para resolver el problema. 

C2:200X1 + 100X2

C2:200X1 + 100X2+S2 

Nuevamente S2 es una variable de holgura que establece el dinero no utilizado, S2 . S2 determina la cantidad no empleada de dinero (menor a US$1.000) y el dinero disponible (igual a US$1.000)

Las restricciones C3:X1 y C4: X2 son condiciones de no negatividad. 

PASO 3: Reescriba la función objetivo con todas las variables en el lado izquierdo 

Z = 240X1 + 160X2

-240X1 - 160X2+ Z =0 

Incluyendo las variables de holgura 

-240X1–160X2+0S1+0S2+Z=0

C1:6X1+5X2+S1=40

C2:200X1+100X2+S2=1.000 

Recuerde que S1= horas no utilizadas S2= dinero no utilizado 

PASO 4: Plantee una matriz a partir de las restricciones y de la función objetivo reescritas. 

C1 = 6X1 + 5X2 + S1 + 0S2 + 0Z =40

C2=200X1 + 100X2 + 0S1 + S2 + 0Z =1000

Función objetivo –240X1 - 160X2 + 0S1 + 0S2 + Z = 0

El método símplex requiere el examen de una serie de matrices. Recuerde que en el método gráfico se requería que examináramos una serie de puntos. En forma análoga el método símplex (cada matriz) nos proporciona un punto esquina de la región de soluciones factibles, sin necesidad de graficar la región.

Una última matriz símplex nos proporcionará el punto esquina óptimo (la solución al problema). 

PASO 5: Determine la solución posible correspondiente a la matriz. 

La solución factible se determina aplicando un método semejante al de Gauss-Jordan, utilizando como siempre un pivote (1) para obtener una matriz en la forma escalonada reducida por renglón.

El valor de la variable que encabeza cada una de las columnas se obtiene leyendo hacia abajo la columna, volteando en 1 y deteniéndose al final del renglón. 

La matriz símplex inicial (1) no está en forma escalonada reducida por renglón . Las columnas S1 , S2 y Z si están en forma escalonada reducida, luego utilizando el esquema anterior. 

F =

Observe que S1=40

S2=1000

Z=0

Y consideremos, inicialmente X1=0 X2=0 

Luego una solución factible corresponde a la matriz 

(X1 X2 S1 S2) = (0,0,40,1000) con Z=0 

Lo anterior es una solución factible por que si X1 e X2=0 se satisfacen las cuatro restricciones.

Esta solución factible implica: que no se fabricaría el container tipo A y B, dispondríamos de 40 horas no trabajadas y US$1.000 no gastados, luego no habría utilidad.