Модели оптимизации в логистических системах

В соответствии с [1] логистическая система – относительно устойчивая совокупность звеньев (структурных подразделений компании, а также поставщиков, потребителей и логистических посредников), взаимосвязанных и объединенных единым управлением логистическим процессом для реализации корпоративной стратегии организации бизнеса. Среди основных логистических стратегий можно указать стратегию минимизации общих затрат на логистику или стратегию максимизации уровня качества логистического сервиса. Количественная оценка стратегий в информационных системах управления проводиться с использованием соответствующий оптимизационных моделей.

Типичными задачами логистических систем является рациональная организация движения материальных потоков по схемам «поставщики– склады - производители», «поставщики - производители» и движения готовой продукции в товаропроводящих сетях по схемам «производители – склады – потребители готовой продукции», «производители – потребители готовой продукции».

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

Формально задача формулируется следующим образом. Имеются пункты производства некоторого вида продукции  с производственными мощностями a_i и пункты потребления этого вида продукции  с потребностями b_j, причем суммарные мощности поставщиков превышают суммарные потребности потребителей . Поставщики и потребители связаны между собой системой транспортных коммуникаций с расстоянием t_ij. Требуется прикрепить потребителей к поставщикам  таким образом, чтобы транспортная работа по доставке данного вида продукции в логистической системе была минимальной.

Для описания модели введем переменные, в качестве которых выступают x_ij - объем перевозок продукции от i-го поставщика j-му потребителю.

В этих обозначениях базовая модель транспортной задачи запишется следующим образом:

минимум суммарной транспортной работы по доставке продукции в логистической системе

                                                                                      (8.49)

при выполнении баланса распределения продукции каждого поставщика

                                                                               (8.50)

при выполнении баланса удовлетворения потребностей каждого потребителя

                                                                                (8.51)

при выполнении запрета на обратные поставки

                                                                        (8.52)

Модель (8.49)-(8.52) представляет собой открытую транспортную задачу.

Пример 8.8. Для хранения одного вида сырья используется три склада А1, А2, А3, мощность которых определяется соответственно объемами 1800т, 900т, 1000т. В предстоящем периоде эти склады должны отправлять груз четырем предприятиям В1, В2, В3, В4, потребность которых в сырье характеризуется объемами 900т, 1000т, 1200т, 600т. Расстояние между предприятиями и складами приведено в табл.

Таблица 8.10. Расстояние между складами и предприятиями (км) (пример 8.8.)

	В1	В2	В3	В4
А1	6	8	5	4
А2	9	7	4	5
А3	7	7	8	9

Определить оптимальный вариант прикрепления потребителей к поставщикам, чтобы объем транспортной работы был минимальным.

Решение. Для формального описания модели введем  переменные x_ij - объем перевозки продукции с i -го склада на j-е предприятие  

В рамках этих обозначений модель транспортной задачи запишется:

минимум транспортной работы по доставке груза со всех складов на все предприятия

при ограничениях на запасы продукции на трех складах

и необходимости удовлетворения потребности каждого предприятия в продукции

и неотрицательности переменных

После решения задачи на компьютере (процедура «Поиск решения» системы Excel ) получаем следующий оптимальный план поставок:

Таблица 8.11. Оптимальный план поставок продукции (т) (пример 8.8)

	В1	В2	В3	В4
А1	900	0	300	600
А2	0	0	900	0
А3	0	1000	0	0

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

 

 

Рис. 8.12 Вариант прикрепления потребителей к поставщикам, соответствующий цели «минимум транспортной работы».

При таком варианте прикрепления объем транспортной работы составляет 19900 ткм.

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

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

Формально задача прикрепления потребителей к поставщикам в условиях многономенклатурного производства при условии взаимозаменяемости номенклатуры формулируется следующим образом. Имеются пункты производства , в которых производятся  видов взаимозаменяемой продукции с производственными мощностями a^k_i и пункты потребления этой продукции  с потребностями , причем часть потребности  должна быть удовлетворена поставками  -го вида продукции, при этом , также . Поставщики и потребители связаны между собой системой транспортных коммуникаций с расстоянием t_ij . Требуется прикрепить потребителей к поставщикам таким образом, чтобы транспортная работа по доставке данного вида продукции в логистической системе была минимальной.

Для описания модели введем переменные, в качестве которых выступают x^k_ij - объем перевозок k-го вида продукции от i-го поставщика j-му потребителю.

В этих обозначениях базовая модель транспортной задачи запишется следующим образом:

минимум суммарной транспортной работы по доставке продукции в логистической системе

                                                                                 (8.53)

при выполнении баланса распределения продукции каждого поставщика

                                                                       (8.54)

при выполнении баланса удовлетворения потребностей каждого потребителя по видам продукции

