LP: forma canónica y forma estándar

Forma canónica y forma estándar

Les programmes linéaires suivent certaines règles lors de son écriture. Un programme linéaire qui suit les règles est dit de forme canonique. L’algorithme du simplexe ne peut que s’appliquer sur des programmes linéaires sous la forme canonique.

Forma canónica

Un programa lineal en su forma canónica es:

  • Un problema de maximización, bajo restricciones inferiores o iguales, cuyas variables son estrictamente positivas.
  • Un problema de Minimización, bajo mayores o iguales restricciones, en el que todas las variables son estrictamente positivas.

Si el programa lineal no se corresponde con estos criterios, es necesario transformar las restricciones o la función objetivo de acuerdo con las siguientes operaciones:

  • max z = - min -z
  • x + y ≥ b es equivalente a - x - y ≤ - b
  • x + y = b es equivalente ax + y ≥ b, x + y ≤ b

La forma canónica a menudo se representa en forma de matriz:

  • el vector de los coeficientes de la función objetivo: c de tamaño n
  • la matriz de los coeficientes de la parte izquierda de las restricciones: A de tamaño m * n
  • el vector de las constantes de la parte derecha de las restricciones: b de tamaño m
  • el vector de variables: x de tamaño n

De ahí el siguiente programa lineal:

Forma canónica

Escrito en la siguiente forma:

Forma canónica

Forma estándar

Para cada restricción de desigualdad de la forma canónica, agregamos una variable de desviación positiva e tal que:

Ax ≤ b ⇔ Ax + e = b, e ≥ 0, aquí e es un vector de tamaño m de variables de desviación.

Por lo tanto, la forma canónica se lleva a la forma estándar mediante la adición de las variables de variación en el vector de variables:

forma estándar
  • el vector de los coeficientes de la función objetivo: c de tamaño n + m (n para xym para e aunque estos últimos no entran en el cálculo)
  • la matriz de los coeficientes de la parte izquierda de las restricciones: Ã de tamaño m * (n + m), siendo la parte derecha de la matriz una matriz de identidad de tamaño m.
  • el vector de las constantes de la parte derecha de las restricciones: b de tamaño m
  • el vector de variables de tamaño n + m

Algunas desigualdades no permiten tener variables de base positivas. Para ello debemos sumar otras variables llamadas variables de exceso y artificiales.

Aquí están las reglas a seguir para transformar mejor el simplex en forma estándar:

  • restricciones "mayor o igual que" o "menor o igual con b negativo": hacer b positivo y agregar "- variable de desviación + variable artificial"
  • Restricciones de "igualdad": agregue "+ variable artificial"
  • restricciones "menor o igual que con b positivo": agregue "+ variable de variación" como se vio anteriormente.
Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: