Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

CONTENIDO
PRODUCCIÓN Y OPERACIONES

MÉTODO SIMPLEX PASO A PASO: EJEMPLOS

DE MAXIMIZAR Y MINIMIZAR
Una de las temáticas que nunca falta en el desarrollo del curso de
investigación de operaciones es el algoritmo simplex.

¿Qué es el método simplex?

El método simplex es un procedimiento iterativo para resolver problemas de
programación lineal, donde se busca obtener la solución óptima de la
función objetivo que logre cumplir el conjunto de restricciones.

Este algoritmo fue desarrollado en el año 1947 por el matemático norteamericano

George Dantzig

Conceptos Básicos
Para comprender de mejor manera el método simplex vamos a revisar algunas
definiciones.
El método parte de dos afirmaciones importantes:
1. El conjunto de posibles soluciones o conjunto factible de cualquier
problema de programación lineal puede representarse mediante un
poliedro convexo. Si un problema de programación lineal tiene una solución
óptima y finita, ésta estará en un vértice del poliedro convexo que
representa al problema.
2. El algoritmo simplex parte de uno de los vértices del poliedro, y verifica si
es el óptimo; si no lo es, busca un nuevo vértice adyacentes que va
mejorando el valor de la función objetivo. Se continúa iterando hasta llegar
al vértice que representa la solución óptima.
En la siguiente imagen vemos el poliedro que representa la solución factible y
cómo realiza el recorrido el algoritmo simplex:

1/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

Pasos del Método Simplex

Los pasos para seguir en el método simplex son:

1. Definir el problema en la forma

estándar y generar nuestra matriz.
2. Determinar la solución básica inicial.
3. Seleccionar la variable de entrada
utilizando la condición de optimalidad. Si
no se puede seleccionar una variable de
entrada, quiere decir que estamos en la
condición óptima y
finalizan las iteraciones. De otro modo se
continúa con el siguiente paso.
4. Seleccionar la variable de salida
utilizando la condición de factibilidad.
5. Actualizar nuestra matriz realizando las
operaciones de Gauss-Jordan. Volver al
paso número 3.

2/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

1. Def i nir el problema en la

forma estándar y generar matriz
Un problema de programación lineal tiene la
siguiente forma:

Donde x1, x2 … xn son las variables del problema.

Antes de llevar nuestro modelo a la forma estándar

debemos veri car que todas las restricciones
tienen el lado derecho no negativo. Es decir:

b1, b2 … bm ≥ 0

¿Qué hago si el lado derecho de la

restricción es negativo?

Cuando el término independiente de la restricción

es negativo, se debe multiplicar por -1 a toda la
restricción para convertir el valor del lado derecho
en positivo. Esta multiplicación también afectará al
signo de la restricción de la siguiente forma:

Si la restricción es del tipo mayor igual (≥), se

deberá cambiar a menor igual (≤).
En caso la restricción sea del tipo menor igual
(≤), se deberá cambiar a mayor igual (≥).

3/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

Si la restricción es una igualdad, el signo se

mantiene.

Un caso especial es cuando el término

independiente de la restricción es 0 y el signo es
mayor igual (≥); en dicha situación, podemos
multiplicar la restricción por (-1) para convertirla en
menor igual (≤). Esto nos servirá para no utilizar
variables artificiales como veremos
posteriormente.

Convertir restricciones en igualdades

Para convertir las restricciones en igualdades va a

depender de su signo:

Si la restricción es menor igual (≤): Para este tipo

de restricciones debemos introducir una
variable no negativa llamada de holgura y que
son auxiliares para el problema. Por ejemplo:

Cuando la restricción es mayor igual (≥): En este

tipo de restricciones se debe restar una variable

4/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

de exceso y así mismo agregar una variable

artif i cial. Por ejemplo:

Si la restricción es igual (=): En este tipo de

restricciones debemos agregar una variable
artif i cial de la siguiente forma:

El método Simplex “tradicional” o “básico” que

abordaremos en esta entrada, se utiliza para los
problemas de programación lineal donde todas las
restricciones son del tipo menor e igual (≤). Para las
restricciones que utilizan variables artificiales
5/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

