WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 9 | 10 || 12 | 13 |

i0 j, Таблица 46. Совмещенная матрица (ориентированный граф) L0, j - Эi0 j i, j Lmax L Эk k 1 2 3 4 5 k i, k 1,4,6,2 1,4,6,3 1;4 1;5(1,4,5) 1,4,6 31 1 9-36 8-16 3-3 6-18 5-25 17 2,3,1 2;3 2,3,4 2,3,4,5 2,3,4,6 49 2 11-66 6-12 9-9 12-36 11-55 17 3;1 3,4,6,2 3;4 3,4,5 3,4,6 28 3 0 5-30 9-36 3-3 6-18 5-25 14 4,6,3,1 4,6,2 4,6,3 4;5 4;6 26 4 0 10-60 6-24 5-10 3-9 2-10 21 5,2,3,1 5;2 5,2,3 5,2,3,4 5,2,3,4,6 67 5 17-102 6-24 12-24 15-15 17-85 35 6,3,1 6;2 6;3 6,3,4 6,3,4,5 30 6 0 8-48 4-16 3-6 6-6 9-27 15 (a ) = (6, 4, 2, 1, 3, 5) aT = j i, j Таблица 47. Совмещенная матрица (неориентированный граф) Li, j j L Lmax 1 2 3 4 5 k k i, k 0;0 1,4,6,2 1,4,6,3 1;4 1;5(1,4,5) 1,4,6 1 0 9 8 3 6 5 2,6,4,1 2;3 2,6,4 2,6,4,5 2;6 2 0 9 6 6 9 4 3;1 3;2 3;4 3,4,5 3;6 3 4 6 3 6 6 4;1 4,6,2 4;3 4;5 4;6 4 0 3 6 3 3 2 5;1 5,4,6,2 5,4,3 5;4 5,4,6 5 6 9 6 3 5 6,4,1 6;2 6;3 6;4 6,4,5 6 5 4 3 2 5 Если количество баз R > 1, то задача распадается на R подзадач, с одним складом каждая. При этом необходимо n пунктов так разделить на R групп, каждая из которых обеспечивается со своего r -го склада R ( r = 1, R - точка xr ), чтобы суммарная длина маршрутов со всех баз была минимальной. Формальная постановка задачи с R базами может быть представлена в виде R L, R = L0 mxin, (7.5) ( ) kr, j r=1 j j { }kr A = Ai,.. i = kr j, r =1, R, (7.6) r { }k { } n где х = (xr ) – xr – точка размещения r -й базы, обслуживающей R r r r множество пунктов r -й группы с номерами {j}k ; k – номер пункта Ak, в котором размещается r -я база; L0 r – длина кратчайшего пути от k, j r пункта Ak до пункта Aj.

r Подмножества {j}k, (r = 1, R ) являются разбиением полного множества I = {1,n}:

R R r {j}k U{j} = I, I{j} =, i r, n = n, r kr ki r =1 r =r где nr – число элементов множества {j}k.

Для получения точного решения задачи с R базами необходимо R рассмотреть все Cn возможных вариантов размещения баз (точек xr, R r = 1, R ). При каждом из этих вариантов разбиение n пунктов по группам осуществляется в следующем порядке. Последовательно, начиная с первого пункта ( j = 1), для каждого столбца совмещенной матрицы r кратчайших маршрутов пункт Aj включается в группу {j}k, r обслуживаемую r -й базой (пункт i = k ), согласно условию r r min {L0, j}= L0 r, j = 1,n k, r, {j}k, r = 1, R. (7.7) i r k, j i{k } R Условие (7.7) означает, что пункт с номером j ( Aj ) включается в обслуживание ближайшей r -й базой, расположенной в пункте Ak r.

После получения оптимального разбиения (7.7) из матрицы кратчайших R cn маршрутов берутся их длины и вычисляется сумма (7.5). Из всех вариантов, полученных таким путем, выбирается лучший, что и определяет оптимальное размещение R баз.

