Случаи, когда число претендентов не равно количеству мест

Возможны случаи, когда число рабочих, которых надо распреде­лить на соответствующую работу, меньше (или больше) количества мест. В этом случае, вводятся дополнительные фиктивные рабочие (или рабочие места).

Представим, что один рабочий, например 4, уволился. Тогда нам необходимо расставить трех рабочих, имея четыре вакансии. При этом, конечно, общая цель назначений остается неизменной. Введем ус­ловно фиктивного рабочего, характеристики которого будут нулевые, т. е. все

C_4j = 0 (j=1, 2, 3, 4). Тогда получается таблица:

Таблица 2.8.6

Данная проблема решается так же, как и в общем случае, только мы уже не будем совершать этап 2 (понятно, не правда ли?). Опти­мальное решение будет х₁₂ —х₂₃ — х₃₁ =х₄₄=1. Четвертый станок ока­зался незанятым.

А теперь представим ситуацию, когда число рабочих больше числа станков. Она свидетельствует о том, что один рабочий не будет иметь места. Как произвести назначение в этом случае и кого надо уволить, если цель остается неизменной? Для разрешения этой ситуации вво­дится фиктивный станок, на котором показатели работы равны нулю. В нашем случае будем считать, что станок 3, например, больше не используется. Это может быть отображено данными следующей таб­лицы.

Таблица 2.8.7

Здесь мы уже не будем выполнять этап 1. Постарайтесь сами по­лучить оптимальное решение х₁₂ = х₂₄ — х₃₃ — х₄₁ = 1.

Случай, когда некоторые назначения невозможны.

Предположим, что некоторые назначения невозможны, например,

второй рабочий не может выполнять работу на третьем станке. В этом случае, так же, как мы поступали в параграфе II. 4, в соответствующую клетку заносится большое число М. Это автоматически приводит к тому, что клетка окажется незанятой в оптимальном решении.