Optimización Lineal: Solución de

Problemas por el Método Simplex

Laura Agudelo Vélez - Gustavo Gastelbondo Mercado
Universidad Pontificia Bolivariana. Medellı́n

Abstract
The simplex method, in mathematical optimization, is a well-known algo-
rithm used for linear programming. As per the journal Computing in Science
& Engineering, this method is considered one of the top 10 algorithms that
originated during the twentieth century. The simplex method presents an
organized strategy for evaluating a feasible region’s vertices. This helps to
figure out the optimal value of the objective function. It examines the feasi-
ble set’s adjacent vertices in sequence to ensure that, at every new vertex, the
objective function increases or is unaffected. The method uses a systematic
strategy to generate and test candidate vertex solutions to a linear program.
At every iteration, it chooses the variable that can make the biggest modifi-
cation toward the minimum solution. That variable then replaces one of its
covariables, which is most drastically limiting it, thereby shifting the simplex
method to another part of the solution set and toward the final solution.
Keywords: Programación Lineal, Optimización, Método Simplex

INTRODUCCIÓN
El método Simplex fue desarrollado en 1947 por George Bernard Dantzig
y se basa en la conversión de un problema con restricciones con desigual-
dades en un problema cuyas restricciones son ecuaciones lineales. El método
Simplex permite encontrar los valores óptimos para modelos matemáticos
con muchas restricciones. Ante un problema, las desigualdades establecen
limitaciones que representan a las restricciones de las variables. A partir de
ahı́, se prueban posibilidades con el fin de optimizar el resultado tan pronto
como sea posible.

Preprint submitted to Matemáticas Avanzadas February 28, 2018

 El uso más común del método Simplex es maximizar el resultado, es
decir, encontrar el valor más grande posible para un total. Los problemas
tı́picos para resolver por este método están buscando cantidades óptimas de
productos para ser vendidos, con restricciones en el almacenamiento y la
producción de los mismos.

El método Simplex es un procedimiento iterativo que permite mejorar la

solución de la función objetivo en cada paso. El proceso concluye cuando
no es posible continuar mejorando dicho valor, es decir, se ha alcanzado la
solución óptima (el mayor o menor valor posible, según el caso, para el que
se satisfacen todas las restricciones).

Partiendo del valor de la función objetivo en un punto cualquiera, el proced-

imiento consiste en buscar otro punto que mejore el valor anterior. Como
se verá en el método Gráfico, dichos puntos son los vértices del polı́gono (o
poliedro o polı́coro, si el número de variables es mayor de 2) que constituye
la región determinada por las restricciones a las que se encuentra sujeto el
problema (llamada región factible). La búsqueda se realiza mediante de-
splazamientos por las aristas del polı́gono, desde el vértice actual hasta uno
adyacente que mejore el valor de la función objetivo. Siempre que exista
región factible, como su número de vértices y de aristas es finito, será posible
encontrar la solución.

El método Simplex se basa en la siguiente propiedad: si la funcin objetivo

Z no toma su valor máximo en el vértice A, entonces existe una arista que
parte de A y a lo largo de la cual el valor de Z aumenta.

Será necesario tener en cuenta que el método Simplex únicamente trabaja

con restricciones del problema cuyas inecuaciones sean del tipo ”≤” (menor o
igual) y sus coeficientes independientes sean mayores o iguales a 0. Por tanto,
habrá que estandarizar las restricciones para que cumplan estos requisitos
antes de iniciar el algoritmo del Simplex. En caso que después de éste proceso
aparezcan restricciones del tipo ”≥” (mayor o igual) o ”=” (igualdad), o no se
puedan cambiar, será necesario emplear otros métodos de resolución, siendo
el más común el Método de las Dos Fases.

2
1. ALGORITMO DEL MÉTODO SIMPLEX
1.1. Preparar el Modelo Matemático para adaptarlo al Método
Se debe convertir el modelo matemático a forma estándar es decir, cada
restricción es una igualdad y las restricciones de signo para cada variable son
del tipo mayor o igual que cero (”≥”).
El algoritmo Simplex para resolver modelos de programación lineal re-
quiere que el modelo esté en su forma estándar, por lo cual se convierte el
modelo introduciendo nuevas variables, algunas de las cuales reemplazarán a
las variables originales.

• Para cada restricción del tipo ”≤”, se introduce una nueva variable
de holgura (slack variable) Si que se suma al primer miembro y la
desigualdad se convierte en igualdad; se añade la restricción de signo a
la nueva variable Si ≥ 0.

• Para cada restricción del tipo ”≥” se introduce una nueva variable de
exceso (excess variable) ei que se resta al primer miembro y la desigual-
dad se convierte en igualdad; se añade la restricción de signo a la nueva
variable ei ≥ 0.

