Применение методов динамического программирования
(принципа оптимальности Р. Беллмана)
при календарном планировании в строительстве
Выбрать такую очередность включения объектов в строительный поток, чтобы длина суммарного пути перебазирования оказалась минимальной.
Исходные данные – расстояние между пунктами, км
Индекс пунктов (объектов) | А0 | А1 | А2 | А3 | А4 |
А0 | 0 | 20 | 5 | 10 | 40 |
А1 | 20 | 0 | 10 | 25 | 30 |
А2 | 5 | 10 | 0 | 35 | 15 |
А3 | 10 | 25 | 35 | 0 | 50 |
А4 | 40 | 30 | 15 | 50 | 0 |
Составим таблицу вариантов, состоящих лишь из трех участков перебазирования. Сгруппируем эти варианты по одинаковым объектам, стоящим на последнем месте.
Вариант | Суммарное расстояние, км | Вариант | Суммарное расстояние, км | |
А0 А2 А3 А1 А0 А3 А2 А1 | 5 + 35 + 25 = 65 10 + 35 + 25 = 70 | А0 А1 А2 А3 А0 А2 А1 А3 | 20 + 10 + 35 = 65 5 + 10 + 25 = 40 | |
А0 А2 А4 А1 А0 А4 А2 А1 | 5 + 15 + 30 = 50 40 + 15 + 10 = 65 | А0 А1 А4 А3 А0 А4 А1 А3 | 20 + 30 + 50 = 100 40 + 30 + 25 = 95 | |
А0 А3 А4 А1 А0 А4 А3 А1 | 10 + 50 + 30 = 90 40 + 50 + 25 = 115 | А0 А2 А4 А3 А0 А4 А2 А3 | 5 + 15 + 50 = 70 40 + 15 + 35 = 90 | |
А0 А1 А3 А2 А0 А3 А1 А2 | 20 + 25 + 35 = 80 10 + 25 + 10 = 45 | А0 А1 А2 А4 А0 А2 А1 А4 | 20 + 10 + 15 = 45 5 + 10 + 30 = 45 | |
А0 А1 А4 А2 А0 А4 А1 А2 | 20 + 30 + 15 = 65 40 + 30 + 10 = 80 | А0 А1 А3 А4 А0 А3 А1 А4 | 20 + 25 + 50 = 95 10 + 25 + 30 = 65 | |
А0 А3 А4 А2 А0 А4 А3 А2 | 10 + 50 + 15 = 75 40 + 50 + 35 = 125 | А0 А2 А3 А4 А0 А3 А2 А4 | 5 + 35 + 50 = 90 10 + 35 + 15 = 60 |
Из каждой пары вариантов выберем наиболее перспективные (с меньшим значением). Затем развиваем и сопоставляем лишь перспективные варианты.
|
|
Вариант | Суммарное расстояние, км | Вариант | Суммарное расстояние, км | |
А0 А2 А3 А1 А4 А0 А2 А4 А1 А3 А0 А3 А4 А1 А2 А0 А3 А1 А2 А4 А0 А1 А4 А2 А3 А0 А3 А4 А2 А1 | 65 + 30 = 95 50 + 25 = 75 90 + 10 = 100 45 + 15 = 60 65 + 35 = 110 75 + 10 = 85 | А0 А2 А1 А3 А4 А0 А4 А1 А3 А2 А0 А2 А4 А3 А1 А0 А2 А1 А4 А3 А0 А3 А1 А4 А2 А0 А3 А2 А4 А1 | 40 + 50 = 90 95 + 35 = 130 70 + 25 = 95 45 + 50 = 95 65 + 15 = 80 60 + 30 = 90 |
Составляем таблицу, в которую внесем перспективные варианты из предыдущей таблицы и добавим к каждому из них А0 (возвращение мехколонны на исходную базу).
Вариант | Суммарное расстояние, км |
А0 А2 А4 А1 А3 А0 А0 А3 А1 А2 А4 А0 А0 А3 А4 А2 А1 А0 А0 А3 А1 А4 А2 А0 | 75 + 10 = 85 60 + 40 = 100 85 + 20 = 105 80 + 5 = 85 |
Таким образом, устанавливаем, что есть два равноценных оптимальных варианта последовательности строительства объектов.
Задание №4
Оптимизация очередности строительства объектов
В неритмичных потоках
Определить оптимальную очередность строительства нескольких объектов, при которой достигается минимальная общая продолжительность строительства, а также величину общей продолжительности строительства при исходной и оптимальной очередности строительства объектов.
|
|
Выделяем поток №3 как поток наибольшей продолжительности. Затем по каждому объекту находим общее рабочее время, предшествующее потоку наибольшей продолжительности и общее рабочее время, последующее за потоком наибольшей продолжительности.
В третью строку под матрицей записываем со своим знаком разницу между продолжительностью работы на данном объекте последней и первой бригад.
На основе данных дополнительных строк устанавливается рациональная очередность строительства объектов из следующих соображений:
а) на первом месте располагается объект с наибольшим значением Σапос. Остальные объекты располагаются так, чтобы Σапр постепенно возрастало, а Σапос снижалась к концу матрицы;
б) на первом месте располагается объект с наибольшим значением (а m - а1), на последнем – с минимальным значением (а m - а1); остальные объекты располагаются так, чтобы (а m - а1) изменялось постепенно от максимального значения к минимальному.
Принятая очередность строительства объектов по п. а:
Принятая очередность строительства объектов по п. б:
Найдем общую продолжительность строительства комплекса:
а) при исходной очередности объектов
|
|
Т1 = (8 + 8 + 5 + 0 + 4) + (6 + 5 + 4) + (5 + 4) = 49;
б) при очередности объектов 5-2-1-4-3
Т2 = (4 + 8 + 8 + 0 + 5) + (5 + 2 + 0) + (2 + 0) = 34;
в) при очередности объектов 4-5-3-2-1
Т3 = (0 + 4 + 5 + 8 + 8) + (2 + 1 + 9) + (1 + 9) = 47.
Наименьшую продолжительность имеет очередность объектов 5-2-1-4-3.
Задание №5
Дата добавления: 2019-07-15; просмотров: 99; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!