Задачи оптимизации в транспортных процессах на АТ: суть процесса, виды и методы оптимизации, характеристика (не менее 3) оптимизационных за

Министерство образования  и науки Р.Ф.

Федеральное государственное  образовательное бюджетное учреждение высшего профессионального образования

Курганский государственный  университет

Кафедра «Организации безопасности движения»

 

Реферат

на тему:

«Задачи оптимизации в транспортных процессах  на АТ: суть процесса, виды и методы оптимизации, характеристика (не менее 3) оптимизационных задач транспортных процессов»

 

по дисциплине «Моделирование транспортных процессов»

 

 

                                             Студент группы ТС-3681

 Попов А.В.

Преподаватель Борщенко Я. А.

 

 

Курган 2013

 

 

 

В общем смысле оптимизацией называется поиск самого лучшего  или эффективного решения. На практике чаще всего используют математический подход к оптимизации, который гласит, что оптимизационными точками являются точки максимума и/или минимума. Оптимизационные точки для конкретного  процесса или зависимости могут  быть локальными и глобальными. Сложные  процессы могут иметь несколько  локальных экстремальных точек. В этом случае можно определить глобальный минимум или максимум путем сравнения  между собой минимумов (максимумов). Методы поиска экстремальных значений могут быть разными, и эти методы чаще всего называются методами оптимизации:

1. Метод перебора(самый простой)
2. Метод нахождения 2-ой производной
3. Метод градиентов

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

А) аналитические

Б) графические (графо-аналитические)

В) численные

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

1. Если известно аналитическое выражение функции цели от параметров;
2. Если эта функция дважды дифференцируема по параметрам.[1]

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

Метод основан на том, что  каждое ограничение неравенство  отсекает в n-мерном пространстве n-мерную полуплоскость (в данной контрольной работе это двухмерное пространство (плоскость) и простая полуплоскость). Совокупность этих полуплоскостей (если ограничения совместны) образует n-мерную область допустимых решений (ОДР). Оптимальное решение достигается в одной из вершин многогранника. Для определения этой вершины необходимо построить поверхность уровня целевой функции (в контрольной или расчетно-графической работе – линию уровня). Затем, следует перемещать эту поверхность (линию) в направлении градиента до крайней точки (ОДР). [2]

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

Виды оптимизации:

1. Многокритериальная
2. Одномерная

Многокритериальная оптимизация  - процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения.

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

Перечислим некоторые из подходов к задачам со многими критериями:

- метод уступок лицо, принимающее  решения, подводится к выбору  решения путем постепенного ослабления  первоначальных требований, как  правило, одновременно невыполнимых;

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

- метод свертывания лицо, принимающее  решения, сводит многокритериальную  задачу к задаче с одним  критерием;

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

- метод анализа иерархий на  основании суждений экспертов  оценивается вклад в общую  оценку каждого критерия.

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

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

В многокритериальной задаче оптимизации  сравнение решений по предпочтительности осуществляется не непосредственно, а  при помощи заданных на X числовых функций f₁, f₂, … f_m, называемых критериями. Предполагается, что m ?2: при m = 1 задача оптимизации является однокритериальной.

В задачах принятия индивидуальных решений критерии служат для выражения  «интенсивности» существенных свойств (признаков) решений. В задачах принятия групповых решений критерий U характеризует  «качество» (или предпочтительность) решений с точки зрения индивида i, входящего в группу {1, 2,…, m}.

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

Однокритериальная (однофакторная) оптимизация.

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

Общая постановка задачи одномерной оптимизации заключается в следующем: дана некоторая функция f(x) от одной переменной x, необходимо определить такое значение x*, при котором функция f(x) принимает экстремальное значение. Под ним обычно понимают минимальное или максимальное значения. В общем случае функция может иметь одну или несколько экстремальных точек. Нахождение этих точек с заданной точностью можно разбить на два этапа. Сначала экстремальные точки отделяют, т.е. определяются отрезки, которые содержат по одной экстремальной точке, а затем уточняют до требуемой точности .

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

Для решения задачи минимизации  функции f(x) на отрезке [a, b] на практике, как правило, применяют приближенные методы. Они позволяют найти решения этой задачи с необходимой точностью в результате определения конечного числа значений функции f(x) и ее производных в некоторых точках отрезка [a, b]. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации.

