Переход от одного допустимого к другому

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

Теорема. Если допустимое решение невырожденное, то для каждой свободной клетки существует единственный цикл.

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

Новое допустимое решение получают по правилу: Около свободной клетки ставится знак (+), затем поочередно расставляют знаки (–) и (+). У вершин (клеток) со знаком (–) выбирают самую минимальную поставку товара. Эту минимальную поставку товара прибавляют к поставкам товара, находящимся в вершинах со знаком (+) и отнимают у вершин со знаком (–). Остальные занятые вершины, не входящие в этот цикл оставляют без изменения. Можно показать, что полученное решение будет допустимым. Полученное решение проверяют на оптимальность.

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

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