• Para cada variable xi que tiene restricción de signo del tipo ≤ 0, se

cambian todas las apariciones de xi en el modelo por la expresión −x0i
donde x0i es una nueva variable con restricción de signo x0i ≥ 0.

• Para cada variable xi que no tiene restricción de signo, se cambian todas

las apariciones de ella en el modelo por la expresión x0i − x00i donde x0i y
x00i son dos nuevas variables con restricción de signo x0i ≥ 0 , x00i ≥ 0.

Las conversión se realiza en dos fases: en la primera se convierten las

desigualdades y en la segunda se aplican las reglas para las variables que en
el modelo original tiene signo no positivo o no tienen restricción de signo
La forma estándar del modelo de problema consta de una Función Objetivo
sujeta a determinadas restricciones:
El modelo debe cumplir las siguientes condiciones:

1. El objetivo consistirá en maximizar o minimizar el valor de la función

objetivo (por ejemplo, incrementar ganancias o reducir pérdidas, re-
spectivamente).

3
 Función Objetivo:
Sujeto a:

2. Todas las restricciones deben ser ecuaciones de igualdad (identidades

matemráticas).
3. Todas las variables (xi ) deben tener valor positivo o nulo (condición de
no negatividad)
4. Los trminos independientes (bi ) de cada ecuacin deben ser no negativos.

1.2. Tipo de Optimización

Como se ha comentado, el objetivo del método consistirá en optimizar el
valor de la función objetivo. Sin embargo se presentan dos opciones: obtener
el valor óptimo mayor (maximizar) u obtener el valor óptimo menor (mini-
mizar).
Además existen diferencias en el algoritmo entre el objetivo de maxi-
mización y el de minimización en cuanto al criterio de condición de parada
para finalizar las iteraciones y a las condiciones de entrada y salida de la
base. Ası́:

• Objetivo de Maximización:
Condición de parada: cuando en la fila Z no aparece ningún valor
negativo.
Condición de entrada a la base: el menor valor negativo en la fila Z
(o el de mayor valor absoluto entre los negativos) indica la variable Pj
que entra a la base.
Condición de salida de la base: una vez obtenida la variable entrante,
la variable que sale se determina mediante el menor cociente P0 /Pj de
los estrictamente positivos.

• Objetivo de Minimización:
Condición de parada: cuando en la fila Z no aparece ningún valor
positivo.

4
 Condición de entrada a la base: el mayor valor positivo en la fila Z
indica la variable Pj que entra a la base.
Condición de salida de la base: una vez obtenida la variable entrante,
la variable que sale se determina mediante el menor cociente P0 /Pj de
los estrictamente negativos.

No obstante, es posible normalizar el objetivo del problema con el fin de

aplicar siempre los mismos criterios en lo referente a la condición de parada
del algoritmo y a las condiciones de entrada y salida de las variables de la
base. De esta forma, si el objetivo es minimizar la solución, se puede cambiar
el problema a otro equivalente de maximización simplemente multiplicando
la funcin objetivo por ”-1”. Es decir, el problema de minimizar Z es equiva-
lente al problema de maximizar (−1) ∗ Z. Una vez obtenida la solución será
necesario multiplicarla tambin por (-1).

Ventajas: No hay que preocuparse por nuevos criterios de parada, condición

de entrada y salida de la base ya que se mantienen.

Inconvenientes: En el caso de que la función tenga todos los coeficientes

de sus variables básicas positivos, y además las restricciones sean del tipo
de desigualdad ”≤”, al hacer el cambio dichos coeficientes quedan nega-
tivos cumpliendose la condición de parada en la primera iteración (en la
fila del valor de la función objetivo todos los valores son positivos o cero).
Obteniéndose en este caso por defecto un valor óptimo para la función igual
a 0.

Solución: Realmente no existe este problema dado que para que la solución
sea superior a 0 es necesario que alguna restricción tenga impuesta la condicin
”≥” (y se tratarı́a de un modelo para el método de las Dos Fases). En el
caso planteado, la solución real debe ser cero.

1.3. Cambio de signo de los términos independientes

También se ha dicho que los términos independientes (bi ) de cada ecuación
deben ser no negativos para poder emplear el método Simplex. A tal fin, si
alguna de las restricciones presenta un término independiente menor que 0
habrá que multiplicar por ”-1” ambos lados de la inecuación (teniendo en
cuenta que esta operación también afecta al tipo de restricción).

5
 Ventajas: Con ésta simple modificación de signos en las restricciones
