Грузовые автомобильные перевозки (Часть 3)
В нашем примере мы получим цепь VI—V—II—III—VI. Величина поставки 50 ед. прибавляется к поставкам дуги Н-Ш и вычитается из дуги II-VI. Выбранная ранее стрелка с противоположной поставкой ликвидируется. Общее количество стрелок остается неизменным. Очередная проверка показывает, что новый базисный план получился оптимальным.
Если при полном использовании мощностей и полном удовлетворении спроса количество стрелок оказывается меньше, чем Р -1, то задача оказывается вырожденной. Способ борьбы с вырождением заключается в том, что вводятся дополнительные стрелки с нулевыми поставками. Совершенно безразлично, из положительной или отрицательной вершины будут выходить, и входить стрелки. Важно, чтобы стрелки не образовывали замкнутую цепь.
При сетевой постановке задач задаются не только поставщики и потребители, но могут задаваться и пункты пересечения участков - вершин, в которых нет ни поставщиков, ни потребителей. Наличие таких нулевых вершин не меняет способа решения. Им присваиваются потенциалы на тех же основаниях, что и другим вершинам, но их спрос или предложение равны нулю.
Результаты решения транспортных задач на сети и по матрице совпадают только в том случае, если не учитываются ограничения пропускной возможности дорог. В матричных алгоритмах каждый поставщик и потребитель может быть соответственно только отправителем или получателем груза. Движение груза через поставщика или через другого потребителя в явном виде невозможно. При сетевой постановке задачи движение груза из одного пункта в другой выбирается в ходе самого расчета.
Когда при матричной постановке задачи говорят, что из пункта г в пункт j можно перевезти не более такого-то объема груза, то на самом деле это означает лишь невозможность перевозки большего количества груза по наивыгоднейшему пути между этими пунктами. Блокируя такой путь для большего объема груза, мы не рассматриваем возможность передвижения груза между этими пунктами по другим дорогам, так как в действительности ограничения распространяются на какие-то участки дороги. Поэтому запись ограничений пропускной возможности при сетевой постановке задачи больше соответствует реальным условиям, а следовательно, и дает истинный оптимум.