Некоторые обобщения задачи о максимальном потоке

 

Рассматриваются нестандартные задачи о максимальном потоке.

1. Задача о максимальном потоке с несколькими источниками и несколькими стоками. Пусть – ориентированный граф без петель и без параллельных дуг. Каждой дуге поставлена в соответствие пропускная способность. Среди вершин множества I выделены вершины: – источники и вершины – стоки. Мощность источников не ограничена, стоки могут принять любой поток. Требуется найти стационарный поток на сети, величина которого максимальна.

Решение этой задачи сводится к классической задаче о максимальном потоке (§ 8) применением следующего стандартного приема. Заданную сеть расширяют. К множеству вершин добавляют две новые вершины: s – общий источник и t – общий сток. Множество дуг пополняется дугами, которые связывают общий источник с заданными источниками, и дугами, связывающие заданные стоки с общим стоком. Таким образом, получаем сеть, где

, .

Новые дуги не должны стать на новой сети «узким» местом, поэтому пропускные способности новых дуг неограничены: .

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

v =.

2. Задача с нижними границами на пропускные способности дуг. Задана сеть, в которой выделены две вершины s и t – источник и сток Каждой дуге поставлены соответствие два неотрицательных числа: и – нижняя и верхняя пропускные способности дуги. Требуется найти поток из вершины s в вершину t максимальной величины, если выполняются условия:

\o(I\s\up2( + i -\o(I\s\up2( ( i=

£ x_ij £ , (i, j) Î U.

Для решения этой задачи применим модифицированный алгоритм Форда-Фалкерсона. Изменим в алгоритме (см. § 8) шаг 2б).

Шаг 2. б) если существует дуга, причем, то метка вершины имеет вид. Первая часть метки означает, что вершина j помечена через вершину i, причем дуга (j, i) является обратной дугой формируемого пути. Вторая часть метки вычисляется по правилу

.

Кроме этого заметим, что для данной задачи отдельно требуется решить вопрос о начальном допустимом потоке, поскольку нулевой поток допустимым не является.

3. Задача о максимальном потоке в смешанных сетях. Напомним, что граф называется смешанным, если в нем есть и дуги, и ребра. Поток по дуге имеет единственное направление: из вершины i в вершину j. Наличие ребра в графе означает, что поток может двигаться как в одном направлении, так и в обратном направлении (понятно, что не одновременно). Потоки и по дугам, и по ребрам не превышают заданной пропускной способности дуги или ребра. Как и прежде ставиться задача нахождения максимального потока. Чтобы можно было применить известный алгоритм, преобразуем сеть. Каждое ребро {i, j} заменим двумя дугами и, положив пропускную способность каждого равной пропускной способности ребра: d_ij = d_ji. На расширенной ориентированной сети с помощью алгоритма Форда-Фалкерсона решаем задачу. Затем в максимальном потоке просматриваем дуговые потоки, которые соответствуют ребрам.

Если для ребра {i, j} по дугами, имеем потоки такие, что, то поток пойдет по ребру из вершины i в вершину j, и его величина будет равна. Если же то поток по ребру пойдет из вершины j в вершину i, и его величина будет равна.

4. Задача о максимальном потоке в сетях с пропускными способностями вершин. Пусть в заданной сети с источником s и стоком t задано множество I_оÌ I, каждой вершине которого поставлено в соответствие положительное число a_i, iÎ I_о, – пропускная способность вершины. Требуется, как и прежде, найти поток из вершины s в вершину t максимальной величины, если выполняются условия (8.7), (8.8) и дополнительные условия для вершин с ограниченной пропускной способностью:

\o(I\s\up2( + i £ a_i, iÎ I_о.

Как и в п.1 решение задачи сводится к классической задаче о максимальном потоке на расширенной сети. Вместо каждой вершины kÎ I_о вводят две вершины k₁ и k₂ и дугу (k₁, k₂), которой приписывают пропускную способность, равную пропускной способности вершины: = a_k. Если две вершины k и j из множества I_о являются смежными, то дуга (k, j) преобразуется в дугу (k₂, j₁) (см. рис 9.1).

 

Задача о назначениях

 

1. Классическая задача о назначении. В книге [2, т.1] описана конкретная ситуация, приводящая к так называемой задаче о назначениях.

Задача фирмы «Электрон».Фирма, выпускающая сложную электронную аппаратуру, получила заказ объемом в несколько тысяч новых изделий, собирающихся из отдельных блоков. Руководство фирмы приняло решение разместить заказы на изготовление n блоков и выбрало n фирм-поставщиков, которые зарекомендовали себя ранее как производители высококачественной продукции. Каждый заказ настолько велик, что фирма-поставщик не может выполнить более одного заказа. Каждому поставщику предложено определить стоимость выполнения заказа, т.е. цену, по которой он готов поставить фирме блоки. Некоторые из запрошенных цен настолько велики, что явно свидетельствуют о нежелании отдельных поставщиков принять заказы на определенные блоки. Располагая этой информацией, фирма электронной аппаратуры должна заключить n контрактов на поставку ей n видов блоков, минимизировав при этом свои общие затраты на приобретение комплектующих узлов со стороны.

Математическая модель задачи. Пусть имеется n работ и n исполнителей, каждый из которых может выполнить любую работу. Известны выплаты, которые следует сделать каждому исполнителю за выполнение любой имеющейся работы. Ставится задача распределения исполнителей по работам таким образом, чтобы каждая работа выполнялась только одним исполнителем, каждый исполнитель выполнял только одну работу, и выплаты при этом были бы минимальны.

Введем обозначения. Через I = {1, 2, …, n} обозначим множество работ, через J = {1, 2, …, n} – множество исполнителей, через c_ij – «стоимость» назначения на i-ую работу j-го исполнителя. Переменные в задаче определим следующим образом:

(9.1)

Ограничения на переменные определяются тем, что каждая работа должна быть выполнена одним исполнителем:

iÎ I, (9.2)

и каждый исполнитель выполняет только одну работу:

, jÎ J. (9.3)

Совокупность переменных x = (x₁₁, x₁₂, …, x_nn), которая удовлетворяет условиям (9.1)-(9.3), назовем назначением. Очевидно, что суммарные выплаты, которые следует минимизировать, задаются функцией:

® min. (9.4)

На практике встречаются задачи о назначениях, в которых элемент c_ij выражает эффективность назначения на i-ую работу j-го исполнителя. Тогда целевая функция есть суммарная эффективность назначения, а значит, следует найти ее максимальное значение

® max (9.5)

при тех же ограничениях (9.1)-(9.3).

Далее будем рассматривать задачу (9.1)-(9.4).

Совокупность x^o = (, …, ), удовлетворяющую условиям (9.1)-(9.3), на которой функция (9.4) принимает минимальное значение, назовем оптимальным назначением.

Коэффициенты целевой функции (9.4) удобно задать в виде матрицы n-го порядка

C = (c_ij, iÎ I, jÎ J).

Выполним операцию приведения матрицы C. Для этого в каждой строке выбираем минимальный элемент

u_i =, iÎ I,

и вычитаем его из каждого элемента этой строки. В результате получим матрицу С₁, в каждой строке которой имеется по крайней мере один нулевой элемент. Затем в каждом столбце j матрицы С₁ находим минимальный элемент v_j, и вычитаем его из каждого элемента столбца. В результате получим матрицу C₂, у которой в каждом столбце и каждой строке имеется хотя бы один нулевой элемент. Числа u_i и v_j, которые вычитались, называются константами приведения.

Лемма 1. Оптимальное назначение в задаче (9.1)-(9.4) является оптимальным в задаче (9.1)-(9.3) с целевой функцией

, (9.6)

где u_i и v_j – константы приведения матрицы С. И обратно, оптимальное назначение в задаче (9.1)-(9.3), (9.6) является оптимальным для задачи (9.1)-(9.4).

Доказательство. Преобразуем сумму (9.6), раскрыв скобки и перегруппировав слагаемые,

= =

= - - =
= - -

Далее учтем ограничения (9.2) и (9.3):

= - -.

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

Лемма 2. Если в задаче (9.1)-(9.4) все элементы матрицы С неотрицательны, и имеется такое назначение x = (x₁₁, x₁₂, …, x_nn), что

= 0, (9.7)

то это назначение оптимально.

Доказательство. Очевидно.

Рассмотрим алгоритм решения задачи о назначениях, в котором используется алгоритм решения задачи о максимальном потоке.

Предварительный шаг алгоритма состоит в приведении исходной матрицы, т.е. переход от матрицы C к матрице C₂.

Общий шаг. 1) На основании матрицы C₂ строим двудольный орграф, где – множество вершин, которые соответствуют работам, – множество вершин, соответствующих исполнителям. Дуга (s_i, t_j)Î U, если соответствующий элемент матрицы C₂ равен нулю.

2) По графу G строим расширенную сеть: вводим две дополнительные вершины s и t – источник и сток, и дополнительные дуги из источника s в вершины множества S и из вершин множества Т в сток t. Пропускные способности всех дуг полагаем равными единице.

3) На полученной сети решаем задачу о нахождении максимального потока из источника s в сток t.

4) Если величина максимального потока v = n, то решение закончено. Оптимальное назначение соответствует дугам вида (s_i, t_j), для которых величина дугового потока равна единице. Оптимальность назначения следует из леммы 2, поскольку каждой такой дуге соответствует нулевой элемент матрицы С₂.

5) Если величина максимального потока меньше n, то необходимо ввести дополнительные дуги вида (s_i, t_j), чтобы увеличить мощность потока. Необходимую для этого информацию можем извлечь из последнего шага алгоритма построения максимального потока.

