Решение транспортной задачи алгоритмом Басакера - Гоуэна

Работа добавлена на сайт samzan.net:

Лабораторная работа

Транспортные задачи

Транспортные модели (задачи) - специальный класс задач линейного программирования. Эти модели часто описывают перемещение (перевозку) какого-либо товара из пункта отправления (исходный пункт, например место производства) в пункт назначения (склад, магазин, грузохранилище). Назначение транспортной задачи - определить объем перевозок из пунктов отправления в пункты назначения с минимальной суммарной стоимостью перевозок. При этом должны учитываться ограничения, налагаемые на объемы грузов, имеющихся в пунктах отправления (предложение), и ограничения, учитывающие потребность грузов в пунктах назначения (спрос).

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

Введем для начала понятие сети. Сеть состоит из множества узлов - (называемых также вершинами или точками соединения) и множества дуг (называемых также звеньями, или ребрами), которые связывают эти узлы. Для изображения узлов и дуг используются соответственно кружки и линии. Будем использовать символ для обозначения узла и символ для обозначения дуги, ведущей из в . Последовательность узлов и дуг сети называется цепью, ведущей из узла , в узел . Если , то такая последовательность называется циклом.

На рисунке 1 показано общее представление транспортной задачи в виде сети с пунктами отправления и пунктами назначения, которые показаны в виде узлов сети. Дуги, соединяющие узлы сети, соответствуют маршрутам, связывающим пункты отправления и назначения. С дугой , соединяющей пункт отправления с пунктом назначения , соотносятся два вида данных: стоимость перевозки единицы груза из пункта в пункт и количество перевозимого груза . Объем грузов в пункте отправления равен , а объем грузов в пункте назначения - . Задача состоит в определении неизвестных величин , минимизирующих суммарные транспортные расходы и удовлетворяющих ограничениям, налагаемым на объемы грузов в пунктах отправления (предложение) и пунктах назначения (спрос).

Рисунок - Представление транспортной задачи

Сведение транспортной задачи к задаче о потоке минимальной стоимости

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

Пусть и - множества пунктов отправления и пунктов получения соответственно, между которыми должен быть распределен некоторый однородный товар. Каждый пункт отправления имеет ограниченный склад и каждый пункт получения - определенную потребность (спрос). Известна стоимость перевозки единицы товара из в , равная . В простейшем случае на объемы перевозок из в не наложено никаких ограничений, но, если имеются ограничения на количество товара, перевозимого из некоторых в некоторые , то соответствующим дугам приписывается конечная пропускная способность . Задача состоит в отыскании плана перевозок от пунктов отправления к пунктам потребления, имеющего минимальную стоимость, при условиях, что спрос должен быть удовлетворен (но избытков быть не должно) и объем перевозок от данного пункта отправления не должен превышать объемы его склада.

Эту задачу можно рассматривать как задачу нахождения потока, имеющего заданную величину и обладающего минимальной стоимостью в сети, изображенной на рисунке 2. (Упорядоченная пара чисел, приписанная каждой дуге, представляет пропускную способность дуги и единичную стоимость перевозок). Если перевозки из некоторых пунктов в некоторые пункты не разрешаются, то соответствующие дуги в сети просто опускаются. Таким образом, решая задачу о потоке в сети, мы получим план, позволяющий перевезти заданное количество товара при минимальной стоимости.

Рисунок - Транспортная задача в сетевой постановке

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

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

(1)

для всех . (2)

Здесь первая сумма берется по дугам, ведущим в узел , а вторая сумма - по дугам, ведущим из узла .

Неотрицательное число , фигурирующее в (1), называется величиной потока. Число называется потоком по дуге , или дуговым потоком.

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

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

Необходимо найти поток из источника в сток, имеющий заданную величину и обладающий минимальной стоимостью.

Формально задача ставится следующим образом:

минимизировать

при условиях

при всех .

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

Рассмотрим алгоритм поиска потока минимальной стоимости, предложенный Басакером и Гоуэном.

Алгоритм Басакера - Гоуэна имеет следующий вид:

Шаг 0. Положить все дуговые потоки и величину потока равными пулю.

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

Шаг 2. Найти кратчайшую цепь (то есть цепь минимальной стоимости) из в , используя дуговые стоимости , найденные на шаге 1. Затем пропускать по этой цепи поток до тех пор, пока она не перестанет быть кратчайшей цепью. Получить величину нового потока, прибавив к величине старого величину потока, текущего по рассматриваемой цепи. Если величина нового потока равна , то конец. В противном случае перейти к шагу 1.

Поиск кратчайшей цепи

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

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

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

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

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

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

Значения вычисляются просто:

для всех .

Пусть значения вычислены для всех , тогда получим формулу для расчета :

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

Тогда алгоритм Форда – Беллмана может быть представлен следующим образом:

Шаг 0. По данной матрице весов дуг положить , для всех узлов .

Шаг 1. Произвести пересчет значений для всех узлов по формуле:

(3)

Если , тогда .

Повторить шаг 1 раз.

Решение транспортных задач алгоритмом Басакера – Гоуэна

Для решения транспортной задачи алгоритмом Басакера - Гоуэна будем использовать программу «T-zadacha». В программе берется транспортная задача в сетевой постановке и решается как задача поиска потока минимальной стоимости алгоритмом Басакера - Гоуэна.

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

Рассмотрим решение транспортной задачи с помощью программы.

Задача:

Дана транспортная задача в сетевой постановке, представленная на рисунке 3, где каждой дуге сопоставлено два числа: первое число – пропускная способность дуги, второе – ее дуговая стоимость. Имеется 4 пункта отправления (узлы 1, 2, 3, 4) и 2 пункта назначения (узлы 5, 6).

Рисунок

Даны матрица пропускных способностей - и матрица дуговых стоимостей - :

Необходимо найти план перевозок (поток) величины 8, обладающий минимальной стоимостью.

Решение:

1. Запускаем программу «T-zadacha». Первоначальное окно программы имеет вид:

Рисунок

2. Вводим количество узлов – 8, количество дуг – 14 и величину потока (план перевозок) – 8. Далее нажимаем на кнопку «OK», и окно программы принимает следующий вид:

Рисунок

3. Вводим матрицу пропускных способностей и нажимаем на кнопку «Заполнить», расположенную под ней. Окно программы принимает вид:

Рисунок

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

После заполнения матрицы дуговых стоимостей, нажать на кнопку «Заполнить», расположенную под ней, тогда окно программы примет вид:

Рисунок

Таким образом, все входные данные заполнены, и можно приступить к решению задачи.

4. Нажать на кнопку «Решить задачу». Открылось результативное окно программы:

Рисунок

Получили решение задачи, представленное матрицей дуговых потоков и суммарной стоимостью потока (плана перевозок), равной 52.

Полученный поток можно изобразить в виде сети:

Рисунок

Варианты для выполнения лабораторной работы

Вариант № 1