,                                                           (8.55)

при выполнении запрета на обратные поставки

,                                                 (8.56)

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

Пример 8.9 . Суточная производственная мощность кирпичного завода А₁ составляет: кирпич силикатный 3 млн.шт., кирпич глиняный – 4 млн.шт. Суточная производственная мощность кирпичного завода А₂ составляет: кирпич силикатный 5 млн.шт., кирпич глиняный – 2 млн.шт. Кирпич должен быть вывезен на два строительных объекта: на объект В₁ необходимо поставить 2 млн.шт. кирпича силикатного, 3 млн.шт. кирпича глиняного, 2 млн.шт. - кирпич любой, на объект В₂ необходимо поставить 1 млн.шт. кирпича силикатного, 2 млн.шт. кирпича глиняного, 4 млн.шт. - кирпич любой. Расстояние между заводами и строительными объектами представлено в следующей таблице:

Таблица 8.12. Расстояние между заводами и строительными объектами(км)

Поставщики	Потребители
	В1	В2
А1	10	15
А2	20	10

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

Решение. Каждого поставщика А₁, А₂ разобьём на два условных поставщика (А₁^г А₁^с), (А₂^г А₂^с), которые поставляют соответственно глиняный и силикатный кирпич. Каждого потребителя В₁, В₂ разобьём на три условных потребителя (В₁^г В₁^с В₁^л), (В₂^г В₂^с В₂^л), которые потребляют соответственно глиняный, силикатный, и любой кирпич. В соответствии с этим разбиением составим матрицу расстояний, заблокировав заведомо большими числами маршруты, по которым поставка не может быть осуществлена.

Таблица 8.13. Матрица расстояний с учетом взаимозаменяемости материалов (км)

Поставщики	Потребитель В1			Потребитель  В2
	В1с	В1г	В1л	В2с	В2г	В2л
А1с	10	М	10	15	М	15
А1г	М	10	10	М	15	15
А2с	20	М	20	10	М	10
А2г	М	20	20	М	10	10

 

Ориентируясь на данную матрицу расстояний, введем обозначения модели: - поставка от i-го условного поставщика j-му условному потребителю,  Заметим, что поскольку суммарные мощности поставщиков (3+4+5+2=14) равны суммарным потребностям потребителей (2+3+2+1+2+4=14), имеем закрытую транспортную задачу В этих обозначениях модель задачи будет иметь вид:

Ограничения на мощности заводов по производству силикатного кирпича:

Ограничения на мощности заводов по производству глиняного кирпича:

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

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

величина поставок не может быть отрицательной величиной:

Целевая функция характеризует минимум транспортной работы по перевозке грузов от всех поставщиков всем потребителям:

 Результатом решения модели является следующий оптимальный план поставок:

Таблица 8.14. Оптимальный план поставок

Поставщики	Потребитель В1			Потребитель  В2
	В1с	В1г	В1л	В2с	В2г	В2л
А1с	2		1
А1г		3	1
А2с				1		4
А2г					2

 

Из оптимального плана видно, что потребитель В₁ обеспечивается кирпичом от поставщика А₁, а потребитель В₂ - от А₂.

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

 

 

Рис. 8.13 Вариант прикрепления потребителей к поставщикам, соответствующий цели «минимум транспортной работы».

 

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

В этом случае формально задача  прикрепления потребителей к поставщикам при организации движения материальных потоков по схеме «поставщики – склады – производители» («производители – склады – потребители») формулируется следующим образом. Имеются пункты производства некоторого вида продукции  с производственными мощностями a_i и пункты потребления этого вида продукции  с потребностями b_j, причем суммарные мощности поставщиков превышают суммарные потребности потребителей . Поставщики и потребители связаны между собой через систему складов  с емкостью    , причем . Производители и склады, склады и потребители связаны между собой системой транспортных коммуникаций с расстоянием соответственно t_ir , t_rj . Требуется прикрепить потребителей к складам и склады к поставщикам таким образом, чтобы транспортная работа по доставке данного вида продукции в логистической системе была минимальной.

Для описания модели введем переменные, в качестве которых выступают x_ir - объем перевозок от i-го поставщика на r-й склад, y_rj - объем перевозок с r-го склада j -му потребителю, x_r - неиспользованная емкость r -го склада.

В этих обозначениях базовая модель транспортной задачи запишется следующим образом:

минимум суммарных транспортных затрат по доставке груза от поставщиков на склады и со складов на предприятия

при выполнении ограничений по вывозу продукции от каждого поставщика

при выполнении ограничения по использованию емкости склада

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

 

при условии удовлетворения потребности каждого потребителя

при условии запрета на обратные перевозки

при ограничении на недоиспользованные емкости складов

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

