Método Simplex

Resumen de la unidad 2

En este documento se describen: el método

simplex, el método de las dos fases, el método
de las “M” y el método simplex revisado.

Ing. Lorenie Izet Moreno Fuentes

José Leonardo Saucedo García 07380654

21 de mayo de 2010

1
 INDICE

2 METODO SIMPLEX
2.1 Teoría del Método Simplex………………………………………………… 3
2.2 Forma Tabular del Método Simplex………………………………………. 4
2.3 Problemas de programación lineal que requieren la introducción de
variables artificiales……………………………………………………………... 6
2.3.1 Método de las “M” y método de las dos fases…………………... 11
2.4 El método simplex revisado………………………………………………... 13
Conclusiones…………………………………………………………………………….. 15
Bibliografía……………………………………………………………………………… 16

2
 2.1 TEORÍA DEL MÉTODO SIMPLEX

Es un método genérico de solución de problemas lineales, desarrollado por George Dantzig

en 1947

La mayoría de los problemas reales de programación lineal tienen más de dos variables, por
lo tanto, demasiado grande para una solución gráfica, el método simplex puede ser utilizado
para encontrar la solución óptima de los problemas con multivariables. El método simplex
es un conjunto de instrucciones con las cuales se examinan los puntos en las esquinas de
una forma metódica hasta conseguir la mejor solución; la mayor utilidad o el menor costo.

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.

El método consiste en partir de un vértice del conjunto de soluciones o solución inicial y

determinar si es óptima. Si no lo es, se pasa a partir de él a otro vértice adyacente, por un
criterio semejante al del gradiente, en el que mejore el valor de la función objetivo o
función económica, repitiéndose esta operación hasta que no sea posible mejorar la función
objetivo, en cuyo caso ya se ha alcanzado el óptimo.

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.

Deberá tenerse en cuenta que este método sólo trabaja para restricciones que tengan un tipo
de desigualdad "≤" y coeficientes independientes mayores o iguales a 0, y habrá que
estandarizar las mismas para el algoritmo. En caso de que después de éste proceso,
aparezcan restricciones del tipo "≥" o "=" habrá que emplear otros métodos, siendo el más
común el método de las Dos Fases.

Preparando El Modelo Para Adaptarlo Al Método Simplex

Esta es la forma estándar del modelo:
Función objetivo: c1·x1 + c2·x2 + ... + cn·xn
Sujeto a: a11·x1 + a12·x2 + ... + a1n·xn = b1
a21·x1 + a22·x2 + ... + a2n·xn = b2
...
am1·x1 + am2·x2 + ... + amn·xn = bm
x1,..., xn ≥ 0
Para ello se deben cumplir las siguientes condiciones:
1. El objetivo es de la forma de maximización o de minimización.
2. Todas las restricciones son de igualdad.
3. Todas las variables son no negativas.
4. Las constantes a la derecha de las restricciones son no negativas.

2
 2.2 FORMA TABULAR DEL MÉTODO SIMPLEX
La forma tabular del método simplex registra:
1. Los coeficientes de las variables.
2. Las constantes del lado derecho de las ecuaciones.
3. La variable básica que aparece en cada ecuación

- Construcción de la primera tabla: En la primera columna de la tabla aparecerá lo que

llamaremos base, en la segunda el coeficiente que tiene en la función objetivo cada variable
que aparece en la base (Cb), en la tercera el término independiente de cada restricción (P 0),
y a partir de ésta columna aparecerán cada una de las variables de la función objetivo (Pi).
Para tener una visión más clara de la tabla, incluiremos una fila en la que pondremos cada
uno de los nombres de las columnas. Sobre ésta tabla que tenemos incluiremos dos nuevas
filas: una que será la que liderará la tabla donde aparecerán las constantes de los
coeficientes de la función objetivo, y otra que será la última fila, donde tomará valor la
función objetivo. Nuestra tabla final tendrá tantas filas como restricciones.

