Математическое моделирование транспортных потоков

• Номер работы:
  562325
• Раздел:
  Все работы   →   Контрольные работы   →   Математические методы и модели в экономике
• Год добавления:
  31.05.2019 г.
• Объем работы:
  18 стр.
• Выдержка из работы:
  Некоторые тезисы из работы по теме Математическое моделирование транспортных потоков
  Задача 20 (О максимальном потоке).
  Будем считать, что из пункта А в пункта Б едет (возможно, через другие пункты) непрерывный поток автомобилей величиной X автомобилей в единицу времени. Также будем считать, что у каждой дороги, соединяющей два пункта, пропускная способность ограничена числом сij машин в единицу времени. Необходимо найти, какой максимальный поток можно запустить из пункта А в пункт Б с учетом пропускных способностей дорог.
  а) Запишите эту задачу, как задачу линейного программирования, напишите двойственную к ней задачу.
  Указание. Считайте граф ориентированным. Используйте матрицу инциденций графа.
  б) Пусть сij – неотрицательные целые числа. Покажите, что в оптимальном решении задачи поток, проходящий через каждую дорогу, будет также целым.
  Указание. Используйте вид матрицы инциденций графа (в каждом столбце только два числа не равны нулю; эти числа: 1 и минус 1).
  в) Как при доказательстве целочисленности решения (см. пункт б)) можно использовать теорему Гофмана–Краскала о том, что полиэдр, задаваемый ограничениями вида с абсолютно унимодулярной матрицей A и произвольным вектором (таким, что система совместна), имеет все вершины с целочисленными компонентами?
  Замечание. Отметим, что по теореме Пуанкаре, матрица инциденций произвольного ориентированного графа абсолютно унимодулярна, т.е. определитель любой еe квадратной подматрицы равняется одному из трех чисел: минус 1, 0, 1.
  г) Оцените сложность алгоритма Форда–Фалкерсона (сij – неотрицательные целые числа) и время работы соответствующей программы для поиска максимального потока (количество пунктов – 1000).
  д) Сойдется ли за конечное время к оптимальному решению алгоритм Форда–Фалкерсона, если сij – неотрицательные вещественные числа?
  е) Модифицируйте алгоритм Форда–Фалкерсона для решения задачимаксимального потока при неотрицательных вещественных сij (например, алгоритмы Эдмонса–Карпа и Диница), оцените их сложность и время работы (количество вершин – 1000).
  ж) Оцените пространственную и временную сложность алгоритма Карзанова нахождения максимального потока. В чем заключаются преимущества алгоритма Карзанова, например, над алгоритмом Форда– Фалкерсона?
  Решение:
  .............