2.Оптимизация графика с использованием линейного программирования

Эффективность использования симплекс-метода при оптимизации графика работ можно повысить, если сократить размерность системы ограничений и число итераций поиска оптимального решения. Этого можно достичь, если в качестве оптимизируемой переменной использовать t_ij - приращения длительностей работ при переходе от «срочного» к оптимальному плану реализация проекта.

Пусть имеется «срочный» план с критическим путем S_ср<=T. В случае S_ср>T задача неразрешима, так как «срочный» план обеспечивает минимально возможные сроки выполнения проекта.

Оптимизируемая переменная t_ij представляет разность между длительностью работы и минимально допустимым сроком выполнения d_ij:

t_ij= t_ij - d_ij (12.4)

В исходном «срочном» плане t_ij=0 для всех (i;j) Q. Увеличение t_ij снижает затраты от уровня «срочного» плана, поэтому в качестве критерия оптимальности можно взять максимум суммарной экономии:

(12.5)

Из (12.4) следует, что

t_ij = t_ij + d_ij (12.6)

После подстановки (12.6) в исходные ограничения (12.2) и (12.3) условия допустимых длительностей работ примут вид:

(12.7)

3.Пример выполнения лабораторной работы

Задание

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

	7							9
4			5			6		8
	1		2			3

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

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

Таблица 12.1

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

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

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

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

Таблица 12.2

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

Длительность критического пути в первом случае составит - 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
Варианты полных путей	1	1
	2	0
	…
	r

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

Таблица 12.4

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

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

(12.8)

(12.9)

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

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

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

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

Таблица 12.5

Номер работы	Индекс начального события работы, i	Индекс конечного события работы, j	Срочный план, (tij=dij)j	Оптимальный план, (tij=dij+tij)	Нормальный план, (tij=Dij)
1	2	3	4	5	6
1	0	1	5	6	8
2	0	2	4	6	6
3	0	3	4	5	5
4	1	5	2	4	4
5	2	5	3	3	3
6	3	4	3	5	5
7	5	7	5	6	6
8	3	6	2	2	2
9	6	7	2	3	3

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

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