Пусть S_пом – множество вершин, помеченных на последнем шаге алгоритма (S_помÌ S), T_неп – множество вершин, непомеченных на последнем шаге алгоритма (T_непÌ T). Ясно, что надо ввести новую дугу из S_пом в T_неп. В матрице С₂ рассмотрим элементы на пересечении строк, соответствующих вершинам из S_пом, и столбцов, соответствующих вершинам из T_неп (на рис. 9.1 заштрихованный блок). Пусть c – минимальный среди них элемент. Вычитаем число c из всех элементов, соответствующих вершинам из S_пом, и прибавляем c ко всем элементам столбцов, соответствующих вершинам из T_пом. Переходим к пункту 1) общего шага.

Заметим, что. В противном случае, т.е. при, в сети существует дуга (s_i, t_j), где и, чего не может быть согласно алгоритму Форда-Фалкерсона. В результате преобразования матрицы в заштрихованном блоке появится новый нулевой элемент, а значит, появится новая дуга (s_i, t_j), где и. Кроме этого отметим, что элементы матрицы на пересечении строк, соответствующих вершинам из S_неп, и столбцов, соответствующих вершинам из T_пом, увеличиваются на c. Это означает, что в новой сети может исчезнуть дуга, где s_iÎ S_неп и t_jÎ T_пом, но эта дуга «бесполезна», т.к. вершину t_j все же пометили, но не через вершину s_i.

Конечность алгоритма следует из того, что добавление новой дуги приводит к тому, что в результате алгоритма Форда-Фалкерсона помечается дополнительно, по крайней мере, одна вершина. Число вершин конечно, поэтому рано или поздно произойдет увеличение потока на единицу. Общая же величина потока ограничена сверху числом n.

Замечание. Если задача о назначениях есть задача максимизации (9.1)-(9.3), (9.5), то прежде, чем применять описанный выше алгоритм, преобразуем матрицу C. Найдем максимальный элемент среди всех элементов матрицы: = m. Далее получим матрицу, где. Нетрудно доказать, что оптимальное назначение, на котором целевая функция достигает минимума, является оптимальным назначением, на котором целевая функция достигает максимума.

Пример 1. Найти оптимальное назначение в задаче на минимизацию целевой функции, если матрица «стоимости» назначений имеет вид

С =.

Решение. Выполним процедуру приведение матрицы. Константы приведения по строкам равны 3, 6, 3, 4, 1. В полученной матрице С₁ константы приведения по столбцам равны 0, 0, 0, 2, 0. В результате имеем матрицу С₂.

С₁ =, С₂ =.

