Metodo Simplex

ÍNDICE DE CONTENIDOS

CAPITULO 1. Introducción. 2

CAPITULO 2. Planteamiento del problema. 3

CAPITULO 3. Algoritmo de solución. 5

CAPITULO 4. Comparación de algoritmos. 6

CAPITULO 5. Traza del algoritmo. 8

CAPITULO 6. Conclusiones. 14

ÍNDICE DE ILUSTRACIONES

Figura 1. Representación de conjuntos convexos y no convexos. 3

Figura 2. Trayectoria típica del uso del método de “Punto Interior” 7

ÍNDICE DE TABLAS

Tabla 1. Tabla de datos para solución de problema. 4

Tabla 2. Tabla inicial del método “Simplex”. 9

Tabla 3. Buscando candidato para ser valor de entrada en fila Z. 10

Tabla 4. “Columna Pivote” encontrada por método. 10

Tabla 5. “Fila pivote” y valor del “pivote” de la 1° iteración. 11

Tabla 6. Tabla “Simplex” de la 2° iteración del método. 12

Tabla 7. Tabla final con los valores de las incógnitas buscadas. 12

Introducción.

Problemas de maximización y minimización de recursos se pueden encontrara a diario en decisiones triviales del día a día, por ejemplo en la organización de tiempo para estudio, para aprovechar las utilidades de una empresa, así existen muchos casos en los que se hace presente esta problemática. Por otra parte darle soluciones a estos problemas no parece tan complicado como se ve, en el caso de que existan pocas variables a revisar, para un problema. Pero ¿Qué pasa cuando existen muchas variables par tomar en cuenta?

En el presente informe se verá que la problemática planteada de maximización de utilidades, puede ser resuelta mediante un método llamado “Simplex”, el cual permite por iteraciones, y mediante un algoritmo de muy fácil uso, encontrar las soluciones esperadas (ya sea de maximización o de minimización).

Se presentará básicamente en este informe el método de uso de este algoritmo, los pasos a seguir y algunas restricciones que impone el método a la hora de usarlo. Por lo cual nos guiaremos de trabajos de investigaciones o paper antes hechos para obtener información más fiable sobre el tema.

Planteamiento del problema.

El método “Simplex” busca, resolver problemas de programación lineales que se presentan, buscando maximizar o minimizar la función usada, la que vendrá sujeta a condiciones o restricciones, también del tipo lineal.

El modelo de programación lineal está compuesto de lo siguiente:

1.- Conjunto de variables de decisión.

2.- Un conjunto de restricciones.

3.- Una función objetivo.

Dentro del método se pueden encontrar en dos puntos para encontrar la solución.

.- Región factible: conjunto de todos los puntos que satisfacen las restricciones, incluyendo los signos.

Esta región representa un conjunto convexo (S), puesto que cualquier segmento rectilíneo que una un par de puntos entre un punta A y otro B se encuentran en el conjunto (S). S puede observar tal apreciación en la siguiente figura a mostrar.

Representación de conjuntos convexos y no convexos.

Se puede ver claramente que uniendo los puntos A y B con un segmento rectilíneo, los únicos conjuntos que dan un tramo completamente perteneciente al conjunto son los de B y C.

.- Solución óptima: Dentro del tipo de problemas de optimización se le llama así al mayor valor que puede tomar la función, en el caso de maximizar la función.

En caso contrario, de buscar una minimización, se necesita encontrar el menor valor que d como solución a la función.

Este problema se aplica básicamente a usos económicos, para utilidades de empresas, pero también nos podría permitir, buscar optimizar, por ejemplo, las horas de estudio que debemos dedicar a cada ramo de la universidad. También se podría usar para optimizar dinero a la hora de comprar en un supermercado, escogiendo entre dos tipos de productos iguales, pero de diferentes marcas y ver cual proporciona una mejor calidad de vida (Aquí se optimiza el dinero a largo plazo, no incurriendo en enfermedades innecesarias) o bien se podría usar para optimizar el consumo de proteínas en una determinada dieta.

Los ejemplos anteriores, no muy usados en el diario vivir, nos permiten observar el uso que se le puede dar a este método, pero principalmente se puede recalcar que se usa, en la mayoría de los casos, para optimizar recursos empresariales de utilidades.

Problema.

