Диссертация (792540), страница 17

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 17)

Здесь можно задать количество предполагаемых ТЛЦ илииспользовать ограничения на общий объем финансирования. Решение такойзадачи имеет оценочное значение, которое позволяет поставить и решатьподобныезадачинанижнихуровняхиерархии:длятерриторииэкономических округов, республик, областей. Сама задача оптимизациивыбора местоположения ТЛЦ должна обладать свойством подобия дляпостановок различного иерархического уровня. При этом решения на верхнихуровнях дают лишь теоретические результаты, а не фактические проектныерешения для построения физических ТЛЦ.В целях получения единой математической модели ниже будемрассматривать некоторую ограниченную плоскую область, на которой заданасетьпунктов(вершин),соединенныхнеоднородными(однонаправленными или двунаправленными), рисунок 2.4.дугами101Рисунок 2.4 – Пункты (вершины) и неоднородная сеть дорогПункты (вершины), расположенные в рассматриваемой ограниченнойобласти, описывают:1)промышленные объекты;2)города;3)железнодорожные станции;4)имеющиеся ТЛЦ.Дуги графа описывают сеть железных и шоссейных дорог; 1-4определяются точками (вершинами графа) с заданными координатами, i –номер вершины, (xi, yi) – декартовы координаты.

Сеть дорог – дуги графа. Дугинеоднородные. В каждой вершине i известен объем контейнеропригоднойпродукции. Обозначим её ai. Она включает как имеющиеся фактическиеобъёмы контейнерных перевозок, так и ожидаемые объёмы на некоторыйпроектный период. Величина ai отображает объём только собственно даннойвершины, без учета дополнительного объёма контейнеропереработки,который образуется, если данная вершина будет терминально-логистическимцентром.Известны «расстояния» перевозки контейнеров из точки i в точку j – cij.В простейшем случае cij – собственно расстояние в километрах. Но в реальных102задачах cij может включать все трудности, возникающие при перевозке из i в j,а именно:1)ограничения пропускной способности инфраструктуры из i в j;2)необходимость «перевалки» контейнеров – автомобиль-вагон инаоборот;3)тарифы;4)пробки на шоссейных дорогах и т.д.Все это можно учесть в отдельной методике вычисления cij.

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

Создание ТЛЦ –весьма затратный проект, поэтому требует тщательного и всестороннегообоснования [133].Предлагаетсяместонахожденияэкономико-математическаяТЛЦдлянекотороймодельтерриториисинтезаточек(область,округ,республика, страна). Решить такую задачу – это значит определить те точки i,которые и будут ТЛЦ. Пусть уже известно, сколько ТЛЦ должно быть взаданном районе – m.Тогда задача ставится так: для заданного графа вершин и ребер найтитакие вершины (всего их m), чтобы они в каком-либо оптимальном смыслепокрывали все объёмы контейнеропереработки всех узлов J ( j  1, n ).Обозначим I – множество покрывающих вершин.

Таким образом, I –подмножество вершин из J.103Существующие подходы для решения подобных задач используютметоды оптимальных покрытий [43]. Вопрос о том, что некоторый узел j будетобслуживаться ТЛЦ i, не совсем связан с геометрической близостью пунктовi и j.