Сеть, соответствующая матрице С₂ изображена на рис. 9.2, здесь, . Первый общий шаг алгоритма приводит к построению максимального потока, величина v которого равна 4 < n = 5. На последнем шаге алгоритма Форда-Фалкерсона удалось пометить вершины s, s₃, t₂, s₂ (на рис.9.2 эти вершины отмечены знаком «плюс»). Следовательно, S_пом = {s₂, s₃}, T_неп = {t₁, t₃, t₄, t₅}. В матрице С₂ на пересечении строк, соответствующих вершинам из S_пом, и столбцов, соответствующих вершинам из T_неп находятся элементы:

,

минимальный элемент среди них равен c = 2. Вычитаем число 2 из всех элементов второй и третьей строк, и прибавляем число c ко всем элементам второго столбца. Получим новую матрицу

Сеть, соответствующая матрице С₃ изображена на рис.9.3. Общий шаг алгоритма приводит к построению максимального потока, величина которого равна n = 5. Дуговые потоки единичной величины идут по дугам (s₁, t₅), (s₂, t₂), (s₃, t₁), (s₄, t₃), (s₅, t₄). Этому потоку соответствуют назначения:

на 1-ую работу 5-ый исполнитель,

на 2-ую работу 2-ый исполнитель,

на 3-ую работу 1-ый исполнитель,

на 4-ую работу 3-ий исполнитель,

на 5-ую работу 4-ый исполнитель.

Стоимость такого назначения равна 3 + 6 + 5 + 4 + 3 = 21.

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

2. Задача о максимальной занятости.Пусть имеется n исполнителей и m работ. Каждый исполнитель может выполнять определенные работы из указанного перечня работ. Требуется назначить исполнителей на работы таким образом, чтобы занять максимальное количество исполнителей.

Схема решения. Определим nхm-матрицу назначений

C = (c_ij, , ),

где элемент с_ij равен нулю тогда и только тогда, когда i-ый исполнитель может выполнять j-ую работу, и не равен нулю в противном случае. На основании матрицы C строим двудольный орграф, где – множество вершин, которые соответствуют исполнителям, – множество вершин, соответствующих работам. Дуга (s_i, t_j)Î U, если соответствующий элемент матрицы C равен нулю. Как и в классической задаче о назначениях, по графу G строим расширенную сеть, и на полученной сети решаем задачу нахождении максимального потока из источника s в сток t. Величина максимального потока v есть максимальное число исполнителей, которые назначаются на работы. Конкретные назначения определяем по дугам вида (s_i, t_j), для которых величина дугового потока равна единице.

3. Задача о назначении на «узкие» места.Пусть имеется n работ и n исполнителей. Каждый исполнитель i может выполнять любую работу j. Требуется найти такое назначение исполнителей на работы, чтобы наименьшая эффективность среди конкретных назначений работника i на j-ую работу была наибольшей. Предполагается, что любой исполнитель выполняет только одну работу, и каждая работа выполняется только одним исполнителем.

Примером такой задачи может служить распределение рабочих на конвейере. Под эффективностью понимается скорость выполнения конкретным исполнителем определенной операции на конвейере. Ясно, что скорость движения конвейера определяется минимальной эффективностью.

Схема решения. Задана матрицу A =, где a_ij – эффективность назначения i-го работника на j-ую работу. Любое назначение можно представить в виде подстановки

,

p(i) – номер работы, на которую назначен i-ый исполнитель. Произвольному назначению поставим в соответствие вектор эффективностей:

,

и определим число

.

Ясно, что требуется найти подстановку P⁰, для которой F(P⁰) будет максимальным. Заметим, что число подстановок равно n!, и поэтому решение перебором всех подстановок не рационально.

Пусть задано некоторое начальное назначение

,

и найдено число F(P₀). Определим квадратную матрицу n-го порядка

C =,

где элемент с_ij равен нулю, если a_ij > F(P₀), и не равен нулю в противном случае. По матрице C строим двудольный орграф, где – множество вершин, которые соответствуют исполнителям, – множество вершин, соответствующих работам. Дуга (s_i, t_j)Î U, если соответствующий элемент матрицы C равен нулю. Как и в классической задаче о назначениях, по графу G строим расширенную сеть, и на полученной сети решаем задачу нахождении максимального потока из источника s в сток t. Если величина максимального потока v = n, то по дугам вида (s_i, t_j), для которых величина дугового потока равна единице, находим новое назначение P₁, и соответствующее ему число F(P₁). Очевидно, что F(P₁)> F(P₀). Затем повторяем шаг алгоритма, определив матрицу C, исходя из новой оценки F(P₁). Если величина максимального потока v < n, то имеющееся назначение оптимально.

 

