ING.

GENNY PAULINA CAMPOS ANCONA

INVESTIGACIÓN DE OPERACIONES / UNIDAD 1
FACULTAD DE CONTADURÍA Y ADMINISTRACIÓN

MÉTODO DE SOLUCIÓN: SIMPLEX

El método simplex es una técnica algebraica general, que puede usarse para resolver problemas de
programación lineal con un número grande de variables.

Cuando el problema involucra un número considerable de variables y restricciones, se vuelve

indispensable la aplicación del método simplex computarizado.

Sin embargo, con fines ilustrativos, se ejemplificará la forma en que funciona el método simplex
mediante cálculos manuales.

La compresión de la mecánica del simplex facilita la interpretación de los resultados que proporciona
la programación lineal.

El método simplex requiere que el problema sea puesto en un formato especial y que se siga ciertas
reglas específicas para hacer los cálculos.

Tomaremos el sistema de ecuaciones del ejemplo prototipo. Que se resolvió en forma gráfica:

Max (z) = 30 X1 + 50 X2

Sujeto a (s.a.)

2X1 + 1X2 ≤ 160 Harina

1X1 + 2X2 ≤ 110 Manteca

1X1 + 3X2 ≤ 150 Azúcar

X1 , X2 ≥ 0
El primer paso en el método simplex es convertir el problema al formato adecuado, cambiando todas
las desigualdades en las restricciones a ecuaciones o igualdades. Esto se hace añadiendo una variable
de holgura a cada desigualdad, como se muestra a continuación:

2X1 + 1X2 + 1X3 = 160

1X1 + 2X2 + 1X4 = 110
1X1 + 3X2 + 1X5 = 150
INVESTIGACIÓN DE OPERACIONES / UNIDAD 1

X1 , X2 , 𝑋3 , 𝑋4, 𝑋5 ≥ 0

Max Z = 30x1 + 50x2 + 0x3 + 0x4 + 0x5

En la 1ª restricción se ha añadido la variable X 3 en el lado izquierdo de la desigualdad para absorber
la holgura o sobrante que pueda existir entre el valor de lado izquierdo original y el valor del lado
derecho. Por lo tanto X3 debe también quedar restringida a valores no negativos, de tal modo que
represente en forma adecuada la holgura del lado izquierdo de la restricción.

1
 ING. GENNY PAULINA CAMPOS ANCONA
INVESTIGACIÓN DE OPERACIONES / UNIDAD 1
FACULTAD DE CONTADURÍA Y ADMINISTRACIÓN

De igual manera X4 y X5 se añadieron como variables de holgura en la 2ª y 3ª restricciones,

respectivamente. Como no se desea que estas variables afecten a la utilidad, se les asigna un
coeficiente cero para incluirlas en la función objetivo.

Este problema tendrá exactamente la misma solución óptima par X 1 y X2 que la que corresponde al
problema original.

Ahora que el problema tiene la forma que se requiere el método simplex, se puede construir el primer
“tableau”. El término “tableau” se refiere a una serie de cuadros especiales para el simplex que se
construyen con la finalidad de llevar un registro de los cálculos efectuados. El primer tableau se
muestra a continuación:

Tableau 1 Iteración 0

CJ 30 50 0 0 0

CB XB X B P1 P2 P3 P4 P5 𝜃𝑚𝑖𝑛

0 X3 160 2 1 1 0 0 160

0 X4 110 1 2 0 1 0 50

0 X5 150 1 3 0 0 1 55 sale

ZJ Z =0 0 0 0 0 0

𝑍𝑗 − 𝐶𝑗 = -30 -50 0 0 0

entra
Dicho tableau se construye tomando los coeficientes de las variables del problema y colocándolos en
los renglones y columnas correspondientes. Por ejemplo, el primer renglón de números que se
encuentra en el cuerpo de tableau corresponde a los coeficientes de la 1ª restricción; el segundo
renglón corresponde a los coeficientes de la 2ª restricción, etc.

En cada tableau el renglón superior contiene a 𝑪𝒋 , donde: INVESTIGACIÓN DE OPERACIONES / UNIDAD 1

𝐶𝑗 = coeficientes de las variables en la función objetivo, colocados de forma que correspondan a las
columnas representadas por cada variable 𝑃𝑗 . Por ejemplo, el coeficiente de utilidad de X1 es 30 y
está escrito justo arriba del símbolo 𝑃1 .

