Теорема о разрешимости транспортной задачи

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

.

Если данное условие нарушается, то задача называется открытой.

Если суммарный запас продукта превышает спрос, т.е.:

,

то в рассмотрение вводится фиктивный пункт потребления со просом, равным:

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

Если общий спрос потребителей больше суммарного запаса, то вводится фиктивный пункт отправления с запасом продукта:

.

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

3. Построение начального плана транспортной задачи

Начальный опорный план представляет собой распределительную таблицу, состоящую из загруженных клеток, называемых базисными и пустых – свободными. При этом число базисных клеток должно быть ровно m + n – 1. Такой план называется невырожденным.

Составить начальный опорный план можно различными способами.

Способ "северо-западного угла". Первой загружается клетка (1; 1). Если закрывается строка, то следующей загру­жается клетка (2; 1); если же закрывается столбец, то следу­ющей загружается клетка (1;2). Итак, каждый раз загружа­ется клетка, соседняя либо по строке, либо по столбцу (в за­висимости от конкретных данных задачи). Последней будет загружена клетка (m,n). В результате загруженные клетки расположатся вдоль диагонали (1; 1) — (m,n), поэтому способ "северо-западного угла" называют еще диагональным спосо­бом.

Способ "предпочтительных оценок ". Решая задачу на минимум, заполнение таблицы начинается с клетки с наименьшим значением оценочного коэффициента, а при решении задачи на максимум – с клетки с наибольшим значением. Затем находим лучшую клетку из оставшихся и так до полного распределения ресурсов.

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

Способ Фогеля. Прежде всего по каждой строке и каж­дому столбцу находят разности двух наименьших тарифов (будем записывать их за пределами распределительной та­блицы напротив соответствующих строк и столбцов). Из этих разностей выделяется наибольшая, и в соответствующей стро­ке (столбце) загружается клетка с наименьшим тарифом. За­крывшаяся строка (столбец) исключается из дальнейшего рассмотрения. Описанная операция повторяется до тех пор, пока не закроются все строки и столбцы.

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