33

CAPÍTULO IV

PROGRAMACIÓN LINEAL

EL MÉTODO SIMPLEX

El tonto no ve el mismo árbol

que el sabio
William Blake

Introducción
Este método fue desarrollado por George B, Dantzig, en los Estados Unidos en 1947 y hoy en día es muy
popular debido a su amplio uso y versatilidad en la resolución de los problemas de programación lineal
(Gallagher y Watson, 1992).

Es un procedimiento matricial iterativo basado en la metodología de Gauss Jordan (Izar, 1998) para
manejar variables no negativas, de fácil implementación en computadora, lo que permite solucionar problemas
de un número elevado de variables y de restricciones de una manera ágil y eficiente.

Al igual que el método gráfico, este método parte del problema de programación lineal debidamente
planteado, es decir, con las ecuaciones de la función objetivo y las restricciones definidas matemáticamente.

El método Simplex toma siempre como posible solución un punto correspondiente a uno de los vértices de
la región factible de solución, siendo la primera aproximación el origen. De aquí, en las siguientes iteraciones,
el Simplex se moverá hacia otros vértices, hasta que alguno de ellos sea el óptimo, lo cual sucede cuando un
vértice tiene mejor valor de la función objetivo que los 2 vértices adyacentes a él, es decir el anterior y el
posterior, siendo entonces cuando se ha logrado la solución del problema de programación lineal (Davis y
McKeown, 1986).

Etapas del Método Simplex

El método Simplex puede dividirse en tres etapas, que son las siguientes (Hillier y Lieberman, 1991):
1. Etapa inicial. Consiste en dar la primera solución factible en el vértice
correspondiente al origen. Esta etapa abarca los tres primeros pasos del procedimiento
Simplex el que se explica más adelante.
2. Etapa iterativa. La cual implica que el método busque una mejor solución a la anterior
en otro vértice. Esta etapa corresponde al paso 4 del procedimiento Simplex.
3. Etapa de prueba de optimalidad. Esta se logra cuando la solución de un vértice es
mejor que la de los vértices adyacentes a él. Esta etapa es el 5° paso de la metodología
Simplex.

Para la explicación del procedimiento Simplex, se resolverá un primer ejemplo señalando en él las
situaciones de carácter particular del caso, así como también las de tipo general.

Propiedades de las soluciones factibles

Este método se basa en algunas propiedades de las soluciones factibles de la programación lineal, las cuales
son las siguientes (Hillier y Lieberman, 1991):
1. En caso de haber alguna solución óptima, ésta se localizará en uno de los vértices de
la zona factible de solución.
34
2. Si existen soluciones múltiples, éstas se situarán en vértices adyacentes de la región
factible de solución.
3. Habrá siempre un número finito de soluciones factibles en los vértices.
4. La solución óptima en un vértice será aquella que sea mejor que las soluciones de
vértices adyacentes a aquel.

Metodología Simplex
Ahora se presenta un ejemplo para ilustrar la metodología Simplex, aplicada a un caso de maximización.

Caso de Maximización

Ejemplo IV.1.- Resolver el problema de programación lineal

Max Z= 10 X1 + 12X2

Sujeto a las restricciones

4X1 + 3X2 < 3.6 (1)
X1 + X2 = 1 (2)
2X1 + 3X2 > 2.4 (3)

Solución:
Se aplicará la metodología Simplex, explicando cada paso debidamente:
Paso 1. Convertir las desigualdades de las restricciones en igualdades mediante la incorporación de
variables de holgura (también llamadas variables de excedente) y/o variables artificiales (también conocidas
como ficticias), las cuales se agregarán a las restricciones con un coeficiente cuyo valor puede determinarse de
la siguiente tabla:

Tabla IV.I.- Coeficientes de las variables de holgura y artificiales según el tipo de restricción.
Tipo de restricción Coeficiente de la variable de Coeficiente de la variable artificial
holgura
Menor o igual que (< ) +1 0
Mayor o igual que (>) -1 +1
Igualdad (=) 0 +1
Aproximadamente igual +1 y -1 0

En esta tabla las restricciones de tipo menor o igual que (<) agregan una variable de holgura porque se
supone que les falta algo para lograr la igualdad, siendo eso que les falta precisamente dicha variable.

Las restricciones de igualdad no llevan variable de holgura, porque ya existe una igualdad entre el lado
izquierdo y el lado derecho de la ecuación. Sin embargo, requieren entonces de una variable artificial con
coeficiente +1, para poder integrar la parte identidad de la tabla Simplex, tal y como se verá más adelante.

Por su parte las restricciones del tipo mayor o igual que (>) restan una variable de holgura, dado que al
lado izquierdo le sobra algo para igualarse al lado derecho y agregan una variable artificial pues la variable de
holgura tiene coeficiente -1, siendo necesario entonces incorporar una variable artificial con coeficiente +1
para que la parte identidad de la tabla Simplex quede debidamente formada.

Si se observa el ejemplo, se tienen 3 restricciones, una de cada tipo. La primera es del tipo menor o igual
que (<), de acuerdo a la tabla se agregará una variable de holgura con coeficiente +1 y no se agregan variables
artificiales, pues sus coeficientes serán cero, entonces, dicha restricción quedará de la siguiente forma:

4X1 +3X2 + H1 = 3.6 (1)

Siendo H1 la variable de holgura.

 35

La segunda restricción es de igualdad, por lo que no habrá variables de holgura (sus coeficientes para este
tipo de restricción son cero), pero sí habrá una variable artificial con coeficiente +1, entonces:

X1 + X 2 + F1 = 1 (2)

Donde F1 es la variable artificial.

Para la tercera restricción, ésta es del tipo mayor o igual que (>), por lo que conforme a la tabla, llevará
una variable de holgura con coeficiente -1 y una variable artificial con coeficiente +1, con esto se tendrá:

2X1 + 3X2 - H2 + F2 = 2.4 (3)

Donde H2 es la variable de holgura y F2 la variable artificial.

Paso 2. Incluir las variables de holgura y artificiales en la ecuación de la función objetivo con un
coeficiente que será cero en el caso de las variables de holgura y M para las artificiales, donde M se supone
que es un valor muy grande, el cual no necesariamente debe ser conocido, pues el método más adelante
tenderá a eliminar dicha variable de la zona de solución del problema.

Entonces con esto, la función objetivo será:

Max Z = 10X1 + 12X2 + 0H1 + 0H2 - MF1 - MF2

Aquí cabe aclarar que la M se ha agregado con signo negativo por tratarse de un problema de
maximización, pues para casos de minimización, la M será positiva.

A una solución se le llama aumentada cuando incluye las variables de holgura además de las de decisión.

Paso 3. Formar la primera tabla, para esto:

a) Expresar las ecuaciones de las restricciones en función de sus coeficientes, del modo siguiente:

X1 X2 H1 H2 F1 F2
3.6 4 3 1 0 0 0
1 1 1 0 0 1 0
2.4 2 3 0 -1 0 1
columna de cuerpo parte identidad
constantes

b) Agregar el renglón objetivo arriba del renglón de variables, el cual incluirá los coeficientes de las
variables en la función objetivo, con esto se tendrá:

10 12 0 0 -M -M
X1 X2 H1 H2 F1 F2
3.6 4 3 1 0 0 0
1 1 1 0 0 1 0
2.4 2 3 0 -1 0 1

A estos coeficientes de las variables en la función objetivo también se les denomina contribuciones.

c) Buscar la primera solución (conocida también como solución básica inicial), en función de las variables
cuyos coeficientes son +1 en la parte identidad, con esto se tendrá lo siguiente:
36

10 12 0 0 -M -M
X1 X2 H1 H2 F1 F2
0 H1 3.6 4 3 1 0 0 0
-M F1 1 1 1 0 0 1 0
-M F2 2.4 2 3 0 -1 0 1
columna zona de
objetivo solución

Como se puede observar de la tabla, se agregó a la zona de solución en cada renglón, aquella variable cuyo
coeficiente es +1 en la parte identidad.

También en la columna objetivo se han incluido los coeficientes que tienen éstas en la función objetivo.

A las variables que forman la zona de solución se les llama variables básicas.

De esta forma la primera solución será:

H1 = 3.6
F1 = 1
F2 = 2.4
Z=0

Aquí Z es cero porque no aparece en la zona de solución, de igual forma H 2, X1 y X2 son cero por esta
misma razón. A estas variables se les denomina no básicas.

d) Generar el renglón índice o renglón de la utilidad por medio de la siguiente fórmula:

Sumatoria de los productos de El elemento correspondiente

Número los elementos de la columna
a la columna en el
= por el respectivo elemento de
índice
la columna objetivo renglón objetivo

Ec. (IV.1)

Aquí es pertinente señalar que esta fórmula es aplicable para problemas de maximización. Para casos de
minimización los términos del lado derecho del signo igual cambian de signo, es decir, la sumatoria irá con
signo menos y el elemento del renglón objetivo con signo más.

Ahora se procede a calcular con la fórmula (IV.1) los elementos del renglón índice:

Para la columna que encabeza la variable X1, se tiene:

Sumatoria = 0x4 + (-M) x1 + (- M) x2

= 0 - M - 2M = 0 - 3M

Por tanto el elemento índice será:

Elemento índice: 0 - 3M - 10 = -10 - 3M

Para la columna de X2 será:

Sumatoria = 0x3 + (-M) x1 + (-M) x3

= 0 - M - 3M = 0 - 4M
 37
Elemento índice = 0 - 4M - 12 = -12 - 4M

Por su parte, para la columna de H1:

Sumatoria = 0x1 + (-M) x0 + (-M) x0

=0+0+0=0
Elemento índice = 0 - 0 = 0

Para la columna de H2:

Sumatoria = 0x0 + (-M) x0 + (-M) (-1)

=0+0+M=0+M
Elemento índice = 0 + M - 0 = 0 + M

Para la columna de F1:

Sumatoria = 0x0 + (-M) x1 + (-M) x0

=0-M+0=0-M
Elemento índice = 0 - M - (-M) = 0

Para la columna de F2:

Sumatoria =0x0 + (-M) x0 + (-M) x1

=0+0-M=0-M
Elemento índice = 0 - M - (-M) = 0

La utilidad será el elemento índice correspondiente a la columna de constantes, el cual será:

Sumatoria = 0x3.6 + (-M) x1 + (-M) x2.4

=0 - M - 2.4M = 0 - 3.4 M
Elemento índice = 0 - 3.4M - 0 = 0 - 3.4M
(utilidad)

Como puede observarse, todos los números índice tienen en este caso 2 términos: uno numérico y uno en
función de M. Para estos casos se descompone el renglón en 2 partes, una con la parte numérica y otra con los
términos que contienen a M.

Con esto, la tabla Simplex quedará de la siguiente manera:

10 12 0 0 -M -M
X1 X2 H1 H2 F1 F2
0 H1 3.6 4 3 1 0 0 0
-M F1 1 1 1 0 0 1 0
-M F2 2.4 2 3 0 -1 0 1
Utilidad 0 -10 -12 0 0 0 0 Numérica
-3.4 -3 -4 0 1 0 0 Parte M

El valor de -3.4 que corresponde a la parte M del renglón índice puede omitirse.

Con esto ha quedado completa la primera tabla Simplex, que muestra la primera aproximación de solución
al problema.

Primera solución:
38
Variables básicas Variables no básicas
H1 = 3.6 H2 = 0
F1 = 1 X1 = 0
F2 = 2.4 X2 = 0

Esta aproximación será el óptimo (solución del problema), cuando no haya números negativos en el
renglón índice considerando sus 2 partes (prueba de optimalidad).

Como en este caso sí existen elementos negativos, significa que esta aproximación deberá mejorar en las
iteraciones subsecuentes.

En el método Simplex, el número de variables básicas es igual al número de restricciones funcionales (3 en

este ejemplo); mientras que el número de variables no básicas es el número de grados de libertad que tiene el
problema (también 3 en este caso).

Paso 4. Mejorar la aproximación anterior mediante el siguiente procedimiento:

a) Determinar la columna clave o columna de trabajo. La cual será aquella que posea el número índice más
negativo (en caso de empate se selecciona al azar).

En los casos que la tabla Simplex tenga 2 partes del renglón índice, se considera en primer lugar la parte
con términos en M y luego la numérica.

En base a lo antes descrito, el número índice de la parte M más negativo es el -4, por lo que la columna a
la que pertenece (la que encabeza la variable X2), será la columna clave.

10 12 0 0 -M -M
X1 X2 H1 H2 F1 F2
0 H1 3.6 4 3 1 0 0 0
-M F1 1 1 1 0 0 1 0
-M F2 2.4 2 3 0 -1 0 1
0 -10 -12 0 0 0 0
-3 -4 0 1 0 0

Esto se ha representado en la tabla enmarcando a la columna clave.

b) Determinar el renglón clave.

El renglón clave será aquel que tenga el menor cociente de los obtenidos al dividir el elemento respectivo
de la columna de constantes entre el elemento correspondiente de la columna clave, (en caso de empate
también se selecciona al azar). Aquí no se incluye el renglón índice como candidato a ser clave, sólo los
renglones de las restricciones.

Además, no se tomarán como denominadores aquellos elementos de la columna clave que sean menores o
iguales que cero.

Por lo tanto hay 3 renglones que pueden ser clave.

Para el primer renglón, se tiene:

Cociente = 3.6/3 =1.2
Para el segundo renglón:
Cociente = 1/1 =1.0
Para el tercer renglón:
Cociente = 2.4/3 = 0.8
 39

De aquí el menor cociente ha sido el del tercer renglón, el que se enmarca en la tabla:

10 12 0 0 -M -M
X1 X2 H1 H2 F1 F2
0 H1 3.6 4 3 1 0 0 0
-M F1 1 1 1 0 0 1 0
-M F2 2.4 2 3 0 -1 0 1
0 -10 -12 0 0 0 0
-3 -4 0 1 0 0

c) Determinar el número clave o elemento pivote, que será aquel elemento que pertenece a la vez al
renglón y a la columna clave.

En este ejemplo, el número clave es el 3, que ha quedado encerrado en un cuadro, al pertenecer al renglón
y a la columna clave.

d) Hacer el número clave la unidad, lo que se consigue al dividir el renglón clave entre el número clave.

Al llevar a cabo lo anterior, el renglón clave quedará de la siguiente manera:

0.8 0.667 1 0 -0.333 0 0.333

e) Sustituir la variable y su contribución que encabeza el renglón clave (variable que sale), por la variable
y su contribución que encabeza la columna clave (variable que entra).

Con este cambio el renglón clave quedará de la siguiente manera:

12 X2 0.8 0.667 1 0 -0.333 0 0.333

Ahora la variable X2 se ha convertido en básica al entrar a la zona de solución.

Aquí es pertinente mencionar que la metodología Simplex de 2 fases indica que es posible eliminar las
variables artificiales de la tabla Simplex en cuanto dejen de ser básicas, como en este caso la variable F2, que
con la modificación del presente inciso ha salido de la zona de solución, por lo que puede eliminarse de la
tabla la columna correspondiente a dicha variable.

f) Hacer ceros los elementos restantes de la columna clave, con excepción del número clave.

Esto se logra mediante modificaciones matriciales consistentes en sumarle o restarle a cada renglón un
determinado número de veces el renglón clave, procedimiento conocido como Reducción de Gauss (Izar
Landeta,1998).

Procediendo entonces con el primer renglón, si se observa la última tabla, si se le resta a este renglón el
renglón clave multiplicado por 3, se generará un cero en el elemento correspondiente a la columna clave, con
esta modificación, se tendrá lo siguiente:

3.6 4 3 1 0 0 0
-3 (0.8 0.667 1 0 -0.333 0 0.333)
1.2 2 0 1 1 0 -1

Ahora para el segundo renglón, si se le resta el renglón clave, dará un cero en el respectivo elemento de la
columna clave, esto es:
40
1 1 1 0 0 1 0
- (0.8 0.667 1 0 -0.333 0 0.333)
0.2 0.333 0 0 0.333 1 -0.333

Ahora se pasa al renglón índice, primero en su parte numérica, donde se ve que si a éste se le suma 12
veces el renglón clave, dará un cero en el elemento correspondiente a la columna clave, con esto se tendrá:

0 -10 -12 0 0 0 0
+12 (0.8 0.667 1 0 -0.333 0 0.333)
9.6 -2 0 0 -4 0 4

Finalmente se va a la parte M del renglón índice, a la cual se le suma el renglón clave multiplicado por 4,
con esto se tendrá:

-3 -4 0 1 0 0
+4 (0.667 1 0 -0.333 0 0.333)
-0.333 0 0 -0.333 0 1.333

Con estos cambios, la tabla Simplex completa para esta iteración es:

10 12 0 0 -M
X1 X2 H1 H2 F1
0 H1 1.2 2 0 1 1 0
-M F1 0.2 0.333 0 0 0.333 1
12 X2 0.8 0.667 1 0 -0.333 0
9.6 -2 0 0 -4 0
-0.333 0 0 -0.333 0

Aquí ya se ha eliminado de la tabla a F2 tal y como se comentó en el inciso (e) anterior.

Esta nueva aproximación es:

Variables básicas Variables no básicas

H1 = 1.2 H2 =0
F1 = 0.2 X1 = 0
X2 = 0.8 F2 = 0
Z = 9.6

Si se compara esta solución con la anterior en lo concerniente a las variables no básicas, H 2 y X1

permanecen sin cambio y solamente X2 ha pasado a ser básica en lugar de F2. Cuando solamente una de las
variables no básicas cambie de una iteración a la siguiente, como en el caso presente, se dice que las 2
soluciones son adyacentes.

Esta solución es mejor que la anterior, pero todavía no es lo óptimo, puesto que sigue habiendo números
negativos en el renglón índice, por lo que se proseguirá con la metodología.

Paso 5. Repetir el paso 4 hasta encontrar el óptimo, el que se logrará cuando ya no existan números
negativos en ninguna de las partes del renglón índice; o bien detener el procedimiento si el problema es cíclico
(caso de degeneración) o no tiene solución, lo que se comentará más adelante.

Entonces se repetirá el paso 4, iniciando con el inciso (a):

a) Determinar la columna clave, que en este caso, si se observa la parte de M del renglón índice, se ve que
hay un empate entre la columna que encabeza X1 y la que encabeza H2, por lo que debe elegirse al azar una
 41
de ellas. En este caso, se toma la primera, para que X1 entre a la zona de solución, con esto la tabla Simplex
quedará de la manera siguiente:

10 12 0 0 -M
X1 X2 H1 H2 F1
0 H1 1.2 2 0 1 1 0
-M F1 0.2 0.333 0 0 0.333 1
12 X2 0.8 0.667 1 0 -0.333 0
9.6 -2 0 0 -4 0
-0.333 0 0 -0.333 0

b) Determinar el renglón clave, para esto se obtendrán los cocientes de los 3 primeros renglones:

Primer renglón, Cociente = 1.2/2 = 0.6

Segundo renglón, Cociente = 0.2/0.333 = 0.6
Tercer renglón, Cociente = 0.8/0.667 = 1.2

Aquí existe un empate entre el primero y el segundo renglón para ser nominados como renglón clave, por
lo que se debe seleccionar uno de ellos al azar. En este caso se toma al segundo renglón como clave, esto para
que la variable F1que encabeza este renglón deje de ser básica, con esto la tabla quedará en la siguiente forma:

10 12 0 0 -M
X1 X2 H1 H2 F1
0 H1 1.2 2 0 1 1 0
-M F1 0.2 0.333 0 0 0.333 1
12 X2 0.8 0.667 1 0 -0.333 0
9.6 -2 0 0 -4 0
-0.333 0 0 -0.333 0

c) El número clave en este caso es 0.333 que queda encuadrado por el renglón y la columna clave.

d) Para hacer el número clave la unidad, se divide el renglón clave entre 0.333, con esto sus elementos
serán:

0.6 1 0 0 1 3

e) Al hacer el cambio de variable, entrará X1 a la zona de solución y saldrá F1, con lo que al salir ésta, es
posible eliminarla de la tabla, con lo cual se tendrá:

10 12 0 0
X1 X2 H1 H2
0 H1 1.2 2 0 1 1
10 X1 0.6 1 0 0 1
12 X2 0.8 0.667 1 0 -0.333
9.6 -2 0 0 -4
-0.333 0 0 -0.333

f) Generar ceros en el resto de los elementos de la columna clave, para esto:

Al primer renglón se le resta el renglón clave multiplicado por 2, entonces:

42
1.2 2 0 1 1
-2 (0.6 1 0 0 1)
0 0 0 1 -1

Al tercer renglón se le resta el segundo renglón multiplicado por 0.667, entonces:

0.8 0.667 1 0 -0.333

-0.667 (0.6 1 0 0 1)
0.4 0 1 0 -1

Para la parte numérica del renglón índice, a ésta se le suma el renglón clave multiplicado por 2, con lo que
se tendrá:

9.6 -2 0 0 -4
+2 (0.6 1 0 0 1)
10.8 0 0 0 -2

Finalmente, para la parte M del renglón índice, se le suma a ésta el renglón clave multiplicado por 0.333
para obtener:

-0.333 0 0 -0.333
+0.333 ( 1 0 0 1 )
0 0 0 0

Aquí puede el lector percatarse que la parte M de renglón índice desaparece de la tabla Simplex al ser cero
todos sus elementos, esto se debe al hecho de que han desaparecido de la zona de solución las variables
artificiales.

Con estos cambios la tabla Simplex será ahora la siguiente:

10 12 0 0
X1 X2 H1 H2
0 H1 0 0 0 1 -1
10 X1 0.6 1 0 0 1
12 X2 0.4 0 1 0 -1
10.8 0 0 0 -2

Esta aproximación es:

Variables básicas Variables no básicas

H1 = 0 H2 = 0
X1 = 0.6
X2 = 0.4
Z = 10.8

Esta solución es mejor que la anterior.

Ahora la pregunta es: ¿ya es el óptimo?, aquí ha desaparecido la parte M del renglón índice, pero queda la
parte numérica de éste, en la cual puede verse que todavía hay un número negativo, por lo que la respuesta a la
pregunta anterior es negativa y por lo tanto, deberá irse a otra iteración repitiendo el paso 4.

a) Determinar la columna clave, en este caso será la que está encabezada por H2, pues es la única que
tiene un número negativo en el renglón índice.
 43
b) El renglón clave será el segundo (encabezado por X 1), pues es el único que tiene denominador positivo
y diferente de cero, con lo cual la tabla será:

10 12 0 0
X1 X2 H1 H2
0 H1 0 0 0 1 -1
10 X1 0.6 1 0 0 1
12 X2 0.4 0 1 0 -1
10.8 0 0 0 -2

c) Aquí el renglón clave quedará tal y como está, pues el número clave es la unidad, por lo tanto se omite
el inciso (d) y puede pasarse al (e).

e) Al hacer el cambio de variables, saldrá X1 de la zona de solución y entrará H2, con esto el renglón clave
completo será:

0 H2 0.6 1 0 0 1

f) Ahora se generarán los ceros en los elementos restantes de la columna clave.

Al primer renglón se le suma directamente el renglón clave:

0 0 0 1 -1
+(0.6 1 0 0 1)
0.6 1 0 1 0

Al tercer renglón se le suma también el renglón clave:

0.4 0 1 0 -1
+(0.6 1 0 0 1)
0 1 1 1 0 0

Al renglón índice se le suma el renglón clave multiplicado por 2:

10.8 0 0 0 -2
+2 (0.6 1 0 0 1)
12 2 0 0 0

Con estos cambios, la tabla Simplex queda de la siguiente manera:

10 12 0 0
X1 X2 H1 H2
0 H1 0.6 1 0 1 0
0 H2 0.6 1 0 0 1
12 X2 1 1 1 0 0
12 2 0 0 0

Esta opción ya es la óptima al no haber números negativos en el renglón índice y la solución es:

Variables básicas Variables no básicas

H1 = 0.6 X1 = 0
H2 = 0.6
44
X2 = 1
Z = 12

Una representación gráfica del ejemplo se muestra en la figura IV.1:

X
2
1.4 Figura IV.1 Gráfica del
ejemplo IV.1
1.2
Ec.(1)
V
4
1.0
V
2
0.8

0.6
V
3
0.4

0.2 Ec.(3)
Ec.(2)
V
1

