Programacion Lineal

Programación Lineal

David Cid Barato 76727978 - R


Índice

Introducción…………………………………………………………………………………………………………….… Página 3
Antecedentes Históricos.
En qué consiste la programación lineal.
Qué significa el término lineal.
En qué consiste el método Simplex.
Resolución del problema a través del Método Simple………………………………………… Página 5
Planteamiento del problema.
Análisis detablas y gráfico.
Conclusión.

1- Introducción:

a. Antecedentes históricos.
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 hasta 1947. En la posguerra, muchas industrias lo usaron ensu 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 Kantoróvich, un matemático ruso, que utiliza técnicas similares en la economía antes de Dantzig y ganó el premio Nobel en economía en 1975. En 1979, otro matemático ruso, Leonid Khachiyan, diseñóel llamado Algoritmo del elipsoide, a través del cual demostró que el problema de la programación lineal es resoluble de manera eficiente, es decir, en tiempo polinomial. Más tarde, en 1984, Narendra Karmarkar introduce un nuevo método del punto interior para resolver problemas de programación lineal, lo que constituiría un enorme avance en los principios teóricos y prácticos en el área.
Elejemplo original de Dantzig de la bú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 (factorial de 70, 70!) ; el número de posibles configuraciones excede al número de partículas en el universo. Sinembargo, toma sólo un momento encontrar la solución óptima mediante 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 deben ser revisadas.
b. En qué consiste la programación lineal:
La Programación Lineal es un procedimiento o algoritmomatemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo, también lineal.
Consiste en optimizar (minimizar o maximizar) una función lineal, denominada función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones linealesc. Que significa el término lineal:
Es aquel en los términos están elevados a 1.
d. En qué consiste el método Simplex.

El método del simplex fue creado en 1947 por el matemático George Dantzig .
El método del simplex se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen tres o más variables.

El álgebra matricial y el proceso deeliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales constituyen la base del método simplex.

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.

2- Resolución del problema a través del Método Simple:

e. Planteamiento del problema:

Una empresaembotelladora de bebidas refrescantes tiene 2 productos principales,D1 Y D2, cuya producción se realiza en 2 secciones, una de envasado y otra de embalaje de productos. La capacidad semanal en horas de trabajo, e la sección de embasado es de 30, mientras que la de sección de embalaje es de 200 hs de trabajo semanales. El envasado y el embalaje de 1000 de ambos tipos de bebida requieren de la utilización...