Поэтому правильней ставить вопрос о мере cij, непосредственноучитывающей всё многообразие факторов удобства обслуживания j-го узла iм ТЛЦ. Это особенно проявляется при рассмотрении строительства ТЛЦвблизи крупных городов. Поэтому cij – это некоторая мера, выражающаяобщую экономическую эффективность того, что узел j обслуживается ТЛЦ i.Введем управляемые переменные xij:xi j={1, если j-й узел будет обслуживаться i-м ТЛЦ;xi j={0, в противном случае.Матрица X={xij} – это решение. Матрица X содержит n строк и nстолбцов, но так как m<n некоторые строки состоят только из нулей.Сформулируем некоторые ограничения на эти переменные и введем врассмотрение целевую функцию F ( xij ) , которая бы количественно выражаластепень общей экономической эффективности от создания сети ТЛЦ именнопри каждом решении {xij}.Каждый узел j прикрепляется только к одному ТЛЦ из I, поэтомуmxi 1ij 1,j  1, n(2.1)Если можно, чтобы узел i прикреплялся, «хотя бы к одному» ТЛЦ, тоmxi 1ij1,j  1, n(2.2)X={xij} представляет собой матрицу нулей и единиц.

Согласно (2.1),допустимой будет такая матрица, в которой в каждом столбце j будет лишьодна единица. Например,104010x ij  0001 0 1 1 00 0 0 0 10 1 0 0 0.0 0 0 0 00 0 0 0 00 0 0 0 0 Очевидно m  n . Поэтому строк, содержащих, хотя бы одну единицу,будет m  n , остальные нулевые.Таким образом, если количество ТЛЦ задано, а именно m, тоnn xm,iji 1 j  n(2.3)0,1где a 0,1 – означает0, еслиa  0a 0,1  .1, еслиa  0Видно, что матрица {xij} может изображать допустимое решение, когдаm заранее не задано. Тогда (2.3) можно убрать из рассмотрения.Общий объём переработки контейнеров в i-м ТЛЦ складывается изобъёмов тех вершин J, которые обрабатываются i-м ТЛЦ. Он определяется,какnAi   a i x ij ,i  1, m .j 1Если необходимо, чтобыna xj 1iijna xj 1iijAminAAimax, то возникают ограничения:Amax,i  1, m(2.4)Amin,i  1, m(2.5)На рисунке 2.5 приведен пример решения задачи для m=2, n=10.10500001*X 000000 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 01 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 1 0 0 0 1 1 1 10 0 0 0 0 0 0 0 0 Рисунок 2.5 – Пример решения задачи (m=2, n=10)При разработке целевой функции F ( xij ) следует отметить два подхода:интегральный и гарантирующий (минимаксный).Первый подход основан на том, что проект создания сети ТЛЦ1)нацелен на получение эффекта в целом для системы (когда не важно, что комуто одному будет плохо, лишь бы в целом был лучший результат).

Обычно всестоимостные (экономические) критерии основываются на этом. В нашемслучае в качестве такой целевой функции F ( xij ) можно взять:Fx ijnn  c ij x ij  min ,j 7,i  5,9 ,(2.6)i 1 j 1которая выражает потенциальные общие затраты в доставке ипереработке контейнеров всеми ТЛЦ для всех узлов j.Другой подход связан с тем, чтобы гарантировать величину2)максимального «расстояния»планcij, которое присутствует в плане x  будет выравнивать величины  x c  .ijijF ( xij )  max{xij cij }  min .ijТо есть,ij x  . Здесьij106Fopt ( xij )  min max{xij cij }  F0 .{ xij }(2.7)( ij )Известно, что такая целевая функция потребует более сложного методарешения.Поэтомувоспользуемсяследующимприемом.Объявимоптимальное значение F0, искомой переменной, которая добавляется кимеющимся переменным xij.

Таким образом, в задаче будет следующаясовокупность переменных{F0,xij}, то есть всего их будет n2+1.Тогда в качестве новой целевой функции возьмемF  F0  min .(2.8)С дополнительными выражениямиx c Fijiji  1, n ,,0j  1, n(2.9)Итак, в первом приближении задача выбора местоположения ТЛЦможет быть записана в виде одной из двух задач математическогопрограммирования:I.x Fnijnxi 1ijnni 1j 1n  c ij  x ij  min . 1,j  1, n x a xiij 1(2.12)0,1ijn a x(2.11)m.ijni 1(2.10)i 1 j 1ijAAmaxmin,i  1, n(2.13),i  1, n(2.14)x 0,1 .(2.15)ijII.x   F0 min .x c F0,Fijijij(2.16)i  1, nj  1, n(2.17)107nxi 1ijnni 1j 1 1, xii 1ij 1(2.19)0,1ijn a x(2.18)m.ijn a xj  1, nijAAmaxmin,i  1, n(2.20),i  1, n(2.21)x 0,1 .(2.22)ijЗаметим, что в вышеприведенной модели считается, что ТЛЦ находитсяв одном из узлов i  1, n . Возникает вопрос, а что, если ТЛЦ можно построитьв месте, где нет узла.