correspondientes se posibilita la aplicación del método Simplex al problema
modelado.
Inconvenientes: Puede resultar que en las restricciones donde tengamos
que modificar los signos de las constantes, los tipos de desigualdad fueran
”≤” (quedando tras la operación del tipo ”≥”) siendo necesario desarrollar el
método de las Dos Fases. Este inconveniente no es controlable, aunque podrı́a
ocurrir el caso contrario y resultar beneficioso si los términos independientes
negativos se presentan en todas aquellas restricciones con desigualdad de tipo
”≥”. Si existe alguna restricción del tipo ”=” no supondrı́a ninguna ventaja
ni desventaja puesto que siempre serı́a de necesaria aplicación el método de
las Dos Fases.

1.4. Normalización de Restricciones

Otra de las condiciones del modelo estándar del problema es que todas
las restricciones sean ecuaciones de igualdad (también llamadas restricciones
de igualdad), por lo que hay que convertir las restricciones de desigualdad o
inecuaciones en dichas identidades matemáticas.
La condición de no negatividad de las variables (x1 ,...,xn ≥0) es la nica
excepción y se mantiene tal cual.

Restricción de tipo ”≤”

Para normalizar una restricción con una desigualdad del tipo ”≤”, hay
que añ adir una nueva variable, llamada variable de holgura xs (con la
condición de no negatividad: xs ≥ 0). Esta nueva variable aparece con coefi-
ciente cero en la función objetivo, y sumando en la ecuación correspondiente
(que ahora sı́ será una identidad matemática o ecuación de igualdad).

a11 x1 + a12 x2 ≤ b1 → a11 x1 + a12 x2 + 1xs = b1

Restricción de tipo ”≥”

En caso de una desigualdad del tipo ”≥”, también hay que añ adir una
nueva variable llamada variable de exceso xs (con la condición de no neg-
atividad: xs ≥ 0). Esta nueva variable aparece con coeficiente cero en la
función objetivo, y restando en la ecuacón correspondiente.
Surge ahora un problema con la condición de no negatividad con esta
nueva variable del problema. Las inecuaciones que contengan una desigual-
dad de tipo ”≥” quedan:

6
 a11 x1 + a12 x2 ≥ b1 → a11 x1 + a12 x2 -1xs = b1

Al realizar la primera iteración con el método Simplex, las variables básicas

no estarán en la base y toman valor cero. En este caso la nueva variable xs ,
tras hacer cero a x1 y x2 , toma el valor −b1 y no cumpliı́a la condición de
no negatividad. Es necesario aãdir otra nueva variable xr , llamada variable
artificial, que también aparece con coeficiente cero en la función objetivo y
sumando en la restricción correspondiente. Quedando entonces de la sigu-
iente manera:
a11 x1 + a12 x2 ≥ b1 → a11 x1 + a12 x2 -1xs +1xr = b1

Restricción de tipo ”=”

Para las restricciones de tipo ”=” (aunque ya son identidades) también es
necesario agregar variables artificiales xr . Como en el caso anterior, su coefi-
ciente será cero en la función objetivo y aparecerá sumando en la restricción
correspondiente.

a11 x1 + a12 x2 = b1 → a11 x1 + a12 x2 +1xr = b1

En el último caso se hace patente que las variables artificiales suponen una
violación de las leyes del álgebra, por lo que es necesario asegurar que dichas
variables artificiales tengan un valor 0 en la solución final. De esto se en-
carga el método de las Dos Fases y por ello siempre que aparezcan este tipo
de variables habrá que realizarlo.

1.5. Obtener una Solución Básica Factible (SBF)

Una solución básica (SB) a un sistema de ecuaciones Ax = b con m
ecuaciones y con n incógnitas, es decir m × n, (n ≥ m) es una solución
al sistema que se obtiene haciendo cero n−m variables y que resulta en un
sistema con solució única. A una variable de decisión que deliberadamente
se hace cero se le llama variables no básica (VNB) y mientras que a aquella
que se conserva dentro del nuevo sistema se le llama variable básica (VB).

En términos de Algebra Lineal, este concepto equivale a seleccionar m colum-

nas de A y que éstas formen una base para Rm . Las columnas no selec-
cionadas corresponden a aquellas variables que se hacen cero deliberada-
mente. Una vez seleccionadas las columnas el nuevo sistema con el mismo

7
vector de constantes debe resolverse. La solución obtenida se llama solución
básica.

En términos de matrices, tiene el significado que las variables que no se hacen

cero deliberadamente forman una matriz invertible. El proceso para obtener
una solución factible corresponde a tomar de A columnas para formar una
matriz cuadrada que resulte invertible.

Una solución básica Factible (SBF) a un sistema de ecuaciones Ax = b con

