2) Методы решения тз.

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

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

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

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

задачи.

Дано: на трех станциях отправления А₁, А_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.

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

пункт назначения	В1	В2	В3	В4	запасы
ст. отправления
А1	x11	x12	x13	x14	a1
	c11	c12	c13	c14
А2	x21	x22	x23	x24	a2
	c21	c22	c23	c24
А3	x31	x32	x33	x34	a3
	c31	c32	c33	c34
потребности	b1	b2	b3	b4

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

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

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. Какие методы ее решения Вы узнали?