Многоэтапные транспортные задачи

Существуют два типа много этапных задач:

1) производственные мощности промежуточных звеньев меньше либо равны мощности начального и конечного звеньев;

2) мощность промежуточных звеньев превышает мощность начального и конечного звеньев.

Задачи первого типа не отличаются от однопродуктовых. Такая задача разбивается на блоки и решение осуществляется по блокам.

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

Пример.С трех глиняных карьеров А_1, А₂ и А₃ поступает глина на четыре кирпичных завода В₁, В₂, В₃ и В₄. Кирпичные заводы поставляют свою продукцию на две стройки С₁ и С₂. Данные о мощностях и расстояния между объектами приведены в табл. 2.6.

Эта задача относится ко второму типу, так как ∑А < ∑В, а ∑В > ∑С, поэтому необходимо построить таблицу с фиктивной диагональю. При построения таблицы выделяют блоки куда будут осуществляться поставки согласно условию.

Таблица 2.6

Исходная таблица мощностей и расстояний

Особого внимания заслуживают клетки, которые находятся на пересечении одноименных строк и столбцов – это клетки фиктивной диагонали. Внутри них оценка затрат равна 0. По экономическому смыслу груз, размещенный в этих клетках, означает неиспользованную мощность предприятия. Все остальные клетки заштриховываются. После этого задача решается методом потенциала. Кратко рассмотрим механизм решения подобных задач на примере (табл. 2.7).

Пример

Таблица 2.7