ALGEBRA DEL SIMPLEX

ALGEBRA DEL SIMPLEX

Desarrollado por George Dantzig en

1947, se ha comprobado su
extraordinaria eficiencia, y se usa en
forma rutinaria para resolver
problemas grandes en las
computadoras de hoy en día.

3
ALGEBRA DEL SIMPLEX
El método simplex es un procedimiento algebraico. Sin embargo, sus
conceptos fundamentales son geométricos. La comprensión de estos
conceptos geométricos proporciona una fuerte intuición sobre la forma en
que opera el método simplex y las razones de su elevada eficiencia.

Excepto en el caso de problemas muy pequeños, se ejecuta siempre en una

computadora y existe una amplia variedad de paquetes complejos de
software para ello. También se usan extensiones y variaciones del método
simplex para realizar análisis posóptimo (que incluye el análisis de
sensibilidad) del modelo.

4
ALGEBRA DEL SIMPLEX

5
FORMA ESTÁNDAR
✓Conceptos geométricos fundamentales del método simplex.
✓Computadora sólo puede seguir instrucciones algebraicas.

El procedimiento algebraico se basa en la solución de sistemas de

ecuaciones. Por lo tanto, el primer paso para preparar el método
simplex es convertir las restricciones funcionales de desigualdad en
restricciones de igualdad equivalentes: Forma estándar.

6
FORMA ESTÁNDAR
Minimization problem Maximization problem
𝑛 𝑛

min ෍ 𝑐𝑗 𝑥𝑗 max ෍ 𝑐𝑗 𝑥𝑗
𝑗=1 𝑗=1
𝑆. 𝐴: 𝑆. 𝐴:
Canonical form 𝑛 𝑛

෍ 𝑎𝑖𝑗 𝑥𝑗 ≥ 𝑏𝑖 ∀ 𝑖 = 1, … , 𝑚 ෍ 𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 ∀ 𝑖 = 1, … , 𝑚
𝑗=1 𝑗=1
𝑥𝑗 ≥ 0 ∀ 𝑗 = 1, … , 𝑛 𝑥𝑗 ≥ 0 ∀ 𝑗 = 1, … , 𝑛
𝑛 𝑛

min ෍ 𝑐𝑗 𝑥𝑗 max ෍ 𝑐𝑗 𝑥𝑗
𝑗=1 𝑗=1
𝑆. 𝐴: 𝑆. 𝐴:
Standard form 𝑛 𝑛

෍ 𝑎𝑖𝑗 𝑥𝑗 = 𝑏𝑖 ∀ 𝑖 = 1, … , 𝑚 ෍ 𝑎𝑖𝑗 𝑥𝑗 = 𝑏𝑖 ∀ 𝑖 = 1, … , 𝑚
𝑗=1 𝑗=1
𝑥𝑗 ≥ 0 ∀ 𝑗 = 1, … , 𝑛 𝑥𝑗 ≥ 0 ∀ 𝑗 = 1, … , 𝑛

7
FORMA ESTÁNDAR
En un modelo de PL económico, el lado derecho representa la disponibilidad de un
recurso, y el izquierdo el uso del recurso por todas las actividades del modelo
(variables). La cantidad excedente del lado derecho respecto de izquierdo da
entonces la cantidad no utilizada del recurso.
Para convertir una desigualdad (≤) en ecuación se agrega una variable de holgura al
lado izquierdo de la restricción.

6𝑥1 + 4𝑥2 ≤ 24

6𝑥1 + 4𝑥2 + 𝑠1 = 24

8
 FORMA ESTÁNDAR
Una restricción (≥) establece un límite inferior en las actividades económicas de
la programación lineal, así que la cantidad en la cual el lado izquierdo excede el
límite mínimo representa un exceso. Así pues, la conversión de (≥) a (=) se logra
restando una variable de excedente no negativa del lado izquierdo de la
desigualdad.

𝑥1 + 𝑥2 ≥ 900

𝑥1 + 𝑥2 = 900 + 𝑠1
𝑥1 + 𝑥2 − 𝑠1 = 900

9
FORMA ESTÁNDAR
El único requerimiento que falta es que el lado derecho de la ecuación
resultante sea no negativo.

