viagra super force

+7(495) 123-XXXX  г. Москва

Выпуски журналов

  • Серия
  • Серия
  • Серия
  • Серия
  • Журнал
  • Журнал
  • Журнал
  • Журнал

А.Л. Андрианов,  (Соискатель, Московский финансово-промышленный университет)

Серия «Естественные и Технические науки» # ЯНВАРЬ  2017

Линейное программирование
Статья изучает эволюцию алгоритмов решения задач линейного программирования (ЗЛП), и их влияния на развития математики. Центральная проблема, связующая исследования, – поиск полиномиального и эффективного метода решения ЗЛП. Анализируется вклад Левина А.Ю. (метод центрированных сечений Левина-Ньюмана), Немировского А.С. (метод описанных эллипсоидов), Хачияна Л.Г. (доказательство полиномиальной разрешимости ЗЛП на основании нового подхода). Показано значение работы Кармаркара Н., автора алгоритма, сходящегося к решению не по границе допустимого множества, а сквозь многогранник. Проанализирован вклад Левина Л.А., изучавшего универсальные задачи, сложность и сводимость комбинаторных проблем.

Ключевые слова: Линейное программирование, оптимизация, метод центрированных сечений Левина-Ньюмана, метод эллипсоидов, полиномиальная разрешимость, Левин, Немировский, Хачиян, Кармаркар.

 

Развитие линейного программирования (ЛП) началось и проходило параллельными курсами в СССР (в работах Л.В. Канторовича) и на Западе (в трудах Дж.Б. Данцига) и имело множество сходных моментов. Оба автора имели близкие взгляды на математику. Одна из известных фраз Данцига, написанная им в предисловии к его знаменитой книге 1963 года – «Линейное программирование, его применение и обобщения» звучит так: «Решающая проверка для теории – её способность решать те задачи, которые породили её». Точно также один из творческих принципов Петербургской–Ленинградской школы можно выразить фразой «…нет ничего практичнее хорошей теории». Леонид Витальевич, будучи её ярким представителем, подчёркивал: «…для моей деятельности характерным является постоянное взаимопроникновение теории и практики». В соответствии с этим, в обоих случаях толчком к развитию ЛП стали конкретные задачи, продиктованных практикой. При исследованиях внимание уделялось именно практической направленности результатов, их внедрению в приложения и развитию реально применимых алгоритмов, что прекрасно иллюстрирует цитата из той же книги Данцига: «Точка зрения этой работы конструктивна. Она отражает начало теории достаточно мощной для того, чтобы справиться с некоторыми из сложных задач по принятию решений, для которых она была создана» [1-4].

Само рассмотрение задачи с ограничениями типа неравенств уже стало новаторским (Лагранж, разработав правило множителей Лагранжа, изучал исключительно задачи с равенствами, причём только гладкие). Для общего случая выпуклой экстремальной задачи с неравенствами необходимое условие получил В. Каруш (William Karush), 1939 год, защитивший диссертацию в Чикаго. Однако, диссертация не была опубликована и осталась неизвестной. Позже необходимые условия получили Х.У. Кун (H. W. Kuhn) и А.У. Таккер (A. W. Tucker).

Помимо создания метода разрешающих множителей и симплекс метода (СМ), одним из важнейших достижений Канторовича и Данцига стало открытие ими огромного количества экономических задач, которые описываются ЛП, и осознание экономической интерпретации двойственной задачи (множители Лагранжа прямой задачи являются оптимальным решением для двойственной и наоборот). Также выяснилось: эта же математическая модель, кроме экономической, описывает также задачу управления. Большое практическое значение данных задач способствовало тому, что центральной проблемой стало изучение не только теоретического, но и практического решения данных вопросов и, в первую очередь, ‒ развитие и исследование соответствующих алгоритмов. Данная статья касается преимущественно именно алгоритмов, разработанных для решения задач ЛП (ЗЛП), а также их влияния на развития математики в целом.

1. Левин Анатолий Юрьевич (1936–2007).

Один из замечательных результатов был получен А.Ю. Левиным, придумавшим в 1965 году метод центрированных сечений [5], который применим для поиска минимума не только линейной, но и произвольной выпуклой функции. Основной механизм работы его алгоритма таков ([6, с.78–79]).

Читать полный текст статьи …


СПИСОК ЛИТЕРАТУРЫ:
1. Андрианов А.Л. Развитие линейного программирования в ранних работах Л.В. Канторовича // Историко-математические исследования. Вторая серия. Выпуск 13 (48). – М.: «Янус-К», 2009. – С. 323–339.
2. Андрианов А.Л. Л.В. Канторович как создатель линейного программирования // Вопросы истории естествознания и техники. – 2009. – №4. – С. 77–89.
3. Andrianov A. (2011) The full Monge problem solution based on the linear programming (LP). Proceedings of the 8th Congress of the International Society for Analysis, its Applications, and Computation, pp.94-101
4. Андрианов А.Л. Дж.Б. Данциг и линейное программирование // Казанская наука. №8. 2014. – Казань: Изд-во Казанский Издательский Дом, 2014. С. 19-23.
5. Левин А.Ю. Об одном алгоритме минимизации выпуклой функции // ДАН СССР, 160. №6, 1965. С. 1241-1243.
6. Магарил-Иляев Г.Г., Тихомиров В.М. Выпуклый анализ и его приложения. Издание второе. УРСС, Москва, 2003.
7. Yamnitsky B., Levin L. (1982) An old linear programming problem runs in polynomial time. 23rd Annual Symposium of Foundations of Computer Science.pp.327–328.
8. Юдин Д. Б., Немировский А. С. Оценка информационной сложности задач математического программирования / Экономика и математические методы, т. XII, вып.. 1, стр. 118-142, 1976.
9. Немировский А. С., Юдин Д. Б. Методы оптимизации, адаптивные к «существенной» размерности задачи, Автомат. и телемех., 1977, выпуск 4, 75–87. 10. Khachiyan L. (1979) [A polynomial algorithm in linear programming]. Soviet Mathematics Doklady, 224 (5) pp. 1093–1096.
11. Todd M. (2005) Leonid Khachiyan, 1952–2005: An Appreciation. In "Tributes to George Dantzig and Leonid Khachiyan" // SIAG/OPT Views-and-News, vol.16, nn 1-2, October 2005, pp. 4–6.
12. Karmarkar N. (1984) A new polynomial-time algorithm for linear programming, Combinatorica 4, pp. 373–395.
13. https://en.wikipedia.org/wiki/Interior_point_method
14. https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm
15. Левин Л.А. Универсальные задачи перебора // Проблемы передачи информации. – 1973. – Т. 9, № 3. – С. 115–116. Levin L. Universal search problems // Problems of Information Transmission, 1973, 9(3), 115-116.
16. Cook S. (1971) The Complexity of Theorem Proving Procedures. Proceedings Third Annual ACM Symposium on Thoery of Computing, May 1971, pp 151–158.
17. Karp R. (1972) Reducibility among Combinatorial Problems. In Raymond E. Miller and James W. Thatcher (editors). Complexity of Computer Computations, pp. 85–103.
 



© 
А.Л. Андрианов, Журнал "Современная наука: актуальные проблемы теории и практики".
 

 

 

 
SCROLL TO TOP

 Rambler's Top100 @Mail.ru