Транспортная логистика (линейное программирование)

Н.Н. Пашков

ТРАНСПОРТНАЯ 
ЛОГИСТИКА
(ЛИНЕЙНОЕ 
ПРОГРАММИРОВАНИЕ)

 
Учебное пособие

МОСКВА 
2020

УДК 656.02:519.8
ББК 65.37:22.18
 
П 22
 

Рецензенты:
Кузнецов Александр Петрович, доктор технических наук, 
Академик, член Президиума Российской Академии Транспорта, 
Зам. ген. директора «Институт проблем транспорта и логистики» 
(ИПТИЛ ВИНИТИ РАН), Президент Межрегиональной общественной организации «Корпус инженеров путей сообщения» 
(МОО «КИПС»);
Ларин Олег Николаевич, доктор технических наук, профессор.

 
Пашков Н.Н.
П 22  
Транспортная 
логистика 
(линейное 
программирование):  
Учебное пособие / Н.Н. Пашков. — М.: Прометей, 2020. — 202 с.

 
ISBN 978­5­00172­021­8

В учебном пособии рассмотрены матричные методы решения 
классических и вырожденных задач линейного программирования транспортной логистики: минимальный остов сети, кратчайшие пути и маршруты, задача о назначениях, векторная оптимизация плана грузовой работы, экспертиза транспортных систем, 
конфликтные задачи мультимодальных перевозок. Приведены 
необходимые сведения из линейной алгебры, матричного анализа, теории игр и теории графов.
Изучаемые задачи сопровождаются практическими примерами, которые решаются в общедоступной электронной среде 
табличного процессора MS Excel.
В Приложениях даны варианты практических заданий для 
самостоятельного решения задач транспортной логистики студентами 2–3 курса технологических направлений подготовки.
Представляет интерес для широкого круга специалистов, чья 
профессиональная деятельность связана с логистикой транспортных систем.

 
©  Пашков Н.Н., 2020
ISBN 978-5-00172-021-8 
© Издательство «Прометей», 2020

—   3  —

О ГЛ А ВЛ Е Н И Е

ВВЕДЕНИЕ  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6

1. ОСНОВЫ  ТРАНСПОРТНОЙ  ЛОГИСТИКИ . . . . . . . . 10
1.1. Объекты логистики . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2. Термины логистики  . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3. Правила логистики . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4. Задачи транспортной логистики . . . . . . . . . . . . . . 20

2. МОДЕЛИ ЗАДАЧ ЛИНЕЙНОГО  
ПРОГРАММИРОВАНИЯ  . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1. Задачи линейного программирования  . . . . . . . . . 25
2.1.1. Оптимизация производственного плана . . . . 25
2.1.2. Целочисленное линейное  
программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.1.3. Задача о назначениях . . . . . . . . . . . . . . . . . . . . . 29
2.1.4. Кратчайшие пути . . . . . . . . . . . . . . . . . . . . . . . . 31
2.1.5. Минимальный остов сети . . . . . . . . . . . . . . . . . 32
2.2. Формы записи задач линейного  
программирования . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3. Матричная модель задачи линейного 
программирования . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4. Решение систем линейных уравнений  . . . . . . . . . 37
2.5. Решение систем линейных неравенств . . . . . . . . . 43
2.5.1. Основная теорема о линейных  
неравенствах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

—   4   —

Оглавление

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО 
ПРОГРАММИРОВАНИЯ  . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.1. Симплекс­метод  . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.1.1. Алгебра симплекс-метода . . . . . . . . . . . . . . . . . 50
3.1.2. Признак неограниченности целевой  
функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.2. Метод Мура­Пенроуза  . . . . . . . . . . . . . . . . . . . . . . 58
3.3. Общая задача линейного программирования . . . . 62
3.3.1. Двойственность задач линейного 
программирования  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.4. Алгебраический метод решения вырожденных  
задач линейного программирования . . . . . . . . . . . 65

4. СЕТЕВЫЕ ЗАДАЧИ ТРАНСПОРТНОЙ  
ЛОГИСТИКИ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.1. Классическая транспортная задача . . . . . . . . . . . . 73
4.2. Транспортная задача с промежуточными  
пунктами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.3. Задача коммивояжера  . . . . . . . . . . . . . . . . . . . . . . 80

