Otras clases de álgebra lineal

Programación lineal

 

La programación lineal, aunque suena complicado, es en realidad una manera de optimizar, es decir, maximizar o minimizar una función lineal de varias variables, sujeta a una serie de restricciones, también lineales. La función lineal que se quiere optimizar se llama función objetivo, y las restricciones se expresan mediante un sistema de inecuaciones lineales que hay que resolver.

¿Cuál es el objetivo principal de la programación lineal? Resolver situaciones reales mediante la identificación y la resolución de dificultades para así aumentar la productividad en lo que respecta a los recursos (sobre todo los que son limitados y costosos), mejorando también los beneficios.

Desarrollado por el matemático norteamericano George Dantzig en 1947, el Método Simplex es el que se usa tradicionalmente para resolver problemas de programación lineal. Este método busca el máximo de una función lineal en un conjunto de variables que resuelva una serie de inecuaciones lineales.

Por otro lado, como es normal que los problemas de programación lineal cuenten con una gran cantidad de variables, no es muy común tener que resolverlos de forma manual. Para ello, podemos recurrir a programas especializados, como WinQSB, TORA, Lingo o, para modelos menos complejos, puede servir la herramienta Solver de Excel.

 

Historia de la programación lineal

 

¿Sabes cuál es el origen de este método? Aunque podríamos decir que la programación lineal como se conoce hoy en día se remonta al matemático francés Jean Baptiste-Joseph Fourier (1768-1830), la solución de un sistema lineal de inecuaciones es una técnica matemática que se creó durante la Segunda Guerra Mundial para planificar los gastos y los retornos. El objetivo era reducir los gastos que tenía el ejército y aumentar las pérdidas del bando contrario. No se conoció hasta pocos años después del final de la guerra. Posteriormente, muchos sectores la usaron en su planificación diaria y hoy en día la usa la mayoría de las empresas.

Aparte de George Dantzig, que, como hemos comentado, desarrolló el método simplex en 1947, esta técnica también tuvo aportaciones por parte del matemático húngaro John von Neumann (teoría de la dualidad) y del matemático ruso Leonid Kantoróvich (premio Nobel de economía en 1975).

Años más tarde, hubo otras dos aportaciones significativas: la demostración de que el problema de la programación lineal se puede resolver en tiempo polinomial gracias al algoritmo del elipsoide (Leonid Khachiyan), y el enorme avance que supuso el nuevo método para resolver problemas de programación lineal que introdujo el matemático indio Narendra Karmarkar.

 

¿Cómo resolver un problema de programación lineal?

 

Lo primero que hay que hacer para resolver un problema mediante programación lineal es identificar los elementos básicos del modelo matemático, que son los siguientes:

 

  • Función objetivo
  • Variables
  • Restricciones

La función objetivo está relacionada con la pregunta que se quiere responder. Si hay varias preguntas, la función objetivo debe resolver la pregunta fundamental.

Las variables se deben identificar a partir de una serie de preguntas derivadas de la pregunta fundamental. Las variables pueden tomar diversos valores posibles, solo hay que conocer su valor óptimo, que lleve a conseguir el objetivo de la función general del problema. Las variables deben ser números reales mayores o iguales a cero: Xi ≥ 0

En cuanto a las restricciones de un problema de programación lineal, son todos aquellos elementos que limiten la libertad de los valores que pueden tener las variables. Por ejemplo, medios económicos, espacio de trabajo, mano de obra, etc.

Tras escribir la función objetivo según los datos del problema y escribir las restricciones en forma de sistema de inecuaciones, hay que averiguar el conjunto de soluciones factibles mediante una representación gráfica de las restricciones.

Para ello, debes calcular las coordenadas de los vértices del recinto de soluciones factibles (si son pocos) y calcular el valor de la función objetivo en todos los vértices para saber cuál de ellos presenta el valor máximo o mínimo según se requiera una cosa y otra.

¡Encontrarás muchos ejemplos de problemas y ejercicios de programación lineal en nuestros apuntes!

 

Aplicaciones de la programación lineal

 

Hay problemas cuyo número de posibles configuraciones o soluciones puede ser infinita, pero gracias a la programación lineal y la aplicación del método simplex, es posible reducir drásticamente el número de posibles soluciones óptimas.

¡Y hay muchos problemas prácticos de la investigación de operaciones pueden plantearse como problemas de programación lineal!

La programación lineal se usa en una infinidad de campos. Por ejemplo, está muy presente en la microeconomía, la ingeniería y la administración de empresas, tanto para aumentar los ingresos lo máximo posible como para reducir al mínimo los gastos de un sistema de producción.

Por tanto, aprender la metodología de la programación lineal te será muy útil si quieres formarte como ingeniero industrial y administrador porque dispondrás de herramientas muy útiles para mejorar la toma de decisiones en las empresas y, en consecuencia, mejorar los procesos de las mismas.

Algunos ejemplos son la gestión de inventarios, la cartera y la gestión de finanzas, la asignación de recursos humanos (horarios de trabajo, asignación de tareas, programación de horarios en el ámbito educativo, etc.), recursos de maquinaria y recursos naturales (uso del suelo para diferentes tipos de cultivos, por ejemplo), la planificación de campañas de publicidad, marketing (estudio de mercado, selección efectiva de medios de comunicación, asignación de territorio de ventas, distribución de ventas, etc.), administración forestal (tala de árboles para maximizar las ganancias), etc.

Seguro que practicando un poco con ejercicios y con un poco de motivación, ¡serás un as en los problemas de programación lineal!