РОССИЙСКАЯ АКАДЕМИЯ НАУК
УРАЛЬСКОЕ ОТДЕЛЕНИЕ
ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

И.И.ЕРЕМИН





ДВОЙСТВЕННОСТЬ

В ЛИНЕЙНОЙ ОПТИМИЗАЦИИ

ЕКАТЕРИНБУРГ, 2001

Издание осуществлено при поддержке
Компании ``Ювелирный Дом'', г. Екатеринбург

УДК 519.6

Е р е м и н И.И. Двойственность в линейной
оптимизации. Екатеринбург: УрО РАН, 2001.
ISBN 5-7691-1131-3.

Книга посвящена вопросам теории двойственности для линейных залач оптимизации, а именно: двойственность для стандартных задач линейного программирования, несобственных, лексикографических, парето-лексикографических и дизъюнктивных. Двойственность является базовой идеей теории математического, в частности -- линейного, программирования, позволяющей на ее основе осуществлять конструктивный анализ моделей оптимизации.

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

Ответственный редактор --
доктор физико-математических наук Л.Д.Попов

ISBN 5-7691-1131-3

E $\,\frac{\mbox{ПРП-2000--21(01)Д}} {\mbox{8П6(03)1998}}$ПВ-2001 $\copyright$ Еремин И.И., 2001

ПРЕДИСЛОВИЕ

Предлагаемая книга является по существу авторским сборником работ, опубликованных в последние годы и связанных между собой единой темой, а именно темой двойственности в математическом программировании (МП), преимущественно для задач в линейной постановке. Последнее обстоятельство объясняется просто: автор исследовал не общие вопросы двойственности, каковые хорошо изучены и для общих задач МП, а вопросы со спецификой либо в постановке самой задачи, либо спецификой требований к двойственности. В смысле сказанного изучались классы несобственных, лексикографических, парето-лексикографических и дизъюнктивных задач линейной оптимизации. Сформулированные требования к двойственности, т.е. к схемам формирования двойственной задачи, соблюдения для последней характеристических свойств исходной задачи, обеспечение свойств взаимной сопряженности и содержательных формулировок теорем двойственности, определили свои трудности уже в классе линейных задач. Сказанное и объясняет преимущественность выбора класса задач в линейной постановке, хотя выход за линейность также имеет место (в разделах I, IV, V).

Раздел 1 выполняет скорее всего функцию введения, в рамках которого конспективно излагается совокупность вопросов, касающихся двойственности как для общих задач МП, так и для задач в линейной постановке. В конце этого раздела помещена литература [1-67], содержащая в основном [11-67] работы автора по двойственности (автор не ставил перед собой цель дать полную библиографию по проблеме двойственности в математическом программировании). В четырех последующих разделах приведены результаты по симметричной двойственности для лексикографических и парето-лексикографических задач линейной и квадратичной оптимизации, при этом рассмотрены случаи как собственных (разрешимых), так и несобственных задач [47, 55, 58, 65]. Автор не стал включать раздел по развернутому изложению теории двойственности для несобственных задач стандартного линейного программирования, этот материал подробно изложен в монографии [23]. Содержанием раздела VI является глава VII книги [67] (с измененным названием). В этой главе изучаются дизъюнктивные задачи кусочно-линейного программирования с изложением вопросов двойственности.

Во введении из книги автора ``Теория линейной оптимизации'' [67] был дан краткий исторический материал по формированию двойственности в линейном и нелинейном программировании. В нем подчеркивается фундаментальная роль в этом Дж.фонНеймана, О.Моргенштерна (Теория игр и экономическое поведение. М.: Наука, 1970, 708 с. (русский перевод)), Дж.Данцига (Линейное программирование, его применение и обобщение. М.: Прогресс, 1966, 600 с. (русский перевод)) и В.Л.Канторовича (Математические методы организации и планирования производства. Л.: ЛГУ, 1939, 68 с.). Замечательный материал по истории возникновения линейного программирования (в частности, и двойственности) имеется в очерке Дж.Данцига ``Воспоминания о возникновении линейного программирования'' (Memoirs the American. Math. Society, 1984, v. 48,  298).

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

Автор выражает глубокую благодарность Галине
Федоровне Корниловой, взявшей на себя труд компьютерного набора текста книги.