debemos utilizar el método de 2 fases

Generar la matriz

Aplicando lo indicado en los puntos anteriores

tendríamos lo siguiente:

Una vez convertidas nuestras restricciones en

ecuaciones procederemos a generar nuestra
matriz:

En nuestra matriz podemos identif i car lo siguiente:

6/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

Vector de Costes: Es el vector que contiene los

coef i cientes de todas las variables de la
función objetivo. En la parte inferior del vector
se indican las variables en orden.
Vector Solución: En esta columna se coloca la
solución básica inicial y se va actualizando
conforme se realizan las iteraciones. En la
columna Cb se indica el coeficiente que
corresponde a cada variable en el vector de
costes. Así mismo siempre se iniciará con las
variables de holgura en la base cuando el
problema no tenga variables artificiales.
Coef i cientes Restricciones: Se colocan los
coef i cientes de las restricciones en el mismo
orden en que fueron formuladas. La columna R
contiene a los términos independientes también
conocido como vector de recursos.
Vector de costes reducidos: También conocido
como precios sombra. Este vector se calcula
multiplicando el vector solución por los
coef i cientes de las restricciones y se resta el
vector de costes. Este procedimiento lo
explicaremos al detalle en nuestra entrada del
método de las dos fases y de la M Grande,
donde se presentan variables artif i ciales. En
los ejercicios que veremos en esta entrada, al
no existir variables artificiales, el vector de
costes será igual al vector de costes
multiplicado por
“-1”.

7/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

2. Determinar la solución básica inicial:

Como habíamos mencionado, el método simplex

parte de un vértice de la región factible, es decir, un
punto extremo. Con cada iteración avanzaremos de
vértice en vértice hasta llegar a la solución óptima.

En nuestro caso, en la matriz elaborada podemos

