РАСПРЕДЕЛЕНИЕ ЗЕМЛЯНЫХ МАСС

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

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

Название транспортной рассматриваемая задача [1] получила потому, что к ней сводится оптимизация плана перевозок грузов из т пунктов отправления с запасами а₁,..., а_т в п пунктов назначения с потребностями b₁,…b_n Роль коэффициентов с_ij в целевой функции играют удельные стоимости, т.е. стоимости перевозки одной единицы груза из пункта / в пункту. Задача состоит в минимизации общей стоимости, перевозки грузов при условии, что грузы оказываются полностью вывезенными из всех пунктов отправления и потребности всех пунктов назначения оказываются полностью удовлетворенными.

Переменные в этой задаче удобно снабжать индексами i, j Если первый индекс принимает т значений, а второй - п, то общее число перемен­ных Ху (размерность задачи) равно, очевидно, тп. Сущность задачи состоит в минимизации целевой функции

при т + п ограничениях типа равенств:

Обычно предполагается дополнительное соблюдение равенства

иначе здача не будет иметь решений.

При этих условиях имеется решение сформулированной задачи минимизации, содержащее не более т + п - 1 ненулевых значений перемен­ных Ху. Мы будем называть их назначениями.

При решении транспортной задачи пользуются двумя тп матрицами - матрицей планов Р =| p_t|_j и матрицей удельных стоимостей С =| c,j|, подвергая их специальным преобразованиям. Для формирования матри-цы Р на начальном шаге делается ровно т + п - 1, назначений (некоторые из них могут быть нулевыми) с тем, чтобы, во-первых, удовлетворялись условия

(i=1,2,…m)

(j=1,2,…n)

во-вторых, чтобы выбранные (для назначений) элементы матрицы не образовывали ни одного цикла. Под циклом здесь понимается последовательность элементов матрицы l₁, l₂,…l_k+1 (k > 1), начинающихся и кончающихся одним и тем же элементом (любые ее два соседних элемента распо­ложены либо в одном столбце, либо в одной строке). Пример такого цикла (l₁, l₂, l₃, l₄, l₅, l₆) дает матрица

в которой явно выделены лишь элементы, образующие цикл. При этом элементы (l₁, l₃, l₅,) составляют так называемый нечетный полуцикл цикла (l₁, l₂, l₃, l₄, l₅, l₆) (с фиксированным началом цикла l₁), а элементы цикла l₂, l₄, l₆ - четный полуцикл.

Удовлетворяющий этим условиям начальный выбор может быть сде­лан последовательным (по строкам., а внутри строки — по столбцам) при помощи максимальных назначений, лимитируемых лишь имеющимися за­пасами и потребностями (так называемый принцип северо-западного угла). Например, для a₁ = 10, a₂ = 15, а_з = 20; b₁ = 15,b₂= 15, b₃= 10, b₄ = 5 на­чальные назначения приведены в табл. 2.1.

 

Таблица 2. 1

bj ai

 

Строки этой таблицы озаглавлены запасами <я/ в пунктах отправления, а столбцы - потребностями bj в пунктах назначения. Первое назначение в первой строке исчерпывает весь запас в первом пункте отправления, второе назначение исчерпывает остающиеся потребности первого пункта назначения и т.д. Общее число назначений (равное 6) удовлетворяет условию m+n-1 (3+4-1=6), циклы отсутствуют, так что начальную матрицу планов

 

P =

 

можно считать построенной.

Пусть матрица удельных стоимостей имеет вид:

 

C =

Жирным шрифтом в ней выделены элементы, соответствующие сделанным назначениям. Преобразования матрицы С состоят в прибавлении ко всем элементам одной и той же строки или одного и того же столбца не­которой константы (положительной или отрицательной). Целью таких пре­образований является обращение в нуль всех выделенных элементов мат­рицы (в случае, когда выделенные элементы матрицы не составляют цикла, достижение этой цели оказывается всегда возможным).

Прибавляя к строкам матрицы С числа -3, -4, -3, а к столбцам числа +1, 0, +1, -1, превратим ее в матрицу:

C₁ =

Если бы все элементы матрицы С ₁были неотрицательными, перво­начальный выбор назначений давал бы оптимальное решение. Но посколь­ку в нашем случае дело обстоит не так, то применяется процедура исправ­ления начальных назначений. Для исправления присоединяем к уже выде­ленным элементам матрицы C₁ее наибольший по абсолютной величине отрицательный элемент (в данном случае элемент С ₂₄ = -2). Если началь­ный выбор содержал точно т + п — 1 элементов, то (это нетрудно дока­зать) при таком присоединении обязательно образуется цикл из выделенн­ых элементов - в данном случае цикл (С ₂₄ = -2, С ₃₄ = -2, С ₂₂ = 0, С ₂₄).

Рассмотрим теперь соответствующий цикл