Пример 8.10.  Имеются три поставщика груза (А,Б,В) соответственно мощностью 2500т 1200т и 1100т и четыре потребителя (I, II, III, IV), потребность которых составляет соответственно 900т, 1000т, 1200т, 600т. Между поставщиками и потребителями отсутствуют прямые транспортные коммуникации. Сначала поставки осуществляются автомобильным транспортом, затем груз отгружается на склад и со склада доставляется потребителям железнодорожным транспортом. В наличии имеется два склада (1,2) емкостью соответственно 2500т и 3000т каждый. В таблице приведены расстояния между поставщиками и складами и между складами и потребителями.

Таблица 8.15. Расстояние между поставщиками и складами

Поставщики и потребители	Склады
	1	2
А	23	30
Б	18	25
В	31	22
I	100	400
II	300	220
III	200	300
IV	150	120

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

Решение. В задаче в качестве поставщиков выступают пункты производства А, Б, В и склады 1,2. В качестве потребителей – пункты потребления I, II, III, IY и склады 1,2. В соответствии с этим разбиением составим матрицу расстояний, заблокировав заведомо большими числами маршруты, по которым поставка не может быть осуществлена.

Таблица 8.16. Матрица расстояний (км)

	I	II	III	IY	1	2
А	М	М	М	М	23	30
Б	М	М	М	М	18	25
В	М	М	М	М	31	22
1	100	300	200	150	0	М
2	400	220	300	120	М	0

 

Ориентируясь на данную матрицу расстояний, введем обозначения модели: - поставка от i-го условного поставщика j-му условному потребителю,  В этих обозначениях модель задачи будет иметь вид:

Ограничения со стороны мощностей поставщиков:

, , , , ;

 

Ограничения со стороны потребностей потребителей:

, , , , , ;

Целевая функция характеризует минимум транспортной работы по перевозке грузов от всех поставщиков всем потребителям:

 Результатом решения модели является следующий оптимальный план поставок:

 

 

Таблица 8.17. Оптимальный план поставок  (т)

	I	II	III	IY	1	2
А					1400
Б					700	500
В						1100
1	900		1200		400
2		1000		600		1400

 

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

 

Рис. 8.14. Формирования логистической системы, соответствующий цели «минимум транспортной работы».

 

Из решения задачи видно, незагруженная мощность первого склада 400т, второго – 1400.

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

Формально задача формулируется следующим образом. Осуществляется развозка некоторого вида груза из базового пункта  по нескольким пунктам , связанным между собой автомобильными дорогами с расстоянием - расстояние от i–го пункта до j -го пункта . В каждом пункте  автомобиль должен побывать ровно один раз и после развозки всех грузов ему необходимо вернуться в базовый пункт. Задача состоит в определении порядка посещения автомобилем пунктов  так, чтобы суммарное расстояние, проходимое автомобилем, было минимальным.

Для формального описания модели

Введем переменные:

.

Экономический смысл переменной состоит в том, что если , то в маршрут включается звено ( i , j ).

В этих обозначениях модель запишется:

Целевая функция описывает, что длина маршрута автомобиля подлежит минимизации:

При ограничительных условиях:

автомобиль заезжает в пункт j только один раз

.

автомобиль выезжает из пункт i  только один раз

.

не допускается расщепление замкнутого из n+1 звеньев маршрута автомобиля на несколько замкнутых маршрутов меньшего числа звеньев

Сформулированная задача в математике известна как задача коммивояжера. Заметим, что в этой задаче в качестве неизвестных, кроме переменных , выступают переменные .

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

Пример 8.11. Определить порядок объезда автомобилем из пункта А пунктов  с тем, чтобы обеспечить минимальную длину маршрута. Расстояние между пунктами представлено в табл.

Таблица 8.18. Матрица расстояний между пунктами

	А
А	-
	6	-
	1	9	-
	4	3	5	-
	5	4	7	3	-

Решение. В качестве переменных выступают которые описывают включение звена (i,j) в маршрут, а также переменные  Матрицу переменных удобно представить в следующем виде:

 

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

 

	А
А	100	6	1	4	5
	6	100	9	3	4
	1	9	100	5	7
	4	3	5	100	3
	5	4	7	3	100

 

Приведем в этих переменных формализованное описание модели.

Длина маршрута автомобиля описывается следующей целевой функцией:

 

При ограничениях:

После реализации модели на компьютере в системе Excel с помощью функции Поиск решения, получим следующее решение:

	=3	=4	=2	=5	=1
=3	0	1	0	0	0
=4	0	0	0	1	0
=2	1	0	0	0	0
=5	0	0	0	0	1
=1	0	0	1	0	0

Длина кратчайшего маршрута составила 17 км, порядок объезда пунктов на маршруте следующий: А .

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