Задача «время-стоимость»

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

Зависимость между длительностью работы и ее стоимостью с некоторой долей условности можно представить в виде аппроксимирующей прямой, имеющей линейную зависимость (рис.1.16)

C(ij)

C_max

C_изм

∆С

С_min

t_min t_изм t_max t(ij)

Рис.1.16. График «время-стоимость» работы (ij)

Чем более мы стремимся сократить время работы, тем дороже она нам обходится. Для каждого вида работ можно определить коэффициент возрастания затрат на единицу времени:

S(ij) =

C_max(ij) – C_min(ij)

t_max(ij) – t_min(ij)

В курсе рассматривается алгоритм оптимизации сетевой модели по критерию «стоимость».

Дано: Сетевая модель. По каждой работе (ij) дается возможный диапазон длительности работы t_min(ij), t_max(ij), минимальная стоимость работы C_min(ij),коэффициент S(ij). Необходимо найти зависимость Ткр между и суммарными затратами, ставя задачу обеспечить минимум возрастания затрат при уменьшении Ткр.

Алгоритм заключается в следующем:

1. Найти критический путь, его длину Ткр.

С = ∑С(ij)

Lкр = (i₀, i₁,…,i_n) из предположения t(ij) = t_max(ij)

2. На этом пути найти работу (kℓ) Є Lкр, у которой S(kℓ) будет иметь наименьшее значение.

3. Для выбранной работы найти величину ∆t(kℓ) = t_max(kℓ) - t_min(kℓ)

4. Определить ∆С(kℓ) = S(kℓ)*∆t(kℓ)

5. Следовательно, при уменьшении Ткр на величину ∆t(kℓ) стоимость всех работ увеличивается на величину ∆С(kℓ)

С^* = С_пред. + ∆С(kℓ)

6. Рассчитать сетевую модель с учетом измененной продолжительности работы (kℓ).

7. Возвратиться к п.1. В результате реализации данного алгоритма получается график зависимости С от Ткр. По этому графику легко координировать отношения между инвестором и производителем.

ПРИМЕР

Дано: Сетевая модель (рис.1.17)

Рис.1.17

Информация о сетевой модели задана в табл.1.5.

Таблица 1.5.

ij	tmin дни	tmax дни	Cmin руб	S(ij) руб/день
1-3
3-4
1-2
2-4
1-6
6-7
4-5
7-5
			∑90

Необходимо: сократить Ткр так, чтобы дополнительные затраты были минимальными.

Рассчитаем сетевую модель из предположения t(ij) = t_max, получим Ткр^max = 30; из предположения t(ij) = t_min – получим Ткр^min = 15.

Таким образом:

Ткр^min ≤ Ткр ≤ Ткр^max

15 ≤ Ткр ≤ 30

Будем сокращать Ткр.=30 так, чтобы дополнительные затраты росли оптимально, т.е. были минимальными. Решение сведем в таблицу 1.6.

Таблица 1.6.

Пути	ij / S(ij)	Ткр (шаги)
1-3	3-4	1-2	2-4	1-6	6-7	4-5	7-5
1)1-3-4-5
2)1-2-4-5
3)1-6-7-5
Tmax – tmin									∑ стоимость
шаги

График зависимости стоимости от времени будет иметь вид (рис.1.18)

∑С

∑С_опт^max 235

∑C^min 90

15 21 22 24 30 Ткр

Рис.1.18. График зависимости стоимости от времени выполнения проекта

Последовательность расчета:

На первом шаге рассматриваем 2-ой путь, так как он является критическим Ткр=30. На этом пути выбираем работу (1-2), так как у нее S(1-2) наименьшая среди других работ: S(1-2) = 2.

∆t(1-2) = t_max(1-2) – t_min(1-2) = 6

∆C(1-2) = S(1-2)* ∆t(1-2) = 2*6 =12

∑С^изм = ∑С^{первоначальн.} + ∆C = 90+12 = 102

Ткр_{(измененное)} = Ткр_{(старое)} - ∆t(1-2) = 30-6 = 24

На втором шаге появились два одинаковых по длине критических пути. Выбираем любой из них, например, путь номер два. На этом пути выбираем работу (4-5), так как = работа (1-2) уже исчерпана с точки зрения уменьшения, а из оставшихся работ S(4-5) имеет меньшее значение, т.е. S(4-5) = 5.

∆t(4-5) = 3.

Работа (4-5) принадлежит и первому и второму пути, следовательно, длина и первого и второго пути должна быть уменьшена на 3 ед. Длина второго пути станет равна (24-3) = 21. Длина первого пути станет равна (20-3) = 17. Длина третьего пути осталась без изменения

∆C(4-5) = 5*3 = 15

∑С^изм = ∑С^{предыд.} + ∆C(4-5) = 102+15 = 117. И т.д.