Universidad de Cádiz

Estadı́stica y Optimización
Grado en Arquitectura Naval e Ingenierı́a Marı́tima

Optimización Lineal.
Métodos Simplex.

Profesora:
Marı́a José Benı́tez Caballero

Curso 2019-2020
Optimización Lineal.
Métodos Simplex. Marı́a José Benı́tez Caballero

Índice
1. Teorı́a 2

2. Ejemplos 4

1
 Optimización Lineal.
Métodos Simplex. Marı́a José Benı́tez Caballero

1. Teorı́a
A continuación, vamos a trabajar con el algoritmo denominado Método Simplex. Este
algoritmo fue desarrollado por George Dantzig en 1947 y se considera el inicio de la
Programación Lineal tal y como la conocemos ahora. Actualmente, este método es
el más utilizado, además de ser uno de los más eficientes.
Este método se basa en el Teorema Fundamental de la Optimización Lineal, el cual
nos dice que si el problema tiene solución, ésta se encuentra en los vértices. Ası́ pues,
deberı́amos calcular todos los vértices posibles, sustituirlos en la función objetivo y
elegir entre todos ellos, el que se adecue a lo que el problema nos exija. Pero esta idea
debe ser complementada, ya que, por ejemplo, necesitamos poder calcular todos los
vértices, o si el recinto no es acotado, no podrı́amos dar una solución. El algoritmo
Simplex es una formalización de esta idea y a grandes rasgos se puede resumir como:

Algoritmo Simplex
Paso 1 Consideremos un vértice v de la región factible como vértice inicial.
Paso 2 Decidimos si es ese vértice v es la solución óptima.
Paso 3 Si v no es una solución óptima, escogeremos otro vértice a través de un meca-
nismo de selección y volveremos al Paso 2.
La idea novedosa que presentó este método es la parte de mecanismo de selección,
ya que nos asegura dar el menor número de pasos posibles hasta obtener el vértice
óptimo. Para poder aplicar el Método Simplex necesitamos que el problema esté en
forma estándar. Para ello, introduciremos las variables holgura. Si una restricción es
de la forma 6, entonces la variable holgura se introducirá sumando. Mientras que si
la restricción tiene signo >, la variable holgura entrará con signo negativo.
Ası́, el algoritmo se inicia con una solución factible básica x~b . Estas variables básicas
son aquellas que forman la matriz identidad dentro de la matriz de costos tecnológi-
cos. Normalmente, estas variables básicas están formadas por las variables holguras o
variables artificiales. Una vez que las variables básicas están localizadas, construimos

2
Optimización Lineal.
Métodos Simplex. Marı́a José Benı́tez Caballero

la siguiente tabla:

Variables básicas x1 x2 ... xn b

xb1 a11 a12 . . . a1n b1
.. .. .. .. .. ..
. . . . . .
xbm am1 am2 . . . amn bm
c1 c2 ... cn

Lo primero que debemos hacer es comprobar si la solución es factible y óptima. Para

ello debemos comprobar ciertas caracterı́sticas de la tabla. Para que la solución sea
factible, todos los valores de los términos independientes deben ser no negativos, es
decir, bi >, para todo i = 1, . . . , m. Para comprobar si es solución óptima, debemos
fijarnos en los costos y en el tipo de problema:
Si el problema es de máximo, los costos marginales deben ser todos negativos
o ceros.
Si necesitamos minimizar, los costos marginales deben ser todos positivos o
ceros.
Si esto no sucediese, entonces la solución no es óptima y debemos iniciar el proceso
para seleccionar otra posible solución. Para ello, debemos elegir una variable para
que entre en el vector de variables básicas y otra variable debe salir del vector.
Para elegir la variable que entra, consideraremos aquella variable cuyo costo marginal
sea el de mayor valor (en valor absoluto), distinta de cero y que hagan que la solución
no sea óptima. Consideremos que esta variable es la variable xj . Para saber que
variable será la que salga de la solución básica, consideraremos la fórmula:
 
b1 b2 bm
mı́n , ,...
aj1 aj2 ajm

siempre y cuando Aj
0. Por lo tanto, la variable que abandona el vector de
variables básicas será aquella cuyo valor sea el mı́nimo. Intercambiamos las variables,
y realizamos transformaciones elementales en la matriz de costos hasta obtener una
nueva tabla. Ahora, comprobamos si esta nueva solución es la óptima del mismo
modo que se ha descrito con anterioridad. Si ası́ fuese, se acabarı́a el método. Si no
es la solución óptima, repetimos los pasos para obtener una nueva solución.
En la siguiente sección se aplica el Método Simplex a varios ejemplos.

