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
