Проверка решения на оптимальность

Полученное допустимое невырожденное решение проверяют на оптимальность с помощью ряда критериев. Рассмотрим метод потенциалов.

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

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

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

Примем эту теорему без доказательства.

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

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