Delist.ru

Повышение эффективности эксплуатации машин в строительстве путем выбора оптимальных вариантов выполнения механизированных работ (29.05.2007)

Автор: Двизов Денис Александрович

– начальные состояния для

последнего этапа;

– начальные состояния для

предпоследнего этапа; и т.д;

– начальное состояние для

– начальные состояния для

последнего этапа;

– начальные состояния для

предпоследнего этапа; и т.д.

В пятой главе «Выбор оптимальной трассы строительства магистральных сооружений методом динамического программирования» показана общая схема решения рассматриваемых задач и приведён конкретный пример для случая, когда строительство ведётся в одном из двух взаимно перпендикулярных направлений (H и L).

Постановка задачи. Требуется проложить трубопровод из начального пункта S0 в конечный пункт SК (рис. 3). Нетрудно убедиться в том, что существует множество вариантов траектории строительства, каждый из которых требует определённых затрат средств. На рисунке 3 показаны некоторые из них.

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

Рассмотрим схему решения задачи в общем виде.

Разобьём трассу строительства на отдельные участки (этапы). Будем считать, что на каждом этапе строить можно либо в направлении Н, либо в направлении L (рис.4).

Число этапов в направлении Н примем равным nН, а в направлении L – nL. Тогда общее число этапов будет n= nН + nL.

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

Рисунок 3 – Возможные траектории строительства трубопровода

Рисунок 4 – Разбивка трассы трубопровода на этапы и оптимальная

траектория строительства

Затраты средств на строительство трубопровода на каждом этапе обозначим соответственно:

C(1)1, C(1)2 – затраты средств на первом этапе;

C(2)1, C(2)2, C(2)3, C(2)4 – затраты средств на втором этапе; … … … … …

C(n-1)1, C(n-1)2, C(n-1)3, C(n-1)4 – затраты средств на предпоследнем (n-1)-м этапе;

C(n)1, C(n)2 – затраты средств на последнем n-м этапе.

Согласно требованиям метода динамического программирования решение задачи начнём с последнего n-ого этапа. На начало этого этапа можем находиться либо в пункте В(n)1, либо в В(n)2 (рис.4). Если окажемся в пункте В(n)1, то мы должны двигаться в конечный пункт SК в направлении L и тратить на строительство F(n)1=C(n)1 единиц средств. Если же окажемся в пункте В(n)2, то надо двигаться в направлении Н, а затраты средств на строительство в этом случае составят F(n)2=C(n)2 единиц. Эти направления на рисунке 4 отмечены стрелками.

Затем рассматриваем предпоследний (n-1)-й этап. На начало этого этапа можем находиться в одном из пунктов: В(n-1)1, В(n-1)2 или В(n-1)3.

Если окажемся в пункте В(n-1)1, то выбора нет, надо перемещаться в направлении L и тратить C(n-1)1 единиц средств. А затраты средств за два последних этапа составят F(n-1)1=C(n-1)1+C(n)1 единиц.

Если окажемся в пункте В(n-1)2, то можем двигаться либо в направлении Н, либо в направлении L. В этом случае надо выбрать то направление, которое требует меньше средств. Это направление выбираем из условия:

Предположим, что меньшей окажется верхняя величина выражения (8). Тогда выбираем направление Н.

Если окажемся в пункте В(n-1)3, то выбора нет. Надо двигаться в направлении Н, затрачивая на два этапа F(n-1)3=C(n-1)4+F(n)2 единиц

Выбранные для этого этапа направления строительства на рисунке 4 указаны стрелками.

Таким образом, мы нашли так называемые условные оптимальные решения для двух последних этапов.

Аналогично определяем условные оптимальные решения для предшествующих этапов, т.е. для (n-2)-го, (n-3)-го и т.д. этапов.

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

Затем, «пробегая» процесс решения в обратном направлении, т.е. от первого до последнего этапа, по стрелкам находим оптимальную траекторию. На рисунке 4 она выделена жирной линией. При строительстве по такой траектории затраты средств на строительство будут минимальными и равны

Мы рассмотрели задачу при условии, что строительство трубопровода можно вести только в двух взаимоперпендикулярных направлениях: Н или L. Однако возможны более сложные варианты, когда строительство может вестись в одном из трёх направлений – кроме двух указанных выше, ещё и по диагонали.

Методика решения таких задач изложена в главах 6 и 7.

В шестой главе «Выбор оптимального варианта строительства магистральных сооружений первым способом» рассмотрена схема решения задачи, как в общем виде, так и на примере, при трёх направлениях

строительства – H, D и L.

В диссертации изложены общий подход и схема решения задач этим способом. Здесь приведём лишь конкретный пример.

загрузка...