Problemas, soluciones y aplicaciones de programación lineal [con ejemplo]

La ciencia de datos tiene muchas aplicaciones, una de las más destacadas es la optimización. Todos tendemos a centrarnos en optimizar cosas. La optimización se enfoca en obtener los resultados más deseados con los recursos limitados que tiene.

Hay todo tipo de problemas de optimización disponibles, algunos son pequeños, algunos son muy complicados. Mientras los revisa, encontrará una categoría específica llamada problemas de programación lineal. En este artículo, hemos discutido qué son y cómo puede trabajar en ellos.

Suponga que usted es un vendedor de frutas que puede comprar naranjas o manzanas o una determinada combinación de ambas. Sin embargo, solo tiene un presupuesto de INR 5,000 y solo puede almacenar 30 bolsas de ellos. Ahora, debe comprarlos de la manera que le brinde la mayor ganancia.

Ahora, una bolsa de naranjas te cuesta 500 INR, mientras que una bolsa de manzanas te cuesta 750 INR. Puedes ganar 100 INR con la venta de una bolsa de naranjas y 200 INR con la venta de una bolsa de manzanas.

Este problema tiene varias posibilidades. Puede elegir comprar solo naranjas, pero luego, solo tendrá 10 bolsas en su almacén y su ganancia será de INR 1000. De manera similar, puede elegir comprar solo manzanas y obtener INR 1500 como ganancia. También puedes comprar una combinación de los dos.

Estos problemas se denominan problemas de programación lineal y los analizaremos en detalle. Empecemos:

¿Qué es la Programación Lineal?

La programación lineal es un método para representar relaciones complejas mediante el uso de funciones lineales. Nuestro objetivo con la programación lineal es encontrar las soluciones más adecuadas para esas funciones. La relación real entre dos puntos puede ser muy compleja, pero podemos usar la programación lineal para representarlos con sencillez. La programación lineal encuentra aplicaciones en muchas industrias.

Conceptos básicos de la programación lineal

Estos son algunos términos fundamentales de la programación lineal:

Restricción

Las limitaciones (o restricciones) de sus variables de decisión se denominan restricciones. La mayoría de las restricciones de tiempo son las limitaciones que tiene en sus recursos para resolver un problema.

Decisión variable

Estas variables definen su salida. Su resultado depende de estas variables, por eso las llamamos 'variables de decisión'.

Restricción de no negatividad

Las variables de decisión de un problema de programación lineal solo pueden tener un valor no negativo. Significa que los valores de sus variables de decisión pueden ser iguales o mayores que cero solamente.

Función objetiva

La función objetivo es el objetivo de tomar su decisión. En términos simples, es el resultado final de su problema de programación lineal. Por ejemplo, cuando busca la ganancia máxima que puede obtener con un conjunto dado de recursos, la ganancia máxima es la función objetivo.

Formulación de problemas de programación lineal

Debe saber cómo formular una programación lineal para aplicarla en la vida real. Suponga que usted es un fabricante de juguetes y solo produce dos juguetes: A y B. En términos generales, sus juguetes requieren dos recursos X e Y para fabricarse. Aquí están los requisitos de sus juguetes:

• Una unidad del juguete A requiere una unidad del recurso X y tres unidades del recurso Y

• Una unidad del juguete B requiere una unidad del recurso X y dos unidades del recurso Y

Tiene cinco unidades del recurso X y 12 unidades del recurso Y. Sus márgenes de ganancia en la venta de estos juguetes son:

• 6 INR por cada unidad vendida del juguete A
• 5 INR por cada unidad vendida del juguete B

¿Cuántas unidades de cada juguete produciría para obtener la máxima ganancia?

La solución

Representemos nuestro problema de programación lineal en una ecuación:

Z = 6a + 5b

Aquí, z representa el beneficio total, a representa el número total de unidades de juguete A y b representa el número total de unidades B. Nuestro objetivo es maximizar el valor de Z (el beneficio).

Ahora, su empresa querría producir tantas unidades de estos juguetes como sea posible, pero tiene recursos limitados. Las limitaciones de nuestros recursos son las limitaciones de este problema. Solo tenemos un total de

a + b 5

Ahora cada unidad del juguete A y B requiere 3 y 2 unidades del recurso Y respectivamente. Y solo tenemos un total de 12 unidades de recurso Y, por lo que matemáticamente se vería así:

3a + 2b 12

Recuerda que los valores de las unidades del juguete A solo pueden ser números enteros. Esto significa que también tenemos las restricciones de a->0 y b<-0.

Entonces, ahora tiene un problema de programación lineal adecuado. Puede formular otros problemas de programación lineal siguiendo este ejemplo. Si bien este ejemplo fue bastante simple, los problemas de LP pueden volverse muy complicados.

Leer: Temas e ideas de proyectos de programación lineal

Pasos para formular problemas de programación lineal

Para formular un problema de programación lineal, siga estos pasos:

• Encuentre las variables de decisión
• Encuentre la función objetivo
• Identificar las restricciones
• Recuerda la restricción de no negatividad

Si un problema cumple con los criterios anteriores, es un problema de programación lineal. Es una buena práctica tener en cuenta este criterio cuando trabaje para identificar el tipo de problema.

Resolviendo Problemas de Programación Lineal con R

Si usa R, resolver problemas de programación lineal se vuelve mucho más simple. Eso es porque R tiene el paquete lpsolve que viene con varias funciones diseñadas específicamente para resolver este tipo de problemas. Es muy probable que utilice R con mucha frecuencia para resolver problemas de LP como científico de datos. Es por eso que hemos compartido dos ejemplos distintos para ayudarlo a comprender mejor su implementación:

Ejemplo

Comencemos con un problema básico. Una organización tiene dos productos con precios de venta de INR 25 e INR 20 y se denominan producto A y B respectivamente. Todos los días, tienen 1800 unidades de recursos para producir estos productos. El producto A requiere 20 unidades de recursos y el B requiere 12 unidades de recursos. El tiempo de producción de estos dos productos es de cuatro minutos y la organización obtiene un total de ocho horas de trabajo todos los días. El problema es, ¿cuál debe ser la cantidad de producción de cada uno de estos productos para maximizar las ganancias de la empresa?

Solución:

Empezaremos resolviendo este problema definiendo su función objetivo:

max(Ventas) = ​​max( 25 y 1 + 20 y 2 )

Aquí, 25 y 20 son los precios del producto A y B respectivamente, y1 es el total de unidades producidas del producto A e y2 es el total de unidades producidas del producto B. Nuestras variables de decisión son y1 e y2.

Ahora estableceremos las restricciones para nuestro problema:

Restricción de recursos:

20 años 1 + 12 años 2 1800

Limitación de tiempo:

4 y 1 + 4 y 2 8*60

Nuestro objetivo es encontrar el número correcto de productos que tenemos que fabricar para obtener el máximo beneficio.

Usando R para resolver el problema:

Usaremos lpsolve para resolver este problema de LP y comenzaremos con la configuración de la función objetivo:

> requerir(lpResolver)

Cargando paquete requerido: lpSolve

> objetivo.en <- c(25, 20)

> objetivo.en

[1] 25 20

Luego construiremos una matriz para las restricciones:

> const <- matriz(c(20, 12, 4, 4), nfila=2, porfila=VERDADERO)

> constante

[,1] [,2]

[1,] 20 12

[2,] 4 4

> restricciones_de_tiempo <- (8*60)

> recursos_restricciones <- 1800

> limitaciones_de_tiempo

[1] 480

> recursos_restricciones

[1] 1800

Ahora vamos a crear las ecuaciones ya definidas:

> rhs <- c(restricciones_de_recursos, restricciones_de_tiempo)

> derecho

[1] 1800 480

> dirección <- c(“<=”, “<=”)

> dirección

[1] “<=” “<=”

Una vez que se agrega toda la información necesaria, podemos comenzar a encontrar la respuesta óptima. La sintaxis de nuestro paquete es:

lp( dirección, objetivo, const.mat, const.dir, const.rhs )

> óptimo <- lp(dirección=”max”, objetivo.in, const, dirección, rhs)

> óptimo

Éxito: la función objetivo es 2625

> resumen (óptimo)

Modo de clase de longitud

dirección 1 -ninguno- numérico

x.count 1 -ninguno- numérico

objetivo 2 -ninguno- numérico

const.count 1 -ninguno- numérico

restricciones 8 -ninguno- numérico

int.count 1 -ninguno- numérico

int.vec 1 -ninguno- numérico

bin.count 1 -ninguno- numérico

binary.vec 1 -ninguno- numérico

