Диссертация (1138083), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

При этом в исходной системе уравнений (целевой функции иограничений) выделяются ненулевые базовые и нулевые не базовые переменные,а последовательное улучшение решения достигается применением операциипивотирования.Симплекс-метод – простой и удобный инструмент решения задач линейногопрограммирования небольшой размерности, однако если число столбцов матрицыограничений велико, вычисления с использованием этого метода становятсямалоэффективными. Основной недостаток симплекс-метода – необходимостьхранить и пересчитывать симплексную таблицу или обратную базисную матрицу.Множество переменных, которые при поиске оптимального решения будут хотябы раз базисными, составляет малую часть в сравнении со всеми возможнымивариантами оптимальной матрицы, хранимыми и пересчитываемыми напрасно.Этот недостаток устраняется с применением метода генерации столбцов, которыйбыл впервые описан применительно к задачам по проектированию логистическихсетей в работе исследователя Крау.Методы линейного программирования используются тогда, когда расчетоптимального решения выполняется на среднесрочный (до 2-х лет) временнойгоризонт, а функции затрат и уровня сервиса (при наличии в рамках модели)носят линейный характер (что, как правило, невозможно, если учитываются76затраты на содержание запасов, в частности, страховых).

Кроме того, переменныетакже должны быть линейными, что существенно затрудняет применениеограничений на потенциально возможные местоположения складов. Этинедостатки устраняются при использовании методов смешанного целочисленногопрограммирования, имеющих как линейные, так и (как правило) булевыепеременныепринятиярешенийоразмещенииобъектовлогистическойинфраструктуры.Постановка задачи смешанного целочисленного программирования обопределении требуемого количества объектов в рамках моделей дискретнойоптимизации может выглядеть следующим образом:∑∑∑∑{}где fi — затраты на открытие складского объекта; yi — бинарная переменная,отражающая решение об открытии объекта в конкретном месте (0 — неоткрывать, 1 — открывать); cij — транспортные затраты на единицу груза отобъекта i до конечной точки продаж j; xij — доля от общего объема продукции,закупаемой торговой точкой j, которая поставляется с объекта (склада) i.Постановка задачи, приведенная выше, представляет так называемуюпроблему размещения складов без учета ограничений на доступные складскиемощности (uncapacitated warehouse location problem).

Как можно заметить, модельпризвана дать ответы сразу на два вопроса: где необходимо расположить склад икакой объем продукции должен через него следовать. Для учета доступныхмощностей склада необходимо ввести дополнительное ограничение:Ndj 1jxij  si yi ,77где dj — потребность магазина j; si — максимальный грузопоток через склад(распределительный центр) i.Приведенная выше постановка задачи — упрощенный пример; болеесложные модели позволяют учитывать дополнительные категории затрат (как,например, затраты на хранение запасов) и осуществлять оптимизациюэшелонированных цепей поставок. В табл. 3.4, 3.5 приведен перечень основныхклассификаций моделей смешанной дискретной оптимизации и примеры целевыхфункций (Приложение Н).Точные и эвристические методы решения задач дискретной оптимизацииСформулированнаявформемоделисмешанногоцелочисленногопрограммирования задача о проектировании сети распределения является NPсложной44.

NP-сложность таких задач обуславливается, в частности, тем, что приросте числа складов в сети распределения количество допустимых вариантов«назначения»магазиновзаскладами(распределениямагазиновмеждуобслуживающими объектами складской инфраструктуры) возрастает нелинейно.Для того чтобы оценить возможное количество таких назначений, можноиспользоватьизвестноевкомбинаторикечислоСтирлинга2-города,показывающее, сколько существует вариантов разбиения множества из mэлементов(магазинов)наnнепустыхподмножеств(складовилираспределительных центров):∑( )Так, для 96 магазинов и 21 склада существует Q (96, 21) = 1,3749*107 вариантовраспределения магазинов между складами.

Ввиду такого колоссального объемавычислений для нахождения оптимального решения требуются особые методы,изучениюкоторыхипосвященоподавляющеебольшинствостатейпорассматриваемой научной тематике. Большинство исследователей выделяютследующие группы:44Megiddo N., Supowit K.J. On the complexity of some common geometric location problems // Siam J. Comput, Vol. 13,№ 1, Feb. 198478 точныеметоды(достоверноеполучениеглобальногооптимальногорешения):o методы перебора (прямого или направленного);o методы сведения задачи к линейной (методы аппроксимации илидекомпозиции);o методы динамического программирования. эвристические и мета-эвристические методы (получение приближенногорешения)Ключевыми критериям выбора метода на данном этапе являются приемлемаяточность результата (здесь в противоположность критерию точности на первомэтапе классификации речь идет о десятых долях процента), допустимое время нарешение, располагаемые вычислительные мощности и вычислительная сложностьсамой задачи.

