Методы решения ТЗ

Транспортная задача является одной из основных оптимизационных математических задач. Впервые постановка ТЗ была проведена в 1930г. в трудах советского экономиста А. Толстого. В 1941г. решение ТЗ предложил венгерский экономист Эгервари, поэтому один из методов решения ТЗ называется «венгерский метод». В 1941г. решение задачи окончательно сформулировал американский математик Хичхок.

В СССР внедрение математических методов решения задач было осуществлено в 1958г. в автотранспортной промышленности.

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

a) Получение математической модели классической транспортной

задачи.

Дано: на трех станциях отправления А₁, А_2, А₃ сосредоточено соответственно а₁, а₂ и а₃ тонн грузов. Эти грузы надо доставить в 4 пункта назначения В_1,В₂,В₃ и В₄ соответственно b_1, b_2, b_3,b_4. При этом сумма запасов на А_i (i=1,2,3) равна сумме потребностей на B_j(j=1,2,3,4),или

а₁₊ а₂₊ а₃= b₁+b₂₊ b₃ +b₄, или в общем виде:

Транспортные расходы на перевозку 1т груза от станции i в пункт j известны и обозначаются С_ij

Требуется составить такой план перевозок, чтобы:

- общие расходы по перевозке были минимальными;

- был полностью удовлетворен спрос на B_j

- был полностью вывезен груз с А_i

Решение.

Обозначим х₁₁ – кол-во груза перевозимого из А₁ в В₁

х₁₂ – кол-во груза перевозимого из А₁ в В₂

и т.д., в общем виде х_ij – кол-во груза, перевезенного из станции i в пункт назначения j.

Полученные исходные данные удобнее записать в виде специальной таблицы:

С одной стороны:

общее кол-во груза, доставленного в В₁ равно

b₁= x₁₁+x₂₁+x₃₁ , т.е. потребность в грузе удовлетворена.

С другой стороны:

общее количество груза отправленного с А₁ равно

a₁=x₁₁+x₁₂+x₁₃+x₁₄, т.е. груз вывезен полностью.

Аналогично рассуждая запишем остальные равенства:

b₂= x₁₂+x₂₂+x₃₂ a₂=x₂₁+x₂₂+x₂₃+x₂₄

b₃= x₁₃+x₂₃+x₃₃ и a₃=x₃₁+x₃₂+x₃₃+x₃₄

b₄= x₁₄+x₂₄+x₃₄

Тогда общие транспортные расходы составят:

Z=c₁₁x₁₁+c₂₁x₂₁+c₃₁x₃₁+c₁₂x₁₂+c₂₂x₂₂+c₃₂x₃₂+c₁₃x₁₃+c₂₃x₂₃+c₃₃x₃₃+c₁₄x₁₄+c₂₄x₂₄₊

+c₃₄ x₃₄,

или в общем виде:

Таким образом, математическая модель ТЗ имеет вид:

среди неотрицательных решений системы:

a₁=x₁₁+x₁₂+x₁₃+x₁₄

a₂=x₂₁+x₂₂+x₂₃+x₂₄

a₃=x₃₁+x₃₂+x₃₃+x₃₄

b₁= x₁₁+x₂₁+x₃₁

b₂= x₁₂+x₂₂+x₃₂

b₃= x₁₃+x₂₃+x₃₃

b₄= x₁₄+x₂₄+x₃₄

выбрать такое, при котором было бы минимальным.

Или для общего случая:

при условии, что

(сумма запасов на всех станциях отправления равна сумме потребностей пунктов назначения)

min

б) Методы решения транспортной задачи.

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

Наиболее известными методами построения опорных планов являются:

- метод северо-западного угла;

- метод минимального элемента;

- аппроксимация Фогеля;

- метод двойного предпочтения.

Полученный таким образом опорный план оптимизируется одним из следующих методом:

- метод потенциалов;

- метод дифференциальных рент;

- венгерский метод;

- дельта-метод;

- распределительный метод.

На практике наиболее часто используется метод потенциалов. Впервые был предложен в 1949г. советскими математиками Канторовичем и Гавуриным, окончательно был сформирован американцем Данцигом. Суть плана – текущий базисный план проверяется на оптимальность, при необходимости осуществляется переход к «лучшему» базисному плану.

Литература: 2, 5-25 с.

Контрольные вопросы:

1. Почему транспортная задача называется транспортной?

2. В чем ее суть?

3. Какие методы ее решения Вы узнали?