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

В этом случае значение разности () представляет собой объем товара (в единицах его измерения), перевезенного через -ый промежуточный пункт, так как  - максимально возможный объем поставок товара на склад с номером , a  — объем товара, осевшего на этом складе. В таблице 5 заполнены лишь те клетки, которые содержат переменные , соответствующие направленным дугам сети, а также переменные , соответствующие промежуточным пунктам. Именно в этом и заключается отличие таблицы 5 от таблицы 1.

Следует отметить, что в таблице 4 заданы восемь ограничений и десять переменных, а в транспортной  таблице заданы уже тринадцать ограничений (по строкам и столбцам) и пятнадцать переменных. Увеличение размерности на пять единиц объясняется наличием пяти промежуточных пунктов.

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

Нетрудно убедиться в том, что в транспортной таблице 5 строка, соответствующая первому складу (исток), и столбцы, соответствующие третьему и восьмому складам (стоки), задают те же ограничения, что и соответствующие строки в таблице 4. Обратимся теперь к -му складу, являющемуся промежуточным пунктом, т.е. }. Пусть  - множество номеров складов, на которые товар может быть доставлен с -го склада, а  - множество номеров складов, с которых товар может быть доставлен на -ый склад. Тогда ограничение для -го склада, заданное в таблице 4, имеет следующий вид:

 

 

Где   - величина, чистого запаса товара, введенная на третьем этапе построения рассматриваемой транспортной таблицы 5.

Так как соответствующие ограничения, задаваемые в транспортной таблице 5 (по строке и по столбцу), могут быть представлены следующим образом:

 

 

 

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

На этом доказательство того, что рассматриваемая транспортная задача с промежуточными пунктами эквивалентна классической транспортной задаче, можно считать завершенным.6

 

 

 

 

4. Вырожденные планы. Циклы и пополнение плана

Далее покажу, каким требованиям должны удовлетворять составляемые планы. Для этого вернемся к системе ограничений (1) (2). В соответствии с определением плана перевозок у матрицы сумма элементов й строки равняется , , а сумма элементов -го столбца равняется , . Условие закрытости транспортной задачи означает, что среди уравнений системы (1), (2) независимыми являются только уравнений, поэтому в любом базисном решении этой системы должно быть базисных переменных. Поскольку свободные переменные в таком решении равны нулю, то в транспортной таблице им будут соответствовать пустые клетки. Клетки таблицы, в которые записаны отличные от нуля перевозки, называются базисными, а остальные (пустые) - свободными.

Определение 8.

План называется вырожденным, если количество базисных клеток в нем меньше, чем .

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

Определение 9.

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

Ломаная линия может иметь точки самопересечения, но не в клетках цикла.

 

 

Определение 10.

План называется ациклическим, если его базисные клетки не содержат циклов.

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

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

Доказательство. Опорное решение занимает 1 клеток таблицы, которым соответствуют линейно независимые векторы-условия. Если же к занятым клеткам присоединить одну свободную, то соответствующие им m+n векторов линейно зависимы, и по той же теореме существует цикл, содержащий эту клетку. Предположим, что таких циклов два  (i1,j1), (i1,j2), (i2,j2), …, (ik,j1) и (i1,j1), (i2,j1), …, (i1,ji). Тогда, объединив клетки обоих циклов без свободной клетки  (i1,j1), получим последовательность клеток  (i1,j2), …, (ik,j1), (i2,j1), …, (i1,ji), которые образуют цикл. Это противоречит линейной независимости векторов-условий, образующих базис опорного решения. Следовательно, такой цикл единственный.

Возвращаясь к рассматриваемому примеру 3, видим, что первоначальный план, полученный по методу наименьшей стоимости, имеет 5 базисных клеток, однако . Значит, план нужно пополнить еще одной базисной клеткой. Попробуем выбрать для этого клетку Соединив базисные клетки горизонтальными и вертикальными отрезками (рис. 4), получаем:

 

 

Видим, что пополненный таким образом план содержит цикл из клеток , следовательно, клетка была выбрана неудачно. Взяв вместо нее клетку получим ациклический план (рис. 5). Поэтому можно заполнить эту клетку, положив . 7

 

 

 

 

 

 

 

 

 

 

 

 

 

