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

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

Любой  опорный план можно представить таблицей ТЗ, в которой заняты ровно    клеток, соответствующих порождающему этот план базису; такие таблицы называются  опорными.  Для невырожденного опорного плана представляющая его опорная таблица единственна, в ней все    чисел в занятых клетках положительны (не равны нулю). Для вырожденного опорного  плана занятые нулями клетки позволяют восстановить один из порождающих этот план базисов.

При описании свойств и преобразований таблиц ТЗ важную роль играет понятие цикла.

Последовательность (неповторяющихся) клеток прямоугольной таблицы называется циклом, если любые две соседние  клетки последовательности, а так же первая с последней, расположены  в одном ряду (строке или столбце), а любой ряд таблицы содержит только одну такую пару или не содержат их вовсе. Графически цикл изображается  ломаной линией, в которой чередуются горизонтальные и вертикальные  звенья, соединяющие соседние клетки. Число клеток в цикле обязательно чётное. Примеры циклов даны на рисунке 1.

Рис.1

Сформулируем без доказательства основные свойства таблиц ТЗ, связанные с понятием цикла.

Теорема 1. Таблица ТЗ является опорной тогда и только тогда, когда в ней  ровно     занятых клеток и любой цикл таблицы содержит хотя бы одну незанятую клетку.

Теорема 2. Для каждой незанятой клетки опорной таблицы ТЗ можно образовать, и при этом только один содержащий данную клетку цикл, в котором все остальные клетки заняты.

Пример 1.  На рис.2 представлены четыре заполненные таблицы одной и той же  ТЗ  с   поставщиками  и    потребителями (циклы в таблицах  в)   и  г)   относятся не к условию задачи данного примера, а к её решению).

Рис.2