Рассмотрена задача построения многозначного решения для уравнения Бакли–Леверетта, описывающего процесс двухфазной фильтрации в среде с переменным коэффициентом пористости. Такое уравнение используется для расчета эволюции поверхности разделения фаз “нефть–вода” при разработке нефтяных месторождений. Показано, как для заданных начальных условий построить каустику многозначных решений.

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