Programación Lineal

Unidad 1 "Programación Lineal"

La programación lineal es un procedimiento o algoritmo matemá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 lineales.

-Historia de la programación lineal (Cronología)

 (1826) Joseph Fourier anticipa la programación lineal. Carl Friedrich Gauss, resuelve ecuaciones lineales por eliminación "gaussiana".

 (1902) Gyula Farkas concibe un método para resolver sistemas de desigualdades.

 (1947) George Dantzig publica el algoritmo simplex y John von Neumann desarrolló la teoría de la dualidad. Se sabe que Leonid Kantoróvich también formuló la teoría en forma independiente.

 (1984) Narendra Karmarkar introduce el método del punto interior para resolver problemas de programación lineal.

El problema de la resolución de un sistema lineal de inecuaciones se remonta, al menos, a Joseph 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 hasta 1947. 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 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. 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.

Durante la segunda guerra mundial, la administración militar en Gran Bretaña llamó a un equipo de científicos para que estudiaran los problemas tácticos y estratégicos asociados a la defensa aérea y terrestre del país. Su objetivo era determinar la utilización más efectiva de los recursos militares limitados. Las aplicaciones incluían entre otras, estudios de la forma de utilizar el radar y de la efectividad de nuevos tipos de bombas. El nombre de investigación de operaciones fue dado aparentemente porque el equipo estaba llevando a cabo la actividad de investigar operaciones (militares). Desde su nacimiento, este nuevo campo de toma de decisiones se ha caracterizado por el uso del conocimiento científico a través del esfuerzo de equipos interdisciplinarios, con el propósito de determinar la mejor utilización de los recursos limitados.

1.1 Definición, desarrollo y tipos de modelos de investigación de operaciones.

Investigación de Operaciones: Es determinar la mejor solución (optima) para un problema de decisión con la restricción de recursos limitados. Como técnica para la resolución de problemas, investigación de operaciones debe visualizarse como una ciencia y como un arte. Como Ciencia radica en ofrecer técnicas y algoritmos matemáticos para resolver problemas de decisión adecuada. Como Arte debido al éxito que se alcanza en todas las fases anteriores y posteriores a la solución de un modelo matemático, depende de la forma apreciable de la creatividad y la habilidad personal de los analistas encargados de tomar las decisiones.

"La Investigación de Operaciones en la Ingeniería de Sistemas se emplea principalmente en los aspectos de coordinación de operaciones y actividades de la organización o sistema que se analice, mediante el empleo de modelos que describan las interacciones entre los componentes del sistema y de éste con este con su medio ambiente".

-Desarrollo de la Investigación de Operaciones (IO):

Durante la segunda guerra mundial, la administración militar en Gran Bretaña llamó a un equipo de científicos para que estudiaran los problemas tácticos y estratégicos asociados a la defensa aérea y terrestre del país. Su objetivo era determinar la utilización más efectiva de los recursos militares limitados. Las aplicaciones incluían entre otras, estudios de la forma de utilizar el radar y de la efectividad de nuevos tipos de bombas.

El nombre de investigación de operaciones fue dado aparentemente porque el equipo estaba llevando a cabo la actividad de investigar operaciones (militares). Desde su nacimiento, este nuevo campo de toma de decisiones se ha caracterizado por el uso del conocimiento científico a través del esfuerzo de equipos interdisciplinarios, con el propósito de determinar la mejor utilización de los recursos limitados

Un modelo de la investigación de operaciones se define como una representación idealizada (simplificada) de un sistema de la vida real. Este sistema puede ya estar en existencia o puede todavía ser una idea en espera de ejecución. En el primer caso el objetivo del modelo es analizar el comportamiento del sistema a fin de mejorar su funcionamiento. En el segundo, el objetivo es diversificar la mejor estructura del sistema futuro.

La complejidad de un sistema real resulta del gran número de elementos (variables) que controlan el comportamiento del sistema. Aunque una situación real puede involucrar un número sustancial de variables, generalmente., una pequeña fracción de estas variables realmente domina el comportamiento del sistema. Por consiguiente, la simplificación del sistema real en términos de un modelo se concentra principalmente en la identificación de las variables y relaciones dominantes que lo gobiernan.

...