Задача о кратчайшем пути как задача

Линейного программирования

Запишем задачу о кратчайшем пути как задачу линейного программирования (ЛП). Пусть x_ij = 0, если дуга (i; j) входит в путь m, x_ij = 0, если дуга (i; j) не входит в путь m, i, j = .

Задачу о минимальном пути можно записать в виде:

L(x) = ® (1)

= 1, = 1, (2)

= , k = . (3)

Любое решение системы неравенств (2)-(3) определяет путь в сети без контуров (но не в сети с контурами).

Пусть все контуры имеют строго положительную длину, то есть нет контуров отрицательной и нулевой длины. Тогда решение задачи (1)-(3) определяет путь кратчайшей длины.

Сформулируем задачу линейного программирования, двойственную задаче (1)-(3).

Известно, что всякая задача линейной оптимизации имеет так называемую "двойствен­ную задачу", которую иногда полезно использовать для поиска решения и ана­лиза получаемых результатов в исходной задаче. Кроме того, двойственная за­дача дает экономическое обоснование для записи исходной задачи при поиске оптимального применения производственных ресурсов.

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

Исходная задача на минимум заменяется задачей на максимум и наоборот.

Коэффициенты в целевой функции заменяются постоянными в правых частях ограничений исходной задачи.

Постоянные в правых частях ограничений заменяются коэффициентами целевой функции исходной задачи.

Столбцы и строки в коэффициентах при неизвестных в ограничениях исходной задачи меняются местами в двойственной задаче.

j-я неотрицательная переменная исходной задачи заменяется на j-е неравенство вида ≥ двойственной задачи.

j-я переменная, не имеющая ограни­чения в знаке исходной задачи заменяется на j-е соотношение в виде равенства двойственной задачи.

j-е неравенство вида ≤ исходной задачи заменяется на j-ю неотрицательную переменную двойственной задачи.

j-е соотношение в виде равенства исходной задачи заменяется на j-юпеременную, не имеющую огра­ничения в знаке двойственной задачи.

Значения переменных у_i в оптимальном решении двойственной задачи представляют собой оценки влияния правых частей системы простых ограни­чений исходной задачи на оптимальное значение ее целевой функции. Если рассмотреть задачу использования различных видов сырья, объемы которых за­даются правыми частями, то:

- для у_i = 0 при увеличении i-ro ресурса оптимальный доход остается неиз­менным и ценность этого ресурса равна нулю, поскольку фактически рас­полагаемый объем ресурса превышает все потребности в нем, поэтому та­кой ресурс не имеет никакой ценности;

- если значение у_i мало, то незначительному увеличению i-ro ресурса будет соответствовать небольшое увеличение оптимального дохода и ценность ресурса невелика;

- если значение y_i велико, то незначительному увеличению i-ro ресурса бу­дет соответствовать существенное увеличение оптимального дохода и ценность ресурса будет высока. Уменьшение такого ресурса ведет к суще­ственному сокращению выпуска продукции.

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

поставив в соответствие ограничениям (2) двойственные переменные l₀ и l_n, а ограничениям (3) – двойственные переменные {l_i}, i = :

l_n - l₀ ® max (4)

l_j - l_i £ l_ij, i, j = . (5)

По теореме двойственности линейного программирования, для оптимальных решений задач (1)-(3) и (4)-(5) значения целевых функций совпадают.

Задача (4)-(5) называется задачей о потенциалах вершин графа. Общая ее формулировка такова: найти потенциалы вершин {l_i}, удовлетворяющие системе неравенств (5) и максимизирующие некоторую функцию F(l), где l = (l₀, l₁, ..., l_n). Необходимые и достаточные условия существования решения задачи о потенциалах даются теоремой 1.

Примером является задача о ближайших потенциалах, в которой F(l) = |l_j - |, где { } могут интерпретироваться как желательные потенциалы.

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

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

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

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

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

Одномерная задача о «ранце»

Пусть имеется n предметов, которые могут быть полезны в походе. Полезность i-го предмета оценивается числом a_i, вес предмета (или его объем) - b_i. Суммарный вес, который может нести турист (объем рюкзака), ограничен величиной R. Требуется найти набор предметов, обладающий максимальной суммарной полезностью и удовлетворяющий ограничению.

Обозначим x_i – переменную, принимающую значение ноль (если i-ый предмет не кладется в ранец) или единица (если i-ый предмет кладется в ранец). Тогда задача о ранце имеет вид:

® (6)

£ R. (7)

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

Пусть имеются 4 предмета, веса и ценности которых приведены в табл. 1.

Таблица 1. Веса и ценности предметов

i	ai	bi

Построим сеть, приведенную на рис. 14, по следующим правилам. По оси абсцисс будем последовательно откладывать номера предметов, по оси ординат – их вес. Из каждой точки (начиная с точки (0; 0)) выходят две дуги – горизонтальная (соответствующая альтернативе «не брать предмет») и наклонная (соответствующая альтернативе «взять предмет»), вертикальная проекция которой равна весу предмета.

Рис. 14. Метод дихотомического программирования

Длины наклонных дуг положим равными ценности предметов, длины горизонтальных дуг – нулю. Полученная сеть (конечная вершина является фиктивной и вес любой дуги, соединяющей ее с другими вершинами, равен нулю) обладает следующими свойствами: любому решению задачи (6)-(7) соответствует некоторый путь в этой сети; любому пути соответствует некоторое решение задачи. Таким образом, задача свелась к нахождению пути максимальной длины (потенциалы вершин приведены в квадратных скобках). Решение задачи – результат применения алгоритма 1 (сеть не содержит контуров) – на рисунке 4 выделено жирными линиями. Значение целевой функции равно 16.