2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Ссылки, которые, может помогут
Сообщение16.05.2007, 16:06 
Если в 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

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

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

 
 
 
 
Сообщение17.05.2007, 22:58 
Аватара пользователя
Посмотрите здесь: http://enci.ru/%D0%9C%D0%B5%D1%82%D0%BE ... 0%BE%D0%B2

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

Поискав в 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

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

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group