Программирование на сетях

которую можно увеличить поток по каждому ребру (i, j) выделенного пути, чтобы получить новый поток X1 мощности, большей на единиц. Как видно из табл. 1.4., по ребру (1, 2) можно дополнительно пропустить 6 ед., по ребру (2, 4) – 4 ед., по ребру (4, 6) – только 2 ед., так что

Для построения матрицы нового потока X1 к соответствующим элементам xij0 матрицы XP0 прибавляется найденное значение , после чего возвращаются к п. 2 алгоритма, и т.д. до получения максимального потока.

Прибавим величину к элементам x120 = 1, x240 = 0 и x460 = 2, обозначающим ненасыщенный путь (по всем остальным ребрам величина потока не изменится). Приходим к матрице нового потока X1 (см. табл. 1.5), мощность которого равна 7 ед. Этот поток вновь надо исследовать на оптимальность, т. е. вернуться к п. 2 алгоритма. Вновь составляем матрицу R – X1 (см. табл. 1.5), а по ней – списки вершин, достижимых из истока I по ненасыщенным путям:



Из этих списков видно, что сток 6 снова в подмножестве A, а путь, ведущий в него, состоит из ненасыщенных ребер (1, 2), (2, 4), (4, 5), (5, 6). Новый поток X2, (его матрица представлена в табл. 1.6, получается преобразованием потока X1, если увеличить на потоки по указанным ребрам найденного ненасыщенного пути. Мощность нового потока X2 составляет 9 ед. Для исследования этого потока составляется матрица R – X2 (табл. 1.8), а по ней – списки.

(1.8)

Таблица 1.6

i/j

1

2

3

4

5

6

1

0

5

2

2

0

0

2

-5

0

0

4

1

0

3

-2

0

0

0

2

0

4

-2

-4

0

0

2

4

5

0

-1

-2

-2

0

5

6

0

0

0

-4

-5

0



Таблица 1.7

i/j

1

2

3

4

5

6

1

0

4

2

0

0

0

2

6

0

8

2

0

0

3

8

8

0

0

0

0

4

7

11

0

0

8

0

5

0

6

4

3

0

2

6

0

0

0

10

10

0



По спискам (1.8) видно, что сток 6 не попал в подмножество A вершин, достижимых из истока по ненасыщенным ребрам. Значит поток X2 максимален. Нанесем его на сеть с указанием направления потоков по отдельным ребрам (см. рис. 1.11).


Таблица 1.8


i/j

1

2

3

4

5

6

1

0

4

2

0

0

0

2

6

0

8

2

0

0

3

8

8

0

0

0

0

4

7

11

0

0

8

0

5

0

6

4

3

0

2

6

0

0

0

10

10

0


Рис. 1.11

Можно было бы и не строить матрицу R – X2, если своевременно заметить, что потоки по ребрам (4, 6) и (5, 6) равны их пропускным способностям, т.е эти ребра насыщены (см. табл. 1.7 и 1.8).

Используя списки (табл. 1.8) выделим подмножества A и B, на которые оказалось разбитым множество всех вершин: A = {1, 2, 3}, B = {4, 5, 6}. Теперь можно выписать ребра, образующие разрез A / B минимальной пропускной способности: (1, 4), (2, 4), (2, 5), (3, 5).

Заключение


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

Список использованной литературы


  1. Акулич Н.А. Математическое программирование в примерах и задачах. – М.: Высшая школа, 2003.

  2. Иозайтис В.С., Львов Ю.А. Экономико-математическое моделирование производственных систем. – М.: Высшая школа, 2000.

  3. Миненко С.Н., Гамазина Г.И. Экономико-математическое моделирование производственных систем. – Учебное пособие, МГИУ

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: