Metodo Simplex

Algoritmo símplex

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 al autor principal del artículo en su página de discusión pegando: {{subst:Aviso referencias|Algoritmo símplex}} ~~~~


Existen desacuerdos sobre la exactitud dela información en este artículo o sección.
En la página de discusión puedes consultar el debate al respecto.


Este artículo o sección necesita una revisión de ortografía y gramática.
Puedes colaborar editándolo (lee aquí sugerencias para mejorar tu ortografía). Cuando esté corregido, borra este aviso, por favor.
Puedes ayudarte del corrector ortográfico, activándolo en: Mispreferencias → Accesorios → Navegación →  El corrector ortográfico resalta errores ortográficos con un fondo rojo.


Un sistema de desigualdades lineales define un poliedro como una región factible. El algoritmo simplex comienza en un vértice y se mueve a lo largo de las aristas del poliedro hasta que alcanza el vértice de la solución óptima.
En optimización matemática, el término algoritmo símplex habitualmentese refiere a un conjunto de métodos muy usados para resolver problemas de programación lineal, en los cuales se busca el máximo de una función lineal sobre un conjunto de variables que satisfaga un conjunto de inecuaciones lineales. El algoritmo simplex primal fue desarrollado por el matemático norteamericano George Dantzig en 1947, y procede examinando vértices adyacentes del poliedro desoluciones. Un algoritmo simplex es un algoritmo de pivote.
Un método llamado de manera similar, pero no relacionado al anterior, es el método Nelder-Mead (1965) o método de descenso (o ascenso) símplex; un método numérico que busca un mínimo (o máximo) local de una función cualquiera examinando en cada paso los vértices de unsimplex.
Índice
  [ocultar] 
1 Entrada del problema
2 Conceptos básicos2.1 Modelo Ampliado
2.2 Solución óptima
2.2.1 Solución óptima múltiple
3 Algoritmo del método Simplex
4 Ejemplo
5 Véase también
6 Enlaces externos
Entrada del problema[editar · editar código]
Considerar un problema de programación lineal,
maximizar 
sujeto a 
El algoritmo símplex requiere que el problema de programación lineal esté en la forma aumentada de la programación lineal. Elproblema puede ser escrito como sigue, en forma de matriz:
Maximizar  en:


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 devariables excede el número de ecuaciones. La diferencia entre el número de variables y el número de ecuaciones nos da losgrados 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 decero 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 quesu valor puede ser calculado trivialmente ( 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...