Problema de planificación y programación.
La planificación y programación automatizadas se ocupa de llevar a cabo estrategias o secuencias de acciones. La planificación moderna, incluso dentro de la IA, refleja cada vez más la integración de la teoría y las técnicas algorítmicas de alto rendimiento de la investigación de operaciones desde al menos la década de 1950.
Introducción a los problemas de planificación
La planificación es la organización del logro de objetivos en un área específica, con diferentes medios y durante un período/jerarquía. El resultado de este problema es un "plan" que responde detalladamente a las preguntas del tipo QQOQCC: quién, qué, dónde, cuándo, cómo y cuánto.
El problema de planificación permite, según las condiciones y la información, responder a las siguientes preguntas:
- ¿Cómo gestionar la secuencia lógica de tareas y distribuirlas en el tiempo?
- ¿Cómo analizar las cargas de trabajo solicitadas a los recursos o medios si son limitados?
- ¿Cómo expresar una necesidad de recursos o medios si no son limitados?
- ¿Cómo tener en cuenta las limitaciones externas al proyecto (pedido del cliente, entrega del proveedor, etc.)?
- ¿Cómo analizar las consecuencias de una brecha entre los eventos reales y los previstos?
- ¿Cómo identificar las fechas de inicio tardío o finalización anticipada de las actividades?
- ¿Cómo simular los supuestos optimistas, pesimistas o más probables?
- ¿Cómo analizar el impacto de un peligro o un riesgo si se convierte en un problema?
- ¿Cómo priorizar las tareas?
El problema de asignación está relacionado con muchos otros problemas en la investigación de operaciones (reducción de problemas en los 21 problemas de Karp, por ejemplo). Aquí veremos dos subproblemas que se encuentran con frecuencia en los problemas de asignación.
Subproblema: programación
El problema de programación es un problema de planificación de tareas en el que hay que decidir el orden en el que se deben ejecutar las tareas. Este problema es Np-difícil dada la variedad y complejidad de sus restricciones.
Los diferentes métodos presentados en este curso permiten mostrar de forma clara y rápida los datos relacionados con la realización de un plan, tales como:
- tiempos, plazos
- medios o recursos
- los costos.
El problema clásico de programación es:
Subproblema: Asignación
Este problema consiste en la mejor asignación de tareas a los agentes. Cada agente puede realizar una sola tarea por un costo determinado y cada tarea debe ser realizada por un solo agente. Todas las asignaciones (es decir, los pares agente-tarea) tienen un costo definido, siendo el objetivo minimizar el costo total de las asignaciones para realizar todas las tareas. Este problema se resuelve en tiempo polinomial.
Subproblema: transporte
Como los dos problemas anteriores, el problema del transporte es una maximización. El problema de transporte es una de las subclases de problemas de programación lineal donde el objetivo es transportar varias cantidades de un solo producto homogéneo que inicialmente se almacena en varios orígenes, a diferentes destinos, de modo que el transporte total sea mínimo.
Deja unI la cantidad de la mercancía disponible en el origen i; bj o la cantidad de producto requerida para el destino j; vsij el costo de transportar una unidad de una mercancía desde el origen i hasta el destino j; y xij es la cantidad transportada desde el origen i hasta el destino j.
Aqui esta el problema:
Si la suma de las fuentes es igual a la suma de las demandas, se dice que el problema está equilibrado, en cuyo caso las restricciones se convierten en igualdades. En caso contrario, se crea un punto de demanda virtual (dummy) correspondiente al exceso de oferta y con coste de transporte cero.
El problema del transporte a menudo se representa como un gráfico bipartito con un problema de flujo (acoplamiento). Aquí mostraremos otras variantes para solucionar este problema.
