Практическое занятие № 17 Распределение комплектов машин по объектам строительства

17.1. Цель работы – решение задач распределения комплектов машин по объектам строительства 6-ю способами.

17.2. Общие сведения. При выборе объемов работ на планируемый период строительная организация имеет парк машин. Исходя из годовой выработки каждой машины, инженерно-техническая служба будет ограничиваться суммарным объемом работ по объектам, равным суммарной годовой выработке машин. При этом количество объектов может быть не равным количеству машин, имеющихся в парке. Данные задачи не имеют на сегодняшний день окончательного решения одним методом. Поэтому такие типы задач решаются шестью способами одновременно. Затем берут наиболее удачное решение с минимальными затратами и проверяют полученное решение на оптимальность.

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

Пример решения задачи. В строительной организации имеются 6 бульдозеров, у которых суммарная годовая выработка составила в прошлом году 132 тыс.м³ разработанного грунта. При этом известны приведенные затраты Сij, связанные с выполнением единицы объема работы каждой машиной. Формируя объемы работ на следующий год, строительная организация выбрала 4 объекта с общим объемом земляных работ 132 тыс.м³. Требуется расставить бульдозеры по строящимся объектам так, чтобы суммарные затраты были минимальны. Исходные данные приведены в таблице 17.1.

Таблица 17.1

Марка бульдозера	Затраты на выполнение единицы объема работ Сij по объектам Вj, р./м3				Годовая выработка машин Пi, тыс. м3
	В1	В2	В3	В4
ДЗ-422 (А1)	20	38	51	16	18
ДЗ-42Г (А2)	32	18	48	71	14
ДЗ-42Г-1 (А3)	19	36	18	44	20
ДЗ-110В (А4)	18	24	55	67	26
ДЗ-116В (А5)	69	28	36	18	31
ДЗ-117А (А6)	41	56	24	32	23
Годовой объем работ Vj. тыс.м3	19	33	46	34	132

Решение задачи возможно при основной закономерности:

. (17.1)

Критерий оптимизации - суммарные затраты на выполнение всех работ можно записать:

. (17.2)

1. Решение задачи способом северо-западного угла. Сначала выполняют работы на 1- м объекте насколько возможно, затем на 2-м и т.д. (знаменатель, правая часть клетки). При этом способе объемы работ располагаются от левого верхнего угла матрицы до нижнего правого (табл. 17.2).

Таблица 17. 2

Марка бульдозера	Затраты на выполнение единицы работы Сij по объектам Вj, руб./м3				Пi, тыс. м3
	В1	В2	В3	В4
А1	20 / 18	38	51	16	18
А2	32 / 1	18 / 13	48	71	14
А3	19	36 / 20	18	44	20
А4	18	24	55 / 26	67	26
А5	69	28	36 / 20	18 / 11	31
А6	41	56	24	32 / 23	23
Vj, тыс. м3	19	33	46	34	132

Суммарные затраты:

Y = 18×20+ 1×32 + 13×18 + 20×36 + 26×55 + 20×36 + 11×18 +

+ 23×32 = 360 + 32 + 234 + 720 + 1430 + 720 + 198 + 736 = 4 430 тыс. руб.

2. Решение задачи способом наименьшего элемента в строке. Поочередно, начиная с первой строки матрицы с наименьшим стоимостным элементом, в клетку вносится максимально возможный объем работ. Если объем работ по строке не выполнен, то находится следующая клетка с минимальным элементом в этой строке, куда и распределяются оставшиеся объемы работ (табл. 17.3).

Таблица 17.3

Марка бульдозера	Затраты на выполнение единицы работы Сij по объектам Вj, р./м3				Пi, тыс. м3
	В1	В2	В3	В4
А1	20	38	51	16 / 18	18
А2	32	18 / 14	48	71	14
А3	19	36	18 / 20	44	20
А4	18 / 19	24 / 7	55	67	26
А5	69	28/12	36 / 3	18 / 16	31
А6	41	56	24 / 23	32	23
Vj, тыс. м3	19	33	46	34	132