ver la solución básica inicial que sería S1=35, S2=18
y S3=26 (cada variable del vector solución se iguala
al valor que se encuentra en la columna R. Estas
variables se denominan variables básicas. El valor
de Z inicial también se muestra en la columna R
que es 0.

Las variables que no se encuentran en la base se

denominan variables no básicas y en este caso

8/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

serían X1 y X2. Ambas tienen un valor de 0. ¿Con

esta solución tenemos el mejor valor de Z? Para
saberlo debemos continuar al siguiente paso:

3. Seleccionar la variable de entrada

utilizando la condición de optimalidad

Con nuestra matriz f i nalizada e identificada nuestra

solución básica inicial revisaremos la condición de
optimalidad.

Condición de Optimalidad:

La condición de optimalidad consiste en veri car si

la solución actual que tenemos en nuestra matriz
es la óptima o si se puede mejorar. Se veri ca de la
siguiente manera:

En un problema de maximización si todos los

coef i cientes del vector de costes reducidos son
mayores o iguales que cero, quiere decir que
estamos en el punto óptimo y f i naliza el
problema.
En un problema de minimización si todos los
coef i cientes del vector de costes reducidos son
menores o iguales que cero, quiere decir que
estamos en el punto óptimo y f i naliza el
problema.

Siguiendo con el ejemplo, siendo el problema de

maximización, podemos ver que en el vector de
costes reducidos existen valores negativos, lo que
significa que no estamos en el óptimo. Eso quiere
decir que debemos iniciar las iteraciones
seleccionando la variable de entrada.

9/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

Variable de Entrada
La variable de entrada hace referencia a una de las
variables no básicas que ingresará a la base y
formará parte de la solución del problema.

Los criterios para seleccionar la variable de entrada

depende si el problema es de maximización o
minimización:

Para problemas de maximización, la variable de

entrada será la variable no básica con el
coeficiente más negativo en el vector de costes
reducidos.
Para problemas de minimización, la variable de
entrada será la variable no básica con el
coeficiente más positivo en el vector de costes
reducidos.

La columna donde está ubicada la variable se

denomina columna pivote.

En el ejemplo nuestra variable de entrada sería X 1

dado que tiene el valor más negativo en el vector
de costes reducidos, es decir “-3”:

10/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

4. Seleccionar la Variable de Salida con

la Condición de Factibilidad

A continuación explicaremos a que se re ere la

condición de factibilidad:

Condición de Factibilidad

La condición de factibilidad, para cualquier

problema ya sea de maximización o minimización,
se veri ca evaluando los valores de los coef i cientes
de la matriz de restricciones que se encuentran en
la columna que corresponde a la variable de
entrada.

Se debe veri car que al menos uno de sus valores

sea mayor que 0 para obtener nuestra variable de
salida. Si no se cumple esa condición signif i ca
que el problema tiene solución ilimitada no
acotada.

Variable de Salida

Para determinar la variable que sale de la base se

debe dividir el valor correspondiente a la columna
R con su respectivo coeficiente en la columna de
la variable de entrada (siempre y cuando este
coef i ciente sea estrictamente positivo).

De los resultados obtenidos, el menor valor

corresponde a la que contiene a la variable de
salida. Esta la llamaremos l a f i l a pivote

Veremos su aplicación con el ejemplo:

11/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

La variable de salida sería S2. El número que se

encuentra al cruzar la f i la pivote y la columna
pivote es el elemento pivote; en nuestro caso sería
3:

5. Actualizar la Matriz

Una vez determinado nuestro elemento pivote,

realizaremos las operaciones de Gauss-Jordan para
formar nuestra matriz identidad

El nuevo valor de cada la se calculará de la

siguiente manera:

12/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

Para la f i la pivote: El nuevo valor se obtendrá

dividiendo el valor actual entre el elemento
pivote.

Nuevo Valor Fila Pivote = Valor Actual Fila Pivote /

Elemento Pivote

Para las otras las: El nuevo valor se calcula

restando del valor actual, la multiplicación del
elemento de la f i la que se encuentra en la
columna pivote por el nuevo valor calculado en
la f i la pivote.

Nuevo Valor = Valor Actual – (Elemento Fila

Columna Pivote*Nuevo Valor Fila Pivote).

Para entenderlo mejor, continuaremos resolviendo

el ejemplo. Iniciaremos con la f i la pivote:

En las otras las realizaremos los cálculos de forma

diferente. Iniciaremos con la f i la de S1:

13/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

Para la la S3 tenemos:

14/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

Finalmente en la f i la Z tenemos:

La matriz resultante sería:

15/25
 Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

Cómo puedes ver la posición donde se encontraba

nuestro elemento pivote ahora es 1 y los elementos
que lo acompañan en la columna se convierten en
0. Es así que empezamos a formar nuestra matriz
identidad.

Volver al paso número 3

Con este último resultado, volveremos al paso 3 y

repetiremos el proceso. Cómo existen valores
negativos en el vector de costes reducidos,
podemos seguir optimizando.

El único valor negativo es -4, por lo que la variable

que ingresará es X2.

Para elegir la variable que va a salir, dividimos cada

valor de la columna R por su contraparte de la
columna X2 (este último valor debe ser positivo)

23/(19/3) = 69/19 = 3.632

El valor en la columna X2 es negativo por lo que
no se toma en cuenta.
14/(16/3) = 21/8 = 2.625

El menor valor se encuentra en la la de S3, por lo que es la variable que saldrá

de la base. El elemento pivote es 16/3.

16/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

Realizamos nuevamente las iteraciones obteniendo

el siguiente resultado:

En esta última matriz vemos que el vector de costes

reducidos ya no tiene ningún valor negativo, lo que
quiere decir que nos encontramos en el valor
óptimo. Obtendremos los valores de las variables
básicas y de Z de la siguiente forma:

Las variables que no se encuentran en la base

tendrán valor de 0.

Solución: X1= 31/4, X2= 21/8, S1= 51/8, S2= 0, S3= 0,

Z = 57/2

Ejemplo 1 – Maximizar:
17/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

A continuación se presenta un nuevo problema de

maximización:

Función Objetivo

Maximizar: Z = 2X1 + 5X2

Sujeto a:

X1 + 6X2 ≤ 20

X1 + X2 ≤ 60

X1 ≤ 40

X1, X2 ≥ 0

Solución

El problema se adecuará al modelo estándar de

programación lineal, agregando las variables de
holgura, exceso y/o artif i ciales en cada una de las
restricciones:

Restricción 1: Tiene signo “≤” (menor igual) por

lo que se agrega la variable de holgura S1.
Restricción 2: Tiene signo “≤” (menor igual) por
lo que se agrega la variable de holgura S2.
Restricción 3: Tiene signo “≤” (menor igual) por
lo que se agrega la variable de holgura S3.

A continuación se muestra el problema en la forma

estándar. Se colocará el coeficiente 0 (cero) donde
corresponda para crear nuestra matriz:

18/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

Para encontrar la variable que entra a la base

elegimos el valor más negativo del vector de costes
reducidos: -5. Por lo tanto la variable de entrada
sería X2.

Para la variable de salida dividiremos los valores de

la columna R con los de la columna X2 (siempre y
cuando sean positivos). Los resultados en orden
serían: 20/6, 60 y la última la no se considera
porque su valor correspondiente a X2 no es positivo
(0). Se debe elegir el menor valor de esta división:

19/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

20/6; por lo tanto la variable de salida se encuentra

en la primera la: S1.

El elemento pivote se encuentra en el cruce de X2 y

S1: 6.

Realizamos las reducciones de Gauss-Jordan:

Ingresa la variable X1 y sale de la base la

variable X2. El elemento pivote es 1/6. Repetimos
las operaciones de Gauss-Jordan y obtenemos la
siguiente matriz:

20/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

En esta última matriz, todos los valores del vector

de costes reducidos son positivos lo que indica que
nos encontramos en el punto óptimo. El resultado
sería:

Ejemplo 2 – Minimizar
Se tiene el siguiente problema:

Función Objetivo

Minimizar: Z = 3X1 – 2X2

Sujeto a:

21/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

2X1 + X2 ≤ 18

2X1 + 3X2 ≤ 42

3X1 – 2X2 ≤ 5

X1, X2 ≥ 0

Solución

El problema se adecuará al modelo estándar de

programación lineal, agregando las variables de
holgura, exceso y/o artif i ciales en cada una de las
restricciones:

Restricción 1: Tiene signo “≤” (menor igual) por

lo que se agrega la variable de holgura S1.
Restricción 2: Tiene signo “≤” (menor igual) por
lo que se agrega la variable de holgura S2.
Restricción 3: Tiene signo “≤” (menor igual) por
lo que se agrega la variable de holgura S3.

A continuación se muestra el problema en la forma

estándar. Se colocará el coeficiente 0 (cero) donde
corresponda para crear nuestra matriz:

22/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

Como el ejercicios es de minimización, elegiremos

el mayor valor positivo para la variable de entrada:
2. Por lo tanto la variable de entrada sería X2.

Para la variable de salida dividiremos los valores de

la columna R con los de la columna X2 (siempre y
cuando sean positivos). Los resultados en orden
serían: 18/1, 42/3 y la última la no se considera
porque su valor correspondiente a X2 es negativo
(-2). Se debe elegir el menor valor de esta división:
42/3=14; por lo tanto la variable de salida se
encuentra en la segunda la: S2.

El elemento pivote se encuentra en el cruce de X2 y

S2: 3.

Realizamos las reducciones de Gauss-Jordan:

23/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

En esta última matriz, todos los valores del vector

de costes reducidos son negativos, lo que indica
que nos encontramos en el punto óptimo del
problema de minimización. El resultado sería:

Nota: El valor de Z puede ser negativo ya que el

problema resuelto no restringe su valor.

Ejercicios Resueltos del

Método Simplex
A continuación encontrarás algunos ejemplos
adicionales resueltos con nuestra calculadora
online de programación lineal (versión de
membresía):

24/25
Método Simplex Paso a Paso: Ejemplos de Maximizar y Minimizar

Ref l exión Final

El método simplex es una temática infaltable
cuando se aborda la programación lineal; así que
es indispensable que conozcas cómo aplicarlo en
los diferentes tipos de problemas. Con los ejemplos
mostrados estarás en la capacidad de resolver
ejercicios donde no se requiera el uso de variables
artificiales.

25/25