Нахождение исходного опорного решения транспортной задачи

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

Ввиду того, что r = p+q-1, опорное решение не может иметь отличных от нуля координат более p+q-1. Число отличных от нуля координат невырожденного опорного решения равно p+q-1, а для вырожденного опорного решения меньше.

1. Метод северо-западного угла

2. Метод минимальной стоимости

3. Метод двойного предпочтения

1. Начинают с того, что приписывают переменной x11, стоящей в северо-западном углу таблицы, минимальное из значений a1 и b1.

x11=min a1b1

Двигаются в соседнюю клетку по строке вправо, если a1>b1, или по столбцу вниз если a1<b1, полагая x12=a1-b1b2(min), x21=b1-a1a2(min). Это продолжают до тех пор, пока не исчерпаются ресурсы и потребности. Последняя заполненная клетка окажется pq. Решение, получаемое по методу сз угла – опорное решение.

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

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

3. В каждом столбце отмечают знаком √ клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки имеют отметку √√. В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.

Цикл – набор клеток вида (i1k2,i2k1), в котором только две соседние клетки расположены в одном столбце или одной строке распределительной таблицы, причем последняя клетка находится в том же столбце или в той же строке, что и первая.

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

Поиск по сайту: