4.4.2. Дельта-метод
Рассмотрим алгоритм дельта-метода в общем виде:
Рассмотрим таблицы приращений
,
полученных соответственно в результате
выбора каждого столбца наименьшей
стоимости и вычитания ее из всех
стоимостей столбца, а также таблицу
,
получающихся в результате выбора в
каждой строке
приращений
и вычитании его из всех приращений
строки при условии, что строки с
нулевым приращением
не рассматриваются.
Заполнение проводится по столбцам, содержащим одно нулевое приращение, в клетки, содержащие его, записываются потребности, без учета величины запасов на складах. Затем уже с учетом произведенных постановок просматриваем столбцы, содержащие два нулевых и более приращений, и заполняем их, до тех пор, пока все объемы потребностей не будут закреплены за поставщиками.
Подсчитываются для строк разницы между фактическими запасами и полученными для опорного “фиктивного” плана. Критерием оптимальности плана является нулевая разница по всем запасам и “фиктивным” планом. В случае положительной разницы строки называют недостаточными, в случае отрицательной разницы - избыточными, нулевыми строки называют в случае 0-разницы.
Отмечаются столбцы, с занятыми клетками в избыточных строках. Для каждой недостаточной и нулевой строки просматриваются приращения , стоящие в отмеченных столбцах, выбирается наименьшее в строке. Эти значения показывают, какое приращение стоимости будет получено на данном шаге, если единицу потребности перезакрепить от одного поставщика к другим (избыточные и недостаточные строки). Сравнивая со значениями нулевой строки, получим два случая:
а) для каждой нулевой строки минимальное значение меньше либо равно по отношению к приращениям нулевой строки.
б) минимальное приращение больше приращений нулевой строки;
В случае а) производится непосредственное перераспределение потребности из избыточной строки в недостаточную в клетку отмеченного столбца, которой соответствует минимальное
В случае б) составляются цепочки.
Для построения цепочки в нулевой строке в отмеченном столбце находим клетку, для которой разность меньше минимального значение , и отмечаем ее знаком “+”, в этом же столбце находим занятую клетку, стоящую в избыточной строке, и отмечаем ее знаком “-” - начало цепочки. Начиная движение по построенному звену цепочки от “-” к “+”, попадаем в нулевую строку, затем передвигаемся по нулевой строке к занятой клетке и отмечаем ее знаком “-”, далее по столбцу переходим в клетку недостаточной строки и отмечаем ее знаком “+”.
Составляем для каждой цепочки алгебраическую сумму приращения, считая их отрицательными, если они стоят в клетке, отмеченной знаком “-”, и положительными, если клетка отмечена знаком “+”. Если сумма больше минимального , то производится непосредственное распределение, если меньше, то распределение производится по цепочке.
Исключаем из рассмотрения отмеченные столбцы. Если занятая клетка избыточной строка стала незанятой или избыточной , то начинаем п.4. В противном случае продолжаем процесс до тех пор, пока все строки не превратятся в нулевые