Los valores de 𝐶𝑏 corresponden a los coeficientes en la función objetivo de las variables que están en
la base o en la solución. En el primer tableau, todos los valores de 𝐶𝑏 son iguales a cero ya que en la
solución inicial sólo hay variables de holgura.

2
 ING. GENNY PAULINA CAMPOS ANCONA
INVESTIGACIÓN DE OPERACIONES / UNIDAD 1
FACULTAD DE CONTADURÍA Y ADMINISTRACIÓN

La columna 𝑋𝑏 representa los valores de las variables para la solución en turno. Por ejemplo, la
solución inicial es X3 = 160, X4 = 110, X5 = 150. A todas las variables que no aparecen en la solución
se les asigna siempre un valor de cero. Por lo tanto, X1 = 0 y X2 = 0 en el primer tableau.

Por último el tableau tiene dos renglones en la parte inferior los cuales han sido marcados con:

𝑍𝑗 y 𝑍𝑗 − 𝐶𝑗 .
𝑚

𝑍 = ∑ 𝐶𝑏𝑖 𝑋𝑏𝑖
𝑖=1

𝑍𝑗 = ∑ 𝐶𝑏𝑖 𝑃𝑖𝑗
𝑖=1

Por ejemplo: 𝑍𝑗 = 0(2) + 0(1) + 0(1) = 0

En el primer tableau, los valores resultantes de 𝑍𝑗 son siempre iguales a cero ya que todos los valores
de 𝐶𝑗 son cero.

El último renglón del tableau, representado por 𝑍𝑗 − 𝐶𝑗 es el resultado de restar el valor de 𝐶𝑗 que
se encuentra en la parte superior del tableau al de 𝑍𝑗 que acaba de calcularse.

El método simplex funciona desplazándose de una esquina de la región factible a otra que le sea
adyacente. El primer tableau representa la esquina que se encuentra en el origen, ya que se tiene
X1 = 0 y X2 = 0. En el origen las 3 restricciones tienen holgura (X3 = 160, X4 = 110 y X5 = 150).

Para determinar que variable entra en la nueva solución se selecciona el valor más negativo del
reglón( 𝑍𝑗 − 𝐶𝑗 )

Se marca esta columna con una línea punteada (en este archivo, con sombreado gris), se le llama
¨columna clave¨.

Como entrará una variable a la solución (a la base), alguna variable de la base tendrá que salir, por lo
que tendremos un criterio de salida.

Criterio de salida: Se calcula el cociente de los valores de la solución entre los coeficientes de la
INVESTIGACIÓN DE OPERACIONES / UNIDAD 1

“Columna clave”, sólo para los coeficientes positivos, a este cociente se le llama
𝜃𝑚𝑖𝑛 , entonces:
𝑿𝒃𝒊
𝜃𝑚𝑖𝑛 = { , 𝒆𝒏 𝒅𝒐𝒏𝒅𝒆 𝑷𝒊𝒋 > 𝟎}
𝑷𝒊𝒋

La variable que sale corresponde al renglón que tenga el cociente más pequeño. Llámese a éste
“Renglón clave”. Este renglón se marca también con una línea punteada (en este archivo, marcado
con sombreado gris).

3
 ING. GENNY PAULINA CAMPOS ANCONA
INVESTIGACIÓN DE OPERACIONES / UNIDAD 1
FACULTAD DE CONTADURÍA Y ADMINISTRACIÓN

En el primer tableau, la aplicación de la regla de entrada es: se selecciona P2 que corresponde a la

variable X2 para entrar a la solución (a la base).

La aplicación de la regla de salida produce los siguientes cocientes, uno para cada renglón:

160 110 100

= 160 ; = 55 ; = 50
1 2 2
Se elige el mínimo o sea el 3er renglón, es decir X5 es la variable que sale de la solución.

A la intersección del renglón clave y la columna clave suele llamarse ¨Elemento pivote¨.

