Методы исследования операций при принятии решений. Бодров В.И - 37 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Если последнее не желательно, то можно вместо целевой функции (2.10) использовать другую це-
левую функцию
,
11
i
n
i
ii
n
i
i
tMbQ
∑∑
==
−ρ= (2.11)
где М
i
– некоторое большое число – штраф на время выполнения операций.
При большом t
i
целевая функция уменьшается, поэтому в оптимальном решении будет компромисс
между стоимостью комплекса работ и временем выполнения каждой операции. Подбором чисел М
i
можно выделить те операции, в которых желательно уменьшить время их выполнения, и те, в которых же-
лательно уменьшить стоимость работ.
Представленную задачу можно сформулировать и как задачу минимизации времени t(k) выполне-
ния всего комплекса работ при затратах не меньше заданных.
Для решения этих задач разработано много алгоритмов, использующих их особенности и обладающих
большим быстродействием (например, алгоритм Келли), чем симплекс-метод.
В качестве примера рассмотрим эвристический метод, позволяющий как вручную, так и с помощью
вычислительной техники найти достаточно близкое к оптимальному решение.
Этот метод рассматривается на примере графа (рис. 2.14).
В табл. 2.3 представлены для данного примера диапазоны изменения продолжительности работ [
i
ρ
,
i
ρ ], цены b
i
единицы уменьшения продолжительности работы и интервалы изменения продолжительно-
сти .
q
i
ρ∆
2.3 Результаты расчета графа эвристическим путем
Вершина
i
ρ
i
ρ
b
i
q
i
ρ∆
0 1 2 10 1
1 2 4 2 2
2 2 3 2 1
3 1 1 – 0
4 4 4 – 0
5 4 6 2 2
6 4 12 3 8
7 1 3 4 2
8 1 2 4 1
9 0 0 – 0
Продол-
житель-
ность
10 20
Как видно из рис. 2.14, анализ графа проводится при продолжительностях работ, равных макси-
мальным
.
i
ρ
При этом время выполнения всех работ составило Т = 20.
При минимальных значениях продолжительностей работ
i
ρ
время выполнения комплекса работ со-
гласно графу (рис. 2.16) в соответствии с данными табл. 2.3 составляет Т = 10.
Значения допустимых изменений продолжительности работ приведены в табл. 2.3.
Алгоритм решения задачи оптимизации продолжительности работ сети представлен на рис. 2.17.
Этот алгоритм позволяет построить зависимость увеличения стоимости С работ от уменьшения времени
Т выполнения работ, что позволяет найти необходимый компромисс среди этих величин.
Согласно блок-схеме алгоритма вначале выписываются все возможные пути графа от начальной
вершины до конечной (табл. 2.4).

Страницы