Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Алгоритм метода частичных потоков




Транспортная задача по критерию стоимости

Пример нахождения максимального потока

 

Дана транспортная сеть (рисунок 3.3). Найти для нее максимальный поток.

 

x2 (9) x3

3 4

(6) 2 (9)

x0 (4) z


(7) (5)

4 x1 (3) x4 3

Рисунок 3.3 – Транспортная сеть


 

Таблица 3.3 – Первый этап решения задачи

 

xi  
  (0+,¥)
  (0+,3)
  (0+,3)
  (2+,3)
  (3+,3)
  (3+,3)

 

x2 (9) x3

6 7

(6) 2 (9)

x0 (4) z


(7) (5)

4 x1 (3) x4 3

Рисунок 3.4 – Транспортная сеть после первого этапа

Таблица 3.4 – Второй этап решения задачи

xi  
  (0+,¥)
  (0+,3)
  ---
  (1+,2)
  (1+,1)
  (4+,1)

 

x2 (9) x3

7

2 (9)

x0 (4) z


(7) (5)

5 x1 (3) x4 4

 

Рисунок 3.5 – Транспортная сеть после второго этапа

Таблица 3.5 – Третий этап решения задачи

 

xi  
  (0+,¥)
  (0+,2)
  ---
  (1+,2)
  (3+,2)
  (3+,2)

x2 (9) x3

9

4 (9)

x0 (4) z


(7) (5)

7 x1 x4 4

 

Рисунок 3.6 – Транспортная сеть после третьего этапа

 

 

Максимальный поток: 3+1+2=6.

 

 

Известно, что стоимость перевозки по дуге единицы груза .

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

Задача решается исходя из теории потоков.

Введём обозначения:

- пропускная способность дуги из в ;

- стоимость прохождения единицы потока по дуге ;

- поток, проходящий по дуге .

Стоимость всего пути по дуге : .

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

 

где , поток по дуге не должен превышать пропускную способность.

Считаем, что - длина пути, тогда стоимость прохождения некоторого потока по пути из в равна: .

Существует два варианта решения транспортной задачи:

 

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

 

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

 

 

1. В простейшем графе ищем кратчайший путь из в , .

2. Пусть в результате пункта 1 определили путь , имеющий пропускную способность , т.е. .

3. Пропускаем по данному пути поток , так что

4. Производим замену пропускной способности дуг по правилу:

5. Поток, который необходимо пропустить по транспортной сети, уменьшаем на , .

6. Исключаем из дальнейшего рассмотрения дуги, у которых .

7. Рассматриваем новый граф , как частичный граф исходного и переходим к пункту 1 для пропуска по транспортной сети потока .

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

8. Алгоритм останавливается, когда , .

Общая стоимость перевозки определяется по формуле (1).

 

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

 




Поделиться с друзьями:


Дата добавления: 2015-08-31; Просмотров: 403; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.026 сек.