Programacion lineal

Solo disponible en BuenasTareas
  • Páginas : 6 (1419 palabras )
  • Descarga(s) : 4
  • Publicado : 26 de noviembre de 2009
Leer documento completo
Vista previa del texto
Introduccion
La programacion lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales donde las variables que definen al mismo son conocidas pero se necesita encontrar la combinación de las mismas que permitan optimizar un rendimiento (maximizar un beneficio, minimizar costos o ambos).
Para laformulacion de modelos es necesario seguir un orden, los cuales se presentaran mas adelante. Al igual que el análisis de sensibilidad ya que es una de las partes más importantes en la programación lineal, sobretodo para la toma de decisiones. Los metodos a tratar son el metodo grafico y el metodo simplex.

PROGRAMACION LINEAL

Historia de la programación lineal

El problema de laresolución de un sistema lineal de inecuaciones se remonta, al menos, a Fourier, después de quien nace el método de eliminación de Fourier-Motzkin. La programación lineal se plantea como un modelo matemático desarrollado durante la Segunda Guerra Mundial para planificar los gastos y los retornos, a fin de reducir los costos al ejército y aumentar las pérdidas del enemigo. Se mantuvo en secreto hasta1947. En la posguerra, muchas industrias lo usaron en su planificación diaria.
Los fundadores de la técnica son George Dantzig, quien publicó el algoritmo simplex, en 1947, John von Neumann, que desarrolló la teoría de la dualidad en el mismo año, y Leonid Kantorovich, un matemático ruso, que utiliza técnicas similares en la economía antes de Dantzig y ganó el premio Nobel en economía en1975. Leonid Khachiyan en 1979 fue el primero en demostrar que el problema de la programación lineal se solucionaba en tiempo polinomial, sin embargo, el mejor avance en los principios teóricos y prácticos en el campo se produjo en 1984, cuando Narendra Karmarkar introduce un nuevo método del punto interior para resolver problemas de programación lineal.
El ejemplo original de Dantzig de labúsqueda de la mejor asignación de 70 personas a 70 puestos de trabajo es un ejemplo de la utilidad de la programación lineal. La potencia de computación necesaria para examinar todas las permutaciones a fin de seleccionar la mejor asignación es inmensa; el número de posibles configuraciones excede al número de partículas en el universo. Sin embargo, toma sólo un momento encontrar la solución óptimamediante el planteamiento del problema como una programación lineal y la aplicación del algoritmo simplex. La teoría de la programación lineal reduce drásticamente el número de posibles soluciones óptimas que deberán ser revisadas.

Metodología de formulación directa para construir modelos de programación lineal
Como su nombre lo indica, la formulación directa estriba en pasardirectamente del sistema asumido al modelo de PL. Para tal efecto, se propone el siguiente orden: definir el objetivo, definir las variables de decisión, enseguida las restricciones estructurales y finalmente establecer las condiciones técnicas
1. Definir el Objetivo: Consiste en definir un criterio de optimización el cual puede ser Maximización o Minimización dependiendo del problema que se deseeresolver, el cual es una función lineal de las diferentes actividades del problema. Bajo el criterio de optimización definido se pretende medir la contribución de las soluciones factibles que puedan obtenerse y determinar la óptima.
2. Definir las variables de decisión: Son las incógnitas del problema básicamente consisten en los niveles de todas las Actividades que pueden llevarse a cabo en el problemaa formular, estas pueden ser de tantos tipos diferentes como sea necesario, e incluir tantos subíndices como sea requerido.
3. Definir las restricciones: Son los diferentes requisitos que debe cumplir cualquier solución para que pueda llevarse a cabo. En cierta manera son las limitantes en los valores de los niveles de las diferentes actividades (variables). Las restricciones más comunes son...
tracking img