Транспортная задача. Матричные игры: Методические указания к практическим занятиям, страница 4

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

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

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

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

  невязок, соответствующих выделенным рядам; по условию баланса равна нулю и последняя, я  невязка. Это означает справедливость всех равенств (7), т.е. выполнение  свойства а).

Свойство  в)  очевидно для циклов С,  не содержащих занятых клеток – в таких циклах  не заняты все клетки. Пусть С  содержит занятые клетки таблицы после  го шага, и   имеет наименьший  номер среди всех занятых клеток цикла С.  Рассмотрим клетки    и  ,  соседние  с    в С. Хотя бы одна из них должна остаться   незанятой, так как  после  го  шага  выбор клеток из ой  строки или  го столбца прекращается.

В описанном выше процессе на  ом  шаге  можно заполнять любую из   клеток  «незапрещенной» части таблицы. Различные методы построения начальной опорной таблицы получили свои названия по правилу выбора очередной занятой клетки. В методе  северо-западного угла (СЗУ) всегда выбирается левая верхняя (северо-западная)  клетка незапрещенной части таблицы, в методе минимальной стоимости (МС) – та из клеток этой части, которой соответствует наименьшее значение стоимости

Пример 2. Для ТЗ из примера 1 построить начальную опорную таблицу методом  СЗУ; методом МС.

Решение. На первом шаге метода СЗУ запишем в левую верхнюю клетку (1, 1) число    вычислим  

  выделим  1-ый столбец  (символы   во всех незанятых клетках); запишем новое значение невязки 1-ой строки  Результат  1-го шага представлен на рис.3а).