✓ Si el lado derecho resulta negativo, el requerimiento se satisface

multiplicando ambos lados de la ecuación por -1.

10
FORMA ESTÁNDAR
Ejemplo 1:
Forma canónica

max 𝑍 = 3𝑥1 + 5𝑥2

S.A.
𝑥1 ≤ 4
2𝑥2 ≤ 12
3𝑥1 + 2𝑥2 ≤ 18
𝑥1 , 𝑥2 ≥ 0
11
FORMA ESTÁNDAR
Ejemplo 1:
Forma estándar o aumentada
Forma canónica
max 𝑍 = 3𝑥1 + 5𝑥2
max 𝑍 = 3𝑥1 + 5𝑥2
S.A.
S.A. 𝑥1 + 𝑠1 = 4
𝑥1 ≤ 4 2𝑥2 + 𝑠2 = 12
2𝑥2 ≤ 12 3𝑥1 + 2𝑥2 + 𝑠3 = 18
3𝑥1 + 2𝑥2 ≤ 18 𝑥1 , 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
𝑥1 , 𝑥2 ≥ 0

12
FORMA ESTÁNDAR
Ejemplo 2:
Forma canónica

max 𝑍 = 0,5𝑥1 − 5𝑥2 + 𝑥3

S.A.
𝑥1 + 𝑥2 + 𝑥3 ≤ 5
𝑥1 ≥ 𝑥2 − 1
𝑥1 , 𝑥2 , 𝑥3 ≥ 0

13
FORMA ESTÁNDAR
Ejemplo 2: Forma estándar
Forma canónica
max 𝑍 = 0,5𝑥1 − 5𝑥2 + 𝑥3
max 𝑍 = 0,5𝑥1 − 5𝑥2 + 𝑥3
S.A.
S.A. 𝑥1 + 𝑥2 + 𝑥3 + 𝑠1 = 5
−𝑥1 + 𝑥2 + 𝑠2 = 1
𝑥1 + 𝑥2 + 𝑥3 ≤ 5
𝑥1 , 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 ≥ 0
𝑥1 ≥ 𝑥2 − 1
𝑥1 , 𝑥2 , 𝑥3 ≥ 0

14
FORMA ESTÁNDAR
Ejemplo 3:
Forma canónica

min 𝑍 = 𝑥1 + 5𝑥2

S.A.
𝑥1 + 𝑥2 ≥ 5
0,5𝑥1 + 1,5𝑥2 = 2.5
𝑥1 , 𝑥2 , 𝑥3 ≥ 0

15
FORMA ESTÁNDAR
Ejemplo 3:
Forma canónica Forma estándar

min 𝑍 = 𝑥1 + 5𝑥2 min 𝑍 = 𝑥1 + 5𝑥2

S.A. S.A.
𝑥1 + 𝑥2 ≥ 5 𝑥1 + 𝑥2 − 𝑠1 = 5
0,5𝑥1 + 1,5𝑥2 = 2.5 0,5𝑥1 + 1,5𝑥2 = 2.5
𝑥1 , 𝑥2 , 𝑥3 ≥ 0 𝑥1 , 𝑥2 , 𝑥3 𝑠1 ≥ 0

16
SOLUCIONES BÁSICAS

17
SOLUCIONES BÁSICAS

Una solución básica es una solución en

un vértice aumentada.

Una solución básica factible (BF) es una

solución factible en un vértice
aumentada.

18
SOLUCIONES BÁSICAS
max 𝑍 = 3𝑥1 + 5𝑥2 max 𝑍 = 3𝑥1 + 5𝑥2
S.A. S.A.
𝑥1 ≤ 4 𝑥1 + 𝑠1 = 4
2𝑥2 ≤ 12 2𝑥2 + 𝑠2 = 12
3𝑥1 + 2𝑥2 ≤ 18 3𝑥1 + 2𝑥2 + 𝑠3 = 18
𝑥1 , 𝑥2 ≥ 0 𝑥1 , 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0

El punto:
𝑥1 = 4 y 𝑥2 = 6
𝑠1 , 𝑠2 , 𝑠3 =¿ ?

