<<
>>

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

Предположим, что задана сеть с пропускными способностями дуг cij. Пусть также для каждой дуги (i;j) заданы число sij-, интерпретируемое как затраты (например, затраты на перевозку единицы груза из вершины i в вершину j).
Задача поиска потока минимальной стоимости заключается в нахождении для заданной величины j суммарного потока ее распределения по дугам, минимизирующего сумму затрат. Общие методы решения задачи о потоке минимальной стоимости рассматриваются в [5, 7, 19].

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

быть разбито на два непересекающихся подмножества, причем ребра (дуги) графа соединяют вершины только из разных подмножеств), представленный на рисунке 4: вершины сети разбиты на две группы - m поставщиков и n потребителей.

Известно [15], что граф является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины, или когда в нем все простые циклы имеют четную длину (теорема Кенига). Для поставщиков заданы имеющиеся у них количества единиц

товара (груза и т.д.) ab i = 1, m , для потребителей - требуемые им

количества единиц товара bh i = 1, n. Также известны затраты sij- перевозки единицы товара от i-го поставщика j-му потребителю.

mn

Пусть задача является замкнутой, то есть У ai = У bi - суммар-

i=1 i=1

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

ПОСТАВЩИКИ

ПОТРЕБИТЕЛИ

Рис. 4. Транспортная задача

Рис.

4. Транспортная задача

Формально транспортную задачу можно записать в виде:

mn

(1) У У xij sij ® min

