Diferença entre forma padrão e forma canônica

Há alguma variação na literatura em relação à terminologia, mas mais comumente:

  • A forma geral é \ min \ {c ^ Tx: b_ \ ell \ leq Ax \ leq b_u, \, \ ell \ leq x \ leq u \}.
  • A forma canônica ou simétrica é \ max \ {c ^ Tx: Ax \ leq b, \, x \ geq 0 \} com duplo \ min \ {b ^ Ty: A ^ Ty \ geq c, \, y \ geq 0 \ }
  • O formato padrão é \ min \ {c ^ Tx: Ax = b, \, x \ geq 0 \}.

É possível transformar cada um deles em qualquer um dos outros por:

  • incluindo variáveis ​​de folga ou superávit para converter desigualdades em igualdades (e colocar limites em folgas para converter restrições de intervalo);
  • converter igualdade em pares de desigualdades;
  • conversão de limites em restrições explícitas;
  • negando o objetivo de converter um problema mínimo para um máximo ou vice-versa;
  • substituir variáveis ​​para converter um limite superior em um limite inferior ou mudar um limite inferior para zero;
  • dividindo variáveis ​​irrestritas na diferença de duas variáveis ​​não-negativas.