Умовна нумерація груп вагонів

Застосування умовної нумерації груп вагонів дозволяє виявити початкову упорядкованість состава та скоротити обсяг роботи з формування. Так, проаналізувавши состав із приклада видно, що состав частково вже є упорядкованим, тобто одиниці знаходяться перед двійками, трійки перед четвірками, п'ятірки перед шістками. Тому, змінивши нумерацію груп на умовну, можна скоротити обсяг роботи з формування.

Привласнення умовних номерів зручно виконувати в таблиці (див. табл. 1.3) за наступним алгоритмом:

1. Кожному вагону надати порядковий номер 0, 1, 2...;

2. Відсортувати состав;

3. Виділити зростаючі групи порядкових номерів;

4. Привласнити умовні номери кожній зростаючій групі (0, 1, 2, ...).

Таблиця 1.3

Привласнення умовних номерів

Вихідний состав
Порядкові номери
Відсортований состав
Порядкові номери
Умовні номери груп

Відсортуємо состав розподільним методом відповідно до умовних номерів груп (групи розташувати по зростанню)

Номер групи (призначення)	Умовний номер групи	Код
1, 2
3, 4
5, 6

Як видно, на останньому етапі замість збирання трьох колій у разі використання умовної нумерації можна виконувати збирання з двох колій.

Порівняння комбінаторного та розподільного методу показує, що комбінаторний має перевагу у разі малої кількості колій (2, 3) через відсутність збирання вагонів. Якщо кількість груп перевершує кількість колій незначно, то краще використовувати розподільний метод.

Лекція № 2.
Розподільна задача лінійного програмування і її використання для оптимізації технологічних процесів залізничних станцій

2.1. ЗАДАЧА О ЗАГРУЗКЕ

Задача ставится следующим образом.

Имеется n штучных грузов каждый i-й весом q_i ед. (i= 1, 2,..., ..., n). Грузы необходимо поместить на автомобили: грузоподъем­ность отдельного автомобиля установлена в Q ед. (max q_{i £} Q). Требуется найти такое распределение грузов по автомобилям, которое требовало бы минимального числа автомобилей.

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

