Транспортная задача.

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

Три основных алгоритма:

1. Метод северо-западного угла. Движение осуществляется с северо-запада на юго-восток.

f(x) = 1*20 + 2*40 + 6*70 + 5*40 + 2*10 + 4*100 = 1140

Метод северо-западного угла имеет существенный недостаток, т.к. построен без учета знаний коэффициентов затрат задачи (тарифов за перевозку).

Существует модификация этого метода, лишенная этого недостатка.

2. Метод наименьших затрат (метод наименьшего коэффициента).

На каждом шаге максимально возможную поставку следует давать не в северо-западную клетку, а в клетку с наименьшим коэффициентом затрат.

Алгоритм:

1. Находим в таблице поставок клетки с наименьшим коэффициентом затрат если их несколько (коэффициенты равны), то сравниваем максимально возможные поставки и даем поставку в ту клетку, где максимально возможная поставка больше.

2. Если же и максимально возможные поставки равны, то отдаем поставку любую из них.

f(x) = 2*60 + 1*20 + 2*100 + 3*50 + 4*7 + 4*10 = 810

3. Метод аппроксимации Фогеля.

Алгоритм:

Перед распределением единиц между поставщиками и потребителями необходимо провести ряд расчетов:

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

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

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

4. Затем вновь повторяют поиск двух наименьших тарифов, находят разность между ними и результаты записывают в отведенные для этого клетки, но здесь следует отметить, что тариф в заполненной клетке исключается из внимания и расчеты по оставшимся тарифам.

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

6. Расчеты проводят до тех пор, пока в клетках полностью не будут стоять « – »

f(x) = 1*20 + 2*10 + 5*30 + 5*10 + 2*110 + 3*100 = 760