Алгоритм решения транспортно-складской задачи

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

Рисунок 1 – Общая схема процесса постановки и решения задач

оптимизации в форме диаграммы деятельности языка UML

Таким образом, отдельными этапами процесса постановки и решения задач оптимизации являются:

1. Анализ проблемной ситуации.

2. Построение математической модели.

3.Анализ модели.

4. Выбор метода и средства решения.

5. Выполнение численных расчетов.

6. Анализ результатов расчетов.

7. Применение результатов расчетов.

8. Коррекция и доработка модели.

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

1. Анализ проблемной ситуации

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

2. Построение математической модели

Рассмотрим математическую постановку задачи. Определим двоичные переменные решения и положим , если склад j арендуется, и в противном случае.

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

− ежемесячная стоимость аренды j-го склада;

– количество автофургонов, отправленных со склада j в регион i;

– средние транспортные издержки на отправку одного автофургона со склада j в регион i;

– пропускная способность (мощность) j-го склада;

– спрос i-го региона (рынка).

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

(1)

Первое ограничение в (1) – это ограничение по пропускной способности (мощности) складов. Если , то со склада j невозможно отправить ни один автофургон. Второе ограничение в (1) гарантирует удовлетворение спроса в i-м регионе. Третье и четвертое ограничения – традиционные для классической транспортной задачи ограничения на неотрицательность и целочисленность переменных . Последнее ограничение указывает, что переменная должна быть двоичной.

Графически данная модель представлена на рисунке 2.

Рисунок 2 – Граф транспортно-складской задачи

Модель задачи размещения центров распределения подробно рассмотрена в монографии Дж. Шапиро.^[1] В стандартном виде этой задачи дистрибьюторская компания должна создать сеть распределительных центров, из которых она будет поставлять свою продукцию на свои рынки с целью удовлетворения прогнозируемого спроса на следующий год. Цель – минимизировать сумму складских и транспортных издержек при поддержании приемлемого уровня обслуживания покупателей. Хотя это и является задачей стратегического планирования, предполагается, что спрос на следующий год известен и постоянен. Во многих случаях маркетологи компании определяют план маркетинга и продаж, не учитывая при этом логистических последствий. Данный план передается менеджерам по логистике, которые отвечают за то, чтобы продукция доставлялась на рынки вовремя и с низкими затратами.

3. Анализ модели

На переменные модели накладываются ограничения целочисленности и неотрицательности, а на переменные модели накладывается ограничение двоичности, следовательно, данная модель относится к классу смешанного линейного программирования.

4. Выбор метода и средства решения

На выбор метода и средства оказывает влияние характер математической мо­дели и математические свойства множества допустимых альтернатив. В качестве метода решения данной задачи используется надстройка Поиск решения, входящая в поставку MS Excel. Средство Поиск решения позволяет оптимизировать линейные и нелинейные модели. Линейность модели позволяет использовать в средстве Поиск решения алгоритм симплекс-метода, который правильно работает только для формул, отражающих линейные взаимосвязи между переменными.

5. Выполнение численных расчетов

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

1) формирование конкретных значений исходных данных (значений коэф­фициентов ограничений и целевой функции) и их ввод в специальном формате на отдельный рабочий лист MS Excel;

2) задание свойств алгоритма расчета и параметров поиска решения MS Excel;

3) выполнение расчетов с целью получения решения в форме конкретных значений переменных модели;

4) представление результатов расчетов в графической форме (если это требуется для их наглядной интерпретации).

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

6. Анализ результатов расчетов

Цель данного этапа заключается в анализе точности и правильности полу­ченных результатов, если поиск решения MS Excel закончился успешно. При этом возможна следующая последовательность действий:

1) оценка точности и верификация полученных результатов на основе про­верки согласованности отдельных компонентов вычислительных расчетов с использованием аналитической модели и ручного просчета;

2) интерпретация полученных результатов в форме управляющих воздейст­вий или альтернатив решения исходной проблемы;

3) оценка потенциальной возможности реализации полученных результатов применительно к системе-оригиналу.

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

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

Задание

Компания ОАО «ПЕТМОЛ», занимающаяся производством и реализацией молока и молочных продуктов потребителям в Санкт-Петербурге и Ленинградской области, располагает тремя распределительными центрами (терминалами), расположенными по следующим адресам:

- терминал «Центр» − Московский пр., 65 (склад готовой продукции Санкт-Петербургского молочного комбината №1 ОАО «ПЕТМОЛ»);

