Metodo Simplex

UNIVERSIDAD LATINA DE PANAMA

FACULTAD DE INGENIERÍA

LICENCIATURA EN INGENIERÍA INDUSTRIAL EMPRESARIAL

INVESTIGACIÓN

METODO SIMPLEX

FACILITADOR:

RICAURTE GARRIDO IBARRA

JAIME ESPINOZA

8-864-916

KEVIN DA SILVA

8-820-12098

JUEVES 14 DE FEBRERO DE 2013

INTRODUCCIÓN

El método simplex es un procedimiento algebraico, que a pesar de que es un algoritmo la mayoría de sus conceptos son geométricos. Se enfoca en llegar a la respuesta óptima de la programación lineal, a través de sus respectivos pasos que se pueden caracterizar por ser pesados o tediosos.

Este método puede llegar a encontrar las soluciones de problemas de programación lineal, ya sean problemas de maximización tanto como de minimización. En este método cada paso que se va haciendo es en busca de mejora, en busca de llegar a resolver el problema. Nos damos cuenta que el proceso del método llega a su fin cuando ya no hay mas mejora y llegamos a la solución o a la respuesta optima.

HISTORIA

El Método Simplex publicado por George Dantzig en 1947 consiste en un algoritmo iterativo que secuencialmente a través de iteraciones se va aproximando al óptimo del problema de Programación Lineal en caso de existir esta última.

La primera implementación computacional del Método Simplex es el ano 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones.

El Método Simplex hace uso de la propiedad de que la solución óptima de un problema de Programación Lineal se encuentra en un vértice o frontera del dominio de puntos factibles (esto último en casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación progresiva de estos vértices hasta encontrar el óptimo. Cabe destacar que para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como formato estándar.

DEFINICIÓN

El método simplex es una herramienta algebraica que permite localizar de manera eficiente el óptimo entre los puntos extremos de una solución a un problema de programación lineal.

El método del simplex fue creado en 1947 por el matemático George Dantzig. El método del simplex se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen tres o más variables.

El álgebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales constituyen la base del método simplex.

Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.

METODOLOGÍA DEL MÉTODO SIMPLEX

Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.

Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.

El método del simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.

Con miras a conocer la metodología que se aplica en el Método SIMPLEX, vamos a resolver el siguiente problema:

Maximizar Z= f(x,y)= 3x + 2y

sujeto a: 2x + y 18

2x + 3y 42

3x + y 24

x 0 , y 0

Se consideran las siguientes fases:

1. Convertir las desigualdades en igualdades

Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:

2x + y + h = 18

2x + 3y + s = 42

3x +y + d = 24

2. Igualar la función objetivo a cero

- 3x - 2y + Z = 0

3. Escribir la tabla inicial simplex

En las columnas aparecerán todas las variables del problema y, en las filas, los coeficientes de las igualdades obtenidas, una fila para cada restricción y la última fila con los coeficientes de la función objetivo:

Tabla I . Iteración nº 1

Base Variable de decisión Variable de holgura Valores solución

x y h s d

h 2 1 1 0 0 18

s 2 3 0 1 0 42

d 3 1 0 0 1 24

Z -3 -2 0 0 0 0

4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base

A. Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y

...