PHPSimplex

Modeling problems theory

To be able to solve a problem intervening an algorithm, first must extract all the information that contributes itself, and arranging the problem for the aforementioned algorithm.

The steps to model a problem are the following:

• Step 1: Determining decision variables and expressing them algebraically.
  
  
  • X1,..., Xn
  
  
• Step 2: Determining the restrictions and expressing them as equations or inequalities in function of the decision variables:
  
  
  • A11·X1 + A12·X2 + ... + A1n·Xn ≥, ≤, ó = b1
  • A21·X1 + A22·X2 + ... + A 2n·Xn ≥, ≤, ó = b2
  • ...
  • Am1·X1 + Am2·X2 + ... + Amn·Xn ≥, ≤, ó = bm
  
  
• Step 3: Expressing all implicit conditions established by the origin of variables: negativeness, integer, only a few allowed values, ...
  
  
  • X1,..., Xn ≥ 0
  • X1,..., Xn are integers, or boolean,...
  
  
• Step 4: Determining Objective Function.
  
  
  • Maximize or minimize Z = C1·X1 + C2·X2 + ... + Cn·Xn

 

As example, let see how to model some typical problems:

• Diet problem
  
  
• Transporting troops' problem
  
  
• Transporting goods' problem
  
  
• Fruit trees' problem
  
  
• Allocative personnel's problem
  
  
• Minimal road's problem
  
  
• Location problem
  
  
• Stock Exchange Investment's problem