1

Descripción del método simplex

Códigos PACS: 02.10.Yh, 02.09.+p

Derlis Hernández Lara ¹*

1 Centro de Investigación en Computación, Instituto Politécnico Nacional

* dhernandezl0600 @ipn.mx

_________________________________________________________________

Resumen. En este trabajo se describe el método simplex, haciendo énfasis en las consideraciones más

significativas que esto conlleva, como son los fundamentos necesarios para su correcta interpretación y

aplicación. El algebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de

ecuaciones lineales constituye la base del método simplex, cuya principal aplicación es resolver problemas

de programación lineal en los que intervienen tres o más variables [1]. Al aplicar dicho método se obtiene la

trayectoria más óptima de un sistema, ya sea encontrando su valor máximo o el mínimo, dependiendo de la

necesidad del sistema o problema planteado. Es importante determinar primero si el sistema con el que se está

trabajando tiene solución o no, porque puede darse el caso de que se empiece a trabajar y no se llegue a

ninguna solución, para esto la descripción del método se apoya en la obtención del determinante del sistema

de ecuaciones, el cual debe cumplir la condición de ser diferente de cero para que exista una solución,

situación de la cual no es posible percatarse si solo se aplica el método de Gauss-Jordan.

Palabras clave: Método simplex, Gauss-Jordan, álgebra matricial, programación lineal.

Abstract. This paper describes the simplex method, emphasizing the most significant considerations

that entails, as are the necessary foundations for proper interpretation and application. Matrix algebra and the

process of Gauss-Jordan elimination to solve a system of linear equations is the basis of the simplex method,

whose main application is to solve linear programming problems that involve three or more variables [1]. By

applying this method provides the optimum trajectory of a system, either by finding its maximum or

minimum value, depending on the needs of the system or problem. It´s important to first determine if the

system you are working has a solution or not, because it may happen that you start working and not come to

any solution to this description of the method relies on obtaining the determinant system of equations, which

must meet the condition of being different from zero so that there is a solution, a situation which can´t realize

itself applies the Gauss-Jordan.

Keywords: Simplex method, Gauss-Jordan, matrix algebra, linear programming.

________________________________________________________________________________________

Introducción

El Método Simplex es un método analítico de

solución a problemas de programación lineal

capaz de resolver modelos más complejos

que los resueltos mediante el método gráfico

sin restricción en el número de variables.

El Método Simplex es un método iterativo

que permite ir mejorando la solución en cada

paso. La razón matemática de esta mejora

radica en que el método consiste en caminar

del vértice de un poliedro a un vértice vecino

de manera que aumente o disminuya (según

2

el contexto de la función objetivo, sea

maximizar o minimizar), dado que el número

de vértices que presenta un poliedro solución

es finito, siempre se hallará solución.

Este famoso método fue creado en el año de

1947 por el estadounidense George Bernard

Dantzig y el ruso Leonid Vitalievich

Kantorovich, con el ánimo de obtener un

algoritmo capaz de solucionar problemas

de m restricciones y n variables [2].

DETERMINANTE DE UNA MATRIZ

Definición: Sea una matriz de 2 x 2 se define

el determinante de la matriz A, y se expresa

como det(A) o bien |A|, de la siguiente

manera:

[

] (1)

det(A) = |A| =a11 · a22 – a12 · a21

(2)

Dada una matriz cuadrada A de orden n, se

define el menor complementario de un

elemento de A, aij, como el determinante de la

matriz que se obtiene al suprimir la fila i y la

columna j en la que se encuentra dicho

elemento aij. El menor se representa por Mij.

Se define el menor de un elemento aij al

determinante que resulta de eliminar el

renglón i y la columna j [5]. Si se denota

como Mij a tal determinante, se tiene:

(3)

El determinante de una matriz determina si

los sistemas son singulares o mal

condicionados. En otras palabras sirve para

determinar la existencia y la unicidad de los

