Путь максимальной эффективности с учетом штрафов.

, ч fa(т - т(m)), т(m) < T ,,

нению, то есть: c(m) = < , где коэффициенты a

lb (T (m) - T), т < т (m)

и b могут быть как положительными, так и отрицательными.

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

m* = arg max [Э(ц) - c(m)].

m

Обозначим lij(1) = Эу - Я ty, где Я - некоторый параметр, Т(Я) - продолжительность оптимального пути при параметре Я, то есть пути, имеющего максимальную длину, измеряемую в 1у(Я). Легко показать, что с ростом Я величина Т(Я) не возрастает.

Обозначим T(a), T(b) - продолжительности оптимального пути при Я равном a (соответственно, b), m(a), m(b) - эти пути (для их нахождения необходимо решить две задачи на поиск пути максимальной длины). Рассмотрим шесть случаев (исходную задачу можно разбить на две подзадачи - поиска максимума 3(m) -

c(m) при T(m) ? т и при T(m) > т).

Пусть a > Д, тогда T(b) > T(a) и:

если T(b) > T(a) > T, то m(b) - оптимальное решение;

если T > T(b) > T(a), то m(a) - оптимальное решение;

если T(b) > T > T(a), то, сравнивая m(a) и m(b) по длинам l = Э - c, выбираем путь, имеющий максимальную длину.

Пусть a <Д, тогда ДД < T(a) и:

если T(a) > T(b) > T, то m(b) - оптимальное решение;

если T > T(a) > T(b), то m(a) - оптимальное решение;

если T(a) > T > T(b), то задача не имеет эффективных методов решения (возможные подходы описаны в [7]).