Después de aplicar las reglas de entrada y salida el siguiente paso es transformar el tablero en una
nueva solución, usando el elemento pivote. Esto puede hacerse mediante el proceso de eliminación
de Gauss, el cual transforma el tableau pero mantiene la misma solución para las ecuaciones de
restricción. Este proceso de eliminación se puede multiplicar con cualquier renglón del tableau por
una constante distinta de cero y sumarlo a cualquier otro renglón, colocando la suma en el nuevo
tableau. Lo que se está haciendo es resolver el sistema de ecuaciones simultáneas.

Según las reglas de Gauss, todos los coeficientes del renglón clave se dividen entre el elemento pivote
y el resultado se coloca en el nuevo tableau (Tableau 2).

Tableau 2 Iteración 1

CJ 30 50 0 0 0

CB XB X B P1 P2 P3 P4 P5 𝜃𝑚𝑖𝑛

0 X3 110 5⁄ 0 1 0 −1⁄ 66
3 3

0 X4 10 1⁄ 0 0 1 −2⁄ 30
3 3 sale

50 X2 50 1⁄ 1 0 0 1⁄ 150 (÷3)(2)(-1)
3 3

ZJ Z = 2,500 50⁄ 50 0 0 50⁄

3 3
−40⁄ 50⁄
INVESTIGACIÓN DE OPERACIONES / UNIDAD 1

𝑍𝑗 − 𝐶𝑗 = 3
0 0 0 3

entra

4
 ING. GENNY PAULINA CAMPOS ANCONA
INVESTIGACIÓN DE OPERACIONES / UNIDAD 1
FACULTAD DE CONTADURÍA Y ADMINISTRACIÓN

Tableau 3 Iteración 2

CJ 30 50 0 0 0

CB XB X B P1 P2 P3 P4 P5 𝜃𝑚𝑖𝑛

0 X3 60 0 0 1 -5 3 20 sale

30 X1 30 1 0 0 3 -2 --- (÷1⁄3)(−5⁄3)(-1⁄3)

50 X2 40 0 1 0 -1 1 40

ZJ Z = 2,900 30 50 0 40 -10

𝑍𝑗 − 𝐶𝑗 = 0 0 0 40 -10

entra

Tableau 4 Iteración 3

CJ 30 50 0 0 0

CB XB X B P1 P2 P3 P4 P5

0 X5 20 0 0 1⁄ −5⁄ 1
3 3

30 X1 70 1 0 2⁄ −1⁄ 0 (÷3)(2)(-1)
3 3

50 X2 20 0 1 −1⁄ 2⁄ 0
3 3

ZJ Z = 3,100 30 50 10⁄ 70⁄ 0

3 3
𝑍𝑗 − 𝐶𝑗 = 0 0 10⁄ 70⁄ 0
3 3
Todos +s y 0s
INVESTIGACIÓN DE OPERACIONES / UNIDAD 1

A este nuevo resultado se le llama ¨Renglón pivote¨. Después se multiplica el renglón pivote por
una constante y se le suma al renglón correspondiente del tableau anterior, de tal forma que el
resultado en la columna correspondiente del nuevo tableau sea cero. Debe seleccionarse la
constante adecuada para cada renglón.

En el ejemplo: todo el renglón clave del 1er tableau se dividió entre 3 para generar un 1 en el lugar
del elemento pivote en el tableau 2 y todos los valores correspondientes del nuevo renglón que
recibirá el nombre de renglón pivote. Este renglón pivote se multiplicó por (− 2) y se le sumó a
cada elemento del 2º renglón en el 1er tableau de tal forma que tendremos un nuevo renglón en el

5
 ING. GENNY PAULINA CAMPOS ANCONA
INVESTIGACIÓN DE OPERACIONES / UNIDAD 1
FACULTAD DE CONTADURÍA Y ADMINISTRACIÓN

tableau 2, en donde el elemento correspondiente del renglón clave se convirtió en cero. De manera
semejante se calculan los valores para el primer renglón.

Así se obtiene el segundo tableau garantizando que la solución no ha sido alterada en cada uno de
los pasos del método simplex, las variables que se encuentran en las solución (o en la base) deben
tener un 1 en alguna posición y el resto son ceros, obteniéndose así una matriz identidad dentro del
tableau. Esto permite leer la solución directamente del tableau. En el segundo tableau se tiene que
X1 = 0, X2 = 50, X3 = 110, X4 =10 y X5 = 0.

