Габасов Р., Кириллова Ф.М. Методы линейного программирования.
Ч.1: Общие задачи. Ч.1. Изд. стереотип.

Оглавление

Предисловие

Модели и методы линейного программирования имеют огромное прикладное значение и поэтому включаются в программы многих учебных заведений. Существует ряд монографий и пособий по линейному программированию, рассчитанных на аудиторию с самыми разными интересами. Появление в этой ситуации еще одной книги не может не вызвать определенных вопросов и поэтому требует соответствующего обоснования. Идея написания книги возникла у авторов после чтения студентам факультета прикладной математики БГУ лекций по избранным главам линейного программирования в дополнение к тем сведениям, которые были известны им из общих курсов. Мы обратили внимание на то, что в основных конечных методах линейного программирования (симплекс-методе и двойственном симплекс-методе) никак не используется дополнительная информация о планах и двойственных планах, которая, как правило, имеется у специалистов, занятых практическими задачами. Наконец, оказалось, что в классических методах отсутствуют критерии субоптимальности для останова процесса решения после достижения заданного приближения по целевой функции к оптимальному плану. Эти обстоятельства заставили нас взяться за разработку методов решения задач линейного программирования, в той или иной мере свободных от указанных недостатков.

В основе новых методов решения лежат понятия опорных планов и копланов. Эти объекты, являясь естественным обобщением классических понятий базисных планов прямой и двойственной задач из теории симплекс-метода, позволяют более гибко подходить к проблеме эффективного решения задач линейного программирования. Изменение основных понятий симплекс-метода вызвало принципиальные изменения и обобщения других методов, так или иначе связанных с ним. Основные результаты этой работы включены в данную книгу. Книга разбита на три части (1. Общие задачи; 2. Транспортные задачи; 3. Специальные задачи), традиционно содержащиеся почти во всех достаточно полных руководствах по линейному программированию.

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

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

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

Материал, как правило, излагается в векторно-матричной форме. Используются традиционные обозначения. Векторы обозначаются строчными латинскими буквами, матрицы – прописными. Греческими буквами чаще всего обозначаются скалярные величины. Каждый вектор, участвующий в операциях, мыслится записанным в виде столбца; для получения вектор-строки используется символ ' (штрих) – транспонирование. Все символы поясняются при их введении.

При подготовке к печати первой части книги нам большую помощь оказали В.П.Кирлица и О.И.Костюкова. А.Я.Каменецкий предоставил в наше распоряжение свои результаты по комбинированному методу (§ 2 гл.V) и методам решения вырожденных задач (§ 2 гл.VI). Пользуясь случаем, выражаем им искреннюю благодарность.

Об авторах

Габасов Рафаил Федорович

Доктор физико-математических наук, профессор. Окончил Уральский политехнический институт. С 1968 г. работал в Белорусском государственном университете (с 1970 по 2000 гг. — заведующий кафедрой, с 2000 г. — профессор кафедры методов оптимального управления). Заслуженный деятель науки БССР (1982). Почетный доктор Иркутского государственного университета. Лауреат премии Академии наук Беларуси за цикл работ по конструктивной теории экстремальных задач (1995). Автор более 500 научных работ, в том числе 8 монографий, посвященных качественной и конструктивной теории оптимального управления и ее приложениям.

Кириллова Фаина Михайловна

Доктор физико-математических наук, профессор, член-корреспондент Национальной академии наук Беларуси. Окончила Уральский государственный университет. С 1967 г. работает в Институте математики Национальной академии наук Беларуси (с 1969 по 2007 гг. — заведующая лабораторией теории процессов управления, с 2008 г. — главный научный сотрудник Института математики). Почетный доктор Иркутского государственного университета. Лауреат премии Совета Министров СССР (1986) и премии Академии наук Беларуси (1995). Заслуженный деятель науки Республики Беларусь (2001). Автор 8 монографий и свыше 300 работ по качественным и конструктивным методам оптимизации и их приложениям.