Российский экономический

Рис. 5.1.
Схема «правида знаков» 
Знаком «+» помечены те клетки, поставка в которых увеличится. Видно, 
что именно их коэффициенты затрат войдут в выражение для 
∆𝐹
со знаком «+». 
В остальных клетках рис. 5.1 поставка уменьшится (в них вписан знак «–»), их 
коэффициенты затрат войдут в выражение для 
∆𝐹
со знаком «–». Ломаную, со-
единяющую клетки с изменяемой поставкой, будем называть означенным цик-
лом пересчета (см. рис. 5.1). 
Таким образом, можно сформулировать правило 1 нахождения оценки 
свободной клетки: для свободной клетки следует построить цикл пересчета, в 
вершинах этого цикла расставить последовательно чередующие знаки, начиная 
со знака «+» в свободной клетке, тогда значение оценки свободной клетки рав-
но алгебраической сумме коэффициентов затрат клеток цикла, взятых с соот-
ветствующими знаками. 
100

---

Рис. 5.2. 
Цикл пересчета перевозки по «правилу знаков»
 
Аналогично, составляя означенный цикл пересчета для каждой свободной 
клетки, можно найти ее оценку. При этом, конечно, цикл не всегда будет получать-
ся таким простым, как в разобранном примере для клетки (1,3). Например, означен-
ный цикл пересчета для клетки (1,1), показанный на рис. 5.2, более сложный. 
Оценка клетки (1,1) в этом случае равна: 
β
11
= (1 + 3 + 2) − (2 + 1 + 4) = −1
. 
Замечание. 
Иногда для произвольного означенного цикла вводится поня-
тие «оценка цикла» — алгебраическая сумма коэффициентов, стоящих в вер-
шинах цикла, взятых с соответствующими знаками. Приведенные выше рас-
суждения показывают, что оценка цикла равна оценке той единственной сво-
бодной клетке, которая входит в данный цикл.
 
Для облегчения нахождения цикла пересчета в конкретных задачах дадим 
его точное определение. Циклом в матрице будем называть ломаную с верши-
нами в клетках и звеньями, лежащими вдоль строк и столбцов матрицы, удо-
влетворяющую условиям: 

ломаная должна быть связной, т.е. из любой ее вершины можно по-
пасть в любую другую вершину по звеньям ломаной; 

в каждой вершине ломаной встречаются два звена, одно из которых 
располагается по строке, другое — по столбцу.