Этап третий

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

Все 0 матрицы выделены, т.е. находятся в выделенных строках или столбцах, в этом случае переход к третьему этапу.

Этап второй.

Последний элемент цепочки это 0 со штрихом.

Шаг второй: В построенной цепочке 0 со штрихом заменяется на 0 со звездочкой, а звездочка аннулируется. А остальные элементы матрицы C_k которые не вошли в цепочку, остаются без изменения. Все штрихи и все "+ " в строках уничтожаются. Остаются 0 со звездочкой. Получаем матрицу.

В матрице все столбцы с независимым 0 помечаются знаком "+" при этом матрице С_к+1 количество независимых 0 увеличится на один. Если количество 0 станет равным n, то конец. Записывается матрица X с единицами в позициях соответствующим независимым 0 в С_к+1 и вычисляется критерий эффективности.

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