Lo que se está calculando es la solución de un sistema de tres ecuaciones con tres incógnitas para
cada tabla hasta alcanzar el óptimo.

El segundo tableau aún no es óptimo. Será óptimo cuando todos los valores del renglón (𝑍𝑗 − 𝐶𝑗 ) 
0.

Se repite el procedimiento, hasta obtener el cuarto tableau en donde todos los (𝑍𝑗 − 𝐶𝑗 =) son
mayores o iguales a cero, lo cual nos indica que la solución alcanzada es la óptima. Observando el
tableau 4,

𝑋1 = 70
𝑋2 = 20
𝑋3 = 0
𝑋4 = 0
𝑋5 = 0
con Z = $ 3,100

Podemos comparar este resultado con el que obtuvimos con el método gráfico y observaremos
que se llegó a la misma solución.

INVESTIGACIÓN DE OPERACIONES / UNIDAD 1

6
 ING. GENNY PAULINA CAMPOS ANCONA
INVESTIGACIÓN DE OPERACIONES / UNIDAD 1
FACULTAD DE CONTADURÍA Y ADMINISTRACIÓN

PROBLEMA DE MINIMIZACIÓN
La programación lineal también puede usarse para resolver problemas de minimización. Sin
embargo, es necesario hacer algunas modificaciones en los procedimientos.

Como ilustración de un problema de minimización, suponga un taller en el cual hay dos tipos
diferentes de máquinas, la máquina 1 y la máquina 2, pueden emplearse para producir un solo
producto 2. Las máquinas del taller presentan diferencias en cuanto al total producido por hora, a la
cantidad de mano de obra que debe usarse y al costo de operación. Supóngase además que debe
producirse, por lo menos, una cierta cantidad del producto y que se pretende utilizar, por lo menos,
la fuerza de trabajo normal. Bajo estas condiciones. ¿Cuánto debe usarse cada máquina fin de
minimizar los costos totales y cumplir al mismo tiempo con los requerimientos?

Este problema puede formularse en términos de las técnicas de programación lineal de la siguiente
manera:

Sea: 𝑋1 = Horas de Máquina 1

𝑋2 = Horas de Máquina 2

Por otra parte, se supone que la Máquina 1 puede producir 20 kg del producto por hora, la Máquina
2, 15 kg. del producto por hora, y se requiere que ambas máquinas elaboren por los menos, 100 kg.
del producto. Esta restricción puede expresarse matemáticamente así:

20 𝑋1 + 15 𝑋2 ≥ 100
Considérese además que se requieren dos horas de mano de obra por cada hora de operación de la
Máquina 1, tres horas de mano de obra por cada hora de operación de la Maquina 2, y se quieren
usar por lo menos 15 horas del tiempo disponible de mano de obra normal. Esta restricción puede
expresarse matemáticamente de la siguiente forma.

2 𝑋1 + 3 𝑋2 ≥ 15

Por último, se supone que cuesta $ 25 por hora (mano de obra y materia prima) operar la Máquina
1 y $30 por hora operar la Máquina 2. El deseo de Minimizar los costos totales de operación puede
expresarse matemáticamente como sigue:

𝑀𝑖𝑛 (𝑧) = 25 𝑋1 + 3 0𝑋2

INVESTIGACIÓN DE OPERACIONES / UNIDAD 1

Este problema, ha sido graficado como ejemplo 2 del tema anterior, junto con las restricciones X1 
0, X2  0. Igual que antes, las restricciones se graficaron como ecuaciones, pero la región de
factibilidad para los signos  se encuentra ahora a la derecha de la recta, puesto que los puntos
factibles deben ser mayores que los puntos de la recta.

En la gráfica del ejemplo 2 se muestran también las rectas de costo. Como se requiere minimizar la
función objetivo, la recta de costo que se encuentre más cerca del origen debe seleccionarse como
el costo mínimo. La solución óptima ocurre en la intersección de las dos restricciones. Al resolver las
dos restricciones como ecuaciones simultáneas se tiene que X1 = 2.5, X2 = 3.33 para la solución
óptima. El costo mínimo correspondiente es $ 162.50.

7
 ING. GENNY PAULINA CAMPOS ANCONA
INVESTIGACIÓN DE OPERACIONES / UNIDAD 1
FACULTAD DE CONTADURÍA Y ADMINISTRACIÓN

