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.

-Tipos de modelos:

 Simbólico o matemático.- Es el tipo más importante de modelo de investigación de operaciones. Al formular este tipo uno supone que todas las variables relevantes son cuantificables. Por consiguiente, los símbolos matemáticos se utilizan para representar variables, las cuales entonces están relacionadas con las funciones matemáticas apropiadas para describir el comportamiento del sistema. Luego la solución del modelo se logra por manipulación matemática apropiada.

 De Simulación.- Los modelos de simulación “imitan” el comportamiento del sistema sobre un periodo. Esto se logra especificando ciertos eventos, los cuales son puntos en el tiempo, cuya ocurrencia significa que puede recolectarse la información importante perteneciente al comportamiento del sistema. Una vez que se definen tales eventos es necesario prestar atención al sistema únicamente cuando ocurre un evento. La información que mide el funcionamiento del sistema se acumula en observaciones estadísticas, las cuales se actualizan en cuanto cada evento tiene lugar. Dado que los modelos de simulación no necesitan funciones matemáticas explicitas para relacionar las variables, usualmente es posible simular sistemas complejos que no pueden modelarse o resolverse matemáticamente. Tal flexibilidad permite una representación más aproximada al sistema. La principal falla de la simulación consiste en que el análisis es equivalente a realizar experimentos y por consiguiente está sujeto al error experimental. Esto lleva a las dificultades usuales de diseñar (estadísticamente) el experimento, recolectar observaciones y entonces ejecutar las pruebas estadísticas necesarias de inferencia.

 Heurístico.- El método Heurístico de solución descansa en las reglas empíricas o intuitivas que, dada una solución actual al modelo, permiten la determinación de una solución mejorada. Actualmente los métodos heurísticos son procedimientos de búsqueda que pasan inteligentemente de un punto de solución a otro, con el objetivo de mejorar el valor del criterio del modelo. Cuando ninguna mejora adicional puede lograrse la mejor solución que se haya tenido es la solución aproximada al modelo.

En la investigación de operaciones se utiliza herramientas que nos permiten tomar una decisión a la hora de resolver un problema tal es el caso de los modelos e investigación de operaciones que se emplean según sea la necesidad. Para llevar a cabo el estudio de Investigación de Operaciones es necesario cumplir con una serie de etapas o fases. Las principales etapas o fases son las siguientes:

1.-Definición del problema: Desde el punto de vista de investigación de operaciones esto indica tres aspectos principales: (a) Una descripción de la meta o el objetivo del estudio, (b) Una identificación de las alternativas de decisión del sistema y (c) Un reconocimiento de las limitaciones, restricciones y requisitos del sistema.

Una descripción del objetivo del estudio debe reflejar una representación aproximada del interés total del sistema. Una falla común

...