12. Понятие сети. Понятие двухполюсной сети.

Двухполюсная сеть - это связный мультиграф, в котором отмечены две вершины и и и; эти точки называются первым полюсом и вторым полюсом. Сумма или параллельное соединение NMi N2 получается отождествлением 1 с г и У. [1]

14. Разрез сети. Теорема о максимальном потоке и минимальном разрезе

Пусть V - величина потока, протекающего из источника s в сток t по дугам G=(N,A). Она зависит от пропускной способности дуг. Вводится понятие разреза - множества дуг, исключение которых из сети отделило бы источник от стока.

Разрез - это дуги 2-4 и 3-4. Пропускная способность разреза - это сумма пропускной способности всех дуг разреза., ориентированных определённым образом.

Пусть разрез отделяет множество узлов от множества узлов , причём а Тогда для ориентированной сети пропускной способностью разреза в направлении называется сумма пропускных способностей всех его ориентированных дуг, начальные узлы которых принадлежат , а конечные - .

Cр = С24+С34

Сформулируем теорему о максимальном потоке и минимальном разрезе. Она доказана Фордом и Фалкерсоном.

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

В данном случае, величина минимального разреза равна трём, и величина максимального потока тоже равна трём.

16. Постановка задачи о максимальном потоке. Задача о потоке минимальной стоимости.

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

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

пределени

Дана транспортная сеть с источником , стоком и пропускными способностями .

Величиной потока (value of flow) называется сумма потоков из источника . В статье «Транспортная сеть» доказано, что она равна сумме потоков в сток .

Задача о максимальном потоке заключается в нахождении потока такого, что величина потока максимальна.

17. Постановка транспортной задачи.

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.[1][2] Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

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

Методы решения

Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей её можно решить проще (для задач малой размерности).

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

Метод северо-западного угла (диагональный)

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