Problema de planificación 101

Problema de planificación y programación

La planificación y programación automatizadas se trata de llevar a cabo estrategias o secuencias de acciones. La planificación moderna, incluso dentro de la IA, ha reflejado 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 en un período / jerarquía. El resultado de este problema es un “plan” que responde en detalle 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 diferencia entre eventos reales y pronosticados?
  • ¿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 riesgo si se convierte en 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 programación de tareas en el que se trata de decidir el orden en el que se deben realizar las tareas. Este problema es Np-difícil teniendo en cuenta la variedad y complejidad de sus limitaciones.

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 de programación clásico es el siguiente:

Sea N tareas TI requiriendo una duración deI datos y fecha de inicio tI por determinar. El problema está sujeto a dos tipos de limitaciones: limitaciones de tiempo: duración y precedencia de la tarea; restricciones de recursos - disyuntivas: si las tareas i y j se realizan en la máquina k, deben realizarse en tal o cual orden; o acumulativo: tarea que consume unik del recurso k. El recurso k tiene una capacidad Ak. En todo momento, la suma de los consumos de la máquina k debe ser menor que su capacidad.

Subproblema: asignación

Este problema consiste en asignar mejor las 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. Las asignaciones (es decir, los pares agente-tarea) tienen un costo definido, con el objetivo de minimizar el costo total de las asignaciones para poder realizar todas las tareas. Este problema se resuelve en tiempo polinomial.

Dado un conjunto de agentes S y un conjunto de tareas T, es posible modelar el problema mediante un grafico de dos partidos políticos G = ((S, T), E), con función de peso vs en los bordes. Por tanto, el problema de asignación consiste en encontrar un acoplamiento perfecto F⊂E minimizando la suma ∑e∈F c (e) los pesos de los bordes de F.

Subproblema: transporte

Como los dos problemas anteriores, el problema del transporte es una maximización. El problema del 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 se almacenan inicialmente en varios orígenes, a diferentes destinos de manera que el transporte total sea mínimo.

Deja unI la cantidad del producto disponible en origen i; Bj o la cantidad de producto requerida para el destino j; vsij el costo de transportar una unidad de un bien 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:

planificación programación transporte asignación

 

Si la suma de las fuentes es igual a la suma de las demandas, se dice que el problema está equilibrado, en este caso las restricciones se convierten en igualdades. De lo contrario, creamos un punto de demanda virtual (ficticio) correspondiente al exceso de oferta y con un costo de transporte cero.

planificación programación transporte asignación

El problema de transporte a menudo se representa como un gráfico bipartito con un problema de flujo (acoplamiento). Mostraremos aquí otras variantes para solucionar este problema.

Compartir, repartir