Вычисление потенциалов

Поставим в соответствие каждому поставщику и каждому потребителю величины и оответственно так, чтобы для всех базисных клеток плана были выполнены условия:

+ = , , (2)

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

Такая система имеет бесконечное множество решений. Требуется найти любое ее решение. Обычно для простоты полагают один из потенциалов равным нулю и затем вычисляют остальные. В транспортной таблице для потенциалов , ,… заводится дополнительные строка, а для потенциалов , ,… – дополнительный столбец, куда записываются найденные значения.

Таблица.

5.2. Проверка оптимальности плана

Для каждой свободной клетки плана вычисляются разности и полученные значения записываются в левых нижних углах соответствующих клеток.

Заметим, что для базисных клеток должно автоматически выполняться соотношение , и этим фактом можно пользоваться для контроля правильности нахождения потенциалов.

План является оптимальным, если все разности окажутся неотрицательными: .

В противном случае план можно улучшить способом перераспределения поставок.

Таким образом, справедлива следующая теорема об опримальности решения транспортной задачи.

Теорема. Для того чтобы некоторое опорное решение было оптимальным необходимо и достаточно, чтобы существовала система из чисел и , которые удовлетворяли бы следующим условиям:

для базисных клеток,

для свободных клеток.

Эти условия называются условиями потенциальности транспортной задачи.

Дата добавления: 2015-06-30; просмотров: 142; Нарушение авторских прав

Мы поможем в написании ваших работ!