Тема 10 Сетевые модели Введение



страница1/8
Дата28.12.2017
Размер0.83 Mb.
#5552
ТипАнализ
  1   2   3   4   5   6   7   8

Тема 10 Сетевые модели

Введение

Сетевые модели могут строиться:



  • в терминах событий: вершины- события, дуги - взаимосвязь событий;

  • в терминах работ: вершины- работы, дуги - взаимосвязь работ;

  • в терминах работ и событий: вершины - события результата работ (начало либо завершение), дуги - сами работы.

С помощью сетевых моделей можно решить множество задач. Рассмотрим следующие конкретные примеры.

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

2. Определение кратчайшего пути между двумя городами, проходящего по существующей сети шоссейных дорог.

3. Определение максимальной пропускной способности (в тоннах/год) трубопровода для транспортировки угольной пульпы с шахт Вайоминга на тепловые электростанции в Хьюстоне. (Уголь под напором воды поступает в специально спроектированный трубопровод и перегоняется с шахт в пункты назначения.)

4. Определение наиболее экономичной (имеющей минимальную стоимость) схемы транспортировки нефти из пунктов нефтедобычи на перерабатывающие заводы и далее в центры распределения. Сырую нефть и нефтепродукты можно транспортировать на танкерах, грузовиках или по нефтепроводу. Помимо условий, определяющих верхний предел для добычи нефти и нижний предел для удовлетворения спроса на нее, необходимо принимать во внимание ограничения мощности нефтеперерабатывающих заводов и пропускных способностей соответствующих транспортных коммуникаций.

Анализ указанных примеров показывает, что оптимизационные задачи на сети можно описать следующими четырьмя типами моделей:

1) минимизации сети;

2) нахождения кратчайшего маршрута;

3) определения максимального потока;

4) минимизации стоимости потока в сети с ограниченными пропускными способностями коммуникаций.

Рассмотренные примеры связаны с определением расстояний и материальных потоков. Однако во многих приложениях переменные могут представлять величины иной природы, как, например, потоки запасов или денег.

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

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

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



1. Определение кратчайшего маршрута для сети без циклов

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

Введем следующие обозначения:

dij – расстояние на сети между смежными узлами i и j.

uj – кратчайшее расстояние между узлами 1 и j, u1=0.

Общая формула для вычисления uj имеет вид: uj= mini {uj+dij}

(кратчайшее расстояние до предыдущего узла i плюс расстояние между текущим узлом j и предыдущим узлом i).

Из этой формулы следует, что кратчайшее расстояние uj до узла j можно вычислить лишь после того, как определено кратчайшее расстояние до каждого предыдущего узла i, соединенного дугой с узлом j.

Минимальное расстояние между начальным и конечным узлами находится в конце прямого хода вычислений. Оптимальный маршрут определяется при обратном проходе с использованием условия ui= uj-dij.

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

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

Рекурсивные вычисления представляют собой основу вычислительной схемы динамического программирования.

Рассмотрим алгоритм на примере сети, представленной на рис.1.1. Предварительно сеть упорядочена и разбита на последовательность этапов, определяющих ход вычислений.


Этап
1

Этап
2

Этап
3

Этап
4

Этап
5

U2=2 5 U5=7



11 6


2 8

10 U4=7 U7=13

U1=0

4 7 9


3

1


U3=4 U6=5

Рис. 1.1
Узел 1 представляет начальную точку (исходный пункт), а узел 7- конечную точку (пункт назначения). Заметим, что сеть не имеет циклов, поскольку нет ни одной цепи, связывающей узел с самим собой. Для узла 1 можно вычислить лишь u2 и u3. (Заметим, что, хотя узел 4 соединен узлом 1 дугой, соответствующее значение u4 вычислить нельзя, пока не будут определены u2 и u3).

Процедура завершается, когда получено значение u7.

Вычислительная схема состоит из следующих этапов:



  • Этап 1: u1=0.

  • Этап 2: u2= u1+d12=0+2=2).

u3= u1+d13=0+4=4.

  • Этап 3: u4= min {u1+d14, u1+d24, u1+d34 } = min {0+10, 2+11, 4+3 } =7.

  • Этап 4: u5= min {u2+d25, u4+d45}= min {2+5, 7+8 } =7.

u6= min {u3+d36, u4+d46 }= min {4+1, 7+7 }=5.

  • Этап 5: u7= min { u5+d57, u6+d67 } = min {7+6, 5+9 } =13.

Минимальное расстояние между узлами 1 и 7 равно 13, а соответствующий маршрут- 1257, который находится на обратном проходе с использованием условия : ui= uj-dij.

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

Вычисления выполняются с использованием информации обо всех кратчайших расстояниях до непосредственно предшествующего узла. Например, в узле 5 величина u5 вычисляется по кратчайшим расстояниям между узлом 1 и узлами 2 и 4, т.е. u2 и u4. Заметим, что не обязательно знать конкретный маршрут, дающий кратчайшее расстояние между узлами 1 и 4. Величина u4 включает всю информацию, необходимую для узла 4. Именно такая информация позволяет использовать рекурсивные вычисления.

Все вычисления можно провести непосредственно на сети (рис. 1.1).

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




Поделитесь с Вашими друзьями:
  1   2   3   4   5   6   7   8




База данных защищена авторским правом ©vossta.ru 2022
обратиться к администрации

    Главная страница