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

Пусть для каждой дуги (n + 1)-вершинной сети заданы два числа: эффект Э_ij и время t_ij. Каждый путь m из начальной вершины в конечную вершину характеризует некоторый процесс (проект). Под продолжительностью пути будем понимать сумму времен его дуг. Если продолжительность процесса отличается от заданного времени T, то налагаются штрафы c(m), пропорциональные отклонению, то есть: c(m) = , где коэффициенты a и b могут быть как положительными, так и отрицательными.

Задача заключается в том, чтобы найти путь m^*, максимизирующий разность между эффектом и штрафами, то есть m^* = arg [Э(m) - c(m)].

Обозначим l_ij(l) = Э_ij - l t_ij, где l - некоторый параметр, T(l) – продолжительность оптимального пути при параметре l, то есть пути, имеющего максимальную длину, измеряемую в l_ij(l).

С ростом l величина T(l) не возрастает.

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

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

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

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

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

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

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

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

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

В этом случае задача не имеет простого решения, как в предыдущих случаях и приходится решать две задачи.

Задача 1. Минимизировать S(µ)+α(T(µ)-T₀) при ограничении T(µ)≤T₀

Задача 2. Минимизировать S(µ)+β(T(µ)-T₀ при ограничении T(µ)≥T₀

Лучшее из решений задач 1 и 2 будет оптимальным решением задачи.

Пример. Рассмотрим сеть приведённую на рис. 16. Затраты S_ij и продолжительности τ_ij указаны у дуг (первое число – затраты, а второе - продолжительности).

_(70;4)

_{(80;1) (90;1) (50;3)}

_(50;6) ^(40;3) _(70;2)

_(10;7)

^(80;2)

_(40;4)

_{(30;6) ( (10;9)}

Рис. 16. Исходная сеть к примеру

I. Пусть α=10, β=5

Определим µ(α). Соответствующая сеть с длинами дуг L_ij=S_ij+ατ_ij приведена на рис. 17 , путь µ(α) выделен µ(α)=(0,3,5,7)

₍₁₁₀₎

(90)

_{(90) (110) (90)}

Рис. 17. Преобразованная сеть

Имеем Т(α)=13 S(α)=120

L(α)=250

Определим µ(β) .Соответствующем сеть приведем на рис. 18.

(90) (85) (95) (65) (55) (80) (80) (45) (90) (60) (55) (60)

Pис. 18. Определение µ(β)

Имеем µ(β)=(0,3,6,7)

T(β)=22, S(β)=50, L(β)=160

Рассмотрим три случая

1. Пусть Т₀ = 24

поскольку

Т₀ > T( ) > T ( ),

то µ(α)= (0,3,5,7) – оптимальное решение.

Имеем F=S(α)+ α(T-T₀)=120+10(13-24)=10

2. Пусть Т₀ = 10.

Поскольку Т₀ < Т (α) <T(β), то

µ(β)=(0,3,6,7) - оптимальное решение.

Имеем:

F=S(β)+β(T(β)-T₀)=110

3. Пусть Т₀₌16, поскольку

T(α)<T₀<T(β)

то необходимо сравнить два решения.

3.1 µ=µ(α)=(0,3,5,7)

Имеем:

F₁₌L(α)-αT₀=250-10*16=90

3.2 µ=µ(β)=(0,3,6,7)

Имеем:

F₂=L(β)-βT₀=160-5*16=80

Так как F₁>F₂,то µ(β) - оптимальное решение и F=min (90;80)=80

II. Пусть α=5, β=10.

Пути µ(α) и µ(β) были определены выше:

µ(α)=(0,3,6,7)

T(α)=22, S(α)=50, L(α)=160

µ(β)=(0,3,5,7)

T(β)=13, S(β)=120, L(β)=250

Рассмотрим три случая

1. Пусть Т₀ = 24

Поскольку Т₀ >T(α)>T(β), то µ(α)=(0,3,6,7)- оптимальное решение.

Имеем:

F=S(α)+α(T(α)-T₀)=50-2*5=40

2. Пусть Т₀ = 10.

Поскольку Т₀ <T(β)<T(α), то μ(β)=(0,3,5,7) - оптимальное решение.

Имеем:

F=S(β)+β[T(β)-T₀]=120+10*3=150

3. Пусть Т₀ = 16. Поскольку T(β)<T₀<T(α), то для определения оптимального решения необходимо решить две задачи.

Задача 1. Определить путь μ, минимизирующий L(α)= при ограничении T(μ)≤T₀

Задача 2. Определить путь μ минимизирующий L(β),при ограничении T(μ)≥T₀

Рассмотрим первую задачу. Для этого заметим, что путей для которых T(μ)≥16 всего два.

Это путь μ₁=(0,2,6,7) и путь μ₂ =(0,3,6,7,) . Чтобы их исключить, достаточно удалить вершину 6. В полученной подграфе определим путь с минимальными затратами S(μ) (см. рис. 19)

[85]

(90) [135] (85) (65) [185] [80] (55)

(80) (95) (45) [105] (80) [45] (60)

Рис. 19. Путь с минимальными затратами S(μ)

Имеем μ=(0,3,5,7),

F₁=L(α)-αT₀=185-5*16=105

Рассмотрим вторую задачу.

Поскольку всего два пути имеют T(μ)>16, то сравнив их получаем оптимальный путь μ=(0,3,6,7), L(β)=270

F₂=L(β)-βT₀=270-10*16=110

Из двух решений выбираем лучшее.

Окончательно получаем оптимальный путь μ=(0,3,5,7) с величиной критерия F= 105.

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