Исследование операций в задачах: учеб. - метод. пособие для студентов факультета прикладной математики и информатики. В 3 ч. Ч. II : Сетевые задачи / авт.-сост.: А. Н. Исаченко, Л. Ф. Дробушевич. – Минск: БГУ, 2011. – 63 с.

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

Предназначено для студентов факультета прикладной математики и информатики.

Оглавление

ВВЕДЕНИЕ

3

ЗАДАЧА О МИНИМАЛЬНОМ ОСТОВНОМ ДЕРЕВЕ НЕОРИЕНТИРОВАННОГО ГРАФА

4

КРАТЧАЙШИЕ ПУТИ

8

ПОТОКИ В СЕТЯХ

16

Задача о максимальном потоке

17

Задача о многополюсном максимальном потоке

24

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

31

Потоки минимальной стоимости

35

ЗАДАЧИ О НАЗНАЧЕНИИ

41

Классическая задача о назначении

41

Задача о назначении на узкие места

47

ЗАДАЧА КОММИВОЯЖЁРА

52

Общая схема метода ветвей и границ

53

Алгоритм Литтла

55

ЛИТЕРАТУРА

61