Один из эффективных способов решения этой задачи состоит в следующем [36]. Любым способом определяются нижняя т и верхняя `т границы решения так, что искомое значение т числа автомобилей должно заведомо быть в пределах между этими границами m£m£m.

 

Затем выбирается промежуточное значение числа автомобилей. Предположим,

m =entier[(m + m)/2], (2.13)

для которого ищется допустимая загрузка. Если таковая нахо­дится, то т становится верхней границей, иначе (т+1) становит­ся нижней границей. Затем по (2.13) отыскивается новое значе­ние т и делается следующая попытка распределения грузов и так до тех пор, пока границы не совпадут, указывая на решение задачи.

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

Способ отыскания такого распределения поясним на примере, взятом из работы [2].

Пусть имеются грузы весом по 120; 120; 222; 222; 240; 240; 180; 180; 180 и 180 ед. и автомобили грузоподъемностью 480 ед. Попытаемся определить минимальное число автомобилей для пе­ревозки данных грузов. Общая масса груза составляет 1884 ед. Поэтому, как минимум, требуются четыре автомобиля, но, безус­ловно, достаточно 10 автомобилей (по одному грузу на каждый).

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

Нужно испытывать различные способы загрузки отдельных автомобилей. Формально способом загрузки или просто загруз­кой назовем набор, состоящий из номеров грузов, предназначен­ных к погрузке на данный автомобиль. Если суммарная масса груза, предназначенного к погрузке, превосходит грузоподъем­ность автомобиля (случай I), то соответствующую загрузку на­зовем недопустимой, в противном случае — допустимой. Приме­рами допустимых загрузок являются: (1), (1; 2; 3), но не (1; 2; 3; 4). Допустимое распределение груза представляет собой сово­купность допустимых загрузок, при которой каждый груз вклю­чен в некоторую загрузку.

Будем рассматривать так называемое лексикографическое упорядочение загрузок: одна загрузка в этом порядке предшест­вует другой, если при одновременном просмотре номеров (ком­понент) грузов от начала этих загрузок в первой паре неравных номеров грузов меньшим будет номер из первой загрузки, либо первая загрузка короче второй и номера всех ее грузов равны первым номерам второй загрузки. Например загрузка (1; 2) предшествует (1; 3), а (1; 3) предшествует (1; 3; 2).

Так как количество загрузок является хотя и большим, но ог­раниченным числом, то все загрузки можно пронумеровать. Для проверки существования допустимого распределения груза на т автомобилей можно представить себе следующий процесс. Будем выбирать все возможные допустимые загрузки для первого ав­томобиля. Этот перебор характеризует собой внешний цикл (цикл первого уровня). После выбора некоторой загрузки перечень гру­за уменьшается. Весь оставшийся груз (его будем называть сво­бодным) порождает новое множество допустимых загрузок — множество второго уровня. Оно является подмножеством исход­ного множества первого уровня. Выбор загрузок для первого ав­томобиля порождает различные множества на втором уровне.

Для каждого множества второго уровня будем перебирать под­ряд все его элементы, составляя множество третьего уровня. Этот перебор характеризует цикл второго уровня (внутренний). И так далее. Такой процесс представляет собой полный перебор ва­риантов. Более того, многие варианты встречаются по несколько раз. Например, распределения груза, содержащего эквивалент­ные загрузки, отличающиеся только порядком включения груза, но не составом его. Примером эквивалентных загрузок являются загрузки (1; 3; 2) и (1; 2; 3). Чтобы избежать их рассмотрения, будет считать загрузку недопустимой, если груз с большим номе­ром включен в нее раньше, чем груз с меньшим номером (слу­чай 2). Количество вариантов при этом сильно уменьшается (на последнем уровне, например, сохраняется всего один вариант), но остается все еще слишком большим. Далее приведем еще не­сколько соображений, позволяющих сократить количество вари­антов до приемлемого.

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

Можно ограничить просмотр загрузок и сверху. Если загрузка на некотором уровне имеет первой компонентой число S и в спис­ке свободных грузов есть груз с номером, меньшим чем S (слу­чай 4), то этот груз не может быть включен в данную загрузку. Он не может быть включен и ни в одну из последующих загру­зок. Если он включен в некоторую загрузку на уровне с большим номером, то последняя загрузка имеет первой своей компонен­той число, меньшее S, и поэтому предшествует загрузке рассмат­риваемого уровня, что считается невозможным (случай 3). Если имеется груз, который не может быть включен ни в одну из за­грузок на данном и всех последующих уровнях, то бессмысленно перебирать варианты, при которых сохраняются загрузки на предшествующих уровнях.

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

Далее будем считать, что неполные загрузки (случай 5) счи­таются недопустимыми. О допустимости или недопустимости за­грузки следует говорить, имея в виду определенный список сво­бодного груза.

Выбранное количество т автомобилей обладает суммарной грузоподъемностью Q_m ед. Общая масса груза составляет

ед. Имеется запас грузоподъемности Q_m –

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

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

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

До описываемого примера сделано несколько шагов, послед­ний из которых дал переход на уровень k. Это значит, что для (k–1) автомобилей найдены некоторые допустимые загрузки. Если остался один автомобиль (k = m), то неотрицательный запас гарантирует существование для этого автомобиля допусти­мой загрузки. При этом итерация заканчивается получением рас­пределения груза. Если же осталось более одного автомобиля (k < m), то определяем очередную загрузку для k-ro автомобиля, при обнаружении которой очередной шаг заканчивается. Новый шаг будет относиться к следующему уровню.

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

Когда испытаны все допустимые загрузки для первого уров­ня, итерация заканчивается и мы устанавливаем, что для m авто­мобилей допустимого распределения груза не существует.

Теперь вернемся к примеру и рассмотрим, каким образом для определенного уровня формируется очередная допустимая за­грузка. Считая, что грузу одинаковой массы присваивается один и тот же номер (случай 7), имеем по два груза с номерами 1; 2; 3 и четыре груза с номером 4. Требуется отыскать допустимое рас­пределение этого груза при m = 4 или установить, что такого рас­пределения нет.

Суммарная грузоподъемность четырех автомобилей составля­ет 1920 ед. (4-480). Общая масса груза составляет 1884 ед. Име­ем запас, равный 36 ед.

Первой испытываемой загрузкой для первого уровня являет­ся загрузка (1), но она не является полной (случай 5). Следу­ющей является загрузка (1; 1), но и она неполная. Далее идет загрузка (1; 1; 2), она полная. Ее недогруз равен 18, что не пре­вышает запаса (18<36). Эта загрузка принимается. Остается запас 18. Первый шаг закончен.

Второй шаг относится ко второму уровню. Из списка свобод­ного груза исчезли оба первые и один второй груз. На втором шаге аналогично определяется (как будто решается новая зада­ча) допустимая загрузка (2; 3). Ее недогруз равен 18.

Поэтому перед третьим шагом, относящимся к третьему уров­ню, имеется запас 0. Список свободного груза следующий: 3; 4; 4; 4; 4. Первой полной загрузкой является загрузка (3; 4). Но ее не­догруз (60) превышает запас (случай 6). Поэтому она недопу­стима. Если бы имелся в списке свободного груза груз с номе­ром 5, то лексикографически следующей была бы загрузка (3; 5). Поскольку такого груза нет, то следующей является загрузка (4). Кроме того, что эта последняя загрузка неполная, она остав­ляет в числе свободных груз с номером 3, меньшим, чем номер, груза, который в нее включен первым (3<4 — случай 4). Как от­мечалось, бессмысленно перебирать варианты дальше, сохраняя загрузки на предыдущих уровнях. Надо вернуться к предыдуще­му (второму) уровню и испытывать для него следующий вари­ант.

Таким образом, четвертый шаг будет относиться ко второму уровню. Вместо принятой ранее на этом уровне загрузки (2; 3) надо будет найти следующую за ней допустимую загрузку. Спи­сок свободного груза: 2; 3; 3; 4; 4; 4; 4. Запас равен 18. Следу­ющей испытываемой загрузкой является загрузка (2; 4), посколь­ку пополнять (2; 3) не имеет смысла: если она была принята раньше, значит она полная. Загрузка (2; 4) тоже полная, но она имеет большой недогруз (78>18). Она недопустима. Следующей за ней является загрузка (3), которая оставляет свободный груз-с номером 2. Этот случай уже рассмотрен. Он указывает, что чет­вертый шаг закончен.

Следует перейти к предыдущему (первому) уровню. При этом, список свободного груза восстанавливается до исходного. Запас принимает исходное значение — 36. Следующей допустимой за­грузкой на первом уровне является загрузка (1; 1; 3).

Еще на нескольких шагах не возникает новых ситуаций. На шестом шаге принимается загрузка (2; 2) для второго уровня. На седьмом шаге устанавливаются отсутствие допустимых загрузок: для третьего уровня и необходимость возврата на второй уровень. На восьмом шаге принимается новая загрузка для второго уров­ня— (2; 3). А на девятом и десятом шагах вновь устанавливает­ся отсутствие допустимых загрузок последовательно для третьего и второго уровней.

На 11-м шаге переходим к первому уровню, где список свобод­ного груза совпадает с исходным и запас равен 36. Требуется най­ти очередную допустимую загрузку, следующую за (1; 1; 3). Ис­пытывая загрузку (1; 1; 4), устанавливаем, что ее недогруз (60) превышает запас. Следующей испытываем загрузку (1; 2). Она не является полной, но и не может быть пополнена без наруше­ния условия об упорядоченности компонент загрузки. Пополне­ние может произойти включением в нее груза с номером 1. За­грузка (1; 2; 1) лексикографически следует за загрузкой (1; 2). Однако она считается недопустимой. Эквивалентный ей допусти­мый вариант — загрузка (1; 1; 2) —предшествует загрузке (1; 2) и уже был рассмотрен. То же самое выясняется для следующей за (1; 2) испытываемой загрузки (1; 3). Она неполная и не мо­жет быть пополнена. Далее следует загрузка (1; 4). Она непол­ная, но может быть пополнена. Загрузка (1; 4; 4) является до­пустимой. Ее недогруз 0.

12-й шаг связан со вторым уровнем, где список свободного груза: 1; 2; 2; 3; 3; 4; 4; запас — 36. В этой ситуации первой за­грузкой является (1). Ее пополнением — загрузка (1; 2), которая теперь является полной. Но начинать просмотр загрузок следует не с них (случай 3), а с загрузки, принятой для предыдущего (первого) уровня— (1; 4; 4). Последняя и на этом уровне оказы­вается допустимой. Шаг закончен.

13-й шаг (третий уровень) оказывается последним. На нем обнаруживается допустимая загрузка (2; 2), т. е. происходит от­сылка к четвертому (последнему) уровню. Отсылка к последне­му уровню означает получение допустимого распределения. Для оставшегося свободного груза автоматически существует допу­стимая загрузка (3; 3). Итерация закончена.

Она дает m = m = 4. Следовательно, задача решена. Получен оптимальный план.

Весь проделанный ход вычислений для определения допусти­мого распределения груза при m = 4 приведен в табл. 2.14.

 

 

Таблица 2.14

 

Запас, ед.	Шаг	Уровень	Количество сво­бодного груза вида	Испытание	Номера грузов	Масса загрузки, ед.	Недогруз, ед.	Примечание
										–	Случай 5
								1,1	120 + 120		» 5
								1,1,2	120 + 120 +222		Принимается
			—								Случай 5
								2,3	222 + 240		Принимается
			—	—							Случай 5
								3,4	240 + 180		» 6
											» 4
			—					2,4	222 + 180		» 6
											» 4
								1,1,3	120 + 120 + 240		Принимается
			- —								Случай 5
								2,2	222 + 222		Принимается
			—	—							Случай 5
								3,4	240 + 180		» 6
											» 4
36 18	8 9	2 3	— —	2 1	—	4 4	1 1	2,3 2,4	222 + 240 222 + 180	18 78	Принимается Случай 6
			—					2,4	222 + 180		» 6
								1,1,4	120 + 120 + 180		» 6
								1,2	120 + 222		» 5
								1,3	120 + 240		» 5
								1,4	120 + 180		» 5
								1,4,4 1,4,4	120 + 180 + 180 120 + 180 + 180	0 0	Принимается »
			—			—					Случай 5
—	—	—	—	—	—	—		2,2	222 + 222 -		Принимается
			—	—		—	—	3,3	—	—	Принимается
											без испытаний

 

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

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

Для приведенного примера оба упорядочения оказываются удачными. План, строящийся

для определения т, дает т = 4 и оказывается оптимальным.