Metodo Simplex Metodo Complejo

INTRODUCCION

El método Simplex es un algoritmo iterativo que permite mejorar la solución con cada paso sucesivo.

El algoritmo termina cuando no se puede seguir mejorando más la solución.

Se parte de una solución básica inicial para la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore la anterior solución.

JUSTIFICACION

El método simplex es un es un método algebraico alterativo que permite ir mejorando la solución a cada paso del procedimiento comenzando con una solución básica (punto extremo) y modificando esta a lo largo del proceso, a través de la inclusión y exclusión de una variable; siempre aumentando la utilidad (o reduciendo el costo) hasta encontrar una solución óptima

OBJETIVO:

Resolver, a través del Método Simplex, problemas de optimización restringida considerando la importancia de éste para la toma de decisiones y el manejo de recursos en el ámbito educativo.

METODO GRAFICO, METODO SIMPLEX

MÉTODO GRÁFICO

El método gráfico se utiliza para la solución de problemas de PL, representando geométricamente a las restricciones, condiciones técnicas y el objetivo.

El modelo se puede resolver en forma gráfica si sólo tiene dos variables. Para modelos con tres o más variables, el método gráfico es impráctico o imposible.

Cuando los ejes son relacionados con las variables del problema, el método es llamado método gráfico en actividad. Cuando se relacionan las restricciones tecnológicas se denomina método gráfico en recursos.

Los pasos necesarios para realizar el método son siete:

1. graficar las soluciones factibles, o el espacio de soluciones (factible), que satisfagan todas las restricciones en forma simultánea.

2. Las restricciones de no negatividad Xi>= 0 confían todos los valores posibles.

3. El espacio encerrado por las restricciones restantes se determinan sustituyendo en primer término <= por (=) para cada restricción, con lo cual se produce la ecuación de una línea recta.

4. trazar cada línea recta en el plano y la región en cual se encuentra cada restricción cuando se considera la desigualdad lo indica la dirección de la flecha situada sobre la línea recta asociada.

5. Cada punto contenido o situado en la frontera del espacio de soluciones satisfacen todas las restricciones y por consiguiente, representa un punto factible.

6. Aunque hay un número infinito de puntos factibles en el espacio de soluciones, la solución óptima puede determinarse al observar la dirección en la cual aumenta la función objetivo.

7. Las líneas paralelas que representan la función objetivo se trazan mediante la asignación de valores arbitrarios a fin de determinar la pendiente y la dirección en la cual crece o decrece el valor de la función objetivo.

EJEMPLO. MAXIMIZAR RESTRICCIONES:

Z = 3X1 + 2X2

X1 + 2X2 <=6 (1)

2X1 + X2 <=8 (2)

-X1 + X2 <=1 (3)

X2 <= 2 (4)

X1 >= 0 (5)

X2 >= 0 (6)

CONVIRTIENDO LAS RESTRICCIONES A IGUALDAD Y REPRESENTÁNDOLAS GRÁFICAMENTE SE TIENE:

X1 + 2X2 = 6 (1)

2X1 + X2 = 8 (2)

-X1 + X2 = 1 (3)

X2 = 2 (4)

X1 = 0 (5)

X2 = 0 (6)

Solución

Punto---(X1, X2)----Z

A --------(0, 0)-------0

B --------(4, 0)-------12

C --------(3.3, 1.3)---12.6

( óptima )

D...........(2, 3)..........12

E...........(1, 3)...........9

F...........(0, 2)..........4

Tabla 2. Solución Método Gráfico

.

Para obtener la solución gráfica, después de haber obtenido el espacio de solución y graficada la función objetivo el factor clave consiste en decidir la dirección de mejora de la función objetivo.

MÉTODO SIMPLEX.

En la solución gráfica observamos que la solución óptima está asociada siempre con un punto extremo del espacio de soluciones. 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 ( 10 ) :

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)

TABLA SIMPLEX como se capturaría la solución básica factible inicial en el siguiente ejemplo:

sea:

Maximizar Z = 2X1+4X2

sujeto a:

2X1+ X2<= 230

X1+ 2X2<= 250

X2<= 120

todas las X1,X2>=0

Seleccione la variable que entra y la variable que sale de la base:

Entra X2 y sale S3, se desarrolla la nueva tabla solución y se continua el proceso iterativo hasta

Encontrar la solución óptima si es que está existe. Tabla Optima:

Solución: Z = $500 fabricando X1=10 X2=120 Sobrante

...