2014 dxdy logo

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

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




 
 Симплексы вместо эллипсоидов
Сообщение22.10.2006, 22:37 
Добрый вечер!
Я изучаю полиномиальные алгоритмы для решения задач линейного программирования.
Существует алгоритм аналогичный методу эллипсодов, но вместо эллипсоидов используютя симплексы. Вроде бы этим подходом занимался Дикин И.И. Не могу найти ни его работ на эту тему, ни описаний этого метода. Если кому-то этот метод знаком опубликуйте или подскажите, где читать.
Спасибо. С уважением, Михаил.

 
 
 
 Гипотеза?
Сообщение23.10.2006, 08:56 
Не знаю ответ на Ваш вопрос.
Но, поиском в Google по Дикин И привел (как обычно бывает, в перемешку с однофамильными политиками и подозреваемыми в преступлении) примерно к такому линку

http://www.botik.ru/PSI/lib/new05/new9.html

где можно найти ссылку

12
ДИКИН И.И.
Решение задач линейного программирования методом внутренних точек. - Иркутск: Ин-т систем энергетики, 2005. - 35 с. - (Препринт ИСЭМ СО РАН, 2005, № 2).

Близко, мне кажется, к этой проблематики явно можно найти следующие интересные публикации на английском:

http://www.cs.cmu.edu/~guyb/realworld.html

и там посмотреть Lecture Notes (Fall 97) по линку

http://www.cs.cmu.edu/afs/cs/project/ps ... orld.ps.gz

, и в частности раздели LP1 и LP2.

По этой же теме, думаю можно в Интернете поиском в Google по Wang, O'Leary interior point methods in linear programming получить свободно краткую статью об адаптивном использовании итеративных методов внутренной точки --- pdf.

Надеюсь на снисхождение, если не отвечаю прямо в спрашиваемое.

 
 
 
 Спасибо за ссылки!
Сообщение23.10.2006, 17:24 
Спасибо за ссылки, но ничего принципиально нового я там не нашел. Дело в том, что я занимаюсь дискретной оптимизацией, и конечной целью является даже не метод как таковой, а то, что при использовании симплексов возникают некие комбинаторные свойства (узнать бы какие).

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


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