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

В основу настоящей книги положены лекции, читавшиеся в течение ряда лет студентам математико-механического факультета Уральского государственного университета им. А. М. Горького.

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

Линейное программирование тесно связано, в частности в методологическом плане, с теорией линейных неравенств. Так, например, один из основных инструментов линейного программирования, а именно, принцип двойственности, выливается в совокупность более или менее очевидных следствий теоремы о зависимых неравенствах. Подход же к двойственности в выпуклом программировании естественным образом реализуется на основе принципа линеаризации.

Методологической направленности изложения материала, ставящего во главу угла системы линейных неравенств, мы обязаны С. Н. Черникову [С. Н. Черников, Линейные неравенства, М., Наука, 1968]. У него же нами взяты схемы доказательств ряда теорем, относящихся к линейным неравенствам.

Уровень трудности чтения глав I, II (линейное программирование) и III—V (выпуклое программирование) различен. Материал первых двух глав может служить естественным продолжением университетского курса линейной алгебры. Что касается глав III—V, то они могли бы лечь в основу специального курса.

Все сведения по линейной алгебре, необходимые при чтении данной книги, можно найти в книге А. И. Мальцева [А. И. Мальцев, Основы линейной алгебры, М., Наука, 1970].

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

Авторы без оговорок используют теоретико-множественные приёмы (в частности, теорему Цермело о возможности полного упорядочения произвольного множества).

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

ПРЕДИСЛОВИЕ

Предисловие	5

Г л а в а I. Конечные системы линейных неравенств	7

§ 1. Основные понятия	7
§ 2. Теорема о существовании k-граней	9
§ 3 Параметрическое представление множества решений конечной
системы линейных неравенств	14
§ 4. Теорема Минковского-Фаркаша о зависимых неравенствах	18
§ 5. Теорема о достижимости для неравенств — следствий 2-го рода	23
§ 6. Условия совместности конечной системы линейных неравенств	27
§ 7. Исключение неизвестных из системы линейных неравенств	29
Упражнения	31

Г л а в а II. Линейное программирование	34

§ 8. Постановка задачи линейного программирования и некоторые её
свойства	34
§ 9. Экономическая интерпретация задачи линейного программирования;
содержательный подход к двойственности	36
§ 10. Двойственность в линейном программировании	39
§ 11. Условия оптимальности	13
§ 12. Содержательная интерпретация условий оптимальности	15
§ 13. Матричные игры и двойственность	47
Упражнения	51

Г л а в а III. Бесконечные системы линейных неравенств и
некоторые приложения	54

§ 14. Финитно определённые системы линейных неравенств	54
§ 15. Двойственность для задач линейного программирования с финитно
определёнными системами линейных ограничений	64
§ 16. Применение двойственности к задаче на минимакс	67
§ 17. Условия совместности бесконечной системы выпуклых неравенств	77
Упражнения	79

Г л а в а IV. Выпуклое программирование	82

§ 18. Выпуклые функции и некоторые их свойства	82
§ 19. Задача выпуклого программирования, промежуточные результаты	91
§ 20. Обобщённая двойственность для задач выпуклого
программирования	99
§ 21. Теорема Куна-Таккера	105
§ 22. Условия оптимальности	108
§ 23. Принцип линеаризации и схема формирования двойственных
программ (другой подход)	110
§ 24. Прямая и обратная теоремы двойственности	11З
§ 25. Сведение задач выпуклого программирования к задачам на
безусловный экстремум	119
Упражнения	125

Г л а в а V. Анализ параметрических задач выпуклого
программирования	128

§ 26. Вопросы корректности задач ВП	128
§ 27. Локально опорные функционалы к функции оптимума	142
§ 28. О маргинальных значениях задачи выпуклого программирования	148
Упражнения	155

П р и л о ж е н и е. Теорема об отделимости	158
Послесловие	162
Указания к решению задач	170
Обозначения	187
Литература	188
Предметный указатель	190

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

Компьютер и задачи выбора, Журавлёв Ю. И., сост., 1989
Геометрическое программирование, Даффин Р., Питерсон Э., Зенер К., 1972
Оптимальные решения, Ланге О., 1967
Оптимальные решения в экономике, Канторович Л. В., Горстко А. Б., 1972
Элементы линейной алгебры и линейного программирования, Карпелевич Ф. И., Садовский Л. Е., 1963
Методы оптимизации. Применение математических методов в экономике. Пособие для учителей, Монахов В. М., Беляева Э. С., Краснер Н. Я., 1978
Математическое программирование: Методы решения производственных и транспортных задач, Рейнфельд Н., Фогель У., 1960
Линейное программирование: Пособие для экономистов, Габр Я., 1960
Экономико-математические методы. Вып. III: Экономико-математические модели народного хозяйства, 1966
Алгоритмы решения экстремальных задач, Романовский И. В., 1977
Введение в минимакс, Демьянов В. Ф., Малозёмов В. Н., 1972
Математические методы исследования операций, Саати Т. Л., 1963
Экономико-математические методы и модели: компьютерное моделирование: Учебное пособие, Орлова И. В., Половников В. А., 2007

elapsed time 0.022 sec

/Наука и Техника/Математика

ОГЛАВЛЕНИЕ

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