Imágenes de Wikipedia

Para aquellos más familiarizados con el tema, probablemente sepan que los orígenes de la programación lineal comenzaron aproximadamente a mediados de la década de 1950, y un matemático llamado Jorge Dantzig Estaba involucrado. Si esa fuera su suposición, estaría en lo cierto en su mayor parte, pero todos sabemos que atribuir el mérito de muchos (si no todos) los descubrimientos científicos y matemáticos no es tan simple: a menudo hay más de una persona que contribuyó a la desarrollo de un área de investigación, y ese es ciertamente el caso de la programación lineal. El progreso inicial fue realizado en paralelo por dos matemáticos que trabajaban de forma independiente a mediados del siglo XX y, por lo tanto, el crédito se debió sin duda a más de una persona.

Sin entrar demasiado en la historia, intentemos tener una idea aproximada de la línea de tiempo de los avances clave en la programación lineal. La primera idea para la programación lineal surgió de Leonid KantorovichLa intención de reducir los costos para su propio ejército mientras aumenta los de su ejército enemigo. Sus esfuerzos tuvieron lugar durante la Segunda Guerra Mundial en 2, pero la URSS los descuidó en ese momento. Mientras tanto, TC Koopman tenía una idea similar a la de Kantorovich, pero trabajaba en ella de forma independiente y se adaptaba a sus propias aplicaciones económicas. Unos años más tarde, en 1941, Frank Lauren Hitchcock comenzó a trabajar en ideas similares que, nuevamente, se adaptaron a sus propios problemas de transporte, pero desarrolló una solución similar a lo que ahora se conoce como el método simplex. Para abreviar, los tres hombres estaban en el camino correcto, pero cuando el descubrimiento mereció un Premio Nobel de Economía, Hitchcock había muerto, y así. Kantorovich y Koopmans se llevaron el crédito.

Entre 1946 y 1947, George B. Dantzig desarrolló un algoritmo para el Método Simplex que eficiente. abordó problemas de programación lineal en mayoria de los casos — Este fue un logro increíble. Poco tiempo después, Dantzig presentó la teoría de la dualidad en la programación lineal a John Von Neumann, quien había estado desarrollando una teoría de juegos, y se sorprendió al descubrir que Dantzig había progresado en un problema sin resolver de la programación lineal. Esto fue muy emocionante. (¿Alguien quiere a Will Hunting? ¡El logro de Dantzig fue en realidad la inspiración para la historia de esa película!).

El indomable Will Hunting (Fuente)
 

Esas áreas ahora están bien estudiadas y se usan mucho en importantes aplicaciones de la vida real. Después de la Segunda Guerra Mundial, el trabajo de Dantzig se ha aplicado a las aplicaciones de planificación diaria en muchas industrias, y los matemáticos pronto lograron avances en la resolución de la programación lineal en tiempo polinomial. Eso fue un poco de historia sobre sus orígenes (y puedes leer todo al respecto esta página, por ejemplo), pero por ahora, entremos brevemente en los avances más recientes.

Más recientemente, la investigación en programación lineal se ha centrado en desarrollar algoritmos que mejoren la complejidad computacional. Este papel, por ejemplo, analiza matrices inversas dinámicas más rápidas para LP más rápidos. (Sin embargo, es una ciencia de la computación pesada, y no necesitamos entrar en ella). En general, hay mucha investigacion entrar en la optimización matemática hoy en día en su conjunto, ya sea para acelerar los cálculos, reducir las ineficiencias o introducir nuevas aplicaciones en el aprendizaje automático.

Existen innumerables paquetes de software para admitir la programación lineal aplicada en la industria. Tienes IBM CPLEX, GUROBI software de optimización patentado, paquetes Python de código abierto (como Ciencia, piomo, Pulpa, GEKKO), y probablemente mucho más. Un hecho interesante es que todos estos paquetes usan lo que llamamos un Lenguaje de modelado algebraico (AML), un paradigma crítico que se desarrolló a fines de la década de 1970. Todos estos paquetes son excelentes en lo que hacen por diferentes razones y hay muchas publicaciones de blog que puede leer para obtener una buena comparación entre cada uno de ellos: consulte esta publicación, por ejemplo.

