Полная версия

Главная arrow Логистика arrow Проектирование системы распределения в логистике

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

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

Традиционно методы математического программирования могут быть разделены на две большие группы[1]:

  • • методы линейного программирования (линейный характер целевой функции, ограничений);
  • • методы целочисленного программирования (часть или все используемые переменные имеют ограничение на целочисленность).

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

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

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

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

  • [1] Возможны и другие, более полные классификации.
 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>