19
SOLUCIONES BÁSICAS
max 𝑍 = 3𝑥1 + 5𝑥2 max 𝑍 = 3𝑥1 + 5𝑥2
S.A. S.A.
𝑥1 ≤ 4 𝑥1 + 𝑠1 = 4
2𝑥2 ≤ 12 2𝑥2 + 𝑠2 = 12
3𝑥1 + 2𝑥2 ≤ 18 3𝑥1 + 2𝑥2 + 𝑠3 = 18
𝑥1 , 𝑥2 ≥ 0 𝑥1 , 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0
El punto:
𝑥1 = 4 y 𝑥2 = 3
𝑠1 , 𝑠2 , 𝑠3 =¿ ?

20
SOLUCIONES BÁSICAS
max 𝑍 = 3𝑥1 + 5𝑥2 max 𝑍 = 3𝑥1 + 5𝑥2
S.A. S.A.
𝑥1 ≤ 4 𝑥1 + 𝑠1 = 4
2𝑥2 ≤ 12 2𝑥2 + 𝑠2 = 12
3𝑥1 + 2𝑥2 ≤ 18 3𝑥1 + 2𝑥2 + 𝑠3 = 18
𝑥1 , 𝑥2 ≥ 0 𝑥1 , 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0

El punto:
𝑥1 = 6 y 𝑥2 = 0
𝑠1 , 𝑠2 , 𝑠3 =¿ ?

21
SOLUCIONES BÁSICAS
En el espacio de soluciones algebraicas, las soluciones básicas
corresponden a los puntos de esquina en el espacio de soluciones
gráficas. Esto significa que la cantidad máxima de puntos de esquina es

𝑛
𝑛!
𝐶𝑚 =
𝑚! 𝑛 − 𝑚 !

Como con los puntos de esquina, las soluciones factibles básicas

definen por completo a las candidatas para la solución óptima en el
espacio de soluciones algebraicas.

22
SOLUCIONES BÁSICAS
Una solución básica tiene las siguientes propiedades:
[Link] variable se designa ya sea como variable básica o como variable no básica.
[Link] número de variables básicas es igual al número de restricciones (ahora ecuaciones). El
número de variables no básicas es igual al número total de variables menos el número de
restricciones (n° variables básicas = n – m)
[Link] variables no básicas se igualan a cero.
[Link] valores de las variables básicas se obtienen como la solución simultánea del sistema
de ecuaciones.
[Link] las variables básicas satisfacen las restricciones de no negatividad, la solución básica es
una solución básica factible.

23
SOLUCIONES BÁSICAS
Ejemplo 4:
max 𝑍 = 2𝑥1 + 3𝑥2
S.A.
2𝑥1 + 𝑥2 ≤ 4
𝑥1 + 2𝑥2 ≤ 5
𝑥1 , 𝑥2 ≥ 0

25
SOLUCIONES BÁSICAS
max 𝑍 = 2𝑥1 + 3𝑥2
S.A.
2𝑥1 + 𝑥2 ≤ 4
𝑥1 + 2𝑥2 ≤ 5
𝑥1 , 𝑥2 ≥ 0

26
SOLUCIONES BÁSICAS
max 𝑍 = 2𝑥1 + 3𝑥2
S.A.
2𝑥1 + 𝑥2 ≤ 4
𝑥1 + 2𝑥2 ≤ 5
𝑥1 , 𝑥2 ≥ 0

Forma estándar:
max 𝑍 = 2𝑥1 + 3𝑥2
S.A.
2𝑥1 + 𝑥2 + 𝑠1 = 4
𝑥1 + 2𝑥2 + 𝑠2 = 5
𝑥1 , 𝑥2 , 𝑠1 , 𝑠2 ≥ 0

27
SOLUCIONES BÁSICAS
[Link] variables no básicas se igualan a cero.
[Link] valores de las variables básicas se obtienen como la solución
simultánea del sistema de ecuaciones.

• Variables no básicas = n – m = 4 – 2 = 2
• Igualar 2 variables a 0 y resolver el sistema de ecuaciones.

28
SOLUCIONES BÁSICAS

30
 SOLUCIONES BÁSICAS
Ejemplo 5:
Determine la solución optima del siguiente problema de PL enumerando todas
las soluciones básicas.

max 𝑍 = 2𝑥1 + 3𝑥2 + 5𝑥3

