Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лабораторная работа
Решение транспортной задачи алгоритмом Басакера - Гоуэна
Транспортные задачи
Транспортные модели (задачи) - специальный класс задач линейного программирования. Эти модели часто описывают перемещение (перевозку) какого-либо товара из пункта отправления (исходный пункт, например место производства) в пункт назначения (склад, магазин, грузохранилище). Назначение транспортной задачи - определить объем перевозок из пунктов отправления в пункты назначения с минимальной суммарной стоимостью перевозок. При этом должны учитываться ограничения, налагаемые на объемы грузов, имеющихся в пунктах отправления (предложение), и ограничения, учитывающие потребность грузов в пунктах назначения (спрос).
В общем случае транспортную модель можно применять для описания ситуаций, связанных с управлением запасами, управлением движением капиталов, составлением расписаний, назначением персонала и др.
Введем для начала понятие сети. Сеть состоит из множества узлов - (называемых также вершинами или точками соединения) и множества дуг (называемых также звеньями, или ребрами), которые связывают эти узлы. Для изображения узлов и дуг используются соответственно кружки и линии. Будем использовать символ для обозначения узла и символ для обозначения дуги, ведущей из в . Последовательность узлов и дуг сети называется цепью, ведущей из узла , в узел . Если , то такая последовательность называется циклом.
На рисунке 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
Дана транспортная задача в сетевой постановке:
Даны матрицы пропускных способностей и дуговых стоимостей:
,
Необходимо найти план перевозок (поток) величины 12, обладающий минимальной стоимостью.
Вариант № 2
Дана транспортная задача в сетевой постановке:
Даны матрицы пропускных способностей и дуговых стоимостей:
,
Необходимо найти план перевозок (поток) величины 8, обладающий минимальной стоимостью.
Вариант № 3
Дана транспортная задача в сетевой постановке:
Даны матрицы пропускных способностей и дуговых стоимостей:
,
Необходимо найти план перевозок (поток) величины 16, обладающий минимальной стоимостью.
Вариант № 4
Дана транспортная задача в сетевой постановке:
Даны матрицы пропускных способностей и дуговых стоимостей:
,
Необходимо найти план перевозок (поток) величины 20, обладающий минимальной стоимостью.
Вариант № 5
Дана транспортная задача в сетевой постановке:
Даны матрицы пропускных способностей и дуговых стоимостей:
,
Необходимо найти план перевозок (поток) величины 24, обладающий минимальной стоимостью.
PAGE 17