Читать онлайн «Избранные труды»

Л. Г. ХАЧИЯН ИЗБРАННЫЕ ТРУДЫ Москва МЦНМО 2009  УДК 510. 52+519. 85 Первый тираж издания осуществлен ББК 22. 18 при финансовой поддержке РФФИ Х29 по проекту № 08-07-07013 Хачиян Л. Г. Х29 Избранные труды / Л. Г. Хачиян; [сост. С. П. Тарасов]. — М. : МЦНМО, 2009. — 520 c. ISBN 978-5-94057-509-2 В сборник избранных трудов Л. Г. Хачияна (1952–2005) вошли наибо- лее значительные работы по сложности задач линейного и математического программирования, а также по теории дуализации и генерации. Подробно, в нескольких авторских вариантах, изложен открытый Л. Г. Хачияном полино- миальный алгоритм решения задачи линейного программирования — фунда- ментальный вклад Л. Г. Хачияна в математическое программирование. Книга будет полезна специалистам в области математического програм- мирования и теории сложности, аспирантам и студентам. УДК 510. 52+519. 85 ББК 22. 18 Леонид Генрихович Хачиян Избранные труды Ответственный редактор: С. П. Тарасов Корректор: Л. Ю. Иванова Оригинал-макет подготовлен С. П. Тарасовым и М. П. Юрьевым Подписано в печать 16. 06. 2009 г. Формат 60 × 90 1/ 16. Бумага офсетная. Печать офсетная. Печ. л. 32,5. Тираж 400 экз. Заказ № Издательство Московского центра непрерывного математического образования 119002, Москва, Большой Власьевский пер. , 11. Тел. (499) 241-74-83. Отпечатано с готовых диапозитивов в ППП «Типография „Наука“». 119099, Москва, Шубинский пер. , 6. Книги издательства МЦНМО можно приобрести в магазине «Математическая книга», Большой Власьевский пер. , д. 11 Тел. (499) 241-72-85. Г. , наследники, 2009 c Тарасов С. П. , составление, 2009 ISBN 978-5-94057-509-2 c МЦНМО, оформление, 2009  Содержание От составителя . . . . . . . . . . . . . . . . . . . . . . . 5 А. С. Немировский. Вместо предисловия . . . . . . . . . . . 12 Биографическая справка . . . . . . . . . . . . . . . . . . 24 Раздел I. АЛГОРИТМЫ ДЛЯ МАТРИЧНЫХ ИГР . . . . . . 25 О скорости сходимости игровых процессов решения матрич- ных игр . . . . . . . . . . . . . . . . . . . . . . . . 26 Сублинейный приближенный вероятностный алгоритм для матричных игр (совм. с М. Григориадисом) . . . . . . . . . 38 Раздел II. СЛОЖНОСТЬ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ 49 Сложность выпуклых задач вещественного и целочисленного полиномиального программирования . . . . . . . . . . . 50 Полиномиальный алгоритм в линейном программировании 202 Авторское доказательство полиномиальности линейного про- граммирования . . . . . . . . . . . . . . . . . . . . . 207 Полиномиальные алгоритмы в линейном программировании 224 О точном решении систем линейных неравенств и задач ли- нейного программирования . . . . . . . . . . . . . . . 244 Полиномиальная разрешимость выпуклого квадратичного программирования (совм.