Изменение опорного плана назначений

Опорный план назначений обычно не является оптимальным, т. е. он требует улучшения. В данном параграфе описан алгоритм изменения опорного плана назначений, а в следующем — алгоритм достижения оптимального плана назначений посредством последовательных изменений опорного плана.

Изменение опорного плана — это построение нового плана назначений, который обладает свойствами опорного плана, а именно:

• а) число базисных клеток равно т + п — 1, где т — число типов работников, п — число должностей;
• б) сумма элементов каждой строки матрицы назначений равна численности работников соответствующего типа, а сумма элементов каждого столбца этой матрицы равна количеству рабочих мест соответствующего типа.

Простейшее изменение опорного плана — это такое его изменение, в результате которого один базисный элемент становится свободным, а один свободный элемент — базисным. Понятно, что в результате простейшего изменения получается план назначений, обладающий всеми свойствами опорного плана.

Предположим, что целью изменения опорного плана служит назначение максимально возможного количества работников /-го типа на/-ю должность. Предполагается, что в опорном плане элемент х" равен нулю, т. е. соответствующая клетка опорной матрицы является свободной. Данную клетку назовем целевой. В результате осуществления простейшего изменения опорного плана назначений целевая клетка станет базисной, а одна из базисных клеток исходного опорного плана — свободной.

Алгоритм простейшего изменения опорного плана назначений основан на построении контура изменений —- замкнутой ломаной линии, обладающей следующими свойствами:

• а) одна вершина контура лежит в целевой клетке матрицы назначений, а остальные вершины — в базисных клетках;
• б) любые две стороны контура, имеющие общую вершину, образуют прямой угол.

Этапы алгоритма простейшего изменения опорного плана назначений следующие:

• 1) выбрать целевую клетку среди свободных клеток исходного опорного плана;
• 2) построить контур изменений с вершиной в целевой клетке. Можно доказать, что такой контур единственен;
• 3) пометить целевую клетку знаком «плюс», соседние с ней клетки — знаком «минус» и т. д. (чередовать знаки, перебирая последовательно вершины контура по часовой стрелке). Знак «плюс» («минус») означает, что в результате простейшего изменения опорного плана число работников данного типа, назначенных на данную должность, увеличится (уменьшится);
• 4) рассмотреть элементы матрицы назначений, которые соответствуют вершинам контура изменений, помеченным знаком «минус». Наибольшее из этих чисел обозначим через Ах;
• 5) увеличить на величину Ах элементы матрицы назначений, которые отвечают вершинам контура изменений, помеченным знаком «плюс». В результате элемент матрицы назначений, соответствующий целевой клетке, становится равным Ах; при этом целевая клетка превратится из свободной в базисную;
• 6) уменьшить на величину Ах элементы матрицы назначений, которые отвечают вершинам контура изменений, помеченным знаком «минус». В результате базисный элемент опорного плана, равный Ах, станет равным нулю. Соответствующая клетка матрицы назначений превратится из базисной в свободную;
• 7) рассчитать прирост прибыли, который обеспечивает простейшее изменение опорного плана, по следующей формуле:

где Ал — прирост прибыли, а, у — продуктивность, 6_#у— знак («плюс» или «минус») вершины контура изменений. В приведенной формуле суммирование производится по клеткам матрицы назначений, в которых расположены вершины контура изменений.

Пример. В табл. 6.7 представлен исходный опорный план назначений. Построим новый плана назначений, используя описанный выше алгоритм:

• 1) выберем клетку (3; 3) в качестве целевой клетки опорного плана. В исходном опорном плане данная клетка является свободной (элемент Х33 равен нулю), она отмечена звездочкой в табл. 6.7;
• 2) построим контур изменений, он представляет собой прямоугольник с вершинами (3; 3), (3; 2), (1; 2) и (1; 3);
• 3) клетки (3; 3) и (1; 2) пометим знаком «плюс», а клетки (3; 2) и (1;
• 3) — знаком «минус»;

Изменение опорного плана назначений.

4) определим величину Лх:

5) рассчитаем элементы новой матрицы назначений, которые соответствуют вершинам контура изменений, помеченным знаком «плюс»:

6) рассчитаем элементы новой матрицы назначений, которые соответствуют вершинам контура изменений, помеченным знаком «минус»:

7) рассчитаем прирост прибыли, который обеспечивает данное изменение опорного плана назначений:

Таким образом, описанное изменение опорного плана назначений является ухудшением.