Суммарные затраты:

Y = 18×16 + 14×18 + 20×18 + 19×18 + 7×24 + 12×28 + 3×36+ 16×18 + + 23×24 = 288 + 252 + 360 + 342+ 168 +336 + 288 + 552 = 2 694 тыс.руб.

3. Решение задачи способом наименьшего элемента в столбце. Поочередно, начиная с первого столбца матрицы с наименьшим стоимостным элементом, вносится максимальный объем работ. Если объем работ по столбцу не выполнен, то находится следующая клетка с минимальным стоимостным элементом в столбце, куда и распределяется оставшийся объём работ (табл. 17.4).

Таблица 17.4

Марка бульдозера	Затраты на выполнение единицы работы Сij по объектам Вj, р./м3				Пi, тыс. м3
	В1	В2	В3	В4
А1	20	38	51	16 / 18	18
А2	32	18 / 14	48	71	14
А3	19	36	18 / 20	44	20
А4	18 / 19	24 / 7	55	67	26
А5	69	28 / 12	36 / 3	18 / 16	31
А6	41	56	24 / 23	32	23
Vj, тыс. м3	19	33	46	34	132

Суммарные затраты: Y = 2694 тыс. руб.

4. Решение задачи способом наименьшего элемента в матрице. Этот способ дает лучшие результаты особенно в крупных матрицах. Требуется больше внимания и времени•. В матрице стоимостей имеется клетка с минимальным элементом (А₁, В₄), в которую помещаются максимально возможные объемы работ. Затем ищутся клетки со следующими минимальными стоимостными элементами, куда и помещаются оставшиеся объемы работ и т.д. (табл. 17.5).

Таблица 17.5

Марка бульдозера	Затраты на выполнение единицы работы Сij по объектам Вj, (р./м3)				Пi, тыс. м3
	В1	В2	В3	В4
А1	20	38	51	16/18 (1)	18
А2	32	18/14 (2)	48	71	14
А3	19	36	18/20 (3)	44	20
А4	18/19 (4)	24/7(6)	55	67	26
А5	69	28/12 (8)	36/3 (9)	18/16 (5)	31
А6	41	56	24/23 (7)	32	23
Vj, тыс. м3	19	33	46	34	132

Суммарные затраты: Y = 2694 тыс.руб.

5. Решение задачи способом двойного предпочтения. Очень удобен при решении задач вручную и может дать наилучшие результаты. В табл. 17.6 по строкам, начиная с 1-ой, ищем клетку с наименьшим стоимостным элементом и помечаем звездочкой. Затем ищем клетки с минимальными стоимостными значениями по столбцам и также помечаем звездочками. В клетки, имеющие две звездочки, помещаем максимально возможный объем работ. Затем в клетки с одной звездочкой. Оставшийся объем работ помещаем в другие, не отмеченные звездочкой, но с возможно меньшей стоимостью.

Таблица 17.6

Марка бульдозера	Затраты на выполнение единицы работы Сij по объектам Вj, р./м3				Пi, тыс. м3
	В1	В2	В3	В4
А1	20	38	51	**16/18	18
А2	32	**18/14	48	71	14
А3	19	36	**18/20	44	20
А4	**18/19	24/7	55	67	26
А5	69	28/12	36/3	*18/16	31
А6	41	56	*24/23	32	23
Vj тыс. м3	19	33	46	34	132

Суммарные затраты: Y = 2694 тыс.руб.

6. Решение задачи способом аппроксимации Фогеля. В большинстве случаев дает опорный план, самый близкий к оптимальному. При данном способе ищутся разности в каждой строке и в каждом столбце матрицы между наименьшей стоимостью и ближайшей к ней по величине. Разности по строкам записываются справа в столбце разности, по столбцам - внизу в строке разностей. Из всех разностей по строке и столбцу ищем максимальную величину числа (14) и в соответствующую клетку по строке с наименьшем стоимостным элементом (А₂ В₂) ставим max объем работ (табл. 17. 7).