resultados de los sistemas de ecuaciones

lineales. Un determinante con valor cero

indica que se tiene un sistema singular, un

determínate con valor cercano a cero indica

que se tiene un sistema mal condicionado.

Un sistema singular es cuando en el sistema

de ecuaciones se tiene a más de una ecuación

con el mismo valor de la pendiente. Por

ejemplo ecuaciones que representan líneas

paralelas o que coinciden en los mismos

puntos de graficación [4].

MÉTODO DE GAUSS-JORDAN

Consiste en hacer transformaciones

elementales en las filas de la matriz para

llegar a obtener la matriz identidad.

Realizando estas mismas transformaciones

con la matriz identidad llegamos a la matriz

.

Se llama transformación elemental en una

matriz a:

1) Multiplicar o dividir una fila por un

número real distinto de cero.

2) Sumar o restar a una fila otra multiplicada

por un número real no nulo.

3) Intercambiar el lugar de dos filas entre sí.

Algoritmo de eliminación de Gauss-Jordan

1.- Ir a la columna no cero extrema izquierda.

2.- Si el primer renglón tiene un cero en esta

columna, intercambiarlo con otro que no lo

tenga.

3.- Luego, obtener ceros debajo de este

elemento delantero, sumando múltiplos

3

adecuados del renglón superior a los

renglones debajo de él.

4.- Cubrir el renglón superior y repetir el

proceso anterior con la submatriz restante.

Repetir con el resto de los renglones (en este

punto la matriz se encuentra en la forma de

escalón).

5.- Comenzando con el último renglón no

cero, avanzar hacia arriba: para cada renglón

obtener un 1 delantero e introducir ceros

arriba de éste sumando múltiplos

correspondientes a los renglones con los que

se este trabajando.

Una variante interesante de la eliminación de

Gauss es a la que se llama eliminación de

Gauss-Jordan, que consiste en ir obteniendo

los 1 delanteros durante los pasos uno al

cuatro (llamados paso directo) así para

cuando estos finalicen ya se obtendrá la

matriz en forma escalonada reducida.

Este método se desarrollara cuando se esté

describiendo el método simplex, porque está

implícito en la búsqueda del punto más

óptimo de un sistema de ecuaciones lineales,

recordando que lo que se obtiene es la matriz

identidad [1].

MATRIZ IDENTIDAD

Una matriz puede definirse como una

ordenación rectangular de elementos, (o

listado finito de elementos), los cuales pueden

ser números reales o complejos, dispuestos en

forma de filas y de columnas.

La matriz idéntica o identidad es una matriz

cuadrada (que posee el mismo número tanto

de columnas como de filas) de orden n que

tiene todos los elementos diagonales iguales a

uno (1) y todos los demás componentes

iguales a cero (0), se denomina matriz

idéntica o identidad de orden n, y se denota

por:

(4)

La importancia de la teoría de matrices en el

Método Simplex es fundamental, dado que el

algoritmo se basa en dicha teoría para la

resolución de sus problemas.

PROGRAMACIÓN LINEAL

La Programación Lineal (PL) es una de las

principales ramas de la Investigación

Operativa. En esta categoría se consideran

todos aquellos modelos de optimización

donde las funciones que lo componen, es

decir, función objetivo y restricciones, son

funciones lineales en las variables de decisión

Los modelos de Programación Lineal por su

sencillez son frecuentemente usados para

abordar una gran variedad de problemas de

naturaleza real en ingeniería y ciencias

sociales, lo que ha permitido a empresas y

organizaciones importantes beneficios y

ahorros asociados a su utilización [3].

Los modelos matemáticos se dividen

básicamente en modelos deterministas

(MD) o modelos estocásticos (ME). En el

primer caso (MD) se considera que los

parámetros asociados al modelo son

conocidos con certeza absoluta, a diferencia

de los modelos estocásticos, donde la

totalidad o un subconjunto de los parámetros

