57.Расчет оценок оптимальности распределения транспортных задач и критерий оптимальности.

Исходя из соотношения теоремы оптимальности, формула для вычисления оценок свободных клеток: = + - . Для того чтобы оценки не перепутать с объемами перевозок, оценки заключаются в кружки и проставляются в таблицу.

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

Также, если оценка оптимальности отрицательна, то необязательно находить ее значение. Достаточно поставить вместо числа знак ”-“,т.е. отметить, что клетка благоприятна.

Критерий оптимальности транспортной задачи

План перевозок: ,i=1…m,j…n,является оптимальным тогда и только тогда если:

1) + = – для базисных,

2) ≥ + – для небазисных.

58. Перераспределение поставок в транспортной задаче

Найдем клетку с наибольшей по абсолютной величине отрицательной

разностью ∆cij и построим цикл, в котором кроме этой клетки все остальные

являются базисными. Такой цикл всегда существует и единственен.

Заметим, что в новом плане суммы элементов по строкам и столбцам

должны остаться прежними, поэтому изменение значения в одной клетке

цикла повлечет за собой соответствующие изменения значений во всех ос-

тальных клетках этого цикла. Так как в свободной клетке значение будет

увеличено, то проставим в ее правом нижнем углу знак ⊕ . Теперь пройдем

по всей ломаной цикла, проставляя в правых нижних углах клеток поочеред-

но знаки «плюс в кружке» и «минус в кружке».

Груз будет перераспределен по клеткам цикла на величину ∆x = min xij

следующим образом. В клетках со знаком «плюс» значение перевозки нужно

увеличить на величину ∆x , а в клетках со знаком «минус» – уменьшить на

величину ∆x . Так как после пересчета у нас добавилась лишняя базисная

клетка, то их количество необходимо сократить, убрав нуль в одной из кле-

ток цикла. Если таких клеток получилось несколько, то свободной делаем ту

из них, в которой тариф перевозок максимален.

После этого полученный план проверяется на оптимальность описан-

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

очередной план не станет оптимальным. На этом действие алгоритма завер-

шается.

59. Цепочки перераспределения, их виды.

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

имели поставки. Перемещения внутри цикла по таблице возможны только по

прямым линиям, расположенным под прямым углом по отношению друг к другу.

Число клеток, участвующих в цикле, должно быть четным.

Начинается цикл из клетки, куда должна быть осуществлена поставка.

Двигаясь по горизонтали или по вертикали, находим клетку с поставкой, откуда

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

поставкой (под прямым углом) и так далее до тех пор, пока не вернемся в начальную

клетку. Конфигурация цикла может быть различной. Например,