Если по строке объем работ выполнен, то остальные клетки этой строки помечаются звездочкой и выводятся из дальнейших расчетов. После этого снова вычисляем разности по строкам и столбцам, не принимая во внимание стоимости, имеющие объемы работ и помеченные звездочками. Такие действия проводим до распределения всех объемов работ.

Суммарные затраты: Y = 2763 тыс.руб.

Из шести способов наилучший результат получен способами 2, 3, 4, 5, т.е. Y = 2694 тыс.р. Соответственно в клетках, где распределены объемы работ, и есть объекты, на которых должны работать бульдозеры в планируемом периоде.

После этого переходим ко второму этапу решения задачи. Здесь производится проверка на оптимальность решения или продолжается последовательное улучшение опорного плана.

Таблица 17. 7

Марка		Затраты				Пi, тыс.м3	Столбцы разностей
		В1	В2	В3	В4		1	2	3	4	5	6	7	8
А1		20/15	38/*	51/*	16/3	18	4	4	4	18	-	-	-	-
А2		32/*	18/14	48/*	71/*	14	14	-	-	-	-	-	-	-
А3		19/*	36/*	18/20	44/*	20	1	1	1	1	1	1	-	-
А4		18/4	24/19	55/3	67/*	26	6	6	6	6	6	6	6	37
А5		69/*	28/*	36/*	18/31	31	10	10	-	-	-	-	-	-
А6		41/*	56/*	24/23	32/*	23	8	8	8	17	17	-	-	-
Vj, т.м3		19	33	46	34	132
Строки разностей	1	1	6	6	2
	2	1	4	6	2
	3	1	12	6	16
	4	1	12	6	-
	5	1	12	6	-
	6	1	12	37	-
	7	18	24	-	-
	8	18	-	-	-

В качестве исходного плана принимаем одну из матриц с наименьшими затратами. Например, табл. 17.6.

1. Проверка на оптимальность решения начинается с решения системы уравнений вида

. (17.1)

При этом нужно использовать индексы i,j для клеток, на пересечении которых распределены объемы работ.

V₄ - П₁ → 16; V₂ - П₂ → 18; V₂ - П₄ → 24; V₂ - П₅ → 28;

V₄ - П₃ → 18; V₁ - П₄ → 18; V₄ - П₅ → 18; V₃ - П₅ → 36;

V₃ - П₆ → 24.

Для решения данной системы неизвестному значению, наиболее часто встречающемуся, дается произвольное значение, примем: П₅ = 0;

Тогда, решая систему уравнений, получим: V₁ = 22; V₂ =28; V₃ = 36; V₄ = 18; П₁ = 2; П₂ = 10; П₃ = 18; П₄ = 4; П₅ = 0; П₆ = 12.

2. Далее определяются значения

. (17.2)

При этом используются индексы i,j, на пересечении которых не распределены объемы работ, а значения Vj и Пi берутся из найденных выше.

Z_1.1 =V₁ – П₁ = 22 - 2 = 20, Z_1.2 =V₂ – П₁ = 28 - 2 = 26,

Z_1.3 =V₃ – П₁ = 36 - 2 = 34, Z_2.1 =V₁ – П₂ = 22 - 10 = 12 и т.д.

3. Определяем значения δij по формуле

, (17.3)

условия индексов i и j определяют по шагу 2, Сij – берётся из табл. 17.6,

Zij - по вышенайденному.

δ_1.1 = С_1.1 - Z_1.1 = 20 - 20 = 0; δ_1.2 = С_1.2 - Z_1.2 = 38 – 26 = 12;

δ_1.3 = С_1.3 - Z_1.3 = 51 – 34 = 17; δ_2.1 = С_2.1 – Z_2.1 = 32 – 12 = 20 и т.д.

Если в процессе решения δij ≥0, то исходный план оптимален, если δij<0 хотя бы в одном выражении, то данный опорный план подлежит последовательному улучшению ( смотрите лекционный материал).