РГР 1 - Вариант 13 - Швец - Лысенков - 2006 / Швец

Российский Химико-Технологический Университет

им. Д.И.Менделеева

Кафедра логистики и экономической информатики.

Дисциплина “Основы промышленной логистики”

Расчетно-графическая работа №1

Тема: “Определение оптимального маршрута организации транспортных перевозок от предприятия-изготовителя к рынку сбыта”.

Вариант 13.

Выполнил: студент гр. КС-50

Лысенков С.В.

Проверил: Швец А.С.

Москва 2006

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

При волновой стратегии активная вершина выбирается на любом уровне декомпозиции.

Смыслом обеих стратегий является поиск минимальной верхней границы.

Верхняя граница – лучшее найденное на данный момент полное решение исходной задачи. Знание верхней границы позволяет исключить из рассмотрения часть решения, при условии, что в какой либо висячей вершине нижняя граница будет больше верхней границы, то раскрывать ее дальше не следует.

Данные стратегии в первую очередь влияют на программную реализацию алгоритма метода ветвей и границ.

В зависимости от задачи следует применять различные стратегии ветвления, с целью снизить число раскрытых вершин, тем самым повысить эффективность производимых расчетов.

Для сравнения эффективности стратегий применяют критерий n – число раскрытых вершин дерева вариантов решения, n₀-общее число вершин

n=35

n₀=67

В данной задаче эффективность обеих стратегий одинакова.

Оптимальное решение для данной задачи: 1-1→2-3→3-1→4-1→5-1.

При данном решении транспортные издержки составили: 13.