- терминал «Север» − 6-й Верхний пер., 1 (промышленная зона «Парнас»);

- терминал «Сервис» − 4-й Предпортовый проезд, 5.

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

Таблица 1 – Спрос потребителей i-го рынка D_i, ед.

Потребители	Поставщики	Спрос i-го рынка Di, ед.
Сервис	Центр	Север
Потоки xi,j, ед.
Адмиралтейский район	x1,1	x1,2	x1,3
Васильевский остров	x2,1	x2,2	x2,3
Колпино	x3,1	x3,2	x3,3
Красное село	x4,1	x4,2	x4,3
Ломоносов	x5,1	x5,2	x5,3
Металлострой	x6,1	x6,2	x6,3
Московский район	x7,1	x7,2	x7,3
Невский район	x8,1	x8,2	x8,3
Невский район (левый берег)	x9,1	x9,2	x9,3
Павловск	x10,1	x10,2	x10,3
Петроградская сторона	x11,1	x11,2	x11,3
Петродворцовый район	x12,1	x12,2	x12,3
Пушкин	x13,1	x13,2	x13,3
Фрунзенский район	x14,1	x14,2	x14,3
Центральный район	x15,1	x15,2	x15,3
Продолжение таблицы 1
Шушары	x16,1	x16,2	x16,3
Кировский район	x17,1	x17,2	x17,3
Красносельский район	x18,1	x18,2	x18,3
Васкелово	x19,1	x19,2	x19,3
Всеволожск	x20,1	x20,2	x20,3
Выборг	x21,1	x21,2	x21,3
Выборгский район	x22,1	x22,2	x22,3
Зеленогорск	x23,1	x23,2	x23,3
Калининский район	x24,1	x24,2	x24,3
Красногвардейский район	x25,1	x25,2	x25,3
Кронштадт	x26,1	x26,2	x26,3
Кузьмолово	x27,1	x27,2	x27,3
Ольгино	x28,1	x28,2	x28,3
Первомайское	x29,1	x29,2	x29,3
Песочное	x30,1	x30,2	x30,3
Приморск	x31,1	x31,2	x31,3
Приморский район	x32,1	x32,2	x32,3
Приозерск	x33,1	x33,2	x33,3
Репино	x34,1	x34,2	x34,3
Рощино	x35,1	x35,2	x35,3
Сертолово	x36,1	x36,2	x36,3
Сестрорецк	x37,1	x37,2	x37,3
Советский	x38,1	x38,2	x38,3
Солнечное	x39,1	x39,2	x39,3
Сосново	x40,1	x40,2	x40,3
Токсово	x41,1	x41,2	x41,3
Пропускная способность j-го склада	S1	S2	S3

Для осуществления доставки своей продукции потребителям ОАО «ПЕТМОЛ» использует арендованный подвижной состав, стоимость аренды зависит от сектора развозки и от грузоподъемности подвижного состава. Поскольку перевозки мелкопартионные, то используется малотоннажный подвижной состав, в основном автомобили ГАЗ-3302 «Газель», грузоподъемностью 1,5 тонны. Тарифы, которые используются при расчете с перевозчиками за доставку товара, представлены в таблице 2.

Таблица 2 – Тарифы за доставку грузов автомобильным транспортом c_i,j, руб.

Регион	Распределительные центры
Сервис	Центр	Север
Адмиралтейский район
Васильевский остров
Колпино
Красное село
Ломоносов
Металлострой
Московский район
Невский район
Невский район (левый берег)
Павловск
Петроградская сторона
Петродворцовый район
Пушкин
Фрунзенский район
Центральный район
Шушары
Кировский район
Красносельский район
Васкелово
Всеволожск
Выборг
Выборгский район
Зеленогорск
Калининский район
Красногвардейский район
Кронштадт
Кузьмолово
Ольгино
Первомайское
Песочное
Приморск
Приморский район
Приозерск
Репино
Рощино
Сертолово
Сестрорецк
Советский
Солнечное
Сосново
Токсово

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

Предположим, что компания располагает одним собственным складом (терминал «Центр») и два склада арендует (терминалы «Сервис» и «Север»). Ежемесячная стоимость аренды складов, постоянные затраты на содержание собственного склада и пропускная способность складов выбираются в соответствии с вариантами индивидуальных заданий из Приложения Г. Затраты на складские операции на каждую грузовую отправку (комплектация и погрузка заказа) составляют 550 руб. Предположим также, что из терминала «Центр» мы можем осуществлять прямые поставки товара всем потребителям.