Большим достоинством прямых методов  является то, что от целевой функции  не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем основаны алгоритмы прямых методов минимизации, это возможность  определения значений f(x) в заданных точках .

Среди задач математического программирования самыми простыми и наиболее хорошо изученными являются так называемые задачи линейного программирования (линейной оптимизации).

Рассмотрим данный тип задач. Для  них характерен тот факт, что целевая  функция линейно зависит от , а также то, что ограничения, накладываемые на независимые переменные, имеют вид линейных равенств или неравенств относительно этих переменных.

Такие задачи часто встречаются  на практике - например, при решении  проблем, связанных с распределением ресурсов, планированием производства, организацией работы транспорта и т.д. [3]

 

Задачи оптимизации:

Выделим 2 наиболее важных задачи оптимизации в транспортном процессе:

1. Выбор оптимального маршрута
2. Выбор оптимального типа ПС (подвижного состава)

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

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

 

Рис. 2.12

В задаче имеется ограничение - двигаться по изображенным на схеме  маршрутам можно только слева  на право, т.е. попав, например, в пункт 7, мы имеем право переместиться только в пункт 10 и не можем возвратиться обратно в 5-й или 6-й. Эта особенность транспортной сети дает право отнести каждый из десяти пунктов к одному из поясов. Будем считать, что пункт принадлежит k-му поясу, если из него попасть в конечный ровно за k шагов, т.е. с заездом ровно в (k - 1)-й промежуточный пункт. Таким образом, пункты 7, 8 и 9 принадлежат к первому поясу, 5 и 6 - ко второму, 2, 3 и 4 - к третьему и 1 - к четвертому. Тогда на k-м шаге будем находить оптимальные маршруты перевозки груза из пунктов k-го пояса до конечного пункта. Оптимизацию будем производить с конца процесса, и потому, дойдя до k-го шага, неизвестно, в каком из пунктов k-го пояса окажется груз, перевозимый из первого пункта.

Введем обозначения:  
k - номер шага (k = 1, 2,3,4);  
i - пункт, из которого осуществляются перевозки (i = 1,2,..., 9);  
j - пункт, в который доставляется груз (j = 2,3,.., 10);  
С_{i, j} - стоимость перевозки груза из пункта i в пункт j.  
F_k (i) - минимальные затраты на перевозку груза на k-м шаге решения задачи из пункта i до конечного пункта.

Очевидно, что минимум  затрат на перевозку груза из пунктов k-го пояса до пункта 10 будет зависеть от того, в каком пункте этого пояса мы оказались. Номер i пункта, принадлежащего k-му поясу, будет являться переменной состояния системы на k-м шаге. Поскольку оптимизация осуществляется с конца процесса, то, находясь в некотором пункте i k-го пояса, принимается решение о перемещении груза в один из пунктов (k – 1)-го пояса, а направление дальнейшего движения известно из предыдущих шагов. Номер j пункта (k - 1)-го пояса будет переменной управления на k-м шаге.

Для первого шага управления (k - 1) функция Беллмана представляет собой минимальные затраты на перевозку груза из пунктов 1-го пояса в конечный пункт, т.е. F₁(i) = С_{i  10}. Для последующих шагов затраты складываются из двух слагаемых - стоимости перевозки груза С_{i, j} из пункта i k-го пояса в пункт j (k - 1)-го пояса и минимально возможных затрат на перевозку из пункта j до конечного пункта, т.е. - F_{k - 1} (i). Таким образом, функциональное уравнение Беллмана будет иметь вид

Минимум затрат достигается  на некотором значении j*, которое является оптимальным направлением движения из пункта i в конечный пункт. На четвертом шаге попадаем на 4-й пояс и состояние системы становится определенным i = 1. Функция F₄(1) представляет собой минимально возможные затраты по перемещению груза из 1-го пункта в 10-й. Оптимальный маршрут определяется в результате анализа всех шагов в обратном порядке, а выбор некоторого управления j на k-м шаге приводит к тому, что состояние системы на (k - 1)-м шаге становится определенным. [4]