![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Задача линейного программирования
Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции
Задачи линейного программирования наиболее общего вида (задачи со смешанными ограничениями: равенствами и неравенствами, наличием переменных, свободных от ограничений) могут быть приведены к эквивалентным (имеющим то же множество решений) заменами переменных и заменой равенств на пару неравенств. Классификация оптимизационных задач: 1 классс-задачи распределения: транспортные задачи, задачи о назначениях, задачи о раскрое, задачи о смесях, задачи распределения; 2 класс – задачи управления запасами; 3 класс – задачи теории массового обслуживания:4 класс-задачи выбора маршрута; 5 – задачи теорий расписаний; 6 – задачи теории игр; 7 – задачи ремонта;8 – задачи поиска и 9 – аналитические задачи. В общем случае задача линейного программирования может быть записана в таком виде:
Поиск кратчайших путей Этот тип алгоритмов предназначен для поиска кратчайших путей между некоторыми вершинами графа. В различных задачах весами ребер могут быть длины, времена, стоимости, штрафы, убытки и так далее, то есть, любые величины, обладающие свойством аддитивности. Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути:
1. алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами); Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. В общем случае этот метод основан на приписывании вершинам временных пометок, причем пометка вершины дает верхнюю границу длины пути от некоторой вершины s к рассматриваемой вершине. Эти пометки постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации только одна из временных пометок становится постоянной. Последнее указывает на то, что пометка уже не является верхней границей, а дает точную длину кратчайшего пути от t к рассматриваемой вершине. 2. алгоритм Флойда (для нахождения оптимального маршрута между всеми парами вершин); В отличии от алгоритма Дейкстры, который позволяет при доведении до конца построить ориентированное дерево кратчайших путей от некоторой вершины, метод Флойда позволяет найти длины всех кратчайших путей в графе. Алгоритм:1)Перенумеровать вершины графа от 1 до N целыми числами, определить матрицу D0, каждый элемент di,j которой есть длина кратчайшей дуги между вершинами i и j. Если такой дуги нет, положить значение элемента равным ∞. Кроме того, положить значения диагонального элемента di,iравным 0. 2)Для целого m, последовательно принимающего значения 1...N определить по элементам матрицы Dm-1 элементы Dm 3) Алгоритм заканчивается получением матрицы всех кратчайших путей DN, N – число вершин графа. 3. алгоритм Йена (для нахождения k-оптимальных маршрутов между двумя вершинами). Делается это так: Будем вести список кандидатов в кратчайшие пути. Hаходится первый кратчайший путь. Так как все другие пути не должны совпадать с первым путем, то эти остальные пути не содержат как минимум одно из ребер первого пути. Поэтому, выкидываем по одному ребру из первого пути и находим кратчайшие пути в получаемых графах. Hайденные пути (с пометкой о том, какое ребро было выкинуто) добавляем в список кандидатов. Из списка кандидатов выбираем самый короткий путь - это второй самый короткий путь. Далее находим следующий самый короткий путь аналогично. При нахождении каждого самого короткого пути в список кандидатов добавляется не более N новых путей (на самом деле конечно меньше). При удалении ребра нахождение кратчайшего пути в полученном графе производится за линейное время. Для этого в исходном графе алгоритм Дейкстры запускается как от начальной, так и от конечной вершины. При удалении одного ребра кратчайший путь в новом графе ищется с использованием деревьев, полученных для исходного графа.
|
||||||
Последнее изменение этой страницы: 2016-06-22; просмотров: 883; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.191.150.52 (0.006 с.) |