Файл: Курс лекций.doc

Рисунок 6.7 – График Ганта

5 Постановка задач для решения методами спу

При подготовке задачи для решения методами СПУ проводят следующие операции:

1. составляют перечень всех работ;

2. указывают логическую очередность выполнения работ;

3. определяют ресурсы каждой работы, длительность их выполнения;

4. все сведения представляют в виде таблицы (см. таблицу 6.1).

Таблица 6.1 – Структурно-временная таблица комплекса работ

Теория СПУ позволяет решать задачи плани­рования в различной постановке. Например, в результате решения задачи определяется оптимальный план комплекса при заданной схеме организации работ или же решение задачи связано с поиском оптимальной схемы организации работ, обеспечивающей макси­мальную эффективность. Множество задач можно свести к одной из трех наиболее типичных:

1. Определить максимальную сумму экономии и способ ее полу­чения при заданной организации работ и времени их выполнения.

2. Разработать порядок использования ограниченных дополни­тельных ресурсов, чтобы время выполнения всего комплекса работ не превышало установленного.

3. Распределить выделенные ресурсы между работами так, что­бы минимизировать время выполнения всего комплекса работ.

После описания экономического содержания комплекса работ предприятия следует выделить опреде­ляющие характеристики. В качестве таковых могут быть:

В — общие ресурсы по выполнению комплекса работ;

b_ij — выделенные ресурсы для выполнения элементарной работы (i, j);

t_ij — длительность выполнения элементарной работы (i, j) с выде­ленными ресурсами b_ij;

С_ij - коэффициент пересчета ресурсов работы (i, j), ;

Т — время выполнения всего комплекса работ.

Затем необходимо выбрать главный экономический показатель (критерий эффективности), по которому определяется успех выполнения всего комплекса, например, время выполнения работ Т или общие затраты В. В качестве критерия эффективности Т — время, которое необходимо минимизировать.

Следует иметь в виду, что исходный вариант распределения ресурсов В по элементарным работам (b_ij) определяет длительность их выполнения, т.е. . На основании изложенного функцию в обобщенном виде можно записать так:

. (6.2)

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

Поскольку управляемыми параметрами являются ресурсы работ b_ij, то перераспределить их можно, перенеся часть ресурсов величиной x_ij с работ (i, j), у которых обнаружены резервы, на критические работы (h, k.) Очевидно, объемы снимаемых ресурсов должны равняться вносимым, т. е. х_ij = x_hk. Кроме того, ресурсы не могут быть сняты полностью, т.е. должно выполняться условие 0<х_ij<b_ij.

Таким образом, постановка задачи, например, по переводу магазина на самообслуживание, можно представить так:

найти такой вариант перераспределения ресурсов В между элементарными работами

и такие неотрицательные значения времени выполнения

,

которые при заданных ограничениях

, х_ij = x_hk, t_ij > 0, ,

обращали бы в минимум функцию цели, т.е. обеспечивали оптимальный срок выполнения всего комплекса работ Т°.

6 Виды и сущность оптимизации сетевых моделей

Расчет параметров сетевого графика проекта позволяет выявить критические работы, определяющие ход выполнения всего комплекса работ, продолжительность его реализации, ре­зервы времени событий и работ и проанализировать, можно ли его использовать в качестве плана выполнения работ. Чаще всего требуется улучшение сетевого графика с учетом сроков выполнения работ и рационального использования материаль­ных, трудовых и денежных ресурсов, т. е. требуется его опти­мизация. Рассмотрим некоторые математические модели оп­тимизационных задач на сетевых графиках.

6.1 Оптимизация проекта по времени. Пусть задан срок выполнения проекта t₀, а расчетное t_кр > t₀. В этом случае оптимизация комплекса работ сводится к сокра­щению продолжительности критического пути, которое может быть осуществлено либо за счет перераспределения внутрен­них резервов, либо за счет привлечения дополнительных средств.

Сокращение времени завершения проекта, как правило, связано с привлечением дополнительных средств (количес­тво рабочих, сверхурочное время). Рассмотрим два примера постановки задачи оптимизации проекта по времени с при­влечением дополнительных средств.

Задача 1 заключается в определении величины дополнитель­ных вложений х_ij в отдельные работы проекта с тем, чтобы общий срок его выполнения не превышал заданной величины t₀, а сум­марный расход дополнительных средств В был минимальным.

Задан сетевой график G = (Е,) выполнения проекта, где Е — множество событий, а — множество работ. Продолжительность каждой работы равна t_ij. Известно, что вложение дополнительных средств х_ij в работу (i, j) сокра­щает время ее выполнения от t_ij до t'_ij, причем , гдеk_ij – технологические коэффициенты использования дополнительных средств. Но сокращение продолжительности работы не беспредельно, для каждой работы существует минимально возможное время ее выполнения d_ij.