Метод решения задачи минимизации времени перевозок

Постановку и метод решения задачи, минимизации времени перевозок рассмотрим на следующем примере.

Пример. В четырех базах находятся одинаковые машины, единиц в i-й базе. Эти силы необходимо перевезти в пять мест, единиц в j-й позиции. Время перевозки машин из i-й базы в j-е место равно t_ij. Необходимо составить такой план развертывания, при котором оно будет выполнено в кратчайший срок.

Исходные данные для задачи представлены в таблице. Цифры в клетках на пересечении i-й строки и j-го столбца, указывают время перевозки из i-й базы в j-е место .

Приведем формальную постановку задачи. Пусть - количество машин перевозимых из i‑ й базы в j‑ е место. Поскольку количество машин в базах и на местах ограничено величинами и соответственно, на переменные накладываются ограничения: , . Целевую функцию сформулируем следующим образом: найти матрицу для которой целевая функция принимала бы минимальное значение. В связи с таким видом целевой функции задачи данного класса часто называют транспортными задачами по критерию времени.

№ базы	№ места

Полностью задача запишется следующим образом:

Сравнительный анализ задачи минимизации стоимости перевозок и задачи минимизации времени перевозок показывает, что они отличаются только целевыми функциями. Но различие это является принципиальным.

Действительно, в отличие от линейной целевой функции задачи минимизации стоимости, целевая функция в задаче минимизации времени является кусочно-линейной. Следовательно, к ней даже в принципе не применим симплекс-метод и методы, построенные на его основе.

Для решения таких задач применяется метод разгрузочных цепей, суть которого заключается в следующем. Пусть на k‑ й итерации получен опорный план X^k. Этому плану соответствует матрица времени , где n – число исходных, m – число конечных пунктов, а элементы находятся из соотношений

Найдем в матрице элемент такой, что . Метод разгрузочных цепей позволяет от плана X^k перейти к плану X^k⁺¹такому, что , если только он существует, или установить, что план X^kявляется оптимальным. Алгоритм метода разгрузочных цепей проиллюстрируем, решив с его помощью задачу из примера.

В транспортной таблице приведен начальный опорный план задачи, составленный с помощью способа наименьшего элемента. Целевая функция для этого плана равна 8, (Z = t₄₅=8). Попытаемся уменьшить значение целевой функции. Для этого необходимо исключить из базиса переменную x₄₅, равную единице. Исключив переменную x₄₅, мы должны увеличить значение одной из переменных в строке 4 или столбце 5 на единицу.

Учитывая то обстоятельство, что , увеличим на единицу именно . Руководствуясь теми же соображениями, уменьшим и увеличим на единицу. Процесс перехода от клетки к клетке, отображен в таблице в виде стрелок. Полученный в результате план отображен в следующей таблице. Значение целевой функции на этом плане равно 4, (Z=t₁₅=4).

№ базы	№ места


2		13-1	+1
3
4		7+1	1-1

№ базы	№ места

Улучшить новый план можно, только исключив из базиса переменную , равную 4. Но исключение, ее из базиса неизбежно повлечет увеличение до 28 , а это приведет к нарушению ограничения исходной задачи. Следовательно, найденный опорный план является оптимальным.

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

⇐ Предыдущая 1 2 3 4 567 Следующая ⇒