Tabla
C1 C2 ... Cn
Base Cb P0 P1 P2 ... Pn
Pi1 Ci1 bi1 a11 a12 ... a1n
Pi2 Ci2 bi2 a21 a22 ... a2n
... ... ... ... ... ... ...
Pim Cim bim am1 am2 ... amn
Z Z0 Z1-C1 Z2-C2 ... Zn-Cn

Los valores de la fila Z se obtienen de la siguiente forma: El valor Z0 será el de sustituir Cim
en la función objetivo (y cero si no aparece en la base). El resto de columnas se obtiene
restando a este valor el del coeficiente que aparece en la primera fila de la tabla.
Se observará al realizar el método Simplex, que en esta primera tabla, en la base estarán las
variables de holgura.
- Condición de parada: Comprobaremos si debemos de dar una nueva iteración o no, que lo
sabremos si en la fila Z aparece algún valor negativo. Si no aparece ninguno, es que hemos
llegado a la solución óptima del problema.
- Elección de la variable que entra: Si no se ha dado la condición de parada, debemos
seleccionar una variable para que entre en la base en la siguiente tabla. Para ello nos
fijamos en los valores estrictamente negativos de la fila Z, y el menor de ellos será el que
nos de la variable entrante.
- Elección de la variable que sale: Una vez obtenida la variable entrante, obtendremos la
variable que sale, sin más que seleccionar aquella fila cuyo cociente P 0/Pj sea el menor de
los estrictamente positivos (teniendo en cuenta que sólo se hará cuando Pj sea mayor de 0).

2
La intersección entre la columna entrante y la fila saliente nos determinará el elemento
pivote.
- Actualización de la tabla: Las filas correspondientes a la función objetivo y a los títulos
permanecerán inalterados en la nueva tabla. El resto deberá calcularse de dos formas
diferentes:
• Si es la fila pivote cada nuevo elemento se calculará:

Nuevo Elemento Fila Pivote = Elemento Fila Pivote actual / Pivote.

• Para el resto de elementos de filas se calculará:

Nuevo Elemento Fila = Elemento Fila Pivote actual - (Elemento Columna Pivote
en la fila actual * Nuevo Elemento Fila).

2
 2.3 PROBLEMAS DE PROGRAMACIÓN LINEAL QUE
REQUIEREN LA INTRODUCCIÓN DE VARIABLES
ARTIFICIALES

Resolver mediante el método simplex el siguiente problema:

Z = f(x,y) = 3x +
Maximizar
2y
sujeto a: 2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24
x≥0,y≥0

Se consideran las siguientes fases:

1. Convertir las desigualdades en igualdades

Se introduce una variable de holgura por cada una de las restricciones del tipo ≤, para
convertirlas en igualdades, resultando el sistema de ecuaciones lineales:

2x + y + r = 18
2x + 3y + s =
42
3x +y + t = 24

2. Igualar la función objetivo a cero

- 3x - 2y + Z = 0

3. Escribir la tabla inicial simplex

En las columnas aparecerán todas las variables básicas del problema y las variables de
holgura/exceso. En las filas se observan, para cada restricción las variables de holgura con
sus coeficientes de las igualdades obtenidas, y la última fila con los valores resultantes de
sustituir el valor de cada variable en la función objetivo, y de operar tal como se explicó en
la teoría para obtener el resto de valores de la fila:

Tabla I. Iteración nº 1
3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P3 0 18 2 1 1 0 0

2
P4 0 42 2 3 0 1 0
P5 0 24 3 1 0 0 1
Z 0 -3 -2 0 0 0

4. Condición de parada

Cuando en la fila Z no existe ningún valor negativo, se ha alcanzado la solución óptima del
problema. En tal caso, se ha llegado al final del algoritmo. De no ser así, se ejecutan los
siguientes pasos.

5. Condición de entrada y salida de la base

A. Primero debemos saber la variable que entra en la base. Para ello escogemos la
columna de aquel valor que en la fila Z sea el menor de los negativos. En este caso
sería la variable x (P1) de coeficiente - 3.

