АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Задача о кратчайшем пути

Читайте также:
  1. I. 3.1. Двойственная задача линейного программирования
  2. II.2. Задача о назначениях
  3. II.4. МЕТОД ВЕТВЕЙ И ГРАНИЦ В ЗАДАЧАХ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ
  4. VI. Общая задача чистого разума
  5. В задачах 13.1-13.20 даны выборки из некоторых генеральных совокупностей. Требуется для рассматриваемого признака
  6. в задачах экспертного выбора.
  7. В) Задача
  8. В) Задача
  9. В) Задача
  10. В) Задача
  11. В) Задача
  12. В) Задача

 

Частным случаем задачи об оптимальном потоке является задача по­строения кратчайшего пути между двумя вершинами пути. Пусть дан граф G=[N, A], каждой дуге которого поставлено в соответствие чис­ло С(х, у), называемое длиной дуги (х, у). Выделяются две вершины гра­фа - s и t. Требуется найти путь наименьшей длины, ведущий из вершины s в вершину t. При этом длина произвольного пути определяется следующим образом:

.

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

, где .

Рассмотрим теперь сеть, вершина s которой является источником еди­ничной интенсивности, t - стоком единичной интенсивности, остальные вершины - нейтральные. Дугам приписываются неограниченные пропускные способности, а стоимость перевозок по дуге полагается равной длине дуги. Для потока в рассматриваемой сети

Пусть имеется некоторый конечный граф G = [N ={1,2,…,n}, а], каж­дой вершине i которого поставлено в соответствие некоторое число , назы­ваемое интенсивностью потока. Вершины назовем источниками, нейтраль­ными вершинами и стоками, если , и соответственно. По­током в полученной сети назовем совокупность величин , удов­летворяющих соотношениям

,

.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 |

Поиск по сайту:



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