0.2 0.4 0.6 0.8 1.0 1.2

X
1
En la figura se ven las rectas correspondientes a las restricciones, así como también los puntos que fue
tomando el método Simplex como aproximaciones a la solución llamados vértices y simbolizados por la letra
V en la figura.

La zona factible de solución es la línea recta de la ecuación 2 en el tramo comprendido entre V4 y V3,
justo donde se ha trazado una línea más gruesa, pues es la única parte que cumple con las 3 restricciones.

De este problema el Simplex inicia en el origen, punto V1 (X1 = 0, X2 = 0), el que como puede observarse
en la figura, queda fuera de la zona de solución, siendo por tanto una solución no factible, esto puede
señalarse desde la tabla Simplex para esta aproximación, por el hecho de haber variables artificiales que son
básicas, en este caso F1 = 1 y F2 = 2.4.

En la siguiente aproximación el Simplex va al punto V2 (X1 = 0, X2 = 0.8), el que tampoco es solución

factible, lo que puede notarse en la tabla Simplex respectiva, por el hecho de que F1 = 0.2 y dicha variable
sigue siendo básica.

Para la siguiente iteración el Simplex va al punto V3 (X1 = 0.6, X2 = 0.4), que ya está en la región factible
de solución, lo que en la tabla Simplex se muestra por el hecho de no haber ya variables artificiales básicas.

En la última iteración el método llega al punto V4 (X1 = 0, X2 = 1), el que representa la solución óptima
del problema.

Caso de Minimización

Ejemplo IV.2.- Resolver el problema

 45
Min Z = 8X1 + 7X2 + 9X3

Sujeto a:
2X1 + X2 + X3 > 5 (1)
X1 + 2X2 + 2X3 > 6 (2)
Siendo X1, X2, X3, no negativas.

Solución:
Se aplica la metodología Simplex, adaptándola al caso de minimización, entonces:

Paso 1. Se convierten las desigualdades de las restricciones en igualdades, conforme a la tabla IV.1. En
este problema las 2 restricciones son del tipo mayor o igual que (>), por lo que en cada una de ellas debe
incorporarse una variable de holgura con coeficiente -1 y una variable artificial con coeficiente +1, con estas
modificaciones las restricciones serán:

2X1 + X2 + X3 - H1 + F1 = 5 (1)
X1 + 2X2 + 2X3 - H2 + F2 = 6 (2)

Paso 2. Se incluyen las variables de holgura y artificiales en la ecuación de la función objetivo, con
coeficientes cero para H1 y H2, mientras que por su parte F1 y F2 tendrán +M por tratarse de un problema de
minimización, con esto la función objetivo vendrá dada por:

Min Z = 8X1 + 7X2 + 9X3 + 0H1 + 0H2 + MF1 + MF2

Paso 3. Se forma la primera tabla.

a) Se expresan las ecuaciones de las restricciones en función de sus coeficientes, así como el renglón de
variables, para obtener:

8 7 9 0 0 M M
X1 X2 X3 H1 H2 F1 F2
5 2 1 1 -1 0 1 0
6 1 2 2 0 -1 0 1

b) El renglón objetivo ya está presente en la tabla anterior, con los valores de los coeficientes de las
variables en la función objetivo.

c) La primera solución se da con F1 y F2, pues son las variables que tienen coeficiente +1 en la parte
identidad de la tabla, con esto se tiene:

8 7 9 0 0 M M
X1 X2 X3 H1 H2 F1 F2
M F1 5 2 1 1 -1 0 1 0
M F2 6 1 2 2 0 -1 0 1

d) Ahora debe generarse el renglón índice, para este caso de minimización la fórmula (IV.1) se modifica y
queda con los signos cambiados en el segundo miembro, es decir:
46

Número El elemento correspon- Sumatoria de los productos

= de los elementos de la co-
Indice diente a la columna en lumna por el respectivo e-
el renglón objetivo lemento en la columna ob-
jetivo

Ec. (IV.2)

Al aplicar esta fórmula a cada elemento se obtiene lo siguiente:

Columna que encabeza X1: Número índice = 8 - (Mx2 + Mx1) = 8 - 3M

Columna que encabeza X2: Número índice = 7 - (Mx1 + Mx2) = 7 - 3M
Columna que encabeza X3: Número índice = 9 - (Mx1 + Mx2) = 9 - 3M
Columna que encabeza H1: Número índice = 0 -[ Mx (-1) + Mx0] = M
Columna que encabeza H2: Número índice = 0 -[ Mx0 + Mx(-1)] = M
Columna que encabeza F1: Número índice = M- (Mx1 + Mx0) = 0
Columna que encabeza F2: Número índice = M - (Mx0 + Mx1) = 0
Columna de constantes: Número índice (utilidad) = 0 - (Mx5 + Mx6) = -11M

Al descomponer los números índice en sus parte numérica y de M e incluirlos en la tabla Simplex, se tiene:

8 7 9 0 0 M M
X1 X2 X3 H1 H2 F1 F2
M F1 5 2 1 1 -1 0 1 0
M F2 6 1 2 2 0 -1 0 1
0 8 7 9 0 0 0 0
-3 -3 -3 1 1 0 0

Aquí se ha omitido el -11M del elemento correspondiente a la columna de constantes.

Entonces la primera solución es la de la parte básica de la tabla, es decir:

Variables básicas Variables no básicas

F1 = 5 X1 = 0
F2 = 6 X2 = 0
Z=0 H1 = 0
H2 = 0

Como puede verse en la tabla Simplex, esta primera aproximación no es el óptimo, pues aparecen números
negativos en el renglón índice, por tanto se continua con la metodología en el paso 4.

Paso 4. Ir a la siguiente iteración para mejorar la aproximación inicial.

a) Para determinar la columna clave, se ve de la tabla que hay un triple empate, por lo que se selecciona
arbitrariamente a la columna encabezada por X2:

8 7 9 0 0 M M
X1 X2 X3 H1 H2 F1 F2
M F1 5 2 1 1 -1 0 1 0
M F2 6 1 2 2 0 -1 0 1
0 8 7 9 0 0 0 0
-3 -3 -3 1 1 0 0
 47
b) Se calculan los cocientes de los 2 renglones de las restricciones, para saber cual es el clave:

Para el primer renglón:

5
Cociente  5
1
Para el segundo renglón:
6
Cociente  3
2
Por lo que este último es el renglón clave, lo que ya aparece señalado en la tabla anterior.

c) El número clave es el 2, que aparece encuadrado en la tabla.

d) Para hacer el número clave igual a la unidad, se divide el renglón clave entre 2, con este cambio, el
renglón quedará de la manera siguiente:

3 0.5 1 1 0 -0.5 0 0.5

e) Se cambia de variable sacando a F2 y su contribución de la zona de solución, e introduciendo a X 2 y su

contribución. Además de acuerdo a la metodología Simplex de 2 fases, se elimina la columna de F2 de la
tabla, quedando de la siguiente forma:

8 7 9 0 0 M
X1 X2 X3 H1 H2 F1
M F1 5 2 1 1 -1 0 1
7 X2 3 0.5 1 1 0 -0.5 0
0 8 7 9 0 0 0
-3 -3 -3 1 1 0

f) Se hacen ceros los elementos de la columna clave con excepción del número clave, para lo cual se
procede con las operaciones:

Al primer renglón, se le resta el renglón clave:

5 2 1 1 -1 0 1
- (3 0.5 1 1 0 -0.5 0)
2 1.5 0 0 -1 0.5 1

A la parte numérica del renglón índice, se le resta el renglón clave multiplicado por 7:

0 8 7 9 0 0 0
-7 (3 0.5 1 1 0 -0.5 0)
-21 4.5 0 2 0 3.5 0

A la parte M del renglón índice, se le suma 3 veces el renglón clave:

-3 -3 -3 1 1 0
+3 (0.5 1 1 0 -0.5 0)
-1.5 0 0 1 -0.5 0

Con estos cambios la tabla Simplex será ahora:

48
8 7 9 0 0 M
X1 X2 X3 H1 H2 F1
M F1 2 1.5 0 0 -1 0.5 1
7 X2 3 0.5 1 1 0 -0.5 0
-21 4.5 0 2 0 3.5 0
-1.5 0 0 1 -0.5 0

Y la nueva solución es:

Variables básicas Variables no básicas

F1 = 2 X1 = 0
X2 = 3 X3 = 0
Z = 21 H1 = 0
H2 = 0

Aquí debe aclararse que Z no es -21 como aparece en la tabla Simplex, sino +21 puesto que la
metodología Simplex presenta Z con el signo invertido cuando se trata de problemas de minimización.

De esta aproximación, se observa que no es el óptimo, puesto que aún hay números negativos en el renglón
índice, por lo que debe pasarse a otra iteración, repitiendo el paso 4, iniciando con el inciso (a).

a) La columna clave será ahora la que está encabezada por X1, puesto que contiene al número índice más
negativo.

b) Calculando los cocientes, se tiene:

Primer renglón:
2
Cociente   1.333
1.5
Segundo renglón:
3
Cociente 6
0.5
Por lo que el renglón clave será el primero, quedando la tabla así:

8 7 9 0 0 M
X1 X2 X3 H1 H2 F1
M F1 2 1.5 0 0 -1 0.5 1
7 X2 3 0.5 1 1 0 -0.5 0
-21 4.5 0 2 0 3.5 0
-1.5 0 0 1 -0.5 0

c) El número clave es 1.5, pues pertenece al renglón y a la columna clave.

d) Si se divide el renglón clave entre 1.5, éste queda de la siguiente manera:

1.333 1 0 0 -0.667 0.333 0.667

e) Con el cambio de variable, sale F1 y entra X1, con esto y eliminando de una vez a F1 de la tabla, ésta
queda del modo siguiente:

8 7 9 0 0
X1 X2 X3 H1 H2
 49
8 X1 1.333 1 0 0 -0.667 0.333
7 X2 3 0.5 1 1 0 -0.5
-21 4.5 0 2 0 3.5
-1.5 0 0 1 -0.5

f) Ahora hay que generar los ceros en los restantes elementos de la columna clave, de la siguiente manera:

Al segundo renglón, se le resta el renglón clave multiplicado por 0.5:

3 0.5 1 1 0 -0.5
-0.5 (1.333 1 0 0 -0.667 0.333 )
2.333 0 1 1 0.333 -0.667

A la parte numérica del renglón índice, se le resta el renglón clave multiplicado por 4.5:

-21 4.5 0 2 0 3.5

-4.5 (1.333 1 0 0 -0.667 0.333 )
-27 0 0 2 3 2

Finalmente a la parte M del renglón índice, se le suma el renglón clave multiplicado por 1.5:

-1.5 0 0 1 -0.5
+1.5 ( 1 0 0 -0.667 0.333 )
0 0 0 0 0

Con estas modificaciones la tabla es:

8 7 9 0 0
X1 X2 X3 H1 H2
8 X1 1.333 1 0 0 -0.667 0.333
7 X2 2.333 0 1 1 0.333 -0.667
-27 0 0 2 3 2
0 0 0 0 0

Aquí puede verse que la parte M del renglón índice desaparece al hacerse cero todos sus elementos, pues
ya no hay ninguna variable artificial en la zona de solución.

Además en la parte numérica de este mismo renglón, ya no hay números negativos, por lo que esta
aproximación ha resultado ser el óptimo, con la siguiente solución:

Variables básicas Variables no básicas

X1 = 1.333 X3 = 0
X2 = 2.333 H1 = 0
Z = 27 H2 = 0

Una representación gráfica del ejemplo se muestra en la figura IV.2, la que se presenta en 3 dimensiones,
puesto que hay 3 variables de decisión. Cada ecuación de las restricciones es un plano en forma de triángulo
que corta el espacio tridimensional.

Como en el presente caso las restricciones son del tipo mayor o igual que (>), la región factible de solución
será la exterior a los 2 planos. La línea más externa de éstos se muestra en la figura con un trazo más grueso,
de esta manera todo el espacio que quede de dichas líneas hacia afuera será la zona de solución factible.
50
El método inicia en el origen, señalado como el punto V1 en la figura donde X1 = 0, X2 = 0, X3 = 0. Este
punto queda dentro de los planos, por lo tanto no está en la región factible de solución, lo que era notorio
desde la tabla Simplex, por el hecho de tener a F1= 5 y F2 = 6 como variables básicas.

