Транспортная задача и методы её решения

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

1. Расстояния в первой и четвертой строках таблицы (табл. 22) умножаем на 1,00, во второй -- на 1,20 и в третьей -- на 1,25; в результате получаем новую таблицу расстояний (табл. 23).

Таблица 22

2. Объемы угля в пунктах отправления выражаем в тоннах условного топлива, т.е. А₁=30 * 1=30 т, А₂=50 * 1,2=60 т, А₃=40 * 1,25=50 т и A₄=20* 1=20 т.

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

Таблица 23

Таблица 24

Таблица 25

9. Усложнённая задача перевозки разнородной продукции

К классической транспортной задаче можно свести и более сложную задачу. Изменим условия только что рассмотренной задачи. Пусть в пункте А₂ имеется уголь двух марок - 24 т марки А и 30 т марки Б. Кроме того, введем покое условие: клиент Б₄ может использовать уголь только марок А и В, а клиент В, уголь также только марок А и Б. Остальные условия прежние.

Чтобы решить эту задачу методом потенциалов необходимо:

1) пункт отправления А₂ рассматривать как два пункта - А`₂ и А``₂, в каждом из которых имеется уголь только одной марки;

2) клетки матрицы, соответствующие запрещённым перевозкам, блокировать;

3) в остальном поступать так же, как и при решении предыдущей задачи.

В табл. 26 представлена оптимальная схема прикрепления потребителей угля за поставщиками в тонах условного топлива, а в табл. 27 -оптимальный план перевозки угля (* - уголь марки А;** - уголь марки Б).

10. Транспортная задача по критерию времени

Нередко при выполнении перевозок решающее значение приобретает фактор времени. Это имеет место, например, при вывозке зерна на заготовительные пункты во время уборки урожая, при перевозке скота и др. Рассмотрим такую задачу.

Пусть из пунктов А₁, А₂, ..., А_i, ...,А_m в пункты В₁, В₂, ..., В_j, …, В_n необходимо доставить однородный продукт в возможно короткое время. Запасы продукта в пунктах отправления и потребность в нём в пунктах назначения равны между собой и составляют соответственно а₁, а₂, ..., а_i, ..., a_m и b₁, b₂, …, b_j, …, b_n единиц. Время доставки груза из каждого пункта А_i в каждый пункт В_j известно и составляет t_ij часов.

Таблица 26

Таблица 27

Прежде чем сформулировать критерий оптимальности, проанализируем задачу. Очевидно, что срок доставки всей продукции определяется самой продолжительной перевозкой. Чтобы его уменьшить, необходимо сократить время самой продолжительной из выполняемых перевозок. Из этого следует, что использование в качестве критерия оптимальности линейной формы

T = t _ijx_ij (23)

не даст нужного результата: решение, для которого величина Т достигает минимального значения, как, правило, не будет оптимальным по времени. В табл. 28 представлен план перевозок, оптимальный по минимуму линейной формы Т. Все перевозки по этому плану будут выполнены за 8 ч. при Т = 370 ч.

Таблица 28

В табл. 29 показан другой план этой задачи, по которому значение линейной формы несколько больше - Т = 380 ч (план по критерию Т не оптимален, так как t_ij < u_i + v_j), но все перевозки выполняются за 5 ч.

Таблица 29

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

Обозначим через x_ij количество груза, планируемого к отправке из пункта A в пункт B. Тогда при выбранном критерии оптимальности задача формируется следующим образом: определить набор чисел x_ij (план перевозок), для которого время t (X) наиболее продолжительной перевозки

t ( X) = max t_ij для x_ij > 0 (24)

достигает минимума при условиях

x_ij = b_j, j = 1, 2, …, n; (25)

x_ij = a_i, i= 1, 2, …, m; (26)

x_ij > 0, i= 1, 2, …, m; j = 1, 2, …, n. (27)

Выражение (24) означает наибольшее из времен запланированных перевозок.

Так как t (X) - нелинейная функция своих переменных x_ij, то модель (24) - (27) не является задачей линейного программирования. Это задача на минимакс, и решить её методами линейного программирования нельзя. Вместе с тем решение задачи можно свести к последовательному решению одним из способов распределительного метода (методом потенциалов) серии обычных транспортных задач, где оптимальное решение предыдущей задачи служит исходным планом последующей задачи. Процедура вычислений складывается из следующих шагов.

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

2. Найти методом потенциалов план, у которого линейная форма

t_ij x_ij достигает минимального значения.

3. Определить max t_ij (наибольшее из времён) запланированных перевозок (где x_ij >0).

4. Во всех клетках матрицы, где t_ij = max t`_ij, заменить на число M = .

5. Отыскать для изменённой матрицы решение, при котором линейная форма t_ij x_ij достигает минимума. Если в полученном решении

x_ij > 0 расположены только в клетках, где t_ij < М, то снова находим mах t``_ij и повторяем шаги 4 и 5. Если же в полученном решении имеется хотя бы один x_ij > 0, расположенный в клетке с t_ij = М, то оптимальным по критерию (24) будет предыдущее решение.

Очевидно, что после конечного числа повторений шагов 3, 4 и 5 будет получено оптимальное решение, т.е. такой план перевозок, по которому грузы всем потребителям будут доставлены за возможно короткое время.

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

Таблица 30

Таблица 31

Решив эту матрицу методом потенциалов, находим план (табл. 31), обеспечивающий минимум линейной формы. Наибольшее время перевозки по этому плану составляет 12 ч ( перевозка А₁ в В₄). Во всех клетках, где время доставки груза равно или больше этой величины (клетки А₁В₄ и А₄В₄), заменяем его числом М = 100 (блокируем клетки) и вновь отыскиваем план, у которого линейная форма имеет наименьшую величину (табл. 32). Поскольку ни одна из загрузок не находится в блокированной клетке (с числом 100), продолжаем вычисления.

Таблица 32

Таблица 33

Теперь наибольшее время перевозки составляет 10 ч (клетка А₄В₁,), поэтому блокируем клетки А₁B₁, А₃В₄ и А₄В₁, у которых время равно 10 ч, и находим новый план (табл. 33) с минимальным значением линейной формы. Из таблицы видно, что ни одна из загрузок не находится в блокированной клетке, поэтому процесс вычислений необходимо продолжить.

Таблица 34

Поскольку наибольшая продолжительность из планируемых перевозок равна 8 ч (клетки А₂В₄ и А₄В₃), блокируем клетки А₂В₄, А₄В₂ и А₄В₃, у которых время равно 8 ч или больше 8 ч. В найденном затем новом плане (табл. 34) две загрузки находятся в блокированных клетках.Это свидетельствует о том, что план перевозок, обеспечивающий доставку грузов всем потребителям за возможно короткое время, найден (см. табл. 33)

Использованная литература

Методы линейного программирования для решения транспортных задач: Учебное пособие/ В. М. Тропина; Тул. гос. ун-т.- Тула, 1999.