Основы математического моделирования транспортных процессов и логистика

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

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

Основная задача математического моделирования – выделение законов в природе, обществе и технике и запись их на языке математики.
Например: Зависимость между массой тела m, действующей на него силой F и ускорением его движения а записывается в форме 2-го закона Ньютона: F = m⋅ a;
Зависимость между напряжением в электрической цепи U, ее сопротивлением R и силой тока I записывается в виде закона Ома: I = U/R.
Математической моделью некоторого объекта, процесса или явления будем называть запись его свойств на формальном языке с целью получения нового знания (свойств) об изучаемом процессе путем применения формальных методов.
Альтернативой формальному (математическому) подходу является экспериментальный подход. К его недостаткам можно отнести:
высокая стоимость подготовки и проведения экспериментов;
получение частного знания (знания о конкретном объекте исследования, а не о классе объектов).
Цели и задачи математического моделирования

Классификация математических моделей

Классификация математических моделей
Все математические модели по использованному формальному языку можно разбить на аналитические и имитационные. Аналитические – модели, в которых используется стандартный математический язык. Имитационные – модели, в которых использован специальный язык моделирования или универсальный язык программирования.
Аналитические модели могут быть записаны в виде формул или уравнений. Если какой-либо процесс не может быть описан в виде аналитической модели, его описывают с помощью специального алгоритма или программы. Такая модель является имитационной.

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

Геометрическое представление математических моделей
Геометрически математическая модель может быть представлена как некоторая поверхность отклика, соответствующая расположению точек W = W(x) в k-мерном факторном пространстве Х. Область, в которой определена поверхность отклика, называется областью определения Х*.
Наглядно можно представить себе только одномерную и двухмерную поверхности отклика, причем в последнем случае удобно пользоваться топографическим способом изображения рельефа поверхности с помощью линий уровня (изолиний), построенных в двумерном факторном пространстве Х.

Основные этапы математического моделирования
1) Построение модели. На этом этапе задается некоторый «нематематический» объект — явление природы, конструкция, экономический план, производственный процесс и т. д. При этом, как правило, четкое описание ситуации затруднено. Сначала выявляются основные особенности явления и связи между ними на качественном уровне. Затем найденные качественные зависимости формулируются на языке математики, то есть строится математическая модель. Это самая трудная стадия моделирования.
2) Решение математической задачи, к которой приводит модель. На этом этапе большое внимание уделяется разработке алгоритмов и численных методов решения задачи на ЭВМ, при помощи которых результат может быть найден с необходимой точностью и за допустимое время.

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

Математические модели аналитического типа
Простейшие аналитические модели могут быть заданы явно в виде функции одной или нескольких переменных.
Обычно в виде функций задаются общие законы природы или общие закономерности, полученные в результате интегрирования дифференциальных уравнений. Примером такой модели может служить знаменитая формула К.Э. Циолковского:
,
определяющая приращение скорости ракеты при импульсном сжигании топлива через скорость истечения рабочего тела v и отношение начальной М0 и конечной Mк масс ракеты.

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

Линейные математические модели
Наиболее простыми являются так называемые линейные детерминированные модели. Они задаются в виде линейной формы управляющих переменных (х):
W = a0 + a1x1 + … + akxk
при линейных ограничениях вида
b1j x1 + b2j x2 + … + bkj xk ≥ bj , j = 1,…, q1;
c1j x1 + c2j x2 + … + ckj xk = cj , j = 1,…, q2;
d1j x1 + d2j x2 + … + dkj xk ≤ dj , j = 1,…, q3.
Общее число ограничений m = q1 + q2 + q3 может превосходить число переменных (m > k). Кроме того, обычно вводится условие положительности переменных (xi ≥ 0).

Линейные математические модели
Поверхность отклика для линейной модели представляет собой гиперплоскость. Например, рассмотрим линейную модель двух переменных следующего вида:
W = –2x1 –3x2
при следующих ограничениях
2x1 + 3x2 ≤ 18; x1 – 4x2 ≤ 4;
–2x1 + x2 ≤ 2;
х1 ≥ 0; x2 ≥ 0.
Поверхность отклика представляет собой плоский многоугольник OA'B'C'D'

Линейные математические модели
Примером такой модели является классическая модель стоимости перевозок (транспортная задача).
Имеется k пунктов производства
(i = 1,…, k) и m пунктов потребления
(j = 1,…, m) некоторого продукта. Количество продукта, произведенного в каждом из k пунктов производства, равно ai; количество продукта, необходимого в каждом из m пунктов потребления, равно bj.
Предполагается равенство общего производства и потребления

Линейные математические модели
Количество продукта, перевозимого из i-го пункта производства в j-й пункт потребления, равно xij; стоимость перевозки единицы этого продукта – сij.
Суммарная стоимость перевозок СΣ задается линейной моделью:
при следующих ограничениях
К линейным также относятся модели в виде линейных дифференциальных уравнений (обыкновенных или в частных производных).
Линейное обыкновенное дифференциальное уравнение n-го порядка имеет вид
Начальные условия записываются как
.

Линейные математические модели
Линейное дифференциальное уравнение в частных производных имеет вид.
Модель, заданная в виде дифференциального уравнения в частных производных, включает начальные и граничные условия (условия на границе области определения функции Φ(t)).

Нелинейные детерминированные модели
Нелинейные детерминированные модели обладают бóльшей точностью и гибкостью. Они могут быть заданы в виде нелинейной функции одной или нескольких переменных или в виде дифференциальных уравнений (обыкновенных или в частных производных). Наиболее распространенными среди нелинейных моделей являются:
полиномиальные функции;
позиномные функции;
тригонометрические функции;
экспоненциальные функции;
обыкновенные дифференциальные уравнения;
дифференциальные уравнения в частных производных др.

Нелинейные детерминированные модели
Нелинейные модели могут быть записаны в виде функционала, зависящего от управляющих переменных х и некоторых функций f(x) всех или части этих переменных:
W = W(x,f(x)). При этом функции f(x) могут представлять собой функционалы, зависящие от промежуточных функций f*(x) и т.д. На класс функций f(x), f*(x) не накладывается никаких ограничений, однако предполагается возможность однозначного перехода от вектора управляющих параметров х к общей характеристике модели W.
Область определения модели может быть ограничена с помощью равенств или неравенств xi = ci , i = 1,…, m;
f(x) = cj , j = 1,…, l;
xi min ≤ xi ≤ xi max , i = 1,…, k;
fj(x) ≤ cj , j = 1,…, n.

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ В ВИДЕ
ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ
Математическая модель в виде одного или нескольких обыкновенных дифференциальных уравнений (ОДУ) широко используются при изучении переходных процессов в системах автоматического регулирования (САР), при описании баллистики летательных аппаратов, а также при описании процессов движения (потоки, частицы, механические элементы). В простейшем случае модель может иметь вид линейного дифференциального уравнения n-го порядка:
или системы дифференциальных уравнений 1-го порядка

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ В ВИДЕ
ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ
Модель, заданная в виде дифференциальных уравнений, должна включать в себя необходимый набор начальных условий:
или x1(0) = C1, x2(0) = C2,…, xn(0) = Cn .
Исследование моделей, заданных в виде обыкновенных дифференциальных уравнений, осуществляется аналитическими и численными методами. Наиболее полными являются аналитические решения, обеспечивающие всесторонний анализ полученных результатов. Но такие решения получены лишь для ограниченного числа дифференциальных уравнений. Численные методы решения позволяют найти лишь конкретные значения изучаемой функции при заданной комбинации исходных данных. Для анализа модели можно использовать некоторую совокупность решений.

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ В ВИДЕ
ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ
В качестве простейшего примера математической модели механической системы может быть рассмотрена модель движения груза массой m, закрепленного на вертикальной стенке с помощью пружины жесткостью С и совершающего колебательное движение вдоль оси х в среде с вязкостью ν
Возмущающая сила, вызывающая колебания, зависит от времени f(t). Наряду с возмущающей силой f(t) на груз действует сила инерции , сила вязкого трения ,
усилие пружины .
Все эти силы тормозят движение груза.

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ В ВИДЕ
ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ
Согласно принципу Даламбера сумма всех сил, действующих на груз должна равняться нулю:
Начальные условия характеризуют начальное положение и начальную скорость груза: , x(0) = x0.
Уравнение совместно с начальными условиями представляет собой математическую модель рассматриваемой механической системы.