En la siguiente iteración el método va al punto V2 (X1 = 0, X2 = 3, X3 =0), que tampoco está en la zona
factible de solución, pues tiene a F1 = 2 como variable básica.

X
2
Figura IV.2 Gráfica del
ejemplo IV.2

Ec.(1) V
2
V
3

Ec.(2)
V
O 1
X
1

X
3

Finalmente en la siguiente iteración el método pasa a V3 (X1 = 1.333, X2 = 2.333, X3 = 0), el que sí está
ubicado en la región factible de solución y satisface la prueba de optimalidad, siendo la solución del
problema.

A continuación se presenta otro ejercicio.

Ejemplo IV.3.- Resolver:

Max Z = 8X1 + 6X2
Sujeto a:

4X1 + 3X2 < 3 (1)

X1 + 2X2 < 1.5 (2)
X1 + X 2 = 1 (3)

Solución:
Se aplica la metodología Simplex:

Paso 1. Convertir las desigualdades en igualdades. Las dos primeras restricciones son del tipo menor o
igual que, por lo que conforme a la tabla IV.1, se agrega una variable de holgura en cada una de ellas,
mientras que en la tercera restricción, que es de igualdad, se añade una variable artificial.

4X1 + 3X2 + H1 = 3 (1)

X1 + 2X2 + H2 = 1.5 (2)
X1 + X2 + F1 = 1 (3)
 51

Paso 2. Se incorporan las variables agregadas en el paso anterior a la función objetivo con sus
contribuciones respectivas:

Max Z = 8X1 + 6X2 + 0H1 + 0H2 - M F1

Aquí el signo de M es negativo por tratarse de un problema de maximización.

Paso 3. Se forma la primera tabla.

a) Poner el renglón de variables y las ecuaciones de las restricciones, para obtener:

8 6 0 0 -M
X1 X2 H1 H2 F1
3 4 3 1 0 0
1.5 1 2 0 1 0
1 1 1 0 0 1

b) Ya se ha agregado el renglón objetivo a la tabla.

c) Se da la primera solución en función de las variables con coeficiente uno en la parte identidad, es decir,
H1, H2 y F1, con esto se tiene:

8 6 0 0 -M
X1 X2 H1 H2 F1
0 H1 3 4 3 1 0 0
0 H2 1.5 1 2 0 1 0
-M F1 1 1 1 0 0 1

d) Formar el renglón índice, aplicando la ecuación (IV.1):

Columna encabezada por X1: Número índice = [ 0x4 + 0x1 + (-M)x1 ] -8 = -M - 8

Columna encabezada por X2: Número índice = [ 0x3 + 0x2 + (-M)x1 ] - 6 = -M - 6
Columna encabezada por H1: Número índice = [ 0x1 + 0x0 + (-M)x0 ] - 0 = 0
Columna encabezada por H2: Número índice = [ 0x0 + 0x1 + (-M)x0] -0 = 0
Columna encabezada por F1: Número índice = [ 0x0 + 0x0 + (-M)x1 ] - (-M) = 0
Columna de constantes: Número índice = [ 0x3 +0x1.5 + (-M)x1 ] -0 = -M

Al incorporar estos elementos con sus 2 partes, numérica y de M a la tabla, se tiene:

8 6 0 0 -M
X1 X2 H1 H2 F1
0 H1 3 4 3 1 0 0
0 H2 1.5 1 2 0 1 0
-M F1 1 1 1 0 0 1
0 -8 -6 0 0 0
-1 -1 0 0 0

Sin incluir la parte M de la columna de constantes, la siguiente es la primera solución:

Variables básicas Variables no básicas

H1 = 3 X1 =0
H2 = 1.5 X2 = 0
52
F1 = 1
Z=0

Paso 4. Como hay números negativos en el renglón índice, se sigue con otra iteración.

a) Determinar la columna clave. En la parte M del renglón índice, se ve que hay un empate entre las
columnas encabezadas por X1 y X2, por lo que al azar se escoge la primera de ellas.

b) Determinar el renglón clave. Para esto se calculan los cocientes de los 3 renglones de restricciones:

Para el primer renglón:

3
Cociente   0.75
4
Para el segundo renglón:
1.5
Cociente   1.50
1
Para el tercer renglón:
1
Cociente   1.0
1
Por lo cual el primer renglón es el clave, quedando la tabla así:

8 6 0 0 -M
X1 X2 H1 H2 F1
0 H1 3 4 3 1 0 0
0 H2 1.5 1 2 0 1 0
-M F1 1 1 1 0 0 1
0 -8 -6 0 0 0
-1 -1 0 0 0

c ) Por lo anterior el número clave es el 4 que pertenece al renglón y a la columna clave.

d ) Se divide el renglón clave entre 4, con esto queda del modo siguiente:

0.75 1 0.75 0.25 0 0

e) Se cambia ahora de variable sacando a H1 y reemplazándola por X1, con esto la tabla quedará así:

8 6 0 0 -M
X1 X2 H1 H2 F1
8 X1 0.75 1 0.75 0.25 0 0
0 H2 1.5 1 2 0 1 0
-M F1 1 1 1 0 0 1
0 -8 -6 0 0 0
-1 -1 0 0 0

f) Se hacen ceros los elementos restantes de la columna clave:

Al segundo renglón, se le resta el renglón clave, para obtener:

1.5 1 2 0 1 0
 53
- ( 0.75 1 0.75 0.25 0 0 )
0.75 0 1.25 -0.25 1 0

Al tercer renglón, se le resta el clave, lo cual da lo siguiente:

1 1 1 0 0 1
- ( 0.75 1 0.75 0.25 0 0 )
0.25 0 0.25 -0.25 0 1

A la parte numérica del renglón índice, se le suma el renglón clave multiplicado por 8:

0 -8 -6 0 0 0
+8 ( 0.75 1 0.75 0.25 0 0 )
6.0 0 0 2 0 0

A la parte M del renglón índice, se le suma el renglón clave:

-1 -1 0 0 0
+ ( 1 0.75 0.25 0 0 )
0 -0.25 0.25 0 0

Con esto la tabla Simplex de esta nueva aproximación es:

8 9 0 0 -M
X1 X2 H1 H2 F1
8 X1 0.75 1 0.75 0.25 0 0
0 H2 0.75 0 1.25 -0.25 1 0
-M F1 0.25 0 0.25 -0.25 0 1
6.0 0 0 2 0 0
0 -0.25 0.25 0 0

Que es la nueva iteración, siendo la solución de la misma:

Variables básicas Variables no básicas

X1 = 0.75 X2 = 0
H2 = 0.75 H1 = 0
F1 = 0.25
Z = 6.0

En vista de que esta nueva aproximación no es la óptima, se debe repetir el paso 4, entonces:

a) La columna clave será la que está encabezada por X2, pues es la única que posee un elemento negativo
del renglón índice en su parte M.

b) Se obtienen los cocientes para hallar el renglón clave:

Para el primer renglón:

0.75
Cociente   1.0
0.75
Para el segundo renglón:
54
0.75
Cociente   0.6
1.25
Para el tercer renglón:
0.25
Cociente   1.0
0.25
Por lo tanto el segundo renglón es el clave:

8 6 0 0 -M
X1 X2 H1 H2 F1
8 X1 0.75 1 0.75 0.25 0 0
0 H2 0.75 0 1.25 -0.25 1 0
-M F1 0.25 0 0.25 -0.25 0 1
6.0 0 0 2 0 0
0 -0.25 0.25 0 0

c) El número clave es 1.25.

d) Si se divide el renglón clave entre 1.25, se obtiene:

0.6 0 1 -0.2 0.8 0

e) El cambio de variable será sacando a H2 de la zona de solución e introduciendo a X2, con lo cual se
tiene:

8 6 0 0 -M
X1 X2 H1 H2 F1
8 X1 0.75 1 0.75 0.25 0 0
6 X2 0.6 0 1 -0.2 0.8 0
-M F1 0.25 0 0.25 -0.25 0 1
6.0 0 0 2 0 0
0 -0.25 0.25 0 0

f) Ahora se generan los ceros en los elementos restantes de la columna clave.

Al primer renglón, se le resta el renglón clave multiplicado por 0.75:

0.75 1 0.75 0.25 0 0

-0.75 ( 0.6 0 1 -0.2 0.8 0 )
0.3 1 0 0.4 -0.6 0

Al tercer renglón, se le resta el clave multiplicado por 0.25:

0.25 0 0.25 -0.25 0 1

-0.25 ( 0.6 0 1 -0.2 0.8 0 )
0.1 0 0 -0.2 -0.2 1

A la parte numérica del renglón índice, no se le hará ninguna modificación, dado que el elemento
correspondiente a la columna clave ya es un cero.

A la parte M del renglón índice, se le suma el renglón clave multiplicado por 0.25:
 55
0 -0.25 0.25 0 0
+0.25 (0 1 -0.20 0.8 0 )
0 0 0.20 0.20 0

Con estos cambios la tabla Simplex será:

8 6 0 0 -M
X1 X2 H1 H2 F1
8 X1 0.3 1 0 0.4 -0.6 0
6 X2 0.6 0 1 -0.2 0.8 0
-M F1 0.1 0 0 -0.2 -0.2 1
6.0 0 0 2 0 0
0 0 0.2 0.2 0

En esta tabla puede verse que ya no hay números negativos en el renglón índice, por lo que esta solución
será la óptima, pero hay un problema: La variable artificial F1 aún permanece en la zona de solución, es decir,
continúa como variable básica, esto significa que este problema no tiene solución factible, debido al tipo de
restricciones y esto puede comprobarse de una manera simple: Con la aparente solución de esta tabla:

X1 = 0.3
X2 = 0.6
Z = 6.0

Debe checarse si se respetan las restricciones:

(1) 4X1 + 3X2 < 3

4(0.3) + 3(0.6) < 3
1.2 + 1.8 < 3
3 < 3, sí se cumple

(2) X1 + 2X2 < 1.5

0.3 + 2(0.6) < 1.5
0.3 + 1.2 < 1.5
1.5 < 1.5, sí se cumple

(3) X 1 + X2 = 1
0.3 + 0.6 = 1
0.9 = 1, NO SE CUMPLE

Por esto la aparente solución del problema no cumple con las restricciones, siendo entonces una solución
no factible.

En la figura IV.3 se presenta una gráfica del ejemplo para ilustrar esta situación, donde el área sombreada
representa la zona de solución que satisface a las 2 primeras restricciones. Pero la tercera restricción indica
que la solución debe quedar sobre la recta correspondiente a su ecuación, en la figura es la línea de la
ecuación (3).

Puede verse con claridad que dicha línea no toca en ningún momento al área sombreada, por lo que no
existe ningún punto que satisfaga a todas las restricciones.

Por su parte la secuencia del método Simplex fue la siguiente:

Inicia en el origen, punto V1 (X1 =0, X2 = 0), luego pasa al punto V2 (X1=0.75, X2=0) y finalmente va al
punto V3 (X1 = 0.3, X2 = 0.6) donde aparentemente termina con la solución óptima.
56
X
2
Figura IV.3 Gráfica del ejemplo
IV.3
1.25

1.00

0.75
V
3
0.50

Ec(1)
0.25
Ec(2)
V V Ec(3)
1 2
O
X
0.25 0.50 0.75 1.0 1.25 1.5 1.75 2.0 1

Ejemplo IV.4.- Resolver:

Max Z = 6X1 + 4X2
Sujeto a:

X1 + 2X2 < 4 (1)

3X1 + 2X2 < 8 (2)
Con X1 y X2 no negativas

Solución:
Paso 1. Se convierten las desigualdades en igualdades agregando variables de holgura, según el tipo de
restricciones, con lo cual se tendrá:

X1 + 2X2 + H1 = 4 (1)
3X1 + 2X2 + H2 = 8 (2)

Paso 2. Se incorporan las variables de holgura en la función objetivo, con sus contribuciones:

Max Z = 6X1 + 4X2 + 0H1 + 0H2

Paso 3. Se forma la primera tabla:

a) Se incluye el renglón de variables y las ecuaciones de las restricciones, para obtener:

6 4 0 0
X1 X2 H1 H2
0 H1 4 1 2 1 0
0 H2 8 3 2 0 1

