PHPSimplex

Teoria sobre modelagem de problemas

Com o fim de resolver um problema usando um algoritmo, primeiramente deve-se extrair toda a informação dada pelo enunciado e logo, preparar o problema de acordo com as necessidades do método de resolução.

Os passos para modelar um problema são os seguintes:

• Passo 1: Determinar as variáveis de decisão e expressá-las algebricamente.
  
  
  • X1,..., Xn
  
  
• Passo 2: Determinar as restrições e expressá-las como equações ou inequações dependentes das variáveis de decisão:
  
  
  • A11·X1 + A12·X2 + ... + A1n·Xn ≥, ≤, ó = b1
  • A21·X1 + A22·X2 + ... + A 2n·Xn ≥, ≤, ó = b2
  • ...
  • Am1·X1 + Am2·X2 + ... + Amn·Xn ≥, ≤, ó = bm
  
  
• Passo 3: Expressar todas as condições estabelecidas implicitamente pela natureza das variáveis: que não possam ser negativas, que sejam inteiras, que somente possam ter determinados valores, ...
  
  
  • X1,..., Xn ≥ 0
  • X1,..., Xn são números inteiros, ou são booleanos, ...
  
  
• Passo 4: Determinar a função objetivo.
  
  
  • Maximizar ou minimizar Z = C1·X1 + C2·X2 + ... + Cn·Xn

 

A título de exemplo, explicaremos como modelar alguns dos problemas típicos:

• Problema da dieta
  
  
• Problema do transporte de tropas
  
  
• Problema do transporte de mercadorias
  
  
• Problema das árvores frutíferas
  
  
• Problema de designação de pessoal
  
  
• Problema do caminho mínimo
  
  
• Problema de localização
  
  
• Problema de investimento na bolsa de valores