Forma Estándar De Un Modelo De Programación Lineal

Consideremos un modelo de Programación Lineal en su forma estándar, que denotaremos en lo que sigue por:
Min c1x1 + c2x2 + ... + cnxn
sa a11x1 + a12x2 + ... + a1nxn = b1
a21x1 + a22x2 + ... + a2nxn = b2
... ... ...
am1x1 + am2x2 + ... + amnxn = bm
xi >= 0, i = 1, 2, ..., n y m <= n Matricialmente escrito como: Min cTx s.a Ax = b x >= 0
No existe pérdida de generalidad en asumir que un modelo de PL viene dado en su forma estándar:
EJEMPLO
P) Max 9u + 2v + 5z
sa 4u + 3v + 6z <= 50 u + 2v - 3z >= 8
2u - 4v + z = 5
u,v >= 0
z e IR
Siempre es posible llevar un problema de maximización a uno de minimización. Si f(x) es la función objetivo a maximizar y x* es la solución óptima f(x*) >= f(x), para todo x factible. -f(x*) <= - f(x), para todo x factible. En consecuencia: x* es también mínimo de -f(x) Cada restricción del tipo <= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de holgura no negativa, con coeficiente nulo en la función objetivo. Cada restricción del tipo >= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de exceso no negativa, con coeficiente nulo en la función objetivo.
Siempre es posible escribir una variable libre de signo como la diferencia de dos variables no negativas.
Considerando la siguiente notación: u = x1, v = x2, z = x3 - x4, s1 = x5 (holgura), s2 = x6 (exceso), el problema P) puede ser escrito en forma equivalente como:
Min - 9x1 - 2x2 - 5x3 + 5x4 + 0x5 + 0x6
sa: 4x1 + 3x2 + 6x3 - 6x4 + x5 = 50
x1 + 2x2 - 3x3 + 3x4 - x6 = 8
2x1 - 4x2 + x3 - x4 = 5
xi >= 0, i=1,2,3,4,5,6.