Metodo Simplex

Trabajo de Investigacion Operativa  Tercero Comercial

Universidad Tecnica de  Cotopaxi

Trabajode : El Metodo Simplex

Nombre: Jessica Esquivel

Fecha: 11 / 11 2013

EL MÉTODO SIMPLEX.

Quien se inventó el método Simplex

George Bernard Dantzig (8 de noviembre de 1914 – 13 de mayo de 2005) fue un profesor, físico y matemático estadounidense, reconocido por desarrollar el método simplex y es considerado como el "padre de la programación lineal". Recibió muchos honores, tales como la Medalla Nacional de Ciencia en 1975 y el premio de Teoría John von Neumann en 1974.

Fue miembro de la Academia Nacional de Ciencias, la Academia Nacional de Ingeniería y la Academia Americana de Artes y Ciencias.

El método Simplex es un método secuencial de optimización, 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 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.

Deberá tenerse en cuenta que este método sólo trabaja para restricciones que tengan un tipo de desigualdad "=" y coeficientes independientes mayores o iguales a 0, y habrá que estandarizar las mismas para el algoritmo. En caso de que después de éste proceso, aparezcan (o no varíen) restricciones del tipo "=" o "=" habrá que emplear otros métodos, siendo el más común el método de las Dos Fases.

En qué casos se aplica el método simplex

El método símplex cuya gran virtud es su sencillez, es un método muy práctico, ya que solo trabaja con los coeficientes de la función objetivo y de las restricciones.

Ilustraremos su funcionamiento mediante un ejemplo, pero previamente mostraremos las reglas de decisión para determinar la variable que entra, la que sale, la gran M, y cómo determinar que estamos en el óptimo; Todas éstas reglas de decisión fueron deducidas del método algebraico, solamente que aquí se han acomodado para ser usadas en el tipo de tablero símplex que se usará.

Criterio de decisión	Maximizar	Minimizar
Gran M en la función objetivo	- MXj	+MXj
Variable que entra	La más negativa de los Zj - Cj	La más positiva de los Zj - Cj
Variable que sale	La menos positiva de los b/a , Siendo a > 0 , de lo contrario no restringe	La menos positiva de los b/a , Siendo a > 0 , de lo contrario no restringe a la variable que entra
Solución óptima	Cuando todos los Zj – Cj > 0	Cuando todos los Zj – Cj < 0

Tipos de restricciones

·         Restricciones (

Se añade una variable de holgura, con costo (o ganancia) en la función objetivo igual a 0.

Ejm:

2X1 - 4X2 <= 1, queda:

2X1 - 4X2 + X3 = 1 Cj de X3 en la función objetivo será 0.

·         Restricciones (

Se resta una variable de exceso, con costo (o ganancia) en la función objetivo igual a 0, y se suma una variable artificial con costo +M ó –M según sea maximización o minimización.Ejm:

2X1 + 3X2 >= 1, queda:

2X1 + 3X2 - X3 + X4= 1 Cj de X3 en la función objetivo será 0. y Cj de X4 (artificial) es (M

·         Restricciones =Se le añade una variable artificial con costo +M ó –M según sea maximización o minimización.Ejm:

2X1 + 3X2 = 8, queda:

2X1 + 3X2 + X3= 8 Cj de X3 en la función objetivo será (M

Adicionalmente se presentan las siguientes notas a tener en cuenta:

·         Si en el tablero simplex de la solución óptima queda al menos una variable de superávit ó artificial dentro de las variables básicas, con un valor > 0 , el problema no tiene solución, esto quiere decir que al menos existen dos restricciones excluyentes, por lo tanto no existe área de soluciones factible y menos una solución , en éste caso se debe revisar la formulación del problema.

·         Si al escoger la variable que sale, ninguna de las variables básicas restringe el crecimiento de la variable no básica escogida para entrar, el problema tiene solución indeterminada y se debe revisar la formulación en busca de una nueva restricción que no se tuvo en cuenta en la formulación inicial.

·         Si en el tablero simplex del óptimo, al menos una de las variables no básicas tiene coeficiente cero (0) en la función objetivo, esto es su Zj – Cj = 0, el problema tiene múltiples soluciones y se nos está ofreciendo una de ellas.

Ejemplo 1

Siendo Xi la cantidad a producir del producto i.

Maximizar Z = X1 + X2 {Ganancia total en soles}

S.A.

5X1 + 3X2 <= 15 {Horas disponibles dep. A}

3X1 + 5X2 <= 15 {Horas disponibles dep. B}

Xj >= 0 ; j = 1, 2

Los problemas de Maximización, con todas sus restricciones <= y con la condición de no negatividad, se le llama Forma Estándar ó Forma Normal