Симплекс-алгоритм, сложность которого не является полиномиальной, использует несколько простых свойств, выполняющихся для линейных задач:
1. Неравенства a1x1+a2x2+...+anxn<=b определяют ограниченные гиперплоскостями замкнутые выпуклые подпространства на R.
2. На пересечении некоторого конечного числа выпуклых подпространств образуется выпуклое тело, которое мы будем называть полиэдром, если оно ограничено, и политопом — в противном случае.
3. Любая точка некоторого полиэдра может быть описана как линейная комбинация вершин, или точек-экстремумов, которые являются пересечениями исходных гиперплоскостей. Число этих точек конечно и не превышает в (если мы имеем m гиперплоскостей (неравенств)).
4. Оптимум не может быть достигнут в точке, расположенной строго внутри политопа, потому что тогда мы могли бы с помощью линейной комбинации построить на границе полиэдра точку, в которой функция дохода Z принимала бы более высокое значение. Если задача не вырождена, т. е. если ранг (детерминант) матрицы A не равен m, то значение Z может быть улучшено за счет продвижения по гиперребру до следующей вершины.
5. Мы будем называть базовой квадратной матрицей матрицы А любое подмножество индексов из множества [1,m], которому соответствует базовая квадратная матрица В, выделенная из A и имеющая ранг п. Сказанное выше эквивалентно утверждению: «Оптимум системы линейных неравенств Ax<=b может быть достигнут при решении уравнения с базовой квадратной матрицей матрицы А». Если матрица А разбивается на матрицы В и N и система записывается в виде ВхB+NxN=b, то базовое решение определяется единственным способом: xN=0 и ВхB=b.
Симплекс-алгоритм работает только с базовыми квадратными матрицами, имеющими решение (т. е. с такими, в которых хB>=0), и переходит от одной вершины к другой, используя метод градиента. На каждом этапе из базовой квадратной матрицы удаляется один индекс: одна из переменных обращается в нуль, а другая попадает в базовую квадратную матрицу, т. е. произвольная переменная принимает ненулевое значение. Сходимость обеспечивается конечностью числа вершин политопа.
Всякой ситуации S, полученной из исходной ситуации в ре¬зультате определенной последовательности действий, придается численная оценка
f(S) = g(S) + h(S),
где g(S) — реальная текущая стоимость ситуации S, h(S) — эвристическая функция, которая оценивает стоимость наилучшей последовательности действий, начинающейся с 5 и заканчивающейся решением. Следовательно, f(S) является мерой стоимости решений, «подчиненных» ситуации S, т. е. решений, включающих то же подмножество исходных действий, что и S. Таким образом алгоритм А* приводит к цели за конечное число шагов, если существует конечная последовательность действий, которая ведет от исходной ситуации к решению. Сам алгоритм представлен ниже.
Алгоритм А*, как и другие градиентные алгоритмы, рассмотренное: выданной главе, является строго численным, поэтому исключается формальный анализ каждой ситуации. Алгоритм основан на оценке стоимости некоторого решения. Но существует большое число задач, для которых эта оценка не имеет смысла, потому что, например, в них необходимо найти единственное осуществимое решение. Он не дает способа подсчета интеграла, решения системы уравнений и т.п. Нельзя заранее обнаружить тупики и петли. Поэтому очень часто данный алгоритм становится не продуктивным. В связи с этим А* используется, как правило, в малоизвестных пространствах.