3
Optimización Lineal.
Métodos Simplex. Marı́a José Benı́tez Caballero

2. Ejemplos
Ejemplo 2.1. Resuélvase por el método Simplex adecuado el siguiente problema de
Optimización Lineal:

min Z(x1 , x2 , x3 ) = x1 + x2 − 4x3

sujeto a x1 + x2 + 2x3 6 9
x1 + x2 − x3 6 2
−x1 + x2 + x3 6 4
xi > 0, i = 1, 2, 3

Solución: Lo primero que observamos es que el problema está en forma canónica

pero no estándar. Ası́, debemos introducir variables holgura para poder expresarlo
de forma estándar. Nuestro problema nos quedarı́a como sigue

min Z(x1 , x2 , x3 , x4 , x5 , x6 ) = x1 + x2 − 4x3

sujeto a x1 + x2 + 2x3 + x4 = 9
x1 + x2 − x3 + x5 = 2
−x1 + x2 + x3 + x6 = 4
xi > 0, i = 1, 2, 3, 4, 5, 6
Ası́, los elementos del problema serı́an:
~ = (x1 , x2 , x3 , x4 , x5 , x6 )
Vector de variables X
Vector de costos ~c = (1, 1, −4, 0, 0, 0)
Matriz de coeficientes o de costos tecnológicos
 
1 1 2 1 0 0
 
A =  1 1 −1 0 1 0
 
 
−1 1 1 0 0 1

Vector de términos independientes ~b = (9, 2, 4)

Ası́ pues, las variables que forman la matriz identidad dentro de la matriz de costos
y que, por lo tanto, son solución al sistema de ecuaciones serán:
x~b = (x4 , x5 , x6 )

4
Optimización Lineal.
Métodos Simplex. Marı́a José Benı́tez Caballero

Ya tenemos nuestras variables básicas, construimos ahora la tabla

x1 x2 x3 x4 x5 x6 b
x4 1 1 2 1 0 0 9
x5 1 1 −1 0 1 0 2
x6 −1 1 1 0 0 1 4
1 1 −4 0 0 0

Comprobemos ahora, si la solución es óptima o no. La solución es factible ya que

todos los términos independientes son no negativos. Pero no es óptima, ya que al
estar minimizando el problema necesitamos que todos los costos sean no negativos,
es decir, que todos sean positivos o ceros. Sin embargo, el costo de la variable x3
es negativo. En este caso, como ese es el único costo negativo, es la única variable
que puede entrar en la solución. Ahora debemos elegir la variable que sale, para ello
realizamos la siguiente fórmula:
 
9 4
mı́n , = {4,5, 4} = 4
2 1

Este valor corresponde a la variable x6 . Construimos ahora la nueva tabla. Como

ahora x3 forma parte de la solución del problema, necesitamos que su columna en la
matriz de costos tecnológicos sea toda nula salvo en el lugar de x3 que debe haber
un 1. Ası́ que lo primero que debemos hacer es conseguir un 1 en esa posición:

x1 x2 x3 x4 x5 x6 b
x4
x5
x3 −1 1 1 0 0 1 4

Una vez que el elemento pivote (el elemento señalado en rojo) es un 1, pasamos a
utilizar transformaciones elementales para conseguir ceros en el resto de la columna.
Para ello realizaremos combinaciones lineales entre las filas antiguas y la fila nueva.
Por ejemplo, para conseguir un 0 en el elemento a13 , a la fila de la primera tabla de
la variable x4 , debemos restarle dos veces la fila de la nueva tabla correspondiente a
la variable x3 . Del mismo modo, para conseguir un 0 en el elemento a23 , a la segunda

5
Optimización Lineal.
Métodos Simplex. Marı́a José Benı́tez Caballero

fila de la primera tabla debemos sumarle la nueva fila de la variable x3 de la nueva

tabla. También debemos realizar las cálculos con la fila de costos, quedándonos la
tabla:
x1 x2 x3 x4 x5 x6 b
x4 3 −1 0 1 0 −2 1
x5 0 2 0 0 1 1 6
x3 −1 1 1 0 0 1 4
−3 5 0 0 0 4