R При больших значениях n и R перебор Cn вариантов окажется весьма громоздким (задача NP-полная), поэтому для решения задачи размещения баз примним следующий неформальный подход: первая ( r = 1) база (точка x1) помещается в пункте i = k1 с минимальной суммарной длиной маршрутов (7.4). Из строки i = k1 выбирается несколько наименьших элементов L01, и по соответствующим им k индексам j предварительно формируется первая группа пунктов {j}1k1.

Далее вычисляются суммы длин L оставшихся маршрутов. По k уточненным суммарным длинам L определяется точка размещения xk второго склада ( r = 2). Группа {j}k формируется уже с учетом двух баз, согласно условию (7.7). Далее цикл повторяется, пока не будут размещены все R базы и сформированы R группы.

После этого проверяется возможность улучшить решение путем возможного смещения точек xr. Проиллюстрируем методику решения задачи на примере размещения двух баз на ориентированном графе (табл.

46).

Базу r = 1 следует разместить (табл. 46) в пункте A4 ( k1 = 4 ), т.к. при этом сумма длин минимальна ( L = 26). В группу k1 = 4 включаются пункты с номерами {j} = {4,5,6}4. Длины кратчайших маршрутов к ним соответственно равны {L0, j}= {0,3,2}. Сумма длин использованных маршрутов равна 0 + 3 + 2 = 5. Исправленные значения сумм записаны в нижних частях тех же клеток в правой части табл. 46. Минимальному их значению соответствует строка i = k = 3, поэтому вторая база ( r = 2) размещается в пункте A3. Согласно условию (7.7) все n пунктов последовательно, начиная с A1 ( j = 1), разбиваются на R = 1 подмножества: {j}k, {j}k ( k1 = 4, k = 3). Сохраняя запись индексов, в соответствии с (7.7) и табл. 46 имеем L (R) = {53,1,64,2,03,3,04,4,34,5,24,6}. (7.8) r k, j n r Из (7.8) для полученного размещения баз (k )= (k1,k )= (4;3) следует 1 {j}k =4 = {2,4,5,6}, {j}k =3 = {1;3}. (7.9) { 1 r =r =r Первые индексы в (7.8) указывают номера i = k пунктов размещения баз и позволяют выделить множества номеров пунктов, обслуживаемых с соответствующих баз (вторые индексы в (7.8)). На основании (7.8) и (7.9) для (7.5) имеем L(x0,2)= (6 0 + 2)+ (5 ) = 11+ 5 = 16, 1+4+ 43 1+423 4 r =1 (k1=4) r =2(k2 =3) где суммируемые элементы в табл. 46 выделены шрифтом.

Множество {j} = {4,5,6}, сформированное до введения второй базы, согласно (7.7) уточнено [см. (7.9)].

Перебор всех C6 = 15 возможных вариантов подтвердил оптимальность размещения баз в пунктах A4 и A3 (их номера в (7.9) выделены шрифтом).

Примечание. Решая R частных задач, соответствующих разбиению (7.9), можно убедиться, что перемещение базы из пункта A4 в любой из пунктов A5, A6 (табл. 46, i = 4 ) только ухудшит решение. Например, переместив базу r = 1 из A4 в A6, получим (табл. 46) L = L0;2 + L0;4 + L0;5 = 4 + 6 + 9 = 19 > 16 = L.

6 6 6 6 Рассмотренным методом получим решение для случая неориентированного графа ( R = 2 ). Базу r = 1 следует поместить в пункт A4 (табл. 47, i = k1 = 4). В начальное множество {j}4 включены почти все элементы j (кроме j = 2 ). Действительно, в каждом из столбцов j {j}длина маршрута L0, j наименьшая (исключая ноль). После уточнения сумм длин оставшихся маршрутов ( L записаны в нижних частях клеток k столбца L (табл. 47)) определяется минимальная длина L = 0. Ей k соответствует строка i = k = 2 и {j}2 = {2}.

Согласно полученному решению базы размещаются в пунктах A4 и r r A2 ({k }= {4;2}), при этом множества номеров групп {j}k обслуживаемых объектов и суммы длин маршрутов, согласно (7.7) и (7.5), равны:

L 0 r = {34;1,02;2,34;3,04;4,34;5,24;6}, {k } = {4;2}, R r k, j n {j}4 = {1,3,4,5,6}, {j}2 = {2}, (7.10) L(x,2) = (3 3 + 0 3 + 2)+ 0 = 11.

{ 1+ 442+ r =r =r Поскольку для формирования множества баз {k } использовался R неформальный сокращенный метод, то полученное решение следует попытаться улучшить методом перемещений. Такую попытку в данном случае требуется сделать для группы маршрутов, исходящих от базы r = 1, расположенной в пункте A4.

Из строки i = k1 = 4 (табл. 47) по начальным дугам маршрутов видно, что переход точки x1 возможен к пунктам {1,3,5,6}. Каждый из этих переходов дает увеличение суммы длин маршрутов:

xA4 A1 : L(x) = 0 + 0 + 6 + 3 + 6 + 4 = 19 > 11, xA4 A3 : L(x) = 5 + 0 + 0 + 3 + 6 + 4 = 18 > 11, xA4 A5 : L(x) = 3 + 6 + 3 + 0 + 0 + 2 = 14 > 11, xA4 A6 : L(x) = 3 + 4 + 3 + 0 + 3 + 0 = 13 > 11.

Перебор всех C6 = 15 вариантов размещения баз подтверждает оптимальность решения (7.10). При оптимизации размещения очередной R +1-й базы исходной информацией является вариант с размещением R баз (7.8), и к нему последовательно добавляется каждый из n - R возможных вариантов размещения R +1-й базы. Из этих вариантов выбирается лучший (с минимальной суммой длин L ).

k Для дальнейшего уменьшения объема вычислений вместо оценки и n сравнения - R вариантов в вычислительной схеме (табл. 48) использован метод перемещений при начальном размещении r = 3 базы в одном из пунктов Ai, {}= {1,2,5,6} (табл. 46, ориентированный граф).

i Таблица t № j 1 2 3 4 5 L(x, R) R L0 r (R) 1 53 64 03 04 34 24 2 k, j 1 L0, j 2 8 4 3 6 9 0 - L0 r (R +1) 3 53 46 03 04 34 06 3 k, j L0, j 4 11 0 6 9 12 11 - L0 r (R +1) 5 53 02 03 04 34 24 3 k, j Примечание. В строках 1, 3, 5 сохранены только первые индексы (номера пунктов – баз). Вторые индексы вынесены в верхнюю часть таблицы.

В первой строке табл. 48 записана исходная информация (7.8). Длины маршрутов L0, j от третьей базы ( k3 = 6) взяты из табл. 46, i = 6 (строка табл. 48). «Свертка» этих строк в соответствии с (7.7) дает улучшенный результат, записанный в строке № 3 табл. 48.

Из пункта A6 смещение базы r = 3 возможно только в пункт A2, что видно из начальных дуг маршрутов (табл. 46, строка i = 6 ). Переместив базу r = 3 из пункта A6 в пункт A2, получим улучшенное решение, записанное в строке № 5 табл. 48 («свертка» строк № 1 и 4). Элементы, изменившие свои значения в ходе «свертки» (7.7), в табл. 48 выделены шрифтом.

Дальнейшее улучшение решения смещением точки х3 из пункта Aполучить невозможно. Это следует из анализа начальных дуг маршрутов (табл. 46, строка i = 2 ).

Описанную процедуру можно выполнить без записи табл. 48, т.к.

элементы строки 1 табл. 48 выделены в табл. 46 шрифтом.

Из табл. 47 для неориентированного графа видно, что при полученном решении (7.10) для R = 2 все значащие выделенные элементы являются минимальными в своих столбцах (не считая L0,i = 0, i = 1,n ).

i Следовательно, уменьшение суммы (7.5) можно достигнуть только заменой наибольшего из выделенных элементов ( L0,1 = L0,3 = L0,5 = 3) на 4 4 ноль, путем размещения в соответствующем пункте Ai i {1,3,5} точки х3.

Таким образом будет получено три варианта решения (размещения базы r = 3):

r {k }: {4,2,1}, {4,2,3}, {4,2,5}.

Суммарная длина маршрутов при R = 3 уменьшится на 3 ед. по сравнению с решением (7.10) для R = 2 и станет равной 8 ед. Только первая база ( r = 1, A4 ) будет обслуживать несколько пунктов, другие две – по одному (по месту расположения базы).

При R = n каждая база обслуживает свой пункт и суммарная длина маршрутов равна нулю.

7.2. Учет грузопотоков и грузоподъемности транспортных средств при размещении баз В реальных условиях при размещении баз необходимо учитывать потребности по доставке грузов в различные пункты, а также грузоподъемность транспортных средств, используемых r -й базой, расположенной в пункте Ak r. Тогда задача будет состоять в таком r размещении R баз в R пунктах (вектор (k ) ), при котором суммарные R энергозатраты будут минимальны.

Дополнительной к совмещенной матрице кратчайших маршрутов информацией будут являться вектор грузов a = (a ), которые должны j n быть доставлены в каждый пункт в течение некоторого периода времени, и грузоподъемность транспортных средств, используемых r -й базой (пункт r i = k ). Грузопоток от пункта Ai к Aj будет включать в себя полезные энергозатраты ЭiПj и пассивные ЭiТ j, связанные с пробегом самого,, транспортного средства (к пункту Aj - L0, j и обратно – L0j,i ), при этом его i т r вес ai, j зависит от типа средства (от номера базы r : i = k ) и пункта доставки груза (т.е. от j ). Тогда полезные и пассивные энергозатраты от пункта Ai к A запишутся в виде j т r r ЭiП = a L0, j, ЭiТ = ai, j(L0, j + L0j,i), i {k }, j {j}k, r = 1, R,, j j i, j i R где i,1j – пассивные затраты, даны для одного рейса.

Так как груз a может во много раз превышать грузоподъемность j средства gi, j, то потребуется сделать a gi, j рейсов для перевозки всего j груза, и, следовательно, полные пассивные энергозатраты для перевозки грузов по маршруту i0 j вычисляются по формуле, a a j T ЭiТ = ЭiТ1 j = ai, j(L0, j + L0j,i)g,, j i, j gi, j i, j Tгде Эi,j – пассивные энергозатраты на одну поездку туда и обратно.

Полагая, что для межгородской транспортной сети более типичен Т случай L0, j = L0,i, а средства однотипны ( gi, j = g, ai, j = aТ, i, j ), то для i j каждого маршрута получим следующие грузопотоки:

2aТ Эi, j = ЭiПj + ЭiТ j = a L0, j 1+ = ЭiПj kТ, (7.11),, j i, g где kТ – коэффициент транспортных (пассивных) энергозатрат.

Поскольку в (7.11) множитель в скобках (коэффициент kТ ) не зависит от i, j, то он может быть опущен, что не повлияет на размещение баз.

Вычислив совмещенную матрицу i0 j i0 j,, =, (7.12) ЭiПj a L0, j, j i можно все, изложенное в подразделе 7.1, применить и для оптимального размещения баз с учетом грузопотоков и транспортных средств.

Формальная постановка обобщенной задачи размещения баз в новых условиях мало отличается от задачи (7.5), (7.6):

R Э(x, R) = a L0 min, k, j x { }k j r r r = 1 j j r r x {Ai}, т.е. k {j}k, r = 1, R, n где a – груз, подлежащий доставке в пункт Aj (j = 1,n).

j Для иллюстрации метода при R = 2 используем совмещенную матрицу (табл. 46), в правом нижнем углу каждой клетки которой записаны полезные энергозатраты ЭiП (7.12), соответствующие, j кратчайшим маршрутам i0 j. Вектор грузов a записан между табл. 46 и, табл. 47. Суммарные затраты, вычисленные по формуле n Эk = Э0, i = k = 1,n, k, j j = записаны в верхних частях клеток в столбце Эk табл. 46. Минимальные энергозатраты Э6 = 103 ед. соответствуют пункту A6(i = k1 = 6), где и размещается первая (r = 1) база. В множество обслуживаемых этой базой пунктов включаются наименьшие из элементов Э6, j, и в первую очередь те из них, которые минимальны в своих столбцах. Таким путем предварительно получена группа номеров объектов для обслуживания базой r = 1, расположенной в пункте A6 (k1 = 6):

{j}k = {2,3,4,6}.

Соответствующие суммарные энергозатраты равны:

Э6 = Э0 = 16 + 6 + 6 + 0 = 28 (табл. 5, i = k1 = 6).

6, j i{j}k Энергозатраты, необходимые для обслуживания базой k1 = оставшихся пунктов I \{j}6 = {1;5}, равны:

Э6 - Э6 = 103 - 28 = 75 (табл. 46, i = 6 ).

Аналогичным образом уточняются требуемые энергозатраты и для других строк ( k 6):

Y Эk = Эk - Эk = Эk - Э0r = Э0r, r r j ={j}k k, j jI \{j}k k, j Y где вторая сумма обозначает, что уточненное значение энергозатрат Эk может быть вычислено и непосредственно как сумма энергозатрат на обслуживание пунктов, не вошедших в множество {j}k :

Y Э6 = Э0 = 48 + 27 = 75.

j ={1;5} Из столбца Эk табл. 46 следует, что минимальные затраты соответствуют размещению базы r = 2 в пункте A1. По аналогии с (7.8) для R = 2 получаем Э, (R) = {01;1, 166;2, 66;3, 31;4, 181;5, 06;6} r k, j n откуда следуют разбиение пунктов по группам обслуживания и соответствующие им энергозатраты:

r r r {j}6=1 = {2,3,6}, {j}1 =2 = {1,4,5}, {k } = {6;1}, Э(x, R) = 22 + 21 = 43. (7.13) R Анализируя возможные смещения базы r = 1 из А6 в А3 или в А(табл. 46, строка i = 6 ) и базы r = 2 из А1 в А4 ( табл. 46, строка i = 1) методом смещений, можно убедиться, что улучшить решение невозможно.

Например, сместив базу r = 2 из А1 в А4, для нового варианта размещения r баз {k }={k1;k }= {6;4} получим (используются сроки i {6;4} табл. 46):

(R) = {486;1, 166;2, 66;3, 04;4, 94;5, 06;6}, Эk r, j r {j}6=1 = {1,2,3,6}, {j}r =2 = {4;5}, Э(x, R) = 70 + 9 = 79 > 43.

Примечание. Оптимальное размещение (7.13) баз совпало с пунктами, в которые требуется доставить наиболее тяжелые грузы (a1 = 6, a6 = 5), что логически вполне оправдано.

Для более точного учета энергозатрат при перевозках необходимо принимать во внимание коэффициент, опущенный в (7.11), но позволяющий получить некоторую дополнительную информацию, связанную с перевозками грузов. Например, если в качестве единицы измерения веса взять вес транспортного средства (т.е. aT = 1), то при g = (возможная загрузка транспортного средства в 5 раз больше веса транспортного средства) коэффициент kT в (7.11) будет равен kT = 1+ 0,4 = 1,4, т.е. пассивные энергозатраты составят 40 % от полезных энергозатрат ЭiПj (7.11). Если при прочих равных условиях вдвое, увеличить полезные энергозатраты (возвращение транспорта с полной загрузкой), то пассивные затраты снизятся до 20 %. Дальнейшее их снижение возможно только путем увеличения загрузки gi, j.

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

Необходимо разместить его в такой точке x, чтобы наиболее удаленный от точки пункт района был, насколько это возможно, ближе к точке x.

Формальная постановка задачи может быть записана в виде минимаксной задачи:

LLm(x, R) = max min, (7.14) 1 j n x, j х x G(A,M ), R =1, где L0, j – кратчайший путь от точки x до пункта Aj (j = 1,n); G(A, M ) – x граф дорожной сети.

Pages:     | 1 |   ...   | 9 | 10 || 12 | 13 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.