MÉTODO SIMPLEX

METODO SIMPLEX
La programación lineal se puede resolver a través del algoritmo simplex; su importancia radica
en que proporciona soluciones etapa por etapa, donde la solución básica factible está en
consideración, y cada etapa nos da una mejor solución óptima.
El álgebra matricial y el proceso de eliminación completa de Gauss-Jordan para resolver un
sistema de ecuaciones simultáneas linealesson las raíces del método simplex de la PL.
Para utilizar el método simplex, es necesario cambiar todas las desigualdades en igualdades.
Para hacer esta transformación a igualdad, donde automáticamente aumentamos una matriz
identidad a nuestro modelo, como requisitos para obtener la matriz A/I/B (A es la matriz de
coeficientes tecnológicos, I es la matriz identidad y B es el vector dedisponibilidad o vector
columna de términos independientes) tenemos que utilizar variables de exceso y variables
artificiales.
Se dice de holgura pues toman la diferencia entre la parte derecha de la ecuación o los
sobrantes de los recursos disponibles. Se utiliza variables de holgura (exceso) para convertir
las desigualdades en igualdades y se utiliza variables artificiales cuando la variable de laholgura no proporciona coeficientes positivos en la matriz identidad. Es decir, las variables que
están en la base; los coeficientes de la fila de la función objetivo correspondiente de la matriz
identidad, deben ser positivos, así como la variable artificial tiene una función matemática, se
tiene que asegurar que nunca aparezca en la solución final. Esta condición se puede cumplir
dando uncoeficiente de costo artificial a la función objetivo.
1. Forma canónica de un PPL
Un PPL diremos que está escrito en la forma canónica de la siguiente manera:
Maximizar (Minimizar)

Z  c1 x1  c2 x2  c3 x3  ........  cn xn

Sujeto a (s.a.):

a11 x1  a12 x 2  ........  a1n x n  b1
a 21 x1  a 22 x 2  ........  a 2 n x n  b2
a11 x1  a12 x 2  ........  a1n x n  b3
.......

...

...

....

...

...

....

...

a m1 x1  a m 2 x 2  ........  a mn x n  bm
x1, x 2, x3,

, xn  0

2. Forma Estándar de un PPL
Un PPL diremos que está escrito en la forma estándar, si está escrito de la siguiente manera:

Maximizar (Minimizar)
Sujeto a (s.a.):

Z  c1 x1  c2 x2  c3 x3  ........  cn xn

a11 x1  a12 x 2  ........  a1n x n  b1
a 21x1  a 22 x 2  ........  a 2 n x n  b2
a11 x1  a12 x 2  ........  a1n x n  b3
...

....

...

...

....

...

...

....

...

a m1 x1  a m 2 x 2  ........  a mn x n  bm
, xn  0

x1, x 2, x3,

3. Reglas para convertir un PPL a la forma estándar
El primer paso para resolver un PPL mediante el método simplex es escribir el PPL en la forma
estándar; como nosiempre el programa original está en esta forma, se hace necesario un
conjunto de reglas; para convertirlo.
Conversión de una desigualdad en igualdad y solución de un PPL
Veremos dos casos:
a. El problema tiene todas sus restricciones de tipo “  ”:
Convertir toda desigualdad, de la forma:

a11x1  a12x2  ........  a1n xn  b1 …(1)
Se puede convertir en igualdad, mediante la adición de unanueva variable no negativa

Si ; llamada variable Slack u Holgura; de esta manera (1) se convierte en:
a11x1  a12 x2  ........  a1n xn  S1  b1 … (2)
Ejemplo:

2 x1  5x2  2

Equivale

a

2 x1  5x2  S3  2

b. El problema tiene restricciones: “  ”
Convertir toda desigualdad, de la forma:

a11x1  a12 x2  ........  a1n xn  b1 … (3)
Se puede convertir en igualdad,mediante la sustracción de una nueva variable S i no
negativa llamada variable de Exceso o Surplus y la adición de una variable Ri no
negativa llamada variable Artificial; de esta manera (3) se convierte en:

a11x1  a12 x2  ........  a1n xn  S1  R1  b1 … (4)
Ejemplos:

2 x1  5x2  4 x3  2

es equivalente a

2x1  5x2  4x3  S4  R5  2

3x1  5x2  7 x3  4

es equivalente a...