[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4]

Оценка цикла.

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

При вычислении ΔF многие слагаемые из Fп и Fн взаимно уничтожаются, не влияя на значение ΔF: существенны лишь коэффициенты затрат тех клеток, в которых поставка при рассматриваемом перераспределении изменится. При этом в выражение для ΔF некоторые из них входят со знаком "+", а некоторые - со знаком "-". Для нахождения "правила знаков" удобен чертеж, представленный на рис. 7.1. На нем изображены клетки, в которых будет изменена поставка (слева от каждой клетки написан в скобках ее номер; клетки, соответствующие базисным переменным, перечеркнуты).


Рис. 7.1

При этом знаком "+" помечены те клетки, поставка в которых увеличится. Видно, что именно их коэффициенты затрат войдут в выражение для ΔF со знаком "+". В остальных клетках рис. 7.1 поставка уменьшится (в них вписан знак "-"), их коэффициенты затрат войдут в выражение для ΔF со знаком "-".
Определение
Ломаную, соединяющую клетки с изменяемой поставкой, будем называть означенным циклом пересчета

(см. рис. 7.1).

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

Аналогично, составляя означенный цикл пересчета для каждой свободной клетки, можно найти ее оценку. При этом, конечно, цикл не всегда будет получаться таким простым, как в разобранном примере для клетки (1,3). Например, означенный цикл пересчета для клетки (1,1), показанный на рис. 7.2, более сложный.


Рис. 7.2

Оценка клетки (1,1) в этом случае равна
ΔF = (1+3+2)-(2+1+4)=-1.
Замечание
Иногда для произвольного означенного цикла вводится понятие оценка цикла - алгебраическая сумма коэффициентов, стоящих в вершинах цикла, взятых с соответствующими знаками. Приведенные выше рассуждения показывают, что оценка цикла равна оценке той единственной свободной клетки, которая входит в данный цикл.

Для облегчения нахождения цикла пересчета в конкретных задачах дадим его точное определение.
Определение
Циклом в матрице будем называть ломаную с вершинами в клетках и звеньями, лежащими вдоль строк и столбцов матрицы, удовлетворяющую условиям:
  • ломаная должна быть связной, т.е. из любой ее вершины можно попасть в любую другую вершину по звеньям ломаной;
  • в каждой вершине ломаной встречаются два звена, одно из которых располагается по строке, другое - по столбцу.

Определние
Циклом пересчета называется такой цикл в таблице с базисным распределением поставок, при котором одна из его вершин лежит в свободней клетке, остальные - в заполненных.
Цикл пересчета называется означенным, если в его вершинах расставлены знаки "+" и "-" так, что в свободной клетке стоит знак "+", а соседние вершины имеют противоположные знаки.

Для каждой свободной клетки базисного распределения поставок существует и притом единственный цикл пересчета, причем операция означивания цикла является корректной.
Таким образом, получено правило, позволяющее найти оценку произвольной свободной клетки. Однако нахождение оценок свободных клеток можно существенно упростить. Рассмотрим следующую воображаемую ситуацию. Пусть коэффициенты затрат всех заполненных клеток равны нулю. Если теперь по рассмотренному правилу найти оценку свободных клеток, то окажется, что оценки свободных клеток равны их коэффициентам затрат, т.е. в этом случае значения оценок считываются с таблицы поставок и никаких циклов строить не надо.
С другой стороны, справедлива следующая теорема.

Теорема 7.3.(о потенциалах).
Оценка свободной клетки не изменится, если к коэффициентам затрат некоторой строки (столбца) таблицы поставок прибавить некоторое число.

Определение
Это число, прибавляемое к коэффициентам затрат выделенной строки (столбца), будем называть потенциалом данной строки (столбца).

Пусть для фиксированной свободной клетки построен цикл. Для каждого звена этого цикла, входящего в произвольную выделенную строку, имеем пару соседних вершин цикла. По определению означенного цикла пересчета одна из этих двух вершин имеет знак "+", другая - знак "-". Тогда вклад от этих двух вершин в значение искомой оценки определяется разностью коэффициентов затрат этих вершин. Очевидно, что если к каждому из этих коэффициентов затрат прибавить одно и то же число, то само значение разности не изменится.

Рассмотрение воображаемого случая и теорема 7.3 приводят к
правилу 2 нахождения оценок свободных клеток:
к коэффициентам затрат таблицы поставок в каждой строке и столбце надо прибавить такие числа (потенциалы), чтобы коэффициенты затрат в заполненных клетках стали равными нулю. Полученные при этом коэффициенты затрат свободных клеток равны оценкам этих клеток.

Матрица оценок.

Задача 7.6

Найти оценки свободных клеток базисного распределения поставок, найденного в задаче 7.3.

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

Начнем с первого столбца. Пусть потенциал этого столбца равен нулю (табл. 7.11). Рядом с потенциалом в скобках записываем номер шага (поставки опускаем).

После прибавления этого потенциала к коэффициентам затрат первого столбца коэффициент затрат заполненной клетки (2,1) не изменится; чтобы полученный после сложения коэффициент стал равен нулю, потенциал второй строки табл. 7.11 должен быть равен -1; для обнуления коэффициента затрат клетки (2,4) потенциал четвертого столбца должен быть равен -1 и т. д. Измененные коэффициенты затрат удобно выписать в виде отдельной матрицы оценок. (7.13).

        (7.13)

Внимание!
Элементы матрицы оценок, соответствующие свободным клеткам таблицы поставок, равны оценкам этих свободных клеток.

Из предыдущих рассуждений вытекает, что для фиксированного базисного распределения поставок можно подобрать различные наборы потенциалов, удовлетворяющих правилу 2, однако матрица оценок во всех таких случаях будет одинаковой.

[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4] [В начало страницы]