tienen una distribución de probabilidad

asociada. Los cursos introductorios a la

investigación operativa generalmente se

enfocan sólo en modelos deterministas, como

se muestra en la figura 1.

4

Figura 1, División de los modelos matemáticos.

Pasos para resolver un problema de

programación lineal

1. Elegir las incógnitas.

2. Escribir la función objetivo en función de

los datos del problema.

3. Escribir las restricciones en forma de

sistema de inecuaciones.

4. Averiguar el conjunto de soluciones

factibles representando gráficamente las

restricciones.

5. Calcular las coordenadas de los vértices del

recinto de soluciones factibles (si son pocos).

6. Calcular el valor de la función objetivo en

cada uno de los vértices para ver en cuál de

ellos presenta el valor máximo o

mínimo según nos pida el problema (hay que

tener en cuenta aquí la posible no existencia

de solución si el recinto no está acotado).

Descripción del método simplex

El método simplex es un procedimiento

iterativo que permite ir mejorando la solución

a cada paso. El proceso concluye cuando no

es posible seguir mejorando más dicha

solución.

Partiendo del valor de la función objetivo en

un vértice cualquiera, el método consiste en

buscar sucesivamente otro vértice que mejore

al anterior. La búsqueda se hace siempre a

través de los lados del polígono (o de las

aristas del poliedro, si el número de variables

es mayor). Cómo el número de vértices (y de

aristas) es finito, siempre se podrá encontrar

la solución [2].

El método simplex se basa en la siguiente

propiedad: si la función objetivo, f, no toma

su valor máximo en el vértice A, entonces hay

una arista que parte de A, a lo largo de la

cual f aumenta.

Para conocer la metodología que se aplica en

el método, se resuelve el siguiente problema:

Maximizar Z= f(x,y)= 3x + 2y (5)

sujeto a: 2x + y 18 (6)

2x + 3y 42 (7)

3x + y 24 (8)

x 0 , y 0 (9)

Se consideran las siguientes fases:

1. Convertir las desigualdades en igualdades

Se introduce una variable de holgura por cada

una de las restricciones, para convertirlas en

igualdades, resultando el sistema de

ecuaciones lineales:

2x+ y + h = 18 (10)

2x+ 3y + s = 42 (11)

3x+y + d = 24 (12)

2. Igualar la función objetivo a cero

- 3x - 2y + Z = 0 (13)

3. Escribir la tabla inicial simplex

5

En las columnas aparecerán todas las

variables del problema y, en las filas, los

coeficientes de las igualdades obtenidas, una

fila para cada restricción y la última fila con

los coeficientes de la función objetivo:

Tabla I. Iteración nº 1

Base Variable de

decisión

Variable

de holgura

Valores

solución

x y h s d

h 2 1 1 0 0 18

s 2 3 0 1 0 42

d 3 1 0 0 1 24

Z -3 -2 0 0 0 0

4. Encontrar la variable de decisión que

entra en la base y la variable de holgura que

sale de la base

a) Para escoger la variable de decisión que

entra en la base, se observa la última fila, la

de los coeficientes de la función objetivo y se

selecciona la variable con el coeficiente

negativo mayor (en valor absoluto).

En este caso, la variable ‘x’ de coeficiente -3.

Si existiesen dos o más coeficientes iguales

que cumplan la condición anterior, entonces

se elige uno cualquiera de ellos.

Si en la última fila no existiese ningún

coeficiente negativo, significa que se ha

alcanzado la solución óptima. Por tanto, lo

que va a determinar el final del proceso de

aplicación del método del simplex, es que en

la última fila no haya elementos negativos.

La columna de la variable que entra en la

base se llama columna pivote (en color azul).

b) Para encontrar la variable de holgura que

tiene que salir de la base, se divide cada

término de la última columna (valores

solución) por el término correspondiente de la

columna pivote, siempre que estos últimos

sean mayores que cero. En este caso:

18/2 [=9], 42/2 [=21] y 24/3 [=8]

Si hubiese algún elemento menor o igual que

cero no se hace dicho cociente. En el caso de

que todos los elementos fuesen menores o

iguales a cero, entonces se tendría una

solución no acotada y no se puede seguir.

El término de la columna pivote que en la

división anterior dé lugar al menor cociente

positivo, el 3, porque 8 es el menor, indica la

fila de la variable de holgura que sale de la

base, ‘d’. Esta fila se llama fila pivote (en

color azul).

Si al calcular los cocientes, dos o más son

iguales, indica que cualquiera de las variables

correspondientes pueden salir de la base.

c) En la intersección de la fila pivote y

columna pivote se encuentra el elemento

pivote operacional, 3.

5. Encontrar los coeficientes de la nueva

tabla

Los nuevos coeficientes de ‘x’ se obtienen

dividiendo todos los coeficientes de la

fila ‘d’ por el pivote operacional, 3, que es el

que hay que convertir en 1.

A continuación mediante el método de

eliminación de Gauss se hacen ceros los

restantes términos de su columna, con lo que

se obtiene los nuevos coeficientes de las otras

filas incluyendo los de la función

objetivo ‘Z’.

Obsérvese el siguiente ejemplo:

Vieja fila de s 2 3 0 1 0 42

- - - - - -

Coeficiente 2 2 2 2 2 2

x x x x x x

Nueva fila pivote 1 1/3 0 0 1/3 8

= = = = = =

Nueva fila de s 0 7/3 0 1 -2/3 26

6

Tabla II. Iteración nº 2

Base Variable

de

decisión

Variable de

holgura

Valores

solución

x y h s d

h 0 1/3 1 0 -2/3 2

s 0 7/3 0 1 -2/3 26

x 1 1/3 0 0 1/3 8

Z 0 -1 0 0 1 24

Como en los elementos de la última fila hay

uno negativo, -1, significa que no se ha

llegado todavía a la solución óptima. Hay que

repetir el proceso:

La variable que entra en la base es ‘y’, por ser

la variable que corresponde al coeficiente -1

Para calcular la variable que sale, se dividen

los términos de la última columna entre los

términos correspondientes de la nueva

columna pivote: 2:1/3[=6], 26:7/3[=78/7] y

8:1/3[=8], como el menor cociente positivo es

6, se tiene que la variable de holgura que sale

es ‘h’.

El elemento pivote, que ahora hay que hacer

1, es 1/3.

Operando de forma análoga a la anterior se

obtiene la tabla:

Tabla III. Iteración nº 3

Base Variable de

decisión

Variable

de holgura

Valores

solución

x y h s d

y 0 1 3 0 -2 6

s 0 0 -7 1 4 12

x 1 0 -1 0 1 6

Z 0 0 3 0 -1 30

Como en los elementos de la última fila hay

uno negativo, -1, significa que no se ha

llegado todavía a la solución óptima. Hay que

repetir el proceso: La variable que entra en la

base es ‘d’, por ser la variable que

corresponde al coeficiente -1

Para calcular la variable que sale, se dividen

los términos de la última columna entre los

términos correspondientes de la nueva

columna pivote: 6/-2[=-3], 12/4[=3], y

6:1[=6], como el menor cociente positivo es

3, se tiene que la variable de holgura que sale

es s.

El elemento pivote, que ahora hay que hacer

1, es 4.

Se obtiene la siguiente tabla:

Tabla IV. Final del proceso

Base Variable

de

decisión

Variable de

holgura

Valores

solución

x y h s d

y 0 1 -1/2 -1/2 0 12

d 0 0 -7/4 1/4 1 3

x 1 0 3/4 -1/4 0 3

Z 0 0 5/4 1/4 0 33

Como todos los coeficientes de la fila de la

función objetivo son positivos, se ha llegado

a la solución óptima.

La solución óptima viene dada por el valor de

