В книге излагаются основные разделы теории и численные методы решения задач линейного программирования. Значительное место уделяется качественному исследованию свойств содержательных моделей методами линейного программирования. Основной материал сопровождается упражнениями теоретического характера.

Табл. 19. Илл. 35. Библ. 28 назв.

Данная книга представляет собой учебное пособие по линейному программированию, рассчитанное на студентов и аспирантов высших учебных заведений по специальностям математика, прикладная математика, экономическая кибернетика, а также на инженеров, пользующихся математическим моделированием как средством исследования реальных процессов.

Изучение свойств систем линейных неравенств ведётся, по-видимому, очень давно. Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, следует отнести к 30-м годам нашего столетия. Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман, знаменитый математик и физик, доказавший основную теорему о матричных играх и изучивший экономическую модель, носящую его имя; советский академик, лауреат Нобелевской премии Л. В. Канторович, сформулировавший ряд задач линейного программирования и предложивший метод их решения, незначительно отличающийся от симплекс-метода. Публикации основных его работ помешала война, и книга вышла в свет только в 1959 г.

Первая постановка транспортной задачи предложена в 1930 г. советским учёным А. Н. Толстым. М. К. Гавурин вместе с Л. В. Канторовичем разрабатывал методы решения задач линейного программирования. В годы войны пробудился интерес к задачам линейного программирования в США. Симплекс-метод разработан Дж. Данцигом при дальнейшем участии А. Чарнса, Л. Форда и Д. Фалкерсона. Теорема двойственности доказана Д. Гейлом, Г. У. Куном и А. У. Таккером на основе идей Дж. фон Неймана.

Накопленный опыт применения линейного программирования показывает, что наряду с разработкой эффективных вычислительных приёмов решения линейных задач всё большую роль приобретают качественные методы исследования свойств задач линейного программирования. В связи с этим в книге уделяется несколько большее внимание данному вопросу, чем обычно.

Книга состоит из восьми глав.

Глава I носит вводный характер. В ней обсуждаются некоторые общие вопросы моделирования, рассматриваются примеры содержательных проблем, приводящих к задачам линейного программирования. Поначалу на примерах подробно описывается методика формализации содержательных задач, что позволяет читателю освоиться с переходом к векторно-матричным обозначениям. При обсуждении формализованных моделей обращается внимание не только на их достоинства, но и на ограниченность, что должно предостеречь читателя от абсолютизации математических выводов и рекомендаций.

Глава II посвящена теории выпуклых многогранных множеств. По этому поводу скажем, что хотя изложение двойственности и симплекс-метода при желании можно провести, не опираясь на указанную теорию, всё же, по нашему мнению, глубокое понимание свойств задач линейного программирования невозможно без знания структуры многогранных множеств. Автор приложил максимум усилий, чтобы сделать материал главы доступным. Основные понятия и факты иллюстрируются примерами и рисунками, позволяющими осознать на геометрическом наглядном материале (в основном на плоскости, реже в трёхмерном пространстве) основные идеи. Предварительное обсуждение каждого факта делает его интуитивно очевидным, так что в ряде случаев (их немного) читатель, не привыкший к абстрактным математическим доказательствам, может опустить их без ущерба для понимания существа дела.

В главе III формулируется и доказывается основной результат — теоремы двойственности в линейном программировании.

Глава IV представляет собой раздел, в котором проводится качественный анализ решений некоторых из содержательных моделей и указываются другие сферы применения теории двойственности. Так, здесь доказывается теорема о магистрали в динамической модели Леонтьева с обсуждением содержательного смысла этого важного результата, теорема о замещении в динамической модели межотраслевого баланса. Наряду с классическим примером использования теории двойственности — доказательством теоремы фон Неймана о матричных играх, — приведены факты о свойствах множества решений в играх n лиц, причём использование теории двойственности делает все доказательства здесь особенно простыми. Отметим также доказательство теоремы Фробениуса-Перрона о свойствах неотрицательных матриц. Доказывается дискретный принцип максимума для линейных вадач.

В главе V излагается симллекс-метод численного решения эадач линейного программирования.

Глава VI преследует цель подготовить читателя к применению симплекс-метода для исследования целочисленных задач линейного программирования. Здесь описывается иной способ организации числовой информации — так называемая симплексная таблица в координатной форме. На этой основе излагается метод решения лексикографических задач линейного программирования, что эатем также используется при обосновании алгоритма Гомори решения целочисленных задач.

Глава VII предназначена продемонстрировать, как преобразуется основная вычислительная схема симплекс-метода при решении специфических классов задач. Основным примером служит классическая транспортная вадача. После теоретического рассмотрения несложной теории транспортных сетей показано, как симплексный вычислительный алгоритм в данном случае сводится к выполнению ряда логических операций по поиску циклов в сети. Большой раздел посвящён целочисленным задачам линейного программирования с изложением содержательных моделей (задача о коммивояжёре, задача о ранце и т. п.).

Последняя глава VIII даёт понятие о трудностях, возникающих в связи с возможной некорректностью задачи линейного программирования. Обсуждается вопрос о важности этого момента, ввиду приближённости любой статистической информации к реальной задаче. Приводятся методы регуляризации подобных задач, основанные на идеях А. Н. Тихонова.

Весь материал сопровождается упражнениями.

Автор приносит благодарность всему коллективу кафедры исследования операций Московского государственного университета, принимавшему активное участие в работе над книгой.

ПРЕДИСЛОВИЕ
С. А. Ашманов

Книги на ту же тему

1. Математическое программирование: Методы решения производственных и транспортных задач, Рейнфельд Н., Фогель У., 1960
2. Линейное программирование: Пособие для экономистов, Габр Я., 1960
3. Оптимальные решения, Ланге О., 1967
4. Элементы линейной алгебры и линейного программирования, Карпелевич Ф. И., Садовский Л. Е., 1963
5. Методы оптимизации. Применение математических методов в экономике. Пособие для учителей, Монахов В. М., Беляева Э. С., Краснер Н. Я., 1978
6. Введение в теорию линейного и выпуклого программирования, Еремин И. И., Астафьев Н. Н., 1976
7. Итеративные методы в теории игр и программировании, Беленький В. З., Волконский В. А., Иванков С. А., Поманский А. Б., Шапиро А. Д., 1974
8. Оптимальные решения в экономике, Канторович Л. В., Горстко А. Б., 1972
9. Практические занятия по курсу математического программирования, Капустин В. Ф., 1976
10. Равновесная термодинамика и математическое программирование, Каганович Б. М., Филиппов С. П., 1995
11. Экономико-математические методы. Вып. III: Экономико-математические модели народного хозяйства, 1966
12. Теория игр, Оуэн Г., 1971
13. Теоретико-игровые модели принятия решений в эколого-экономических системах, Горелик В. А., Кононенко А. Ф., 1982
14. О некоторых вопросах современной математики и кибернетики. Сборник статей в помощь учителю математики, Смолянский М. Л., сост., 1965
15. Методы оптимизации, Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М., 1978
16. Современное состояние теории исследования операций, Моисеев Н. Н., ред., 1979
17. Геометрическое программирование, Даффин Р., Питерсон Э., Зенер К., 1972
18. Экономико-математические методы и модели: компьютерное моделирование: Учебное пособие, Орлова И. В., Половников В. А., 2007
19. Прикладное оптимальное проектирование: Механические системы и конструкции, Хог Э. Д., Арора Я. С., 1983
20. Численные методы в экстремальных задачах, Пшеничный Б. Н., Данилин Ю. М., 1975
21. Прикладной функциональный анализ, Балакришнан А. В., 1980
22. Введение в минимакс, Демьянов В. Ф., Малозёмов В. Н., 1972
23. Элементы теории оптимальных систем, Моисеев Н. Н., 1975
24. Параллельные алгоритмы целочисленной оптимизации, Хохлюк В. И., 1987
25. Алгоритмы решения экстремальных задач, Романовский И. В., 1977
26. Разрешимость и устойчивость задач полиномиального программирования, Белоусов Е. Г., Андронов В. Г., 1993
27. Элементы динамического программирования, Вентцель Е. С., 1964
28. Динамические задачи дискретной оптимизации, Рихтер К., 1985
29. Теория максимина и её приложение к задачам распределения вооружения, Данскин Д. М., 1970
30. Анализ сложных систем и элементы теории оптимального управления, Раскин Л. Г., 1976
31. Математические методы исследования операций, Саати Т. Л., 1963
32. Исследование операций в военном деле, Чуев Ю. В., 1970
33. Исследование операций, Динер И. Я., 1969
34. Управление перевозочным процессом с применением электронных цифровых вычислительных машин, Петров А. П., ред., 1963
35. Информационно-планирующая система железнодорожных узлов, Дел Рио Б., Фролов В. Я., 1972