Гольштейн Е.Г., Юдин Д.Б. Специальные направления в линейном программировании Изд. стереотип.

Оглавление

Предисловие

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

В [87] достаточно обстоятельно изложены теория и конечные методы решения общей задачи линейного программирования и некоторых важных специальных задач.

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

Настоящую работу следует рассматривать как продолжение книги [87]. При изложении материала авторы ориентировались на читателя, знакомого с основными понятиями, качественными результатами и вычислительными алгоритмами, приведенными в [87].

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

Глава 1 содержит основы теории и методы анализа транспортных сетей. Сетевые постановки задач транспортного типа являются достаточно содержательными и наглядными и в ряде случаев допускают использование более экономных методов анализа по сравнению с соответствующими матричными постановками. Приложения сетевых методов выходят за рамки задач транспортного типа.

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

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

Методы главы 3 являются основой экономного анализа однопараметрических семейств задач линейного программирования.

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

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

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

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

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

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

В книге сохранены терминология, обозначения и методические подходы, принятые в [87]. Отдельные главы книги весьма слабо связаны между собой, и читатель, знакомый с основами линейного программирования, может начать изучение "Новых направлений" с любой главы. Авторы весьма признательны В.В.Боковой за оформление рукописи и подготовку ряда иллюстративных примеров.

Об авторах

Гольштейн Евгений Григорьевич

Доктор физико-математических наук, профессор, заслуженный деятель науки РФ. Заведующий лабораторией Центрального экономико-математического института РАН, профессор экономического факультета МГУ имени М. В. Ломоносова. Сфера научных интересов — теория и вычислительные методы задач оптимизации и равновесия; развитие математического аппарата, используемого в экономико-математическом моделировании. Е. Г. Гольштейн — автор около 200 научных работ, в том числе 12 книг, большинство из которых переведено на английский, немецкий, французский, испанский, японский и другие языки.

Юдин Давид Беркович

Доктор технических наук, профессор, заслуженный деятель науки и техники РСФСР. Участник Великой Отечественной войны. В течение ряда лет консультировал Госплан СССР. Более 35 лет являлся профессором экономического факультета МГУ имени М. В. Ломоносова; с 1994 г. — профессор Высшей школы экономики. Награжден двумя орденами и 16 медалями. В 1982 г. Международным обществом по математическому программированию и Американским математическим обществом Д. Б. Юдину присвоена премия имени Фалкерсона по дискретной математике. В 1994 г. избран действительным членом Нью-Йоркской академии наук. Автор 18 монографий по различным разделам математического программирования, по теории и методам принятия решений, а также более 200 научных работ в различных периодических изданиях.