Необходимо оценить целесообразность аренды дополнительных складских площадей путем построения и оптимизации транспортно-складской модели компании ОАО «ПЕТМОЛ».

Порядок выполнения работы

1. Построить математическую модель данной задачи.

2. С помощью программы MS Excel создать новую рабочую книгу.

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

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

5. Создать сценарии поиска решения для различных наборов исходных данных.

6. Оптимизировать модель, т.е. получить решения для различных сценариев поиска решения.

7. Проанализировать полученное решение, составив сводную таблицу результатов решения по различным сценариям.

8. Сделать вывод о целесообразности аренды складских площадей для компании ОАО «ПЕТМОЛ».

Пример

Построить и оптимизировать транспортно-складскую модель компании ОАО «ПЕТМОЛ» при следующих исходных данных:

− стоимость аренды склада в промзоне «Парнас» (терминала «Север») составляет 1 млн. рублей ежемесячно;

− стоимость аренды склада в Московском районе (терминала «Сервис») − 750 тыс. рублей ежемесячно;

− постоянные затраты на содержание собственного склада составляют 1,5 млн. руб. ежемесячно;

− пропускная способность терминала «Центр» неограниченна, т.е. равна спросу потребителей всех регионов;

− пропускная способность терминала «Сервис» составляет 1800 грузовых отправок;

− пропускная способность терминала «Север» – 2500 грузовых отправок в течение месяца.

Затраты на складские операции на каждую грузовую отправку (комплектация и погрузка заказа) составляют 550 руб. Предположим также, что из терминала «Центр» мы можем осуществлять прямые поставки товара всем потребителям.

Решение

1. Поскольку при решении транспортно-складской задачи для компании ОАО «ПЕТМОЛ» необходимо учесть затраты на складские операции на каждую грузовую отправку , то целевая функция данной задачи принимает вид:

(2)

при ограничениях

(3)

Первые три неравенства в (3) – это ограничения по пропускной способности терминалов «Сервис», «Центр» и «Север» соответственно. Далее идут ограничения по спросу в соответствующих регионах. Равенство здесь означает, что спрос потребителей в каждом регионе должен быть полностью удовлетворен. Смысл последних трех ограничений очевиден и соответствует аналогичным ограничениям в (1).

2. С помощью программы MS Excel создадим новую рабочую книгу.

3. Исходные данные сформулированной выше задачи представлена на рисунках 3 и 4. Здесь мы видим, что для представления исходных данных и результатов решения задачи на рабочем листе созданы четыре таблицы:

- Стоимость доставки, руб., содержащая данные о стоимости перевозок единицы товара от i-го поставщика к j-му потребителю (т.е. стоимость одного рейса грузового автомобиля);

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

Рисунок 3 – Исходные данные транспортно-складской задачи

для компании ОАО «ПЕТМОЛ» (начало)

Рисунок 4 – Исходные данные транспортно-складской задачи

для компании ОАО «ПЕТМОЛ» (окончание)

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

В данную таблицу необходимо занести следующие расчетные формулы:

a) формулы расчета предложения поставщиков, которое равно ежемесячной пропускной способности терминалов умноженной на значение ячейки «Выбор» в таблице Исходные данные для распределительных центров, для чего необходимо в ячейку B59 занести формулу: =B52*B53 и распространить ее на весь диапазон ячеек, содержащих предложение поставщиков − B59:D59;

b) формулы расчета суммы по строкам таблицы для чего необходимо в ячейку E60 занести формулу: =СУММ(B60:D60) и распространить ее на весь диапазон ячеек, содержащих столбца «Сумма» − E60:E102;

c) формулы для расчета суммы по столбцам таблицы для чего необходимо в ячейку B101 занести формулу: =СУММ(B60:B100) и распространить ее на весь диапазон ячеек строки «Сумма» − B101:D101;

d) формулу для расчета транспортных затрат для чего необходимо в ячейку B102 занести формулу: =СУММПРОИЗВ(B5:B45;B60:B100) и распространить ее на весь диапазон ячеек, содержащих транспортные затраты − B102:D102;

- Мощность и затраты распределительных центров, содержащая результаты вычисления величины потоков (т.е. грузовых отправок) и общих издержек распределительных центров.

a) формулу для отображения результатов расчетов ежемесячной пропускной способности терминалов для чего необходимо в ячейку B108 занести формулу: =B59 и распространить ее на весь диапазон ячеек строки «Ежемесячная пропускная способность (грузовые отправки), ед.» − B108:D108;

b) формулу для расчета общих издержек распределительных центров для чего необходимо в ячейку B109 занести формулу: =B50*B53+B51*B101 и распространить ее на весь диапазон ячеек строки «Общие издержки распределительного центра, руб.» − B109:D109.

Отдельной строкой представлены Общие издержки обращения, руб., куда заносится целевая функция в виде: =СУММ(B102:D102;B109:D109).

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

4. Для оптимизации данной модели в окно Поиск решения должны быть внесены параметры оптимизации так, как это представлено на рисунке 5.

Рисунок 5 – Окно Поиск решения с ограничениями

5. Создадим сценарии поиска решения для различных наборов исходных данных.

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

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

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

В Microsoft Office Excel 2007 инструмент Диспетчер сценариев,который доступен через пункт меню Данные – Анализ «что – если» (рисунок 6).

Рисунок 6 – Доступ к средству Диспетчер сценариев

Сценарий можно создать щелкнув на кнопке Добавить в окне диалога Диспетчер сценариев (рисунок 7).

Рисунок 7 – Вид окно диалога Диспетчер сценариев

После чего открывается окно Изменение сценария, куда необходимо ввести название сценария, диапазон изменяемых ячеек и щелкнуть на кнопке OK (рисунок 8).

Рисунок 8 – Окно диалога Изменение сценария

В открывшемся окне Значения ячеек сценария необходимо ввести значения каждой изменяемой ячейки и щелкнуть на кнопке OK (рисунок 9).

Рисунок 9 – Окно диалога Значения ячеек сценария

Затем необходимо добавить другие сценарии поиска решения, после чего окно диалога Диспетчер сценариев приобретает вид, представленный на рисунке 10.

Рисунок 10 – Вид окна Диспетчер сценариев после создания сценариев транспортно-складской задачи

Создадим сценарии для транспортно-складской модели компании ОАО «ПЕТМОЛ». Очевидно, что в рамках данной модели возможны четыре сценария:

1) сценарий «Центр» – обслуживание всех клиентов компании только с центрального склада (переменные y_j принимаю значения {0;1;0});

2) сценарий «Центр+Сервис» – обслуживание всех клиентов компании с терминалов «Центр» и «Сервис» (переменные y_j принимаю значения {1;1;0});

3) сценарий «Центр+Север» – обслуживание всех клиентов компании с терминалов «Центр» и «Север» (переменные y_j принимаю значения {0;1;1});

4) сценарий «Центр+Сервис+Север» – использование всех трех складов для обслуживания клиентов (переменные y_j принимаю значения {1;1;1}).

6. Оптимизируем модель, т.е. получим решения для различных сценариев поиска решения.

Результаты решения данной задачи представлены на рисунках 11 – 14.

Рисунок 11 – Результаты поиска решения по сценарию «Центр»

Рисунок 12 – Результаты поиска решения по сценарию «Центр+Сервис»

Рисунок 13 – Результаты поиска решения по сценарию

«Центр+Север»

Рисунок 14 – Результаты поиска решения по сценарию «Центр+Сервис+Север»

7. Проанализируем полученное решение, составив сводную таблицу результатов решения по вариантам (таблица 3).

Таблица 3 – Сводная таблица результатов решения

Сценарий поиска решения	Ежемесячные затраты, тыс. руб.	Увеличение в сравнении с лучшим вариантом, %
складские	транспортные	общие
«Центр»				-
«Центр+Сервис»				5,3
«Центр+Север»				6,6
«Центр+Сервис+Север»				11,9

Анализ полученного решения показывает, что минимум транспортно-складских затрат имеет место при обслуживании всех клиентов компании только с центрального склада. В этом случае общие издержки обращения составят 12984 тыс. руб. Использование сценария «Центр+Сервис» дает стоимость решения равную 13675 тыс. руб., сценария «Центр+Север» – 13847 тыс. руб., сценария «Центр+Сервис+Север» – 14538 тыс. руб.

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

Контрольные задания

Исходные данные и варианты индивидуальных заданий для выполнения контрольной работы представлены в Приложении Г. Вариант индивидуального задания выбирается по двум последним цифрам номера зачетной книжки студента.