Оптимизация в логистике. Транспортная задача

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Оглавление

 

 

 

 

 

 

 

 

Введение

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Теоретическая часть

1.1. Основы логистики

 

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

Логистическая функция — это укрупненная группа логистических операций.

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

В качестве ключевых логистических функций выделяют:

• поддержание стандартов обслуживания потребителей;
• управление закупками;
• транспортировку;
• управление запасами;
• управление процедурами заказов;
• управление производственными процедурами;
• ценообразование;
• физическое распределение продукции.

Функция поддержания стандартов обслуживания потребителей обеспечивает заданное качество продукции. Распределение товаров и послепродажный сервис — важнейшие задачи логистического менеджмента любой фирмы.

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

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

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

Управление процедурами заказов  — это установление порядка их получения и обработки, определение времени поступления готовой продукции или услуг, координация работ по доставке и продаже готовой продукции потребителям.

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

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

Физическое распределение продукции  — комплексная логистическая функция, составная часть процесса дистрибьюции. Заключается в физическом перемещении и хранении готовой продукции производителями и (или) посредниками.

Далее будут рассмотрены некоторые задачи, решаемые в рамках логистики.

2. Задача о нахождение кратчайшего пути

2.1. Описание задачи и способы решения

 

Задачу о поиске кратчайшего  пути можно решить с помощью теории графов. Существует несколько алгоритмов решения данной задачи, такие как: алгоритм Дейкстры, Алгоритм Беллмана - Форда, алгоритм Флойда - Уоршелла, алгоритм Джонсона, алгоритм Левита. Рассмотрим один из них.

Алгоритм Дейкстры  -  алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.

2.2. Формальное определение

 

Дан  взвешенный  ориентированный граф G(V,E) без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа.

2.3. Неформальное объяснение

 

 

 

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Шаг алгоритма. Если все вершины  посещены, алгоритм завершается. В противном  случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.

3. Транспортная задача

3.1. Определение

 

Одна из самых распространённых задач логистики. Рассмотрим её подробнее.

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

 

	Потребитель B1,  потребность 20 кг	Потребитель B2,  потребность 30 кг	Потребитель B3,  потребность 30 кг	Потребитель B4,  потребность 10 кг
Поставщик A1,  запас 30 кг	С11=2 руб./кг	С12=3 руб./кг	С13=2 руб./кг	С14=4 руб./кг
Поставщик A2,  запас 40 кг	С21=3 руб./кг	С22=2 руб./кг	С23=5 руб./кг	С24=1 руб./кг
Поставщик A3,  запас 20 кг	С31=4 руб./кг	С32=3 руб./кг	С33=2 руб./кг	С34=6 руб./кг

 

Цена перевозки (например, в рублях за 1 килограмм груза) C_ij записывается в ячейки таблицы на пересечении соответствующего потребителя и поставщика (цена может быть и отрицательной — в этом случае она представляет собой прибыль). Неизвестной (искомой) величиной в задаче являются такие объемы перевозки x_ij от поставщиков к потребителям, чтобы минимизировать общие затраты на транспортировку. В табличной записи цены отделяют от объемов перевозки косой чертой или квадратным уголком, в этой статье из соображений лучшей доходчивости они подписаны. При решении транспортной задачи единственными необходимыми арифметическими действиями являются сложение и вычитание. Для поиска начального решения применяют метод северо-западного угла,  метод минимальных тарифов  или метод Фогеля,  а для окончательной оптимизации — метод потенциалов.  В то же время, транспортная задача является подмножеством задач линейного программирования и может решаться симплекс-методом.

3.2. Историческая справка

Проблема была формализована французским  математиком Гаспаром Монжем в 1781 г. По сведениям Alexander Schrijver, первым, кто изучал транспортную задачу математически, был А. Н. Толстой из СССР. В 1930 г. вышла его работа о поиске минимального общего километража в железнодорожных перевозках, где использовались перераспределительные циклы. По сведениям Гасса, задача такого вида в западной литературе впервые была поставлена Хичкоком в 1941 г. и детально разобрана Купмансом, который работал членом Объединенного комитета перевозок во время Второй мировой войны, когда недостаток грузовых судов представлял собой критическое узкое место. Как проблему линейного программирования (детализация симплекс-метода) ее впервые рассмотрел Дж. Данциг. Другой процесс вычисления («метод одновременного решения прямой и двойственной задач») был предложен Фордом и Фулкерсоном в 1956 г. Способ решения транспортной задачи (методом потенциалов) в СССР был опубликован Канторовичем и Гавуриным в 1949 г. и ранее. В своей книге «Линейное программирование, его применения и обобщения» (М.: Соцэкгиз, 1966) Дж. Данциг ссылается на публикации Канторовича 1939 г. и 1942 г., а также последующую статью 1949 г., содержащие, как он считал, в завершенном виде теорию задачи о перевозках, хотя и с неполным вычислительным алгоритмом, написанные на доступном для расчетчиков языке. К сожалению, по его мнению, эти работы оказались малоизвестными в СССР и за его пределами. В противоположность этому, сам Канторович в своих мемуарах 1987 г. утверждал, что университет немедленно опубликовал его статью, и она была разослана в пятьдесят Народных комиссариатов. По сведениям Данцига, для ЭВМ программа симплекс-метода для случая решения транспортной задачи была впервые разработана в 1950 г. для машины СЕАК, а программа для общего симплекс-метода — в 1951 г. под руководством А. Ордена из ВВС США и А. Д. Гофмана из Бюро стандартов.

3.3. Балансировка задачи

 

Если сумма запасов равна сумме потребностей, то транспортная задача называется закрытой. Если равенство не соблюдается, то задача называется открытой. Для решения транспортной задачи необходимо, чтобы она была приведена к закрытому виду.

В показанном выше примере, сумма запасов = 30 + 40 + 20 = 90 кг, а сумма потребностей = 20 + 30 + 30 + 10 кг = 90 кг (запасы и потребности равны между собой, задача закрытая).

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

 

3.4. Поиск начального решения

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

3.5. Метод северо-западного угла

Допустимое (но не всегда оптимальное с точки зрения стоимости  доставки) начальное решение транспортной задачи можно построить, последовательно перебирая строки таблицы (то есть поставщиков) сверху вниз. В пределах каждой строки, нужно перебрать слева направо не охваченных или не полностью охваченных поставками потребителей, записывая в соответствующие ячейки объем поставляемого груза от поставщика в данной строке, и так до исчерпания возможностей поставщика. Таким образом, весь груз от поставщиков будет распределен по потребителям. Этот метод был предложен Данцигом в 1951 г. и назван Чарнесом и Купером «правилом северо-западного угла».

 

 

 

	B1, 20 кг	B2, 30 кг	B3, 30 кг	B4, 10 кг
A1, 30 кг	X11=20 кг	Х12=10 кг
A2, 40 кг		Х22=20 кг	Х23=20 кг
A3, 20 кг			Х33=10 кг	Х34=10 кг

 

В таблице здесь и далее зеленым  цветом отмечены ячейки с ненулевыми объемами перевозки груза (базисные ячейки).