транспортная задача Цель - в минимизации полной стоимости перевозок известного

количества товаров со складов к потребителю.


постановка транспортной задачи :

определение оптимального плана перевозок однородного груза
из m пунктов отправления A1, A2, . . . , Am
в n пунктов назначения B1, B2, . . . , Bn.


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

пунктов отправления A1, A2, . . . , Am
в

n пунктов назначения B1, B2, . . . , Bn.


определение минимального значения целевой функции стоимости перевозок




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

План, при котором целевая функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

опорного плана.

опорный план находят последовательно за n+m-1

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

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

Опорный план является исходным условием для проверки последнего на оптимальность и нахождения оптимального плана.

отправления и первый из оставшихся пунктов назначения.

Заполнение

клеток таблицы условий начинается с левой верхней клетки для неизвестного X11 (“северо-западный угол”)
заканчивается для неизвестного Xmn, т. е. идет как бы по диагонали таблицы с севера на запад.

A1, A2, A3 поступил однородный груз в количествах, соответственно равных

140, 180 и 160 ед. Это груз требуется перевезти в пять пунктов назначения B1, B2, B3, B4, B5 соответственно в количествах 60, 70, 120, 130 и 100 ед. Тарифы перевозок единицы груза с каждого из пунктов отправления в соответствующие пункты назначения указаны в таблице:

n=5

5+3-1=7
Заполнение таблицы начнем с неизвестного x11, т. е. попытаемся удовлетворить потребности первого пункта назначения за счет запасов первого пункта отправления. Так как запасы пункта A1 больше, чем потребности пункта B1, то полагаем x11=60, записываем это значение в соответствующей клетке табл и временно исключаем из рассмотрения столбец B1, считая при этом запасы пункта A1 равными 80.

назначения B2. Запасы пункта A1 больше потребностей пункта B2. Положим

X12=70, запишем это значение в соответствующей клетке табл и временно исключим из рассмотрения столбец B2. В пункте A1 запасы считаем равными 10 ед.

A1 и назначения B3. Потребности пункта B3 больше оставшихся запасов

пункта A1. Положим X13=10 и исключим из рассмотрения строку A1. Значение X13=10 запишем в соответствующую клетку табл и считаем потребности пункта B3 равными 110 ед.

x23 и т. д.
Через шесть шагов остается один пункт

отправления A3 с запасом груза 100 ед. и один пункт назначения B5 с потребностью 100 ед. Соответственно имеется одна свободная клетка, которую и заполняем, полагая x35=100. В результате получаем опорный план

ориентируясь на тарифы перевозок, а именно:

на каждом шаге следует

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

Сущность метода минимального элемента и состоит в выборе клетки с минимальным тарифом.

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

Поэтому более целесообразно опорный план транспортной задачи находить методом минимального элемента.

для переменной x13. Положим x13=160, запишем это значение в соответствующую

клетку таблицы и временно исключим из рассмотрения строку A1. Потребности пункта назначения B3 считаем равными 30.

A2 и A3 и четырьмя столбцами B1, B2, B3 и

B4 клетка с наименьшим тарифом находится на пересечении строки A3 и столбца B2, где С32=2. Положим X32=50 и внесем это значение в соответствующую клетку.

будем считать запасы пункта A3 равными 120. После этого рассмотрим

оставшуюся часть таблицы с двумя строками A2 и A3 и тремя столбцами B1, B3 и B4. В ней минимальный тариф находится в клетке на пересечении строки A3 и столбца B3 и равен 3. Заполним описанным выше способом эту клетку и аналогично заполним клетки, находящиеся на пересечении строки A2 и столбца B1, строки A3 и столбца B4, строки A2 и столбца B4. В результате получим опорный план. При данном плане перевозок общая стоимость перевозок составляет. S=1*160+4*120+8*20+2*50+3*30+6*90=1530

всем строкам находят разность между двумя записанными в них минимальными

тарифами.

разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи.

Среди разностей выбирают максимальную.

В строке (или столбце), которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.

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

разности между двумя минимальными тарифами, записанными в данной строе или

столбце, и поместим их в соответствующем дополнительном столбце или строке. Так в строке A2 минимальный тариф равен 4, а следующий за ним равен 5, разность между ними 5-4=1. Точно так же разность между минимальными элементами в столбце B4 равна 6-2=4.

них соответствует столбцу B4. В этом столбце минимальный тариф записан

в клетке, находящейся на пересечении строки A1 и столбца B4. Таким образом эту клетку следует заполнить.. Заполнив ее, тем самым мы удовлетворим потребности пункта B4. Поэтому исключим из рассмотрения столбец B4 и будем считать запасы пункта A1 равными 160-110=50