Задания к лабораторным работам

 

11.1 Лабораторная работа «Построение остовного дерева минимального веса»

Задание. Дан неориентированный граф. Требуется построить остовное дерево минимального веса, используя а) алгоритм Прима, б) алгоритм Краскала. Выполнить чертеж.

В таблице 1 приведены множества I, U и веса ребер соответственно перечислению их в U.

 

Таблица 1

Вариант 1	I
U	{{1, 2}, {1, 5}, {1, 4}, {2, 3}, {2, 5}, {3, 5}, {3, 6}, {4, 5}, {4, 7}, {5, 6}, {5, 7}, {5, 8}, {5, 9}, {6, 9}, {7, 8}, {8, 9} }
веса	10, 4, 3, 9, 11, 5, 12, 6, 15, 13, 10, 4, 7, 8, 4, 8
Вариант 2	I
U	{{1, 2}, {1, 4}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {3, 6}, {4, 5}, {4, 7}, {4, 8}, {5, 6}, {5, 8}, {6, 8}, {6, 9}, {7, 8}, {8, 9} }
веса	10, 5, 3, 9, 11, 5, 10, 6, 15, 13, 10, 5, 7, 8, 4, 8
Вариант 3	I
U	{{1, 2}, {1, 5}, {1, 4}, {2, 3}, {2, 5}, {3, 5}, {3, 6}, {4, 5}, {4, 7}, {4, 8}, {5, 6}, {5, 8}, {6, 8}, {6, 9}, {7, 8}, {8, 9}}
веса	10, 14, 13, 9, 11, 15, 12, 16, 15, 13, 10, 14, 7, 8, 14, 8
Вариант 4	I
U	{{1, 2}, {1, 5}, {1, 4}, {2, 3}, {2, 4}, {2, 5}, {3, 5}, {3, 6}, {4, 5}, {4, 7}, {4, 8}, {5, 6}, {5, 8}, {5, 9}, {7, 8}, {8, 9} }
веса	15, 14, 23, 19, 16, 15, 14, 26, 25, 23, 20, 24, 27, 18, 14, 18
Вариант 5	I
U	{{1, 2}, {1, 5}, {1, 4}, {2, 3}, {2, 5}, {3, 5}, {3, 6}, {4, 5}, {4, 7}, {5, 7}, {5, 8}, {5, 9}, {6, 8}, {6, 9}, {7, 9}, {8, 9} }
веса	20, 15, 22, 16, 25, 17, 18, 14, 18, 14, 13, 19, 21, 23, 20, 24
Вариант 6	I
U	{{1, 2}, {1, 5}, {1, 4}, {2, 3}, {2, 5}, {3, 5}, {3, 6}, {4, 5}, {4, 7}, {5, 6}, {5, 7}, {5, 8}, {5, 9}, {6, 9}, {7, 8}, {8, 9} }
веса	5, 15, 4, 8, 10, 4, 3, 9, 11, 13, 12, 6, 10, 4, 7, 8,
Вариант 7	I
U	{{1, 2}, {1, 4}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {3, 6}, {4, 5}, {4, 7}, {4, 8}, {5, 6}, {5, 8}, {6, 8}, {6, 9}, {7, 8}, {8, 9} }
веса	11, 5, 4, 7, 10, 5, 10, 6, 15, 13, 10, 5, 9, 8, 3, 8
Вариант 8	I
U	{{1, 2}, {1, 5}, {1, 4}, {2, 3}, {2, 5}, {3, 5}, {3, 6}, {4, 5}, {4, 7}, {4, 8}, {5, 6}, {5, 8}, {6, 8}, {6, 9}, {7, 8}, {8, 9}}
веса	14, 14, 12, 8, 10, 15, 13, 16, 15, 13, 11, 10, 7, 8, 14, 9
Вариант 9	I
U	{{1, 2}, {1, 5}, {1, 4}, {2, 3}, {2, 4}, {2, 5}, {3, 5}, {3, 6}, {4, 5}, {4, 7}, {4, 8}, {5, 6}, {5, 8}, {5, 9}, {7, 8}, {8, 9} }
веса	25, 23, 20, 24, 14, 18, 15, 14, 23, 19, 27, 18, 16, 15, 14, 26,
Вариант 10	I
U	{{1, 2}, {1, 5}, {1, 4}, {2, 3}, {2, 5}, {3, 5}, {3, 6}, {4, 5}, {4, 7}, {5, 7}, {5, 8}, {5, 9}, {6, 8}, {6, 9}, {7, 9}, {8, 9} }
веса	23, 20, 24, 17, 15, 22, 16, 18, 14, 18, 20, 14, 13, 19, 21, 25
Вариант 11	I
U	{{1, 2}, {1, 5}, {1, 4}, {2, 3}, {2, 5}, {3, 5}, {3, 6}, {4, 5}, {4, 7}, {5, 6}, {5, 7}, {5, 8}, {5, 9}, {6, 9}, {7, 8}, {8, 9} }
веса	4, 11, 5, 12, 6, 15, 4, 8, 3, 9, 13, 10, 7, 8, 4, 10.
Вариант 12	I
U	{{1, 2}, {1, 4}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {3, 6}, {4, 5}, {4, 7}, {4, 8}, {5, 6}, {5, 8}, {6, 8}, {6, 9}, {7, 8}, {8, 9} }
веса	10, 5, 3, 8, 11, 5, 10, 4, 13, 15, 10, 5, 7, 9, 7, 8

 

