Везде
СТАНОВЛЕНИЕ И НАЧАЛЬНЫЕ ЭТАПЫ РАЗВИТИЯ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Оглавление
Аннотация Оценить Содержание публикации
Библиография Комментарии
Поделиться
QR
Метрика
СТАНОВЛЕНИЕ И НАЧАЛЬНЫЕ ЭТАПЫ РАЗВИТИЯ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Аннотация
Код статьи
S0205-96060000513-1-1
Тип публикации
Статья
Статус публикации
Опубликовано
Авторы
Андрианов Александр Львович 
Выпуск
Том 38 №2
Страницы
351-361
Аннотация
В статье рассмотрены становление и начальные этапы развития алгоритмов решения задач линейного программирования (ЗЛП) и их влияние на развитие математики. Центральная проблема, связующая исследования, - поиск полиномиального и эффективного метода решения ЗЛП. Анализируется вклад А.Ю. Левина (метод центрированных сечений Левина - Ньюмана), А.С. Немировского (метод описанных эллипсоидов), Л.Г. Хачияна (доказательство полиномиальной разрешимости ЗЛП на основании нового подхода). Показано значение работы Н. Кармаркара, создавшего алгоритм, сходящийся к решению не по границе допустимого множества, а сквозь многогранник. Проанализирован вклад Л.А. Левина, изучавшего универсальные задачи, сложность и сводимость комбинаторных проблем.
Ключевые слова
линейное программирование, оптимизация, метод центрированных сечений Левина – Ньюмана, метод эллипсоидов, полиномиальная разрешимость, А.Ю. Левин, А. С. Немировский, Л. Г. Хачиян, Н.К. Кармаркар
Классификатор
Дата публикации
01.04.2017
Всего подписок
4
Всего просмотров
1116
Оценка читателей
0.0 (0 голосов)
Цитировать   Скачать pdf

Библиография



Дополнительные библиографические источники и материалы

1. Andrianov, A. (2011) The Full Monge Problem Solution Base on the Linear Programming (LP), in Proceedings of the 8th Congress of the International Society for Analysis, its Applications, and Computation. Moscow: PFUR Press. pp. 220. 
2. Andrianov, A. L. (2009) Kantorovich kak sozdatel' lineinogo programmirovaniia [Kantorovitch as the Founder of Linear Programming], Voprosy istorii estestvoznaniia i tekhniki, no. 4, pp. 77-89. 
3. Andrianov, A. L. (2009) Razvitie lineinogo programmirovaniia v rannich rabotach L. V. Kantorovicha [Development of Linear Programming in the Early Works of L. V. Kantorovitch], Istoriko-matematicheskie issledovaniia, vtoraia seriia, no. 13 (48), pp. 323-339. 
4. Andrianov, A. L. (2011) Razvitie lineinogo programmirovaniia v rabotach L. V. Kantorovicha 1930-50-kh godov [Development of Linear Programming in Works of L. V. Kantorovitch in the 1930s - 1950s], Istoriko-matematicheskie issledovaniia, vtoraia seriia, no. 14 (49), pp. 25-40. 
5. Andrianov, A. L. (2014) Dzh. B. Dantsig i lineinoe programmirovanie [G. В. Dantzig and Lin­ear Programming], Kazanskaia nauka, no. 8, pp. 19-23. 
6. Cook, S. A. (1971) The Complexity of Theorem Proving Procedures, in Proceedings of the Third Annual ACM Symposium on Theory of Computing, Shaker Heights, Ohio, USA, May 3-5, pp. 151-158. 
7. Dantsig, Dzh. (Dantzig, G. B.) (1966) Lineinoe programmirovanie, ego primenenie i obobshcheniia [Linear Programming and Extensions]. Moskva: Progress. Edmonds, J. (1965) Paths, Trees, and Flowers, Canadian Journal of Mathematics, vol. 17, p. 449-467. 
8. Grotschel, M., Lovasz, L., and Schrijver, A. (1981) The Ellipsoid Method and Its Consequences in Combinatorial Optimization, Combinatorica, vol. 1. pp. 169-197. 
9. Iudin, D. B. and Nemiroskii A. S. (1976) Otsenka informatsionnoi slozhnosti zadach matematicheskogo programmirovaniia [The Estimation of Information Complexity of the Problems of Mathematical Programming], Ekonomika i matematicheskie metody, vol. 12, no. 1, pp. 118-142. 
10. Iudin, D. B. and Nemiroskii, A. S. (1976) Informatsionnaia slozhnost' i effektivnye metody resheniia vypuklykh ekstremal'nykh zadach [Information Complexity and Efficient Meth­ods for Solving Convex Extreme Problems], Ekonomika i matematicheskie metody, vol. 12, no. 2, pp. 357-369. 
11. Kantorovich, L. V. (1987) Moi put' v nauke [My Journey in Science], Uspekhi matemanicheskikh nauk, vol. 42, no. 2 (254), pp. 183-213. 
12. Karmarkar, N. K. (1984) A New Polynomial-Time Algorithm for Linear Programming, Com­binatorica, vol. 4, no. 4. pp. 373-395. 
13. Karp, R. M. (1972) Reducibility Among Combinatorial Problems, in: Miller, R. E., Thatch­er J. W. (eds.) Complexity of Computer Computations. New York: Plenum, pp. 85-103. 
14. Khachiian, L. G. (1979) Polinomial'nyi algoritm v lineinom programmirovanii [Polynomial Algorithm in Linear Programming], Doklady AN SSSR, vol. 244, no. 5, pp. 1093-1096. 
15. Khachiyan, L. G. (1979) A Polynomial Algorithm in Linear Programming, Soviet Mathematics Doklady, vol. 20, no. 1, pp. 191-194. 
16. Klee, V. and Minty, G. J. (1969) How Good Is the Simplex Algorithm? in: Shisha, O. (ed.) Inequalities III (Proceedings of the Third Symposium on Inequalities Held at the University of California, Los Angeles, Calif., September 1-9, Dedicated to the Memory of Theodore S. Motzkin). New York and London: Academic Press, pp. 159-175. 
17. Levin, A. Iu. (1965) Ob odnom algoritme minimizatsii vypukloi funktsii [On a Convex Func­tion Minimization Algorithm], Doklady AN SSSR, vol. 160, no. 6, pp. 1244-1247. 
18. Levin, L. (1973) Universal'nye zadachi perebora [Universal Search Problems], Problemy peredachi informatsii, vol. 9, no. 3, pp. 115-116. 
19. Magaril-Iliaev, G. G. and Tikhomirov, V. M. (2003) Vypuklyi analiz i ego prilozheniia. 2-e izd. [Convex Analysis and Its Applications. 2nd ed.]. Moskva: URSS. 
20. Nemiroskii, A. S. and Iudin, D. B. (1977) Metody optimizatsii, adaptivnye k "sushchestvennoi" razmernosti zadachi [Optimization Methods Adaptable to the "Essential" Problem Dimen­sion], Avtomatika i telemekhanika, no. 4, pp. 75-87. 
21. Todd, M. (2005) Leonid Khachiyan, 1952-2005: An Appreciation, SIAG/OPT Views-and-News, vol. 16, no. 1-2, pp. 4-6. 
22. Yamnitsky, B. and Levin, L. (1982) An Old Linear Programming Algorithm Runs in Polyno­mial Time, in: 23rd Annual Symposium of Foundations of Computer Science, November 3-5, 1982, Chicago, Illinois, USA. New York, pp. 327-328.

Комментарии

Сообщения не найдены

Написать отзыв
Перевести