b) El renglón objetivo ya fue incluido en la tabla.

c) La primera solución se da en función de las variables H1 y H2 como aparece en la tabla anterior.

d) Se forma el renglón índice al aplicar la ecuación (IV.1) al caso presente:

 57

Columna encabezada por X1 Número índice = ( 0x1 + 0x3) -6 = -6

Columna encabezada por X2 Número índice = (0x2 + 0x2) -4 = -4
Columna encabezada por H1 Número índice = (0x1 + 0x0 )-0 = 0
Columna encabezada por H2 Número índice = (0x0 + 0x1) - 0= 0
Columna de constantes Número índice = (0x4 + 0x8) - 0 = 0

Por lo tanto, al incluir estos elementos en la tabla Simplex, se tendrá:

6 4 0 0
X1 X2 H1 H2
0 H1 4 1 2 1 0
0 H2 8 3 2 0 1
0 -6 -4 0 0

Aquí debe notarse que no hubo parte M del renglón índice, esto debido a que no existen variables
artificiales.

Entonces la primera solución es:

Variables básicas Variables no básicas

H1 = 4 X1 = 0
H2 = 8 X2 = 0
Z=0

Como se ve en la tabla, esta aproximación no es la óptima, por tanto debe irse a una nueva iteración con el
paso 4.

a) La columna clave será la encabezada por X1 al poseer el número índice más negativo.

b) Se obtienen los cocientes de los dos renglones para determinar el renglón clave:

Primer renglón:
4
Cociente  4
1
Segundo renglón:
8
Cociente   2.667
3
Por tanto el renglón clave es el segundo, tal como se muestra en la tabla:

6 4 0 0
X1 X2 H1 H2
0 H1 4 1 2 1 0
0 H2 8 3 2 0 1
0 -6 -4 0 0

c) El número clave es el 3.

d) Si se divide el renglón clave entre 3, se obtiene:

2.667 1 0.667 0 0.333

58

e) Se cambia de variable sacando a H2 e introduciendo a X1:

6 4 0 0
X1 X2 H1 H2
0 H1 4 1 2 1 0
6 X1 2.667 1 0.667 0 0.333
0 -6 -4 0 0

f) Se generan los ceros en los restantes elementos de la columna clave.

Al primer renglón, se le resta el renglón clave:

4 1 2 1 0
- ( 2.667 1 0.667 0 0.333 )
1.333 0 1.333 1 -0.333

Al renglón índice, se le suma el clave multiplicado por 6:

0 -6 -4 0 0
+6 ( 2.667 1 0.667 0 0.333 )
16 0 0 0 2

Con estos cambios la tabla Simplex será:

6 4 0 0
X1 X2 H1 H2
0 H1 1.333 0 1.333 1 -0.333
6 X1 2.667 1 0.667 0 0.333
16 0 0 0 2

Esta aproximación ya es el óptimo, siendo la solución:

Variables básicas Variables no básicas

H1 = 1.333 H2 = 0
X1 = 2.667 X2 = 0
Z = 16.0

Aquí es conveniente comentar lo siguiente:

Siempre que una variable no básica tenga en la tabla Simplex final como coeficiente del renglón índice un
cero, significa que hay varias soluciones óptimas alternas.

En este caso, si se observa la tabla Simplex, se ve que X2 no es variable básica y su coeficiente en el

renglón índice de la tabla final es cero, por tanto, este ejemplo tiene soluciones óptimas alternas.

Esto se debe a que una de las restricciones, en este caso la (2), es paralela a la función objetivo, lo cual
hace que existan varias soluciones óptimas donde la recta de la función objetivo intersecta con dicha
restricción.

Esto se muestra gráficamente en la figura IV.4:

 59
X
2
Figura IV.4 Gráfica del ejemplo
IV.4
5.0
(1) Z=6X +4X =12
1 2
(2) Z=6X +4X =14
4.0 Ec.(2) 1 2

3.0
(2)

2.0
P
1.0 (1)
Ec.(1)
V V
1 2
O X
1
1.0 2.0 3.0 4.0 5.0 6.0

En dicha gráfica las líneas continuas representan las restricciones y las punteadas son dos valores de la
función objetivo, en Z = 12 la (1) y en Z = 14 la (2).

Como puede verse, estas rectas son paralelas a la línea correspondiente a la restricción número 2, de tal
forma que la recta de la función objetivo para Z=16, coincide con la segunda restricción siendo el máximo
valor posible dentro de la zona factible de solución, por eso el resultado ha dado Z = 16.

Sin embargo, habrá varias soluciones óptimas a lo largo de la recta de la segunda restricción desde el
punto P hasta el punto V2. Arriba del punto P ya no se cumple con la primera restricción, por eso se excluye
esta porción de la recta como zona factible de solución.

Este ejemplo es una clara muestra del caso de la existencia de soluciones óptimas alternas.

En cuanto a las iteraciones del método Simplex, éste inicia en el origen, punto V1 (X1 = 0, X2 = 0) como
primera solución, pasando luego al punto V2 (X1 = 2.667, X2 = 0), donde se ha encontrado la solución
óptima rápidamente.

Casos especiales del Método Simplex

En este apartado se presentan casos especiales que suelen aparecer al momento de solucionar problemas de
programación lineal con la metodología Simplex, como es el caso de desempates en la columna o el renglón
claves, cuando no hay variable básica de salida, cuando aparecen términos negativos en las restricciones y los
precios sombra.

Desempates
a).- Empate en la columna clave (variable que entra). En este caso se seleccionará cualquier columna que
se desee, esto en lo único que podrá afectar al desarrollo del método Simplex, será en el número de iteraciones
necesarias para alcanzar la solución óptima.
60
b).- Empate en el renglón clave (variable que sale). En este caso existen reglas para determinar cuál
renglón de los que están empatados debe elegirse como clave. Sin embargo, para fines prácticos se
recomienda seleccionar al azar. El problema en que puede incurrirse cuando se elige el renglón indebido es
que el método vaya de un primero a un segundo vértice, sin cambio en la función objetivo y luego regrese del
segundo al primero en la iteración siguiente, haciéndose esto un ciclo indefinido que nunca llegará a la
solución. En este caso se dice que existe degeneración del Simplex. No obstante, este caso es muy poco usual
en los problemas prácticos y se resuelve simplemente por cambiar el renglón que se eligió como clave por otro
que haya resultado empatado con él.

No hay variable básica de salida (Z no acotada)

Esto sucede cuando todos los elementos de la columna clave son menores o iguales que cero en alguna tabla
intermedia del desarrollo de la metodología Simplex, no pudiendo de esta manera ser seleccionados para
determinar el renglón clave. Se dice que en este caso la Z podría ser infinita o bien negativa, de aquí el porqué
suele llamársele a este tipo de casos como problemas de Z no acotada. Estas situaciones se presentan por
cometer algún error en el planteamiento del problema, o en los cálculos efectuados durante la resolución del
mismo, debiendo entonces revisarse cuidadosamente el caso para encontrar la falla y corregirla. Cuando se da
la situación de una Z negativa, el problema puede volver a ser planteado, debiendo entonces cambiarse todos
los signos de los coeficientes de las variables de decisión en las ecuaciones de las restricciones, lo que da
como resultado obtener la función objetivo con signo positivo (Davis y McKeown, 1986).

Términos negativos en el segundo miembro de las ecuaciones de las restricciones

Hasta ahora se han visto únicamente casos de valores positivos en el segundo miembro de las restricciones. Si
hubiera números negativos, como por ejemplo los siguientes:

X1 - 2X2 = -2 (1)
-2X1 + X2 > -1 (2)
-X1 - X2 < -3 (3)

Lo que debe hacerse, es multiplicar ambos lados de las restricciones por (-1) y en el caso de las
desigualdades invertir el sentido de las mismas, con estos cambios se tendría:

- X1 + 2X2 = 2 (1)
2X1 - X2 < 1 (2)
X1 + X 2 > 3 (3)

Las cuales ya pueden ser manejadas por el método Simplex en la manera usual.

Precios sombra
Estos representan la relación de aumento que tendría la función objetivo por el hecho de aumentar en una
unidad la constante de una restricción dada, o sea el incremento en el recurso correspondiente para esa
restricción (Gallagher y Watson, 1992). Así en el caso del ejemplo IV.4, cuyo planteamiento fue:

Max Z = 6X1 + 4X2

Sujeto a:
X1 + 2X2 < 4 (1)
3X1 + 2X2 < 8 (2)
Con X1, X2 no negativas
La tabla final fue:

6 4 0 0
X1 X2 H1 H2
0 H1 1.333 0 1.333 1 -0.333
6 X1 2.667 1 0.667 0 0.333
16 0 0 0 2
 61

Los precios sombra aparecen en la tabla final con los coeficientes de las variables de holgura en el renglón
índice, así para H1, dicho coeficiente es cero y para H2 es 2, es decir que el precio sombra para la primera
restricción es cero y para la segunda es 2.

Esto significa para el primer caso, que la función objetivo Z no aumentará si aumentamos la constante de
la ecuación de la primera restricción en una unidad, o sea si fuese 5 en lugar de 4, pues si ésta fuera la
situación, la solución óptima sería:

X1 = 2.667, X2 = 0, H1 = 2.333, H2 = 0, Z = 16

Donde puede verse que la Z no cambia (incremento cero).

Por otra parte, para la segunda restricción, el precio sombra de 2, indica que Z aumentará en 2 unidades
por cada unidad de incremento en el coeficiente de la restricción, o sea, que si éste fuese 9 en lugar de 8, la
nueva solución óptima sería:
X1 = 3, X2 = 0, H1 = 1, H2 = 0, Z = 18

Donde puede verse que Z ha aumentado en 2 unidades respecto al problema original.

Los precios sombra por tanto, indican un valor marginal de incremento en la función objetivo con respecto
a un recurso dado, lo cual los hace una información de gran utilidad para analizar el impacto de cambios en
los sistemas operativos.

Dualidad
La dualidad puede definirse con el siguiente enunciado: Para todo problema de maximización de
programación lineal, habrá otro problema asociado de minimización y por otra parte, para todo problema
de minimización, habrá otro problema asociado de maximización.

Al primer problema se le llama primario y al problema asociado correspondiente se le conoce como dual.

En este capítulo se verá cómo plantear un problema dual, dado un problema primario cualquiera.

Importancia
La dualidad es importante por las siguientes razones (Hillier y Lieberman, 1991):

1.- El problema dual puede ahorrar un número considerable de cálculos, en particular cuando el problema
primario tiene muchas restricciones y pocas variables lo que implica un número elevado de cálculos para su
resolución por el método Simplex.
2.- La dualidad tiene una relación importante con el análisis de sensibilidad que se verá más adelante en
este mismo capítulo. Esto es muy útil para analizar cómo puede cambiar la función objetivo ante variaciones
en las diferentes condiciones del problema de programación lineal.
3.- El problema dual proporciona información importante sobre la manera óptima de aplicar recursos que
son escasos a fin de obtener beneficios económicos.

El problema Dual
El planteamiento del problema dual para un problema primario cualquiera, puede hacerse basado en los
siguientes puntos (Davis y McKeown, 1986):

1.- Se invierte el sentido de la función objetivo. Si el problema primario es de

maximización, el problema dual será de minimización y viceversa.
2.- Se invierte el sentido de las desigualdades de las restricciones. Esto es, si las
restricciones del problema primario son del tipo menor o igual que (<), en el problema
dual las restricciones serán del tipo mayor o igual que (>) y viceversa.
62
3.- Los coeficientes de la función objetivo del problema primario pasan a ser las
constantes de las restricciones del problema dual.
Esto implica que el problema dual tendrá tantas restricciones como variables tenga el
primario.
4.- Las constantes de las restricciones del problema primario pasan a ser los coeficientes
de la función objetivo del problema dual.
Esto significa que el dual tendrá tantas variables como restricciones tenga el primario.
5.- Los coeficientes de las restricciones del problema primario se colocan de tal forma
que los renglones del primario pasarán a ser las columnas del problema dual y con este
cambio las columnas del primario serán los renglones del dual.
6.- Las variables del problema primario se denominarán como X, mientras que las del
problema dual serán Y, debiendo ser no negativas.

A continuación se ilustran estos puntos con un ejemplo.