Вариант 13	I
U	{{1, 2}, {1, 5}, {1, 4}, {2, 3}, {2, 5}, {3, 5}, {3, 6}, {4, 5}, {4, 7}, {4, 8}, {5, 6}, {5, 8}, {6, 8}, {6, 9}, {7, 8}, {8, 9}}
веса	11, 15, 12, 14, 7, 8, 14, 8, 10, 14, 13, 9, 16, 15, 13, 10
Вариант 14	I
U	{{1, 2}, {1, 5}, {1, 4}, {2, 3}, {2, 4}, {2, 5}, {3, 5}, {3, 6}, {4, 5}, {4, 7}, {4, 8}, {5, 6}, {5, 8}, {5, 9}, {7, 8}, {8, 9} }
веса	14, 26, 25, 23, 20, 16, 15, 23, 19, 24, 27, 18, 14, 18, 15, 14,
Вариант 15	I
U	{{1, 2}, {1, 5}, {1, 4}, {2, 3}, {2, 5}, {3, 5}, {3, 6}, {4, 5}, {4, 7}, {5, 7}, {5, 8}, {5, 9}, {6, 8}, {6, 9}, {7, 9}, {8, 9} }
веса	20, 14, 13, 19, 21, 15, 22, 16, 25, 23, 20, 24, 17, 18, 14, 18
Вариант 16	I
U	{{1, 2}, {1, 5}, {1, 4}, {2, 3}, {2, 5}, {3, 5}, {3, 6}, {4, 5}, {4, 7}, {5, 6}, {5, 7}, {5, 8}, {5, 9}, {6, 9}, {7, 8}, {8, 9} }
веса	10, 8, 4, 8, 4, 3, 10, 4, 5, 12, 6, 7, 9, 11, 15, 13

 

11.2 Лабораторная работа «Нахождение кратчайшего пути на сети »

Задание. Дана сеть. В таблице 2 приведены множества I, U и веса дуг соответственно перечислению их в U. Вес дуги – расстояние между соответствующими вершинами.

а) Найти кратчайший путь из вершины 1, в вершину 9, используя алгоритм Дейкстра.

б) По алгоритму Флойда найти кратчайшие расстояния между любой парой вершин графа. Дать комментированный ответ для двх пар вершин (например, для вершин 1 и 8, 3 и 9)

Таблица 2

