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

Н.Н. Пашков

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

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

МОСКВА 
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 
Тезаурус — термины профессиональной деятельности, определяющие точный смысл специальных понятий.