‘Z’ en la columna de los valores solución, en

este caso: 33. En la misma columna se puede

observar el vértice donde se alcanza, viendo

las filas correspondientes a las variables de

decisión que han entrado en la base: D(3,12).

Si en el problema de maximizar aparecieran

como restricciones, inecuaciones de la forma:

; multiplicándolas por -1 se

transforman en inecuaciones de la forma

– , y se llega al caso anterior.

Si en lugar de maximizar se trata de un

problema de minimizar se sigue el mismo

proceso, pero cambiando el sentido del

criterio, es decir, para entrar en la base se

7

elige la variable cuyo valor, en la fila de la

función objetivo, sea el mayor de los

positivos y se finalizan las iteraciones cuando

todos los coeficientes de la fila de la función

objetivo son negativos.

Interpretación geométrica del método del

simplex

Las sucesivas tablas que se han construido

van proporcionando el valor de la función

objetivo en los distintos vértices, ajustándose,

a la vez, los coeficientes de las variables

iniciales y de holgura.

En la primera iteración (Tabla I) han

permanecido todos los coeficientes iguales, se

ha calculado el valor de la función objetivo

en el vértice A(0,0), siendo este 0.

A continuación se desplaza por la arista AB,

calculando el valor de f, hasta llegar a B.

Este paso aporta la Tabla II.

En esta segunda iteración se ha calculado el

valor que corresponde al vértice B(8,0):

Z=f(8,0) = 24

Sigue por la arista BC, hasta llegar a C, donde

se para y despliega los datos de la Tabla III.

En esta tercera iteración se ha calculado el

valor que corresponde al vértice C(6,6) :

Z=f(6,6)=30.

Se continúa haciendo cálculos a través de la

arista CD, hasta llegar al vértice D. Los datos

que se reflejan son los de la Tabla IV.

Concluye con esta tabla, advirtiendo que ha

terminado (antes ha comprobado que la

solución no mejora al desplazarse por la arista

DE), obsérvese la figura 2.

El valor máximo de la función objetivo es 33,

y corresponde a x = 3 e y = 12 (vértice D).

Figura 2, Interpretación geométrica del método

simplex.

Si se calcula el valor de la función objetivo en

el vértice E(0,14), su valor no supera el valor

33.

Conclusiones

En este trabajo se hizo la descripción del

método simplex, tomando en cuenta las

consideraciones más significativas para su

correcta interpretación y aplicación. Primero

hay que determinar si el sistema de

ecuaciones planteadas tiene solución o no, si

no la tiene no se podrá resolver por este

método. Con el método simplex se resuelven

problemas de programación lineal, en donde

se busca el punto o la trayectoria más optima

en donde convergen las ecuaciones que

describen al problema. Este método se enfoca

solo a problemas de modelos matemáticos

determinísticos, así que no resulta útil para

procesos estocásticos.

Bibliografía

[1] J.L. Urrutia–Galicia, J.C. Alcérreca–

Huerta, M.A. Ordaz–Alcántara,

Programación lineal con espacios covariante

y contravariante. Una perspectiva física y

matemática, Universidad Nacional Autónoma

de México, 2007.

8

[2] Arbonas, M.E. Optimización Industrial (I):

Distribución de los recursos. Colección Productica No. 26.Marcombo S.A, 1989.

[3] Moskowitz,H. y Wright G.P. Investigación

de Operaciones. Prentice_Hall Hispanoamericana S.A. 1991.

[4] M. Chávez de Diego, Diagonalización de

matrices, España, Escuela Técnica Superior

de Ingeniería de Edificación de Sevilla, 2005.

[5] J. L. Gallego Gómez, Apuntes de

Econometría. LADE y LE, 2009, Universidad

de Cantabria, Disponible en la Web:

http://ocw.unican.es/ciencias-sociales-y-

juridicas/econometria/econometria/apuntes/ap

endice1.pdf