No entraremos en detalles, pero hablemos de lo que debe saber como usuario de la teoría y la metodología de la programación lineal. La teoría de la programación lineal es hermosa por sí misma, pero lo es aún más cuando puedes establecer las conexiones entre la programación lineal y el álgebra lineal. Ya sea que haya recogido un libro de texto, tomó un curso introductorio en lineao aprendido esto formalmente en la escuela, no hay duda de que llegarás a la misma conclusión de que la programación lineal es un caso especial de álgebra lineal, y probablemente una de las extensiones más importantes y relevantes del álgebra lineal elemental.

Independientemente de la ruta que haya elegido tomar para aprender programación lineal, es probable que haya encontrado la siguiente secuencia de temas (o similar):

• Componentes de un programa lineal
• Formas de programas lineales
• Problemas comunes de programación lineal
• Teoría de la dualidad y análisis de sensibilidad
• Tipos especializados de programas lineales
• Programación lineal aplicada

(¿Le parece bien? Si me he perdido algo, deje un comentario a continuación). Si ese es el caso y dice que está familiarizado con todos estos temas, entonces creo que debería dejar de leer aquí y llamarlo un día (¡y felicítese porque acaba de recibir una breve historia de la programación lineal!). Sin embargo, si al menos uno de los temas anteriores le suena nuevo, le diría que continúe leyendo este artículo, ya que creo que valdrá la pena.

En aras de mantener las cosas breves y consumibles, vamos a omitir los dos primeros temas de la secuencia, pero aquí hay un buen recurso donde puede obtener más información sobre los componentes de un programa lineal y las formas de los programas lineales. De manera similar, omitiremos la discusión de la teoría de la dualidad y el análisis de sensibilidad, pero algunos recursos excelentes son esta página y esta página.

Ahora, si está intentando aplicar los principios de programación lineal para resolver un problema, es probable que haya otras clases de modelos que haya considerado para su problema y haya llegado (con suerte razonablemente) a la conclusión de que un modelo de programación lineal solucionaría tu problema. Si es así, puede ser que también hayas pensado en algunos problemas clásicos que usan programación lineal: El problema de la mezcla, El problema de la asignación, El problema del transporte, El problema del viajante de comercio, y muchas más.

Si su problema suena más o menos como cualquiera de estos problemas, entonces ya sabemos cómo resolver su problema y está listo para comenzar. De lo contrario, querrá pensar más profundamente en su problema y encontrar una manera de traducirlo inteligentemente en un problema de programación lineal. Considere algunas preguntas como:

• ¿Compras necesite un LP para resolver este problema, o existe la posibilidad de que esto podría ser un problema trivial?
• ¿Cuál es tu principal objetivo?
• ¿Solo tienes un objetivo o hay muchos?
• ¿Es un problema de maximización o un problema de minimización?
• ¿Cuáles son todas las restricciones posibles que se te ocurran?
• ¿Son todas sus variables de decisión no negativas o necesita algún tipo especial de especificación?

He explicado un montón por ahora, así que en lugar de hablar un poco más, solo te mostraré cómo se vería un problema de programación lineal aplicada "no estándar", en código. Si recuerda, dijimos que hay muchos paquetes Python de código abierto disponibles que usan el paradigma AML. PuLP es uno de ellos, así que usaremos PuLP por ahora.

Este es un ejemplo semi-hipotético con 12 refugios para personas sin hogar de la vida real en la ciudad de Toronto: direcciones de la vida real, edificios de la vida real, número falso de habitaciones/camas disponibles (es decir, suministro/capacidad), número falso de nuevos solicitudes de camas (es decir, demanda), 'cluster' falso al que pertenece un refugio. Tema sombrío, lo sé. Los datos fueron adquiridos de la ciudad Catálogo de datos abiertos.

Código por autor

