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

Пусть для каждой дуги (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.

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