Транспортная задача по критерию времени - Анализ транспортной задачи по критерию времени

Задача по критерию времени возникает при перевозке срочных грузов. Как и в обычной транспортной задаче, имеется m поставщиков с запасами однородного груза в количестве a1,a2, ...,am и n потребителей, которым этот груз доставляется от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок груза, при котором запасы всех грузов являются минимальным.

Составим математическую модель этой задачи. Обозначим xij - объем перевозимого груза от i-го поставщика j-му потребителю. Система ограничений задачи не отличается от системы ограничений обычной транспортной задачи. Пусть Х=(Хij), i=1,2 ...,m; j=1,2,..., n - некоторое опорное решение задачи. Запишем целевую функцию задачи. Обозначим через Т(Х) наибольшее значение элементов матрицы Т=(tij), i=1,2,..., m; j=1,2,..., n, соответствующих клеткам таблицы, занятым опорным решением: Т(Х)= max{tij}. Таким образом, за время Т(Х) план перевозок будет выполнен полностью. транспортный экономический математический

Задача решается в следующем порядке. Находится начальное опорное решение Х1. Определяется значение целевой функции Т(Х1)=max{tij}=tl1k1. Все свободные клетки, которым соответствует значение tij>T(X1), исключается из рассмотрения (перечеркиваются). Занимать эти клетки нецелесообразно, так как увеличивается значение целевой функции. Чтобы уменьшить ее значение, необходимо освободить клетку (l1, k1), в которой tij достигает максимума. Для этого строят так называемые разгрузочные циклы, которые могут включать в свой состав несколько свободных клеток. В каждом разгрузочном цикле, начиная с разгружаемой клетки (l1, k1), расставляются поочередно знаки "-" и "+" и осуществляется сдвиг на величину Q=min {xij}. Если удается эту клетку разгрузить, то она исключается из рассмотрения (зачеркивается). Получается новое опорное решение Х2, на котором значение целевой функции меньше, чем на Х1.

Далее снова пытаются разгрузить клетку, соответствующую Т(Х2)=max{tij}=tl2k2. Процесс продолжается до тех пор, пока возможность разгрузить соответствующую клетку не исчезнет.

Похожие статьи




Транспортная задача по критерию времени - Анализ транспортной задачи по критерию времени

Предыдущая | Следующая