P₀ = P₂₄, P₃₄, P₃₂, P₂₂, P₂₄

в матрице планов Р и превратим его в цикл

P₂₄ +P, P₃₄-P, P₃₂+P, P₂₂-P, P₂₄+P

где р - наименьшая величина в четном полуцикле (P₃₄, P₂₂ ) цикла ро (величина р как бы сдвигается го каждого элемента четного полуцикла к следующему за ним элементу нечетного полуцикла). В нашем случае P=P₃₄=5. Производя указанное преобразование цикла и исключая из числа выделенных элементов вновь возникший нулевой элемент P₃₄-P, получим новую матрицу планов Р₁:

P₁ =

 

Здесь, как и раньше, полужирным шрифтом даны выделенные элементы. Выделяя те же элементы в матрице C₁, получаем матрицу :

=

 

Прибавляя к последнему столбцу число +2, приведем матрицу к виду:

 

C₂ =

 

с нулевыми выделенными элементами, не содержащую отрицательных элементов. Это означает, что план P₁оптимален. Суммарная стоимость перевозок S₁по этому плану равна:

S₁= 10-2 + 5-3 + 5-4 + 5-3 + 10-3 + 10-2 = 120,

в то время как суммарная стоимость перевозок S₀по начальному плану P₀ была равна

So - 10-2 + 5-3 + 10-4 + 5-3 + 10-2 + 5-4 = 130.

Как и всякая задача линейного программирования, транспортная задача может иногда иметь не один, а множество оптимальных планов. На такую си­туацию указывает наличие дополнительных (помимо выделенных) нулей в заключительной (преобразованной) матрице удельных стоимостей. Присое­диняя эти нули точно так же, как мы поступали с отрицательными элемента­ми, можно двигать вдоль возникающих циклов то или иное количество гру­зов, не нарушая при этом оптимальности плана. Например, в заключительной матрице Сг рассмотренного выше примера можно образовать цикл из нуле­вых элементов (С ₂₁, С ₂₂, С ₁₂, С _11, С ₂₁)и передвинуть в нем какую-нибудь вели­чину груза, скажем С _22.В результате получим новый план

=

с общей стоимостью перевозок

S₁ = 7-2 + 3-3 + 8-3 + 2-3 + 5-3 + 10-3 + Ю-2 = 120.

Таким образом, этот план, как и план P₁, является оптимальным.

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

Пользуясь изложенной задачей, можно находить оптимальные реше­ния распределения земляных масс при проектировании производства зем­ляных работ, выполняемых, например при возведении железнодорожного земляного полотна

Пусть заданный участок представлен продольным профилем с гра­фиком попикетных объемов (рис. 1).

Прежде всего нужно разбить продольный профиль на отдельные уча­стки ~ массивы, которые при решении задачи будут рассматриваться как поставщики (выемки) и потребители (насыпи). Желательно, каждую на­сыпь и каждую выемку, если они не очень протяженные (400...600 м), представить как массив, определив по графику попикетных объемов его объем. Если в пределах насыпи или выемки имеется несколько достаточно протяженных участков с примерно равными рабочими отметками, их вы­деляют как отдельные массивы. Однако делать это нужно очень осторожно, так как граница между массивами, как и в графике попикетных объемов, вертикальная, а технология механизированной разработки грунта подразу­мевает работу горизонтальными проходками. Учитывая местные условия и возможные ограничения, оговоренные в задании на проектирование, намечаются резервы, кавальеры, карьеры и отвалы.

При выполнении курсового проекта можно руководствоваться следующим:

- объем резерва (кавальера) равен объему соответствующей насыпи (выемки), но не больше 6000 м³ на пикет;

- объем намеченных карьеров можно принимать на порядок выше суммы объемов всех насыпей участка;

- объем всех намеченных отвалов следует принимать таким, чтобы учитывалось известное ограничение:

 

 

В рассматриваемом примере выделенные массивы поставщиков обозначены арабскими цифрами, а потребителей - арабскими цифрами со штрихом.

При построении матриц Р и С для рассматриваемого примера нужно воспользоваться данными табл. 2.2:

Таблица 2.2

 

 

Потребители Поставщики	1'	2'	3'
		12 l11	7 l12	16 l13
		10 l21	1000 зп	14 l23
		8 l31	1000 зп	0 фп
		15 l41	0 фп	0 фп

Здесь в левой стороне таблицы приведены номера и объемы постав­щиков, в верхней части - номера и объемы потребителей. В правом верхнем углу каждой выделенной клетки при возможности реальной поставки указывается дальность транспортировки – lij (l₁₁ l₁₂ l₁₃ и т.д.); в левом верхнем углу клетки указывается стоимость разработки и транспортировки грунта Cij, внизу, в середине клетки, указывается объем поставки (если она имеется).

