Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания
VII. СЕТЕВЫЕ ЗАДАЧИ
Довольно широкий класс задач, встречающихся при планировании разных работ, проектировании систем, организации транспортных перевозок, размещении различных объектов обслуживания населения и многие другие процессы описываются сетевыми моделями. Во многих случаях эти задачи можно свести к задачам математического программирования. Однако характерной особенностью таких задач является большая размерность, обуславливающая необходимость поиска более эффективных методов оптимизации. Эти методы должны не только быть эффективными в вычислительном смысле, но и обеспечивать гибкость по отношению к изменениям исходных данных. Плодотворной основой для построения таких методов является аппарат сетевого анализа, базирующийся на теорию графов. Теория графов это раздел математики, началом развития которого явилась задача о кенигсбергских мостах, сформулированная швейцарским ученым Л. Эйлером в 1736 году.
В данном разделе мы рассмотрим наиболее известные и хорошо изученные сетевые задачи, имеющие большое прикладное значение, а именно задачи поиска кратчайшего пути, задачу коммивояжера и задачу определения максимального потока в сети.
Перед тем как приступить к знакомству с методами решения указанных проблем приведем ряд определений и понятий теории графов, используемых при построении алгоритмов решения сетевых задач.