Полиномиальность лин. программирования (метод эллипсоидов)

[Muxaj1bi4]

Добрый день!
Помогите пожалуйста, я никак не могу разобраться. Существует метод эллипсоидов, его можно использовать для нахождения допустимой точки для систем линейных неравенств. Непонятно: 1.Как узнать что допустимой точки нет? 2. Как решение задачи о нахождении допустимой точки системы линейных неравенств позволяет решать задачу линейного программирования?

[Brukvalub]

Цитирую: Если в задаче линейного программирования удалось построить шар, содержащий искомое решение, то она может быть решена методом эллипсоидов. Для этого в начале находим какую-нибудь точку u внутри шара, удовлетворяющую ограничениям задачи. Проводим через нее гиперплоскость f(x) < f(u), где f — целевая функция, и находим точку в пересечении исходных и новой гиперплоскостей (начиная с текущего эллипсоида). С новой найденной точкой проделываем то же самое. Процесс сходится к оптимальному решению с экспоненциальной скоростью (поскольку с этой скоростью убывает объем эллипсоида). (см. http://ru.wikipedia.org/wiki/%D0%9C%D0% ... 0%BE%D0%B2 ) Вывод: метод эллипсоидов решает именно задачу линейного программирования, а не задачу "о нахождении допустимой точки системы линейных неравенств".

[Vassil]

Если в Google поискать по ключевым словам

testing feasibility in linear programming

между прочим выходить ссылка на статью
"My Memories of Leonid Khachiyan and a Personal Tribute for His Contributions in Linear Programming" написанная Bahman Kalantari :

http://www.cs.rutgers.edu/~kalantar/khachiyan2005.pdf

В литературе этой статьи есть ссылка на статью
"Notes on the Khachiyan-Kalantari algorithm" by Vasek Chvatal:

http://www.cs.rutgers.edu/~chvatal/521/khakal.pdf

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

А если вообще интересует как практически лучше находить опорное стартовое решение, то быть может полезна эта статья и литература к ней:
"Improving the Efficiency of the Simplex Algorithm Based on a Geometric Explanation of Phase 1" by Daniel Solow and Hans Halim по линку:

http://wsomfaculty.cwru.edu/solow/lp.pdf

Возможно есть другие более подходящие источники.

[Muxaj1bi4]

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

[Brukvalub]

Посмотрите здесь: http://enci.ru/%D0%9C%D0%B5%D1%82%D0%BE ... 0%BE%D0%B2

[Vassil]

Быть может уже вопрос выяснили.
А вопрос был: Как решение задачи о нахождении допустимой точки системы линейных неравенств позволяет решать задачу линейного программирования за полиномиальное время?
Конечно, иногда можно многими разными путями дойти до решения.
И еще, можно по разному объяснить один и тот метод.

Поискав в Google по ключевым словам ellipsoid algorithm linear programming
наряду с другими вещами вышла эта ссылка:

http://www.cs.princeton.edu/courses/arc ... ipsoid.pdf

The Ellipsoid Algorithm for Linear Programming. Lecturer: Sanjeev Arora, COS 521, Fall 2005. Princeton University. Scribe Notes: Siddhartha Brahma

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