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

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

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

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