Ejemplo IV.5.- Una panadería prepara 2 tipos de pan, uno con mermelada y el otro con cajeta. Hay
mermelada para preparar hasta 5 kilos del primer tipo de pan y cajeta para 8 kilos del segundo tipo. El
primer tipo requiere de 2 unidades de harina, mientras que el segundo tipo sólo una. El expendio cuenta con
un total de 15 unidades de harina.

El primer tipo de pan deja una utilidad de $ 30 por kilo y el segundo tipo $ 40 por kilo.

¿Cuántos kilogramos de cada tipo debe preparar el expendio a fin de maximizar sus utilidades?

Plantear el problema primario y luego el dual para este caso.

Solución:
Para el problema primario habrá 2 variables, X1 y X2, siendo:

X 1 = Kilos de pan del primer tipo

X 2 = Kilos de pan del segundo tipo
ZP = Utilidad en $

Entonces la función objetivo será:

Max ZP = 30 X1 + 40 X 2

Aquí 30 y 40 son los coeficientes de la función objetivo, representando la utilidad de cada tipo de pan en
$/kilogramo.

Las restricciones son:

(1) X 1< 5 Cantidad disponible de mermelada

(2) X2<8 Cantidad disponible de cajeta
(3) 2X 1 + X 2 < 15 Cantidad disponible de harina
Siendo X1, X2 No negativas.

Para el problema dual se aplica la metodología descrita antes. De acuerdo al primer punto, el problema
dual será de minimización, dado que el primario fue de maximización. Conforme al segundo punto, para el
problema dual se tendrán restricciones del tipo mayor o igual que (>), dado que las del primario son del tipo
menor o igual que (<).

Ahora se pasa al punto 3, los coeficientes de la función objetivo del primario, que son 30 y 40, serán ahora
las constantes de las restricciones del dual, teniendo éste por lo tanto 2 restricciones.
 63
De acuerdo al punto 4, las constantes de las restricciones del primario son 5, 8 y 15, por lo que éstos serán
los coeficientes de la función objetivo del problema dual, que tendrá 3 variables.

Ahora conforme al punto 5, los coeficientes de las restricciones para el primario son:

1 0
0 1
2 1

Los cuales deben transponerse para el dual, es decir, colocar los renglones como columnas, con esto se
tendrá:
1 0 2
0 1 1

Que serán ahora los coeficientes de las 2 restricciones del dual.

Finalmente de acuerdo al paso 6, habrá 3 variables para el problema dual, las cuales serán Y 1, Y2 y Y3.

Con esto el planteamiento del dual es:

Min ZD = 5 Y1 + 8Y2 + 15 Y3

Con las restricciones:

(1) Y1 + 2 Y3 > 30
(2) Y2 + Y3 > 40
Siendo Y1, Y2 y Y3 No negativas

Aquí es importante señalar que las variables duales son costos marginales de los recursos utilizados, para
el caso del ejemplo anterior se tiene:

Y1 = Costo marginal de la mermelada, $/unidad de mermelada

Y2 = Costo marginal de la cajeta, $/unidad de cajeta
Y3 = Costo marginal de la harina, $/unidad de harina

Por eso el objetivo del problema dual es ahora el de minimizar el consumo de los recursos disponibles, es
decir la ZD que es el costo por este concepto.

A continuación se presenta un ejemplo con la resolución de los problemas primario y dual del caso
anterior.

Ejemplo IV.6.- Resolver los problemas primario y dual del ejemplo anterior.

Solución:
Para ambos problemas se utilizará la metodología Simplex.

Para el primario se tienen que agregar variables de holgura, una por cada restricción, con una contribución
a la función objetivo de cero, es decir:

Max Zp = 30 X1 + 40 X2 + 0 H1 + 0 H2 + 0 H3
Sujeto a:
X 1 + H1 = 5
X 2 + H2 = 8
2 X1 + X2 + H3 = 15
Con X1, X2 > 0
64
Con esto la primera tabla Simplex será:

30 40 0 0 0
X1 X2 H1 H2 H3
0 H1 5 1 0 1 0 0
0 H2 8 0 1 0 1 0
0 H3 15 2 1 0 0 1
0 -30 -40 0 0 0

La cual al aplicarle el Simplex dará para la siguiente iteración:

30 40 0 0 0
X1 X2 H1 H2 H3
0 H1 5 1 0 1 0 0
40 X2 8 0 1 0 1 0
0 H3 7 2 0 0 -1 1
320 -30 0 0 40 0

De aquí al proseguir con la metodología Simplex, se llega a la solución óptima en la siguiente iteración,
siendo la tabla respectiva la siguiente:

3 4 0 0 0
X1 X2 H1 H2 H3
0 H1 1.5 0 0 1 0.5 -0.5
40 X2 8 0 1 0 1 0
30 X1 3.5 1 0 0 -0.5 0.5
425 0 0 0 25 15

Así la solución es:

H1 = 1.5
X2 = 8
X1 = 3.5
Zp = 425
(H2 = H3 = 0)

Para el problema dual, las restricciones necesitan una variable de holgura y otra artificial por cada
restricción, con esto se tendrá:

Min ZD = 5Y1 + 8Y2 + 15Y3 + 0H1 + 0H2 + MF1 + MF2

Sujeta a las restricciones:

Y1 + 2Y3 - H1 + F1 = 30
Y2 + Y3 - H2 + F2 = 40
Con Y1, Y2, Y3 > 0

Con esto al aplicar la metodología Simplex, la primera tabla será:

5 8 15 0 0 M M
Y1 Y2 Y3 H1 H2 F1 F2
M F1 30 1 0 2 -1 0 1 0
M F2 40 0 1 1 0 -1 0 1
0 5 8 15 0 0 0 0 Parte #
-1 -1 -3 1 1 0 0 Parte M
 65

Si se sigue aplicando la metodología Simplex, la tabla correspondiente para la siguiente iteración es:

5 8 15 0 0 M
Y1 Y2 Y3 H1 H2 F2
15 Y3 15 0.5 0 1 -0.5 0 0
M F2 25 -0.5 1 0 0.5 -1 1
-225 -2.5 8 0 7.5 0 0
0.5 -1 0 -0.5 1 0

Al pasar a la siguiente iteración se llega al óptimo, cuya tabla será:

5 8 15 0 0
Y1 Y2 Y3 H1 H2
15 Y3 15 0.5 0 1 -0.5 0
8 Y2 25 -0.5 1 0 0.5 -1
-425 1.5 0 0 3.5 8
0 0 0 0 0

Siendo su solución:
Y3 = 15
Y2 = 25
ZD = 425
(Y1 = H1 = H2 = 0)

Aquí es significativo que en el punto óptimo ambos problemas dan el mismo valor para la función
objetivo, es decir Zp = ZD = 425.

Esta es una de las razones de la importancia del problema dual, que al resolverse proporciona la solución
del primario.

Esta igualdad de las funciones objetivo tiene una explicación, pues Zp es la utilidad que se obtiene por los
diferentes tipos de pan y ZD es el costo incurrido por aplicar los recursos disponibles, de tal forma que en el
punto óptimo ambas Z coinciden dando la situación más conveniente para el negocio.

Otra situación importante que se puede señalar en este problema es que la solución dual puede obtenerse
desde la tabla final del primario, pues los coeficientes índices de las variables de holgura en esta tabla son los
valores de las variables duales en la solución óptima dual, esto es:

H1P = 0 = Y1
H2P = 25 = Y2
H3P = 15 = Y3

Asimismo de la tabla óptima dual se puede obtener la solución primaria al coincidir los coeficientes
índices de las variables de holgura duales con los valores óptimos para las variables primarias, esto es:

H1D = 3.5 = X1
H2D = 8 = X2
Interpretación económica del Dual
La interpretación de la solución dual proporciona una visión sobre la manera óptima de utilizar los recursos de
que se dispone (Hillier y Lieberman, 1991).

Debería uno estar dispuesto a pagar un costo mayor por un recurso hasta por el valor de su variable dual
correspondiente a la solución óptima.
66
Para ilustrar esto, se retoma el caso del expendio de pan donde para el caso de la cajeta, Y2 fue en la tabla
dual final 25, lo que significa que podría pagarse hasta $ 25 adicionales como máximo por cada unidad extra
de cajeta usada, dado que esta cantidad es la utilidad adicional que se obtendría por su empleo.

Este concepto es el mismo que se manejó en el apartado de los precios sombra, dado que los coeficientes
del renglón índice de las variables de holgura de la tabla Simplex final del problema primario son los valores
óptimos de las variables duales en el problema dual, lo que indica que la utilización óptima de los recursos
disponibles, lleva al mismo tiempo a lograr una utilidad máxima.

Análisis de Sensibilidad
El análisis de sensibilidad es muy útil en la programación lineal, consiste en estudiar los cambios que sufre la
función objetivo ante modificaciones en cualquiera de los parámetros del problema, como pueden ser las
constantes de las restricciones, los coeficientes de las variables en las ecuaciones de las restricciones, las
contribuciones de las variables en la función objetivo, adición de nuevas restricciones, nuevas variables, etc.

Todo esto es muy importante, puesto que en los problemas reales las condiciones suelen cambiar, debido a
que muchas veces los datos que se manejan son sólo pronósticos futuros de la situación esperada, los cuales
están sujetos a variaciones e imprevistos que siempre están presentes.

Por medio del análisis de sensibilidad es posible evaluar dichos cambios sin tener que resolver
completamente el problema planteado, lo que significa un ahorro considerable de cálculos en el procedimiento
del método Simplex (Hillier y Lieberman, 1991).

Clasificación de casos para el Análisis de Sensibilidad

Para el estudio del análisis de sensibilidad, se dividirá su presentación en las siguientes 5 partes, que son las
que suelen aparecer con mayor frecuencia en el ámbito de los negocios (Davis y McKeown, 1986):
1.- Cambios en las constantes de las restricciones.
2.- Cambios en las contribuciones de las variables en la función objetivo.
3.- Cambios en los coeficientes de las variables en las ecuaciones de las restricciones.
4.- Adición de nuevas variables.
5.- Adición de nuevas restricciones.

Para el estudio de estos puntos, se presentará un ejemplo de cada uno de ellos, que serán resueltos y
explicados en cada uno de sus pasos hasta encontrar la solución óptima del nuevo problema, la cual puede ser
la misma del problema original (antes de haber efectuado la modificación de sus parámetros), o bien haber
cambiado, dependiendo de la magnitud de variación en el parámetro respectivo.

Se tomará como caso base el de la panadería presentado cuando se habló de la dualidad, el cual era:

Max Z = 30 X1 + 40 X2

Sujeto a las restricciones:

X1 < 5 (1)
X2 < 8 (2)
2X1 + X2 < 15 (3)

Cuya primera tabla Simplex fue:

30 40 0 0 0
X1 X2 H1 H2 H3
0 H1 5 1 0 1 0 0
 67
0 H2 8 0 1 0 1 0
0 H3 15 2 1 0 0 1
0 -30 -40 0 0 0

Y su tabla final (solución óptima) fue:

3 4 0 0 0
X1 X2 H1 H2 H3
0 H1 1.5 0 0 1 0.5 -0.5
40 X2 8 0 1 0 1 0
30 X1 3.5 1 0 0 -0.5 0.5
425 0 0 0 25 15

Cambios en las constantes de las restricciones

Esto se ilustrará con el siguiente ejercicio:

Ejemplo IV.7.- Resolver por medio del análisis de sensibilidad el siguiente problema:

Max Z = 30 X1 + 40 X2
Sujeto a las restricciones:
X1 < 5 (1)
X2 < 6 (2)
2X1 + X2 < 15 (3)

Solución:
El cambio respecto al problema original es en la segunda restricción, donde ahora X 2 < 6 y no 8, esto
significa que el recurso cajeta ha disminuido, habiendo ahora solamente la necesaria para producir como
máximo 6 kgs de pan de cajeta.

Para resolver el problema Simplex ante este cambio sin tener que aplicar toda la metodología desde el
principio, es útil la aplicación de la siguiente fórmula:

Matriz de coeficient es  Vector de 

de las variables de holgura  constantes  Vector 
  x   solución del 
 Ec.(IV.3)
en la tabla Simplex final  de las   
    problema 
del caso base  restriccio nes 

