- 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 |