Тема 4 распределительный метод

1. Математическая модель и особенности транспортной задачи

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

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

Модель транспортной задачи в общем виде записывается в следующей форме:

г де і — количество поставщиков; ј — количество потребителей; а_і — ограничения по предложению; b_j — ограничения по спросу; с_іј— элементы целевой матрицы; х_іј — объем корреспонденции между і-й и j-й точками.

Критерием оптимальности в транспортной задаче может быть минимум грузовой работы в тонно-километрах, затраты времени или стоимость перевозки.

Рассмотрим конкретный пример транспортной задачи.

Пусть имеются три грузообразующих точки А₁ А₂ и А₃, из которых следует вывезти однородный груз четырем потребителям (В₁, В₂, В₃, В₄) в количестве соответственно 400, 600 и 1000 т. При этом потребителю В₁ необходимо доставить 200 т. груза, В₂ — 400, В₃ — 800 и В₄—600т..

Расстояния между грузоотправителями и потребителями указаны в табл. 1.

Таблица 1

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

В этой задаче неизвестно количество груза, которое следует перевозить от каждого отправителя конкретному потребителю.

Обозначим через х_ij количество тонн груза, которое должно быть перевезено от i-го поставщика j-му потребителю. Тогда модель задачи выразится следующей системой уравнений:

Целевая функция будет представлять собой сумму произведений расстояний на соответствующий объем перевозок груза в тоннах:

В сe неизвестные могут принимать положительные значения или равняться нулю, т. е. хij ≥ 0.

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

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

2. Она совместна, т. е. имеет решение.

3. Элементами матрицы системы являются единицы и нули.

4. Система является линейно зависимой, так как любое ее уравнение можно представить в виде линейной комбинации остальных уравнений. Например, если из суммы уравнений (1), (2), (3) вычесть суммы уравнений (4), (5) и (6), то получим уравнение (7).

5. Число линейно независимых уравнений всегда на одно меньше общего количества уравнений в системе, так как без любого одного уравнения каждое оставшееся уравнение нельзя представить как линейную комбинацию из других уравнений. Следовательно, базис системы равен количеству уравнений за вычетом единицы. В нашем примере базис равен 6(7 - 1 = 6).

6. Целевая функция выражается линейной формой. Матрица целевой функции — это матрица-строка, элементами которой могут быть расстояния, время или стоимость перевозки.

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