Это может быть выгодно, если затраты на созданиеинфраструктуры для нового ТЛЦ (нового узла) будут меньше, чемдополнительная выгода от его функционирования. Такое может быть, еслиновый узел находится между большими скоплениями узлов с большими ai.Чтобы учесть это, можно дополнять исходное множество узлов J новымивиртуальными узлами, находящимися в некоторых замечательных, с точкизрения геометрии, точках.

Например, это «центры тяжести» узлов [60].Координаты дополнительного узлаi=0 можно получить, знаякоординаты каждой i вершины (xi,yi) и объемы ai, по формулам1 nx0   ai xiV i 1,(2.23)1 ny0   ai yiV i 1,(2.24)nV   aii 1.(2.25)Получим множество узлов. При этом необходимо задать проекты новыхучастков дорог из нового узла в некоторые вершины j.

После этого можнодополнить матрицы X и С дополнительными элементами x0j, xj0 и c0j, cj0.108Решая рассмотренные задачи на новом множестве J+, получаем новыйоптимальный план {xij*+}. При этом если новые значения критерия F*+ будутменьше F*, то принимаем новое решение.Обе задачи I и II принадлежат к классу задач линейного булевапрограммирования (ЛБП). Известно, что эта задача принадлежит к такназываемым NP трудным задачам. Это означает, что сложность решенияподобных задач растет быстрее, чем любой полином от количествапеременных. У задачи I - количество переменных n2, количество строкограничений 3n+1. У задачи II - n2+1 переменных и n2+3n+1 строкограничений.Реальные расчеты необходимо делать для n порядка от 10 до 100 и более.Для количества узлов n=10 получаем:задачу I с 100 переменными и 31 ограничением,задачу II с 101 переменной и 131 ограничением.Для n=100 соответственно имеем:для I - 104 переменных и 301 ограничение,для II - 104 переменных и 10301 ограничений.Из изложенного ясно, что приведенные математические модели впринципе позволяют решать поставленную задачу на основе алгоритмоврешения задач ЛБП для небольших регионов.

Известны многочисленныеалгоритмы и компьютерные программы, решающие такие задачи [43], [44],[45]. Точные решения можно получить, например, на основе так называемогоаддитивного алгоритма при числе ограничений N<102 [87].Приближенные решения можно получить на основе «генетического»алгоритма, исследование возможностей которого дано в работах [44], [152].Анализ этих работ показывает, что возможность решения задачоптимизацииразмещенияпрограммированиядажеТЛЦбезвучетавидезадачрасположенияматематическоготочек-производствограничивается большой их сложностью, что не позволяет практическирешать такие задачи для крупных регионов и страны в целом.109Таким образом, в диссертационном исследовании были рассмотреныметоды нахождения оптимальных терминально-логистических центров наплоскости, если заданы координаты и «вес» точек. Оценочный анализ данныхметодов представлен в таблице 2.2.Таблица 2.2 - Анализ методов нахождения оптимальных «центров» на плоскостиПостановка задачиРешениеСоздание одного центра1.

Для заданных n точек найти одинРешение - точка Торичелли. Для n ≥ 5геометрический центр, сумма расстояний отзадача решается приближенно.которого до этих точек минимальна.2. Для заданных k точек найти центр, лежащийРешение нелинейного уравненияна заданной прямой, чтобы суммарноевысокой степени, приближеннымирасстояние от центра до точек былометодами.минимально.3. Для заданных n точек найти такую сетьРешение – сеть Штейнера. Для n ≥ 5дорог, чтобы общая длина дорог, соединяющая задача решается приближенноточки, была минимальной.перебором вариантов.Создание многих центров4. Задано n вершин графа, рёбра – это пути,Решение в виде задачисоединяющие вершины. Найти подмножествоматематического программирования навершин - центров (количество их k может бытьоснове переборных алгоритмов типазадано или не задано), чтобы суммарная длинаветвей и границ.

Характеристики

Список файлов диссертации