m ecuaciones y con n incógnitas, es decir m × n, (n ≥ m) es una solución
básica con valores no negativos para las variables de decisión. Para un modelo
de Programacin Lineal con m restricciones, dos soluciones básica factibles se
dicen ser soluciones básica factibles adyacentes si acaso tienen m−1 variables
básicas en común.

1.6. Determinar si la Solución Básica Factible (SBF) es Óptima

Si hay una variable no básica cuyo aumento hace que el valor actual de
la función a maximizar suba, entonces la solución actual no es óptima. Si
la SBF no esóoptima, se debe determinar la variable no básica que deberı́a
convertirse en básica (la de mayor impacto en la función objetivo) y cual
variable básica deberı́a convertirse en una no básica (la que impone una
restricción mayor a la variable de mayor impacto).

Con la selección anterior y usando operaciones elementales de renglón de-

terminar una SBF nueva adyacente a la anterior. posteriormente, se debe
verificar que la nueva SBF calculada sea óptima.

Una vez estandarizado el modelo puede ocurrir que sea necesario aplicar el
método Simplex o el método de las Dos Fases. Véase en la Figura 1 la forma
de actuación para llegar a la solución del problema modelado.

8
 Figure 1: Diagrama de Flujo Aplicación del Método

2. DESARROLLO DEL MÉTODO SIMPLEX

Las columnas de la tabla están dispuestas de la siguiente forma: la
primera columna de la tabla contiene las variables que se encuentran en
la base (o variables básicas), esto es, aquellas que toman valor para propor-
cionar una solución; la segunda columna recoge los coeficientes que dichas
variables básicas tienen en la función objetivo (esta columna es llamada Cb );
la tercera muestra el término independiente de cada restriccin (P0 ); a partir
de ésta, aparece una columna por cada una de las variables de decisión y
holgura presentes en la función objetivo (Pj ).

Sobre esta tabla se agregan dos nuevas filas: una de ellas, que lidera la tabla,
donde aparecen los coeficientes de las variables de la función objetivo, y una

9
última fila que recoge el valor la función objetivo y los costes reducidos Zj −
Cj .
Se muestra a continuación el aspecto general de la tabla del método Sim-
plex

Figure 2: Tabla método Simplex

Condición de parada: Se cumple la condición de parada cuando la

fila indicadora no contiene ningún valor negativo entre los costes reducidos
(cuando el objetivo es la maximización), esto es, no existe posibilidad de
mejora.
Una vez cumplida la condición de parada, el valor de cada variable que
logra la solución óptima se encuentra en la columna P0 , indicándose en la
base a qué variable corresponde dicho valor. Si una variable no aparece en
la base, significa que su valor es cero. De la misma forma el valor óptimo de
la función objetivo (Z) se encuentra en la columna P0 , fila Z.

Si no se cumple la condición de parada es necesario realizar una iteración

más del algoritmo, esto es, determinar la variable que se vuelve básica y la
que deja de serlo, encontrar el elemento pivote, actualizar los valores de la
tabla y comprobar si se cumple nuevamente la condición de parada.

Es también posible determinar que el problema no se encuentra acotado y su

solución siempre resultará mejorable. En tal caso no es necesario continuar
iterando indefinidamente y se puede finalizar el algoritmo. Esta situación
ocurre cuando en la columna de la variable entrante a la base, todos los
valores son negativos o nulos.

10
 Elección de la variable que entra a la base: Cuando una variable
se vuelve bésica, es decir, entra en la base, comienza a formar parte de la
solución. Observando los costes reducidos en la fila Z, se decide que entra a
la base la variable de la columna en la que éste sea el de menor valor (o de
mayor valor absoluto) entre los negativos.

Elección de la variable que sale de la base: Una vez obtenida la

variable entrante, se determina que sale de la base la variable que se en-
cuentre en aquella fila cuyo cociente P0 /Pj sea el menor de los estrictamente
positivos (teniendo en cuenta que esta operación se hará únicamente cuando
Pj sea superior a 0).

Elemento pivote: El elemento pivote de la tabla queda marcado por la

intersección entre la columna de la variable entrante y la fila de la variable
saliente.

Actualización de la tabla: Las filas correspondientes a la función ob-

jetivo y a los tı́tulos permanecerán inalteradas en la nueva tabla. El resto de
valores deberán calcularse como se explica a continuación:

• En la fila del elemento pivote cada nuevo elemento se calcula como:

Nuevo Elemento Fila Pivote = Anterior Elemento Fila Pivote/Pivote

• En el resto de las filas cada elemento se calcula:

Nuevo Elemento Fila=

Anterior Elemento Fila-(Anterior Elemento Fila en Columna Pivote * Nuevo Elemento Fila Pivote)