Este problema también puede resolverse mediante el método simplex haciendo algunas
modificaciones menores. El primer paso es convertir en ecuaciones las desigualdades. Puesto que
en este caso las son de tipo , se debe restar una variable en el lado izquierdo para igualar los dos
lados. Esta variable se llama variable exceso pero desempeña la misma función que las variables del
holgura cuando se trata de signos . El problema de programación lineal que resulta es:

Objetivo:

𝑀𝑖𝑛 (𝑧) = 25 𝑋1 + 30𝑋2 + 0𝑋3 + 0𝑋4

Sujeto a:

20 𝑋1 + 15𝑋2 − 𝑋3 = 110
2 𝑋1 + 3𝑋2 − 𝑋4 = 15
X1 , X2 , 𝑋3 , 𝑋4 ≥ 0

El método simplex requiere una solución no negativa factible como punto de partida. Si se establece
X1 = 0, X2 = 0 como punto de partida, tal como se hizo en el ejemplo anterior, se tendrá que X 3 = -
100, X4 = -15. Como esta solución viola la condición de no negatividad, en este problema no se
dispone de un punto de partida factible. Para corregir esta situación, se añade una variable artificial
a cada ecuación con un coeficiente positivo muy grande (llamado W grande o gran W) en la función
objetivo. Como se están minimizando los costos, el método simplex hará que las variables artificiales
salgan de la solución debido al alto costo que representan sus coeficientes. Desde luego, esto es lo
que se requiere, puesto que las variables artificiales no pueden permanecer en la solución óptima. El
propósito de las variables es proporcionar un punto de partida factible para la aplicación del método
simplex.

Con el empleo de las variables artificiales, la formulación del problema sería como sigue:

Objetivo:

𝑀𝑖𝑛 (𝑧) = 25 𝑋1 + 30𝑋2 + 0𝑋3 + 𝑊𝑋4 + 0𝑋5 + 𝑊𝑋6

Sujeto a: INVESTIGACIÓN DE OPERACIONES / UNIDAD 1

20 𝑋1 + 15𝑋2 − 𝑋3 + 𝑋4 = 110
2 𝑋1 + 3𝑋2 − 𝑋5 + 𝑋6 = 15

X1 , X2 , 𝑋3 , 𝑋4 , 𝑋5, 𝑋6 ≥ 0

En este momento se ha logrado una formulación de programación lineal con una solución inicial
cuyos valores son X1 = 0, X2, = 0, X3 = 0, X4 = 100, X5 = 0, X6 = 15. Entonces el costo inicial es 100
W + 15 W, el cual es muy elevado, puesto que W es un número positivo arbitrariamente grande. El
problema está ya listo para vaciarse en el primer tableau simplex que se muestra en el tableau 1.

8
 ING. GENNY PAULINA CAMPOS ANCONA
INVESTIGACIÓN DE OPERACIONES / UNIDAD 1
FACULTAD DE CONTADURÍA Y ADMINISTRACIÓN

Tableau 1 Iteración 0

CJ 25 30 0 W 0 W

CB XB X B P1 P2 P3 P4 P5 P6 𝜃𝑚𝑖𝑛

W 𝑋4∗ 100 20 15 -1 1 0 0 5 sale

W 𝑋6∗ 15 2 3 0 0 −1 1 7.5

ZJ Z = 115 W 22 𝑊 18W-30 -W W −𝑊 W

𝑍𝑗 − 𝐶𝑗 = 22W - 25 18W-30 -W 0 −W 0

entra

Cuando se trata de problemas de minimización, la variable que entra se selecciona con el valor
positivo más alto de Zj − Cj , ya que se requiere reducir el valor de la función objetivo tanto como sea
posible en cada iteración. En el primer tableau, la columna que entra es por tanto P 1 que corresponde
a la variable 𝑋1 , la cual tiene el coeficiente positivo más alto en el renglón Zj − Cj . , los pasos restantes
del método simplex se aplican exactamente en la misma forma que en el problema de maximización.
Con la regla del cociente mínimo,  *4 es la variable que sale. El elemento pivote se usa para ejecutar
la transformación de Gauss y construir el tableau 2.

Tableau 2 Iteración 1

CJ 25 30 0 W 0 W

