Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Бурков В.Н. Элементы теории графов
 
djvu / html
 

быть разбито на два непересекающихся подмножества, причем
ребра (дуги) графа соединяют вершины только из разных подмно-
жеств), представленный на рисунке 4: вершины сети разбиты на
две группы - т поставщиков и п потребителей.
Известно [15], что граф является двудольным тогда и только
тогда, когда он не содержит циклов нечетной длины, или когда в
нем все простые циклы имеют четную длину (теорема Кента).
Для поставщиков заданы имеющиеся у них количества единиц
товара (груза и т.д.) at, i = 1, т , для потребителей - требуемые им
количества единиц товара bh i = 1, п. Также известны затраты sy
перевозки единицы товара от г'-го поставщика у'-му потребителю.
т п
Пусть задача является замкнутой, то есть /1dl = /\ bf - суммар-
i=i i=i
ное предложение равно суммарному спросу (вводя фиктивного
поставщика или фиктивного потребителя любую незамкнутую
задачу можно свести к замкнутой). Требуется определить потоки
товаров от потребителей к поставщикам, минимизирующие сум-
марные затраты.
ПОСТАВЩИКИ
ПОТРЕБИТЕЛИ
Рис. 4. Транспортная задача
20

 

1 10 20 21 22 23 24 25 26 27


Математика