Модели, заданные в виде уравнений в частных производных
Ряд задач, связанных с использованием физических полей, приводит к моделям в виде дифференциальных уравнений в частных производных.
Особенностью таких задач является то, что изучаемые параметры изменяются не только во времени, но и зависят от координат x, y, z рассматриваемого пространства. Такие модели называются нестационарными. Модели, в которых параметры не зависят от времени, называются стационарными.
К таким моделям сводятся описания полей температур в элементах конструкции двигателя и полей скоростей при течении жидкости (газа). Уравнениями в частных производных описываются колебания элементов конструкции и поля напряжений, возникающих при работе этих элементов.

Модели, заданные в виде уравнений в частных производных
Линейное дифференциальное уравнение в частных производных имеет вид
Математическая модель, описанная дифференциальными уравнениями в частных производных, должна включать в себя необходимые для решения задачи краевые условия:
Должна быть задана область D, ограниченная поверхностью (на плоскости – кривой) Γ , в которой определяется решение.
Должны быть заданы условия на границе Γ этой области.
В случае нестационарного поля эти граничные условия, так же как и сама область могут меняться во времени.

Стохастические модели
Точные величины и зависимости, используемые в детерминированных моделях, представляют собой лишь некоторые средние значения (математические ожидания) реальных случайных величин (зависимостей). Так, физические константы, характеризующие материалы и рабочие тела (предел прочности материала σ, теплопроводность λ, плотность ρ и т.д.) меняются в зависимости от партии материала и условий окружающей среды. Всегда имеется определенный разброс размеров деталей l, расходов топлива в системах подачи. Все это приводит к тому, что и результирующие функции, характеризующие процесс, также носят случайный характер. Результаты, полученные с помощью детерминированной модели, представляют собой математические ожидания этих характеристик. При этом конкретные данные для конкретной системы могут существенно отличаться от этих математических ожиданий.

ЭМПИРИЧЕСКИЕ МАТЕМАТИЧЕСКИЕ МОДЕЛИ
При разработке эмпирической математической модели предполагается использование экспериментальных данных, полученных при испытаниях объектов. Результаты таких испытаний всегда представляют собой наборы величин, характеризующих работу объекта или системы при различных сочетаниях управляющих параметров.
Наиболее эффективным средством представления результатов экспериментов в системах математического моделирования являются эмпирические модели.

ЭМПИРИЧЕСКИЕ МАТЕМАТИЧЕСКИЕ МОДЕЛИ
Объект идентификации представляет собой так называемый «черный ящик» с некоторым числом регулируемых (или, по крайней мере, измеряемых) входов х и одним или несколькими наблюдаемыми (измеряемыми) выходами.
xi – управляющие переменные; ωi – неопределенности (шумы); qi – ограничения; W – характеристическая функция. Переход к эмпирическим моделям предполагает заведомый отказ от аналитических методов исследования. Поэтому эмпирические модели более разнообразны и включают в себя различные по форме математические зависимости.

ЭМПИРИЧЕСКИЕ МАТЕМАТИЧЕСКИЕ МОДЕЛИ
Задачей идентификации является построение модели объекта по результатам наблюдений его реакции на возмущения внешней среды.
При этом необходимо учитывать ошибки, возникающие при измерении характеристик объекта.
Требуется построить зависимость (модель)
W = f(x), которая описывает характеристики изучаемой системы. Это уравнение называется уравнением регрессии и описывает поверхность (гиперповерхность) отклика, характеризующую эмпирическую модель.
Обычно предполагается, что имеющиеся экспериментальные данные дают достаточно информации для воссоздания математического описания объекта.

ЭМПИРИЧЕСКИЕ МАТЕМАТИЧЕСКИЕ МОДЕЛИ
При этом на практике может встретиться два случая:
1) Форма математической модели известна заранее, а задача идентификации сводится к определению коэффициентов этой модели. Так, описание ряда затухающих или развивающихся процессов дается зависимостями экспоненциального типа. Задача исследования является определение коэффициентов α, β.
2) Форма математической модели заранее неизвестна. В этом случае для идентификации модели используются отрезки бесконечных рядов, а задача заключается в определение числа членов ряда и коэффициентов при этих членах. Модель может быть представлена в виде
где fq(xi) – некоторые заданные функции; βqi – коэффициенты регрессии; q = 0, 1,…, l.

ЭМПИРИЧЕСКИЕ МАТЕМАТИЧЕСКИЕ МОДЕЛИ
Конкретный вид модели зависит от выбора функций fq(x), по которым производится разложение W. Например, при описании колебательных процессов удобно использовать ряд Фурье. В одномерном случае (k = 1) уравнение принимает вид
Сама постановка задачи идентификации включает в себя элемент неопределенности, возможность множественности решений. Важно выбрать лучшее или, по крайней мере, достаточно хорошее из этих решений.
Для оценки точности модели естественно использовать величины отклонений, полученных в эксперименте величин Wj и их оценок Wmj , предсказанных моделью
εj = Wj – Wmj.

Численные методы решения нелинейных уравнений
Дано нелинейное уравнение:
Необходимо решить это уравнение, т. е. найти его корень
Большинство употребляющихся приближенных методов решения уравнений являются, по существу, способами уточнения корней. Для их применения необходимо знание интервала изоляции [a,b], в котором лежит уточняемый корень уравнения.

Численные методы решения нелинейных уравнений
Процесс определения корней алгебраических и трансцендентных уравнений состоит из 2 этапов:
отделение корней, - т.е. определение интервалов изоляции [a,b], внутри которого лежит каждый корень уравнения;
уточнение корней, - т.е. сужение интервала [a,b] до величины равной заданной степени точности .
Для алгебраических и трансцендентных уравнений пригодны одни и те же методы уточнения приближенных значений действительных корней:
метод половинного деления (метод дихотомии);
метод простых итераций ;
метод Ньютона (метод касательных) ;
модифицированный метод Ньютона ( метод секущих );
метод хорд и др.

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

Численные методы решения нелинейных уравнений
На первом этапе, как правило, применяется графический метод исследования функции f(x), а способ отделения корней основан на следующей теореме:
Если функция f(x), определяющая уравнение f(x) = 0, на концах отрезка [a;b] принимает значения разных знаков, т.е. f(a)*f(b)<0, то на этом отрезке содержится, по крайней мере, один корень уравнения.
Если функция f(x) строго монотонна, то корень на отрезке [a;b] единственный (f'(a)*f'(b)>0) .
Предварительное исследование функции f(x) начинается с выбора подмножества допустимых значений аргумента x - отрезка [a;b].

Метод половинного деления
Дано нелинейное уравнение f(x)=0.
Найти корень уравнения, принадлежащий отрезку [a,b], с заданной точностью ε.
Для уточнения корня методом половинного деления последовательно осуществляем следующие операции:
Делим интервал пополам: t=(a+b)/2, в качестве нового интервала изоляции принимаем ту половину интервала, на концах которого функция имеет разные знаки

Метод половинного деления
Для этого:
1) Вычисляем значение функции f(x) в точках a и t.
2) Проверяем: если f(a)f(t) < 0, то корень находится в левой половине отрезка [a,b]. Тогда отбрасываем правую половину отрезка и делаем переприсваивание b=t.
3) Если f(a)f(t) < 0 не выполняется, то корень находится в правой половине отрезка [a,b] . Тогда отбрасываем левую половину и делаем переприсваивание a=t. В обоих случаях получим новый отрезок [a,b] в два раза меньший предыдущего. Процесс, начиная с пункта 1, циклически повторяем до тех пор, пока длина отрезка [a,b] не станет равной либо меньшей заданной точности, т.е. (b-a)/2 ≤ε.

Метод половинного деления
Схема алгоритма уточнения корней по методу половинного деления

Метод Ньютона (метод касательных)
Метод Ньютона основан на замене исходной функции f(x), на каждом шаге поиска касательной, проведенной к этой функции. Пересечение касательной с осью Х дает приближение корня.
Выберем начальную точку x0=b (конец интервала изоляции). Находим значение функции в этой точке и проводим к ней касательную, пересечение которой с осью Х дает нам первое приближение корня x1.

