Метод вычеркивания

Метод вычеркивания позволяет проверить, является ли данное решение транспортной задачи опорным.

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

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

Ниже приведены примеры «вычеркиваемого» (опорного) и «невычеркиваемого» (неопорного) решений:

«вычеркиваемое» «невычеркиваемое»

Дата добавления: 2014-01-04