Одесса ОНУ - 2013

Институт инновационного и последипломного образован

Кафедра экономической кибернетики

И практической экономики

МЕТОДИЧЕСКОЕ ПОСОБИЕ

Одесса ОНУ - 2013

Методическое пособие «Решение потоковых

задач» ориентировано на студентов, изучающих

дисциплины «Дискретная математика», «Оптими-

зационные методы и модели», «Исследование опе-

раций».

Составитель Любота В.Н.,

к.ф.-м.н.,доцент

Утверждено на заседании Ученого Совета

Института инновационного и последипломного образования

Одесского национального университета им. И.И. Мечникова

Протокол № от 2013 г.

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ.................................................................................................................................. 3

СТАНДАРТНАЯ ЗАДАЧА О ПОТОКЕ МИНИМАЛЬНОЙ СТОИМОСТИ..................................... 4

ПОСТАНОВКА ЗАДАЧИ О КРАТЧАЙШЕМ ПУТИ.................................................................. 5

ПОСТАНОВКА ЗАДАЧИ О МАКСИМАЛЬНОМ ПОТОКЕ...................................................... 8

ПОРЯДОК РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ НА ЭВМ........................... 9

РЕШЕНИЕ ДВОЙСТВЕННОЙ ЗАДАЧИ ………………………………………………………………………………. 12

РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В СИСТЕМЕ MAPLE ………………….. 13

КОНТРОЛЬНЫЕ ЗАДАНИЯ ………………………………………………………………………………………………… 14

РЕШЕНИЕ ЗАДАЧИ О КРАТЧАЙШЕМ ПУТИ................................................................................ 15

ДЕРЕВО КРАТЧАЙШИХ ПУТЕЙ………………………………………………………………………………………………. 16

РЕШЕНИЕ ЗАДАЧИ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНОГО ПОТОКА........................................... 18

РЕШЕНИЕ ЗАДАЧИ О МАКСИМАЛЬНОМ ПОТОКЕ В СИСТЕМЕ MAPLE…………………………….. 23

РЕШЕНИЕ ЗАДАЧИ ОПРЕДЕЛЕНИЯ МИНИМАЛЬНОГО РАЗРЕЗА ……………………………………….. 25

РЕШЕНИЕ ЗАДАЧИ ОПРЕДЕЛЕНИЯ ПОТОКА МИНИМАЛЬНОЙ СТОИМОСТИ......................... 26

КОНТРОЛЬНЫЕ ЗАДАНИЯ ………………………………………………………………………………………………… 27

ЛИТЕРАТУРА …………………………………………………………………………………………………………………………. 30

ВВЕДЕНИЕ

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

Задачи планирования перевозок имеют четко выраженную сетевую структуру [1], обусловленную наличием транспортной сети, по которой перемещаются транспортные средства. Этим объясняется широкое приме нение для решения задач планирования перевозок методов и моделей опти мизации потоков в сети, наиболее адекватно учитывающих специфику структуры этих задач. Наряду с понятием «задача о потоке в сети» возможно использование термина «потоковое программи- рование» [2]. Центральное место в классификации задач потокового программирования занимает стандартная линейная задача о потоке минимальной стоимости (СЗПМС). Частными случаями СЗПМС являются задачи о кратчайшем пути и о макси мальном потоке. Более общими задачами являются задача о сетях с выигры шами и задачи с нелиней ными функциями стоимости потоков по дугам.

Вершина, из которой начинается перемещение объектов, называется источником, а в которой перемещение заканчивается – стоком. Объекты, кото рые перемещаются или «протекают» из источника в сток, будут называться единицами потока или просто единицами.

Если количество единиц, которое может проходить по дуге ограни-

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

Наконец, дугам графа приписываем числа, которые и называют потоком.

Пусть G (X, U) – орграф без петель и кратных дуг, имеющий один

тупик-сток (вершина s) и один антитупик-источник(вершина t).