Si existiesen dos o más coeficientes iguales que cumplan la condición anterior

(caso de empate), entonces se optará por aquella variable que sea básica.

La columna de la variable que entra en la base se llama columna pivote (En color
verde).

B. Una vez obtenida la variable que entra en la base, estamos en condiciones de

deducir cual será la variable que sale. Para ello se divide cada término
independiente (P0) entre el elemento correspondiente de la columna pivote, siempre
que el resultado sea mayor que cero, y se escoge el mínimo de ellos.

En nuestro caso: 18/2 [=9], 42/2 [=21] y 24/3 [=8]

Si hubiera algún elemento menor o igual a cero no se realiza dicho cociente, y caso
de que todos los elementos de la columna pivote fueran de ésta condición
tendríamos una solución no acotada y terminaríamos el problema.

El término de la columna pivote que en la división anterior dé lugar al menor

cociente positivo, el 3, ya que 8 es el menor cociente, indica la fila de la variable de
holgura que sale de la base, t (P5). Esta fila se llama fila pivote (En color verde).

Si al calcular los cocientes, dos o más son iguales (caso de empate), se escoge
aquella que no sea variable básica (si es posible).

C. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote, 3.

6. Encontrar los coeficientes de la nueva tabla.

2
Los nuevos coeficientes de la fila pivote, t (P5), se obtienen dividiendo todos los
coeficientes de dicha fila entre el elemento pivote, 3, que es el que hay que convertir en 1.

A continuación mediante la reducción gaussiana hacemos ceros los restantes términos de su

columna, con lo que obtenemos los nuevos coeficientes de las otras filas incluyendo los de
la función objetivo Z.

También se puede hacer de la siguiente manera:

Fila del pivote:

Nueva fila del pivote = (Vieja fila del pivote) / (Pivote)

Resto de las filas:

Nueva fila = (Vieja fila) -(Coeficiente de la vieja fila en la columna de la variable

entrante) x (Nueva fila del pivote)

Veámoslo con un ejemplo una vez calculada la fila del pivote (fila de x (P1) en la Tabla II):

Vieja fila de P4 42 2 3 0 1 0
Menos - - - - - -
Coeficiente 2 2 2 2 2 2
Por x x x x x x
Nueva fila pivote 8 1 1/3 0 0 1/3
= = = = = =
Nueva fila de P4 26 0 7/3 0 1 -2/3

Tabla II. Iteración nº 2

3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P3 0 2 0 1/3 1 0 -2/3
P4 0 26 0 7/3 0 1 -2/3
P1 3 8 1 1/3 0 0 1/3
Z 24 0 -1 0 0 1

Se puede observar que no hemos alcanzado la condición de parada ya que en los elementos
de la última fila, Z, hay uno negativo, -1. Hay que repetir el proceso:

2
 A. La variable que entra en la base es y (P2), por ser la variable que corresponde a la
columna donde se encuentra el coeficiente -1.

B. Para calcular la variable que sale, dividimos 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]
y como el menor cociente positivo es 6, tenemos que la variable que sale es r (P3).

C. El elemento pivote, que ahora hay que hacer 1, es 1/3.

Operando de forma análoga a la anterior obtenemos la tabla:

Tabla III. Iteración nº 3

3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P2 2 6 0 1 3 0 -2
P4 0 12 0 0 -7 1 4
P1 3 6 1 0 -1 0 1
Z 30 0 0 3 0 -1

Como en los elementos de la fila Z hay uno negativo, -1, significa que no hemos llegado
todavía a la solución óptima. Hay que repetir el proceso:

A. La variable que entra en la base es t (P5), por ser la variable que corresponde al
coeficiente -1.

B. Para calcular la variable que sale, dividimos 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]
y como el menor cociente positivo es 3, tenemos que la variable que sale es s (P4).

C. El elemento pivote, que ahora hay que hacer 1, es 4.

Obtenemos la tabla:

Tabla IV. Iteración nº 4

3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P2 2 12 0 1 -1/2 0 0
P5 0 3 0 0 -7/4 0 1
P1 3 3 1 0 -3/4 0 0

2
Z 33 0 0 5/4 0 0

Se observa que en la última fila todos los coeficientes son positivos, por lo tanto se cumple
la condición de parada, obteniendo la solución óptima.

La solución óptima viene dada por el valor de Z en la columna de los valores solución, en
nuestro caso: 33. En la misma columna se puede observar el punto donde se alcanza,
observando las filas correspondientes a las variables de decisión que han entrado en la base:
(x, y) = (3,12)

2
 2.3.1 Método de las “M” y método de las dos fases

MÉTODO SIMPLEX PENAL O DE LA ‘M’ GRANDE

Como su nombre lo indica, consiste en penalizar la inclusión de las variables artificiales en
la función objetivo con un coeficiente ‘M’ muy grande que para el caso de maximizar es ‘-
M’ y para el caso de minimizar es ‘+ M’.
La primera solución básica del simplex en tal caso, debe de incluir a todas las variables
artificiales que fueron necesarias en el arreglo del modelo de programación lineal por
resolver esto último porque las variables artificiales se utilizan precisamente para tomar la
primera solución básica. A medida que se cumplen las etapas de cálculo en el simplex, las
variables artificiales deberán de ir saliendo de la misma, en consecuencia del coeficiente
‘M’ muy grande.
Si se presenta el caso de que las variables artificiales no se logren sacar de la base y por lo
tanto se anulen, ello significará que tal problema no tiene solución factible.
 El método de la M Grande incluye variables de apoyo con un coeficiente muy
grande (M) o muy pequeño (-M) en la función objetivo.
 Esto da lugar a problemas numéricos que conducen a soluciones erróneas. Esto es
especialmente grave en problemas de cierto tamaño.
 El término independiente (RHS) debe ser ³0.
 A las restricciones del tipo £ se añade una variable de holgura con coeficiente +1
 A las restricciones del tipo ³, se añade una variable de holgura con coeficiente −1 y
una variable artificial con coeficiente +1
 A las restricciones del tipo = se añade una variable artificial con coeficiente +1
 La contribución de las variables de holgura a la función objetivo es 0
 La contribución de las variables artificiales a la función objetivo se fijan:
o Min: + M
o Max: - M
 Siendo M un número suficientemente grande.

MÉTODO DE LAS DOS FASES

Éste método difiere del Simplex en que primero hay que resolver un problema auxiliar que
trata de minimizar la suma de las variables artificiales. Una vez resuelto este primer
problema y reorganizar la tabla final, pasamos a la segunda fase, que consiste en realizar el
método Simplex normal.

Fase 1

2
En esta primera fase, se realiza todo de igual manera que en el método Simplex normal,
excepto la construcción de la primera tabla, la condición de parada y la preparación de la
tabla que pasará a la fase 2.
- Construcción de la primera tabla: Se hace de la misma forma que la tabla inicial del
método Simplex, pero con algunas diferencias. La fila de la función objetivo cambia para la
primera fase, ya que cambia la función objetivo, por lo tanto aparecerán todos los términos
a cero excepto aquellos que sean variables artificiales, que tendrán valor "-1" debido a que
se está minimizando la suma de dichas variables.
La otra diferencia para la primera tabla radica en la forma de calcular la fila Z. Ahora
tendremos que hacer el cálculo de la siguiente forma: Se sumarán los productos Cb·Pj para
todas las filas y al resultado se le restará el valor que aparezca en la fila de la función
objetivo.