Метод Ньютона (метод касательных)
В результате итерационный процесс схождения к корню реализуется рекуррентной формулой
Процесс поиска продолжаем до тех пор, пока не выполнится условие
Упростим это условие и получим:
Метод обеспечивает быструю сходимость, если выполняется условие:
т.е. первую касательную рекомендуется проводить в той точке интервала [a,b], где знаки функции f(x0) и ее кривизны f"(x0) совпадают.

Схема алгоритма уточнения корня метод Ньютона

Метод хорд
Метод основан на замене функции f(x) на каждом шаге поиска хордой, пересечение которой с осью Х дает приближение корня.
При этом в процессе поиска семейство хорд может строиться:
а) при фиксированном левом конце хорд, т.е. z=a, тогда начальная точка x0=b;
б) при фиксированном правом конце хорд, т.е. z=b, тогда начальная точка х0=a

Метод хорд
В результате итерационный процесс схождения к корню реализуется рекуррентной формулой:
для случая а)
для случая б)
Процесс поиска продолжается до тех пор, пока не выполнится условие
Метод обеспечивает быструю сходимость, если f(z)f"(z) > 0, т.е. хорды фиксируются в том конце отрезка [a,b], где знаки функции f(z) и ее кривизны f"(z) совпадают.

Метод хорд
Схема алгоритма уточнения корня методом хорд

Решение систем линейных уравнений (СЛАУ)
Постановка задачи
Требуется найти решение системы n линейных уравнений:
a11·x1 +a12·x2+…+a1n·xn=b1
a21·x1 +a22·x2+…+a2n·xn=b2
……
an1·x1 +an2·x2+…+ann·xn=bn
Эту систему уравнений можно записать также в матричном виде: A⋅X=B
где A – матрица системы, B – вектор правых частей, X – вектор неизвестных.
При известных A и B требуется найти значения x, при подстановке которых в систему уравнений она превращается в тождество.

Решение систем линейных уравнений (СЛАУ)
Необходимым и достаточным условием существования единственного решения СЛАУ является условие det A≠0, т.е. определитель матрицы A не равен нулю. В случае равенства нулю определителя матрица A называется вырожденной и при этом СЛАУ либо не имеет решения, либо имеет их бесчисленное множество. В дальнейшем будем предполагать наличие единственного решения. Системы линейных алгебраических уравнений можно решать как с помощью прямых, так и итерационных методов. Для систем уравнений средней размерности чаще используют прямые методы. Итерационные методы обычно применяют для решения задач большой размерности, когда использование прямых методов затруднено ограничениями по доступной оперативной памяти ЭВМ и вычислительной ошибкой, которая накапливается при большом количестве арифметических операций. Вычислительная ошибка возникает из-за ограничений разрядной сетки компьютера при представлении вещественных чисел.

Решение систем линейных уравнений (СЛАУ)
Описание метода простой итерации
Из первого уравнения системы
a11·x1 +a12·x2+…+a1n·xn=b1
a21·x1 +a22·x2+…+a2n·xn=b2
……
an1·x1 +an2·x2+…+ann·xn=bn
выражаем х1, из второго – х2 и так далее. Получим:
x1= b1/a11 – (a12·x2+ a13·x3+…+a1n·xn)/ a11
x2= b2/a22 – (a21·x1+ a23·x3+…+a2n·xn)/ a22
xj= bj /ajj – (aj1·x1+ aj2·x2+…+ajj-1·xj-1+ajj+1·xj+1+…+ajn·xn)/ ajj
……..
xn= bn /ann – (an1·x1+ an2·x2+…+ann-1·xn-1)/ ann

Метод простой итерации
Подставим в правую часть этой системы значения и получим . Первая итерация закончена и переходим к второй итерации. Подставим значения x0 и рассчитаем x1 и так далее. Расчетная формула пересчета значений х в общем виде:
Условие окончания итерационного процесса при достижении точности ε в упрощённой форме имеет вид:
Существует более точное условие окончания итерационного процесса, которое более сложно и требует дополнительных вычислений.

Итерационный процесс в методе Гаусса-Зейделя строится по формуле
после выбора соответствующего начального приближения .
Метод Гаусса-Зейделя можно рассматривать как модификацию метода Якоби. Основная идея модификации состоит в том, что новые значения используются здесь сразу же по мере получения, в то время как в методе Якоби они не используются до следующей итерации
где
Метод Гаусса—Зейделя

Таким образом, i-тая компонента (k+1) -го приближения вычисляется по формуле:
Условие сходимости
Приведём достаточное условие сходимости метода
Теорема.
Пусть , где матрица, обратная к (L + D) . Тогда при любом выборе начального приближения :
метод Гаусса-Зейделя сходится;
скорость сходимости метода равна скорости сходимости геометрической прогрессии со знаменателем ;
верна оценка погрешности:
Метод Гаусса—Зейделя

Условие окончания
Условие окончания итерационного процесса Зейделя при достижении точности в упрощённой форме имеет вид:
Более точное условие окончания итерационного процесса имеет вид
Ход метода, где: a[n][n] - матрица коэффициентов
x[n], p[n] - текущее и предыдущее решения
b[n] - столбец правых частей. Все перечисленные массивы вещественные и должны быть определены в основной программе, также в массив x[n] следует поместить начальное приближение столбца решений (например, все нули)
Метод Гаусса—Зейделя

Пример. Методом Зейделя решить систему (точность 0,01)
Приведем систему к виду
Метод Гаусса—Зейделя

Метод Гаусса—Зейделя
Ответ: (0,752; 1,289; -0,005)

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

Пусть известные значения некоторой функции f образуют следующую таблицу:
При этом требуется получить значение функции f для такого значения аргумента х, которое входит в отрезок [x0;xn], но не совпадает ни с одним из значений xi (i=0,1,…,n). Классический подход к решению задачи построения приближающей функции основывается на требовании строгого совпадения значений f(x) и F(x) в точках xi (i=0,1,2, …,n), т.е.F(x0)=y0, F(x1)=y1, …, F(xn)=yn.
В этом случае нахождение приближенной функции называют интерполяцией (или интерполированием), а точки x0, x1, …, xn – узлами интерполяции. Геометрически это означает, что нужно найти кривую y=F(x) некоторого определенного типа, проходящую через заданную систему точек Mi(xi,yi).
Интерполяция. Постановка задачи интерполяции

Задача интерполирования может иметь в общей постановке бесчисленное множество решений или совсем их не иметь. Однако эта задача становится однозначной, если вместо произвольной функции F(x) искать некоторую функцию конкретного вида, удовлетворяющую условиям.
Наиболее удобной в практическом использовании функцией является алгебраический многочлен степени n :
Pn(x)=a0xn + a1xn-1 + … + an-1x + an
Чтобы задать многочлен n-ой степени достаточно задать его n+1 коэффициент. Значения многочлена просто вычисляются, его легко продифференцировать, проинтегрировать и т.д. Поэтому алгебраические многочлены нашли широкое применение для приближения функций.
Интерполяция

Интерполяционный многочлен должен пройти через каждую узловую точку (xi, yi) таблицы, т.е.,
Подставляя каждую узловую точку таблицы, получаем систему линейных уравнений:
Неизвестными системы являются a0, a1, a2, :, an т.е. коэффициенты многочлена. Коэффициенты при неизвестных системы легко могут быть определены на основании данных исходной таблицы.
Интерполяция

Интерполяционный многочлен может быть построен при помощи специальных интерполяционных формул Лагранжа, Ньютона, Стерлинга, Бесселя и др.
Интерполяционный многочлен по формуле Лагранжа имеет вид:
Интерполяция по Лагранжу

Докажем, что многочлен Лагранжа является интерполяционным многочленом, проходящим через все узловые точки, т.е. в узлах интерполирования xi выполняется условие Ln(xi) = yi. Для этого будем последовательно подставлять значения координат узловых точек таблицы в многочлен. В результате получим:
если x=x0, то Ln(x0) = y0,
если x=x1, то Ln(x1) = y1,
……………
если x=xn, то Ln(xn) = yn.
Это достигнуто за счет того, что в числителе каждой дроби при соответствующем значении уj, j=0,1,2,:,n отсутствует сомножитель (x-xi), в котором i=j, а знаменатель каждой дроби получен заменой переменной х на соответствующее значение хj.
Интерполяция по Лагранжу

