Ensayo

METODO DUAL SIMPLEX.
________________________________________
TEORIA DE LA DUALIDAD.
Cada problema de programación lineal tiene un segundo problema asociado con el. Uno se denomina primal y el otro dual. Los 2 poseen propiedades muy relacionadas, de tal manera que la solución óptima a un problema proporciona información completa sobre la solución óptima para el otro.
Las relaciones entre elprimal y el dual se utilizan para reducir el esfuerzo de computo en ciertos problemas y para obtener información adicional sobre las variaciones en la solución óptima debidas a ciertos cambios en los coeficientes y en la formulación del problema. Esto se conoce como análisis de sensibilidad o post-optimidad.
DEFINICION DEL PROBLEMA DUAL.
Para poder elaborar el problema dual apartir del primal, este se debe presentar en su forma canónica de la siguiente forma:
Maximizar
Sujeto a:



El problema dual se puede obtener a partir del problema primal y viceversa de la siguiente manera:
1. Cada restricción de un problema corresponde a una variable en el otro.
2. Los elementos del lado derecho de las restricciones en un problema son iguales a los coeficientesrespectivos de la función objetivo en el otro.
3. Un problema busca maximizar y el otro minimizar.
4. El problema de maximización tiene restricciones que y el problema de minimización tiene restricciones que.
5. Las variables en ambos casos son no negativas.

Algoritmo símplex

Un sistema de desigualdades lineales define un poliedro como una región factible. El algoritmo simplex comienza enun 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 habitualmente se 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 deinecuaciones lineales. El algoritmo simplex primal fue desarrollado por el matemático norteamericano George Dantzig en 1947, y procede examinando vértices adyacentes del poliedro de soluciones. 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éricoque busca un mínimo (o máximo) local de una función cualquiera examinando en cada paso los vértices de un simplex.
•
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. El problema 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 de variables excede el número de ecuaciones. La diferencia entre el número devariables 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 llamadasvariables 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 ( para ellas, dado que la...