Así para el caso base de la panadería, si se observa la tabla final, la parte de la matriz correspondiente a los
coeficientes de las variables de holgura es:

 1 0.5 0.5
0 1 0 
 
 0 0.5 0.5 
H1 H2 H3
El vector de constantes originales de las restricciones era:
68
5
 
 8 
 15 
Por lo que al efectuar la multiplicación matricial, conforme a la Ec. (IV.3), se tendrá:

 1 0.5 0.5  5 
0 1  Vector 
0  x 8    
     Solución
 0 0.5 0.5   15
(3 x 3) (3x1) (3 x 1)

Por lo que la solución es:

H 1  1. 5 
 
X2
8
X 1  3.5 

Tal y como podía haberse leído desde la tabla final.

Para obtener la nueva solución óptima ante el cambio en la constante de la segunda restricción, lo que se
debe hacer es aplicar la fórmula de la Ec. (IV.3) con el nuevo vector de constantes de las restricciones, es
decir:

 Vector 
 1 0.5 0.5  5  
0 1 Solución 
0  x 6    
     del problema
 0 0.5 0.5   15
 modificado 

Con lo cual la nueva solución será:

H1 = 0.5
X2 = 6
X1 = 4.5

Siendo entonces Z:

Z = 30 X1 + 40 X2
= 30 (4.5) + 40 (6)
= 135 + 240 = 375

Como esta solución es factible, representará la nueva solución óptima.

Si la nueva solución no hubiera sido factible (caso de que una variable básica resultara negativa), entonces
se tendría que haber aplicado la metodología Simplex hasta llegar a la tabla final que daría la nueva solución
óptima.

Cambios en las contribuciones de las variables en la función objetivo

Estos cambios pueden agruparse en 2 categorías:
Cambios en la contribución de una variable básica y cambios en la contribución de una variable no básica.
 69

Se presenta un problema del primer caso, aunque ambos tipos se tratan de la misma manera.

La metodología general para este tipo de problemas es la siguiente:

En la tabla Simplex final del problema original, se cambian las contribuciones de las variables (básicas y
no básicas) en el renglón objetivo, tal y como hayan cambiado de acuerdo a las nuevas condiciones del
problema y con esto se recalculan los elementos del renglón índice, si ninguno de ellos se ha hecho negativo,
la solución óptima seguirá siendo la misma, cambiando solamente la Z; por el contrario, si existen elementos
negativos en el renglón índice, se aplica la metodología Simplex normal hasta llegar a la nueva solución
óptima, este procedimiento se ilustra con un ejemplo.

Ejemplo IV.8.- Si para el problema de la panadería, llega un incremento en la utilidad del pan, siendo ahora
para el primer tipo de $ 50 por kilo y para el segundo de $ 45 ¿Cuál será la cantidad óptima de cada pan a
producir de modo que se maximicen las utilidades?

Solución:
Con estos cambios en los precios del pan, que son cambios en las contribuciones de las variables básicas,
la ecuación de la función objetivo será:

Z = 50 X1 + 45 X2

Sujeta a las mismas restricciones originales.

De acuerdo al procedimiento explicado anteriormente, la última tabla Simplex del problema original era
la siguiente:

50 45 0 0 0
X1 X2 H1 H2 H3
0 H1 1.5 0 0 1 0.5 -0.5
40 X2 8 0 1 0 1 0
30 X1 3.5 1 0 0 -0.5 0.5

Donde ya se han cambiado las contribuciones de las variables en el renglón objetivo. Ahora se procede a
recalcular los números del renglón índice, utilizando para ello la fórmula dada por la Ec. (IV.1), aplicándola a
aquellos elementos que sufrieron cambios en el renglón objetivo:

Número índice de
la columna de X1 = [ (0)(0) + (40)(0) + (30)(1) ] - 50 = 30 - 50 = -20

Número índice de
la columna de X2 = [ (0)(0) + (40)(1) + (30)(0) ] - 45 = 40 - 45 = -5

Para los demás elementos del renglón índice no habrá cambios, de modo que sus valores índice serán los
mismos, con esto la nueva tabla será:

50 45 0 0 0
X1 X2 H1 H2 H3
0 H1 1.5 0 0 1 0.5 -0.5
40 X2 8 0 1 0 1 0
30 X1 3.5 1 0 0 -0.5 0.5
425 -20 -5 0 25 15
70
Y de aquí se sigue con la metodología Simplex normal: determinar la columna clave, el renglón clave, el
número clave, etc., hasta llegar a la nueva solución óptima, que será aquella que ya no contenga números
índice negativos, esta tabla final será:

50 45 0 0 0
X1 X2 H1 H2 H3
0 H1 1.5 0 0 1 0.5 -0.5
45 X2 8 0 1 0 1 0
50 X1 3.5 1 0 0 -0.5 0.5
535 0 0 0 20 25

Con lo cual puede verse que la solución óptima no ha cambiado, sólo la función objetivo.

Para saber cuánto se puede modificar una variable básica sin que la solución óptima cambie, se efectúa el
siguiente análisis: De la última tabla Simplex del problema original, la cual es:

30 40 0 0 0
X1 X2 H1 H2 H3
0 H1 1.5 0 0 1 0.5 -0.5
40 X2 8 0 1 0 1 0
30 X1 3.5 1 0 0 -0.5 0.5
425 0 0 0 25 15

Para establecer el intervalo de valores que X1 puede tener en su contribución sin que cambie la solución
óptima, se determina para las variables no básicas el cociente de su número índice entre el valor del
coeficiente correspondiente al renglón de la variable básica (X1) y a la columna de la variable no básica, así
para H2 se tendrá:

Cociente= 25/(-0.5) = -50

Por su parte para H3:

Cociente= 15/0.5 = 30

Aquí un cociente negativo indica el aumento permitido para X1 y un cociente positivo mostrará la
disminución posible para X1.

Con esto X1 puede aumentar hasta en 50 unidades y disminuir hasta en 30 unidades en su contribución,
con esto su intervalo de valores permitidos será:

0 < X1 < 80

En caso de haber varios cocientes positivos y negativos, se manejarán los que marquen el intervalo más
estrecho, es decir los menores cocientes en valor absoluto, tanto positivos como negativos.

Por su parte al realizar un análisis similar para la variable X2, el cociente para H2 será:

Cociente= 25/1 = 25

Y para H3:

Cociente = 15/0= OO

Esto significa que X2 puede disminuir hasta 25 unidades y aumentar hasta el infinito en su contribución,
con esto su intervalo de valores permitido es:
 71

15 < X2 < ∞

Cambios en los coeficientes de las variables en las ecuaciones de las restricciones

Estos suceden cuando existe una modificación en alguna de las restricciones, por ejemplo en la cantidad
requerida de recursos para elaborar cada artículo. Esto significa un cambio en alguno(s) de los coeficientes de
las variables en las ecuaciones de las restricciones.

Este tema también puede dividirse en 2 categorías: cambios en los coeficientes de una variable básica y
cambios en los coeficientes de una variable no básica.

La metodología que utiliza el análisis de sensibilidad en estos casos es la misma para ambos incisos, lo
cual se describe enseguida y luego se ilustra con un ejemplo.

El planteamiento se basa en la siguiente ecuación:

Vector de  Vector de 
M atriz de coeficient es     
de las variables de holgura  coeficient es  coeficient es 
  X de la variable   de la variable  Ec.(IV.4)
en la tabla Simplex final     
  Xi al inicio  Xi al final del 
del caso base  del problema  problema 
  

De tal forma que al cambiar el vector de coeficientes de Xi al inicio del problema, cambiará también el
vector de los coeficientes Xi en la tabla final, la cual por la metodología Simplex podrá resolverse hasta llegar
a la solución óptima para el problema modificado.

Se presenta un ejemplo para el cambio en los coeficientes de una variable básica.

Ejemplo IV.9.- Para el problema original de la panadería, existe un cambio debido a que la cajeta adquirida
para elaborar el segundo tipo de pan es de menor calidad, por lo que alcanza solamente para la mitad del pan.
En este caso, ¿Cuál será la solución óptima del problema?

Solución:
En este caso lo que cambia es la segunda restricción, la cual será ahora:

2X2 < 8

Para este problema el vector de coeficientes de X2 al inicio del problema se modifica, siendo ahora:

 0
 2
 
 1
Entonces si se aplica la Ec. (IV.4) al caso presente, para obtener:

 1 0.5 0.5  0  0.5 

0 1 0  x  2  2 
     
 0 0.5 0.5   1  0.5
72
Quedando la última tabla de la siguiente forma:

30 40 0 0 0
X1 X2 H1 H2 H3
0 H1 1.5 0 0.5 1 0.5 -0.5
40 X2 8 0 2 0 1 0
30 X1 3.5 1 -0.5 0 -0.5 0.5
425 0 25 0 25 15

En la cual se ha recalculado el número índice que corresponde a la columna de X 2 del modo siguiente:

Número índice de
la columna de X2 = [ (0)(0.5) + (40)(2) + (30)(-0.5) ] - 40 = 65 - 40 = 25

Como puede verse en esta tabla, el número índice de la columna de X2 deberá ser cero, puesto que esta
variable es básica. Asimismo el número de esta columna y del renglón que encabeza X2 debe ser la unidad y
los restantes elementos de esta misma columna deberán ser cero. Si se aplica la metodología Simplex, se llega
a la siguiente tabla:

30 40 0 0 0
X1 X2 H1 H2 H3
0 H1 -0.5 0 0 1 0.25 -0.5
40 X2 4 0 1 0 0.5 0
30 X1 5.5 1 0 0 -0.25 0.5
325 0 0 0 12.5 15

De esta tabla se observa que ya no hay números índice negativos, pero existe un problema: H 1 sigue
siendo básica y es negativa, lo cual no puede ser una solución viable del caso. Para modificar la tabla y
corregir esta situación, es preferible ir al problema dual equivalente, cuya tabla correspondiente a esta última
situación es:

5 8 15 0 0
Y1 Y2 Y3 H1 H2
8 Y2 12.5 -0.25 1 0 0.25 -0.5
15 Y3 15 0.5 0 1 -0.5 0
-325 -0.5 0 0 5.5 4

Donde hay un número índice negativo que corresponde a la columna encabezada por Y1, por lo que esta
variable debe ser incluida en la base conforme al método Simplex normal, que al proceder hacia la solución
óptima, produce la siguiente tabla final:

5 8 15 0 0
Y1 Y2 Y3 H1 H2
8 Y2 20 0 1 0.5 0 -0.5
5 Y1 30 1 0 2 -1 0
-310 0 0 1 5 4

Cuya solución equivalente del primario es:

X1 = 5
X2 = 4
H3 = 1
 73
Z = 310

Aquí se ve que la solución óptima ha cambiado, pues se incluye a H3 como variable básica en lugar de H1
que era básica en el problema original.

Para el caso de cambios en los coeficientes de las restricciones de variables no básicas, el procedimiento
de solución es exactamente el mismo.

Adición de nuevas variables

Este caso se presenta cuando una empresa decide incorporar nuevos productos en su línea de ventas.

Cada nuevo producto representará una nueva variable, que debe incluirse en el problema en la función
objetivo con su contribución, así como también en las restricciones con sus coeficientes según el
planteamiento del caso.

La variable deberá incluirse en la última tabla Simplex del caso base con su contribución respectiva y sus
coeficientes deberán calcularse por medio de la fórmula dada por la Ec. (IV.4), así como también su número
índice.

Esto se ilustra con el siguiente ejemplo.

Ejemplo IV.10.- Partiendo del caso base, la panadería ha proyectado introducir al mercado un nuevo tipo de
pan, el cual dará una utilidad de $ 35 por kilo. Este nuevo tipo de pan requiere de 1.5 kgs de harina para
preparar un kilogramo del nuevo pan.

Ante esta nueva situación del mercado, ¿Cómo deberá la panadería producir ahora los 3 tipos de pan, de
tal modo que sus utilidades sean máximas?

Solución:
La nueva variable quedará incorporada en la función objetivo de la siguiente manera:

Max Z = 30 X1 + 40 X2 + 35 X3

Sujeta a las restricciones:

X1 < 5 (1)
X2 < 8 (2)
2X1 + X2 + 1.5X3 < 15 (3)

Como puede observarse de estas ecuaciones, el vector de coeficientes iniciales para la nueva variable X 3
es:

 0
 0
 
 15
