![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Пример 2.
На рис. 5 показана транспортная сеть, состоящая из пяти городов (расстояния между городами (в км) приведены возле соответствующих дуг сети). Необходимо найти кратчайшие расстояния от города
Шаг 0. Назначаем узлу Шаг 1. Из узла
Среди узлов Шаг 2. Из узла 3 (последнего узла с постоянной меткой) можно попасть в узлы 4 и 5. Получаем следующий список узлов.
Временный статус метки Шаг 3. Из узла
Временная метка Шаг 4 Из узла
Алгоритм позволяет проводить вычисления непосредственно на схеме сети, как показано на рис. 6. Кратчайший маршрут между узлом Таким образом, получаем путь 40. Алгоритмы нахождения кратчайшего пути. Алгоритм Флойда. Этот алгоритм более общий по сравнению с алгоритмом Дейкстры, так как он находит кратчайшие пути между любыми двумя узлами сети. В этом алгоритме сеть представлена в виде квадратной матрицы с Покажем сначала основную идею метода Флойда. Пусть есть три узла
Алгоритм Флойда требует выполнения следующих действий.
Шаг 0. Определяем начальную матрицу расстояний
Шаг k (основной). Задаем строку
тогда выполняем следующие действия: a) создаем матрицу b) создаем матрицу Поясним действия, выполняемые на Если сумма элементов ведущих строки и столбца (показанных в квадратиках) меньше элементов, находящихся на пересечении столбца и строки (показаны в кружках), соответствующих рассматриваемым ведущим элементам, то расстояние (элемент в кружке) заменяется на сумму расстояний, представленных ведущими элементами.
После реализации 1. Расстояние между узлами 2. Промежуточные узлы пути от узла 41. Транспортные модели. Определение транспортной модели. Транспортные модели (задачи) — специальный класс задач линейного программирования. Эти модели часто описывают перемещение (перевозку) какого-либо товара из пункта отправления (исходный пункт, например место производства) в пункт назначения (склад, магазин, грузохранилище). Назначение транспортной задачи — определение объемов перевозок из пунктов отправления в пункты назначения с минимальной суммарной стоимостью перевозок. При этом должны учитываться ограничения, накладываемые на объемы грузов, имеющихся в пунктах отправления (предложения), и ограничения, учитывающие потребность грузов в пунктах назначения (спрос). В транспортной модели предполагается, что стоимость перевозки по какому-либо маршруту прямо пропорциональна объему груза, перевозимого по этому маршруту. В общем случае транспортную модель можно применять для описания ситуаций, связанных с управлением запасами, управлением движением капиталов, составлением расписаний, назначением персонала и др. На рис. 1 показано представление транспортной задачи в виде сети с
42. Решение транспортной задачи. Определение начального решения. Метод северо-западного угла. В данном разделе будет детально описан алгоритм решения транспортной задачи. Этот алгоритм повторяет основные шаги симплекс-метода. Однако для представления данных, вместо обычных симплекс-таблиц, используются транспортные таблицы со специальной структурой. Алгоритм решения транспортной задачи будет проиллюстрирован на следующем примере. Последовательность шагов алгоритма решения транспортной задачи в точности повторяет аналогичную последовательность этапов симплексного алгоритма. Таблица 2.1
Шаг 1. Определяем начальное базисное допустимое решение, затем переходим к выполнению второго шага. Шаг 2. На основании условия оптимальности симплекс-метода среди всех небазисных переменных определяем вводимую в базис переменную. Если все небазисные переменные удовлетворяют условию оптимальности, вычисление заканчиваются; в противном случае переходим к третьему шагу. Шаг 3. С помощью условия допустимости симплекс-метода среди текущих базисных переменных определяем исключаемую переменную. Затем находим новое базисное решение. Возвращаемся ко второму шагу. Рассмотрим каждый описанный шаг в отдельности.
|