Пример

В задаче, у которой все C[j] > 0, при движении по векторной решетке с помощью шагов вперед целевая функция возрастает, т.е. ее значение с точки зрения направления оптимизации ухудшается. На этой основе может быть сформулировано следующее правило, ограничивающее движение по векторной решетке: как только при перемещении по векторной решетке достигается допустимая точка, дальнейшее движение с помощью шагов вперед прекращается; необходимо сделать шаг назад.

Из этого правила следует, что алгоритм в основном работает с недопустимыми решениями. В частности, если допустимой оказывается нулевая точка, то она является наилучшим допустимым и, следовательно, оптимальным решением всей задачи.

Метод направленного перебора заключается в переборе вершин векторной решетки по маршрутам шагами вперед и назад. Шаг- переход на соседний уровень.

Чтобы исключить повторное попадание в вершины введем правило. Шаг вперед из вершины х возможен только по переменным с индексами

Дата добавления: 2014-01-07