Por lo tanto, obtenemos como solución básica las variables x~b = (x4 , x5 , x3 ). antes
de continuar, debemos comprobar si la solución es óptima, ya que factible lo sigue
siendo. Como hay costos negativos, debemos seguir con el método.
La única variable con costo negativo es la variable x1 , ası́ que ésta será la que entre en
el vector de variables básicas. Para saber de que variable tomará el lugar, calculamos
el mı́nimo de los términos independientes entre los coeficientes de la variable a entrar,
siempre y cuando esos coeficientes sean positivos. Como en este caso, el coeficiente
en la segunda fila es un cero no entrarı́a en los cálculos, ası́ como, la variable x3 , ya
que su coeficiente es negativo. Ası́, la única variable que puede salir de la tabla es
x4 . Como podemos observar en la tabla (señalado en rojo), el elemento pivote no
es un 1, ası́ que dividiremos toda esa fila por 3 para ası́ obtenerlo. Y realizamos las
cuentas para obtener ceros en el resto de la columna, de forma análoga a como se
ha descrito anteriormente. Obtenemos la siguiente tabla:

x1 x2 x 3 x4 x5 x6 b
−1 1 −2 1
x1 1 3
0 3
0 3 3

x5 0 2 0 0 1 1 6
2 1 1 13
x3 0 3
1 3
0 3 3

0 4 0 1 0 2

Por lo tanto, la nueva solución básica está formada por las variables (x1 , x5 , x3 ). Para
saber si es la óptima, miramos la tabla y como podemos observar, todos los costos
son no negativos, ası́ como los términos independientes. Por lo tanto, es solución
óptima.

6
Optimización Lineal.
Métodos Simplex. Marı́a José Benı́tez Caballero

Ası́, la solución al problema es:

1
x1 = 3
x4 = 0
x2 = 0 x5 = 6
13
x3 = 3
x6 = 0

Y la función objetivo toma el valor z( 13 , 0, 13

3
) = −17.

Ejemplo 2.2. Un vehı́culo de transporte que tiene capacidad para transportar 6

unidades de peso y 7 unidades de volumen, puede transportar 4 tipos de artı́culos
cuyos pesos, volúmenes y beneficios unitarios son:

A1 A2 A3 A4
Peso 2 3 4 5
Volumen 3 1 2 4
Beneficio 5 3 6 8

¿Cuántos artı́culos de cada tipo debe transportar para maximizar el beneficio?

Solución: Primero, vamos a definir las variables que presenta el problema:

x1 ≡ Unidades de artı́culo A1 transportado

x2 ≡ Unidades de artı́culo A2 transportado
x3 ≡ Unidades de artı́culo A3 transportado
x4 ≡ Unidades de artı́culo A4 transportado

Al tener definidas las variables podemos plantear el problema. Como se nos pide
obtener el máximo beneficio, la función objetivo se construirá con los datos de be-
neficio planteados en la tabla. Ası́, la función objetivo que debemos maximizar es
Z(x1 , x2 , x3 , x4 ) = 5x1 + 3x2 + 6x3 + 8x4 . Por lo tanto, con el resto de información
construiremos las restricciones que deben cumplirse. Como el peso que se puede
transportar no puede superar las 6 unidades, tenemos que 2x1 + 3x2 + 4x3 + 5x4 6 6.
Del mismo modo tenemos que para las unidades de volumen la restricción serı́a
3x1 +x2 +2x3 +4x4 6 7. Es obvio que no se pueden transportar una cantidad negativa

7
Optimización Lineal.
Métodos Simplex. Marı́a José Benı́tez Caballero

de artı́culos, por lo tanto, todas las variables deben ser no negativas. Condensando
toda esta información, el problema de Optimización Lineal se puede expresar ası́:

max Z(x1 , x2 , x3 , x4 ) = 5x1 + 3x2 + 6x3 + 8x4

sujeto a 2x1 + 3x2 + 4x3 + 5x4 6 6
3x1 + x2 + 2x3 + 4x4 6 7
xi > 0, i = 1, 2, 3, 4

Como el problema está en forma canónica, podemos definir todos los elementos
asociado al problema de Optimización Lineal.
~ = (x1 , x2 , x3 , x4 )
Vector de variables X
Vector de costos ~c = (5, 3, 6, 8)
Matriz de coeficientes o de costos tecnológicos
 
2 3 4 5
A= 
3 1 2 4