S.A.
−6𝑥1 + 7𝑥2 − 9𝑥3 ≥ 4
𝑥1 + 𝑥2 + 4𝑥3 ≤ 10
𝑥1 , 𝑥2 , 𝑥3 ≥ 0

31
 SOLUCIONES BÁSICAS
Ejemplo 5:
Determine la solución optima del siguiente problema de PL enumerando todas
las soluciones básicas.

max 𝑍 = 2𝑥1 + 3𝑥2 + 5𝑥3

S.A.
−6𝑥1 + 7𝑥2 − 9𝑥3 − 𝑠1 = 4
𝑥1 + 𝑥2 + 4𝑥3 + 𝑠2 = 10
𝑥1 , 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 ≥ 0

32
 SOLUCIONES BÁSICAS
N° de soluciones básicas:
𝑛
𝑛! 5!
𝐶𝑚 = = = 10
𝑚! 𝑛 − 𝑚 ! 2! 5 − 2 !

N° de variables básicas:
𝑚=2

N° de variables no básicas:
𝑛−𝑚 =5−2=3

33
SOLUCIONES
Variable no
BÁSICAS
Variable Solución Valor
N° ¿Factible?
básica básica x1 x2 X3 S1 S2 objetivo
1 x1,x2,x3 s1,s2 0 0 0 -4 10 No 0,00
2 x1,x2,s1 x3,s2 0 0 -0,4 0 11,8 No -2,22
3 x1,x2,s2 x3,s1 0 0 2,5 -27 0 No 12,50
4 x1,x3,s1 x2,s2 0 0,57 0 0 9,43 Si 1,71
5 x1,x3,s2 x2,s1 0 10 0 66 0 Si 30,00
6 x1,s1,s2 x2,x3 0 2,86 1,78 0 0 Si 17,51
7 x2,x3,s1 x1,s2 -0,7 0 0 0 10,7 No -1,33
8 x2,x3,s2 x1,s1 10 0 0 -64 0 No 20,00
9 x2,s1,s2 x1,x3 -7,1 0 4,27 0 0 No 7,20
10 x3,s1,s2 x1,x2 5,08 4,92 0 0 0 Si 24,92

34
SOLUCIONES BÁSICAS
Variable no Variable Solución Valor
N° ¿Factible?
básica básica x1 x2 X3 S1 S2 objetivo
1 x1,x2,x3 s1,s2 0 0 0 -4 10 No 0,00
2 x1,x2,s1 x3,s2 0 0 -0,4 0 11,8 No -2,22
3 x1,x2,s2 x3,s1 0 0 2,5 -27 0 No 12,50
4 x1,x3,s1 x2,s2 0 0,57 0 0 9,43 Si 1,71
5 x1,x3,s2 x2,s1 0 10 0 66 0 Si 30,00
6 x1,s1,s2 x2,x3 0 2,86 1,78 0 0 Si 17,51
7 x2,x3,s1 x1,s2 -0,7 0 0 0 10,7 No -1,33
8 x2,x3,s2 x1,s1 10 0 0 -64 0 No 20,00
9 x2,s1,s2 x1,x3 -7,1 0 4,27 0 0 No 7,20
10 x3,s1,s2 x1,x2 5,08 4,92 0 0 0 Si 24,92

35
 SOLUCIONES BÁSICAS
Ejemplo 6:
Considere el siguiente problema de PL

max 𝑍 = 𝑥1 + 3𝑥2

S.A.
𝑥1 + 𝑥2 = 2
−𝑥1 + 𝑥2 ≤ 4
𝑥1 ≥ 0
𝑥2 𝑙𝑖𝑏𝑟𝑒

36
 SOLUCIONES
Ejemplo 6:
BÁSICAS
Considere el siguiente problema de PL

max 𝑍 = 𝑥1 + 3 𝑥2+ − 𝑥2−

S.A.
𝑥1 + 𝑥2+ − 𝑥2− = 2
−𝑥1 + 𝑥2+ − 𝑥2− + 𝑠1 = 4
𝑥1 ≥ 0
𝑥2+ , 𝑥2− ≥ 0

37
 SOLUCIONES BÁSICAS