При продольной возке грунта (из выемки в насыпь) дальность перемещения lij можно принимать как расстояние между центрами тяжести соответствующих массивов плюс 50-70 метров. Центр тяжести массива на­ходят как центр тяжести площади графика попикетных объемов рассматриваемого массива.

При поперечной возке (из резерва в насыпь или из выемки в кавальер) дальность возки грунта зависит от расстояний между въездами и съез­дами. В курсовом проекте можно пользоваться данными табл. 2.3.

Таблица 2.3

 

Средняя рабочая отметка массива, м	Расстояние между въездами и съездами, м	Дальность поперечной возки, м

 

 

Транспортировка грунта из карьера в насыпь или из выемки в отвал по существу является тоже поперечной возкой. Места расположения отва­лов и карьеров в курсовом проекте задаются или принимаются по согласо­ванию с руководителем курсового (дипломного) проектирования.

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

При нахождении оптимального варианта распределения земляных масс может оказаться, что резервы, кавальеры, карьеры и отвалы были востребованы лишь частично или совсем не востребованы. В то же время должно выполняться требование транспортной задачи

 

поэтому следует предусмотреть формальную возможность вывоза излиш­ков грунта из резервов и карьеров и заполнения кавальеров и отвалов. Та­кие поставки называются фиктивными, и в соответствующие клетки таб­лицы вносится обозначение "фп" — фиктивная (формальная) поставка. Ина­че говоря, предусматриваются формальная возможность вывоза грунта из резервов и карьеров в отвал и формальное заполнение кавальеров и отвалов из карьеров.

По графикам единичной себестоимости (см. прил.2) производится предварительный выбор машин для каждой связи ij и определяется стои­мость разработки и перемещения 1 м³ грунта выбранным типом машин для данной дальности возки lij.

В клетке таблицы с запрещенной поставкой, очевидно, нужно назна­чить заведомо большую цену перевозки - по крайней мере на два порядка выше средней реальной цены (в примере она равна 1000). В клетке с возможной фиктивной поставкой цена должна равняться нулю, тогда стоимость данной поставки

Cij =Cij∙Vij=0∙Vij=0

 

Таким образом матрица С для рассматриваемого примера будет иметь вид:

 

C=

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

В выделенном поле табл. 2.2 находят клетку с наименьшей единич­ной стоимостью Су (нулевые стоимости не учитываются), и в нее записыва­ется максимально возможная поставка В нашем случае это клетка 1,2’ с C₁₂= 7.Наибольшая поставка здесь равна 3 (в данном случае величина по­ставки ограничивается объемом потребления). Следующая самая низкая единичная стоимость в клетке 3, 1¹, где С₃₁ = 8. Здесь объем поставки огра­ничивается возможностями поставщика, и поэтому V₃₁ = 3. И так далее. После реальных поставок удовлетворяются фиктивные. Таким образом по­строили матрицу Р

:

P=

Стоимость производства работ по этому варианту распределения земляных масс - произведение матриц Р•С (функционал) - равна:

3-10 + 2-8 + 3-7 + 3-16 + 1-14 + 80-0 = 129.

Представим матрицу С в виде матрицы С\, где выделим полужирным шрифтом заполненные клетки (клетки с поставками):

 

C₁=

 

C₂=

 

Произведя соответствующие преобразования (см. с. 10-И), получим матрицу С₂, из которой видно, что полученный план не оптимален.

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

На кафедре "Строительное производство" разработана компьютерная программа (в MS DOS) решения транспортной задачи применительно к распределению земляных масс при проектировании производства земляных работ. Воспользуемся этой программой для нахождения оптимального варианта распределения.

 

Вход в задачу: TZ > start.bat Вводятся: фамилия

шифр задания

количество поставщиков (в примере 4)

количество потребителей 3

объем каждого поставщика (в сотнях м³)

объем каждого потребителя

цены по каждой связи if

При вводе данных иметь в виду:

↑- строка вверх

↓- строка вверх

PGUP (9) - страница вверх

PGDOWN (3) - страница вниз

FI ~ обнулить цену (объем).

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

Для рассматриваемого примера получено следующее решение:

 

Поставщик	Потребитель	Объем	цена

 

Стоимость оптимального варианта (функционал) составила 105 еди­ниц (2-10+3-12+2-14+3-7=105), что меньше, чем полученная для матрицы Р. При этом видим, что в клетке 3,3’ матрицы (с наибольшим нарушением оп­тимальности) предусмотрена поставка.

На основании полученных результатов расчета строится схема опти­мального распределения земляных масс, на которой указываются объемы и направления перемещения грунта. Проектируется календарный график производства земляных работ на участке (см. рис. I). При этом нужно соблюдать технологические ограничения: например, на одном массиве не мо­гут работать одновременно экскаваторные и скреперные комплекты. Более подробно вопрос о проектировании календарного графика будет рассмотрен во 2-й части методических указаний.