Algoritmo símplex

Algoritmo símplex
Un sistema de desigualdades lineales define un politopo como una región factible. El algoritmo simplex comienza en un vértice y se mueve a lo largo de las aristas del politopo hasta que alcanza el vértice de la solución óptima.

En la teoría de optimización, el algoritmo símplex, descubierto por el matemático norteamericano George Bernard Dantzig en 1947, es una técnica popular para dar soluciones numéricas del problema de la programación lineal. Un método sin relación, pero llamado de manera similar, es el método Nelder-Mead o método símplex cuesta abajo, debido a Nelder y Mead (1965), que es un método numérico para optimización de problemas libres multidimensionales, perteneciente a la clase más general de algoritmos de búsqueda. El que permite encontrar una solución óptima en un problema de maximización o minimización, buscando en los vértices del polígono.

En ambos casos, el método usa el concepto de un símplex, que es un politopo de N + 1 vértices en N dimensiones: un segmento de línea sobre una línea, un triángulo sobre un plano, un tetraedro en un espacio de tres dimensiones y así sucesivamente.

Entrada del problema

Considerar un problema de programación lineal,

maximizar \mathbf{c}^T \mathbf{x}
sujeto a \mathbf{A}\mathbf{x} \le \mathbf{b}, \, \mathbf{x} \ge 0

El algoritmo símplex requiere que el problema de programación lineal esté en la forma aumentada de la programación lineal. El problema puede ser escrito como sigue, en forma de matriz:

Maximizar Z en:

  \begin{bmatrix}
    1 & -\mathbf{c}^T & 0 \\
    0 & \mathbf{A} & \mathbf{I}
  \end{bmatrix}
  \begin{bmatrix}
    Z \\ \mathbf{x} \\ \mathbf{x}_s
  \end{bmatrix} = 
  \begin{bmatrix}
    0 \\ \mathbf{b}
  \end{bmatrix}
 \mathbf{x}, \, \mathbf{x}_s \ge 0

donde x son las variables desde la forma estándar, xs son las variables de holgura introducidas en el proceso de aumentación, c contiene los coeficientes de optimización, describe el sistema de ecuaciones contraídas, y Z es la variable a ser maximizada.

El sistema es típicamente no determinado, desde que el número de variables excede el número de ecuaciones. La diferencia entre el número de variables y el número de ecuaciones nos da los grados de libertad asociados con el problema. Cualquier solución, óptima o no, incluirá un número de variables de valor arbitrario. El algoritmo símplex usa cero como valor arbitrario, y el número de variables con valor cero es igual a los grados de libertad.

Valores diferentes de cero son llamados variables básicas, y valores de cero son llamadas variables no básicas en el algoritmo símplex.

Esta forma simplifica encontrar la solución factible básica inicial, dado que todas las variables de la forma estándar pueden ser elegidas para ser no básicas (cero), mientras que todas las nuevas variables introducidas en la forma aumentada, son básicas (diferentes de cero), dado que su valor puede ser calculado trivialmente (\mathbf{x}_{s\,i} = \mathbf{b}_{j} para ellas, dado que la matriz problema aumentada en diagonal es su lado derecho)

En cada una de las desigualdades que se plantean en el modelo matemático de programación lineal, se plantean desigualdades de <, >, <=, >=, o =, estas desigualdades se convierten en igualdades completando con variables de holgura si se trata de menor o igual que, o menor que, en el caso de que sea mayor o igual que o mayor que, se completa con variables de excedente, estas con signo negativo ya que como su nombre lo indica, es una cantidad que esta de excedente y hay que quitar para convertirla en igualdad, en caso se maneje el =, se manejan las variables artificiales.

Véase también

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

  • Algoritmo simplex — Saltar a navegación, búsqueda En la teoría de optimización, el algoritmo símplex , descubierto por el matemático norteamericano George Bernard Dantzig en 1947, es una técnica popular para dar soluciones numéricas del problema de la programación… …   Wikipedia Español

  • Simplex — Saltar a navegación, búsqueda Para el algoritmo del mismo nombre, véase Algoritmo simplex. Un 3 simplejo o tetraedro que puede pensarse como una región del espacio que consiste en la parte acotada por (y que también incluye) los cuatro puntos,… …   Wikipedia Español

  • Símplex — Para el algoritmo del mismo nombre, véase Algoritmo simplex. Un 3 simplejo o tetraedro que puede pensarse como una región del espacio que consiste en la parte acotada por (y que también incluye) los cuatro puntos, los seis segmentos de línea y… …   Wikipedia Español

  • Algoritmo de recocido simulado — Simulated annealing (SA) o recocido simulado es un algoritmo de búsqueda meta heurística para problemas de optimización global; el objetivo geneneral de este tipo de algoritmos es encontrar una buena aproximación al valor óptimo de una función en …   Wikipedia Español

  • Programación lineal — Saltar a navegación, búsqueda La Programación Lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo, también lineal.… …   Wikipedia Español

  • Check Wikipedia — Wikiproyecto:Check Wikipedia Saltar a navegación, búsqueda Esta página contiene de forma consciente fallos ortográficos. Los bots no deben intentar corregirlos. Atajo PR:CWPR:CW …   Wikipedia Español

  • Investigación de operaciones — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Historia de la matemática — Página del Compendio de cálculo por el método de completado y balanceado de Muhammad ibn Mūsā al Khwārizmī (820 d.C.) La historia de las matemáticas es el área de estudio que abarca las investigaciones sobre los orígenes de los descubrimi …   Wikipedia Español

  • Problema de la asignación — Saltar a navegación, búsqueda El problema del asignamiento es encontrar un matching de peso máximo en un grafo bipartido ponderado. Es uno de los problemas fundamentales de optimización combinatoria de la rama de optimización o investigación… …   Wikipedia Español

  • Método de las dos fases — El Método de las Dos Fases es una variante del Algoritmo simplex, que es usado como alternativa al Método de la Gran M, donde se evita el uso de la constante M para las variables artificiales . Se puede resumir así: Taha, Handy (1995).… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”