Таким образом, интерполяционный многочлен Лагранжа приближает заданную табличную функцию, т.е. Ln(xi) = yi и мы можем использовать его в качестве вспомогательной функции для решения задач интерполирования, т.е.
Чем больше узлов интерполирования на отрезке [x0,xn], тем точнее интерполяционный многочлен приближает заданную табличную функцию, т.е. тем точнее равенство:
Однако с увеличением числа узлов интерполирования возрастает степень интерполяционного многочлена n и в результате значительно возрастает объем вычислительной работы. В этом случае удобно находить значения функции в промежуточных точках, не получая многочлен в явном виде.
Интерполяция по Лагранжу

Пример. N=1 (два узла интерполяции)
уравнение прямой, проходящей через точки (x0, y0), (x1, y1)
Интерполяция по Лагранжу

Пример. N=2 (три узла интерполяции)
- уравнение параболы, проходящей через точки (x0, y0), (x1, y1), (x2, y2).
Интерполяция по Лагранжу

Обзор методов численного интегрирования
Методы вычисления однократных интегралов называются квадратурными (для кратных интегралов – кубатурными).
К квадратурным методам относятся методы Ньютона-Котеса. В этих методах φ(x) – это полиномы различных степеней, к ним относятся: метод прямоугольников, метод трапеций, метод Симпсона.

Метод прямоугольников
Алгоритм метода прямоугольников:
Весь участок [a,b] делим на n равных частей с шагом h=(b-a)/n.
Определяем значение yi подынтегральной функции f(x) в каждой части деления, т.е.
В каждой части деления подынтегральную функцию f(x) аппроксимируем интерполяционным многочленом степени n = 0, т.е. прямой, параллельной оси OX. В результате вся подынтегральная функция на участке [a,b] аппроксимируется ломаной линией. Для каждой части деления определяем площадь Si частичного прямоугольника. Суммируем эти площади. Приближенное значение интеграла I равно сумме площадей частичных прямоугольников.

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

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

Метод трапеций
Найдем площади Si частичных трапеций:
Приближенное значение интеграла равно
Точность метода трапеций имеет порядок h2.

Метод трапеций
Алгоритм метода трапеций:
Интервал [a,b] делим на n равных частей с шагом h=(b-a)/n.
Вычисляем значение подынтегральной функции в каждой узловой точке
На каждом шаге подынтегральную функцию f(x) аппроксимируем прямой, соединяющей две соседние узловые точки. В результате вся подынтегральная функция на участке [a,b] заменяется ломаной линией проходящей через все узловые точки.
Вычисляем площадь каждой частичной трапеции.
Приближенное значение интеграла равно сумме площадей частичных трапеций, т.е.

Метод трапеций
Найдем площади Si частичных трапеций:
Приближенное значение интеграла равно
Точность метода трапеций имеет порядок h2.

Метод трапеций
Схема алгоритма метода трапеций

Метод Симпсона
В методе Симпсона в каждой части деления подынтегральная функция аппроксимируется квадратичной параболой a0x2+a1x+a2. В результате вся кривая подынтегральной функции на участке [a,b] заменяется кусочно-непрерывной линией, состоящей из отрезков квадратичных парабол. Приближенное значение интеграла I равно сумме площадей под квадратичными параболами. Т.к. для построения квадратичной параболы необходимо иметь три точки, то каждая часть деления в методе Симпсона включает два шага, т.е. Lk=2h.
В результате количество частей деления N2=n/2. Тогда n в методе Симпсона всегда четное число.
Определим площадь S1 на участке [x0, x2]

Метод Симпсона
Исходя из геометрического смысла определенного интеграла, площадь S1 равна определенному интегралу от квадратичной параболы на участке [x0, x2]:
Неизвестные коэффициенты квадратичной параболы а0 , а1, а2 определяем из условия прохождения параболой через три узловых точки с координатами (x0y0), (x1y1), (x2y2).
На основании этого условия строим систему линейных уравнений:

Метод Симпсона
Решая эту систему, найдем коэффициенты параболы.
Для участка [x2, x4]
Для участка [xi-1, xi+1]:
Суммируя все площади S1 под квадратичными параболами, получим квадратурную формулу по методу Симпсона:
где
N2 - количество частей деления.

Метод Симпсона
Схема алгоритма метода Симпсона

Численные методы решения дифференциальных уравнений первого порядка
Общий вид дифференциального уравнения
Нормальная форма дифференциального уравнения
где y=y(x) -неизвестная функция, подлежащая определению,
f(x,y) - правая часть дифференциального уравнения в нормальной форме, равная первой производной функции y(x). В функцию f(x,y) помимо аргумента x входит и сама неизвестная функция y(x). Если неизвестная функция у зависит от одного аргумента x, то дифференциальное уравнение вида называется обыкновенным дифференциальным уравнением.
Если функция у зависит от нескольких аргументов, то такое дифференциальное уравнение называется дифференциальным уравнением в частных производных.

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

Численные методы решения дифференциальных уравнений первого порядка
Нахождение частного решения дифференциального уравнения удовлетворяющего начальному условию называется задачей Коши.
В численных методах задача Коши ставится следующим образом: найти табличную функцию
которая удовлетворяет заданному дифференциальному уравнению и начальному условию на отрезке [a,b] с шагом h, то есть построить таблицу .

Методы Рунге - Кутта
Наиболее эффективными и часто встречаемыми методами решениями задачи Коши являются методы Рунге - Кутта. Они основаны на аппроксимации искомой функции у(х) в пределах каждого шага многочленом, который получен при помощи разложения функции у(х) в окрестности шага h каждой i-ой точки в ряд Тейлора:
Усекая ряд Тейлора в различных точках и отбрасывая правые члены ряда, Рунге и Кутта получали различные методы для определения значений функции у(х) в каждой узловой точке. Точность каждого метода определяется отброшенными членами ряда.

Метод Рунге - Кутта 1-го порядка (метод Эйлера)
Отбросим члены ряда, содержащие h2, h3, h4, тогда
, учитывая, что
получим формулу Эйлера
Так как точность методов Рунге-Кутта определяется отброшенными членами ряда , то точность метода Эйлера на каждом шаге составляет
Рассмотрим геометрический смысл метода Эйлера.
Формула Эйлера имеет вид:
где .

Метод Рунге - Кутта 1-го порядка (метод Эйлера)
В результате в методе Эйлера на графике вся искомая функция y(x) на участке [a,b] аппроксимируется ломаной линией, каждый отрезок которой на шаге h линейно аппроксимирует искомую функцию. Поэтому метод Эйлера получил еще название метода ломаных.

Метод Рунге - Кутта 1-го порядка (метод Эйлера)
В методе Эйлера наклон касательной в пределах каждого шага считается постоянным и равным значению производной в начальной точке шага xi. В действительности производная, а, значит, и тангенс угла наклона касательной к кривой y(x) в пределах каждого шага меняется. Поэтому в точке xi+h наклон касательной не должен быть равен наклону в точке xi. Следовательно, на каждом шаге вносится погрешность. Первый отрезок ломаной действительно касается искомой интегральной кривой y(x) в точке (x0,y0). На последовательных же шагах касательные проводятся из точек (xi,yi), подсчитанных с погрешностью. В результате с каждым шагом ошибки накапливаются. Основной недостаток метода Эйлера - систематическое накопление ошибок. Поэтому метод Эйлера рекомендуется применять для решения дифференциальных уравнений при малых значениях шага интегрирования h.

Метод Рунге - Кутта 2-го порядка (модифицированный метод Эйлера)
Отбросим в разложении в ряд Тейлора члены ряда, содержащие h3, h4, h5:
Чтобы сохранить член ряда, содержащий h2, надо определить вторую производную y"(xi).Ее можно аппроксимировать разделенной разностью 2-го порядка
Подставляя это выражение, получим
Окончательно, модифицированная или уточненная формула
Эйлера имеет вид:

Метод Рунге - Кутта 2-го порядка (модифицированный метод Эйлера)
Как видно, для определения функции y(x) в точке i+1 необходимо знать значение правой части дифференциального уравнения f(xi+1, yi+1) в этой точке, для определения которой необходимо знать предварительное значение yi+1.
Для определения предварительного значения yi+1 воспользуемся формулой Эйлера. Тогда все вычисления на каждом шаге по модифицированной или уточненной формуле Эйлера будем выполнять в два этапа:
На первом этапе вычисляем предварительное значение
по формуле Эйлера

Метод Рунге - Кутта 2-го порядка (модифицированный метод Эйлера)
На втором этапе уточняем значение yi+1 по модифицированной или уточненной формуле Эйлера
то модифицированную формулу Эйлера
можно представить в виде:

Метод Рунге - Кутта 4-го порядка
Самое большое распространение из всех численных методов решения дифференциальных уравнений с помощью ЭВМ получил метод Рунге-Кутта 4-го порядка. В литературе он известен как метод Рунге-Кутта. В этом методе на каждом шаге интегрирования дифференциальных уравнений искомая функция y(x) аппроксимируется рядом Тейлора, содержащим члены ряда с h4
В результате ошибка на каждом шаге имеет порядок h5.

Метод Рунге - Кутта 4-го порядка
Для сохранения членов ряда, содержащих h2,h3,h4 необходимо определить вторую y", третью y"' и четвертую y(4) производные функции y(x). Эти производные аппроксимируем разделенными разностями второго, третьего и четвертого порядков соответственно. В результате для получения значения функции yi+1 по методу Рунге-Кутта выполняется следующая последовательность вычислительных операций:

Метод Рунге - Кутта 4-го порядка

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

Решение дифференциальных уравнений высоких порядков
В результате дифференциальное уравнение m -го порядка сводится к системе, состоящей из m дифференциальных уравнений первого порядка:
Решением системы , а значит и дифференциального уравнения m -го порядка является m табличных функций

Решение дифференциальных уравнений второго порядка
Общий вид дифференциальных уравнений второго порядка
Нормальная форма дифференциальных уравнений второго порядка:
Заменим y1=y', тогда y'1=y". В результате исходное уравнение сводится к системе, состоящей из двух дифференциальных уравнений первого порядка:
Решением этой системы являются две функции y(x) и y1(x),
где

Решение дифференциальных уравнений второго порядка
Сформулируем задачу Коши для системы, состоящей из двух дифференциальных уравнений второго порядка.
Дана система
Даны два начальных условия:
Необходимо проинтегрировать систему на участке [a, b] с шагом h.
В численных методах задача Коши для системы сводится к
нахождению табличных функций

Решение дифференциальных уравнений второго порядка
На графике решением задачи Коши для системы, состоящей из двух дифференциальных уравнений первого порядка, является совокупность узловых точек.
При этом на каждом шаге, т.е. для каждого значения xi решением являются две узловые точки с координатами (xi, yi), (xi, (y1)i).

Методы одномерной оптимизации

Методы одномерной оптимизации
Численные методы

Методы одномерной минимизации

Метод деления отрезка пополам

Метод деления отрезка пополам

Методы одномерной оптимизации

Методы одномерной оптимизации
Пример.
Найти минимум функции методом
«Золотого сечения»

Метод золотого сечения

Метод золотого сечения
=A2+0,382*(B2-A2)

Метод золотого сечения
=A2+0,618*(B2-A2)

Метод золотого сечения
=0,2*(C2-1,5)*(C2-1,5)-2*EXP(COS(C2-0,3))

