Programación Lineal

1. PROGRAMACION LINEAL Y ANALISIS DE REDES.
Definir y explicar los siguientes conceptos.

Programación lineal
Es un procedimiento matemático que tiene como objetivo la resolución de un problema indeterminado, que consiste en la optimización de una función (objetivo) lineal, de manera que las variables están limitadas por un sistema de inecuaciones lineales.

Origen / historia de laprogramación lineal
El origen de la programación lineal se encuentra en la Segunda Guerra Mundial. Esta herramienta matemática era utilizada en la guerra para minimizar los costos de los aliados y maximizar los costos del enemigo, pero no fue hasta el año 1947 que se dio a conocer. En la posguerra, muchas industrias aprovecharon ésta técnica para la optimización de sus beneficios.

Los fundadoresde 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.

Teoría de sustentación de la técnica
Esta teoría se sustenta con la elaboración eimplementación de diferentes métodos, entre los que cabe destacar el método matemático de programación y planificación de la producción (Kantarovitch), las técnicas de computación y ordenadores, y la publicación del método simplex (G. B. Dantzing).

Distintos modelos de programación lineal
• Modelo de minimización de redes (problema del árbol de mínima expansión). Este tiene que ver con ladeterminación de los ramales que pueden unir todos los nodos en una red, tal que minimice la suma de las longitudes de los ramales escogidos.

• Modelo del flujo máximo. En este se trata de enlazar un nodo fuente y un nodo destino a través de una red de arcos dirigidos. Cada arco tiene una capacidad máxima de flujo admisible. El objetivo es el de obtener la máxima capacidad de flujo entre la fuente y eldestino. El problema de flujo máximo se puede formular como un problema de programación lineal, se puede resolver con el método simplex y usar cualquier software.

• Método gráfico o de las rectas de nivel. Las rectas de nivel dan los puntos del plano en los que la función objetivo toma el mismo valor. El Método Gráfico se utiliza para ilustrar tres conceptos básicos: la metodología para laresolución de un problema de dos variables de decisión, la interpretación de la solución del problema modelado y la observación gráfica de cómo afectan los cambios a la solución del problema.


Supuestos / hipótesis de la programación lineal
Las condiciones que debe haber para que un problema pueda ser resuelto mediante programación lineal son las siguientes:

• Proporcionalidad: En programaciónlineal, tanto la función objetivo como las restricciones deben de ser lineales, es decir que la contribución de cada variable de decisión en la función objetivo y sus requerimientos en las restricciones sea directamente proporcional al valor de la variable. Esta linealidad trae consigo el concepto de proporcionalidad entre el nivel de cada actividad y el empleo de los recursos, así como laproporcionalidad entre el nivel de cada actividad y la medida de efectividad.

• Aditividad: Estipula que la contribución total de todas las variables en la función objetivo y sus requerimientos en las restricciones, sean la suma directa de las contribuciones o requerimientos individuales de cada variable. Existen ocasiones en que una función aún siendo proporcional no es lineal. Debido a esta situación,existen interacciones entre las diferentes actividades, con lo cual, al variar el nivel de una actividad, indirectamente modificamos el efecto que otra actividad tiene sobre la medida de efectividad. La aditividad presupone que la medida total de efectividad y la utilización total de recursos Resultantes de la operación conjunta de las actividades, debe igualar las sumas respectivas de las...