num.bin.solns 1 -ninguno- numérico

objval 1 -ninguno- numérico

solución 2 -ninguno- numérico

presolve 1 -ninguno- numérico

computar.sens 1 -ninguno- numérico

sens.coef.from 1 -ninguno- numérico

sens.coef.to 1 -ninguno- numérico

duales 1 -ninguno- numérico

duals.from 1 -ninguno- numérico

duals.to 1 -ninguno- numérico

escala 1 -ninguno- numérico

use.dense 1 -ninguno- numérico

dense.col 1 -ninguno- numérico

dense.val 1 -ninguno- numérico

dense.const.nrow 1 -ninguno- numérico

dense.ctr 1 -ninguno- numérico

use.rw 1 -ninguno- numérico

tmp 1 -ninguno- carácter

estado 1 -ninguno- numérico

Después de ejecutar el código anterior, puede obtener las soluciones deseadas para nuestro problema.

Los valores óptimos para y1 e y2:

Recuerda que y1 e y2 eran las unidades del producto A y del producto B que teníamos que producir:

> solución$óptima

[1] 45 75

La cifra de ventas óptima:

La máxima ganancia que podemos generar con los valores obtenidos de y1 e y2 es:

> óptimo$objetivo

[1] 2625

Lea también: Álgebra lineal para el aprendizaje automático

Usos de la Programación Lineal

Como mencionamos antes, la programación lineal encuentra aplicaciones en muchas industrias. Aquí hay algunas áreas donde lo usamos:

• Con la creciente popularidad de los servicios de entrega, la programación lineal se ha convertido en uno de los métodos más favorecidos para encontrar las rutas óptimas. Cuando toma un Ola o Uber, el software usaría programación lineal para encontrar la mejor ruta. Empresas de entrega como Amazon y FedEx también lo utilizan para determinar las mejores rutas para sus repartidores. Se enfocan en reducir el tiempo de entrega y el costo.
• El aprendizaje supervisado del aprendizaje automático funciona sobre los conceptos fundamentales de la programación lineal. En el aprendizaje supervisado, debe encontrar el modelo matemático óptimo para predecir la salida de acuerdo con los datos de entrada proporcionados.
• El sector minorista utiliza la programación lineal para optimizar el espacio en los estantes. Con tantas marcas y productos disponibles, determinar dónde ubicarlos en la tienda es una tarea muy rigurosa. La colocación de un producto en la tienda puede afectar en gran medida sus ventas. Las principales cadenas minoristas como Big Bazaar, Reliance, Walmart, etc. utilizan la programación lineal para determinar la ubicación del producto. Deben tener en cuenta el interés de los consumidores al tiempo que garantizan la mejor ubicación del producto para obtener el máximo beneficio.
• Las empresas utilizan la programación lineal para mejorar sus cadenas de suministro. La eficiencia de una cadena de suministro depende de muchos factores, como las rutas elegidas, los tiempos, etc. Mediante el uso de la programación lineal, pueden encontrar las mejores rutas, tiempos y otras asignaciones de recursos para optimizar su eficiencia.

Más información sobre programación lineal y ciencia de datos

La programación lineal es uno de los conceptos más vitales de la ciencia de datos. También es un tema fundamental que debe conocer para convertirse en un científico de datos competente. Como comentamos, hay muchas aplicaciones para este concepto y puedes encontrar sus casos de uso en tu vida diaria.

Puede obtener más información sobre la ciencia de datos y sus conceptos relacionados en nuestro blog. Tenemos muchos recursos valiosos para ayudarlo a obtener más información. Aquí hay algunos para su lectura adicional:

• Razones principales para convertirse en un científico de datos
• Los algoritmos que todo científico de datos debe conocer
• Cómo convertirse en un científico de datos

Por otro lado, puede obtener un curso de ciencia de datos para aprender de expertos de la industria. Podrás aprender de forma interactiva a través de videos, cuestionarios y proyectos. Tomar un curso lo ayudará a aprender las habilidades necesarias para convertirse en un científico de datos profesional. Consulte el Diploma PG en ciencia de datos de IIIT-B y upGrad, creado para profesionales que trabajan y ofrece más de 10 estudios de casos y proyectos, talleres prácticos, tutoría con expertos de la industria, 1 a 1 con mentores de la industria, más de 400 horas de aprendizaje y asistencia laboral con las mejores empresas.