Vector de términos independientes ~b = (6, 7)

El problema lo tenemos descrito en forma canónica, pero no estándar. Lo cual es
necesario para comenzar el método Simplex necesario. Por ello, introducimos las
variables holgura. En este caso, como todas las restricciones son 6, las variables
holgura entrar sumando. Ası́, el problema nos queda:

max Z(x1 , x2 , x3 , x4 , x5 , x6 ) = 5x1 + 3x2 + 6x3 + 8x4

sujeto a 2x1 + 3x2 + 4x3 + 5x4 + x5 = 6
3x1 + x2 + 2x3 + 4x4 + x6 = 7
xi > 0, i = 1, 2, 3, 4, 5, 6

Por lo tanto, los elementos asociados al problema se verán modificados del siguiente
modo:
~ = (x1 , x2 , x3 , x4 , x5 , x6 )
Vector de variables X

8
Optimización Lineal.
Métodos Simplex. Marı́a José Benı́tez Caballero

Vector de costos ~c = (5, 3, 6, 8, 0, 0)

Matriz de coeficientes o de costos tecnológicos
 
2 3 4 5 1 0
A= 
3 1 2 4 0 1

Vector de términos independientes ~b = (6, 7)

~h = (x5 , x6 )
Vector de variables holgura X
Ahora, el problema está en la forma adecuada para poder aplicar el método Simplex
adecuado. Para elegir entre el método Simplex o el Simplex Dos Fases, debemos
fijarnos en la matriz de costos tecnológicos. Como encontramos la matriz identidad
de orden 2 dentro de la matriz de coeficientes, podemos aplicar el método Simplex.
Ası́, la primera tabla con la que trabajaremos es:

x1 x2 x3 x4 x5 x6 b
x5 2 3 4 5 1 0 6
x6 3 1 2 4 0 1 7
5 3 6 8 0 0

La tabla es factible, ya que los valores de los términos independientes son no ne-
gativos; pero no es óptima, ya que al estar maximizando necesitamos que todos los
costos sean negativos o ceros. Por lo tanto, comenzamos con el método. Para ello,
elegimos como variable que entra x4 , ya que es la variable con mayor costo. Para
saber la variable por la que se cambia, debemos calcular el mı́nimo de los términos
independientes entre los coeficientes de la variable que sale, es decir:
 
6 7 6
mı́n , =
5 4 5
Como el valor 65 corresponde a la variable x5 , es esta la que sale, obteniendo la
siguiente tabla al hacer las cuentas:

x1 x2 x 3 x4 x5 x6 b
2 3 4 1 6
x4 5 5 5
1 5
0 5
7 −7 −6 −4 11
x6 5 5 5
0 5
1 5
9 −9 −2 −8
5 5 5
0 5
0

9
Optimización Lineal.
Métodos Simplex. Marı́a José Benı́tez Caballero

Como podemos observar la solución, sigue sin ser óptima, ya que aún existen costos
marginales positivos. Ası́ pues, la variable que entra es x1 , y para saber cual sale
calculamos el siguiente mı́nimo
 6 11   
11 11
5 5
mı́n 2 , 7 = mı́n 3, = mı́n{3, 10 5714} =
5 5
7 7

Lo que implica que sale la variable x6 . Como podemos ver en la tabla (señalado
en rojo), el elemento pivote no es un 1. Ası́ que debemos multiplicar la fila por 57
para obtenerlo. A continuación, procederemos a obtener los ceros en el resto de la
columna:
x1 x 2 x3 x4 x5 x6 b
8 3 −2 4
x4 0 1 7
1 7 7 7
−6 −4 5 11
x1 1 −1 7
0 7 7 7
8 −4 −9
0 0 7
0 7 7

La solución sigue sin ser una solución óptima, ya que siguen existiendo costos po-
sitivos. En este caso, la única opción es cambiar la variable x4 por la variable x3 .
Realizamos los cambios necesarios en la tabla, obteniendo:

x1 x2 x3 x4 x5 x6 b
7 7 3 −1 1
x3 0 8
1 8 8 4 2
−1 3 −1 1
x1 1 4
0 4 4 2
2
0 −1 0 −1 −1 −1

Esta solución ya es óptima. Por lo tanto,

x1 = 2 x5 = 0
x2 = 0 x6 = 0
1
x3 = 2

x4 = 0

Y el valor que toma la función objetivo será Z(2, 0, 12 , 0) = 13.

10