Нахождение исходного допустимого решения

Назовем клетку в таблице свободной, если , в противном случае назовем клетку занятой.

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

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

В случае, когда число занятых клеток равно полученное допустимое решение называют невырожденным, в противном случае – вырожденным.

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

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

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

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

Дата добавления: 2015-06-30; просмотров: 110; Нарушение авторских прав

Мы поможем в написании ваших работ!