Математическая постановка

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

Математическая постановка задачи оптимизации на графах в общем случае может быть сформулирована в следующем виде:

или ,

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

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

Вернемся к рассмотрению задачи о максимальном потоке в сети и начнем с построения математической модели данной задачи.

Пусть G=(V, E, h) – ориентированный граф, в котором V={v₁, v₂,…,v_n} – конечное множество вершин, E={e₁, e₂,…,e_n} – конечное множество дуг, h: E→Z₊ - весовая функция дуг, которая интерпретируется как пропускная способность дуги. Дополнительно в графе фиксируются две вершины: начальная вершина v_s, которая называется исток, и конечная вершина v_t, которая называется сток.

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

Введем в рассмотрение следующие неотрицательные целочисленные переменные – x_ij, которые интерпретируются как величина потока, проходящего по дуге . Тогда математическая постановка задачи о максимальном потоке в сети может быть сформулирована следующим образом:

,

где множество допустимых альтернатив формируется следующей системой ограничений типа неравенств:

		(15.1)
	(15.2)
	(15.3)
	(15.4)

При этом первое ограничение (15.1) требует выполнения следующего условия: величина потока, выходящего из вершины v_s (истока), должна быть равна величине потока, входящего в вершину v_t (сток). Вторая группа ограничений (15.2) гарантирует выполнение следующего условия: любой частичный поток, входящий в каждую промежуточную вершину графа, должен быть равен потоку, выходящему из этой вершины. Общее количество ограничений (15.1) и (15.2) равно n-1. Третья группа ограничений (15.3) требует выполнения следующего условия: величина потока протекающего по дуге , должна быть неотрицательной и не должна превышать пропускной способности этой дуги c_ij. Наконец, последнее ограничение (15.4) требует, чтобы все переменные принимали только неотрицательные целочисленные значения.

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