En una frutería, llegan dos importadoras de frutas diferentes que le ofrecen al vendedor sus productos, asegurando que los siguientes productos que le ofrecerán le aseguran ganancias si o si. Lo que el vender busca es tener la maximización de utilidades con respecto a los productos ofrecidos, por lo que recurre al uso de método “simplex” para tener una mejor visualización a su problema.

Los datos de los productos ofrecidos, se pondrán en una tabla de utilidades para hacer más fácil la comprensión del problema.

TIPO A TIPO B TOTAL

NARANJAS 2 Kg. 4 Kg. 100 Kg.

PLATANOS 3 Kg. 2 Kg. 120 Kg.

KIWIS 2 Kg. 1 Kg. 100 Kg.

UTILIDADES $ 1200 $ 900

Tabla de datos para solución de problema.

Algoritmo de solución.

En resumen la serie de pasos o el algoritmo que soluciona el problema es el siguiente;

1. Convertir desigualdades en igualdades.

1.1 Si desigualdad es menor o igual agregar variable holgura sumando.

1.2 En caso contrario agregar variable exceso restando y variable artificial sumando.

2. Igualar función objetivo en cero por la derecha.

3. Introducir variables a la tabla “Simplex”.

3.1 Si variable es básica (solo se presenta una vez en todas las ecuaciones).

3.1.1 Agregar a filas

3.2 En caso contrario agregar a columnas.

4. Mientras en la fila de la variable Z haya algún elemento negativo hacer

4.1 Buscar columna pivote, escogiendo el elemento menor de la fila Z.

4.2 Buscar fila pivote.

4.2.1 Si la división entre los elementos de la columna pivote y la columna son positivos mayores que cero.

4.2.1.1 Se puede dividir

4.2.2 En caso contrario

4.2.2.1 División fallida.

4.3. Si todas las divisiones fueron fallidas el método “Simplex” termina.

4.4 En caso contrario se comparan los cocientes para encontrar la fila pivote la cual será la fila que haya obtenido el cociente menor.

4.5. Escoger elemento pivote de la intersección de la fila y columna pivotes. 4.6. Dividir todos los elementos de la fila pivote por el elemento pivote.

4.7. Para las demás filas hacer.

4.7.1 Por cada elemento hacer.

4.7.1.1 Restar el elemento a cambiar por el producto entre el elemento de la fila en que se encuentra el elemento a cambiar pero en la columna pivote por el elemento de la misma columna de elemento a cambiar pero en la fila pivote.

Comparación de algoritmos.

Cálculo de la complejidad del método.

Se ve claramente que la complejidad de tiempo obtenido por el método “Simplex”, tendrá un orden exponencial, es decir, orden O (a*2n). Siendo “n” la cantidad de variables a deducir del planteamiento de las incógnitas y “a” el número de variables básicas que se introducen en la igualación de inecuaciones en el paso 4.2 del algoritmo del método.

Se puede deducir entonces que el algoritmo es de tiempo polinómico solo para “n” pequeños puesto que su complejidad exponencial lo hará de tiempo no polinomio para “n” demasiado grandes.

El método “Simplex”, no es el único que puede resolver problemas lineales, por ejemplo para el mismo caso existen otros algoritmos que resuelve el problema, los que comentaremos a continuación.

Método por “Solución Grafica”.

Este método consta de una serie de pasos para resolver este tipo de problemas, el caso es que solo funciona para problemas que presente dos variables solamente (en este caso servirá).

Lo que busca principalmente es poner las fronteras de las inecuaciones de forma grafica para determinar sus puntos de frontera, los cuales posteriormente se reemplazaran en la ecuación objetivo para determinar cuáles son los puntos que condicionan el mínimo o máximo de la función.

Si la región factible no es acotada, este método puede ser erróneo: soluciones óptimas siempre existen cuando la región factible está acotada, pero pueden no existir en el caso no acotado.

Si la región factible no es acotada, estamos minimizando una función objetiva cuyos coeficientes son no negativos, entonces existe una solución dado por este método.

Método por “Punto Interior de Karmarkar”.

Con el método “Simplex” se obtiene una solución óptima siguiendo una ruta de puntos extremos adyacentes, a lo largo de las orillas del espacio de soluciones. Aunque en la práctica el método “Simplex” ha funcionado bien para resolver problemas grandes, la cantidad de iteraciones necesarias para llegar a la solución óptima puede crecer en forma exponencial, teóricamente. De hecho, los investigadores han construido una clase de programas lineales en los que todos los puntos extremos factibles se visitan antes de llegar al óptimo.

Este método representa un algoritmo de tiempo

...