=ЕСЛИ(E2

=ЕСЛИ(E2

=ЕСЛИ(E2

=ЕСЛИ(E2

Результаты
Поиск минимума функции вида f(x)

Результаты
Поиск минимума функции вида f(x)

Логистика - наука о планировании, контроле и управлении транспортированием, складированием и др. материальными и нематериальными операциями, совершаемыми в процессе доведения сырья и материалов до промышленных предприятий; внутризаводской переработки сырья, материалов, полуфабрикатов; доведения готовой продукции до потребителя в соответствии с его требованиями а также передачи, обработки и хранения соответствующей информации.
Логистика (от греч. - искусство рассуждения, искусство снабжения армии и ее перемещение, математическая логистика).
Понятие Логистика - как математическая логика; техника и технология транспортно-складских работ в военной и/или гражданской области. Логистика -4-й главный элемент военной науки.
У нас в стране Всесоюзная Ассоциация Логистики образована в 1991г.
Фонд Логистических Разработок (1993г.) занимается подготовкой и переподготовкой кадров.
Понятие логистики. История появления и развития логистики

Глобальная цель логистики - сокращение цикла, уменьшение запасов.
Основная задача логистики - использование материалов, энергии, информации, персонала и средств производства. Предоставить потребителю продукцию в заданное время заданного качества в заданное место и за определенную цену.

Логистика - нахождение такого канала товародвижения, который обеспечивает минимальные сроки и минимальные затраты по доставке товаров потребителю. Обеспечивает непрерывность производства и воспроизводства.
Товарный запас - готовая продукция, которая не продана.
Цели товара:
- удовлетворение потребностей потребителя;
- приносить прибыль владельцу;
Цикл товарообращения должен быть как можно короче. Условия:
1. Переход от рынка продавца к рынку потребителя;
2. Производство изделий большими партиями сменяется на мелкосерийное производство.

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

Принципы логистики
1. Саморегулирование (сбалансировапнность производства).
2. Гибкость (возможность внесения изменений в график закупки материалов, изменение в сроках поставки).
3. Минимизация объемов запасов.
4. Моделирование товародвижения.
5. Компьютеризация (управление материальными потоками).
6. Надежность в обеспечении ресурсами.
7. Экономичность (сокращение уровня запасов продукции у потребителя до 30-45%, повышение уровня информационного обслуживания, транспорт)
Условия внедрения логистики:
1. Конкуренция.
2. Отсутствие дефицита.

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

Информационный поток (ИП) не всегда соответствует дан. МП, т.е. ИП и МП могут быть синхронные и асинхронные.
Логистическая операция - обособленная совокупность действий, направленных на преобразование ИП или ИП. Логистическая операция может быть материальной (транспортировка, складирование, погрузка) и нематериальной (сбор данных о МП, хранение и передача данных).
Логистическая функция - укрупненная группа логистических операций, направленных на реализацию целей логистической системы. Основные функции - снабжение, производство, сбыт.

В логистике для управления потоками используют функции:
- Планирование (установление оптимальной траектории движения, разработка расписания или графика следования потока, расчет потребностей в ресурсах для осуществления потока).
- Оперативное регулирование (отслеживание каждого объекта потока, согласно графику движения, выработка и применение управленческих воздействий).
- Учет, сбор, обработка, хранение и выдача информации о МП (составление отчетности).
- Контроль (степень соответствия фактических параметров потока плановым).
- Анализ (причины несоответствия плану).
- Координация (координация процессов закупки, сбыта).

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

Логистический цикл в общем виде включает в себя:
время на формулировку заказа и его оформление в установленном порядке.
время на доставку или передачу заказа поставщику.
время выполнения заказа (время ожидания постановки заказа на выполнение, время выполнения заказа, время простоев, комплекса услуг).
время доставки изготовленной продукции заказчику.
время на подготовку продукции к потреблению.

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

Материальные ресурсы:
- сырье;
- основные материалы (материалы, входящие в продукт и составляющие его основу);
- вспомогательные материалы (материалы в небольших количествах являющиеся составной частью)
- полуфабрикаты;
- комплектующие изделия (могут быть приобретены со стороны или на предприятии);
- незавершенное производство (предметы труда, незаконченные обработкой в данном цехе);
- деталь (готовая часть механизма, используемая при сборке готовой продукции);
- узел (сборочная единица из 2-х и более деталей);
- блок (укрупненные сборочные единицы);
- готовые изделия (соответствующие всем требованиям ГОСТ);
- система (совокупность устройств).

Материальный поток - материальные ресурсы определенных видов, в определенных количествах перемещаемые от определенного поставщика к определенному получателю из одного определенного места в другое в заранее оговоренный срок.
Если материальные ресурсы собраны на складе, они не материальный поток, а материальные запасы.
Характеристики материального потока.
1-я часть: ассортимент, габариты, качество (сорт, марка);
2-я часть: количество материальных ресурсов и интенсивность потока (штучные грузы оцениваются в штуках; объемные - по объему; тяжеловесные и крупногабаритные - по площади, по массе);
3-я часть: начальная точка пути - поставщик, конечная – потребитель, траектория- длина пути; время движения.

Разновидности материальных потоков:
- по номенклатуре (простые или сложные, одно- или многоассортиментные);
- по степени готовности (планируемые, формируемые, расформировываемые)
- по месту в процессе обращения ( ожидающие отгрузки, отгруженные, в пути, прибывшие, ожидающие разгрузки, принятые на склад).
- по непрерывности (непрерывные и дискретные).
- по частоте прибытия или отправления (срочные, длительные, часовые, ежедневные и т.д.).
- по различиям массы или объема (массовые, крупные, средние, мелкие)

Массовые потоки - перемещение которых осуществляется не в единичных транспортных средствах, а в большой их группе,
Крупные - мельче массовых (1-2 вагона, но часто).
Мелкие потоки - масса которых меньше грузоподъемности транспортных средств.
По различиям массы:
тяжеловесные;
легковесные
По степени агрессивности, огнеопасности, взрывоопасности:
Неагрессивные
Агрессивные
Неогнеопасные
Огнеопасные
Взрывоопасные
Взрывобезопасные

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

Материальные потоки по степени определенности делятся на:
детерминированные
стохастические (если отсутствует какая-то характеристика)
По ритмичности отправок:
ритмичные
неритмичные
Для ритмичные МП синхронизированы сроки поставки (отгрузки) в соответствии с заранее спланированным графиком.
По степени равномерности: равномерные и неравномерные.
Равномерные характеризуются постоянством скорости перемещения.

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

Предметом транспортной логистики является комплекс задач, связанных с организацией перемещения грузов транспортом общего назначения.
Задачи транспортной логистики:
выбор вида транспортных средств;
выбор типа транспортных средств;
совместное планирование транспортного процесса со складским и производственным;
совместное планирование транспортных процессов на различных видах транспорта (в случае смешанных перевозок);
обеспечение технологического единства транспортно-складского процесса;
определение рациональных маршрутов доставки.
Транспортная логистика

Транспорт — это отрасль материального производства, осуществляющая перевозки людей и грузов. В структуре общественного производства транспорт относится к сфере производства материальных услуг.
Значительная часть логистических операций на пути движения материального потока от первичного источника сырья до конечного потребителя осуществляется с применением различных транспортных средств. Затраты на выполнение этих операций составляют до 50% от суммы общих затрат на логистику.
Транспортная логистика

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

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

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

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

По способу действия все транспортные средства подразделяются на средства прерывного (циклического) и непрерывного действия,
по направлению перемещения грузов - на горизонтальные (транспортеры, рольганги), вертикальные (автопогрузчики, краны - балки, мостовые краны), наклонные (канатные и монорельсовые дороги).
Стационарные транспортные устройства могут создаваться с опорой на пол и без неё (подъём грузов осуществляется с помощью конструкции, закрепленной на потолке). Примерами устройств, связанных с полом, являются скрытый под полом цепной транспортер, несущий цепной транспортер, ременный транспортер, рольганги. Конструкции, не связанные с полом, обычно следующие: цепной подвесной транспортер, транспортер с электроприводом, ручные тали.
Транспортная логистика

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

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

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

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

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

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

Речной транспорт при перевозках грузов весом более 100 т на расстояние свыше 250 км является самым дешевым видом транспорта. Кроме низких тарифов следует отметить другие его достоинства, например, высокую провозную способность на глубоководных реках, небольшие затраты на организацию судоходства. Затрудняет использование данного вида транспорта неравномерность глубин рек, сезонность работы, небольшая скорость перевозки.
Одним из основных преимуществ автомобильного транспорта является его высокая маневренность и подвижность доставки грузов. Этот вид транспорта может доставлять груз "от дверей до дверей" без промежуточных перегрузок с необходимой степенью срочности. Недостатками являются низкая производительность труда, сравнительная дороговизна перевозок груза и опасность угона автотранспорта.
Технико-экономические особенности различных видов транспорта

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

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

Для ускорения погрузочно-разгрузочных работ, ускорения оборота транспортных средств, улучшения сохранности грузов в этом случае применяются контейнеры и поддоны. Парк контейнеров рассчитывается по формуле:
где N - количество контейнеров, ед.;
Q - общий объем перевозок в планируемом периоде, т;
А - оборот контейнера ( цикл использования, измеряемый от одной погрузки до следующей), сут.;
F - число дней в планируемом периоде;
qH - грузоподъемность - нетто контейнера, т.
Расчет количества контейнеров

Характеристики вагонного парка
Материально-техническая база транспорта включает транспортные средства (вагоны, локомотивы, флот, автомобили), технические устройства и сооружения (станции, депо, порты, пристани, причалы и др.), а также ремонтные предприятия, путевое (дорожное) хозяйство, средства автоматики, телемеханики и связи.
Вагонный парк состоит из пассажирских и грузовых вагонов, которые подразделяют на универсальные (крытые полувагоны, платформы, цистерны) и специализированные (изотермические, кислотные, цементные и т.п.). Каждый тип вагона характеризуется грузоподъёмностью, вместимостью, массой тары и другими показателями.

Характеристики вагонного парка
Грузоподъёмность - показатель мощности транспортного средства, измеряемый количеством тонн грузов, которые могут быть приняты им к перевозке.
Удельная грузоподъёмность - грузоподъёмность, приходящаяся на 1 м3 полного объема вагона (грузовые помещения).
Если плотность груза меньше удельной грузоподъёмности транспортного средства, то его грузовместимость используется полностью, а грузоподъёмность недоиспользуется. Если плотность груза больше удельной, то полностью используется грузоподъёмность, а грузовместимость недоиспользуется. На железнодорожном транспорте повышение грузоподъёмности вагона без увеличения числа осей ограничивается допустимой нагрузкой на путь. Разрабатываются технические нормы загрузки вагонов, зависящие от плотности груза, его формы и рода. За недогруз вагона до технической нормы взимается штраф.

Характеристики вагонного парка
Грузовместимость - суммарный объём помещений транспортного средства, используемый для размещения и перевозки грузов. У грузовых вагонов различают полный (геометрический) объём, равный произведению длины, ширины, высоты вагона, и погрузочный (полезный) объём (используемая часть полного объёма).
Погрузочный объём может быть больше полного при загрузке вагона выше борта.
Удельный объём - объём, приходящиеся на 1т грузоподъёмности.
Производительность вагонного парка характеризуется полным использованием грузоподъёмности и вместимости вагонов.

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

Характеристики морских и речных судов
Транспортный флот - главный элемент материально-технической базы морского и речного транспорта, т.к. он осуществляет основную функцию транспорта - пространственное перемещение грузов.
Основными показателями, характеризующими морские и речные суда, являются водоизмещение, грузоподъёмность, грузовместимость, размеры судов, осадка в гружёном и порожнем состояниях.
Водоизмещение - масса или объём воды, вытесняемый плавающим судном.

Характеристики морских и речных судов
Грузоподъемность судна - максимальное количество груза (без воды, топлива, грузов снабжения) в тоннах, которое судно может принять к перевозке. Для получения максимальной грузоподъемности необходимо правильно устанавливать допускаемую осадку судна (при погружении по грузовую марку) и строго нормировать все судовые запасы.
У судов различают грузовместимость теоретическую, зерновую для сыпучих грузов, грузовместимость для жидких грузов.
Коэффициент использования грузоподъемности судна определяется как частное от деления величины тонно-километров (тонно-миль), фактически выполненных судном за отчетный период, на количество тоннаже-километров (тоннаже-миль) в порожнем и груженом состоянии за этот период.

Характеристики морских и речных судов
Коэффициент использования грузовместимости определяется по следующим формулам:
для простого рейса (при перевозке грузов между двумя портами)
где q1, q2,. .,qn - масса отдельных партий груза, т;
u1, u2,.. .,un - объем, занимаемый каждой партией груза, м3;
l1, l2,...,ln -расстояние перевозки груза, км (миль);
L - средняя дальность перевозки груза, км (миль);
W - грузовместимость судна.
для сложного рейса (при перевозке грузов между несколькими портами, в каждом из которых производится

Характеристики автомобильного транспорта
Подвижной состав автомобильного транспорта состоит из автомобилей, тягачей, прицепов и полуприцепов.
Грузоподъемность автотранспорта определяется его конструкцией и указывается в техническом паспорте автомобиля, прицепа, полуприцепа.
Средняя грузоподъемность ходового автомобиля зависит от структуры парка подвижного состава и коэффициента использования парка транспортных средств по выпуску, т.е. отношения количества машин в движении к числу машин в наличии.

Характеристики автомобильного транспорта
Коэффициент использования грузоподъемности автомобиля характеризует использование номинальной грузоподъемности автомобиля в статике и динамике. Статический коэффициент - отношение загрузки автомобиля в тоннах к его номинальной грузоподъемности в момент окончания погрузки. Определяется за одну ездку - делением количества фактически перевезенного груза на номинальную грузоподъемность автомобилей; за одну смену - делением объема перевозок на произведение номинальной грузоподъемности и количества выполненных за смену ездок.

Характеристики автомобильного транспорта
Динамический коэффициент есть отношение фактических тонно-километров к возможным тонно-километрам при полном использовании грузоподъемности.
Работа подвижного состава автотранспорта оценивается системой технико-эксплуатационных показателей, характеризующих количество и качество выполненной работы.
В работе автомобильного транспорта различают понятие ездки и оборота.
Ездка - законченный цикл транспортной работы, состоящий из погрузки груза на автомобиль tn, движения с грузом trp, разгрузки tp и подачи транспортного средства для следующей погрузки (движение без груза) tдв

Характеристики автомобильного транспорта
Оборот включает одну или несколько ездок, причем подвижной состав обязательно должен возвращаться в исходную точку.
Ускорение оборота влияет на сроки доставки грузов и себестоимость перевозок. Структура оборота тем лучше, чем выше коэффициент использования грузоподъемности и ниже коэффициент порожнего пробега.
Технико-эксплуатационные показатели использования подвижного состава в транспортном процессе можно разделить на две группы.

Характеристики автомобильного транспорта
К первой группе относятся показатели, характеризующие степень использования подвижного состава:
коэффициенты технической готовности, выпуска и использования подвижного состава;
коэффициенты использования грузоподъёмности и пробега;
среднее расстояние ездки с грузом и среднее расстояние перевозки;
время простоя под погрузкой - разгрузкой, время в наряде; техническую и эксплуатационную скорости.

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

Характеристики автомобильного транспорта

Характеристики автомобильного транспорта

Характеристики автомобильного транспорта

Характеристики автомобильного транспорта

В логистике транспорта важно знатъ, насколько эффективно организован процесс транспортировки грузов. Необходимой информацией для подобных расчетов являются транспортные тарифы.
Транспортный тариф — это цена за перемещение материального объекта в пространстве. Основу транспортных тарифов составляют транспортные общественно необходимые затраты труда по доставке груза. Данные затраты определяют стоимость перевозки, денежным выражением которой является транспортный тариф. Транспортные тарифы включают в себя тарифы на грузовые перевозки и пассажирские тарифы.
ТРАНСПОРТНЫЕ ТАРИФЫ

Транспортный тариф рассчитывается на среднюю дальность перевозки в определенных пределах; средняя дальность перевозки называется тарифным поясом. В расчетах учитываются разница в ценах на топливо и суточные расходы водителей по территориальным зонам. В.качестве основного метода ценообразования используются методы, основанные на затратах. За базу могут браться полные затраты транспортных организаций либо предельные затраты. Большую эффективность дает использование ценовых дискриминаций по географическому, временному и качественному признакам.
ТРАНСПОРТНЫЕ ТАРИФЫ

Железнодорожные транспортные тарифы рассчитываются на основе прейскуранта «Тарифы на грузовые железнодорожные перевозки» № 10-01, который был введен в действие в 1990 г. За основу принята средняя для всех железных дорог себестоимость грузовых перевозок, определяемая в целом по всему грузообороту и по перевозке отдельных грузов в зависимости от дальности пробега.
Система тарифов речного транспорта. Данная система приведена в прейскуранте № 14-01, который введен в действие в 1990 г. Тарифы на перевозку грузов речным транспортом дифференцируются по видам грузов и по видам отправок — судовые, контейнерные, сборные и мелкие. Основные тарифы установлены для судовых отправок. Плата за перевозки в контейнерах устанавливается в расчете на контейнер и зависит от его грузоподъемности без учета фактической загрузки.
ТРАНСПОРТНЫЕ ТАРИФЫ

Тарифы автомобильного транспорта включают в себя надбавки за перевозку грузов в специализированных автомобилях, что связано с более высокой себестоимостью перевозок. Скидки с тарифа применяются для того, чтобы повысить коэффициент использования грузоподъемности автомобиля. На автомобильном транспорте взимаются также сборы за дополнительные операции, связанные с погрузочно-разгрузочными работами, складским обслуживанием, экспедированием грузов и т.д. Перевозки пассажиров и багажа автомобильным транспортом по внутриобластным и межобластным маршрутам регулируются субъектами РФ.
ТРАНСПОРТНЫЕ ТАРИФЫ

Управление процессом транспортировки грузов на практике осуществляется путем использования организованного документирования и документооборота, а также информатизации и компьютеризации всего комплекса транспортных процессов.
В транспортировке грузов используются как общие документы, так и специальные. К специальным документам, использующимся при транспортировке, относится договор перевозки. Договор перевозки содержит информацию о согласии перевозчика перевезти оговоренный в договоре груз до заданного пункта в согласованные сроки, а отправителя — в установленном порядке оплатить работу транспортного перевозчика.
ДОКУМЕНТАЦИОННОЕ ОБЕСПЕЧЕНИЕ ГРУЗОВЫХ ПЕРЕВОЗОК

Для железнодорожного транспорта первичным документом, который имеет силу договора, выступает накладная, составляемая отправителем. Кроме того, в состав необходимого комплекта сопроводительной документации, помимо накладной, входят дорожная ведомость, корешок дорожной ведомости, а также квитанция о приеме груза. Накладная содержит сведения о станции назначения, пути назначения, наименование отправителя и получателя, почтовые адреса, количество погрузочных мест, вид упаковки, массу груза, необходимые данные о вагоне и о норме его загрузки.
Для автомобильного транспорта главным документом является типовой договор на перевозку, а для проведения расчетов заказчика и перевозящей автотранспортной организации обязательно составляется товарно-транспортная накладная. Когда автомобиль выпускается на линию, водитель получает путевой лист.
ДОКУМЕНТАЦИОННОЕ ОБЕСПЕЧЕНИЕ ГРУЗОВЫХ ПЕРЕВОЗОК

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

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

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

Решение задачи линейного программирования

Решение задачи линейного программирования

Решение задачи линейного программирования

Решение задачи линейного программирования

Решение задачи линейного программирования

Решение задачи линейного программирования

Решение задачи линейного программирования

Решение задачи линейного программирования

Решение задачи линейного программирования

Решение задачи линейного программирования

Решение задачи линейного программирования

Задача решена

На рисунке показана транспортная сеть. Под дугами или рядом с ними показана их длина. Нужно найти кратчайшее расстояние от пункта 1 до всех остальных.
Оптимальный путь на транспортной сети

Применим метод потенциалов. Потенциал – это длина кратчайшего путь от начального (первого) пункта до данного. Чтобы быстрее решить задачу, нужно правильно занумеровать пункты. Для нумерации применим следующий алгоритм:
а) начальному пункту присвоим номер 1;
б) выделим пункты, соединенные дугой с уже занумерованными, такие пункты показаны (часть сети) на рисунке.
Оптимальный путь на транспортной сети

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

Результаты нумерации пунктов показаны на рисунке.
Оптимальный путь на транспортной сети

1. Первому пункту присвоить потенциал ноль, остальным бесконечность; потенциалы записать над пунктами.
2. Последовательно просматриваются пункты в порядке возрастания их номеров.
Для очередного пункта пересчитывается его потенциал.
Алгоритм расчета кратчайших путей методом потенциалов

На рисунке показан пункт i, для которого пересчитывается его потенциал, а пункты j, k, m, n – это все пункты соединенные с пунктом i дугами. Над пунктами показаны их потенциалы, причем vi – это ранее определенный потенциал i, – например, бесконечность. Под дугами показаны их длины. Новое значение потенциала i обозначим . В качестве принимается меньшее из значений vi,
Если какой-либо потенциал то, естественно,
Над пунктом нужно записать новое значение потенциала , которое может совпадать с прежним, а под пунктом – номер пункта, из которого получен наименьший потенциал. Это необходимо сделать, чтобы запомнить оптимальный путь.
Алгоритм расчета кратчайших путей методом потенциалов

3. После пересчета потенциалов для всех пунктов, нужно начать процедуру пересчета заново. И делать это до тех пор, пока при очередном пересчете ни один потенциал не изменится, в этом случае расчет завершен. Чем точнее проведена нумерация пунктов, тем скорее (за меньшее количество итераций) сходится решение.
4. Просматривая все пункты, нужно показать стрелками направления кратчайших путей. Для этого используются номера пунктов, записанные под пунктами. Если под пунктом i записан номер j, то стрелка ставится в направлении от j к i.
5. После пересчета потенциалов для всех пунктов, нужно начать процедуру пересчета заново. И делать это до тех пор, пока при очередном пересчете ни один потенциал не изменится, в этом случае расчет завершен. Чем точнее проведена нумерация пунктов, тем скорее (за меньшее количество итераций) сходится решение. Просматривая все пункты, нужно показать стрелками направления кратчайших путей. Для этого используются номера пунктов, записанные под пунктами. Если под пунктом i записан номер j, то стрелка ставится в направлении от j к i.
Алгоритм расчета кратчайших путей методом потенциалов

Алгоритм расчета кратчайших путей методом потенциалов
Как узнать длину и направление кратчайшего пути от начального (1) до любого (например, n) пункта?
Потенциал , записанный над пунктом n, – это длина кратчайшего пути от 1-го до n-го пункта, и наоборот. Двигаясь по стрелкам в обратном направлении от n до 1, восстанавливаем кратчайший путь. Покажем, как производится расчет на сети, изображенной на рисунке.

Алгоритм расчета кратчайших путей методом потенциалов

Результат первой итерации расчета потенциалов показан на рисунке.
Алгоритм расчета кратчайших путей методом потенциалов

Алгоритм расчета кратчайших путей методом потенциалов
Начинаем вторую итерацию.
Снова проходим по всем пунктам в порядке возрастания номеров и пересчитываем потенциалы. Для пунктов 2, 3, 4 потенциалы остаются прежними, а вот для пункта 5 меньший потенциал получается из пункта 6, Изменение потенциала пункта 5 приводит к изменению потенциалов пунктов 7,9,10,11 и 12.

Алгоритм расчета кратчайших путей методом потенциалов
Результаты второй итерации расчета потенциалов показан на рисунке.

Алгоритм расчета кратчайших путей методом потенциалов
Переходим к третьей итерации. Пересчитываем потенциалы, пытаясь их уменьшить. Но ни один потенциал не изменяется. Следовательно, получено оптимальное решение. Теперь расставляем стрелки, показывая направления оптимальных путей. Под пунктом 2 стоит номер 1, ставим стрелку от 1 к 2, и аналогично ставим стрелки для всех пунктов. Например, под пунктом 5 стоит номер 6, значит, стрелка должна быть показана от 6 к 5.
Стрелки показывают оптимальные пути от пункта 1 до всех остальных, но, выбирая оптимальный путь, нужно двигаться в обратном направлении по стрелкам.

Алгоритм расчета кратчайших путей методом потенциалов
Например, нужно определить оптимальный путь между пунктами 1 и 8. Над пунктом 8 стоит потенциал 29 – это длина оптимального пути. От пункта 8 идем в обратном направлении по стрелкам 8-3-1 – это и есть оптимальный путь от 1 до 8 и наоборот. Оптимальный путь от 12 до 1 проходит через пункты 12-11-10-9-7-5-6-3-1, длина пути равна 47.
Результаты проведенных расчетов дают возможность определять оптимальные пути от пункта 1 до всех остальных, и наоборот.

Задача коммивояжера
Задача коммивояжера (ЗК) является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё, как об Великую теорему Ферма обламывали зубы лучшие математики.
Постановка задачи
Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Задача коммивояжера
Чтобы привести задачу к математическому виду, введём некоторые термины. Итак, города перенумерованы числами j=(1,2,3..n). Тур коммивояжера может быть описан циклической перестановкой t=(j1,j2,..,jn,j1), причём все j1,..jn – разные номера; повторяющийся в начале и в конце j1, показывает, что перестановка зациклена. Расстояния между парами вершин Сij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал
cjk jk+1
где jn+1=jn

Задача коммивояжера
Относительно математизированной формулировки ЗК уместно сделать два замечания.
Во-первых, в постановке Сij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех i,j :
Сij>=0; Cjj=∞ *
(последнее равенство означает запрет на петли в туре), симметричными, т.е. для всех i,j:
Сij= Сji **
и удовлетворять неравенству треугольника, т.е. для всех i,j,k:
Сij+ Сjk>=Cik ***

Задача коммивояжера
В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям * - *** не удовлетворяют. Особенно часто нарушается условие ** (например, если Сij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому будем различать два варианта ЗК: симметричную задачу, когда условие ** выполнено, и несимметричную - в противном случае. Условия * - *** по умолчанию будем считать выполненными.

Задача коммивояжера
Второе замечание касается числа всех возможных туров. В несимметричной ЗК все туры t=(j1,j2,..,jn,j1) и t’=(j1,jn,..,j2,j1) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!.
Зафиксируем на первом и последнем месте в циклической перестановке номер j1, а оставшиеся n-1 номеров переставим всеми (n-1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в два раз меньше, т.к. каждый засчитан два раза: как t и как t’.
Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i,j) проведено, если Сij=0 и не проведено, если Сij=1. Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом.

Задача коммивояжера
Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём).
В терминах теории графов симметричную ЗК можно сформулировать так:
Дана полная сеть с n вершинами, длина ребра (i,j)= Сij. Найти гамильтонов цикл минимальной длины.
В несимметричной ЗК вместо «цикл» надо говорить «контур», а вместо «ребра» - «дуги» или «стрелки».

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

Задача коммивояжера. Метод ветвей и границ
Общая идея тривиальна: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу – в задаче минимизации, сверху – в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной.
К идее метода ветвей и границ приходили многие исследователи, но Литтл с соавторами (1965 г.) на основе указанного метода разработали наиболее удачный алгоритм решения ЗК.

Алгоритм Литтла
Коммивояжер должен посетить пять городов, заезжая в каждый город по одному разу. Расстояние между городами следующие: между первым городом и вторым – 12 км, между первым и третьим – 25 км, между первым и четвертым – 16 км, между первым и пятым – 31 км, между вторым и третьим – 28 км, между вторым и четвертым – 35 км, между вторым и пятым – 22 км, между третьим и четвертым – 36 км, между третьим и пятым – 20 км, между четвертым и пятым – 19 км. Его маршрут должен минимизировать суммарную длину пройденного пути.

Алгоритм Литтла
Сначала получим приведенный вид данной матрицы. Для этого пронумеруем строки и столбцы. В каждом столбце определим минимальный элемент и запишем его в нижней строке:
.
.

Алгоритм Литтла
.

Алгоритм Литтла
.

Алгоритм Литтла
.

Алгоритм Литтла
.

Алгоритм Литтла
.

Алгоритм Литтла
.

Алгоритм Литтла
.

Алгоритм Литтла
.

Алгоритм Литтла
.

Алгоритм Литтла
.

Алгоритм Литтла
.

Алгоритм Литтла
.

Алгоритм Литтла
.

Алгоритм Литтла
.