Forma canónica y forma estándar
Los programas lineales siguen ciertas reglas al escribirlos. A programa lineal que sigue las reglas se dice que está en forma canónica. el algoritmo de símplex solo se puede aplicar a programas lineales en la forma canónica.
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 restricciones mayores o iguales, todas cuyas 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:
- máx z = – mín -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:
Se escribe de la siguiente forma:
Forma estándar
Para cada restricción de desigualdad de la forma canónica, agregamos un variable de holgura positivo y tal que:
Ax ≤ b ⇔ Ax + e = b, e ≥ 0, aquí e es un vector de tamaño m de variables de brecha.
Así, la forma canónica se lleva a la forma estándar mediante la adición de las variables de brecha en el vector de variables:
- 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 base positivas. Para ello hay que sumar otras variables denominadas excesos y variables artificiales.
Aquí están las reglas a seguir para transformar mejor el simplex en forma estándar:
- Restricciones “mayor o igual” o “menor o igual con b negativo”: haga que b sea positivo y agregue “– variable de holgura + variables artificiales »
- Restricciones de "igualdad": agregue "+ variable artificial"
- Restricciones “menor o igual con b positivo”: agregue “+ variable de diferencia” como se vio anteriormente.
