Teoría sobre el modelado de problemas

Para poder solucionar un problema mediante un algoritmo primero se debe extraer toda la información que nos aporta el enunciado y preparar el problema para dicho algoritmo.

Los pasos para modelar un problema son los siguientes:

• Paso 1: Se determinan las variables de decisión y se expresan algebraicamente.
  
  
• X1,..., Xn


• Paso 2: Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de las variables de decisión:
  
  
  • A11·X1 + A12·X2 + ... + A1n·Xn ≥, ≤, ó = b1
  • A21·X1 + A22·X2 + ... + A 2n·Xn ≥, ≤, ó = b2
  • ...
  • Am1·X1 + Am2·X2 + ... + Amn·Xn ≥, ≤, ó = bm
  
  
• Paso 3: Se expresan todas las condiciones implícitamente establecidas por la naturaleza de las variables: que no puedan ser negativas, que sean enteras, que solo puedan tomar determinados valores, ...
  
  
• X1,..., Xn ≥ 0
• X1,..., Xn son números enteros, o son booleanos,...


• Paso 4: Se determina la función objetivo.
  
  
  • Maximizar o minimizar Z = C1·X1 + C2·X2 + ... + Cn·Xn

A modo de ejemplo vamos a ver como se modelan algunos problemas típicos:

• Problema de la dieta
  
  
• Problema de transporte de tropas
  
  
• Problema de transporte de mercancías
  
  
• Problema de los árboles frutales
  
  
• Problema de asignación de personal
  
  
• Problema del camino mínimo
  
  
• Problema de localización
  
  
• Problema de inversión en bolsa