¿Qué es la programación lineal?

¡Qué pregunta tan maravillosa! ¿Qué es exactamente la programación ‘lineal ‘ (LP)?

Tomemos el clásico problema que motivó la creación de este campo para comprender qué es un LP:

Dadas ‘n’ personas que pueden hacer ‘m’ trabajos con diversos grados de competencia (velocidad de pensamiento), ¿cuál es la mejor asignación de personas para trabajos de modo que los trabajos se completen en el menor tiempo posible?

Viajemos en el tiempo. Regrese a 1950 mentalmente y “piense” cómo resolvería este problema. Piénsalo genuinamente.

Probaría algunos enfoques ad-hoc haciendo las cosas manualmente, pero nunca estará seguro de si realmente tiene la coincidencia “más rápida”. ¿Más rápido qué? Puede comparar a otros y nunca estar seguro.

Te estás preguntando si todo esto podría ser lanzado como un “grupo de ecuaciones” que puedes resolver de alguna manera, dado un objetivo , es decir, maximizar la velocidad de finalización. Es decir, no quiere “una” solución para el sistema de ecuaciones, ¡quiere “la” solución que sea óptima! Es decir, el valor más alto / más bajo depende de la función objetivo (que podría ser maximizar o minimizar algo).

Estas ecuaciones que se presentan rara vez son exactas (lea las igualdades). En la mayoría de los casos, desea decir que esta ecuación es “menor / mayor o igual que” algún límite inferior / superior. ¿Razón? Desea el valor “óptimo”. Pero, ¿qué es lo mejor? Necesita un ‘rango’ de valores para la comparación. De ahí las desigualdades. Si son todas igualdades, realmente no optimizas nada per se. Simplemente “resuelve” las ecuaciones para calcular la respuesta: podría haber infinitas soluciones que imposibiliten seleccionar la mejor. Pero suponiendo que exista una solución, siempre la obtendrá.

Ahora, tenemos nuestras “ecuaciones” que son desigualdades. Llamémoslas restricciones. Como los ha “acotado”, tiene sentido llamarlos así. También tiene una función objetivo que le indica si desea la “mejor” solución más baja / más alta posible.

¿Queda algo? Si. ¿Pueden estas ecuaciones / restricciones ser ecuaciones arbitrarias o tienen que obedecer ciertas “reglas”? Ellas hacen. En el caso de LP, estas restricciones y la función objetivo (que también es una ecuación) deben ser “lineales”.

Funciones lineales: hablando de manera cruda, piense en ellas como “líneas” en el espacio cartesiano. Las líneas son bastante geniales, matemáticamente hablando. Una intersección de 2 líneas da un solo punto, que es fácil de calcular. Dado un montón de líneas, uno puede calcular todos los lugares en los que se cruza el “grupo de líneas”. ¿Quieres un ejemplo?

Si 5 manzanas cuestan $ 10, ¿cuánto cuestan 20 manzanas?

Intente resolver esto “geométricamente”: manzanas en el eje ‘x’ y costo en el eje ‘y’. Dibuja una línea desde (0,0) hasta (5,10). Extienda esta línea más y vea cuál es el ‘valor y’ cuando x = 20. ¡Simple!

¿Qué pasa si 5 manzanas cuestan $ 10 pero 20 manzanas cuestan $ 2 (como en los Estados Unidos :)? Esta NO es una relación lineal. La línea dice que el valor y debería ser $ 40 cuando x = 20. Pero no $ 2. Esto hace que la previsibilidad sea mucho más difícil. Puede ver que se volverá complicado muy rápidamente si estas relaciones no se basan en líneas (es decir, no lineales).

Entonces, si todo es lineal (objetivo y restricciones), ¿qué hago a continuación? Agrega una restricción para cada una de las variables: en 2D es como agregar ecuaciones para los ejes (x = 0; y = 0) pero lo hace (x> = 0 o y> = 0) diciendo que “cualquier valor positivo sería estar bien.

Luego calcula el valor de la función objetivo en la intersección de la función objetivo y cada uno de los “puntos de esquina” de todas las restricciones (conceptualmente hablando). Todas las restricciones se intersectarán de tal manera que encerrarán un “polígono” (en 2D) de “todos los valores posibles de la función objetivo”. ¿Piensa dónde reside el valor óptimo? En las esquinas! (¿Por qué? Piensa en ello 🙂

Ahora, todo lo que necesita hacer es calcular el “valor” de la función objetivo en cada una de las esquinas de la “región factible” (es decir, el polígono de arriba) y solo encontrar el máximo / mínimo. ¡Sencillo!

Entonces, si todo es “como una línea”, ¡puedo encontrar una manera de calcular el máximo / mínimo resolviendo ecuaciones simples! ¡Entonces puedo presentar una prueba de corrección que me dice que mi óptimo es el óptimo! (Piensa, dualidad).

Pero por qué se llama un “programa”. Bueno, cuando este problema fue dado por el Departamento de Defensa, era parte de un “programa”. Se utilizaron funciones lineales para modelar / resolver el problema y el programa se denominó lineal. El nombre “programa lineal” se ha quedado bloqueado. El nombre acaba de pasar a programación dinámica, programación convexa, etc.

Ahora, lea lo que Justin Rising ha escrito anteriormente y comprenderá por qué las matemáticas son como son. Esperemos que esto ayude a iluminar la idea abstracta detrás de los LP y lo fascinantes que pueden ser. ¡Imagínese poder aproximar las restricciones existentes de la vida real como funciones lineales, poner un objetivo en eso y obtener un valor que pueda ayudarlo a tomar sus decisiones de la vida real de la manera más óptima posible! Es alucinante 🙂

Alimento para el pensamiento: ¿Pueden los objetivos / restricciones ser no lineales? ¿Arbitrariamente o hay algunas reglas allí también? Piénsalo. Puede enamorarse de la optimización matemática en su conjunto (u odiarla 🙂

¡La mejor de las suertes!

La programación lineal consiste en la formulación de problemas de la vida real en las formas matemáticas. La formulación del problema incluye:

  1. Identificación de las variables de decisión.
  2. escribiendo la función objetivo.
  3. escribiendo las restricciones.
  4. escribiendo las restricciones no negativas.

La función objetivo y las restricciones son lineales, por lo tanto, la formulación se llama formulación de programación lineal.

Un programa lineal es un problema de optimización en el que se nos pide que encontremos el valor de [matemática] x [/ matemática] que minimiza [matemática] c ^ Tx [/ matemática] sujeto a las condiciones que [matemática] Ax = b [ / math] y [math] x \ geq 0 [/ math]. La palabra “programación” en este sentido es un uso anterior que precede a las computadoras.

¿Cómo se puede aplicar la programación lineal en la industria del software? Cualquier ejemplo?