Пусть [15] в пунктах A1, A2, ... ,Am производят некоторый
однородный продукт в объеме ai (i=1, 2, ... , m)
единиц. В пунктах B1,
B2, ... ,Bn этот продукт потребляется в объеме bj
( j=1, 2, ... , n )
единиц. Из каждого {Ai} возможна
транспортировка в любой Bj. Транспортные
издержки} по перевозке из пункта Ai в пункт Bj единицы
продукции
равны cij (i=1, ... , m; j=1, ... , n).
Необходимо найти такой план перевозок, при котором запросы всех потребителей полностью удовлетворены, весь продукт из пунктов производства вывезен и суммарные транспортные издержки минимальны.
Пусть xij — количество продукта, перевозимого из
пункта Ai в
пункт Bj. Требуется найти значение переменных
(перевозок) xij >= 0 (i = 1, 2, ... , m ; j
= 1, 2, ... , n), удовлетворяющих$$\begin{equation}
Z(x_{ij} ) = \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n {c_{ij}
x_{ij} \quad \to \;\min } }
\end{equation}$$
при ограничениях
$$\begin{equation} \begin{gathered} \sum\limits_{j = 1}^n {x_{ij} = a_i } ,\quad i = 1,...,\;m, \hfill \\ \sum\limits_{i = 1}^m {x_{ij} = b_j } ,\quad j = 1,...,\;n, \hfill \\ \end{gathered} \end{equation}$$
при условии неотрицательности
xij >= 0 (5.3)
и баланса
$$\begin{equation}
\sum\limits_{i = 1}^m {a_i = \sum\limits_{j = 1}^n {b_j .} }
\end{equation}$$
Как известно, условие баланса приводит к линейной зависимости
уравнений в системе (5.2), ранг ее матрицы равен m+n-1.
Сформулируем задачу линейного программирования в канонической постановке, исключив из (5.2) одно уравнение. При этом мы считаем, что условие баланса (5.4) оказывает влияние на корректность постановки задачи и учтено при этой постановке. Исключенное уравнение будем использовать также для контроля получаемого решения.
Следуя плану параллельного решения задачи линейного
программирования и учитывая, что оптимальное решение находится хотя бы
в одной из вершин многогранника допустимых решений, образуемого
ограничениями и условиями, сформируем это множество граней. В его состав
войдут m+n-1 выделенных уравнений-ограничений и m x
n равенств
нулю переменных на основе неотрицательности решения. Выбирая из этой
системы по m x n уравнений с обязательным участием всех
выделенных уравнений-ограничений и решая их совместно, мы можем
находить вершины многогранника решений.
Так мы можем реализовать метод прямого перебора. Количество
вариантов составляет Cm x nm x n - (m + n - 1) .
Это —
количество различных способов приравнивания нулю m x
n-(m+n-1) переменных из их общего числа m x n.
Мы можем реализовать и аналог симплекс-метода, найдя первоначально некоторую вершину, а затем перемещаясь по ребрам в одну из смежных вершин с большим значением целевой функции, пока это возможно.
Исследование плана параллельного решения и формирование алгоритма будем сопровождать примером, для проверки правильности заимствованным в [15]. Для краткости условия (5.3) и (5.4) опущены.
Пример.
Z=7x11+8x12+5x13+3x14+2x21+4x22+5x23+
+9x24+6x31+3x32+1x33+2x34-> min (5.5)
при ограничениях
x11 + x12 + x13 + x14 = 11
x21 + x22 + x23 + x24 = 11
x31 + x32 + x33 + x34 = 8
x11 + x21 + x31 = 5 (5.6)
x12 + x22 + x32 = 9
x13 + x23 + x33 = 9
x14 + x24 + x34 = 7
Введем xij = yk, где k =
(i - 1)n + j.
Исключим из рассмотрения последнее уравнение. Система уравнений граней (действительных и возможных) многогранника решений примет вид
y1 + y2 + y3 + y4 = 11
y5 + y6 + y7 + y8 = 11
y9 + y10 + y11 + y12 = 8 (5.7)
y1+y5+ y9=5
y2+y6+y10 = 9
y3+ y7+ y11 = 9
yk = 0, k = 1, 2, ... , 12.
Итак, на первом этапе задача свелась к выбору и анализу комбинаций
по 12 - 6 = 6 нулевых значений координат искомой вершины
многогранника
решений. Выполняя подстановку выбранной комбинации в (5.7), мы можем
решить образовавшуюся систему шести уравнений с шестью неизвестными.
Таким образом, мы сможем найти координаты некоторой вершины.
Комбинации по шесть нулевых значений координат ("комбинации
нулей") следует выбирать так, чтобы не обратилась в нуль левая часть хотя
бы одного уравнения (5.7), включая исключенное уравнение. Например,
комбинация, где y1 = y2 = y3 = y4 = 0, недопустима.
Найдем дополнительные контрольные ограничения: чтобы решение
было не отрицательным, необходимо, чтобы любое
значение yk, k =
1, ... , m x n, не превышало значение
Тогда в нашем примере y1 <= min(11, 5) =,
аналогично y2 <= , y3 <= , y4 <= , y5 <= , y6 <= , y7 <= , y8 <= , y9 <= , y10 <= , y11 <=, y12 <=
.
Здесь при оценке y4, y8, y12 учтено
последнее уравнение в (5.6).
Воспользуемся векторной формой представления, чтобы подготовить
удобные, нетрудоемкие матричные преобразования. А именно, наша система m
+ n - 1 линейных уравнений-ограничений имеет вид
AY = B,
где A — нуль-единичная матрица, Y —
столбец переменных, B —
столбец свободных членов:$$\begin{equation}
\setcounter{MaxMatrixCols}{20}
\begin{pmatrix}
\colorbox[gray]{0.8}1 \colorbox[gray]{0.8}1 1 1 \colorbox[gray]{0.8}0 0 \colorbox[gray]{0.8}0 0 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0\\
\colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 0 \colorbox[gray]{0.8}1 1 \colorbox[gray]{0.8}1 1 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0\\
\colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 0 \colorbox[gray]{0.8}0 0 \colorbox[gray]{0.8}0 0 1 \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}1 1\\
\colorbox[gray]{0.8}1 \colorbox[gray]{0.8}0 0 0 \colorbox[gray]{0.8}1 0 \colorbox[gray]{0.8}0 0 1 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0\\
\colorbox[gray]{0.8}0 \colorbox[gray]{0.8}1 0 0 \colorbox[gray]{0.8}0 1 \colorbox[gray]{0.8}0 0 0 \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}0 0\\
\colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 1 0 \colorbox[gray]{0.8}0 0 \colorbox[gray]{0.8}1 0 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}1 0\\
\end{pmatrix}
\times
\begin{pmatrix}
y_{1}\\
y_{2}\\
y_{3}\\
y_{4}\\
y_{5}\\
y_{6}\\
y_{7}\\
y_{8}\\
y_{9}\\
y_{10}\\
y_{11}\\
y_{12}\\
\end{pmatrix}
=\begin{pmatrix}
11\\
11\\
8\\
5\\
9\\
9
\end{pmatrix}
\end{equation}$$
Тогда для нахождения хотя бы одного допустимого решения выберем допустимую комбинацию нулей по следующему алгоритму:
l = 0.l := l + 1, yl = 0. Исключим из
матрицы A столбец,
соответствующий этой переменной.A строка, содержащая только нулевые
элементы, или обратилась ли в нуль левая часть исключенного уравнения.
(Предполагаем, что все свободные члены уравнений больше нуля.) При
положительном результате анализа выполняем шаг 5. В противном случае —
следующий шаг.s -й строки A выделяем
множество {ys} переменных, соответствующих единичным элементам.
Проверяем: $$\sum\limits_s {\bar y_s } \geqslant b_s$$?При
отрицательном результате анализа (свободный член превышает
сумму верхних оценок переменных) выполняем шаг 5. В случае успешной
проверки 3 и 4 выполняем шаг 6.yl =
0 выбрано неудачно. Отменяем исключение столбца, соответствующего
переменной yl, и выполняем шаг 2.yl = 0, и если комбинация нулей сформирована не
полностью, выполняем шаг 2.Продолжим рассмотрение примера.
Полагаем y1 = 0. Это не приводит к нарушению оценок, указанных
в алгоритме.
Полагаем y2 = 0. Это также не приводит к нарушению оценок.
Полагаем y3 = 0. Нулевые строки не появились. Однако в первой
строке осталась единственная единица, соответствующая
переменной y4.
Т.к.
Полагаем y4 = 0. Нулевые строки не появились, однако в первой
же
строке осталась единственная единица, соответствующая
переменной y3.
Т.к.
Полагаем y5 = 0. Это не приводит к нарушению оценок.
Полагаем y6 = 0. В пятой строке остается единственная единица,
соответствующая y10. Т.к.
Полагаем y7 = 0, что не приводит к нарушению оценок.
Значение y8 = 0 приводит к нарушению оценки во втором
уравнении.
Значение y9 = 0 приводит к появлению нулевой строки.
Значение y10 = 0 не приводит к нарушению оценок.
Значение y11 = 0 также не приводит к нарушению оценок.
Итак, комбинация нулей найдена. Это отмеченные в (5.8) значения
y1 = 0, y2 = 0, y5 = 0, y7 = 0,
y10 = 0, y11 = 0. (5.9)
Для нахождения других значений переменных необходимо решить систему уравнений на основе (5.8), после исключения нулевых столбцов
$$\begin{pmatrix} 1 1 0 0 0 0 \\ 0 0 1 1 0 0 \\ 0 0 0 0 1 1 \\ 0 0 0 0 1 0 \\ 0 0 1 0 0 0 \\ 1 0 0 0 0 0 \end{pmatrix} \times \begin{pmatrix} y_3\\y_4\\y_6\\y_8\\y_9\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\ 11\\ 8\\ 5\\ 9\\ 9 \end{pmatrix}.$$
Найдем все строки матрицы A, содержащие
не более одного
единичного элемента. Это строки, определяющие компоненты решения y3
= 9, y6 = 9, y9 = 5.
Выполним подстановку, последовательно находя в столбцах
найденных переменных единицы (не более одной) и корректируя правые
части вычитанием найденных значений. Строки и столбцы, соответствующие
найденным значениям переменных, исключаем из матрицы A.
Такой прием подстановки можно повторять до исчерпания уравнений, содержащих в левой части единственную переменную.
В нашем примере после подстановки найденных значений в уравнения
1, 2 и 3 получаем систему$$\begin{pmatrix}
1 0 0\\
0 1 0\\
0 0 1
\end{pmatrix}
\times
\begin{pmatrix}
y_4\\y_8\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11-9\\
11-9\\
8-5
\end{pmatrix}$$
В ней все уравнения имеют единственную переменную.
Они определяют решение y4 = 2, y8 = 2, y12 =
3.
Таким образом, нам не пришлось пока воспользоваться методом
Гаусса, но мы нашли допустимое решение Y0 = (0, 0, 9, 2, 0, 9, 0, 2, 5,
0, 0,
3), для которого выполняются ограничения задачи.
Вектор Y0 определяет
некоторую вершину многогранника допустимых решений, со значением
целевой функции Z(Y0) = 141.
Примем следующий план решения, соответствующий рассмотренному ранее плану параллельного решения задач линейного программирования.
Для перебора всех смежных вершин необходимо в комбинации нулей,
определивших вершину Y0, поочередно исключать одно
значение yr =
0 (это определит одно из исходящих ребер) и оставшуюся систему решать
совместно поочередно со всеми другими уравнениями вида ys = 0, не
входящими в комбинацию нулей. Этим мы будем совершать перемещение в
смежные вершины. Находя значение Z для каждого такого
решения Y1 там, где оно существует, можно найти вершину с меньшим
значением
целевой функции. "Перебравшись" в эту вершину (приняв ее
за Y0 ), мы
можем продолжить анализ смежных ей вершин и т.д. Решение задачи
найдено в том случае, если после перебора всех смежных вершин не
отыскивается вершина с меньшим значением целевой функции.
Продолжим рассмотрение примера.
Итак, (5.8) — исходный вид системы уравнений, (5.9) —
комбинация
нулей ("отсутствующие" столбцы в (5.7) выделены), (5.8) и (5.9)
определяют вершину Y0.
Исключим из (5.9) уравнение y1 = 0, а оставшуюся систему, с
учетом остальных нулей из комбинации (5.9), будем решать совместно с
уравнениями
y3 = 0, y4 = 0, y6 = 0, y8 = 0, y9 = 0, y12 = 0. (5.10)
Значит, в (5.8) положим первоначально y3 = 0 вместо y1 =
0.
Левая часть шестого уравнения (последняя строка матрицы А) обратилась в
нуль.
Положим y4 = 0 вместо y1 = 0. Получим
систему$$\begin{pmatrix}
1 1 0 0 0 0\\
0 0 1 1 0 0\\
0 0 0 0 1 1\\
0 0 0 0 1 0\\
0 0 1 0 0 0\\
0 1 0 0 0 0\\
\end{pmatrix}
\times
\begin{pmatrix}
y_1\\y_3\\y_6\\y_8\\y_9\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}$$
Из нее, как и ранее, за два шага подстановки
находим y3 = 9, y6 =
9, y9 = 5, а затем — y1 = 2, y8 =
2, y12 = 3.
Таким образом, найдено новое допустимое решение Y1 = (2, 0, 9,
0, 0,
9, 0, 2, 5, 0, 0, 3). Однако Z(Y1) =149 > 141. Найденную
вершину
отвергаем. Вместе с тем, т.к. мы нашли вершину "на другом конце"
анализируемого ребра, то и анализ этого ребра прекращаем.
Приступаем к анализу следующего ребра, исключив из (5.9)
уравнение y2 = 0. Оставшуюся систему, с учетом остальных нулей из
(5.9), будем решать совместно с теми же уравнениями (5.10).
Положим в (5.8) y3 = 0 вместо y2 = 0. Последняя
строка
матрицы A стала нулевой.
Замена y4 = 0 вместо y2 = 0 приводит к
системе$$\begin{pmatrix}
1 1 0 0 0 0\\
0 0 0 0 1 1\\
0 0 0 0 1 1\\
0 0 0 0 1 0\\
0 0 1 0 0 0\\
0 1 0 0 0 0\\
\end{pmatrix}
\times
\begin{pmatrix}
y_2\\y_3\\y_6\\y_8\\y_9\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}$$
На ее основе находим новый вектор — допустимое
решение Y1 = (0,
2, 9, 0, 0, 9, 0, 2, 5, 0, 0, 3). Однако Z(Y1) = 151 >
141. Найденную
вершину также отвергаем. Ребро исследовано полностью.
Исключим из (5.9) уравнение y5 = 0, а оставшуюся систему, с
учетом остальных нулей из (5.9), будем решать совместно с теми же
уравнениями (5.10).
Положим в (5.8) y3 = 0 вместо y5 = 0. Последняя
строка
матрицы A обратится в нуль.
Положим y4 = 0 вместо y5 = 0. В первом уравнении не
выполняется ограничение по y3 (.
Положим y6 = 0 вместо y5 = 0. Пятая
строка A обратилась в
нулевую.
Положим y8 = 0 вместо y5 = 0. Получим систему
уравнений$$\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 0 0 1 0 \\
0 0 0 1 0 0 \\
1 0 0 0 0 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_3\\y_4\\y_5\\y_6\\y_9\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}$$
Находим y3 = 9, y6 = 9 и
после подстановки — y4 = 2, y5 =
2. Вновь выполняем подстановку, находим y9 = 3, и после
следующей
подстановки y12 = 5.
Итак, получена вершина Y1 = (0, 0, 9, 2, 2, 9, 0, 0, 3, 0, 0,
5). Т.к. Z(Y1) = 119 < 141, полагаем Y0 :=
Y1 и начинаем пробу возможных
перемещений вдоль ребер из найденной вершины многогранника решений в
вершину с меньшим значением целевой функции:$$\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 0 0 1 0 \\
0 0 0 1 0 0 \\
1 0 0 0 0 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_3\\y_4\\y_5\\y_6\\y_9\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}$$
Запишем вновь аналогично (5.8) и (5.9) систему
уравнений,
решением которой является вершина Y0, отметив в ней
"отсутствующие"
столбцы:$$\begin{equation}
\setcounter{MaxMatrixCols}{20}
\begin{pmatrix}
\colorbox[gray]{0.8}1 \colorbox[gray]{0.8}1 1 1 0 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 \\
\colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 0 1 1 \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}1 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 \\
\colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 0 0 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 1 \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}1 1 \\
\colorbox[gray]{0.8}1 \colorbox[gray]{0.8}0 0 0 1 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 1 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 \\
\colorbox[gray]{0.8}0 \colorbox[gray]{0.8}1 0 0 0 1 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}0 0 \\
\colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 1 0 0 0 \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}0 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}1 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_1\\y_2\\y_3\\y_4\\y_5\\y_6\\y_7\\y_8\\y_9\\y_{10}\\y_{11}\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}
\end{equation}$$
Находим
y1 = 0, y2 = 0, y7 = 0, y8 = 0, y10 = 0, y11 = 0. (5.12)
Начнем движение по ребрам из данной вершины. Для этого будем исключать из (5.12) одно из уравнений, а оставшуюся систему будем решать совместно с не вошедшими в (5.12) уравнениями:
y3 = 0, y4 = 0, y5 = 0, y6 = 0, y9 = 0, y12 = 0. (5.13)
При этом надо учесть, что могут формироваться ранее исследованные комбинации нулей. (Комбинации нулей удобно метить индексным кодом, который следует запоминать для исключения повторного анализа.)
Положим в (5.13) y3 = 0 вместо y1 = 0. Последняя
строка
матрицы A станет нулевой.
Замена y1 = 0 уравнением y4 = 0 приводит к
системе$$\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 0 0 1 0 \\
0 0 0 1 0 0 \\
1 0 0 0 0 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_1\\y_3\\y_5\\y_6\\y_9\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}$$
Решаем с помощью подстановок, находим Y1 =
(2, 0, 9, 0, 2, 9, 0, 0, 3,
0, 0, 5). Т.к. Z(Y1) = 127 > 119, найденную вершину
отвергаем.
Примечание. Нам вновь не пришлось воспользоваться схемой Гаусса. По-видимому, вид уравнений и вхождение каждой переменной не более чем в два уравнения позволяют довольствоваться простой подстановкой. Ниже мы исследуем это подробнее.
Переходим к другому ребру, заменяя в (5.12) уравнение y2 =
0 уравнениями из (5.13).
Замена y3 = 0 вместо y2 = 0 приводит к тому, что
последняя
строка матрицы A становится нулевой.
Замена y4 = 0 вместо y2 = 0 приводит к системе
уравнений$$\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 1 0 1 0 \\
1 0 0 1 0 0 \\
0 1 0 0 0 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_2\\y_3\\y_5\\y_6\\y_9\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}$$
Находим с помощью подстановок Y1 = (0, 2, 9,
0, 4, 7, 0, 0, 1, 0, 0, 7).
Т.к. Z(Y1) = 127 > 119, найденную вершину отвергаем и
переходим к
анализу следующего ребра.
Замена y3 = 0 вместо y7 = 0 приводит к тому, что в
первом
уравнении (9.25) не выполняется условие по ограничению y4 (.
Замена y4 = 0 вместо y7 = 0 приводит к тому, что в
первом же
уравнении (9.25) не выполняется условие по ограничению y3 (.
Замена y5 = 0 вместо y7 = 0 приводит к
системе$$\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 0 0 1 0 \\
0 0 1 0 0 0 \\
1 0 0 1 0 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_3\\y_4\\y_6\\y_7\\y_9\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}$$
Находим Y1 = (0, 0, 7, 4, 0, 9, 2, 0, 5, 0,
0, 3). Однако Z(Y1) = 129 > 119.
Переходим к анализу следующего ребра, поочередно заменяя
уравнениями из (5.13) уравнение y8 = 0 из (5.11).
Замена y3 = 0 вместо y8 = 0 приводит к образованию
последней
нулевой строки матрицы A.
Замена y4 = 0 вместо y8 = 0 приводит к тому, что в
первом
уравнении не выполняется условие по ограничению y3 (.
Замена y5 = 0 вместо y8 = 0 приводит к
системе$$\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 0 0 1 0 \\
0 0 1 0 0 0 \\
1 0 0 1 0 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_3\\y_4\\y_6\\y_8\\y_9\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}$$
Находим Y1 = (0, 0, 9, 2, 0, 9, 0, 2, 5, 0,
0, 3). Т.к. Z(Y1) = 141 > 119, найденную вершину
отвергаем.
Переходим к анализу следующего ребра, поочередно заменяя
уравнениями из (5.13) уравнение y10 = 0 из (5.11).
Замена y3 = 0 вместо y10 = 0 приводит к тому, что
в первом
уравнении (5.11) не выполняется условие по ограничению y4 (.
Замена y4 = 0 вместо y10 = 0 приводит к тому, в
первом же
уравнении (5.11) не выполняется условие по ограничению y3 (.
Замена y5 = 0 вместо y10 = 0 приводит к тому, что
во втором
уравнении (5.11) не выполняется условие по ограничению y6 (.
Замена y6 = 0 вместо y10 = 0 приводит к тому, что
во втором же
уравнении (5.11) не выполняется условие по ограничению y5 (.
Замена y9 = 0 вместо y10 = 0 приводит к
системе$$\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 1 0 1 0 \\
0 0 0 1 1 0 \\
1 0 0 0 0 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_3\\y_4\\y_5\\y_6\\y_{10}\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}$$
Находим Y1 = (0, 0, 9, 2, 5, 6, 0, 0, 0, 3,
0, 5). Т.к. Z(Y1) = 104 < 119,
"перемещаемся" в найденную вершину с меньшим значением
целевой функции.
Новая вершина характеризуется системой уравнений
y1 = 0, y2 = 0, y7 = 0, y8 = 0, y9 = 0, y11 = 0. (5.14)
Перепишем систему (5.11), выделив "отсутствующие" столбцы, вследствие (5.14):$$\begin{equation} \setcounter{MaxMatrixCols}{20} \begin{pmatrix} \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}1 1 1 0 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 \colorbox[gray]{0.8}0 0 \\ \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 0 1 1 \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}0 0 \colorbox[gray]{0.8}0 0 \\ \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 0 0 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}1 1 \colorbox[gray]{0.8}1 1 \\ \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}0 0 0 1 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}1 0 \colorbox[gray]{0.8}0 0 \\ \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}1 0 0 0 1 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 1 \colorbox[gray]{0.8}0 0 \\ \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 1 0 0 0 \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 \colorbox[gray]{0.8}1 0 \\ \end{pmatrix} \times \begin{pmatrix} y_1\\y_2\\y_3\\y_4\\y_5\\y_6\\y_7\\y_8\\y_9\\y_{10}\\y_{11}\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix} \end{equation}$$ После исключения одного из уравнений (5.14) оставшаяся система (5.15), (5.14) будет решаться совместно с одним из уравнений
y3 = 0, y4 = 0, y5 = 0, y6 = 0, y10 = 0, y12 = 0
(5.16)
Замена y1 = 0 на y3 = 0 приводит к появлению
(последней)
нулевой строки матрицы A.
Замена y4 = 0 вместо y1 = 0 приводит к
системе
$$\begin{equation*} \begin{pmatrix} 1 1 0 0 0 0 \\ 0 0 1 1 0 0 \\ 0 0 0 0 1 1 \\ 1 0 1 0 1 0 \\ 0 0 0 1 1 0 \\ 0 1 0 0 0 0 \\ \end{pmatrix} \times \begin{pmatrix} y_1\\y_3\\y_5\\y_6\\y_{10}\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix} \end{equation*}$$
Отсюда Y1 = (2, 0, 9, 0, 3, 8, 0, 0, 0, 1, 0,
7). Т.к. Z(Y1) = 114 > 104,
исследуем следующее ребро, исключив в системе (5.14) уравнение y2 =
0 и заменяя его последовательно уравнениями из (5.16).
Замена y4 = 0 вместо y2 = 0 приводит к
системе$$\begin{equation}
\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 1 0 1 0 \\
1 0 0 1 1 0 \\
0 2 0 0 0 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_2\\y_3\\y_5\\y_6\\y_{10}\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}
\end{equation}$$
Находим Y1 = (0, 2, 9, 0, 5, 6, 0, 0, 0, 1,
0, 7). Т.к. Z(Y1) = 114 > 104, исследуем следующее
ребро, исключив в системе (5.14) уравнение y7 = 0 и заменяя его
последовательно уравнениями из (5.16).
Замена y3 = 0 вместо y7 = 0 приводит к тому, что в
первом
уравнении (9.29) не выполняется условие по ограничению y4 (.
Замена y4 = 0 вместо y7 = 0 приводит к тому, что в
первом же
уравнении (9.29) не выполняется условие по ограничению y3 (.
Замена y5 = 0 вместо y7 = 0 приводит к формированию
нулевой
(четвертой) строки матрицы A.
Замена y6 = 0 вместо y7 = 0 приводит к формированию
нулевой
(пятой) строки матрицы A.
Замена y10 = 0 вместо y7 = 0 приводит к тому, что
в третьем
уравнении (5.15) не выполняется условие по ограничению y12
(.
Замена y12 = 0 вместо y7 = 0 приводит к
системе$$\begin{equation}
\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 1 0 \\
0 0 0 0 0 1 \\
0 0 1 0 0 0 \\
0 0 0 1 0 1 \\
1 0 0 0 1 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_3\\y_4\\y_5\\y_6\\y_{10}\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}
\end{equation}$$
Находим Y1 = (0, 0, 4, 7, 5, 1, 5, 0, 0, 8,
0, 0). Т.к. Z(Y1) = 104 и это
не меньше уже полученной оценки, исследуем следующее ребро, исключив в
системе (5.14) уравнение y8 = 0 и заменяя его последовательно
уравнениями из (5.16).
Замена y3 = 0 вместо y8 = 0 приводит к образованию
нулевой
(шестой) строки матрицы A.
Замена y4 = 0 вместо y8 = 0 приводит к тому, что в
первом
уравнении (5.15) не выполняется условие по ограничению y3 (.
Замена y5 = 0 вместо y8 = 0 приводит к образованию
нулевой
(четвертой) строки матрицы A.
Замена y6 = 0 вместо y8 = 0 приводит к тому, что в
пятом
уравнении (5.15) не выполняется условие по ограничению y10 (.
Замена y10 = 0 вместо y8 = 0 приводит к тому,
что в третьем
уравнении (5.15) не выполняется условие по ограничению y12 (.
Замена y12 = 0 вместо y8 = 0 приводит к
системе$$\begin{equation}
\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 1 0 0 0 \\
0 0 0 1 0 1 \\
1 0 0 0 0 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_3\\y_4\\y_5\\y_6\\y_{8}\\y_{10}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}
\end{equation}$$
Ее решение Y1 = (0, 0, 9, 2, 5, 1, 0, 5, 0,
8, 0, 0) определяет значение Z(Y1) = 134 > 104.
Продолжаем перебор по следующему ребру.
Замена y3 = 0 вместо y9 = 0 приводит к образованию
нулевой
(шестой) строки матрицы A.
Замена y4 = 0 вместо y9 = 0 приводит к тому, что в
первом
уравнении (5.15) не выполняется условие по ограничению y3 (.
Замена y5 = 0 вместо y9 = 0 приводит к тому, что во
втором
уравнении (5.15) не выполняется условие по ограничению y6 (.
Замена y6 = 0 вместо y9 = 0 приводит к тому, что во
втором же
уравнении (5.15) не выполняется условие по ограничению y5 (.
Замена y10 = 0 вместо y9 = 0 приводит к
системе
$$\begin{equation} \begin{pmatrix} 1 1 0 0 0 0 \\ 0 0 1 1 0 0 \\ 0 0 0 0 1 1 \\ 0 0 1 0 1 0 \\ 0 0 0 1 0 0 \\ 1 0 0 0 0 0 \\ \end{pmatrix} \times \begin{pmatrix} y_3\\y_4\\y_5\\y_6\\y_{9}\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix} \end{equation}$$
Ее решение Y1 = (0, 0, 9, 2, 2, 9, 0, 0, 3,
0, 0, 5) определяет значение Z(Y1) = 119 > 104.
Приступаем к анализу следующего ребра, исключая в (5.14)
уравнение y11 = 0 и заменяя его последовательно уравнениями из
(5.16).
Замена y3 = 0 вместо y11 = 0 приводит к тому, что
в первом
уравнении (5.15) не выполняется условие по ограничению y4 (.
Замена y4 = 0 вместо y11 = 0 приводит к тому, что
в первом
уравнении (5.15) не выполняется условие по ограничению y3 (.
Замена y5 = 0 вместо y11 = 0 приводит к тому, что
во втором
уравнении (5.15) не выполняется условие по ограничению y6 (.
Замена y6 = 0 вместо y11 = 0 приводит к тому, что
во втором же
уравнении (5.15) не выполняется условие по ограничению y5 (.
Замена y10 = 0 вместо y11 = 0 приводит к системе
$$\begin{equation} \begin{pmatrix} 1 1 0 0 0 0 \\ 0 0 1 1 0 0 \\ 0 0 0 0 1 1 \\ 0 0 1 0 1 0 \\ 0 0 0 1 0 0 \\ 1 0 0 0 1 0 \\ \end{pmatrix} \times \begin{pmatrix} y_3\\y_4\\y_5\\y_6\\y_{11}\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix} \end{equation}$$
Система не имеет решения, т.к. ранг матрицы системы не равен рангу
Примечание. В несложном
примере это легко обнаружить: вторая
строка матрицы равна сумме четвертой и пятой строк, что противоречит
соотношению между соответствующими свободными членами, $$9 + 5 \ne 11$$. По-видимому, это говорит в пользу применения схемы Гаусса. В
противном случае мы должны контролировать последовательно получаемые
решения на удовлетворение тем соотношениям, которые в его получении не
участвовали. Так, из четвертого и пятого уравнений имеем y5 =
5, y6 =
9. Но в соответствии со вторым уравнением y5 + y6 = 11. В
то же время,
совершая подстановку во второе уравнение, мы получаем нулевую левую
часть, т.е. нулевую строку матрицы A, что опять говорит в пользу
подстановок!
Замена y12 = 0 вместо y11 = 0 приводит к
системе$$\begin{equation}
\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 1 0 1 0 \\
0 0 0 1 1 0 \\
1 0 0 0 0 1 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_3\\y_4\\y_5\\y_6\\y_{10}\\y_{11}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}
\end{equation}$$
Ее решение Y1 = (0, 0, 4, 7, 5, 6, 0, 0, 0,
3, 5, 0) определяет значение
целевой функции Z(Y1) = 89 < 104.
Полагаем Y0 := Y1. Теперь мы должны перемещаться по ребрам из
вновь найденной вершины в поисках вершины с еще меньшим значением
целевой функции. Придется перебрать до 6 x 6 = 36 вариантов
такого
перемещения. Однако, достигнув ответа задачи в [15], положимся на его
правильность и прекратим рассмотрение примера.
Остался неясным вопрос: приходится ли в общем случае при решении систем линейных уравнений для данной задачи пользоваться схемой Гаусса, или достаточно последовательно пользоваться простыми подстановками?
Подстановки мы легко выполняли в том случае, если в результате введения нулевых комбинаций у нас получались уравнения, содержащие в левой части единственную переменную. Если таких уравнений нет, то очевидна целесообразность применения схемы Гаусса.
Тогда выясним, существует ли комбинация нулей, такая, при которой в
каждой строке A, с учетом неисключенной строки, остается не менее
двух
единиц.
Рассмотрим только n = 4 последних уравнений из (5.6): три
последних уравнения из (5.7) и уравнение y4 + y8 + y12 = 7.
Их
матрица имеет вид$$\begin{array}{|c|c |c |c |c |c |c |c |c |c |c |c|}
\hline
\colorbox[gray]{0.8}1 1 1 \\
\hline
1 \colorbox[gray]{0.8}1 1 \\
\hline
1 1 \colorbox[gray]{0.8}1 \\
\hline
\colorbox[gray]{0.8}1 1 1 \\
\hline
\end{array}$$
Т.е. она состоит из m матриц с единицами по
главной диагонали.
Чтобы в одной строке такой матрицы остались хотя бы две единицы,
необходимо оставить невычеркнутыми хотя бы два столбца. В другой строке
должны быть не вычеркнуты хотя бы два обязательно других столбца. Итого,
для четырех строк примера должны остаться невычеркнутыми восемь
различных столбцов. Значит, вычеркнуть мы можем только четыре столбца
(например, как выделено на изображении матрицы), а нам надо положить
равными нулю шесть переменных! Тем самым, на базе лишь этих "нижних"
уравнений образуются не менее двух уравнений с единственной переменной
в левой части.
Т.к. произведение m x n растет значительно быстрее
суммы m +
n, то с ростом параметров задачи указанное свойство усугубляется.
Следовательно, мы с полным основанием может рассчитывать на принцип
подстановки, как мы и делали в примере.
Однако программирование схемы Гаусса может оказаться не только менее трудоемко. Не следует забывать, что в процессе преобразования системы уравнений и последовательного получения значений переменных оперативно устанавливается как неразрешимость или неоднозначность, так и отрицательное решение.
Например, система (5.17) при реализации схемы Гаусса проходит следующие стадии преобразования.
Вычитание первой строки из последней и формирование разности на месте второй строки:$$\begin{equation} \begin{pmatrix} 1 1 0 0 0 0 \\ 0 -1 0 0 2 0 \\ 0 0 1 1 0 0 \\ 0 0 0 0 1 1 \\ 0 0 1 0 0 0 \\ 0 0 0 1 0 0 \\ \end{pmatrix} \times \begin{pmatrix} y_3\\y_4\\y_5\\y_6\\y_{11}\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\-2\\11\\8\\5\\9 \end{pmatrix} \end{equation}$$
Получение нулевой строки в матрице достаточно для заключения о непригодности решения (в данном случае оно не существует).
Рассмотренная транспортная задача, без ограничения пропускной способности транспортных потоков, демонстрирует параллельный алгоритм ее решения. Программа, одинаковая для всех процессоров многопроцессорной ВС или станций локальной вычислительной сети, в основной своей части реализует выборку очередного ребра, исходящего из первоначально найденной вершины многогранника решений. Вдоль него ищется смежная вершина с меньшим значением целевой функции. Процессор, нашедший такую вершину, производит замену ранее исследовавшейся вершины и вынуждает все процессоры приступить к анализу ребер, исходящих из новой вершины. Так — до неудачного поиска вершины с меньшим значением целевой функции.
Использование в качестве источника загрузки процессоров общей уточняемой базы данных, в которой хранятся исследованные варианты поиска, позволяет выявлять еще не исследованные варианты и равномерно распределять нагрузку между процессорами.
Пусть dij — пропускная способность коммуникации (i,
j), что
порождает ограничение
xij <= dij
(5.18)
для всех i, j.
Тогда важная в практическом отношении задача заключается в
минимизации (5.1) — целевой функции Z при ограничениях (5.2),
(5.3),
(5.4) и (5.18).
Очевидно, что для разрешимости T -задачи должны выполняться
условия$$\sum\limits_{j = 1}^n {d_{ij} \geqslant a_i ,\quad i = 1,...,m,}$$
$$\sum\limits_{i = 1}^m {d_{ij} \geqslant b_j ,\quad j = 1,...,n}.$$
Как видим, данную задачу тоже можно решать прямым перебором
вершин R с учетом резко увеличившегося числа уравнений его границ: их
число, с учетом линейной зависимости, составляет теперь n+m-1+2(mx
n). С учетом границ на основе условий неотрицательности решения, общее
число испытываемых систем линейных уравнений составит C2(m x
n)m x n - (m + n - 1).
Однако при этом переборе мы будем исследовать явно несовместимые
варианты компоновки систем — а именно, варианты, включающие пары
уравнений вида xij=0 и xij=dij. Тогда поступим
иначе.
Сначала будем выбирать комбинации переменных, участвующих в
формировании указанных систем линейных уравнений. Всех таких
комбинаций будет Cm x
nm x n - (m + n - 1). После
выбора очередной комбинации переменных определим комбинацию их
значений — 0 или значение пропускной способности. Таких комбинаций для
выбранного набора m x n - (m + n) - 1 переменных
будет 2m x n - (m + n - 1) .
Таким образом, общее число испытываемых систем линейных
уравнений составит Cm x
nm x n - (m + n - 1) x
2m x n - (m + n - 1) .
Воспользуемся и здесь параллельным аналогом симплекс-метода, найдя первоначально некоторую вершину многогранника решений, а затем пытаясь "переместиться" в смежную вершину с меньшим значением целевой функции.
Сделаем важное замечание.
Будем считать, что если вдоль прямой,
отрезком которой является исходящее из вершины L ребро, найдена
смежная вершина M, то на этой же прямой, "в другую
сторону" от L,
нет смежных вершин. Т.е. одна прямая может связывать не более двух
вершин многогранника решений. Предположим, что три вершины M, L,
N лежат на одной прямой. Т.к. L — вершина, то существует
хотя бы еще
одно исходящее из нее ребро. Пусть оно соединяет L с
вершиной K.
Тогда построим плоскость, проходящую через три точки M, N, K, т.е.
через
точку K и прямую MN, которой принадлежит
точка L. Плоскость
поглотила как точку L, так и новое ребро, существование которого мы
предположили.
Это означает, что если мы нашли смежную вершину "с одной стороны" по прямой, отрезком которой является исходящее ребро, то искать смежную вершину "с другой стороны" по этой же прямой не следует.
Этим предположением мы пользовались в предыдущем разделе,
прекращая дальнейший поиск других смежных вершин вдоль прямой в
случае, если одна такая вершина оказывается найденной. Здесь же это
замечание, в частности, означает, что если мы нашли смежную данной
вершину со значением xij = 0 ( xij = dk ), то
испытывать значение xij = dk ( xij = 0 ) не
следует. Т.е., как и ранее, мы вдоль каждого
исходящего ребра будем искать единственную смежную
вершину.
Введем, как и ранее, линейное множество переменных и сформулируем задачу:
Z = 2y1 + 3y2 + 3y3 + 2y4 + 2y5 + y6 ->
min
при ограничениях
y1 + y2 + y3 = 12
y4 + y5 + y6 =10 (5.21)
y1+ y4 =7
y2 + y5 =7
y3 + y6 = 8
и при условии
0 <= y1 <= 4, 0 <= y2 <= 4, 0 <= y3 <= 5, 0 <= y4 <= 4, 0 <= y5
<= 4,
0 <= y6 <= 3. (5.22)
Сформируем ограничения каждой переменной:
y1 + y2 + y3 = 12
y4 + y5 + y6 = 10 (5.23)
y1 + y4 = 7
y2 + y5 = 7
y1 = 0; y1 = 4
y2 = 0; y2 = 4
y3= 0; y3 = 5 (5.24)
y4 = 0; y4 = 4
y5 = 0; y5 = 4
y6 = 0; y6 = 3
Начнем перебор систем по шесть граней в поисках координат одной из вершин многогранника решений. В каждой такой системе должны присутствовать все уравнения (5.23) и два уравнения с разными переменными из (5.24).
Для формирования первой системы уравнений пробуем добавить к
(5.23) уравнение y1 = 0. В результате в третьем уравнении не
выполняется ограничение по y4 (.
Пробуем вариант y1 = 4. Совершив подстановку, убеждаемся, что
он не приводит к подобному противоречию.
Полагаем y2 = 0. В первом уравнении не выполняется ограничение
по y3 (.
Полагаем y2 = 4. Получаем и решаем систему
уравнений
y1 + y2 + y3 = 12
y4 + y5 + y6 = 10
y1 + y4 = 7
y2 + y5 = 7
y1= 4
y2 = 4.
Находим Y = (4, 4, 4, 3, 3, 4). Однако
данная точка не является
вершиной многогранника решений, т.к. y6 = 4 противоречит условию
(5.22).
Испытываем уравнение y3 = 0. В первом уравнении нарушается
ограничение по y1 + y2 (.
Испытываем уравнение y3 = 5. Решаем систему
уравнений
y1 + y2 + y3 = 12
y4 + y5 + y6 = 10
y1 + y4 = 7
y2 + y5 = 7
y1 = 4
y3 = 5.
Находим Y0 = (4, 3, 5, 3, 4, 3).
Решение удовлетворяет условиям
задачи, следовательно, найденная точка — вершина многогранника решений.
Находим значение целевой функции Z(Y0) = 49.
На основе (5.23) и (5.24) выпишем уравнения всех граней, которым
удовлетворяет вершина Y0, т.е. все грани, образующие эту вершину:
y1 + y2 + y3 = 12
y4 + y5 + y6 = 10 (5.25)
y1 + y4 = 7
y2 + y5 = 7
y1 = 4
y3 = 5
y5 = 4
y6 = 3.
Выбирая из (5.25) комбинации по пять уравнений (в каждую
комбинацию обязательно входят все уравнения (5.23)), мы формируем
прямые, которым принадлежат ребра (принадлежащие или не
принадлежащие многограннику допустимых решений), исходящие из
вершины Y0. Решая совместно поочередно с другими гранями из
(5.24)
y1 = 0, y2 = 0, y2 = 4, y3 = 0, y4 = 0, y4 = 4, y5 = 0,
y6 = 0,(5.26)
производим поиск смежной вершины. Нам необходима вершина с меньшим
значением целевой функции Z.
Первая комбинация пяти уравнений составляет
y1 + y2 + y3 = 12
y4 + y5 + y6 = 10 (5.27)
y1 + y4 = 7
y2 + y5 = 7
y1 = 4.
Решая последовательно с уравнениями из (5.26), находим первый
непротиворечивый вариант для y2 = 4. Находим точку Y1 =
(4, 4, 4, 3, 3,4), которая ранее исследовалась и не является вершиной многогранника
решений.
Использование значений y3 = 0 и y4 = 0 приводит к
невыполнению ограничений.
Значение y4 = 4 приводит к противоречию в третьем
уравнении, $$4+ 4 \ne 7$$.
Значения y5 = 0 и y6 = 0 также приводят к
невыполнению
ограничений.
Таким образом, исследованное предполагаемое ребро не принадлежит многограннику решений.
Следующая комбинация пяти уравнений на основе (5.25) составляет
y1 + y2 + y3= 12
y4 + y5 + y6 = 10 (5.28)
y1 + y4 = 7
y2 + y5 = 7
y3 = 5.
Решая последовательно с уравнениями (значениями) из (5.26),
получаем для y2 = 4 точку Y1 = (3, 4, 5, 4, 3, 3).
Т.к. все ограничения
выполняются, Y1 — вершина многогранника решений.
Однако Z(Y1) =
50 > 49, — переходим к исследованию следующего ребра.
Оно определяется системой уравнений
y1 + y2 + y3 = 12
y4 + y5 + y6 = 10 (5.29)
y1 + y4 = 7
y2 + y5 = 7
y5 = 4.
Данная система решается последовательно с уравнениями из (5.26).
Только при значении y4 = 4 получаем не противоречивую систему и
находим точку Y = (3, 3, 6, 4, 4, 2), которая не является вершиной
многогранника решений, т.к. не выполняется условие y3 <= 5. Т.е.
исследованное предполагаемое ребро не принадлежит многограннику
решений.
Последнее предполагаемое ребро определяется системой уравнений
y1 + y2 + y3 = 12
y4 + y5 + y6 = 10
y1 + y4 = 7
y2 + y5 = 7
y6 = 3.
Она решается последовательно с уравнениями из (5.26).
При y2 = 4 получаем непротиворечивую систему и
находим Y1 =
(3, 4, 5, 4, 3, 3), которая является смежной вершиной, т.к. удовлетворяет
всем ограничениям и условиям. Однако Z(Y1) = 50 > 49.
Т.к. все ребра, исходящие из Y0, исследованы, и вершина с
меньшим
значением целевой функции не найдена, вершина Y0 определяет
окончательное решение задачи.
В рассмотренном примере ограничения пропускной способности столь существенны, что не допустили "нулевых" перевозок по одним магистралям во избежание перегрузки других магистралей. Это характерно для исследования фрагмента транспортной сети, когда выделяются допустимые загрузки магистралей. В целом, ограничения могут быть менее жестки либо практически отсутствовать.
Предлагаемый алгоритм, как и ранее, обеспечивает параллельную
структуру программы, воспроизводящую
Исследование потоков в сети — важная, всегда актуальная задача
исследования операций. Она лежит в основе моделирования при
проектировании как транспортных сетей, так и сетей водоснабжения и
канализации. Известен ряд классических моделей (приводимых, например, в
[15]) в этой области. Важнейшую роль играют модели, позволяющие
определить "узкие" мести сети. Они определяют ее максимальную
пропускную способность между выделенными пунктами, или, иначе говоря,
ее минимальное сечение. Это задача
При аналитическом моделировании сети используется известный [15] алгоритм Форда-Фалкерсона.
Теория параллельного программирования способна предложить более
простой алгоритм перебора. Его достоинством является параллелизм,
который позволяет эффективно использовать многопроцессорные ВС и
вычислительные комплексы на основе рабочих станций локальной сети.
Возможен наиболее простой способ распараллеливания на основе
применения
Пусть задана сеть (рис. 5.1). Дуги ее назовем каналами. Каналы
пронумерованы. Направление потоков показано стрелками. Вершины —
точки сопряжения каналов, вершина A — исток,
вершина B — сток.
Каждая дуга i сопровождается информацией об интересующих нас
характеристиках потока, например, о пропускной
способности di канала. В
этом случае правомерен вопрос о максимальной пропускной способности
сети, обусловленной минимальным сечением.
(рис 5.1) Сеть для оценки пропускной способности
В терминах теории параллельного программирования (лекция 7)
каждое сечение сети (например, сечение, пересекающее каналы 1, 2, 4, 7)
является
В [3] приводится алгоритм перебора всех полных множеств взаимно независимых работ. Усовершенствуем его, получая такие множества, упорядоченные по номерам каналов, и исключая повторное нахождение одних и тех же полных множеств. (В лекции 7 изложенные ниже преобразования будут рассмотрены глубже.)
Построим треугольную матрицу следования S, отражающую граф
сети (рис. 5.2а). Сложив каждую последующую строку с теми
предыдущими, которые соответствуют единичным элементам этой строки,
получим матрицу следования S с S и объединим с ее начальным видом
(рис. 5.2в).
Иначе, отобразим S симметрично относительно главной диагонали.
Получим матрицу S, отображающую как порядок следования, так и
порядок предшествования каналов.
(рис 5.2) Полная матрица следования каналов:а — начальный вид, б — дополнение транзитивными связями, в — конечный вид
Теперь матрица S полностью отражает взаимную независимость
каналов. Например, если сложить логически строки 1, 2, 3, то получим
строку, содержащую нули только в позициях 1, 2, 3. Тем самым мы получим
ПМВНК {1, 2, 3}. Множество полное, т.к. дополнительное сложение с любой
другой строкой изменит состав нулей.
Таким образом, наша задача заключается в том, чтобы испытать все варианты сложения групп строк так, чтобы нули в строке-результате оказывались в тех и только в тех позициях, которые соответствуют строкам- слагаемым. Тогда эти строки определят очередное ПМВНК. Упорядочение по номерам строк поможет нам избежать повторного получения ПМВНК с другим порядком следования номеров каналов.
Пусть стек составляют нуль-единичные строки длины n (число
каналов сети). Для каждой строки известно упорядоченное по номерам
множество M каналов, логическая сумма строк которых в
матрице S определила данную строку. Номер k последнего
канала в этом множестве
известно. Для каждой строки известен последний испытанный нулевой
элемент.
i -ю, i = 1, ... ,n-1, строку в
стек. Полагаем M ={i}, k = i.j > i. Переходим к выполнению шага 4.j —
формируем новую вершину стека. Номером канала j дополняем
множество каналов M, участвующих в формировании новой
строки. Полагаем k = j.M, то M — очередное найденное ПМВНК. Фиксируем это
множество. В
любом случае исключаем строку-вершину стека из стека. Выполняем шаг 2.Продолжим исследование приведенной выше сети.
Заносим в стек первую строку матрицы S. Находим первый нуль
после обязательного нуля в первой позиции. Этот нуль указывает, что каналы
1 и 2 s1 в вершине
стека$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Она содержит нули правее позиции 2. Это говорит о том,
что 1 и 2 не
исчерпывают ПМВНК.
Находим первый нуль правее позиции 2 — нуль в позиции 3.
Складываем логически s2 = s1 $$\vee$$ "3". Получаем новую строку в
вершине стека и весь стек в
виде$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_2 1 1 1 1 1 1 1 \\
\cline{2-11}
s_1 1 1 1 1 \\
\cline{2-11}
"1" 1 1 \\
\cline{2-11}
\end{array}$$
Строка в вершине стека содержит нули только в тех
позициях, которые
соответствуют образующим ее каналам 1, 2, 3. Это означает, что мы нашли
ПМВНК {1, 2, 3}, т.е. некоторый разрез сети. Минимальный поток,
проходящий через него, составляет d1 + d2 + d3.
Исключаем из стека строку s2 и в
строке s1 испытываем
следующий нуль правее позиции 2. Это нуль в позиции 4. Формируем новую
вершину стека s3 = s1 $$\vee$$ "4".$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_3 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка s3 содержит нули не только в
позициях 1, 2, 4. Первый такой
нуль правее позиции 4 — в позиции 7.
Формируем новую вершину стека s4 = s3 $$\vee $$ "7". Стек принимает
вид$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_4 1 1 1 1 1 1 \\
\cline{2-11}
s_3 1 1 1 1 1 \\
\cline{2-11}
s_1 1 1 1 1 \\
\cline{2-11}
"1" 1 1 \\
\cline{2-11}
\end{array}$$
Строка s4 содержит нули только в позициях,
соответствующих
каналам, "участвующим" в ее формировании. Значит, найдено еще одно
ПМВНК {1, 2, 4, 7}. Оно определяет разрез сети с пропускной
способностью d1 + d2 + d4 + d7.
Исключаем s4 из стека. Следующий испытываемый нуль в
строке s3 занимает позицию 8. Формируем новую вершину
стека s5 = s3 $$\vee $$ "8".$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_5 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка s5 содержит нули только в позициях
1, 2, 4, 8.
Следовательно, найдено ПМВНК {1, 2, 4, 8} с пропускной
способностью d1 + d2 + d4 + d8.
Исключаем s5 из стека. Находим, что в s3 все нули
исследованы. Исключаем s3 из стека. В s1 следующий
нуль,
подлежащий испытанию, занимает позицию 7. Формируем новую вершину
стека — строку s6 = s1 $$\vee $$ "7".$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_6 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка s6 не содержит нулей правее позиции
7. Исключаем s6 из
стека.
Следующий испытываемый нуль в s1 занимает позицию 8.
Находим s7 = s1 $$\vee $$ "8"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_7 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка также не содержит нулей правее позиции 8.
Исключаем ее из
стека.
Все нули строки s1 испытаны. Исключаем s1 из стека.
В стеке
остается лишь строка "1".
Следующий испытываемый нуль в строке "1" занимает позицию 3.
Формируем новую вершину стека — строку s8 = "1" $$\vee $$ "3"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_8 1 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка s8 не содержит нулей правее позиции
3. Исключаем ее из
стека.
Следующий нуль в первой строке занимает позицию 4. Формируем
новую вершину стека — строку s9 = "1" $$\vee $$ "4"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_9 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка содержит нули не только в позициях 1 и 4.
Первый же
"дополнительный" нуль занимает позицию 2. Это говорит о повторном
формировании уже сформированных ПМВНК. Исключаем строку из стека.
Следующий испытываемый нуль первой строки занимает позицию 6.
Формируем s10 = "1" $$\vee $$ "6"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{10} 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка не содержит "дополнительных" нулей
до позиции 6. Первый
испытываемый нуль занимает позицию 7. Формируем новую вершину
стека s11 = s10 $$\vee $$ "7", а стек принимает
вид$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{11} 1 1 1 1 1 1 1 \\
\cline{2-11}
s_{10} 1 1 1 1 1 1 \\
\cline{2-11}
"1" 1 1 \\
\cline{2-11}
\end{array}$$
Строка s11 содержит нули только в
позициях каналов,
участвующих в ее формировании. Найдено очередное ПМВНК {1, 6, 7} с
потоком d1 + d6 +d7.
Исключаем s11 из стека. Следующий испытываемый нуль
в s10 занимает позицию 8. Формируем s12 = s10 $$\vee $$ "8".$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{12} 1 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка определяет очередное ПМВНК {1, 6,
8} с потоком d1 +
d6 +d8.
Исключаем s12 из стека. Строка s10 испытана
полностью.
Исключаем ее из стека. Следующий испытываемый нуль в строке "1"
занимает позицию 7. Формируем строку s13 = "1" $$\vee $$ "7"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{13} 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Она не содержит "дополнительные" нули
правее позиции 7.
Исключаем строку из стека.
Испытание нуля в позиции 8 первой строки приводит к тому же результату.
Все комбинации каналов с участием канала 1 исчерпаны. Выбираем
следующий канал. Т.е. загружаем в стек вторую строку матрицы S.
Первый
нуль в позиции, не меньшей 2, занимает позицию 3. Формируем новую
вершину стека s14 = "2" $$\vee $$ "3"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{14} 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Первый нуль правее позиции 3 в
строке s14 занимает позицию
5. Формируем s15 = s14 $$\vee $$ "5"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{15} 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка содержит нули только в позициях 2, 3, 5. Это
определяет
ПМВНК {2, 3, 5} с потоком d2 + d3 + d5.
Следующий нуль в строке s14 занимает позицию 9.
Формируем s16 = s14 $$\vee $$ "9"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{16} 1 1 1 1 1 1 1
\\
\cline{2-11}
\end{array}$$
Строка содержит нули только в позициях 2, 3, 9. Это
определяет
ПМВНК {2, 3, 9} с потоком d2 + d3 + d9.
Формируем s17 = "2" $$\vee $$ "4"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{17} 1 1 1 \\
\cline{2-11}
\end{array}$$
Первый "дополнительный" нуль занимает
позицию 5. Формируем s18 = s17 $$\vee $$ "5"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{18} 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка s18 содержит нули не только в
позициях 2, 4, 5. Первый
"дополнительный" нуль занимает позицию 7. Формируем s19 =
s18
$$\vee $$ "7" = "2" $$\vee $$ "4" $$\vee $$ "5" $$\vee $$ "7"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{19} 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка содержит нули только в позициях 2, 4, 5, 7, что
определяет
ПМВНК {2, 4, 5, 7} с потоком d2 + d4 + d5 +
d7.
Следующий (последний) "дополнительный" нуль
строки s18 занимает позицию 8. Формируем s20 = s18
$$\vee $$ "8"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{20} 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
и находим ПМВНК {2, 4, 5, 8} с
потоком d2 + d4 + d5 + d8.
Следующий нуль в строке s17 занимает позицию 7.
Формируем s21 = s17 $$\vee $$ "7"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{21} 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Единственный нуль правее позиции 7 занимает позицию 9.
Формируем s22 = s21 $$\vee $$ "9"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{22} 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
и получаем следующее ПМВНК {2, 4, 7, 9} с
потоком d2 + d4 + d7 +
d9.
Следующий нуль в строке s17 занимает позицию 8.
Формируем s23 = s17 $$\vee $$ "8"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{23} 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Единственный "дополнительный" нуль, правее
позиции 8, занимает
позицию 9. Формируем s24 = s23 $$\vee $$ "9"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{24} 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Т.к. позиции нулей совпадают с позициями всех каналов,
участвующих
в комбинации, получаем ПМВНК {2, 4, 8, 9}, определяющее разрез с
потоком d2 + d4 + d8 + d9.
Последний "дополнительный" нуль
в s17 занимает позицию
9. Формируем s25 = s17 $$\vee $$ "9"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{25} 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка содержит нули не только в позициях 2, 4, 9.
Однако все
"дополнительные" нули занимают позиции левее позиции 9. Это говорит
о повторном нахождении ПМВНК.
Возвращаемся к анализу второй строки матрицы S. Следующий
нуль этой строки занимает позицию 5. Формируем s26 = "2" $$\vee $$ "5"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{26} 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Первый "дополнительный" нуль правее
позиции 5 занимает
позицию 7. Формируем s27 = s26 $$\vee $$ "7"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{27} 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Наличие "дополнительных" нулей только
левее позиции 7 говорит о
повторном нахождении ПМВНК.
Второй, последний, "дополнительный" нуль в
строке s26,
правее позиции 5, занимает позицию 8. Его анализ также приводит к
повторному нахождению ПМВНК.
Следующий нуль второй строки матрицы S занимает позицию 7.
Формируем s28 = "2" $$\vee $$ "7"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{28} 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Первый "дополнительный" нуль в этой
строке, правее позиции 7,
занимает позицию 9. Формируем s29 = s28 $$\vee $$ "9"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{29} 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка не содержит нули правее позиции 9, но содержит
нули левее
этой позиции. Это значит, что мы на пути повторного формирования уже
найденного ПМВНК ( {2, 4, 7, 9} ).
Следующий нуль второй строки S занимает позицию 8.
Формируем s30 = "2" $$\vee $$ "8"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{30} 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Нуль в позиции 9 — правее позиции 8. Однако ситуация
аналогична
рассмотренной на шаге 23.
Вторая строка исчерпана. Переходим к анализу третьей строки
матрицы S. Правее третьей позиции в этой строке есть нуль в
позиции 5.
Формируем s31 = "3" $$\vee $$ "5"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{31} 1 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка не содержит "дополнительных" нулей
правее позиции 5,
хотя содержит нули не только в позициях 3 и 5. Значит, мы не получим
новых ПМВНК.
Следующий (последний) нуль в третьей строке занимает позицию 9.
Формируем s32 = "3" $$\vee $$ "9"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{32} 1 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Исключаем строку из стека, т.к. она имеет нули только
левее позиции
9.
Анализируем четвертую строку и убеждаемся, что новых ПМВНК мы не получим.
Анализируем пятую строку, Она содержит нули правее пятой
позиции - в позициях 6, 7, 8, 10. Формируем s33 = "5" $$\vee $$ "6"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{33} 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Первый "дополнительный" нуль, правее
позиции 6,
занимает позицию 7. Формируем s34 = s33 $$\vee $$ "7"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{34} 1 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка содержит нули только в позициях 5, 6, 7. Найдено
ПМВНК {5, 6, 7} с потоком d5 + d6 + d7.
Следующий нуль — в позиции 8. Формируем s35 =
s33 $$\vee $$ "8"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{35} 1 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка содержит нули только в позициях 5, 6, 8, что
соответствует
ПМВНК {5, 6, 8} с потоком d5 + d6 + d8.
Анализ позиций 7 и 8 пятой строки приводит к повторному нахождению ПМВНК.
Последний "дополнительный" нуль пятой строки занимает
позицию 10. Формируем s36 = "5" $$\vee $$ "10"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{36} 1 1 1 1 1 1 1 1
\\
\cline{2-11}
\end{array}$$
Строка содержит нули в позициях 5 и 10. Найдено
очередное ПМВНК {5, 10} с потоком d5 + d10.
Переходим к анализу шестой строки матрицы S. Она содержит
нули правее шестой позиции в позициях 7, 8, 9. Формируем s37 = "6"
$$\vee $$ "7"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{37} 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Правее седьмой позиции "дополнительный"
нуль занимает позицию
9. Формируем s38 = s37 $$\vee $$ "9"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{38} 1 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка содержит нули в позициях 6, 7, 9. Найдено
ПМВНК {6, 7, 9} с потоком d6 + d7 + d9.
Формируем s39 = "6" $$\vee $$ "8"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{39} 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Правее восьмой позиции "дополнительный"
нуль занимает позицию
9. Как и на предыдущем шаге, находим следующее ПМВНК {6, 8, 9} с
потоком d6 + d8 + d9.
34. Можно убедиться в том, что анализ седьмой и восьмой строк не приведет к получению новых ПМВНК.
Девятая строка содержит единственный нуль правее позиции 9 - в
позиции 10. Формируем s40 = "9" $$\vee $$ "10"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{40} 1 1 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Найдено последнее ПМВНК {9, 10} с
потоком d9 +
d10.
Предпочтительным способом распараллеливания здесь является
распараллеливание по информации. Наиболее простая реализация его может
быть основана на распределении между процессорами или станциями
локальной сети строк матрицы S. И здесь самую простую реализацию
предлагает принцип
Здесь может быть эффективен тот же принцип, который используется
при обработке баз данных, баз знаний и
Его реализация может быть следующей.
В соответствии с S также упорядочено.
Первоначально первый процессор выбирает для обработки и метит первую
строку, второй — вторую и т.д.
По мере освобождения каждый процессор обращается к матрице S и
выбирает первую из неотмеченных строк. Для согласованного обращения к S
организуется синхронизация с помощью семафора методом взаимного
исключения.
Сеть, в т.ч. транспортная, представляет собой
Рассмотренные параллельные методы решения некоторых задач на транспортных сетях ориентированы на "прорыв в размерности", на выход на большие размерности задач, на задачи высокой, даже — экспоненциальной сложности. Только параллельные вычислительные системы могут решать такие задачи. Здесь очень важна концепция перспективных вычислительных средств: только ли разработка супер-ЭВМ призвана удовлетворить высокие требования по производительности? Не находятся ли на наших столах распределенные вычислительные комплексы РС, объединенные в локальные сети на основе современных, уже достаточно оперативных сетевых технологий? Именно для ответа на эти вопросы и должны критически перерабатываться и вновь создаваться параллельные алгоритмы решения сложных задач.
Пусть [15] в пунктах A1, A2, ... ,Am производят некоторый
однородный продукт в объеме ai (i=1, 2, ... , m)
единиц. В пунктах B1,
B2, ... ,Bn этот продукт потребляется в объеме bj
( j=1, 2, ... , n )
единиц. Из каждого {Ai} возможна
транспортировка в любой Bj. Транспортные
издержки} по перевозке из пункта Ai в пункт Bj единицы
продукции
равны cij (i=1, ... , m; j=1, ... , n).
Необходимо найти такой план перевозок, при котором запросы всех потребителей полностью удовлетворены, весь продукт из пунктов производства вывезен и суммарные транспортные издержки минимальны.
Пусть xij — количество продукта, перевозимого из
пункта Ai в
пункт Bj. Требуется найти значение переменных
(перевозок) xij >= 0 (i = 1, 2, ... , m ; j
= 1, 2, ... , n), удовлетворяющих$$\begin{equation}
Z(x_{ij} ) = \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n {c_{ij}
x_{ij} \quad \to \;\min } }
\end{equation}$$
при ограничениях
$$\begin{equation} \begin{gathered} \sum\limits_{j = 1}^n {x_{ij} = a_i } ,\quad i = 1,...,\;m, \hfill \\ \sum\limits_{i = 1}^m {x_{ij} = b_j } ,\quad j = 1,...,\;n, \hfill \\ \end{gathered} \end{equation}$$
при условии неотрицательности
xij >= 0 (5.3)
и баланса
$$\begin{equation}
\sum\limits_{i = 1}^m {a_i = \sum\limits_{j = 1}^n {b_j .} }
\end{equation}$$
Как известно, условие баланса приводит к линейной зависимости
уравнений в системе (5.2), ранг ее матрицы равен m+n-1.
Сформулируем задачу линейного программирования в канонической постановке, исключив из (5.2) одно уравнение. При этом мы считаем, что условие баланса (5.4) оказывает влияние на корректность постановки задачи и учтено при этой постановке. Исключенное уравнение будем использовать также для контроля получаемого решения.
Следуя плану параллельного решения задачи линейного
программирования и учитывая, что оптимальное решение находится хотя бы
в одной из вершин многогранника допустимых решений, образуемого
ограничениями и условиями, сформируем это множество граней. В его состав
войдут m+n-1 выделенных уравнений-ограничений и m x
n равенств
нулю переменных на основе неотрицательности решения. Выбирая из этой
системы по m x n уравнений с обязательным участием всех
выделенных уравнений-ограничений и решая их совместно, мы можем
находить вершины многогранника решений.
Так мы можем реализовать метод прямого перебора. Количество
вариантов составляет Cm x nm x n - (m + n - 1) .
Это —
количество различных способов приравнивания нулю m x
n-(m+n-1) переменных из их общего числа m x n.
Мы можем реализовать и аналог симплекс-метода, найдя первоначально некоторую вершину, а затем перемещаясь по ребрам в одну из смежных вершин с большим значением целевой функции, пока это возможно.
Исследование плана параллельного решения и формирование алгоритма будем сопровождать примером, для проверки правильности заимствованным в [15]. Для краткости условия (5.3) и (5.4) опущены.
Пример.
Z=7x11+8x12+5x13+3x14+2x21+4x22+5x23+
+9x24+6x31+3x32+1x33+2x34-> min (5.5)
при ограничениях
x11 + x12 + x13 + x14 = 11
x21 + x22 + x23 + x24 = 11
x31 + x32 + x33 + x34 = 8
x11 + x21 + x31 = 5 (5.6)
x12 + x22 + x32 = 9
x13 + x23 + x33 = 9
x14 + x24 + x34 = 7
Введем xij = yk, где k =
(i - 1)n + j.
Исключим из рассмотрения последнее уравнение. Система уравнений граней (действительных и возможных) многогранника решений примет вид
y1 + y2 + y3 + y4 = 11
y5 + y6 + y7 + y8 = 11
y9 + y10 + y11 + y12 = 8 (5.7)
y1+y5+ y9=5
y2+y6+y10 = 9
y3+ y7+ y11 = 9
yk = 0, k = 1, 2, ... , 12.
Итак, на первом этапе задача свелась к выбору и анализу комбинаций
по 12 - 6 = 6 нулевых значений координат искомой вершины
многогранника
решений. Выполняя подстановку выбранной комбинации в (5.7), мы можем
решить образовавшуюся систему шести уравнений с шестью неизвестными.
Таким образом, мы сможем найти координаты некоторой вершины.
Комбинации по шесть нулевых значений координат ("комбинации
нулей") следует выбирать так, чтобы не обратилась в нуль левая часть хотя
бы одного уравнения (5.7), включая исключенное уравнение. Например,
комбинация, где y1 = y2 = y3 = y4 = 0, недопустима.
Найдем дополнительные контрольные ограничения: чтобы решение
было не отрицательным, необходимо, чтобы любое
значение yk, k =
1, ... , m x n, не превышало значение
Тогда в нашем примере y1 <= min(11, 5) =,
аналогично y2 <= , y3 <= , y4 <= , y5 <= , y6 <= , y7 <= , y8 <= , y9 <= , y10 <= , y11 <=, y12 <=
.
Здесь при оценке y4, y8, y12 учтено
последнее уравнение в (5.6).
Воспользуемся векторной формой представления, чтобы подготовить
удобные, нетрудоемкие матричные преобразования. А именно, наша система m
+ n - 1 линейных уравнений-ограничений имеет вид
AY = B,
где A — нуль-единичная матрица, Y —
столбец переменных, B —
столбец свободных членов:$$\begin{equation}
\setcounter{MaxMatrixCols}{20}
\begin{pmatrix}
\colorbox[gray]{0.8}1 \colorbox[gray]{0.8}1 1 1 \colorbox[gray]{0.8}0 0 \colorbox[gray]{0.8}0 0 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0\\
\colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 0 \colorbox[gray]{0.8}1 1 \colorbox[gray]{0.8}1 1 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0\\
\colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 0 \colorbox[gray]{0.8}0 0 \colorbox[gray]{0.8}0 0 1 \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}1 1\\
\colorbox[gray]{0.8}1 \colorbox[gray]{0.8}0 0 0 \colorbox[gray]{0.8}1 0 \colorbox[gray]{0.8}0 0 1 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0\\
\colorbox[gray]{0.8}0 \colorbox[gray]{0.8}1 0 0 \colorbox[gray]{0.8}0 1 \colorbox[gray]{0.8}0 0 0 \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}0 0\\
\colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 1 0 \colorbox[gray]{0.8}0 0 \colorbox[gray]{0.8}1 0 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}1 0\\
\end{pmatrix}
\times
\begin{pmatrix}
y_{1}\\
y_{2}\\
y_{3}\\
y_{4}\\
y_{5}\\
y_{6}\\
y_{7}\\
y_{8}\\
y_{9}\\
y_{10}\\
y_{11}\\
y_{12}\\
\end{pmatrix}
=\begin{pmatrix}
11\\
11\\
8\\
5\\
9\\
9
\end{pmatrix}
\end{equation}$$
Тогда для нахождения хотя бы одного допустимого решения выберем допустимую комбинацию нулей по следующему алгоритму:
l = 0.l := l + 1, yl = 0. Исключим из
матрицы A столбец,
соответствующий этой переменной.A строка, содержащая только нулевые
элементы, или обратилась ли в нуль левая часть исключенного уравнения.
(Предполагаем, что все свободные члены уравнений больше нуля.) При
положительном результате анализа выполняем шаг 5. В противном случае —
следующий шаг.s -й строки A выделяем
множество {ys} переменных, соответствующих единичным элементам.
Проверяем: $$\sum\limits_s {\bar y_s } \geqslant b_s$$?При
отрицательном результате анализа (свободный член превышает
сумму верхних оценок переменных) выполняем шаг 5. В случае успешной
проверки 3 и 4 выполняем шаг 6.yl =
0 выбрано неудачно. Отменяем исключение столбца, соответствующего
переменной yl, и выполняем шаг 2.yl = 0, и если комбинация нулей сформирована не
полностью, выполняем шаг 2.Продолжим рассмотрение примера.
Полагаем y1 = 0. Это не приводит к нарушению оценок, указанных
в алгоритме.
Полагаем y2 = 0. Это также не приводит к нарушению оценок.
Полагаем y3 = 0. Нулевые строки не появились. Однако в первой
строке осталась единственная единица, соответствующая
переменной y4.
Т.к.
Полагаем y4 = 0. Нулевые строки не появились, однако в первой
же
строке осталась единственная единица, соответствующая
переменной y3.
Т.к.
Полагаем y5 = 0. Это не приводит к нарушению оценок.
Полагаем y6 = 0. В пятой строке остается единственная единица,
соответствующая y10. Т.к.
Полагаем y7 = 0, что не приводит к нарушению оценок.
Значение y8 = 0 приводит к нарушению оценки во втором
уравнении.
Значение y9 = 0 приводит к появлению нулевой строки.
Значение y10 = 0 не приводит к нарушению оценок.
Значение y11 = 0 также не приводит к нарушению оценок.
Итак, комбинация нулей найдена. Это отмеченные в (5.8) значения
y1 = 0, y2 = 0, y5 = 0, y7 = 0,
y10 = 0, y11 = 0. (5.9)
Для нахождения других значений переменных необходимо решить систему уравнений на основе (5.8), после исключения нулевых столбцов
$$\begin{pmatrix} 1 1 0 0 0 0 \\ 0 0 1 1 0 0 \\ 0 0 0 0 1 1 \\ 0 0 0 0 1 0 \\ 0 0 1 0 0 0 \\ 1 0 0 0 0 0 \end{pmatrix} \times \begin{pmatrix} y_3\\y_4\\y_6\\y_8\\y_9\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\ 11\\ 8\\ 5\\ 9\\ 9 \end{pmatrix}.$$
Найдем все строки матрицы A, содержащие
не более одного
единичного элемента. Это строки, определяющие компоненты решения y3
= 9, y6 = 9, y9 = 5.
Выполним подстановку, последовательно находя в столбцах
найденных переменных единицы (не более одной) и корректируя правые
части вычитанием найденных значений. Строки и столбцы, соответствующие
найденным значениям переменных, исключаем из матрицы A.
Такой прием подстановки можно повторять до исчерпания уравнений, содержащих в левой части единственную переменную.
В нашем примере после подстановки найденных значений в уравнения
1, 2 и 3 получаем систему$$\begin{pmatrix}
1 0 0\\
0 1 0\\
0 0 1
\end{pmatrix}
\times
\begin{pmatrix}
y_4\\y_8\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11-9\\
11-9\\
8-5
\end{pmatrix}$$
В ней все уравнения имеют единственную переменную.
Они определяют решение y4 = 2, y8 = 2, y12 =
3.
Таким образом, нам не пришлось пока воспользоваться методом
Гаусса, но мы нашли допустимое решение Y0 = (0, 0, 9, 2, 0, 9, 0, 2, 5,
0, 0,
3), для которого выполняются ограничения задачи.
Вектор Y0 определяет
некоторую вершину многогранника допустимых решений, со значением
целевой функции Z(Y0) = 141.
Примем следующий план решения, соответствующий рассмотренному ранее плану параллельного решения задач линейного программирования.
Для перебора всех смежных вершин необходимо в комбинации нулей,
определивших вершину Y0, поочередно исключать одно
значение yr =
0 (это определит одно из исходящих ребер) и оставшуюся систему решать
совместно поочередно со всеми другими уравнениями вида ys = 0, не
входящими в комбинацию нулей. Этим мы будем совершать перемещение в
смежные вершины. Находя значение Z для каждого такого
решения Y1 там, где оно существует, можно найти вершину с меньшим
значением
целевой функции. "Перебравшись" в эту вершину (приняв ее
за Y0 ), мы
можем продолжить анализ смежных ей вершин и т.д. Решение задачи
найдено в том случае, если после перебора всех смежных вершин не
отыскивается вершина с меньшим значением целевой функции.
Продолжим рассмотрение примера.
Итак, (5.8) — исходный вид системы уравнений, (5.9) —
комбинация
нулей ("отсутствующие" столбцы в (5.7) выделены), (5.8) и (5.9)
определяют вершину Y0.
Исключим из (5.9) уравнение y1 = 0, а оставшуюся систему, с
учетом остальных нулей из комбинации (5.9), будем решать совместно с
уравнениями
y3 = 0, y4 = 0, y6 = 0, y8 = 0, y9 = 0, y12 = 0. (5.10)
Значит, в (5.8) положим первоначально y3 = 0 вместо y1 =
0.
Левая часть шестого уравнения (последняя строка матрицы А) обратилась в
нуль.
Положим y4 = 0 вместо y1 = 0. Получим
систему$$\begin{pmatrix}
1 1 0 0 0 0\\
0 0 1 1 0 0\\
0 0 0 0 1 1\\
0 0 0 0 1 0\\
0 0 1 0 0 0\\
0 1 0 0 0 0\\
\end{pmatrix}
\times
\begin{pmatrix}
y_1\\y_3\\y_6\\y_8\\y_9\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}$$
Из нее, как и ранее, за два шага подстановки
находим y3 = 9, y6 =
9, y9 = 5, а затем — y1 = 2, y8 =
2, y12 = 3.
Таким образом, найдено новое допустимое решение Y1 = (2, 0, 9,
0, 0,
9, 0, 2, 5, 0, 0, 3). Однако Z(Y1) =149 > 141. Найденную
вершину
отвергаем. Вместе с тем, т.к. мы нашли вершину "на другом конце"
анализируемого ребра, то и анализ этого ребра прекращаем.
Приступаем к анализу следующего ребра, исключив из (5.9)
уравнение y2 = 0. Оставшуюся систему, с учетом остальных нулей из
(5.9), будем решать совместно с теми же уравнениями (5.10).
Положим в (5.8) y3 = 0 вместо y2 = 0. Последняя
строка
матрицы A стала нулевой.
Замена y4 = 0 вместо y2 = 0 приводит к
системе$$\begin{pmatrix}
1 1 0 0 0 0\\
0 0 0 0 1 1\\
0 0 0 0 1 1\\
0 0 0 0 1 0\\
0 0 1 0 0 0\\
0 1 0 0 0 0\\
\end{pmatrix}
\times
\begin{pmatrix}
y_2\\y_3\\y_6\\y_8\\y_9\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}$$
На ее основе находим новый вектор — допустимое
решение Y1 = (0,
2, 9, 0, 0, 9, 0, 2, 5, 0, 0, 3). Однако Z(Y1) = 151 >
141. Найденную
вершину также отвергаем. Ребро исследовано полностью.
Исключим из (5.9) уравнение y5 = 0, а оставшуюся систему, с
учетом остальных нулей из (5.9), будем решать совместно с теми же
уравнениями (5.10).
Положим в (5.8) y3 = 0 вместо y5 = 0. Последняя
строка
матрицы A обратится в нуль.
Положим y4 = 0 вместо y5 = 0. В первом уравнении не
выполняется ограничение по y3 (.
Положим y6 = 0 вместо y5 = 0. Пятая
строка A обратилась в
нулевую.
Положим y8 = 0 вместо y5 = 0. Получим систему
уравнений$$\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 0 0 1 0 \\
0 0 0 1 0 0 \\
1 0 0 0 0 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_3\\y_4\\y_5\\y_6\\y_9\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}$$
Находим y3 = 9, y6 = 9 и
после подстановки — y4 = 2, y5 =
2. Вновь выполняем подстановку, находим y9 = 3, и после
следующей
подстановки y12 = 5.
Итак, получена вершина Y1 = (0, 0, 9, 2, 2, 9, 0, 0, 3, 0, 0,
5). Т.к. Z(Y1) = 119 < 141, полагаем Y0 :=
Y1 и начинаем пробу возможных
перемещений вдоль ребер из найденной вершины многогранника решений в
вершину с меньшим значением целевой функции:$$\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 0 0 1 0 \\
0 0 0 1 0 0 \\
1 0 0 0 0 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_3\\y_4\\y_5\\y_6\\y_9\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}$$
Запишем вновь аналогично (5.8) и (5.9) систему
уравнений,
решением которой является вершина Y0, отметив в ней
"отсутствующие"
столбцы:$$\begin{equation}
\setcounter{MaxMatrixCols}{20}
\begin{pmatrix}
\colorbox[gray]{0.8}1 \colorbox[gray]{0.8}1 1 1 0 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 \\
\colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 0 1 1 \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}1 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 \\
\colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 0 0 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 1 \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}1 1 \\
\colorbox[gray]{0.8}1 \colorbox[gray]{0.8}0 0 0 1 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 1 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 \\
\colorbox[gray]{0.8}0 \colorbox[gray]{0.8}1 0 0 0 1 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}0 0 \\
\colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 1 0 0 0 \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}0 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}1 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_1\\y_2\\y_3\\y_4\\y_5\\y_6\\y_7\\y_8\\y_9\\y_{10}\\y_{11}\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}
\end{equation}$$
Находим
y1 = 0, y2 = 0, y7 = 0, y8 = 0, y10 = 0, y11 = 0. (5.12)
Начнем движение по ребрам из данной вершины. Для этого будем исключать из (5.12) одно из уравнений, а оставшуюся систему будем решать совместно с не вошедшими в (5.12) уравнениями:
y3 = 0, y4 = 0, y5 = 0, y6 = 0, y9 = 0, y12 = 0. (5.13)
При этом надо учесть, что могут формироваться ранее исследованные комбинации нулей. (Комбинации нулей удобно метить индексным кодом, который следует запоминать для исключения повторного анализа.)
Положим в (5.13) y3 = 0 вместо y1 = 0. Последняя
строка
матрицы A станет нулевой.
Замена y1 = 0 уравнением y4 = 0 приводит к
системе$$\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 0 0 1 0 \\
0 0 0 1 0 0 \\
1 0 0 0 0 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_1\\y_3\\y_5\\y_6\\y_9\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}$$
Решаем с помощью подстановок, находим Y1 =
(2, 0, 9, 0, 2, 9, 0, 0, 3,
0, 0, 5). Т.к. Z(Y1) = 127 > 119, найденную вершину
отвергаем.
Примечание. Нам вновь не пришлось воспользоваться схемой Гаусса. По-видимому, вид уравнений и вхождение каждой переменной не более чем в два уравнения позволяют довольствоваться простой подстановкой. Ниже мы исследуем это подробнее.
Переходим к другому ребру, заменяя в (5.12) уравнение y2 =
0 уравнениями из (5.13).
Замена y3 = 0 вместо y2 = 0 приводит к тому, что
последняя
строка матрицы A становится нулевой.
Замена y4 = 0 вместо y2 = 0 приводит к системе
уравнений$$\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 1 0 1 0 \\
1 0 0 1 0 0 \\
0 1 0 0 0 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_2\\y_3\\y_5\\y_6\\y_9\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}$$
Находим с помощью подстановок Y1 = (0, 2, 9,
0, 4, 7, 0, 0, 1, 0, 0, 7).
Т.к. Z(Y1) = 127 > 119, найденную вершину отвергаем и
переходим к
анализу следующего ребра.
Замена y3 = 0 вместо y7 = 0 приводит к тому, что в
первом
уравнении (9.25) не выполняется условие по ограничению y4 (.
Замена y4 = 0 вместо y7 = 0 приводит к тому, что в
первом же
уравнении (9.25) не выполняется условие по ограничению y3 (.
Замена y5 = 0 вместо y7 = 0 приводит к
системе$$\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 0 0 1 0 \\
0 0 1 0 0 0 \\
1 0 0 1 0 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_3\\y_4\\y_6\\y_7\\y_9\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}$$
Находим Y1 = (0, 0, 7, 4, 0, 9, 2, 0, 5, 0,
0, 3). Однако Z(Y1) = 129 > 119.
Переходим к анализу следующего ребра, поочередно заменяя
уравнениями из (5.13) уравнение y8 = 0 из (5.11).
Замена y3 = 0 вместо y8 = 0 приводит к образованию
последней
нулевой строки матрицы A.
Замена y4 = 0 вместо y8 = 0 приводит к тому, что в
первом
уравнении не выполняется условие по ограничению y3 (.
Замена y5 = 0 вместо y8 = 0 приводит к
системе$$\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 0 0 1 0 \\
0 0 1 0 0 0 \\
1 0 0 1 0 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_3\\y_4\\y_6\\y_8\\y_9\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}$$
Находим Y1 = (0, 0, 9, 2, 0, 9, 0, 2, 5, 0,
0, 3). Т.к. Z(Y1) = 141 > 119, найденную вершину
отвергаем.
Переходим к анализу следующего ребра, поочередно заменяя
уравнениями из (5.13) уравнение y10 = 0 из (5.11).
Замена y3 = 0 вместо y10 = 0 приводит к тому, что
в первом
уравнении (5.11) не выполняется условие по ограничению y4 (.
Замена y4 = 0 вместо y10 = 0 приводит к тому, в
первом же
уравнении (5.11) не выполняется условие по ограничению y3 (.
Замена y5 = 0 вместо y10 = 0 приводит к тому, что
во втором
уравнении (5.11) не выполняется условие по ограничению y6 (.
Замена y6 = 0 вместо y10 = 0 приводит к тому, что
во втором же
уравнении (5.11) не выполняется условие по ограничению y5 (.
Замена y9 = 0 вместо y10 = 0 приводит к
системе$$\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 1 0 1 0 \\
0 0 0 1 1 0 \\
1 0 0 0 0 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_3\\y_4\\y_5\\y_6\\y_{10}\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}$$
Находим Y1 = (0, 0, 9, 2, 5, 6, 0, 0, 0, 3,
0, 5). Т.к. Z(Y1) = 104 < 119,
"перемещаемся" в найденную вершину с меньшим значением
целевой функции.
Новая вершина характеризуется системой уравнений
y1 = 0, y2 = 0, y7 = 0, y8 = 0, y9 = 0, y11 = 0. (5.14)
Перепишем систему (5.11), выделив "отсутствующие" столбцы, вследствие (5.14):$$\begin{equation} \setcounter{MaxMatrixCols}{20} \begin{pmatrix} \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}1 1 1 0 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 \colorbox[gray]{0.8}0 0 \\ \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 0 1 1 \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}0 0 \colorbox[gray]{0.8}0 0 \\ \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 0 0 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}1 1 \colorbox[gray]{0.8}1 1 \\ \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}0 0 0 1 0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}1 0 \colorbox[gray]{0.8}0 0 \\ \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}1 0 0 0 1 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 1 \colorbox[gray]{0.8}0 0 \\ \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 1 0 0 0 \colorbox[gray]{0.8}1 \colorbox[gray]{0.8}0 \colorbox[gray]{0.8}0 0 \colorbox[gray]{0.8}1 0 \\ \end{pmatrix} \times \begin{pmatrix} y_1\\y_2\\y_3\\y_4\\y_5\\y_6\\y_7\\y_8\\y_9\\y_{10}\\y_{11}\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix} \end{equation}$$ После исключения одного из уравнений (5.14) оставшаяся система (5.15), (5.14) будет решаться совместно с одним из уравнений
y3 = 0, y4 = 0, y5 = 0, y6 = 0, y10 = 0, y12 = 0
(5.16)
Замена y1 = 0 на y3 = 0 приводит к появлению
(последней)
нулевой строки матрицы A.
Замена y4 = 0 вместо y1 = 0 приводит к
системе
$$\begin{equation*} \begin{pmatrix} 1 1 0 0 0 0 \\ 0 0 1 1 0 0 \\ 0 0 0 0 1 1 \\ 1 0 1 0 1 0 \\ 0 0 0 1 1 0 \\ 0 1 0 0 0 0 \\ \end{pmatrix} \times \begin{pmatrix} y_1\\y_3\\y_5\\y_6\\y_{10}\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix} \end{equation*}$$
Отсюда Y1 = (2, 0, 9, 0, 3, 8, 0, 0, 0, 1, 0,
7). Т.к. Z(Y1) = 114 > 104,
исследуем следующее ребро, исключив в системе (5.14) уравнение y2 =
0 и заменяя его последовательно уравнениями из (5.16).
Замена y4 = 0 вместо y2 = 0 приводит к
системе$$\begin{equation}
\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 1 0 1 0 \\
1 0 0 1 1 0 \\
0 2 0 0 0 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_2\\y_3\\y_5\\y_6\\y_{10}\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}
\end{equation}$$
Находим Y1 = (0, 2, 9, 0, 5, 6, 0, 0, 0, 1,
0, 7). Т.к. Z(Y1) = 114 > 104, исследуем следующее
ребро, исключив в системе (5.14) уравнение y7 = 0 и заменяя его
последовательно уравнениями из (5.16).
Замена y3 = 0 вместо y7 = 0 приводит к тому, что в
первом
уравнении (9.29) не выполняется условие по ограничению y4 (.
Замена y4 = 0 вместо y7 = 0 приводит к тому, что в
первом же
уравнении (9.29) не выполняется условие по ограничению y3 (.
Замена y5 = 0 вместо y7 = 0 приводит к формированию
нулевой
(четвертой) строки матрицы A.
Замена y6 = 0 вместо y7 = 0 приводит к формированию
нулевой
(пятой) строки матрицы A.
Замена y10 = 0 вместо y7 = 0 приводит к тому, что
в третьем
уравнении (5.15) не выполняется условие по ограничению y12
(.
Замена y12 = 0 вместо y7 = 0 приводит к
системе$$\begin{equation}
\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 1 0 \\
0 0 0 0 0 1 \\
0 0 1 0 0 0 \\
0 0 0 1 0 1 \\
1 0 0 0 1 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_3\\y_4\\y_5\\y_6\\y_{10}\\y_{12}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}
\end{equation}$$
Находим Y1 = (0, 0, 4, 7, 5, 1, 5, 0, 0, 8,
0, 0). Т.к. Z(Y1) = 104 и это
не меньше уже полученной оценки, исследуем следующее ребро, исключив в
системе (5.14) уравнение y8 = 0 и заменяя его последовательно
уравнениями из (5.16).
Замена y3 = 0 вместо y8 = 0 приводит к образованию
нулевой
(шестой) строки матрицы A.
Замена y4 = 0 вместо y8 = 0 приводит к тому, что в
первом
уравнении (5.15) не выполняется условие по ограничению y3 (.
Замена y5 = 0 вместо y8 = 0 приводит к образованию
нулевой
(четвертой) строки матрицы A.
Замена y6 = 0 вместо y8 = 0 приводит к тому, что в
пятом
уравнении (5.15) не выполняется условие по ограничению y10 (.
Замена y10 = 0 вместо y8 = 0 приводит к тому,
что в третьем
уравнении (5.15) не выполняется условие по ограничению y12 (.
Замена y12 = 0 вместо y8 = 0 приводит к
системе$$\begin{equation}
\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 1 0 0 0 \\
0 0 0 1 0 1 \\
1 0 0 0 0 0 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_3\\y_4\\y_5\\y_6\\y_{8}\\y_{10}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}
\end{equation}$$
Ее решение Y1 = (0, 0, 9, 2, 5, 1, 0, 5, 0,
8, 0, 0) определяет значение Z(Y1) = 134 > 104.
Продолжаем перебор по следующему ребру.
Замена y3 = 0 вместо y9 = 0 приводит к образованию
нулевой
(шестой) строки матрицы A.
Замена y4 = 0 вместо y9 = 0 приводит к тому, что в
первом
уравнении (5.15) не выполняется условие по ограничению y3 (.
Замена y5 = 0 вместо y9 = 0 приводит к тому, что во
втором
уравнении (5.15) не выполняется условие по ограничению y6 (.
Замена y6 = 0 вместо y9 = 0 приводит к тому, что во
втором же
уравнении (5.15) не выполняется условие по ограничению y5 (.
Замена y10 = 0 вместо y9 = 0 приводит к
системе
$$\begin{equation} \begin{pmatrix} 1 1 0 0 0 0 \\ 0 0 1 1 0 0 \\ 0 0 0 0 1 1 \\ 0 0 1 0 1 0 \\ 0 0 0 1 0 0 \\ 1 0 0 0 0 0 \\ \end{pmatrix} \times \begin{pmatrix} y_3\\y_4\\y_5\\y_6\\y_{9}\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix} \end{equation}$$
Ее решение Y1 = (0, 0, 9, 2, 2, 9, 0, 0, 3,
0, 0, 5) определяет значение Z(Y1) = 119 > 104.
Приступаем к анализу следующего ребра, исключая в (5.14)
уравнение y11 = 0 и заменяя его последовательно уравнениями из
(5.16).
Замена y3 = 0 вместо y11 = 0 приводит к тому, что
в первом
уравнении (5.15) не выполняется условие по ограничению y4 (.
Замена y4 = 0 вместо y11 = 0 приводит к тому, что
в первом
уравнении (5.15) не выполняется условие по ограничению y3 (.
Замена y5 = 0 вместо y11 = 0 приводит к тому, что
во втором
уравнении (5.15) не выполняется условие по ограничению y6 (.
Замена y6 = 0 вместо y11 = 0 приводит к тому, что
во втором же
уравнении (5.15) не выполняется условие по ограничению y5 (.
Замена y10 = 0 вместо y11 = 0 приводит к системе
$$\begin{equation} \begin{pmatrix} 1 1 0 0 0 0 \\ 0 0 1 1 0 0 \\ 0 0 0 0 1 1 \\ 0 0 1 0 1 0 \\ 0 0 0 1 0 0 \\ 1 0 0 0 1 0 \\ \end{pmatrix} \times \begin{pmatrix} y_3\\y_4\\y_5\\y_6\\y_{11}\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix} \end{equation}$$
Система не имеет решения, т.к. ранг матрицы системы не равен рангу
Примечание. В несложном
примере это легко обнаружить: вторая
строка матрицы равна сумме четвертой и пятой строк, что противоречит
соотношению между соответствующими свободными членами, $$9 + 5 \ne 11$$. По-видимому, это говорит в пользу применения схемы Гаусса. В
противном случае мы должны контролировать последовательно получаемые
решения на удовлетворение тем соотношениям, которые в его получении не
участвовали. Так, из четвертого и пятого уравнений имеем y5 =
5, y6 =
9. Но в соответствии со вторым уравнением y5 + y6 = 11. В
то же время,
совершая подстановку во второе уравнение, мы получаем нулевую левую
часть, т.е. нулевую строку матрицы A, что опять говорит в пользу
подстановок!
Замена y12 = 0 вместо y11 = 0 приводит к
системе$$\begin{equation}
\begin{pmatrix}
1 1 0 0 0 0 \\
0 0 1 1 0 0 \\
0 0 0 0 1 1 \\
0 0 1 0 1 0 \\
0 0 0 1 1 0 \\
1 0 0 0 0 1 \\
\end{pmatrix}
\times
\begin{pmatrix}
y_3\\y_4\\y_5\\y_6\\y_{10}\\y_{11}
\end{pmatrix}
=
\begin{pmatrix}
11\\11\\8\\5\\9\\9
\end{pmatrix}
\end{equation}$$
Ее решение Y1 = (0, 0, 4, 7, 5, 6, 0, 0, 0,
3, 5, 0) определяет значение
целевой функции Z(Y1) = 89 < 104.
Полагаем Y0 := Y1. Теперь мы должны перемещаться по ребрам из
вновь найденной вершины в поисках вершины с еще меньшим значением
целевой функции. Придется перебрать до 6 x 6 = 36 вариантов
такого
перемещения. Однако, достигнув ответа задачи в [15], положимся на его
правильность и прекратим рассмотрение примера.
Остался неясным вопрос: приходится ли в общем случае при решении систем линейных уравнений для данной задачи пользоваться схемой Гаусса, или достаточно последовательно пользоваться простыми подстановками?
Подстановки мы легко выполняли в том случае, если в результате введения нулевых комбинаций у нас получались уравнения, содержащие в левой части единственную переменную. Если таких уравнений нет, то очевидна целесообразность применения схемы Гаусса.
Тогда выясним, существует ли комбинация нулей, такая, при которой в
каждой строке A, с учетом неисключенной строки, остается не менее
двух
единиц.
Рассмотрим только n = 4 последних уравнений из (5.6): три
последних уравнения из (5.7) и уравнение y4 + y8 + y12 = 7.
Их
матрица имеет вид$$\begin{array}{|c|c |c |c |c |c |c |c |c |c |c |c|}
\hline
\colorbox[gray]{0.8}1 1 1 \\
\hline
1 \colorbox[gray]{0.8}1 1 \\
\hline
1 1 \colorbox[gray]{0.8}1 \\
\hline
\colorbox[gray]{0.8}1 1 1 \\
\hline
\end{array}$$
Т.е. она состоит из m матриц с единицами по
главной диагонали.
Чтобы в одной строке такой матрицы остались хотя бы две единицы,
необходимо оставить невычеркнутыми хотя бы два столбца. В другой строке
должны быть не вычеркнуты хотя бы два обязательно других столбца. Итого,
для четырех строк примера должны остаться невычеркнутыми восемь
различных столбцов. Значит, вычеркнуть мы можем только четыре столбца
(например, как выделено на изображении матрицы), а нам надо положить
равными нулю шесть переменных! Тем самым, на базе лишь этих "нижних"
уравнений образуются не менее двух уравнений с единственной переменной
в левой части.
Т.к. произведение m x n растет значительно быстрее
суммы m +
n, то с ростом параметров задачи указанное свойство усугубляется.
Следовательно, мы с полным основанием может рассчитывать на принцип
подстановки, как мы и делали в примере.
Однако программирование схемы Гаусса может оказаться не только менее трудоемко. Не следует забывать, что в процессе преобразования системы уравнений и последовательного получения значений переменных оперативно устанавливается как неразрешимость или неоднозначность, так и отрицательное решение.
Например, система (5.17) при реализации схемы Гаусса проходит следующие стадии преобразования.
Вычитание первой строки из последней и формирование разности на месте второй строки:$$\begin{equation} \begin{pmatrix} 1 1 0 0 0 0 \\ 0 -1 0 0 2 0 \\ 0 0 1 1 0 0 \\ 0 0 0 0 1 1 \\ 0 0 1 0 0 0 \\ 0 0 0 1 0 0 \\ \end{pmatrix} \times \begin{pmatrix} y_3\\y_4\\y_5\\y_6\\y_{11}\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\-2\\11\\8\\5\\9 \end{pmatrix} \end{equation}$$
Получение нулевой строки в матрице достаточно для заключения о непригодности решения (в данном случае оно не существует).
Рассмотренная транспортная задача, без ограничения пропускной способности транспортных потоков, демонстрирует параллельный алгоритм ее решения. Программа, одинаковая для всех процессоров многопроцессорной ВС или станций локальной вычислительной сети, в основной своей части реализует выборку очередного ребра, исходящего из первоначально найденной вершины многогранника решений. Вдоль него ищется смежная вершина с меньшим значением целевой функции. Процессор, нашедший такую вершину, производит замену ранее исследовавшейся вершины и вынуждает все процессоры приступить к анализу ребер, исходящих из новой вершины. Так — до неудачного поиска вершины с меньшим значением целевой функции.
Использование в качестве источника загрузки процессоров общей уточняемой базы данных, в которой хранятся исследованные варианты поиска, позволяет выявлять еще не исследованные варианты и равномерно распределять нагрузку между процессорами.
Пусть dij — пропускная способность коммуникации (i,
j), что
порождает ограничение
xij <= dij
(5.18)
для всех i, j.
Тогда важная в практическом отношении задача заключается в
минимизации (5.1) — целевой функции Z при ограничениях (5.2),
(5.3),
(5.4) и (5.18).
Очевидно, что для разрешимости T -задачи должны выполняться
условия$$\sum\limits_{j = 1}^n {d_{ij} \geqslant a_i ,\quad i = 1,...,m,}$$
$$\sum\limits_{i = 1}^m {d_{ij} \geqslant b_j ,\quad j = 1,...,n}.$$
Как видим, данную задачу тоже можно решать прямым перебором
вершин R с учетом резко увеличившегося числа уравнений его границ: их
число, с учетом линейной зависимости, составляет теперь n+m-1+2(mx
n). С учетом границ на основе условий неотрицательности решения, общее
число испытываемых систем линейных уравнений составит C2(m x
n)m x n - (m + n - 1).
Однако при этом переборе мы будем исследовать явно несовместимые
варианты компоновки систем — а именно, варианты, включающие пары
уравнений вида xij=0 и xij=dij. Тогда поступим
иначе.
Сначала будем выбирать комбинации переменных, участвующих в
формировании указанных систем линейных уравнений. Всех таких
комбинаций будет Cm x
nm x n - (m + n - 1). После
выбора очередной комбинации переменных определим комбинацию их
значений — 0 или значение пропускной способности. Таких комбинаций для
выбранного набора m x n - (m + n) - 1 переменных
будет 2m x n - (m + n - 1) .
Таким образом, общее число испытываемых систем линейных
уравнений составит Cm x
nm x n - (m + n - 1) x
2m x n - (m + n - 1) .
Воспользуемся и здесь параллельным аналогом симплекс-метода, найдя первоначально некоторую вершину многогранника решений, а затем пытаясь "переместиться" в смежную вершину с меньшим значением целевой функции.
Сделаем важное замечание.
Будем считать, что если вдоль прямой,
отрезком которой является исходящее из вершины L ребро, найдена
смежная вершина M, то на этой же прямой, "в другую
сторону" от L,
нет смежных вершин. Т.е. одна прямая может связывать не более двух
вершин многогранника решений. Предположим, что три вершины M, L,
N лежат на одной прямой. Т.к. L — вершина, то существует
хотя бы еще
одно исходящее из нее ребро. Пусть оно соединяет L с
вершиной K.
Тогда построим плоскость, проходящую через три точки M, N, K, т.е.
через
точку K и прямую MN, которой принадлежит
точка L. Плоскость
поглотила как точку L, так и новое ребро, существование которого мы
предположили.
Это означает, что если мы нашли смежную вершину "с одной стороны" по прямой, отрезком которой является исходящее ребро, то искать смежную вершину "с другой стороны" по этой же прямой не следует.
Этим предположением мы пользовались в предыдущем разделе,
прекращая дальнейший поиск других смежных вершин вдоль прямой в
случае, если одна такая вершина оказывается найденной. Здесь же это
замечание, в частности, означает, что если мы нашли смежную данной
вершину со значением xij = 0 ( xij = dk ), то
испытывать значение xij = dk ( xij = 0 ) не
следует. Т.е., как и ранее, мы вдоль каждого
исходящего ребра будем искать единственную смежную
вершину.
Введем, как и ранее, линейное множество переменных и сформулируем задачу:
Z = 2y1 + 3y2 + 3y3 + 2y4 + 2y5 + y6 ->
min
при ограничениях
y1 + y2 + y3 = 12
y4 + y5 + y6 =10 (5.21)
y1+ y4 =7
y2 + y5 =7
y3 + y6 = 8
и при условии
0 <= y1 <= 4, 0 <= y2 <= 4, 0 <= y3 <= 5, 0 <= y4 <= 4, 0 <= y5
<= 4,
0 <= y6 <= 3. (5.22)
Сформируем ограничения каждой переменной:
y1 + y2 + y3 = 12
y4 + y5 + y6 = 10 (5.23)
y1 + y4 = 7
y2 + y5 = 7
y1 = 0; y1 = 4
y2 = 0; y2 = 4
y3= 0; y3 = 5 (5.24)
y4 = 0; y4 = 4
y5 = 0; y5 = 4
y6 = 0; y6 = 3
Начнем перебор систем по шесть граней в поисках координат одной из вершин многогранника решений. В каждой такой системе должны присутствовать все уравнения (5.23) и два уравнения с разными переменными из (5.24).
Для формирования первой системы уравнений пробуем добавить к
(5.23) уравнение y1 = 0. В результате в третьем уравнении не
выполняется ограничение по y4 (.
Пробуем вариант y1 = 4. Совершив подстановку, убеждаемся, что
он не приводит к подобному противоречию.
Полагаем y2 = 0. В первом уравнении не выполняется ограничение
по y3 (.
Полагаем y2 = 4. Получаем и решаем систему
уравнений
y1 + y2 + y3 = 12
y4 + y5 + y6 = 10
y1 + y4 = 7
y2 + y5 = 7
y1= 4
y2 = 4.
Находим Y = (4, 4, 4, 3, 3, 4). Однако
данная точка не является
вершиной многогранника решений, т.к. y6 = 4 противоречит условию
(5.22).
Испытываем уравнение y3 = 0. В первом уравнении нарушается
ограничение по y1 + y2 (.
Испытываем уравнение y3 = 5. Решаем систему
уравнений
y1 + y2 + y3 = 12
y4 + y5 + y6 = 10
y1 + y4 = 7
y2 + y5 = 7
y1 = 4
y3 = 5.
Находим Y0 = (4, 3, 5, 3, 4, 3).
Решение удовлетворяет условиям
задачи, следовательно, найденная точка — вершина многогранника решений.
Находим значение целевой функции Z(Y0) = 49.
На основе (5.23) и (5.24) выпишем уравнения всех граней, которым
удовлетворяет вершина Y0, т.е. все грани, образующие эту вершину:
y1 + y2 + y3 = 12
y4 + y5 + y6 = 10 (5.25)
y1 + y4 = 7
y2 + y5 = 7
y1 = 4
y3 = 5
y5 = 4
y6 = 3.
Выбирая из (5.25) комбинации по пять уравнений (в каждую
комбинацию обязательно входят все уравнения (5.23)), мы формируем
прямые, которым принадлежат ребра (принадлежащие или не
принадлежащие многограннику допустимых решений), исходящие из
вершины Y0. Решая совместно поочередно с другими гранями из
(5.24)
y1 = 0, y2 = 0, y2 = 4, y3 = 0, y4 = 0, y4 = 4, y5 = 0,
y6 = 0,(5.26)
производим поиск смежной вершины. Нам необходима вершина с меньшим
значением целевой функции Z.
Первая комбинация пяти уравнений составляет
y1 + y2 + y3 = 12
y4 + y5 + y6 = 10 (5.27)
y1 + y4 = 7
y2 + y5 = 7
y1 = 4.
Решая последовательно с уравнениями из (5.26), находим первый
непротиворечивый вариант для y2 = 4. Находим точку Y1 =
(4, 4, 4, 3, 3,4), которая ранее исследовалась и не является вершиной многогранника
решений.
Использование значений y3 = 0 и y4 = 0 приводит к
невыполнению ограничений.
Значение y4 = 4 приводит к противоречию в третьем
уравнении, $$4+ 4 \ne 7$$.
Значения y5 = 0 и y6 = 0 также приводят к
невыполнению
ограничений.
Таким образом, исследованное предполагаемое ребро не принадлежит многограннику решений.
Следующая комбинация пяти уравнений на основе (5.25) составляет
y1 + y2 + y3= 12
y4 + y5 + y6 = 10 (5.28)
y1 + y4 = 7
y2 + y5 = 7
y3 = 5.
Решая последовательно с уравнениями (значениями) из (5.26),
получаем для y2 = 4 точку Y1 = (3, 4, 5, 4, 3, 3).
Т.к. все ограничения
выполняются, Y1 — вершина многогранника решений.
Однако Z(Y1) =
50 > 49, — переходим к исследованию следующего ребра.
Оно определяется системой уравнений
y1 + y2 + y3 = 12
y4 + y5 + y6 = 10 (5.29)
y1 + y4 = 7
y2 + y5 = 7
y5 = 4.
Данная система решается последовательно с уравнениями из (5.26).
Только при значении y4 = 4 получаем не противоречивую систему и
находим точку Y = (3, 3, 6, 4, 4, 2), которая не является вершиной
многогранника решений, т.к. не выполняется условие y3 <= 5. Т.е.
исследованное предполагаемое ребро не принадлежит многограннику
решений.
Последнее предполагаемое ребро определяется системой уравнений
y1 + y2 + y3 = 12
y4 + y5 + y6 = 10
y1 + y4 = 7
y2 + y5 = 7
y6 = 3.
Она решается последовательно с уравнениями из (5.26).
При y2 = 4 получаем непротиворечивую систему и
находим Y1 =
(3, 4, 5, 4, 3, 3), которая является смежной вершиной, т.к. удовлетворяет
всем ограничениям и условиям. Однако Z(Y1) = 50 > 49.
Т.к. все ребра, исходящие из Y0, исследованы, и вершина с
меньшим
значением целевой функции не найдена, вершина Y0 определяет
окончательное решение задачи.
В рассмотренном примере ограничения пропускной способности столь существенны, что не допустили "нулевых" перевозок по одним магистралям во избежание перегрузки других магистралей. Это характерно для исследования фрагмента транспортной сети, когда выделяются допустимые загрузки магистралей. В целом, ограничения могут быть менее жестки либо практически отсутствовать.
Предлагаемый алгоритм, как и ранее, обеспечивает параллельную
структуру программы, воспроизводящую
Исследование потоков в сети — важная, всегда актуальная задача
исследования операций. Она лежит в основе моделирования при
проектировании как транспортных сетей, так и сетей водоснабжения и
канализации. Известен ряд классических моделей (приводимых, например, в
[15]) в этой области. Важнейшую роль играют модели, позволяющие
определить "узкие" мести сети. Они определяют ее максимальную
пропускную способность между выделенными пунктами, или, иначе говоря,
ее минимальное сечение. Это задача
При аналитическом моделировании сети используется известный [15] алгоритм Форда-Фалкерсона.
Теория параллельного программирования способна предложить более
простой алгоритм перебора. Его достоинством является параллелизм,
который позволяет эффективно использовать многопроцессорные ВС и
вычислительные комплексы на основе рабочих станций локальной сети.
Возможен наиболее простой способ распараллеливания на основе
применения
Пусть задана сеть (рис. 5.1). Дуги ее назовем каналами. Каналы
пронумерованы. Направление потоков показано стрелками. Вершины —
точки сопряжения каналов, вершина A — исток,
вершина B — сток.
Каждая дуга i сопровождается информацией об интересующих нас
характеристиках потока, например, о пропускной
способности di канала. В
этом случае правомерен вопрос о максимальной пропускной способности
сети, обусловленной минимальным сечением.
(рис 5.1) Сеть для оценки пропускной способности
В терминах теории параллельного программирования (лекция 7)
каждое сечение сети (например, сечение, пересекающее каналы 1, 2, 4, 7)
является
В [3] приводится алгоритм перебора всех полных множеств взаимно независимых работ. Усовершенствуем его, получая такие множества, упорядоченные по номерам каналов, и исключая повторное нахождение одних и тех же полных множеств. (В лекции 7 изложенные ниже преобразования будут рассмотрены глубже.)
Построим треугольную матрицу следования S, отражающую граф
сети (рис. 5.2а). Сложив каждую последующую строку с теми
предыдущими, которые соответствуют единичным элементам этой строки,
получим матрицу следования S с S и объединим с ее начальным видом
(рис. 5.2в).
Иначе, отобразим S симметрично относительно главной диагонали.
Получим матрицу S, отображающую как порядок следования, так и
порядок предшествования каналов.
(рис 5.2) Полная матрица следования каналов:а — начальный вид, б — дополнение транзитивными связями, в — конечный вид
Теперь матрица S полностью отражает взаимную независимость
каналов. Например, если сложить логически строки 1, 2, 3, то получим
строку, содержащую нули только в позициях 1, 2, 3. Тем самым мы получим
ПМВНК {1, 2, 3}. Множество полное, т.к. дополнительное сложение с любой
другой строкой изменит состав нулей.
Таким образом, наша задача заключается в том, чтобы испытать все варианты сложения групп строк так, чтобы нули в строке-результате оказывались в тех и только в тех позициях, которые соответствуют строкам- слагаемым. Тогда эти строки определят очередное ПМВНК. Упорядочение по номерам строк поможет нам избежать повторного получения ПМВНК с другим порядком следования номеров каналов.
Пусть стек составляют нуль-единичные строки длины n (число
каналов сети). Для каждой строки известно упорядоченное по номерам
множество M каналов, логическая сумма строк которых в
матрице S определила данную строку. Номер k последнего
канала в этом множестве
известно. Для каждой строки известен последний испытанный нулевой
элемент.
i -ю, i = 1, ... ,n-1, строку в
стек. Полагаем M ={i}, k = i.j > i. Переходим к выполнению шага 4.j —
формируем новую вершину стека. Номером канала j дополняем
множество каналов M, участвующих в формировании новой
строки. Полагаем k = j.M, то M — очередное найденное ПМВНК. Фиксируем это
множество. В
любом случае исключаем строку-вершину стека из стека. Выполняем шаг 2.Продолжим исследование приведенной выше сети.
Заносим в стек первую строку матрицы S. Находим первый нуль
после обязательного нуля в первой позиции. Этот нуль указывает, что каналы
1 и 2 s1 в вершине
стека$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Она содержит нули правее позиции 2. Это говорит о том,
что 1 и 2 не
исчерпывают ПМВНК.
Находим первый нуль правее позиции 2 — нуль в позиции 3.
Складываем логически s2 = s1 $$\vee$$ "3". Получаем новую строку в
вершине стека и весь стек в
виде$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_2 1 1 1 1 1 1 1 \\
\cline{2-11}
s_1 1 1 1 1 \\
\cline{2-11}
"1" 1 1 \\
\cline{2-11}
\end{array}$$
Строка в вершине стека содержит нули только в тех
позициях, которые
соответствуют образующим ее каналам 1, 2, 3. Это означает, что мы нашли
ПМВНК {1, 2, 3}, т.е. некоторый разрез сети. Минимальный поток,
проходящий через него, составляет d1 + d2 + d3.
Исключаем из стека строку s2 и в
строке s1 испытываем
следующий нуль правее позиции 2. Это нуль в позиции 4. Формируем новую
вершину стека s3 = s1 $$\vee$$ "4".$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_3 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка s3 содержит нули не только в
позициях 1, 2, 4. Первый такой
нуль правее позиции 4 — в позиции 7.
Формируем новую вершину стека s4 = s3 $$\vee $$ "7". Стек принимает
вид$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_4 1 1 1 1 1 1 \\
\cline{2-11}
s_3 1 1 1 1 1 \\
\cline{2-11}
s_1 1 1 1 1 \\
\cline{2-11}
"1" 1 1 \\
\cline{2-11}
\end{array}$$
Строка s4 содержит нули только в позициях,
соответствующих
каналам, "участвующим" в ее формировании. Значит, найдено еще одно
ПМВНК {1, 2, 4, 7}. Оно определяет разрез сети с пропускной
способностью d1 + d2 + d4 + d7.
Исключаем s4 из стека. Следующий испытываемый нуль в
строке s3 занимает позицию 8. Формируем новую вершину
стека s5 = s3 $$\vee $$ "8".$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_5 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка s5 содержит нули только в позициях
1, 2, 4, 8.
Следовательно, найдено ПМВНК {1, 2, 4, 8} с пропускной
способностью d1 + d2 + d4 + d8.
Исключаем s5 из стека. Находим, что в s3 все нули
исследованы. Исключаем s3 из стека. В s1 следующий
нуль,
подлежащий испытанию, занимает позицию 7. Формируем новую вершину
стека — строку s6 = s1 $$\vee $$ "7".$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_6 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка s6 не содержит нулей правее позиции
7. Исключаем s6 из
стека.
Следующий испытываемый нуль в s1 занимает позицию 8.
Находим s7 = s1 $$\vee $$ "8"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_7 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка также не содержит нулей правее позиции 8.
Исключаем ее из
стека.
Все нули строки s1 испытаны. Исключаем s1 из стека.
В стеке
остается лишь строка "1".
Следующий испытываемый нуль в строке "1" занимает позицию 3.
Формируем новую вершину стека — строку s8 = "1" $$\vee $$ "3"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_8 1 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка s8 не содержит нулей правее позиции
3. Исключаем ее из
стека.
Следующий нуль в первой строке занимает позицию 4. Формируем
новую вершину стека — строку s9 = "1" $$\vee $$ "4"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_9 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка содержит нули не только в позициях 1 и 4.
Первый же
"дополнительный" нуль занимает позицию 2. Это говорит о повторном
формировании уже сформированных ПМВНК. Исключаем строку из стека.
Следующий испытываемый нуль первой строки занимает позицию 6.
Формируем s10 = "1" $$\vee $$ "6"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{10} 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка не содержит "дополнительных" нулей
до позиции 6. Первый
испытываемый нуль занимает позицию 7. Формируем новую вершину
стека s11 = s10 $$\vee $$ "7", а стек принимает
вид$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{11} 1 1 1 1 1 1 1 \\
\cline{2-11}
s_{10} 1 1 1 1 1 1 \\
\cline{2-11}
"1" 1 1 \\
\cline{2-11}
\end{array}$$
Строка s11 содержит нули только в
позициях каналов,
участвующих в ее формировании. Найдено очередное ПМВНК {1, 6, 7} с
потоком d1 + d6 +d7.
Исключаем s11 из стека. Следующий испытываемый нуль
в s10 занимает позицию 8. Формируем s12 = s10 $$\vee $$ "8".$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{12} 1 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка определяет очередное ПМВНК {1, 6,
8} с потоком d1 +
d6 +d8.
Исключаем s12 из стека. Строка s10 испытана
полностью.
Исключаем ее из стека. Следующий испытываемый нуль в строке "1"
занимает позицию 7. Формируем строку s13 = "1" $$\vee $$ "7"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{13} 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Она не содержит "дополнительные" нули
правее позиции 7.
Исключаем строку из стека.
Испытание нуля в позиции 8 первой строки приводит к тому же результату.
Все комбинации каналов с участием канала 1 исчерпаны. Выбираем
следующий канал. Т.е. загружаем в стек вторую строку матрицы S.
Первый
нуль в позиции, не меньшей 2, занимает позицию 3. Формируем новую
вершину стека s14 = "2" $$\vee $$ "3"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{14} 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Первый нуль правее позиции 3 в
строке s14 занимает позицию
5. Формируем s15 = s14 $$\vee $$ "5"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{15} 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка содержит нули только в позициях 2, 3, 5. Это
определяет
ПМВНК {2, 3, 5} с потоком d2 + d3 + d5.
Следующий нуль в строке s14 занимает позицию 9.
Формируем s16 = s14 $$\vee $$ "9"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{16} 1 1 1 1 1 1 1
\\
\cline{2-11}
\end{array}$$
Строка содержит нули только в позициях 2, 3, 9. Это
определяет
ПМВНК {2, 3, 9} с потоком d2 + d3 + d9.
Формируем s17 = "2" $$\vee $$ "4"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{17} 1 1 1 \\
\cline{2-11}
\end{array}$$
Первый "дополнительный" нуль занимает
позицию 5. Формируем s18 = s17 $$\vee $$ "5"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{18} 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка s18 содержит нули не только в
позициях 2, 4, 5. Первый
"дополнительный" нуль занимает позицию 7. Формируем s19 =
s18
$$\vee $$ "7" = "2" $$\vee $$ "4" $$\vee $$ "5" $$\vee $$ "7"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{19} 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка содержит нули только в позициях 2, 4, 5, 7, что
определяет
ПМВНК {2, 4, 5, 7} с потоком d2 + d4 + d5 +
d7.
Следующий (последний) "дополнительный" нуль
строки s18 занимает позицию 8. Формируем s20 = s18
$$\vee $$ "8"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{20} 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
и находим ПМВНК {2, 4, 5, 8} с
потоком d2 + d4 + d5 + d8.
Следующий нуль в строке s17 занимает позицию 7.
Формируем s21 = s17 $$\vee $$ "7"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{21} 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Единственный нуль правее позиции 7 занимает позицию 9.
Формируем s22 = s21 $$\vee $$ "9"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{22} 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
и получаем следующее ПМВНК {2, 4, 7, 9} с
потоком d2 + d4 + d7 +
d9.
Следующий нуль в строке s17 занимает позицию 8.
Формируем s23 = s17 $$\vee $$ "8"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{23} 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Единственный "дополнительный" нуль, правее
позиции 8, занимает
позицию 9. Формируем s24 = s23 $$\vee $$ "9"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{24} 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Т.к. позиции нулей совпадают с позициями всех каналов,
участвующих
в комбинации, получаем ПМВНК {2, 4, 8, 9}, определяющее разрез с
потоком d2 + d4 + d8 + d9.
Последний "дополнительный" нуль
в s17 занимает позицию
9. Формируем s25 = s17 $$\vee $$ "9"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{25} 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка содержит нули не только в позициях 2, 4, 9.
Однако все
"дополнительные" нули занимают позиции левее позиции 9. Это говорит
о повторном нахождении ПМВНК.
Возвращаемся к анализу второй строки матрицы S. Следующий
нуль этой строки занимает позицию 5. Формируем s26 = "2" $$\vee $$ "5"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{26} 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Первый "дополнительный" нуль правее
позиции 5 занимает
позицию 7. Формируем s27 = s26 $$\vee $$ "7"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{27} 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Наличие "дополнительных" нулей только
левее позиции 7 говорит о
повторном нахождении ПМВНК.
Второй, последний, "дополнительный" нуль в
строке s26,
правее позиции 5, занимает позицию 8. Его анализ также приводит к
повторному нахождению ПМВНК.
Следующий нуль второй строки матрицы S занимает позицию 7.
Формируем s28 = "2" $$\vee $$ "7"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{28} 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Первый "дополнительный" нуль в этой
строке, правее позиции 7,
занимает позицию 9. Формируем s29 = s28 $$\vee $$ "9"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{29} 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка не содержит нули правее позиции 9, но содержит
нули левее
этой позиции. Это значит, что мы на пути повторного формирования уже
найденного ПМВНК ( {2, 4, 7, 9} ).
Следующий нуль второй строки S занимает позицию 8.
Формируем s30 = "2" $$\vee $$ "8"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{30} 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Нуль в позиции 9 — правее позиции 8. Однако ситуация
аналогична
рассмотренной на шаге 23.
Вторая строка исчерпана. Переходим к анализу третьей строки
матрицы S. Правее третьей позиции в этой строке есть нуль в
позиции 5.
Формируем s31 = "3" $$\vee $$ "5"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{31} 1 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка не содержит "дополнительных" нулей
правее позиции 5,
хотя содержит нули не только в позициях 3 и 5. Значит, мы не получим
новых ПМВНК.
Следующий (последний) нуль в третьей строке занимает позицию 9.
Формируем s32 = "3" $$\vee $$ "9"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{32} 1 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Исключаем строку из стека, т.к. она имеет нули только
левее позиции
9.
Анализируем четвертую строку и убеждаемся, что новых ПМВНК мы не получим.
Анализируем пятую строку, Она содержит нули правее пятой
позиции - в позициях 6, 7, 8, 10. Формируем s33 = "5" $$\vee $$ "6"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{33} 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Первый "дополнительный" нуль, правее
позиции 6,
занимает позицию 7. Формируем s34 = s33 $$\vee $$ "7"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{34} 1 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка содержит нули только в позициях 5, 6, 7. Найдено
ПМВНК {5, 6, 7} с потоком d5 + d6 + d7.
Следующий нуль — в позиции 8. Формируем s35 =
s33 $$\vee $$ "8"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{35} 1 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка содержит нули только в позициях 5, 6, 8, что
соответствует
ПМВНК {5, 6, 8} с потоком d5 + d6 + d8.
Анализ позиций 7 и 8 пятой строки приводит к повторному нахождению ПМВНК.
Последний "дополнительный" нуль пятой строки занимает
позицию 10. Формируем s36 = "5" $$\vee $$ "10"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{36} 1 1 1 1 1 1 1 1
\\
\cline{2-11}
\end{array}$$
Строка содержит нули в позициях 5 и 10. Найдено
очередное ПМВНК {5, 10} с потоком d5 + d10.
Переходим к анализу шестой строки матрицы S. Она содержит
нули правее шестой позиции в позициях 7, 8, 9. Формируем s37 = "6"
$$\vee $$ "7"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{37} 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Правее седьмой позиции "дополнительный"
нуль занимает позицию
9. Формируем s38 = s37 $$\vee $$ "9"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{38} 1 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Строка содержит нули в позициях 6, 7, 9. Найдено
ПМВНК {6, 7, 9} с потоком d6 + d7 + d9.
Формируем s39 = "6" $$\vee $$ "8"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{39} 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Правее восьмой позиции "дополнительный"
нуль занимает позицию
9. Как и на предыдущем шаге, находим следующее ПМВНК {6, 8, 9} с
потоком d6 + d8 + d9.
34. Можно убедиться в том, что анализ седьмой и восьмой строк не приведет к получению новых ПМВНК.
Девятая строка содержит единственный нуль правее позиции 9 - в
позиции 10. Формируем s40 = "9" $$\vee $$ "10"$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}
s_{40} 1 1 1 1 1 1 1 1 \\
\cline{2-11}
\end{array}$$
Найдено последнее ПМВНК {9, 10} с
потоком d9 +
d10.
Предпочтительным способом распараллеливания здесь является
распараллеливание по информации. Наиболее простая реализация его может
быть основана на распределении между процессорами или станциями
локальной сети строк матрицы S. И здесь самую простую реализацию
предлагает принцип
Здесь может быть эффективен тот же принцип, который используется
при обработке баз данных, баз знаний и
Его реализация может быть следующей.
В соответствии с S также упорядочено.
Первоначально первый процессор выбирает для обработки и метит первую
строку, второй — вторую и т.д.
По мере освобождения каждый процессор обращается к матрице S и
выбирает первую из неотмеченных строк. Для согласованного обращения к S
организуется синхронизация с помощью семафора методом взаимного
исключения.
Сеть, в т.ч. транспортная, представляет собой
Рассмотренные параллельные методы решения некоторых задач на транспортных сетях ориентированы на "прорыв в размерности", на выход на большие размерности задач, на задачи высокой, даже — экспоненциальной сложности. Только параллельные вычислительные системы могут решать такие задачи. Здесь очень важна концепция перспективных вычислительных средств: только ли разработка супер-ЭВМ призвана удовлетворить высокие требования по производительности? Не находятся ли на наших столах распределенные вычислительные комплексы РС, объединенные в локальные сети на основе современных, уже достаточно оперативных сетевых технологий? Именно для ответа на эти вопросы и должны критически перерабатываться и вновь создаваться параллельные алгоритмы решения сложных задач.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.