CB XB X B P1 P2 P3 P4 P5 P6 𝜃𝑚𝑖𝑛

25 𝑋1 5 1 3⁄ −1⁄ 1⁄ 0 0 6.67
4 20 20
(÷20)(-2)
W 𝑋6∗ 5 0 3⁄ 1⁄ −1⁄ −1 1 3.33 sale
2 10 10
3 75 1 5 1 5
ZJ Z = 5 W +125 25 W+ W- − W+ −𝑊 W
2 4 10 4 10 4
INVESTIGACIÓN DE OPERACIONES / UNIDAD 1

3 45 1 5 11 5 −W
𝑍𝑗 − 𝐶𝑗 = 0 W- W-4 − 10W + 4 0
2 4 10

entra
En el segundo tableau, se selecciona P2 que corresponde a la variable X2 como variable de entrada,
puesto que tiene el valor positivo más alto en Zj − Cj . Al elegir el cociente mínimo sobre los
coeficientes positivos de la columna 2, X6 resulta ser la variable que sale. Al aplicar nuevamente el
procedimiento de eliminación de Gauss se obtiene el tableau 3.

9
 ING. GENNY PAULINA CAMPOS ANCONA
INVESTIGACIÓN DE OPERACIONES / UNIDAD 1
FACULTAD DE CONTADURÍA Y ADMINISTRACIÓN

Tableau 3 Iteración 2

CJ 25 30 0 W 0 W

CB XB X B P1 P2 P3 P4 P5 P6

25 𝑋1 5⁄ 1 0 −1⁄ 1⁄ 1⁄ − 1⁄2
2 10 10 2
30 𝑋2 10⁄ 0 1 1⁄ −1⁄ −2⁄ 2⁄ (3⁄2)(− 3⁄4)
3 15 15 3 3
ZJ Z = 325⁄2 25 30 −1⁄ 1⁄ −15⁄ 15⁄
2 2 2 2
−1⁄ 1 15
𝑍𝑗 − 𝐶𝑗 = 0 0 -W −15⁄ -W
2 2 2 2

entra
El tercer tableau óptimo, ya que todos los valores de Zj − Cj , son negativos; ya no es posible efectuar
reducción alguna en la función objetivo.

En el tableau 3 puede verse que la solución óptima es X 1 = 5/2, X2 = 10/3, y el costo mínimo = $162.50.
Los precios sombra son de $ 50 centavos por cada Kg. adicional que se produzca del producto y $
7.50 por cada hora adicional de mano de que se requiera. Puede usarse el costo marginal de $ 50
centavos por kg. para decidir si se deben o no tomar pedidos adicionales. El costo marginal de mano
de obra de $ 7.50 por hora puede emplearse para decidir si se debe utilizar toda la mano de obra
disponible.

En síntesis, se deben realizar dos ajustes principales al método simplex cuando se tiene un problema
de minimización. Primero, el criterio para elegir la columna que entra debe basarse en el valor más
positivo de Zj − Cj , en lugar de basarse en el valor más negativo de Zj − Cj .

Segundo, el método simplex se detiene en la solución óptima cuando todas las Zj − Cj negativas o
cero. En los pasos restantes, todas las características del método simplex son iguales que el caso de
maximización.
INVESTIGACIÓN DE OPERACIONES / UNIDAD 1

10
 ING. GENNY PAULINA CAMPOS ANCONA
INVESTIGACIÓN DE OPERACIONES / UNIDAD 1
FACULTAD DE CONTADURÍA Y ADMINISTRACIÓN

Resumen:

Tipo de Valor de la función objetivo

restricción F. O.
Maximización Minimización
1. Menor o igual  necesita Variable de holgura Variable de holgura toma un
sumarse una variable de coeficiente cero en F.O. coeficiente cero en F.O.
holgura
2. Mayor igual  necesita Coeficiente cero para la Coeficiente cero para la
una variable de holgura variable de holgura y -W para variable de holgura y +W
negativa y sumar una la variable artificial para la variable artificial
variable artificial positiva
3. Igualdad = necesita Coeficiente -W en la F.O para Coeficiente +W en la F.O.
variable artificial positiva la variable artificial para la variable artificial.

INVESTIGACIÓN DE OPERACIONES / UNIDAD 1

11