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

На втором шаге  в левую верхнюю клетку (1, 2) «незапрещенной»  части таблицы а)  запишем    выделим 1-ую  строку и запишем новое значение невязки 2-го столбца  - получается таблица   б). Таблицы, соответствующие 3-ему и 4-ому шагу, опущены, результат 5-го шага представлен на рис. 3в); стоимости    в «текущих» таблицах  а), б)  и в) опущены, т.к. в методе СЗУ они не  используются. На последнем, 6-ом шаге запишем в клетку (3, 4) число   и удалим все «вспомогательные» записи – символы  и текущие значения невязок. Окончательный результат метода СЗУ – опорная таблица на рис. 3г), соответствующее ей значение целевой функции   

Заполнение  таблицы методом МС можно начинать с клеток (1, 2)  или (3, 1), так как  Выберем клетку (1, 2) и запишем в неё число   При этом    и на 1-ом шаге допустим любой из  двух  вариантов выделения ряда:  выделить 2-ой столбец и заменить     на    или выделить  1-ю строку и заменить    на   Выбрав первый из этих вариантов, получим таблицу  а)  на  рис. 4.

В «незапрещенной» части таблицы а)      Запишем в клетку  (3, 1)   выделим 1-ый столбец и заменим     на  (опять один из двух допустимых вариантов);  после 2-го шага получим таблицу б).  В «незапрещенной» части таблицы б)   после 3-го шага получим таблицу в), в которой не выделен только один столбец (4-ый). Очевидно, что на следующих шагах в клетки этого столбца надо просто «перенести»  текущие невязки всех невыделенных строк, в данном случае числа 0, 10  и 0. Результат применения метода МС представлен на рис. 4г),  соответствующее значение целевой функции   Отметим, что обычно (но не всегда!) начальный план метода МС ближе к оптимальному, чем начальный план метода СЗУ. Именно так получилось в данном примере,

Потенциалы, псевдостоимости,  признак оптимальности.  Набор  чисел    соответствующих строкам и столбцам опорной таблицы ТЗ, называется системой  потенциалов этой таблицы, если выполнены следующие условия:

  для любой занятой клетки  .                      (8)

Условия (8)  представляют собой систему     уравнений (по числу занятых клеток) с   неизвестными. Значения потенциалов можно определить, придавая одному из них произвольное значение (обычно полагают )  и  затем  решая  систему       уравнений (8) относительно    остальных потенциалов. На самом деле систему (8), имеющую очень простую структуру, совсем не обязательно выписывать в явном виде - потенциалы можно вычислить последовательно непосредственно по таблице ТЗ, см. пример 3 ниже.