De esta forma se consigue que todos los elementos de la columna de la

variable entrante sean nulos salvo el de la fila de la variable saliente cuyo
valor será 1. (Es análogo a utilizar el método de Gauss-Jordan para resolver
sistemas de ecuaciones lineales).

3. EJEMPLO MATEMÁTICO
El método Simplex es un procedimiento algebraico, sin embargo, sus con-
ceptos fundamentales son geométricos, por lo que la comprensión de estos
conceptos geométricos nos proporciona una fuerte intuición sobre cómo opera

11
el método Simplex y por qué es tan eficiente. Para comprender los conceptos
geométricos, se analiza el siguiente ejemplo.

Una empresa produce artı́culos de vidrio de alta calidad, entre ellos ventas y
puertas de vidrio. Para su produccin utilizan 3 plantas para sus respectivos
procesos. Los productos fabricados son:

Producto 1: Una puerta de vidrio de 8 pies con marco de aluminio.

Producto 2: Una ventana de marco de madera de 4 por 6 pies.

El producto 1 requiere parte de la capacidad de producción en las plantas

1 y 3 y nada en la planta 2. El producto 2 sólo necesita trabajo en las
plantas 2 y 3. Como se menciona, ambos productos competirı́an por la
misma capacidad de producción en la planta 3, por tanto, no está claro cuál
mezcla de productos serı́a la más rentable. Los Datos de entrada para la
solución del problema se observan en la Figura 3

Figure 3: Datos de entrada del problema

3.1. Solución desde el Punto de vista geométrico

La definición del problema indica que las decisiones que deben tomarse
son el número de lotes de los productos que se fabricarán semanalmente, de
manera que se maximice su ganancia total. Para formular matemáticamente
el problema de programación lineal, se define:

x1 = Nmero de lotes del producto 1 que se fabrican por semana.

x2 = Nmero de lotes del producto 2 que se fabrican por semana.
Z=Ganancia semanal total (en miles de dlares) que generan ambos pro-
ductos

12
Por lo tanto, x1 y x2 son las variables de decisión del modelo. El objetivo
es elegir los valores de x1 y x2 que maximicen Z = 3x1 + 5x2 sujeta a las
restricciones impuestas sobre sus valores por las capacidades de producción
limitadas en las tres plantas. La Figura 3 indica que cada lote del producto
1 que se produce por semana, emplea una hora de producción en la planta
1, y sólo se disponen de 4 horas semanales. En términos matemáticos, esta
restricción se expresa mediante la desigualdad x1 ≤4. De igual manera, la
planta 2 impone la restricción 2x2 ≤12. Y ası́ mismo, la restricción para la
planta 3 es 3x1 + 2x2 ≤18. Por último, como las tasas de producción no
pueden ser negativas, es necesario restringir las variables de decisión a val-
ores no negativos: x1 ≥0 y x2 ≥0.

Para resumir los anterior, el problema consiste en seleccionar los valores

x1 y x2 para maximizar
Z = 3x1 + 5x2 (1)
Sujeta a las Restricciones
x1 ≤ 4 (2)
2x1 ≤ 12 (3)
3x1 + 2x2 ≤ 18 (4)
En la Figura 4, se muestra la región de valores permisibles de x1 ,x2 ,
llamada región factible, y el objetivo es encontrar dentro de esta región el
punto que maximiza el valor de Z.

Igualmente se marcaron las cinco restricciones de frontera y sus puntos de

intersección ya que son puntos clave para el análisis. Una frontera de re-
stricción es una recta que marca el lı́mite de lo que permite la restricción
correspondiente. Los puntos de intersección son las soluciones en los vértices
para el problema. Los cinco puntos que se encuentran en los vértices de la
región factible son: (0,0), (0,6), (2,6), (4,3) y (4,0), y corresponden a las
soluciones factibles en los vértices. Los demás: (0,9), (4,6) y (6,0) se llaman
soluciones no factibles en un vértice.

En cualquier problema de programación lineal con n variables de decisión,

dos soluciones Factibles son adyacentes entre sı́ cuando comparten n−1 fron-
teras de restricción. Dos soluciones factibles adyacentes están conectadas

13
 Figure 4: Restricciones de frontera y soluciones en los vrtices del problema.

por un segmento de recta que se encuentra en estas mismas fronteras de re-

stricción compartidas. Dicho segmento de recta recibe el nombre de arista
de la región factible.

Como en el ejemplo n=2 (hay dos variables de decisión), dos de sus soluciones
factibles son adyacentes si comparten una frontera de restricción; por ejemplo
(0,0) y (0,6) son adyacentes porque comparten la frontera x1 =0.

En la Tabla 1 se indican las soluciones factibles adyacentes para cada solución

