Читать онлайн «Матроиды в дискретной оптимизации»

М. М. Ковалев МАШРОИДЫ В ДИСКРЕТНОЙ ОПТИМИЗАЦИИ УРСС М. М. Ковалев МАТРОИДЫ В ДИСКРЕТНОЙ ОПТИМИЗАЦИИ Было рекомендовано советом факультета прикладной математики Белорусского государственного университета имени В. И. Ленина Издание второе, стереотипное УРСС Москва • 2003 ББК 22. 176, 32. 811 Ковалев Михаил Михайлович Матроиды в дискретной оптимизации. Изд. 2-е, стереотипное. М. : Едиториал УРСС, 2003. - 224 с. ISBN 5-354-00498-5 Настоящая книга содержит основные положения теории матроидов — теории, приобретающей повышенный интерес у специалистов различных областей науки и техники. Обобщены результаты по применению матрои- матроидов в дискретной оптимизации для анализа эффективности эвристических и приближенных методов. Содержатся результаты по дискретному выпуклому анализу и матроидным структурам. Значительное внимание уделяется экс- экстремальным задачам на графах и сетях. Исследуются нелинейные потоковые задачи с полиматроидными ограничениями, а также транспортные задачи и задачи расчета электрических схем. Предназначена для научных работников и инженеров, занятых пробле- проблемами оптимизации в системах автоматизированного проектирования и упра- управления. Может быть использована студентами и аспирантами, специализиру- специализирующимися по прикладной математике. Рецензенты: доктор физико-математических наук В. С. Танаев, доктор физико-математических наук В. К. Леонтьев, кандидат физико-математических наук Э. Н. Гордеев Издательство «Едиториал УРСС». 117312, г. Москва, пр-т 60-летия Октября, 9. Лицензия ИД №05175 от 25. 06. 2001 г. Подписано к печати 10. 09. 2003 г. Формат 60x84/16. Тираж 500 экз. Печ. л. 14. Зак. № 2-1050/270. Отпечатано в типографии ООО «Рохос». 117312, г. Москва, пр-т 60-легия Октября, 9. Математические модели не тождественны самой ситуации, а являются ее приближенным опи- описанием, поэтому и решать задачи ДО разумно с той же степенью приближения к оптимуму. Тем более, что принципиальная труд- трудность задач ДО делает, по-види- по-видимому, невозможным построение эффективных точных алгоритмов для нетривиальных классов за- задач. Следовательно, вопросы си- систематизации эвристических про- процедур, создания математических средств оценки их качества, син- синтеза высокоэффективных семейств «конкурирующих» алгоритмов представляются актуальными. Их актуальность возрастает t расши- расширением приложений ДО в таких новых областях, как проектиро- проектирование сетей ЭВМ, параллельные вычисления, создание интегриро- интегрированных производственных систем из гибких модулей, автоматиза- автоматизация проектирования всевозмож- всевозможных схем и в первую очередь сверхбольших интегральных схем (СБИС).