5. ИНТЕГРИРОВАННЫЕ  ЗАДАЧИ   
ТРАНСПОРТНОЙ ЛОГИСТИКИ . . . . . . . . . . . . . . . . . . . . 83
5.1. Транспортно­складская задача  . . . . . . . . . . . . . . . 83
5.2. Декомпозиция сложных объектов  
транспортной логистики  . . . . . . . . . . . . . . . . . . . . 84
5.3. Векторная оптимизация плана перевозок . . . . . . . 87
5.4. Векторная оптимизация плана грузовой  
работы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.5. Аналитическая экспертиза транспортных  
систем  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.5.1. Критерий эффективности работы  
транспорта  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.5.2. Постановка задачи экспертизы  
транспортных систем . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.5.3. Матричная модель  задачи экспертизы . . . . . 98
5.5.4. Алгебраический метод экспертизы 
транспортных систем . . . . . . . . . . . . . . . . . . . . . . . . . . 98

—   5  —

Оглавление

6. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ ТРАНСПОРТНОЙ 
ЛОГИСТИКИ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.1. Минимальный остов транспортной сети . . . . . . . 102
6.1.1. Алгоритм поиска минимального  
остовного дерева графа  . . . . . . . . . . . . . . . . . . . . . . . .103
6.1.2. Алгебраическое решение задачи поиска 
минимального остова сети . . . . . . . . . . . . . . . . . . . . .111
6.2. Оптимальный план работы погрузчиков . . . . . . . 115
6.3. Оптимальный план перевозок . . . . . . . . . . . . . . . 120
6.4. Транспортная задача с промежуточными  
пунктами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
6.5. Кратчайшие пути . . . . . . . . . . . . . . . . . . . . . . . . . 130
6.6. Кратчайший кольцевой маршрут  . . . . . . . . . . . . 135

7. ОСНОВЫ ТЕОРИИ ИГР  . . . . . . . . . . . . . . . . . . . . . . . . 142
7.1. Матричные игровые задачи . . . . . . . . . . . . . . . . . 142
7.2. Особенности платежной матрицы игры  . . . . . . . 144
7.3. Оптимальная цена игры . . . . . . . . . . . . . . . . . . . . 146

8. КОНФЛИКТНЫЕ ЗАДАЧИ МУЛЬТИМОДАЛЬНЫХ 
ПЕРЕВОЗОК  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
8.1. Метод обратной платежной матрицы  . . . . . . . . . 149
8.2. Метод псевдообратной платежной матрицы . . . . 153
8.3. Пример решения матричной игровой задачи . . . 154

ПРИЛОЖЕНИЯ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
Приложение 1. Элементы матричного анализа . . . . . 160
Приложение 2. Элементы теории графов . . . . . . . . . . 167
Приложение 3. Оптимальный план работы  
погрузчиков  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
Приложение 4. Транспортная задача логистики 
снабжения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
Приложение 5. Транспортная задача логистики  
сбыта . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
Приложение 6. Кратчайшие пути, остовы  
и маршруты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

ЛИТЕРАТУРА  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198

—   6   —

В В Е Д Е Н И Е

Do not put all your eggs in a basket.

Принципы логистики с древних времен использовались в различных сферах деятельности человека для 
организации материального обеспечения торговых караванов, военных операций, государственных планов 
и других крупномасштабных мероприятий.
В настоящее время логистический подход широко применяется в сфере экономики. В экономике под 
логистикой понимается планирование, организация 
и управление материальными, и связанными с ними 
информационными, финансовыми и сервисными потоками в сфере производства и обращения товаров с целью оптимизации использования всех видов ресурсов.
Рисунок В.1 демонстрирует иерархическую структуру взаимосвязей предметных и функциональных областей экономической логистики [9, 23].
Начало широкого применения принципов логистики в экономике приходится на 60–70­е годы 
ХХ века. Обусловлено это тем, что появившиеся информационные технологии сквозного мониторинга всех 
этапов движения сырья, полуфабрикатов и готовой 
продукции в цепях поставок, позволили выявить ряд 
общих проблем, совместное решение которых дает значительную экономию ресурсов.

—   7  —

Введение

4 
 

Рисунок В.1 демонстрирует иерархическую структуру взаимосвязей 

предметных и функциональных областей экономической логистики [9, 23]. 

 

Рисунок В.1. Структура логистики 

Рисунок В.1. Структура логистики

—   8   —

Введение

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

—   9  —

Введение

исследования операций для решения прикладных задач 
транспортной логистики требует привлечения знаний 
и математиков, и специалистов предметной области.
Эффективные инструменты исследования задач 
транспортной логистики дают методы линейной алгебры [8, 25, 34], теории графов [6, 13] и матричного 
анализа [3, 28, 29], которые широко используются 
в цифровых технологиях решения профессиональных 
задач транспортной логистики. Основные элементы линейной алгебры, теории графов и матричного анализа, 
необходимые для понимания изучаемых задач, приведены в учебном пособии.