5. Задача выбора кратчайшего пути

Пусть задана некоторая сеть (рис. 3), каждой ориентированной дуге которой соответствует определенное расстояние. Необходимо найти кратчайший путь из -го узла сети в ее заданный -й узел. К этой задаче, известной в исследовании операций как задача выбора кратчайшего пути, сводятся такие практически важные задачи, как задача о замене оборудования, задача о календарном планировании комплекса работ и т.д. 

Как правило, в сети выделяют один узел, который является конечным (пункт или станция назначения, сток). Задача заключается в отыскании кратчайшего пути в этот конечный узел (на рис. 3 конечным является узел с номером 8) из некоторого другого узла сети (например, из первого узла сети на рис. 3). Величина пределяет расстояние от -го узла сети до ее -го узла.

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

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

Существуют сети, содержащие циклы, каждый из которых представляет собой замкнутый путь (путь, исходящий из некоторого узла сети и возвращающийся в него же). Так, в сети представленной на рис. 3, много циклов, один из них содержит узлы с номерами 2, 3, 5, 6 и 7. Как правило, в задачах исследования операций значения положительны и общая длина цикла является положительной. Следовательно, решение задачи выбора кратчайшего пути не может содержать циклов.

Пусть, для сети, представленной на рис. 3, необходимо найти кратчайший путь от узла с номером 1 (источник) до узла с номером 8 (сток). Установлю связь этой задачи с классической транспортной задачей.

Рассмотрим транспортную задачу с промежуточными пунктами, сеть которой представлена на рис. 3. При этом предположим, что:

а) в узле с номером 1 имеется избыточная единица товара;

б) в узле с номером 8 имеется недостаток единицы товара;

в) узлы с номерами 2-7 являются промежуточными пунктами с нулевыми чистыми запасами (потребность в дополнительных поставках товара равна нулю).

Необходимо разработать план перевозок товара между узлами сети (складами), который при минимальных транспортных затратах позволит на каждом складе поддерживать нулевой чистый запас товара.

Как и в примере 2, считаем, что каждой ориентированной дуге сети соответствует переменное модели , представляющее собой количество товара, которое должно быть отправлено с -го склада на -й. Для каждогого промежуточного пункта вводим переменное с соответствующим ему коэффициентом = 0 в целевой функции, а величину чистого запаса обозначаем через . Если множество пар индексов соответствующих ориентированным дугам сети, представленной на рис. 3, обозначить через , то рассматриваемую задачу можно записать следующим образом:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6. Первоначальный план перевозок

Транспортная задача относится к задачам линейного программирования, и ее можно было бы решить симплекс-методом. Но поскольку система ограничений транспортной задачи проще, чем система ограничений основной задачи линейного программирования, то это дает возможность вместо использования объемных симплекс-таблиц применить более удобный метод, который состоит из следующих этапов:

1. Составление первоначального  плана перевозок;

2. Последовательные улучшения  плана перевозок (перераспределение  поставок) до тех пор, пока план  перевозок не станет оптимальным.

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

6.1.Составление первоначального плана перевозок с помощью метода северо-западного угла

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

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

 

Алгоритм:

1. если , то и исключается поставщик с номером , , ;
2. если , то и исключается потребитель с номером , ,      ;
3. если , то и исключается либо-й поставщик, , , , либо -й потребитель, , , .

 

Проиллюстрирую это на следующем примере.

 

Пример 3.

Таблица 6.

Заказы Запасы
				20
				30
				30		60

Распределяя запасы поставщика сначала потребителю а затем , получаем: . После этого у поставщика остается еще 20 единиц груза, а потребителю нужно 80 единиц. Удовлетворим спрос потребителя , отправив ему 20 единиц груза, оставшихся у поставщика 30 единиц груза от поставщика и 30 единиц груза от . Следовательно, , причем у поставщика остается 60 последних единиц груза. Этот груз и отправим потребителю .

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

 

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

6.2 Составление первоначального плана перевозок с помощью метода наименьшей стоимости

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

 

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