- Conceptos
básicos - Hipótesis
básicas - Planteamiento del
problema - Algoritmo Símplex
(Dantzig, 1951) - Método
Simplex modificado - Método
Simplex súper modificado - Desarrollando
el método Simplex - Problemas
propuestos
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.
Conceptos
básicos
1.- FACTORES PRODUCTIVOS: (Ai)
Son los medios
empleados para la obtención de la producción. Los factores productivos pueden
ser limitados (los cuales originan restricciones), o
limitados.
Los llamaremos Ai = Factor productivo i.
2.- VECTOR EXISTENCIAS: (Po)
Es un vector columna cuyos componentes son las
cantidades disponibles de cada uno de los factores productivos
limitados.
3.- TÉCNICA
Una técnica es una combinación de los
distintos factores productivos
4.- PROCESO PRODUCTIVO: (Pj)
Es la transformación de los factores productivos
en bienes o
productos, de
acuerdo con una técnica determinada.
5.- VECTOR PROCESO
Es un vector columna, cuyos componentes indican las
cantidades necesarias de los distintos factores productivos, para
la realización del proceso Pj.
6.- NIVEL DE PROCESO: (Xj)
Indica la intensidad de utilización de los
distintos factores productivos en el proceso Pj, y lo llamaremos
Xj.
Hipótesis
básicas
7.1.- PROPORCIONALIDAD
Las cantidades de los factores productivos son
proporcionales a su nivel de utilización.
7.2.- NO NEGATIVIDAD
Los niveles de los procesos han
de ser mayores o iguales a cero.
7.3.- ADITIVIDAD
La combinación de varios procesos productivos
utiliza en conjunto la suma de todos los factores exigidos
individualmente a cada uno de ellos.
7.4.- LINEALIDAD
Los rendimientos de los procesos, son directamente
proporcionales a su nivel de utilización, es decir: dado
un proceso Pj, empleado a nivel unitario, obtendremos un
rendimiento Pj, mientras que si Pj es utilizado a un nivel Xj, el
rendimiento del proceso será Xj Pj.
Planteamiento del
problema
Optimizar: Z = ?C1 X 1 ??C 2
X 2 ?? ??C n X n
Sujeto a:
Los problemas de
programación lineal se caracterizan por una
serie de elementos:
1. En la solución óptima: el número
de procesos será igual al número de factores
limitados; aunque en ciertas ocasiones, dicho número de
procesos puede ser menor que el número de factores
limitados. En tal caso, la solución es
degenerada.
2. Los niveles de utilización Xj de los procesos
serán no negativos.
3. Estos niveles serán tales, que todas las
restricciones cumplan como igualdad,
siempre y cuando estemos hablando de procesos que pertenezcan al
óptimo.
4. El programa
(plan de
producción), que cumpliendo las condiciones anteriores,
optimice el valor de la función objetivo, será el
programa óptimo.
Algoritmo
Símplex (Dantzig, 1951)
Página siguiente |