factible.

Sln Factible Slns Adyacentes

(0,6) (2,6) y (0,0)
(2,6) (4,3) y (0,6)
(4,3) (4,0) y (2,6)
(4,0) (0,0) y (4,3)
Table 1: Soluciones factibles adyacentes para cada solución factible del problema

14
 Después de haber obtenido la Tabla 1 , se resuelve el problema utilizando
el método Simplex desde el punto de vista geométrico de la siguiente manera:
• Paso inicial: Elija (0,0) como solución Factible inicial para exami-
narla.
• Prueba de optimalidad: concluya que (0,0) no es una solución
óptima, dado que las soluciones factibles adyacentes son mejores.
• Iteración 1: Moverse a una solución Factible adyacente mejor, (0,6),
realizando los siguientes pasos:
1. De las dos aristas que salen de (0,0), elija moverse a lo largo de la
arista que aumenta el valor de x2 . (Con una función objetivo Z
= 3x1 + 5x2 , al aumentar el valor de x2 , el valor de Z crece más
rápido que si se aumenta el valor de x1 ).
2. Detenerse al llegar a la primera frontera de restricción: 2x2 =12.
Al moverse más lejos en esa dirección, saldrá de la región factible.
3. Obtenga la intersección del nuevo conjunto de fronteras de re-
stricción: (0,6)
• Prueba de optimalidad: Concluya que (0,6) no es una solución
óptima. (existe una solución factible adyacente mejor.
• Iteración 2: Moverse a una mejor solución Factible (2,6), realizando
los siguientes pasos:
1. De las dos aristas que salen de (0,6), elija moverse a la derecha.(Moverse
a lo largo de esta arista aumenta el valor de Z).
2. Detenerse al encontrar a la primera frontera de restricción en esa
dirección: 3x1 + 2x2 ≤ 18.
3. Obtenga la intersección del nuevo conjunto de fronteras de re-
stricción: (2,6)
• Prueba de optimalidad: Concluir que (2,6) es una solución óptima
y detenerse. (ninguna de las soluciones factibles adyacentes es mejor).
En la Figura 5 se muestra la secuencia de soluciones factibles examinadas
por el método Simplex para el problema realizado.
Como pudo apreciarse en el ejemplo, el método Simplex es un algoritmo
iterativo, es decir, un procedimiento de solución sistemático que repite una
serie de pasos fijos, hasta que se obtiene el resultado deseado, con la estruc-
tura mostrada en la Figura 6.

15
 Figure 5: Secuencia de soluciones factibles examinadas por el Método Simplex

3.2. Solución desde el Punto de vista algebraico o tabular

En la solución anterior se hizo énfasis en los conceptos geométricos funda-
mentales del método Simplex. Sin embargo, lo común es que este algoritmo
se trabaje en una computadora que sólo puede seguir instrucciones alge-
braicas. Por lo tanto, es necesario transformar el procedimiento geométrico
conceptual que se acaba de describir, en un procedimiento algebraico que se
pueda usar. 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. Esta conversión se logra mediante la introduccin de
variables de holgura.

Por ejemplo, para la primera restricción x1 ≤4, la variable de holgura se

define como: x3 =4−x1 , que es la holgura que queda en el lado izquierdo de
la desigualdad. Entonces x1 +x3 =4, con x3 ≥0.
Al introducir variables de holgura en las otras restricciones funcionales,

16
 Figure 6: Secuencia de iteración Método Simplex

el modelo de programación lineal original de este ejemplo se puede sustituir

por el modelo equivalente (llamado forma aumentada del modelo), como se
observa en la Figura 7:

Figure 7: Forma original vs Forma algebraica

Aun cuando ambas formas del modelo representan exactamente el mismo

problema, la nueva forma es mucho más conveniente para la manipulación
algebraica y la identificación de las soluciones Factibles. Se le da el nombre
de forma aumentada del problema, porque la forma original se aumentó con
algunas variables suplementarias necesarias para aplicar el método Simplex.

Una solución básica tiene las siguientes propiedades:

• Cada variable se designa ya sea como variable básica o variable no
básica.

17
 • El número de variables básicas es igual al número de restricciones fun-
cionales. Por lo tanto, el número de variables no básicas es igual al
número total de variables menos el número de restricciones funcionales.

• Las variables no básicas se igualan a cero.

• Los valores de las variables básicas se obtienen como la solución simul-

tanea del sistema de ecuaciones.

• Si las variables básicas satisfacen las restricciones de no negatividad, la

solución básica es una solucin factible.

El método algebraico se puede desarrollar con las ecuaciones de la forma

aumentada del modelo, mostradas en la Figura 8, pero por facilidad se hará
de forma tabular, ya que reduce un poco los cálculos.

Figure 8: Tabla Simplex inicial del problema

RESUMEN DEL MÉTODO

Paso inicial: Se introducen las variables de holgura. Se seleccionan las
variables de decisión como las variables no básicas iniciales, (iguales a cero)
y las variables de holgura como las básicas iniciales. Esta elección lleva a la
Figura 8, donde la solucin básicas factible es (0,0,4,12,18).

Prueba de optimalidad: La solución Básica factible es óptima si y sólo

si todos los coeficientes en el renglón (0) son no negativos (≥0). Si es asi
el proceso se detiene, de otra manera sigue a una iteración para obtener la
siguiente solucin básica factible, que incluye cambiar una variable no básica
en básica (paso 1), y viceversa (paso 2) y después despejar la nueva solución
(paso 3).

18
 Iteración 1:
Paso 1: se determina la variable básica entrante, seleccionando la vari-
able con el coeficiente negativo que tiene el mayor valor absoluto en la ecuacin
(0). Se pone un recuadro alrededor de la columna debajo de este coeficiente y
se le da el nombre de columna pivote. En la tabla, el coeficiente más negativo
es 5, de manera que x2 debe convertirse en variable básica.
Paso 2: Se determina la variable básica que sale con la prueba del co-
ciente mı́nimo. Elegir los coeficientes de la columna pivote que son estricta-
mente positivos. Dividir cada coeficiente entre el elemento del lado derecho en
el mismo renglón. Identificar el renglón que tiene el menor de estas razones.
La variable básica en ese renglón es la variable básica que sale, entonces se
debe sustituir por la variable básica entrante en la columna de la variable
básica de la Figura 9.

Figure 9: Prueba del cociente mı́nimo para determinar la primera variable básica saliente.

Luego poner un recuadro en este renglón que se llama renglón pivote.

El número que se encuentra entre los recuadros se llama número pivote. La
variable básica que sale es x4 , y x2 se sustituye en el renglón 2, como se indica
en la Figura 10.
Paso 3: Se despeja la nueva solución básica factible mediante operaciones
algebraicas elementales con renglones, para construir una nueva tabla en la
forma apropiada de eliminación gaussiana, abajo de la actual y después se
realiza la prueba de optimalidad. Las operaciones elementales con renglones
que deben realizarse son:
• Dividir el renglón pivote entre el número pivote. Usar este nuevo
renglón pivote en los pasos 2 y 3.
• Para los renglones (incluso el renglón 0), que tienen un coeficiente neg-
ativo en la columna pivote, se suma a este renglón el producto del valor

19
Figure 10: Tabla Simplex después de dividir el primer renglón pivote entre el primer
número pivote.

absoluto de este coeficiente por el nuevo renglón pivote.

• Para los renglones que tienen un coeficiente positivo en la columna

pivote, se resta de este renglón el producto de este coeficiente por el
nuevo renglón pivote

En el ejemplo, debido a que x2 sustituye a x4 como variable básica, se necesita

reproducir el patrón de la primera tabla de coeficientes de la columna de x4
(0,0,1,0) en la columna de x2 en la segunda tabla Simplex. Para comenzar,
se divide el renglón pivote (renglón 2) entre el número pivote (2), lo que da el
nuevo renglón 2 mostrado en la Figura 10. Despus se suma al renglón (0) el
nuevo renglón (2) multiplicado por 5. Luego se resta del renglón (3) el nuevo
renglón (2) multiplicado por 2. Estos cálculos se muestran en la Figura 11.

Figure 11: Primeras dos tablas Simplex del problema.

20
Ası́, la nueva solución básica factible es (0,6,4,0,6), con Z=30.
Prueba de optimalidad: Se debe verificar si la nueva solución básica
factible es óptima. Como el nuevo renglón (0) todavı́a tiene un coeficiente
negativo (-3) para x2 , la solución no es óptima y se necesita por lo menos
una iteración más.
Iteración 2: Se siguen las instrucciones de los pasos 1 y 2, se encuentra
que x1 es la variable básica entrante y x5 es la que sale, como se observa en
la Figura 12, que tiene el cociente mı́nimo.

Figure 12: Pasos 1 y 2 de la iteración 2

Por otro lado se tiene que:

Figure 13: Pasos 1 y 2 de la iteración 2

21
 Para el paso 3, se divide el renglón pivote (renglón 3) entre el número
pivote 3. Después, se suma al renglón (0) el nuevo renglón 3 multiplicado
por 3. Luego, se resta el nuevo renglón 3 del renglón 1. En la Figura 13 se
tiene ahora la nueva tabla Simplex.

La nueva solución básica factible es (2,6,2,0,0) con Z=36. Al hacer la prueba

de optimalidad se encuentra que la solución es óptima, porque no hay coefi-
cientes negativos en el renglón (0). En consecuencia, la solución óptima del
problema es x1 =2 y x2 =6, igual que al método gráfico.

4. APLICACIÓN EN INGENIERÍA DEL MÉTODO SIMPLEX

Planeamiento para la expansin de un Sistema de Potencia
Se tiene un Sistema Eléctrico de Potencia compuesto por Subestaciones y
lı́neas de transmisión, en el cual se debe llevar un flujo de potencia desde nodo
de origen (Nodo de Generación) a un nodo final (Demanda de carga). En el
nodo de origen se deben evaluar todas las alternativas para visitar los demás
nodos una sola vez. Se asume que existen lı́neas entre cada subestación y
cada uno de los demás nodos y que la longitud de las lı́neas entre dos nodos
es diferente en las dos direcciones. Se debe determinar Cuál lı́nea es mejor
para la transferencia de potencia, considerando la menor distancia.

Para representar matemáticamente el problema, se define un único conjunto

de subestaciones (también denominadas nodos) V ={1,2,3,. . . ,n}, donde n
es el número de subestaciones. Se define A como el conjunto de lı́neas de
transmisión que unen cada par de subestaciones con elementos (i,j) ∈ A. Al
conjunto de lı́neas se le asocia el vector Cij , cuyos elementos representan la
distancia de cada lı́nea; de acuerdo a esto, el esfuerzo necesario para ir de la
Subestación i a la subestación j, Cij , no necesariamente es igual a Cji . El
modelo matemático es el siguiente:
Se representan las variables de decisión como xij , donde:

Figure 14: Representación del camino i−j

22
 Si existe camino entre cada par de subestaciones, se puede definir el con-
junto de variables de decisión:

Para este problema, se tienen los siguientes tipos de restricciones:

1. A cada subestación se llega desde una única subestación anterior. Esto
porque cada nodo se visita una sola vez.

2. Desde la subestación i se puede pasar a una única subestación j. Hay

un único camino de salida

3. Las restricciones dadas no consiguen evitar lazos aislados como solu-

ciones posibles; Por lo tanto, se deben incorporar restricciones que
eviten subtours (potencia encerrada en un lazo). Por lo tanto, se deben
incorporar restricciones que eviten subtours. Observe que un subtour
puede existir solamente si se cumplen las siguientes dos condiciones:

23
 • Existen subconjuntos U de subestaciones que contienen entre 2 o
el número total menos 2 subestaciones, es decir, existe U ⊆ V con
la condicón: 2≤|U |≤|V |−2
• No existen conexiones entre el subconjunto de subestaciones U y
el subconjunto de ciudades {V − U }, es decir

4.1. Ejemplo de Aplicación con 6 Subestaciones n=6

• Este problema tiene n(n−1) variables de decisión. Para n=6 nodos, se
tienen 30 variables.

• El problema tiene (2n −2)restricciones, para este caso 62 restricciones.

Existen n=6 restricciones tipo 1, n=6 restricciones tipo 2 y 50 restric-
ciones tipo 3.De estas últimas, existen 15 restricciones encontradas con
|U |=2, 20 restricciones encontradas con |U |=3 y 15 restricciones con
|U |=4,

Figure 15: Variables de decisón del Problema

Figure 16: Restricciones asociadas a que sólo debe estar activa una lı́nea de llegada a cada
nodo

24
Figure 17: Restricciones asociadas a que sólo debe estar activa una lı́nea de salida a cada
nodo

Figure 18: Restricciones asociadas a |U |=2

25
 Figure 19: Restricciones asociadas a |U |=3

Figure 20: Restricciones asociadas a |U |=4

Con todas las restricciones presentadas anteriormente, el problema tiene

el siguiente modelo matemático con n=6 nodos

26
5. CONCLUSIONES
• El método Simplex es un algoritmo eficiente y confiable para resolver
problemas de programación Lineal sin restricciones. Aunque tiene una
interpretación geométrica útil, el método Simplex es un procedimiento
algebraico, que por medio de cada iteración trata de buscar una solución
óptima, por medio de la eliminación de Gauss para resolver el sistema
de ecuaciones lineales.

• Este método es una manera fácil, práctica y rápida de dar soluciones

óptimas en los diferentes campos laborales a todos los problemas es-
tablecidos o surgidos en el desarrollo de la industria siendo satisfac-
torio y eficaz en las respuestas, permitiendo establecer y generar una
producción y los diferentes procesos en un alto nivel de efectividad
y logrando un ahorro significativo económico en el desarrollo de una
empresa.

27