Вариант 1	I
U	{(1, 2), (1, 4), (2, 3), (2, 5), (3, 5), (3, 6), (4, 5), (4, 7), (5, 1), (5, 6), (5, 7), (5, 8), (6, 9), (7, 8), (8, 9), (9, 5) }
веса	10, 4, 3, 9, 11, 5, 12, 6, 11, 13, 10, 4, 7, 8, 6, 8
Вариант 2	I
U	{(1, 2), (1, 4), (2, 3), (2, 5), (3, 6), (4, 2), (4, 5), (4, 7), (4, 8), (5, 6), (5, 8), (5, 9), (6, 9), (7, 8), (8, 9) }
веса	10, 5, 3, 9, 11, 5, 10, 6, 15, 13, 10, 5, 7, 8, 4
Вариант 3	I
U	{(1, 2), (1, 4), (1, 5), (2, 3), (2, 6), (3, 6), (4, 5), (4, 7), (5, 2), (5, 6), (5, 7), (6, 8), (7, 8), (8, 9) }
веса	10, 14, 13, 9, 11, 15, 12, 16, 15, 13, 10, 14, 7, 8,
Вариант 4	I
U	{(1, 2), (1, 4), (2, 3), (2, 4), (2, 6), (3, 6), (4, 5), (4, 7), (4, 8), (5, 2), (5, 8), (6, 5), (6, 8), (6, 9), (7, 8), (8, 9) }
веса	25, 14, 23, 19, 16, 15, 4, 22, 28, 6, 26, 24, 27, 18, 14, 18
Вариант 5	I
U	{(1, 2), (1, 4), (2, 3), (2, 5), (3, 5), (3, 6), (4, 5), (4, 7), (5, 1), (5, 6), (5, 7), (5, 8), (6, 9), (7, 8), (8, 9), (9, 5)}
веса	20, 15, 22, 16, 25, 17, 18, 14, 18, 14, 13, 19, 21, 23, 20, 24
Вариант 6	I
U	{(1, 2), (1, 4), (2, 3), (2, 5), (3, 6), (4, 2), (4, 5), (4, 7), (4, 8), (5, 6), (5, 8), (5, 9), (6, 9), (7, 8), (8, 9) }
веса	5, 15, 4, 8, 10, 4, 3, 9, 11, 12, 6, 10, 4, 7, 8,
Вариант 7	I
U	{(1, 2), (1, 4), (1, 5), (2, 3), (2, 6), (3, 6), (4, 5), (4, 7), (5, 2), (5, 6), (5, 7), (6, 8), (7, 8), (8, 9) }
веса	5, 4, 7, 10, 5, 6, 15, 13, 10, 5, 9, 8, 3, 8
Вариант 8	I
U	{(1, 2), (1, 4), (2, 3), (2, 4), (2, 6), (3, 6), (4, 5), (4, 7), (4, 8), (5, 2), (5, 8), (6, 5), (6, 8), (6, 9), (7, 8), (8, 9) }
веса	14, 14, 12, 8, 10, 15, 13, 16, 15, 13, 11, 10, 7, 8, 14, 9
Вариант 9	I
U	{(1, 2), (1, 4), (2, 3), (2, 5), (3, 5), (3, 6), (4, 5), (4, 7), (5, 1), (5, 6), (5, 7), (5, 8), (6, 9), (7, 8), (8, 9), (9, 5)}
веса	25, 23, 20, 24, 14, 18, 15, 14, 23, 19, 27, 18, 16, 15, 14, 26,
Вариант 10	I
U	{(1, 2), (1, 4), (2, 3), (2, 5), (3, 6), (4, 2), (4, 5), (4, 7), (4, 8), (5, 6), (5, 8), (5, 9), (6, 9), (7, 8), (8, 9) }
веса	23, 20, 24, 17, 15, 22, 16, 14, 18, 20, 14, 13, 19, 21, 25
Вариант 11	I
U	{(1, 2), (1, 4), (1, 5), (2, 3), (2, 6), (3, 6), (4, 5), (4, 7), (5, 2), (5, 6), (5, 7), (6, 8), (7, 8), (8, 9) }
веса	4, 11, 5, 12, 6, 15, 4, 8, 3, 9, 13, 10, 7, 8
Вариант 12	I
U	{(1, 2), (1, 4), (2, 3), (2, 4), (2, 6), (3, 6), (4, 5), (4, 7), (4, 8), (5, 2), (5, 8), (6, 5), (6, 8), (6, 9), (7, 8), (8, 9) }
веса	10, 5, 3, 8, 11, 5, 10, 4, 13, 15, 10, 5, 7, 9, 7, 8
Вариант 13	I
U	{(1, 2), (1, 4), (2, 3), (2, 5), (3, 5), (3, 6), (4, 5), (4, 7), (5, 1), (5, 6), (5, 7), (5, 8), (6, 9), (7, 8), (8, 9), (9, 5)}
веса	11, 15, 12, 14, 7, 8, 14, 8, 10, 14, 13, 9, 16, 15, 13, 10
Вариант 14	I
U	{(1, 2), (1, 4), (2, 3), (2, 5), (3, 6), (4, 2), (4, 5), (4, 7), (4, 8), (5, 6), (5, 8), (5, 9), (6, 9), (7, 8), (8, 9) }
веса	14, 26, 25, 23, 20, 16, 15, 23, 19, 24, 27, 18, 14, 18, 15
Вариант 15	I
U	{(1, 2), (1, 4), (1, 5), (2, 3), (2, 6), (3, 6), (4, 5), (4, 7), (5, 2), (5, 6), (5, 7), (6, 8), (7, 8), (8, 9) }
веса	20, 14, 13, 19, 21, 15, 22, 16, 20, 24, 17, 18, 14, 18
Вариант 16	I
U	{(1, 2), (1, 4), (2, 3), (2, 4), (2, 6), (3, 6), (4, 5), (4, 7), (4, 8), (5, 2), (5, 8), (6, 5), (6, 8), (6, 9), (7, 8), (8, 9) }
веса	10, 8, 4, 8, 4, 3, 10, 4, 5, 12, 6, 7, 9, 11, 15, 13

 

 