N° de soluciones básicas:
𝑛
𝑛! 4!
𝐶𝑚 = = =6
𝑚! 𝑛 − 𝑚 ! 2! 4 − 2 !

N° de variables básicas:
𝑚=2

N° de variables no básicas:
𝑛−𝑚 =4−2=2

38
SOLUCIONES BÁSICAS
Variable no Variable Solución Valor
N° ¿Factible?
básica básica X1 X2+ X3- S1 objetivo
1 x1,x2+ x2-,s1 0 0 -2 2 No 6,00
2 x1,x2- x2+,s1 0 2 0 2 Si 6,00
3 x1,s1 x2+,x2- - - - - No -
4 x2+,x2- x1,s1 2 0 0 6 Si 2,00
5 x2+,s1 x1,x2- -1 0 -3 0 No 8,00
6 x2-,s1 x1,x2+ -1 3 0 0 No 8,00

39
SOLUCIONES BÁSICAS
Variable no Variable Solución Valor
N° ¿Factible?
básica básica X1 X2+ X3- S1 objetivo
1 x1,x2+ x2-,s1 0 0 -2 2 No 6,00
2 x1,x2- x2+,s1 0 2 0 2 Si 6,00
3 x1,s1 x2+,x2- - - - - No -
4 x2+,x2- x1,s1 2 0 0 6 Si 2,00
5 x2+,s1 x1,x2- -1 0 -3 0 No 8,00
6 x2-,s1 x1,x2+ -1 3 0 0 No 8,00

40
 SOLUCIONES BÁSICAS
Ejemplo 7:

min 𝑍 = 𝑥1 + 2𝑥2

S.A.
𝑥1 + 𝑥2 = 10
0,5𝑥1 − 0,5𝑥2 ≤ 1
𝑥1 , 𝑥2 ≥ 0

41
SOLUCIONES BÁSICAS
N° de soluciones básicas:
𝑛
𝑛! 3!
𝐶𝑚 = = =3
𝑚! 𝑛 − 𝑚 ! 2! 3 − 2 !

N° de variables básicas:
𝑚=2

N° de variables no básicas:
𝑛−𝑚 =3−2=1

42
SOLUCIONES BÁSICAS
Variable no Variable Solución Valor
N° ¿Factible?
básica básica x1 x2 s1 objetivo
1 x1 x2,s1 0 10 6 Si 20,00
2 x2 x1,s1 10 0 -4 No -
3 s1 x1,x2 6 4 0 Si 14,00

43
SOLUCIONES BÁSICAS
Ejemplo 7a:

min 𝑍 = 𝑥1 + 2𝑥2

S.A.
𝑥1 − 𝑥2 = 10
0,5𝑥1 − 0,5𝑥2 ≤ 1
𝑥1 , 𝑥2 ≥ 0

44
SOLUCIONES BÁSICAS
Variable no Variable Solución Valor
N° ¿Factible?
básica básica x1 x2 S1 objetivo
1 x1 x2,s1 0 -10 -4 No -
2 x2 x1,s1 10 0 -4 No -
3 s1 x1,x2 - - - - -

45
 SOLUCIONES
Ejemplo 7b:
BÁSICAS
min 𝑍 = 2𝑥1 + 2𝑥2

S.A.
𝑥1 + 𝑥2 = 10
0,5𝑥1 − 0,5𝑥2 ≤ 1
𝑥1 , 𝑥2 ≥ 0

46
SOLUCIONES BÁSICAS
Variable no Variable Solución Valor
N° ¿Factible?
básica básica x1 x2 s1 objetivo
1 x1 x2,s1 0 10 6 Si 20,00
2 x2 x1,s1 10 0 -4 No -
3 s1 x1,x2 6 4 0 Si 20,00

47
SOLUCIONES BÁSICAS
A medida que el tamaño del problema se incrementa, enumerar todos los
puntos de esquina se vuelve una tarea prohibitiva. Por ejemplo, para m = 10
20
y n = 20, es necesario resolver 𝐶10 = 184754 conjuntos de 10x10
ecuaciones, una tarea abrumadora.

El método simplex atenúa esta carga computacional en forma dramática al

investigar sólo un subconjunto de todas las posibles soluciones factibles
básicas (puntos de esquina).

48
Gracias