? j=1 1 1 {Xj ^

(2) У xit = a„ i = 1, m

J=1

m

У xv = bp J =1 n •

i=1

Добавляя к двудольному графу вход «0» и выход «г» и соединяя вход и выход с остальными вершинами дугами с потоком

xffi = ait , i = 1,m, Xjz = bj, J = 1,n, получаем задачу о потоке минимальной стоимости. Алгоритмы решения транспортной и двойственной к ней задач описаны в [7, 12].

Частным случаем транспортной задачи является задача о назначении, заключающаяся в следующем: имеются n человек (работников), которые могут выполнять различные работы (занимать различные должности), число работ равно числу работников (введя фиктивные должности и/или фиктивные работы, всегда можно незамкнутую задачу привести к рассматриваемой замкнутой форме). Известны затраты sij на назначение i-го работника на j-ю должность (например, минимальная зарплата, за которую он согласится работать на этой должности). Требуется найти назначение работников на должности (каждого работника на одну и только одну должность), минимизирующее суммарные затраты (если sij интерпретируется как эффективность от работы i-го работника на j-ой должности, то оптимальное назначение должно максимизировать суммарную эффективность).

Формально задачу о назначении можно записать в виде (ср. с (1)-(3)):

nn

У У xiJ siJ ® min

и М {Xjj

У Xj = 1, i = 1n

J=1

Пусть имеются n = 3 работника и столько же работ. Матрица 1 2 3 затрат имеет вид: 2 4 7 5 3 8 Алгоритм 8.

Шаг 0. Назначаем каждого человека на самую дешевую для него работу (назначение выделено на рисунке 5 тонкими дугами),

о Г1, если Sj = min slk то есть положим хц = < к . Если при этом

[0, в противном случае

назначение является допустимым (то есть все работы выполняются), то решение получено. Если имеется «дисбаланс», то есть не

n

все работы выполняются ($j1: ^ x^ > 1), то переходим к сле-

i=1

РАБОТНИКИ

Рис.<div class=

5. Задача о назначении" />

Рис. 5. Задача о назначении

ДОЛЖНОСТИ [0]

2 )[1] [2]

Шаг к. Введем два подмножества множества дуг: P1 = {(i; j) | Xj = 1}, P2 = {(i; j) I Xj = 0}. Примем множество вершин-работ, на которых назначено несколько работников за вход сети, множество вершин-работ, которые не выполняются - за выход сети. Изменим направления дуг из множества P1 на обратные и примем их длины равными (-Sj), длины дуг из множества P2 примем равными Sj. Найдем путь / минимальной длины в полученной сети (потенциа- 22

дующему шагу.

лы вершин, вычисляемые при нахождении кратчайшего пути в рассматриваемом примере, приведены в квадратных скобках).

к

Далее полагаем xkj

к

xk если (i; j) g / 1 - xkесли (i; j) e /

В результате в рассматриваемом примере за один шаг получим оптимальное назначение, отличающееся от найденного на нулевом шаге тем, что первому работнику назначается третья работа (см. дугу, обозначенную двойными линиями на рисунке 5).

На каждом шаге число «дисбалансов» уменьшается на единицу. Следовательно, число шагов алгоритма не превышает числа «дисбалансов», которое конечно.

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

Решение общего случая задачи о потоке минимальной стоимости основывается на рассмотрении двойственной задачи [7, 12].

<< | >>
Источник: В.Н. Бурков, Д.А. Новиков. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ. 2001

Еще по теме Поток минимальной стоимости.:

  1. 4.3 Метод диагностического определения потребительной стоимости.
  2. Поток минимальной стоимости.
  3. СОВЕРШЕНСТВОВАНИЕ ТАМОЖЕННОГО КОНТРОЛЯ НА ОСНОВЕ РАМОЧНЫХ СТАНДАРТОВ БЕЗОПАСНОСТИ И ОБЛЕГЧЕНИЯ МИРОВОЙ ТОРГОВЛИ КАК ФАКТОР ЭКОНОМИЧЕСКОГО РАЗВИТИЯ (НА ПРИМЕРЕ КОНТРОЛЯ ТАМОЖЕННОЙ СТОИМОСТИ)
  4. 7.3. ДИСКОНТИРОВАНИЕ ДЕНЕЖНЫХ ПОТОКОВ ПРИ ОПРЕДЕЛЕНИИ ПОКАЗАТЕЛЕЙ ЭФФЕКТИВНОСТИ ИНВЕСТИЦИЙ
  5. Критерии оптимальности.
  6. СТОИМОСТЬ КАПИТАЛА
  7. КЛАССИФИКАЦИЯ ДЕНЕЖНЫХ ПОТОКОВ ПРЕДПРИЯТИЯ
  8. ИНФОРМАЦИОННАЯ СИСТЕМА V. І. УПРАВЛЕНИЯ ДЕНЕЖНЫМИ ПОТОКАМИ
  9. МЕТОДЫ ОЦЕНКИ ДЕНЕЖНЫХ ПОТОКОВ В УСЛОВИЯХ ИНФЛЯЦИИ
  10. ФОРМИРОВАНИЕ СИСТЕМЫ ЦЕЛЕВЫХ ПАРАМЕТРОВ ОРГАНИЗАЦИИ ДЕНЕЖНЫХ ПОТОКОВ ПРЕДПРИЯТИЯ
  11. МЕХАНИЗМ ФОРМИРОВАНИЯ [. ИНВЕСТИЦИОННОЙ ПРИБЫЛИ И ИНВЕСТИЦИОННОГО чистого ДЕНЕЖНОГО ПОТОКА
  12. Определение стоимости инвестиционного проекта.
  13. 6.2.Понятие стоимости капитала и ее особенности
- Аналитическая геометрия - Вариационное исчисление - Векторный и тензорный анализ - Высшая геометрия - Высшая математика - Вычислительная математика - Дискретная математика - Дифференциальное и интегральное исчисление - Дифференциальные уравнения - Исследование операций - История математики - Комплексное исчисление - Линейная алгебра - Линейное программирование - Математика для экономистов - Математическая логика - Математическая физика - Математический анализ - Пределы - Ряды - Статистика - Теория вероятностей - Теория графов - Теория игр - Теория принятия решений - Теория случайных процессов - Теория чисел - Функциональный анализ -
- Архитектура и строительство - Безопасность жизнедеятельности - Библиотечное дело - Бизнес - Биология - Военные дисциплины - География - Геология - Демография - Диссертации России - Естествознание - Журналистика и СМИ - Информатика, вычислительная техника и управление - Искусствоведение - История - Культурология - Литература - Маркетинг - Математика - Медицина - Менеджмент - Педагогика - Политология - Право России - Право України - Промышленность - Психология - Реклама - Религиоведение - Социология - Страхование - Технические науки - Учебный процесс - Физика - Философия - Финансы - Химия - Художественные науки - Экология - Экономика - Энергетика - Юриспруденция - Языкознание -