Supongamos que estamos viendo la instantánea de la oferta y la demanda de camas en los refugios para personas sin hogar en Toronto de cualquier día aleatorio. La selección de refugios para personas sin hogar que estamos analizando se hizo estratégicamente para que busquemos grupos dispersos por la ciudad: algunos refugios están cerca de otros, mientras que algunos están lejos del alcance de otros. Tenga esto en cuenta ya que es relevante para el problema de optimización que especificaremos. Tenga en cuenta que la demanda es a nivel de grupo y no a nivel de alojamiento. 

Además, hay costos (tanto monetarios como temporales) asociados con cada cama adicional disponible en un refugio, y los costos varían, a veces por refugio y otras por grupo. Definiremos un conglomerado como un grupo de refugios que están relativamente cerca unos de otros: un "mapa" visual aproximado de ubicaciones relativas entre sí a continuación.

Además del costo monetario, digamos que también hay un costo de tiempo asociado con la apertura de cada cama adicional, también a veces por el refugio y otras veces por grupo. El razonamiento de este costo de tiempo es que puede haber demanda de una cama dentro del vecindario/grupo, pero la solicitud se realizó en una ubicación con capacidad máxima y el usuario del servicio debe ser reubicado.

Configuraremos esto como un problema de optimización multiobjetivo por lo que nuestra especificación (en el código) deberá poder adaptarse a eso. Primero, minimizamos el costo monetario y luego minimizamos los costos de tiempo. Los coeficientes de la segunda función objetivo corresponden al aumento de tiempo relativo dentro de un grupo de refugio específico (es decir, el costo del tiempo para trasladar a los nuevos usuarios del refugio X al refugio Y). Tenga en cuenta que la especificación del problema de optimización no es única y puede haber más de una especificación que conduzca a los mismos resultados.

Aquí está todo el código como un script largo. El código de especificación del modelo podría condensarse/simplificarse, pero lo mantendremos así para que pueda ver todos los detalles con mayor claridad. Comentamos la función objetivo inicial ya que la agregamos como una restricción de costo monetario en el paso #5.

Código por autor

Si ha ejecutado este código localmente, verá el resultado de la siguiente manera:

A:2671Islington:      1 additional bed(s). B1:26Vaughan:         0 additional bed(s). B2:14Vaughan:         5 additional bed(s). C:850Bloor:           1 additional bed(s). D1:38Bathurst:        2 additional bed(s). D2:38Bathurst:        1 additional bed(s). E1:135Sherbourne:     6 additional bed(s). E2:339George:         5 additional bed(s). E3:339George:         4 additional bed(s). E4:339George:         0 additional bed(s). E5:339George:         0 additional bed(s). E6:339George:         4 additional bed(s). Optimal Value of Objective Function:  36.9

Su primera pregunta podría ser: ¿No es este un problema trivial? Y si no, ¿cómo es que? ¡Esta es una pregunta importante, y es una que podría justificar no especificar un problema de programación lineal en absoluto! Sin embargo, en este caso, no es un problema trivial y necesitamos una especificación de LP, piense por qué.

Insinuación: Primero, minimizamos los costos monetarios y luego minimizamos los costos de tiempo. ¿Puedes pensar en una manera de resolver este problema a mano?

Referencias

[1] B. Kolman y RE Beck, Programación Lineal Elemental con Aplicaciones (1995), Ciencia Directa

[2] GB Dantzig, Reminiscencias sobre los orígenes de la programación lineal (1982), Departamento de Investigación de Operaciones — Universidad de Stanford

[3] R. Fourer, DM Gay, BW Kenighan, Un lenguaje de modelado para la programación matemática (1990)
 
 
Mariam Walaa es un estudiante de matemáticas con más de 3 años de experiencia como científico de datos en ingeniería, comercio minorista y academia trabajando en una variedad de problemas que van desde el procesamiento del lenguaje natural y los sistemas de recomendación hasta la programación lineal y la optimización.
 

• Distribución de relaciones públicas y contenido potenciado por SEO. Consiga amplificado hoy.
• Platoblockchain. Inteligencia del Metaverso Web3. Conocimiento amplificado. Accede Aquí.
• Fuente: https://www.kdnuggets.com/2023/02/linear-programming-101-data-scientists.html?utm_source=rss&utm_medium=rss&utm_campaign=linear-programming-101-for-data-scientists