—   10   —

1. О С Н О В Ы Т РА Н С П О Р Т Н О Й 

Л О Г И СТ И К И

1.1. Объекты логистики

Основным объектом1 логистики является материальный поток — направленное движение множества 
однородных объектов. Понимание точного смысла 
слова поток позволяет избежать семантических ошибок 
в определении тезауруса2 логистики.
Смысл слова поток совпадает во многих языках 
(лат. processus, греч. χείμαρρος, англ. torrent, stream, 
обще-славянск. поток). Поток понимается в этих языках как процесс, ход, течение, ток — направленное движение множества объектов.
Для уточнения смысла термина поток, приведем 
физическое определение потока сплошной среды — 
жидкости. Плотность потока j  (кг/м2·с) векторного поля 
жидкости, плотность которой ρ (кг/м3), определяется 

1 
Объе́кт (лат. objectum — предмет) — явление или процесс, на которое направлена практическая и познавательная деятельность 
субъекта (наблюдателя).

2 
Тезаурус — термины профессиональной деятельности, определяющие точный смысл специальных понятий.

—   11  —

1.1. Объекты логистики

в пространстве векторным полем скорости v = v(x, y, z) 
(м/с) течения:
                                                  
.
= ρ⋅
j
v                                                                 
                                       (1.1)
Для ламинарного режима, количество жидкости, 
которое протечёт за единицу времени через поверхность S, будет равно потоку I (кг/с):

                                                
,
d
= ∫∫
I
j S                                                              
                                     (1.2)

где двойной интеграл вычисляют на поверхности S 
с бесконечно малым приращением dS.
Если жидкость в потоке не претерпевает фазовых 
превращений, то плотность жидкости ρ и плотность j  
потока I связаны уравнением неразрывности:

                                            

(
 
 
0,                                                          1.
div
t
∂ρ +
=
∂
j
                               (1.3)

где div  — дивергенция3 плотности потока j. 
В декартовом пространстве (0, x, y, z) дивергенция 

div  плотности потока  j определяется оператором набла 
∇ :

                                            

(
 
.                                          1.4
y
x
z
j
j
j
div
x
y
z
∂
∂
∂
= ∇ =
+
+
∂
∂
∂
j
j
                           (1.4)

Таким образом, в физическом смысле поток — 
это непрерывное направленное движение множества 
однородных объектов. 
В отличие от непрерывных физических потоков 
сплошных сред, потоки в экономике — дискретные4. 
Такие потоки принято называть логистическими.

3 
Дивергенция (лат. divergere) — расширение, расхождение.

4 
Дискре́тность (лат. discretus) — разделённый, прерывистый) — 
прерывность, свойство, противопоставляемое непрерывности.

—   12   —

1. Основы транспортной логистики

Мера материального потока — скорость, представляет собой дробь, в числителе которой указана единица 
измерения продукции, имеющей вещественную форму 
(штуки, тонны, 
3
ì ), а в знаменателе — единица измерения времени (час, сутки, месяц, год). Например, 
3 /
ì
÷àñ, 
вагонов/сутки, контейнеров/смену, тонн/год, и т.д.

1.2. Термины логистики

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

—   13  —

1.2. Термины логистики

компенсирующие издержки на реализацию логистических операций с материальными и информационными 
потоками, формируют финансовые потоки. 
Унификация логистических операций с позиции 
удовлетворения коммерческих интересов всех сторон — 
участников товародвижения, обеспечивает формирование потока как объекта логистики. Формирование 
потока дает возможность выделить в составе общего 
процесса обеспечения потребителя три типа процессов: 
− технологические, преобразующие материальный поток;
− транспортные, 
формирующие 
направленное 
движение объектов материального потока;
− информационные, сопровождающие все логистические операции.
Логистическая процедура — это обособленная последовательность логистических операций, изменяющих состояние объектов в потоке. Например, упаковка, 
маркировка тарно­штучных грузов.
Логистический процесс — упорядоченная группа 
функционально взаимосвязанных логистических процедур, например, погрузка/выгрузка, взвешивание, 
сортировка, пакетирование и складирование грузов.
Логистическая функция — группа логистических 
процессов, реализующих полный цикл преобразования 
материальных и связанных с ними информационных, 
финансовых и сервисных потоков.
В состав логистических функций включаются шесть 
логистических процессов (групп логистических процедур): сбор заказов, управление закупками, складирование, грузопереработка, пакетирование и перевозка. 
Логистическое звено — функционально обособленный объект, реализующий логистический процесс.