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

Задание

Построить график выполнения комплекса работ в установленный срок Т=16, обеспечивающий минимальные затраты, если последовательность работ описывается ниже представленной моделью (рис.12.2).

Рис.12.2 Конструкция, подлежащая сборке в примере

Длительности операций и удельные затраты на ускорение темпов работ приведены в таблице 12.1.

Таблица 12.1

Наименование работы	Номер работы	Минимальная длительность работы, dij	Максимальная длительность работы, Dij	Удельные затраты на ускорение темпов работы, dij
Установка блока 1
Установка блока 2
Установка блока 3
Установка блока 4
Установка блока 5
Установка блока 6
Установка блока 7
Установка блока 8
Установка блока 9

Строим сетевую модель (вспомогательная таблица работ – таблица 12.2) и определяем критический путь для двух вариантов:

1. нормальный план (длительности работ t_ij=D_ij);

2. срочный план (длительности работ d_ij).

Таблица 12.2

Номер работы	Индекс начального события работы, i	Индекс конечного события работы, j	Минимальная длительность работы, dij	Максимальная длительность работы, Dij	Удельные затраты на ускорение темпов работы, dij

Длительность критического пути в первом случае составит - 18, а во втором - 12, диаграммы Гантта для этих двух вариантов представлены на рис.12.3 и 12.4.

Рис.12.3 Нормальный план выполнения работ

Рис.12.4 Срочный план выполнения работ

Таким образом, необходима оптимизация S_ср<=T (12<16).

Основой для построения системы ограничений (12.7) линейной модели является множество полных путей сети и их длительность в «срочном» плане. Эту информацию удобно представить в виде таблицы 12.3.

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

После вычисления допустимых приращений полных путей из таблицы вычеркиваются столбцы, соответствующие работам с неизменной длительностью. Оставшаяся часть таблицы со столбцом допустимых приращений полных путей составляет часть симплекс-таблицы, соответствующей системе ограничений (12.7).

Таблица 12.3

Работы (i,j)	(i,j)		Длительность полного пути	Допустимое приращение полного пути
dij	dij
Варианты полных путей
…
r

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

Таблица 12.4

Работы (i,j)	0,1	0,2	0,3	1,5	2,5	3,4	5,7	3,6	6,7	Длительность полного пути	Допустимое приращение полного пути
dij
Варианты полных путей

После подстановки числовых значений из таблиц 12.2 и с учётом вспомогательной таблицы 12.4 модель задачи примет вид:

(12.8)

(12.9)

Решим ЗМП средствами Excel. Полученное решение, а также модель прямой задачи представлены ниже (рис. 12.5).

Рис.12.5. Результаты решения задачи оптимизации календарного графика по стоимости

Таким образом, оптимальные приращения времени имеют следующие значения: Dt₀₁=1, Dt₀₂=2, Dt₀₃=1, Dt₁₅=2, Dt₂₅=0, Dt₃₄=2, Dt₅₇=1, Dt₃₆=0, Dt₆₇=1.

На основе полученного решения и исходных данных составляется таблица 12.5 длительностей работ в «срочном» (t_ij=d_ij), оптимальном (t_ij=d_ij+Dt_ij) и «нормальном» (t_ij=D_ij) планах. Диаграмма Гантта для оптимального по затратам плана представлена на рис.12.6.

Таблица 12.5

Номер работы	Индекс начального события работы, i	Индекс конечного события работы, j	Срочный план, (tij=dij)j	Оптимальный план, (tij=dij+Dtij)	Нормальный план, (tij=Dij)

Рис.12.6 Оптимальный план выполнения работ

Длительность критического пути не превышает директивную, а точнее равняется ей (T=16). Переход от «срочного» плана с T=12 к оптимальному с T=16 позволяет достичь экономии С=29 (значение целевой функции рис.12.5).

Варианты для выполнения лабораторной работы №12

Задание

Построить график выполнения комплекса работ в установленный срок T, обеспечивающий минимальные затраты, если последовательность работ описывается моделью на рис.10.8). Принять максимальные длительности выполнения операций D_ij равными t_ij из таблицы 10.7. Минимальные длительности операций и удельные затраты на ускорение темпов работ, а также директивный срок выполнения комплекса работ приведены в таблице 12.6.

Таблица 12.6

Вар №	Минимальная длительность работы, dij
Удельные затраты на ускорение темпов работы, dij
										T

5.Рекомендуемая литература

1. Ашихмин А.А., Подольский М.П., Посметная Т.К. Методические указания по выполнению лабораторных работ на ЭВМ по дисциплине «Математическое программирование и моделирование». – М.: МГГУ, 1985. – С.57.

2. Куперштейн В.И. Современные информационные технологии в делопроизводстве и управлении. – СПб.: БХВ – Санкт-Петербург, 2000. – С.256.

3. Резниченко С.С., Ашихмин А.А. Математические методы и моделирование в горной промышленности. – М.: МГГУ, 1997. – С.252-311.