Tabla
C0 C1 C2 ... Cn-k ... Cn
Base Cb P0 P1 P2 ... Pn-k ... Pn
Pi1 Ci1 bi1 a11 a12 ... a1n-k ... a1n
Pi2 Ci2 bi2 a21 a22 ... a2n-k ... a2n
... ... ... ... ... ... ... ... ...
Pim Cim bim am1 am2 ... amn-k ... amn
Z Z0 Z1 Z2 ... Zn-k ... Zn
Siendo Zj = Σ(Cb·Pj) - Cj y los Cj = 0 para todo j comprendido entre 0 y n-k (variables de
decisión, holgura y exceso), y Cj = -1 para todo j comprendido entre n-k y n (variables
artificiales).

- Condición de parada: La condición de parada es la misma que en el método Simplex

normal. La diferencia estriba en que pueden ocurrir dos casos cuando se produce la parada:
la función toma un valor 0, que significa que el problema original tiene solución, o que
tome un valor distinto, indicando que nuestro modelo no tiene solución.
- Eliminar Columna de variables artificiales: Si hemos llegado a la conclusión de que el
problema original tiene solución, debemos preparar nuestra tabla para la segunda fase.
Deberemos eliminar las columnas de las variables artificiales, modificar la fila de la
función objetivo por la original, y calcular la fila Z de la misma forma que en la primera
tabla de la fase 1.

2
 2.4 El método simplex revisado

El método simplex revisado usa explícitamente operaciones con matrices, por lo que se
vuelve importante describir el problema en notación matricial. Para ayudar al lector a
distinguir entre matrices, vectores y escalares, se usarán siempre letras MAYUSCULAS en
negritas para representar matrices, letras minúsculas en negritas para representar vectores y
letras cursivas normales en el caso de los escalares. También se usará el cero en negritas (0)
para denotar el vector nulo (un vector cuyos elementos son todos cero) ya sea en forma de
columna o de renglón (lo que debe ser claro por la forma del problema), mientras que el
cero normal (0) seguirá representando el número cero.
Si se emplean matrices, nuestra forma estándar del modelo general de programación lineal
establecido anteriormente se convierte en:
Maximizar Z =cx
sujeta a
Ax ≤ b y x ≥ 0,
en donde c es un vector renglón
c = [c1,c2,…,cn],

En donde C es un vector renglón C = [C1,C2,........Cn] X, b y 0 son vectores columna tales

que
X1 b1 0
X2 b2 0
X= 
b= 
0= 
Xn bm 0

y A es la Matriz
a11 a12  a1 n
a21 a22  a2 n
A=  
am 1 am 2  amn
Para obtener la forma de igualdades del problema se introduce al vector columna de las
variables de holgura
Xn + 1
Xn + 2
XS = 
Xn + m
De manera que las restricciones se convierten en

2
 X X
[A , I]
XS
=b y
XS
≥0
en donde I es la matriz idéntica m x n y b el vector 0 ahora tiene (n + m) elementos.

Pasos del método de simplex revisado

1. Paso Inicial: El mismo que para el método simplex original
2. Paso iterativo:
Parte 1 Determinar la variable básica entrante
Parte 2 Determinar la variable básica que sale igual que para el método simplex
original, pero se calcula sólo los números que se necesitan para hacerlo
(los coeficientes de la variable básica entrante en todas las ecuaciones
menos la ecuación (0), y después, para cada coeficiente estrictamente
positivo, se calcula el lado derecho.)
Parte 3 Determinar la nueva solución básica factible: obtener B-1 y el conjunto
XB = B-1b. (El cálculo de XB es opcional, a menos que la prueba de
optimalidad encuentre que es óptima.)
3. Prueba de optimalidad : igual que para el método simplex original, excepto que se
calculan sólo los números necesarios para realizar esta prueba, a saber, los
coeficientes de las variables no básicas en la ecuación (0).

2
 CONCLUSIONES

El método simplex es muy utilizado principalmente en la computación, ya que facilita la

forma de encontrar soluciones a problemas con restricciones para llegar a la solución
óptima.

2
 BIBLIOGRAFIA
http://www.investigacion-operaciones.com/SIMPLEX_analitico.htm

http://www.phpsimplex.com/teoria_metodo_simplex.htm

www.unap.cl/public/MetodoSimplexRevisado.doc