Leí en la wikipedia article, pero parece estar más allá de mi comprensión. Dice que es para la optimización, pero ¿cómo es diferente a cualquier otro método para optimizar las cosas?¿Qué es la programación lineal?
Una respuesta que me introduce en la programación lineal para que pueda comenzar a bucear en un material menos accesible para principiantes sería de gran ayuda.
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 polytope 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: supongamos que desea comprar una combinación de arena roja y arena azul. Supongamos también:
Si dibuja una imagen en el plano de cuánto puede comprar con estas limitaciones, es un pentágono convexo. Entonces, lo que sea que desee optimizar (por ejemplo, la cantidad total de oro en la arena), puede saber que un óptimo (no necesariamente el único óptimo) se encuentra 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 de este tipo se puede resolver en tiempo polinomial, en el número de restricciones o 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 programación lineal. Uno de los primeros ejemplos fue el "problema de la dieta": dado un menú de varios 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 limitaciones (vitaminas, calorías, la suposición 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 polinomial 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 programación convexa y programación entera. Con algunas cualificaciones, la programación convexa puede funcionar igual de bien que la programación lineal, siempre que el objetivo (lo que se quiere maximizar) sea lineal. Resulta que la convexidad, no los lados planos, es la razón principal de que la programación lineal tenga un buen algoritmo.
La programación de enteros, por otro lado, suele ser difícil. Por ejemplo, supongamos que en el problema de ejemplo, debe comprar la arena en bolsas de tamaño fijo en lugar de a granel; esa es la programación entera. Existe un teorema que puede ser NP-hard. Lo difícil que es en la práctica depende de cuán cerca está de la programación lineal. Hay algunos célebres ejemplos de problemas de programación entera en los que, milagrosamente, todos los vértices del programa lineal son puntos enteros. Entonces puede resolver el programa lineal y la solución pasará a ser integral. Un ejemplo de este problema es el problema del matrimonio, cómo casarse entre hombres y mujeres para maximizar la felicidad total. (O, n ciudades para n fábricas, n trabajos para n solicitantes, n computadoras para n impresoras, etc.)
Una gran diferencia (o, al menos, característica distintiva) de programación lineal es que las restricciones se modelan como lineales ecuaciones, es decir, todos son de la forma c_1 x_1 + c_2 x_2.... La sección de formulario estándar del artículo de wikipedia ofrece una visión general bastante buena de esto.
Otra diferencia/característica es que la programación lineal busca maximizar (o minimizar) UNA función: no puede realizar una optimización multiobjetivo con eficacia.
¿No es la maximización de una función la norma? – Mathias
@Mathias: quizás es la norma, pero no es el único tipo de optimización que existe. – awshepard
en realidad, ¡me interesaría saber qué tienes en mente! Un problema de optimización es matemáticamente la minimización de alguna función, y como no se pueden minimizar 2 funciones de la misma variable juntas, generalmente se termina minimizando una función de estas funciones (como una combinación ponderada de ellas ...). – Mathias
La programación lineal es un tema de "programación matemática", que también se denomina "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 quiere obtener un libro de texto, recomiendo this. Si desea buscar sus propios recursos, comience por buscar el Simplex method; es una técnica muy común para resolver estos programas, o el menos común pero definitivamente el tiempo polinomial Ellipsoid method. Aunque no lo he leído todo, al buscarlo rápidamente también sugiere this. PDF puede ser un buen lugar para comenzar. Asegúrese de que todo lo que termine leyendo cubra la dualidad (y quizás específicamente el Farkas' lemma), 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 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 convexa 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 de objetivo lineal. Las restricciones se escriben para enlazar el espacio del problema, mientras que la función objetivo es algo que intenta minimizar (o posiblemente maximizar) que satisfaga las restricciones. El simplex algorithm se usa típicamente para caminar a lo largo de los bordes de la intersección de 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 PL, es importante asegurarse de que las restricciones se vinculen correctamente a la función objetivo. Es posible definir restricciones que no den lugar a una posible solución (por ejemplo, x> 1 y -x> 1). Esto está sobrecargado. También es posible restringir un problema (por ejemplo, busque min x tal que x < 1).
Estoy seguro de que no tiene sentido preguntar dado que la pregunta ya está cerrada, pero ¿la persona que me modificó tendrá la amabilidad de explicar por qué? Gracias. – andand
Como todo el mundo ha dicho, la programación lineal es una forma de resolver problemas de optimización, cuyos términos son lineales.
Podría ayudar a entender qué tipos de problemas de PL de resolver
Un ejemplo en el que he usado la programación lineal es la construcción de un horario de restaurante.En un restaurante que tienen conjuntos de habilidades:
Y usted tiene 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 pastor de una iglesia local. Los empleados también tienen un costo asociado. Bob podría costar $ 10.50/hora mientras que Suzy es de $ 5.15/hora. Finalmente, los empleados pueden tener un mínimo de horas garantizadas. Como Bob ha sido empleado durante 15 años, el jefe dice que siempre obtendrá al menos 35 horas.
El restaurante en sí tiene demandas. 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 en la tarde, y 4 cocineros, 4 servidores, 3 anfitriones, 2 gerentes, 2 bussers en 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 entrar en horas extras. Ningún empleado puede programarse para menos de 2 horas (porque sería una molestia hacer un viaje de 30 minutos por un turno de 2 horas), los empleados no pueden trabajar dos turnos superpuestos, etc.
Ahora que se cumplen todos estos requisitos, brinde un cronograma que cumple con todos los requisitos y produce 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, las variables, los límites variables y restricciones.
Como queremos minimizar el costo, nuestra función objetivo va a involucrar los cambios que los empleados trabajan y los costos asociados (duración del turno * salario).
Las variables en este caso son los cambios que cada empleado puede realizar.
Los límites en estas variables son enteros entre 0 y 1, porque o bien un empleado está trabajando en el turno (1), o bien el empleado no está trabajando en el turno (0). Esto, dicho sea de paso, es un programa especial, llamado Binary Integer Program o BIP, porque todas las variables son enteros (sin valores fraccionarios) y todos los valores son 0 o 1.
Las restricciones son igualdad/restricciones de desigualdad basadas en los requisitos anteriores.
Por ejemplo, si Bob y Suzy pueden trabajar como cocineros por 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.
Una vez que haya definido todas las restricciones que modelan su problema, puede comenzar a resolver el problema.Si se puede encontrar una solución (y dependiendo de las limitaciones el problema puede no ser factible), le dará las asignaciones de empleados que producen el menor costo de mano de obra semanal.
En pocas palabras, se trata de volver a escribir su problema como un conjunto de ecuaciones lineales, y luego resolver esas ecuaciones. – FrustratedWithFormsDesigner
¿De qué "otro método" podría estar hablando? –
Buena pregunta, me olvidé de esto (desde Calc comenzamos a llamarlo "optimización" en lugar de programación lineal) –