algorithm - simplex - programacion lineal teoria

¿Qué es la programación lineal? (5)

Como todos los demás han dicho, la Programación lineal es una forma de resolver problemas de optimización, en la que los términos son lineales.

Podría ayudar entender qué tipo de problemas resuelven los LP

Un ejemplo en el que he usado la programación lineal es la creación de un horario de restaurante. En un restaurante tienes habilidades:

Cocineros
Servidores
Lavaplatos
Hospedadores
Bussers
Gerente etc

Y tienes empleados, cada uno con uno o más conjuntos de habilidades. Cada empleado también tiene una disponibilidad específica. Por ejemplo, Bob no puede trabajar los domingos por la mañana porque es un pastor en una iglesia local. Los empleados también tienen un costo asociado. Bob podría ser de $ 10.50 / hr, mientras que Suzy es de $ 5.15 / hr. Finalmente los empleados pueden tener horas mínimas garantizadas. Desde que Bob ha sido empleado durante 15 años, el jefe dice que siempre obtendrá al menos 35 horas.

El restaurante en sí tiene exigencias. Por ejemplo, tiene 3 turnos: mañana, tarde y noche, y cada uno de estos turnos tiene un conjunto de requisitos de personal: Necesitamos 1 cocinero, 1 servidor, 1 gerente por la mañana, 3 cocineros, 2 servidores, 2 anfitriones, 2 gerentes por la tarde, y 4 cocineros, 4 servidores, 3 anfitriones, 2 gerentes, 2 empresarios por la noche. Cada turno tendrá una duración, y usted puede calcular el costo de cada turno multiplicando la duración por el salario por hora del empleado.

Finalmente, tenemos leyes estatales y federales, y algunas reglas básicas de "negocios": ningún empleado puede trabajar más de 8 horas sin tener que trabajar horas extras. No se puede programar a ningún empleado por menos de 2 horas (ya que sería una aspiración para hacer un viaje de 30 minutos por un turno de 2 horas), los empleados no pueden trabajar en dos turnos superpuestos, etc.

Ahora, dado todos estos requisitos, dame un programa que cumpla con todos los requisitos y produzca el menor costo de mano de obra.

Este es un ejemplo de un problema de optimización de programación lineal.

Un programa lineal típicamente consiste en:

Una función objetivo, variables, límites variables y restricciones.

Dado que queremos minimizar el costo, nuestra función objetivo implicará los cambios en los que trabajan los empleados y los costos asociados (duración del turno * salario).

Las variables en este caso, son los turnos en que cada empleado puede trabajar.

Los límites de estas variables son enteros entre 0 y 1, porque un empleado está trabajando el turno (1) o el empleado no está trabajando el turno (0). Por cierto, este es un programa especial, llamado abreviado Programa de enteros binarios o BIP, porque todas las variables son enteros (sin valores fraccionarios) y todos los valores son 0 o 1.

Las restricciones son restricciones de igualdad / desigualdad basadas en los requisitos anteriores.

Por ejemplo, si Bob y Suzy pueden trabajar como cocineros en la mañana, entonces Bob_Morning_Cook1_Shift + Suzy_Morning_Cook1_Shift = 1 , con Bob_Morning_Cook_Shift = {0,1} y Suzy_Morning_Cook_Shift = {0,1} debido a los límites mencionados anteriormente. Estas tres piezas de información especifican que, como máximo, solo un empleado puede ser asignado como el primer cocinero de la mañana.

Entonces, una vez que haya definido todas las restricciones que modelan su problema, puede comenzar a resolverlo. Si se puede encontrar una solución (y dependiendo de las restricciones, el problema puede no ser factible), le dará las asignaciones de los empleados que producen el costo laboral semanal más bajo.

Leí el article wikipedia, pero parece estar más allá de mi comprensión. Dice que es para optimización, pero ¿en qué se diferencia de cualquier otro método para optimizar cosas?

Una respuesta que me introduzca a la programación lineal para que pueda comenzar a sumergirme en un material menos accesible para principiantes sería lo más útil.

La programación lineal es un tema de "programación matemática", que también se conoce como "optimización matemática". Los programas lineales difieren de los programas matemáticos generales en que para un programa lineal (LP) todas las funciones de restricción y la función objetivo son lineales con respecto a sus variables.

Un buen lugar para comenzar sería here si quiere el trabajo original de Dantzig, o si desea obtener un libro de texto, le recomiendo this . Si desea buscar sus propios recursos, comience por buscar el método Simplex: es una técnica muy común para resolver estos programas, o el método Elipsoide menos común pero definitivamente polinomial. Aunque no lo he leído todo, repasarlo rápidamente también sugiere que this PDF puede ser un buen lugar para comenzar. Asegúrese de que lo que sea que termine de leer cubra la dualidad (y tal vez específicamente el lema de los Farkas ), ya que es una idea central en la mayoría de los solucionadores de LP.

Las extensiones más naturales son programas enteros (similares a los LP, pero todas las variables deben tomar valores enteros, es decir, sin componentes fraccionarios) o programación convexa (quizás una extensión más general). Un buen libro de texto de optimización convexo está disponible en formato PDF here .

La programación lineal es una técnica de optimización que implica restricciones lineales y una función objetivo lineal. Las restricciones se escriben para delimitar el espacio del problema, mientras que la función objetivo es algo que intenta minimizar (o posiblemente maximizar) que satisface las restricciones. El algoritmo símplex se usa normalmente para caminar a lo largo de los bordes de la intersección de la restricción para encontrar el valor mínimo (o máximo) de la función objetivo que satisface las restricciones.

Al configurar un problema de LP, es importante asegurarse de que las restricciones limiten correctamente la función objetivo. Es posible definir restricciones que no den como resultado una solución posible (por ejemplo, x> 1 y -x> 1). Esto es demasiado limitado. También es posible sub-restringir un problema (por ejemplo, encontrar min x tal que x <1).

Las respuestas hasta ahora han dado una definición algebraica de programación lineal y una definición operacional. Pero también hay una definición geométrica. Un politopo es una generalización n-dimensional de un polígono (en dos dimensiones) o un poliedro (en tres dimensiones). Un politopo convexo es un politopo que también es un conjunto convexo. Por definición, la programación lineal es un problema de optimización en el que desea maximizar o minimizar una función lineal en un politopo convexo.

Por ejemplo: suponga que desea comprar una combinación de arena roja y azul. Supongamos también:

No se puede comprar una cantidad negativa de ningún tipo.
El depósito solo tiene 300 libras de arena roja y 400 libras de arena azul.
También su jeep tiene un límite de peso de 500 libras.

Si dibuja en el plano cuánto puede comprar con estas restricciones, es un pentágono convexo. Entonces, lo que sea que desee optimizar (digamos, la cantidad total de oro en la arena), puede saber que un óptimo (no necesariamente el único óptimo) está en uno de los vértices del politopo. De hecho, hay un resultado mucho más fuerte: incluso en altas dimensiones, cualquier problema de programación lineal puede resolverse en tiempo polinomial, en el número de restricciones o en los lados putativos del politopo. Tenga en cuenta que no todas las restricciones corresponden a un lado. Si la restricción es una igualdad, podría reducir la dimensión del politopo. O si la restricción es una desigualdad, podría no crear un lado si ya está implícito en todas las demás restricciones.

Hay muchos problemas prácticos de optimización que son la programación lineal. Uno de los primeros ejemplos fue el "problema de la dieta": dado un menú de muchos tipos de alimentos, ¿cuál es la dieta balanceada más barata posible? Es un problema de programación lineal porque el costo es lineal y porque todas las restricciones (vitaminas, calorías, el supuesto de que no se puede comprar una cantidad negativa de alimentos, etc.) son lineales.

Pero, la programación lineal es aún más importante por una razón teórica. Es uno de los algoritmos de tiempo polinómico más potentes para la optimización o para cualquier otro propósito. Como tal, es muy importante como un sustituto para resolver aproximadamente otros problemas de optimización y como una subrutina para resolverlos exactamente.

Sí, dos generalizaciones son la programación convexa y la programación de enteros. Con algunas calificaciones, la programación convexa puede funcionar tan bien como la programación lineal, siempre que el objetivo (la cosa a maximizar) sea lineal. Resulta que la convexidad, no los lados planos, es la razón principal por la que la programación lineal tiene un buen algoritmo.

La programación de enteros, por otro lado, suele ser difícil. Por ejemplo, suponga que en el problema de ejemplo tiene que comprar la arena en bolsas de tamaño fijo en lugar de a granel; eso es entonces la programación entera. Hay un teorema que puede ser NP-duro. Lo difícil que es en la práctica depende de lo cerca que esté de la programación lineal. Hay algunos ejemplos célebres de problemas de programación de enteros en los cuales, milagrosamente, todos los vértices del programa lineal son puntos enteros. Luego puedes resolver el programa lineal y la solución pasará a ser integral. Un ejemplo de tal problema es el problema del matrimonio, cómo casar n hombres y n mujeres entre sí para maximizar la felicidad total. (O, n ciudades a n fábricas, n trabajos a n solicitantes, n computadoras a n impresoras, etc.)

Una gran diferencia (o al menos, característica distintiva) de la programación lineal es que las restricciones se modelan como ecuaciones lineales , es decir, todas tienen la forma c_1 x_1 + c_2 x_2... La sección de formulario estándar del artículo de wikipedia da una visión general bastante buena de esto.

Otra diferencia / característica es que la programación lineal está buscando maximizar (o minimizar) UNA función: no se puede hacer efectivamente la optimización de objetivos múltiples.