.

Si se aplica la fórmula de la Ec. (IV.4), se tendrá:

 Vector de 
   1 0.5  0.5   0    0.75 
 coeficient es    0 1    
0 x 0  0

 de X 3 en la      
     
 tabla final   0  0.5 0.5  1.5   0.75 
 
74

Y su número índice será:

Número índice en la columna de X3 = [(0)(-0.75) + (40)(0) + (30)(0.75)] - 35 = 22.5 - 35 = -12.5

Estos valores se incluyen en la tabla final en la siguiente forma:

30 40 35 0 0 0
X1 X2 X3 H1 H2 H3
0 H1 1.5 0 0 -0.75 1 0.5 -0.5
40 X2 8 0 1 0 0 1 0
30 X1 3.5 1 0 0.75 0 -0.5 0.5
425 0 0 -12.5 0 2.5 1.5

De aquí el problema se continúa normalmente por el método Simplex. Del análisis de la tabla, se ve que el
número índice de X3 es negativo, por lo que esta variable deberá entrar a la base.

La nueva solución óptima será ahora la siguiente:

30 40 35 0 0 0
X1 X2 X3 H1 H2 H3
0 H1 5 1 0 0 1 0 0
40 X2 8 0 1 0 0 1 0
35 X3 4.667 1.333 0 1 0 -0.667 0.667
483.333 16.667 0 0 0 16.667 23.333

Que ya no es igual a la solución anterior, siendo ahora:

X2 = 8
X3 = 4.667
Z = 483.333

Por lo que la panadería no deberá producir ya el primer tipo de pan.

Adición de nuevas restricciones

Esta situación puede llegar a presentarse debido a limitaciones lógicas que aparecen en el mundo real de los
negocios, tales como la escasez de materias primas, poca disponibilidad de tiempo, de mano de obra, etc.

Cuando aparece una nueva restricción, ésta deberá incluirse en la tabla óptima final con sus coeficientes y
sus variables adicionales correspondientes, según el tipo de restricción, la que entrará a la base con la
constante de la restricción como parte de la solución. De aquí se prosigue normalmente hasta hallar la solución
óptima, que no cambiará si se cumple con la nueva restricción; en caso opuesto, deberá hallarse la nueva
solución óptima por medio de la metodología Simplex normal.

Este procedimiento se ilustra en el ejemplo siguiente para el caso de la panadería.

Ejemplo IV.11.- Si al problema original de la panadería se le añade la condición de que no pueden producirse
más de 10 kilos totales de pan, ¿Cómo afecta esto a la solución óptima?

Solución:
Esta nueva condición significa una cuarta restricción, que sería la siguiente:

X1 + X2 < 10 (4)
 75
Lo primero será comprobar si la solución anterior cumple con esta nueva restricción. Para el caso base,
esta solución era X1 = 3.5 y X2 = 8, por lo tanto:
X1 + X2 = 3.5 + 8 = 11.5 > 10

Por lo que la restricción no se cumple.

Ante esto, conforme a la metodología descrita antes, la nueva restricción debe incorporarse a la tabla final
del caso base, con su variable de holgura, la que se designa como H4, la cual deberá estar en la base de la
tabla junto con la constante de la nueva restricción, que es 10. Con esto la tabla será ahora:

30 40 0 0 0 0
X1 X2 H1 H2 H3 H4
0 H1 1.5 0 0 1 0.5 -0.5 0
40 X2 8 0 1 0 1 0 0
30 X1 3.5 1 0 0 -0.5 0.5 0
0 H4 10 1 1 0 0 0 1
425 0 0 0 25 15 0

Aunque esta tabla no tiene números índice negativos, no puede ser la solución óptima del problema,
debido a que X1 y X2 son variables básicas y por lo tanto deben tener en el nuevo renglón de H4 coeficientes
iguales a cero y no unos como es el caso una vez incorporada la nueva restricción. Por tanto habrá que generar
esos ceros, lo que puede lograrse si al renglón que encabeza H4 se le restan los renglones encabezados por X1
y X2. Con estos cambios la tabla quedará de la siguiente manera:

30 40 0 0 0 0
X1 X2 H1 H2 H3 H4
0 H1 1.5 0 0 1 0.5 -0.5 0
40 X2 8 0 1 0 1 0 0
30 X1 3.5 1 0 0 -0.5 0.5 0
0 H4 -1.5 0 0 0 -0.5 -0.5 1
425 0 0 0 25 15 0

En esta tabla H4 es básica y negativa, por lo que esta solución no es factible, para lo cual, se pasa al
problema dual correspondiente, que es el que se muestra a continuación:

5 8 15 10 0 0
Y1 Y2 Y3 Y4 H1 H2
8 Y2 25 -0.5 1 0 0.5 0.5 -1
15 Y3 15 0.5 0 1 0.5 -0.5 0
-425 1.5 0 0 -1.5 3.5 8

De aquí se sigue la metodología Simplex normal para llegar a la nueva tabla óptima final:

5 8 15 10 0 0
Y1 Y2 Y3 Y4 H1 H2
8 Y2 10 -1 1 -1 0 1 -1
10 Y4 30 1 0 2 1 -1 0
-380 3 0 3 0 2 8

Cuya solución primaria es:

X1 = 2
X2 = 8
Z = 380
76
La que ha cambiado respecto al caso base debido a que éste no cumplía con la nueva restricción.

BIBLIOGRAFÍA

Davis, K. Roscoe, y McKeown, Patrick G., Modelos Cuantitativos para Administración, Grupo Editorial
Iberoamérica, 1986.

Hillier, Frederick S., y Lieberman, Gerald J., Introducción a la Investigación de Operaciones, 5a Edición, Mc
Graw Hill, 1991.

Gallagher, Charles A., y Watson, Hugh J., Métodos Cuantitativos para la Toma de Decisiones, McGraw Hill,
1992.

Izar, Juan M., Elementos de Métodos Numéricos para Ingeniería, Editorial Universitaria Potosina, 1998.
 77
PROBLEMAS PROPUESTOS

IV.1.- Resolver el ejemplo II.1 planteado en el capítulo II:

Min Z = 2.35 X1 + 2.00 X2 + 1.70 X3

Sujeta a las restricciones:
12 X1 + 10 X2 + 8 X3 > 10.0
10 X1 + 10 X2 + 6 X3 < 9.5
60 X1 + 50 X2 + 44X3 > 52.0
X1 + X 2 + X 3 = 1

Con X1, X2, X3, No negativas

IV.2.- Resolver el ejemplo II.3 planteado en el capítulo II:

Min Z = 45 X1 + 37 X2 + 30 X3
Sujeta a las restricciones:
12 X1 + 10 X2 + 8 X3 > 11
30 X1 + 30 X2 + 25 X3 > 28
18 X1 + 15 X2 + 15 X3 > 17
X1 + X2 + X3 = 1

Siendo X1, X2, X3, No negativas.

IV.3.- Resolver el ejemplo II.6 planteado en el capítulo II:

Min Z = 220 X1 + 155 X2 + 175 X3 + 130 X4 + 150 X5

Sujeta a:
X1 + X2 + X3 + X4 + X5 = 6500
0.402 X1 + 0.328 X2 + 0.30 X3 + 0.42 X4 + 0.50 X5 > 2210
0.408 X1 + 0.337 X2 + 0.35 X3 + 0.28 X4 + 0.201 X5 > 1950
0.19 X1 + 0.335 X2 + 0.35 X3 + 0.30 X4 + 0.299 X5 < 1950
X1 < 1500 X2 < 2300 X3 < 3200
X4 < 4500 X5 < 5200

Siendo todas las variables No Negativas.

IV.4.- Solucionar el problema propuesto II.11 de la Compañía “Gravas Finas”:

Max Z = 250 X1 + 180 X2 + 210 X3 + 165 X4 + 195 X5 + 200 X6

Sujeta a:
X1 + X2 + X3 + X4 + X5 + X6 = 8000
0.36 X1 + 0.35 X2 + 0.30 X3 + 0.45 X4 + 0.50 X5 + 0.25 X6 > 0.36 (8000)
0.34 X1 + 0.35 X2 + 0.40 X3 + 0.25 X4 + 0.22 X5 + 0.50 X6 > 0.32 (8000)
0.30 X1 + 0.30 X2 + 0.30 X3 + 0.30 X4 + 0.28 X5 + 0.25 X6 < 0.28 (8000)
X1 < 3500 X2 < 2800 X3 < 3800
X4 < 6400 X5 < 7200 X6 < 2600

Siendo las variables no negativas

78
IV.5 - Solucionar:

Max Z= 100X1 + 120X2 + 200X3

Con las restricciones:
X1 + X2 + 2X3 < 5 (1)
X1 > 2 (2)
2X1 + X3 > 3 (3)
X3 < 2 (4)

Con X1, X2, X3, no negativas.

IV.6.- Solucionar:

Max Z = 8X1 + 9X2

Sujeto a:
X1 + X2 =1 (1)
2X1 + X2 < 1.4 (2)
X1 + 2X2 < 1.5 (3)

Con X1, X2, no negativas.

IV.7.- Resolver el problema propuesto II.13 del trailer del Sr. José Padrón:

Max Z = 350 X1 + 320 X2 + 300 X3 + 400 X4 + 470 X5 + 390 X6

Sujeto a: X1 + X2 + X3 + X4 + X5 + X6 < 35
1.25X1 + 1.333X2 +1.429X3 + 1.667X4 + 1.538X5 + 1.887X6 < 60
X1 < 15 X2 < 12 X3 < 10 X4 < 10 X5 < 8 X6 < 7

Siendo las variables no negativas

IV.8.- Solucionar:

Max Z = X1 + X2 +X3
Con las restricciones:
X1 + 2X2 + X3 < 5 (1)
2X1 + X2 + X3 < 4.8 (2)
X1 + X2 + 2X3 < 5.3 (3)

Con X1, X2, X3 no negativas.

IV.9.- Solucionar:

Min Z = X1 + X2 +0.8X3
Sujeto a las condiciones:
X1 + X 2 + X 3 = 1 (1)
2X1 + X2 + 2X3 > 3 (2)
X1 < 0.4 (3)
X2 < 0.2 (4)

Con X1, X2, X3 no negativas.

 79

IV.10.- Dado el siguiente problema:

Minimizar Z = 4X1 + 3X2

Sujeto a:
(1) 2X1 + X2 > 5
(2) 3X1 + 2X2 > 8
(3) X1 > 2
(4) 2X2 > 1.5
Siendo X1, X2 > 0, plantear el correspondiente problema dual.

IV.11.- Resolver el problema dual del caso anterior.

IV.12.- Plantear y resolver el problema dual para el caso siguiente:

Maximizar Z = 10X1 + 9X2

Sujeto a:
(1) 3X1 + X2 < 3
(2) X1 + X2 = 1
Siendo X1, X2 > 0

IV.13.- Dado el problema:

Max Z = 4X1 + 2X2 + 3X3

Sujeto a las restricciones
X 1 + X2 < 8
X3 < 7
2X1 + X2 + X3 < 14

¿Cómo cambiará la solución óptima, si:

a) La constante de la primera restricción es 12?
b) La constante de la segunda restricción es 10?
c) La constante de la tercera restricción es 20?

Resuelva cada inciso comparado con el problema original.

IV.14.- Respecto al problema base anterior, ¿Cómo se verá afectada la solución óptima, si:
a) La contribución de X1 es ahora 2?
b) La contribución de X2 es ahora 4?
c) La contribución de X3 es ahora 5?

Resuélvase cada inciso respecto al caso original.

IV.15.- Del problema IV.13, ¿Cómo cambia la solución óptima, si se verifican los siguientes cambios:
a) Los coeficientes de X1 en las restricciones son 2, 0, 1 respectivamente?
b) Los coeficientes de X3 en las restricciones son 1, 1, 1 respectivamente?

Responda cada inciso respecto al problema original.

80
IV.16.- Respecto al problema IV.13 ¿Cuál será la solución óptima ante el siguiente cambio:
Se introduce un nueva variable X4 con contribución de 3.5 y coeficientes en las restricciones de 1, 0 y 1
respectivamente?

IV.17.- Si en el problema IV.13 se agrega la restricción:

X2 + X 3 < 6 (4)

¿Cuál será en este caso la solución óptima?