11.3 Лабораторная работа «Нахождение на сети потока максимальной величины»

Задание. Дана сеть. В таблице 2 приведены множества I, U и веса дуг соответственно перечислению их в U. Вес дуги – пропускная способность дуги. Считаем вершину 1 источником, вершину 9 – стоком.

а) Найти поток максимальной величины из источника в сток, используя алгоритм Форда-Фалкерсона.

б) Найти соответствующий найденному потоку разрез минимальной пропускной способности.

 

11.4 Лабораторная работа «Нахождение оптимального назначения»

Задание. В таблице 3 для каждого варианта дана квадратная матрица, которая для задания а) является матрицей стоимостей назначения на i-ую работу j-го исполнителя, для задания б) является матрицей эффективностей назначения на i-ую работу j-го исполнителя.

а) Найти оптимальное назначение, минимизирующее суммарную стоимость назначений.

б) Найти оптимальное назначение, максимизирующее суммарную эффективность назначений.

Вариант 1	Вариант 2	Вариант 3
Вариант 4	Вариант 5	Вариант 6
Вариант 7	Вариант 8	Вариант 9
Вариант 10	Вариант 11	Вариант 12
Вариант 13	Вариант 14	Вариант 15
Вариант 16	Вариант 17	Вариант 18

 

ЛИТЕРАТУРА

 

1. Бахтин В.И. и др. Исследование операций. Курс лекций. – Мн.: БГУ, 2003.

2. Вагнер Г. Основы исследования операций. Т. 1, т. 2, т. 3. – М.: Мир, 1972, 1973, 1973.

3. Волков И.К., Загоруйко Е.А. Исследование операций: учеб. для вузов. – 2-е изд. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2002.

4. Высшая математика для экономистов: учебник: в 3 т.– Мн.: БГЭУ, 2005. – Т. 2.

5. Костюкова О.И. Исследование операций: учеб. пособие для студ. спец.31 03 04 «Информатика» всех форм обучения. – Мн.: БГУИР, 2003. – 94 с.: ил.

6. Котов В.М., Мельников О.И.. Информатика: методы алгоритмизации: учеб. пособие для 10–11-х кл. общеобразоват. шк. с углубл. изучением информатики. – Мн.: Нар. асвета, 2000. – 221 с.: ил.

7. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика: Математическое программирование. – Мн.: Выш. шк., 1994.

 

 

⇐ Предыдущая123456

Поделиться: