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

Оглавление

Предисловие

Транспортные задачи линейного программирования представляют собой математические модели важных практических задач, распространенных в различных сферах человеческой деятельности. Кроме задач о перевозках продуктов к ним сводится много других задач (см., например, [1–4]).

С математической точки зрения задачи, исследуемые в данной, второй, части книги, составляют специальный класс общих задач линейного программирования, рассмотренных в первой части [5]. При решении таких задач используются три подхода. Во-первых, каждую специальную задачу можно записать в форме общей задачи и решать ее общими методами. Во-вторых, можно, учитывая специальную структуру задачи, детализировать общий метод и использовать полученную реализацию метода. Если задачи имеют настолько яркую специфику, что оба указанных подхода для них выглядят искусственными, то применим третий подход, при котором непосредственно реализуются идеи (принципы), положенные в основу методов решения общих задач. Первый подход используется, как правило, при решении задач, которые еще не выделены в специальные классы. В связи с распространенностью подобных задач в линейном программировании предложен мультипликативный метод. Достоинства второго подхода наиболее полно проявляются при решении транспортных задач в матричной форме. Из общего курса "Методы оптимизации" видно, насколько упрощаются и тесно связываются с моделью операции симплекс-метода после его реализации в виде метода потенциалов. Эффективность третьего подхода удобно демонстрировать на транспортных задачах в сетевой форме (на задачах о потоках).

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

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

Книга написана на основании лекций, которые читаются на факультете прикладной математики Белгосуниверситета им.В.И.Ленина. Предполагается, что читатель знаком с линейным программированием в объеме учебного пособия "Методы оптимизации" (в дальнейшем сокращено [МО]) и первой части данной книги (сокращено [ч. 1]), написанных авторами и изданных издательством БГУ в 1975 и в 1977 гг. соответственно.

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

Об авторах

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

Фаина Михайловна КИРИЛЛОВА

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