Методы перебора (прямого или направленного)

Методы прямого перебора, исходя из названия, подразумевают полный перебор вариантов целевой конфигурации сети распределения с последующим выбором оптимального. Эти методы являются наиболее простыми для применения и столь же неэффективными с точки зрения времени и требуемых мощностей для вычисления. В статьях, посвященных этим методам, рассматриваются различные процедуры повышения эффективности их работы. Так, в статье коллектива японских исследователей [63] демонстрируется применение процедуры, позволяющей оценивать изоморфность анализируемых вариантов конфигурации сети и на этом основании удалять неоптимальные варианты из рассмотрения более быстрыми темпами. Вместе с тем ряд исследователей доказывают, что методы прямого перебора непривлекательны с точки зрения времени вычислений для задач с числом заказчиков более десяти единиц [53].

Самым известным из методов направленного перебора является метод ветвей и границ (branch&bound algorithm). Впервые метод ветвей и границ был предложен А. Ландом и А. Дойгом в 1960 г. для решения общей задачи целочисленного линейного программирования [64]. Эффективная с точки зрения компьютационных затрат времени реализация метода для задачи по проектированию сети распределения была предложена Б. Хумавалой (Basheer М. Khumawala) в 1977 г. [52]. Метод предполагает рассмотрение подмножеств возможных решений (содержащих значения переменной yj для каждого потенциального местоположения склада или распределительного центра) и применение к нему набора критериев по выбору переменной «ветвления» и отбраковке неперспективных узлов (узлов, для которых оптимальное значение ниже текущей верхней оценки функции оптимизации). Методы ветвей и границ являются в настоящее время основой всех известных пакетов и библиотек прикладных программ по решению задач целочисленного и частично целочисленного линейного программирования.

Методы сведения задачи к линейной (методы аппроксимации и декомпозиции)

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >