Экономико-математические методы в логистике: линейные оптимизационные задачи с булевыми переменными

Экономико-математические методы в логистике К.Э.Н., ДОЦЕНТ БОРИСОВА ВИКТОРИЯ ВЛАДИМИРОВНА Л ИНЕ ЙНЫ Е ОПТ ИМИЗ А ЦИОНН Ы Е ЗА ДАЧИ С БУ Л Е ВЫ МИ ПЕ РЕ МЕ ННЫ МИ ЗАДАЧА О КОММИВОЯ ЖЕРЕ Общая идея задачи о коммивояж ере Коммивояжер должен объездить некоторый перечень населенных пунктов, побывав в каждом из них только один раз. Затем он должен вернуться в исходный пункт. Варианты критерия: • минимальное суммарное расстояние маршрута; • минимальное суммарное время нахождения в пути. Сетевая модель задачи: графика Витебск Гродн о Минск Могилев Гомель Брест Главные магистрали Сетевая модель задачи: формализация  - узел  Ребро – неориентированная линия  Дуга - однонаправленная линия – из в  Ребро может быть представлено двумя дугами Математическая модель Матрица расстояний между городами, км Объек т Брест Витебс Гомель к Гродно Минск Брест M Витебс к M M Гомель 485 М M Гродно 300 M M M Минск 330 228 282 285 M Могил ев 490 145 168 434 180 Могил ев M Запрет перемещений обозначается либо M, либо ∞ Математическая модель - переменная, фиксирующая факт переезда из населенного пункта в населенный пункт Целевая функция: Математическая модель Целевая функция: Объек т Брест Витебс Гомель к Гродно Минск Брест M Витебс к M M Гомель 485 М M Гродно 300 M M M Минск 330 228 282 285 M Могил ев Математическая модель Ограничения: Первый вид. Выезд из каждого узла в сети должен быть осуществлён только один раз. Второй вид. Въезд в каждый узел сети осуществляется только один раз. Третий вид. Условия, исключающее образование частичных замкнутых маршрутов. Математическая модель Первый вид ограничений. =1 (2) …… =1 (4) (5) (1) (6) (3) Математическая модель Второй вид ограничений. =1 (2) …… =1 (4) (5) (1) (6) (3) Математическая модель Третий вид ограничений. Варианты замкнутых маршрутов (частичный контур) 1-5-3-1 или 2-6-35-6 Специальный вид условия, предотвращающее появление частичных контуров: (2) (4) (5) . Для примера: (1) (6) (3) Методы решения задачи коммивояж ера  MS Excel  Методы комбинаторной оптимизации  Метод ветвей и границ  Генетические алгоритмы  Метод ближайшего соседа и т.д. Продолж ение следует…