К факторам, влияющим на вычислительную сложность задачи,относятся45: охват модели (решается ли сопутствующая основной задаче задачамаршрутизациитранспортныхпотоков,учитываютсялизапасы,неопределенность, периоды времени, пр.); число объектов в сети распределения (как правило, для моделей,содержащих более 20 объектов46, применяются методы эвристики); степень унификации объектов (виды складов, заказчиков, продуктов и пр.); характер функции затрат (линейный или нелинейный); иерархичность (есть ли потребность в моделировании нескольких уровнейиерархии сети распределения); допустимая структура материальных потоков в сети распределения (всепотоки идут от первого звена логистической цепи до последнего, иливозможны потоки между объектами различных уровней иерархическойструктуры);45Часть факторов взята их статьи Güvenç ¸Sahina, Haldun Süralb. A review of hierarchical facility location models //Computers & Operations Research 34 (2007) 2310– 2331.46Ограничение в 20 объектов встречается в работах А.П, Мощевикина, Роберта Лова (Robert Love) и ряда другихисследователей79 допустимость привязки одного заказчика к нескольким складам (илииспользование модели одного поставщика для каждого заказчика); прочие факторы.Точныеметодыпредполагаютстремлениекполучениюдостоверногооптимального результата за полиноминальное время.

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

Вместе с тем ряд исследователейдоказывают, что методы прямого перебора непривлекательны с точки зрениявремени вычислений для задач с числом заказчиков более 1048.Самым известным из методов направленного перебора является метод ветвейи границ (branch & bound algorithm). Впервые метод ветвей и границ былпредложен Ландом и Дойгом в 1960 году для решения общей задачицелочисленного линейного программирования49. Эффективная с точки зрениякомпьютационныхзатратвремениреализацияметодадлязадачипопроектированию сети распределения была предложена Б. Хумавалой (Basheer M.Khumawala) в 1977 году50. Метод предполагает рассмотрение подмножеств47Takeshi Koide, Shuichi Shinmori, Hiroaki Ishii. An efficient complete enumeration method for network design problemsand its applications // Journal of the Operations Research, Society of Japan, Vol.

45, № 3, September 200248Cooper, L. Location-Allocation Problems // Operations Research 11 (1963), No. 3, pp. 331-34349Land A.H., Doig A.G. An automatic method of solving discrete programming problems // Econometrica. V28, 196050Umit Akinc and Basheer M. Khumawala. An Efficient Branch and Bound Algorithm for the Capacitated WarehouseLocation Problem // Management Science, Vol. 23, No.

6 (Feb., 1977), pp. 585-59480возможных решений (содержащих значения переменной yi для каждогопотенциального местоположения склада или распределительного центра) иприменение к нему набора критериев по выбору переменной «ветвления» иотбраковке неперспективных узлов (узлов, для которых оптимальное значениениже текущей верхней оценки функции оптимизации). Методы ветвей и границявляются в настоящее время основой всех известных пакетов и библиотекприкладныхпрограммпорешениюзадачцелочисленногоичастичноцелочисленного лилейного программирования.2)Методы сведения задачи к линейной (методы аппроксимации идекомпозиции)Методы второй группы предполагают аппроксимацию или разбиение задачисмешанной дискретной оптимизации на несколько подзадач, которые могут бытьпредставлены в форме линейных.

Так, метод декомпозиции Бендера, например,позволил Геоффриону и Грэйвзу51 определить оптимальные значения количестваи расположения распределительных центров в рамках многопродуктовой моделиоптимизации (17 продуктовых категорий, 14 заводов, 45 потенциальныхместоположений РЦ и 121 заказчик). Лучше всего логика, используемая в методахрассматриваемой группы, может быть рассмотрена на примере алгоритмадекомпозиции задачи размещения объектов складской инфраструктуры сограничениями на допустимый объем мощностей, предложенного Ван Роем 52.Исследователь предложил выделить в структуре задачи смешанной дискретнойоптимизации две подзадачи: линейную транспортную (которую было предложенорешать при фиксированном значении переменных yi) и задачу размещения (длярешения которой в условие задачи вводилась суррогатная переменная,основанная на ограничении на допустимые мощности).

В результате алгоритмпоследовательного решения двух подзадач показал лучшее время в сравнении срядом других методов.51A.M. Geoffrion, G.V. Graves. Multicommodity Distribution System Design by Benders Decomposition // ManagementScience, Vol. 20, №5, January 1974, 822-84452Tony J.

van Roy. A Cross Decomposition Algorithm for Capacitated Facility Location // Operations Research, Vol. 34,No. 1 (Jan. - Feb., 1986), pp. 145-163813) Методы динамического программированияКак самостоятельный класс, методы динамического программированияприменяются к задачам, решение которых можно разбить на ряд этапов. В основепримененияэтихметодовлежитпринципоснователядинамическогопрограммирования Р. Беллмана: «Каково бы ни было состояние системы втекущий момент, на очередном шаге необходимо принимать такое решение,чтобы в совокупности с оптимальными решениями на всех последующих шагахоно приводило к наилучшему значению целевой функции».Одним из первых метод динамического программирования к задачам оразмещении мощностей применил Роберт Лов53.

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

Характеристики

Список файлов диссертации