Полиномиальная сложность задач линейного программирования.

В классической работе Л. Г. Хачияна[4] предложен полиномиальный алгоритм для задачи линейного программирования с целыми коэффициентами, т.е. показано, что задачу линейного программирования можно решить на детерминированной машине Тьюринга за полиномиальное от длины входа L время.

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

Первый полиномиальный алгоритм, метод эллипсоидов, был предложен в 1979 г. советским математиком Л. Хачияном, разрешившим таким образом проблему, долгое время остававшуюся нерешенной. Метод эллипсоидов имеет совершенно другую, некомбинаторную, природу, нежели симплекс-метод. Л.Г.Хачиян доказал, что при помощи метода эллипсоидов можно решить любую задачу линейного программирования за полиномиальное время.

Идея метода эллипсоидов:

1. построить эллипсоид, который точно содержит всю область допустимых решений;

2. если положение центра эллипсоида не удовлетворяет некоторому ограничению задачи, эллипсоид сужается и центр его переносится.

В итоге будет найдено допустимое решение (если оно существует).

Хачиян доказал, что

1. объемы эллипсоидов убывают экспоненциально;

2. существует величина V, которая является критерием того, разрешима ли задача (если объем эллипсоида меньше V, то задача неразрешима).

Однако в вычислительном плане этот метод оказался неперспективным, так как работал медленнее симплекс-метода. Тем не менее сам факт полиномиальной сложности задач ЛП привел к созданию целого класса эффективных алгоритмов ЛП ‑ методов внутренней точки, первым из которых был алгоритм Н. Кармаркара[5], предложенный в 1984 г. Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод Кармаркара требует итераций для нахождения допустимой точки прямой задачи ЛП x, такой, чтозначение целевой функции отличается не более чем на от оптимального значения.