Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания

VII. СЕТЕВЫЕ ЗАДАЧИ

Довольно широкий класс задач, встречающихся при планировании разных работ, проектировании систем, организации транспортных перевозок, размещении различных объектов обслуживания населения и многие другие процессы описываются сетевыми моделями. Во многих случаях эти задачи можно свести к задачам математического программирования. Однако характерной особенностью таких задач является большая размерность, обуславливающая необходимость поиска более эффективных методов оптимизации. Эти методы должны не только быть эффективными в вычислительном смысле, но и обеспечивать гибкость по отношению к изменениям исходных данных. Плодотворной основой для построения таких методов является аппарат сетевого анализа, базирующийся на теорию графов. Теория графов это раздел математики, началом развития которого явилась задача о кенигсбергских мостах, сформулированная швейцарским ученым Л. Эйлером в 1736 году.

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

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


Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074