Параллельное программирование

Упражнение 1:

Номер 1

В пунктах А₁ и А₂ производится продукт в объемах а₁ и а₂ единиц. В пунктах В₁ и В₂ этот продукт потребляется в объемах b₁ и b₂. Из каждого пункта производства возможна транспортировка в любой пункт потребления. Транспортные издержки по перевозке из пункта A_iв пункт B_j равны c_ij. 
Необходимо решить транспортную задачу, т.е. найти такой план перевозок, при котором запросы всех потребителей полностью удовлетворены, весь продукт из пунктов производства вывезен, и суммарные транспортные издержки минимальны.
Формальная постановка задачи: Z = c₁₁ x₁₁ + c₁₂ x₁₂ + c₂₁ x₂₁ + c₂₂ x₂₂→ min  
при ограничениях 
x₁₁+x₁₂=a₁
x₂₁+x₂₂=a₂
x₁₁+x₂₁=b₁
x₁₂+x₂₂=b₂
при условии неотрицательности решения, x_ij≥ 0, и баланса: a₁+a₂=b₁+b₂. Введем сквозную нумерацию переменных и исключим из рассмотрения последнее условие (устраним линейную зависимость уравнений на основе баланса). Система уравнений всех граней (действительных и возможных) многогранника допустимых решений имеет вид:y₁ +y₂ =a₁
y₃+y₄ =a₂
y₁ +y₃ =b₁
y₁ =0
y₂ =0
y₃ =0
y₄ =0

Сколько вариантов решения систем линейных уравнений следует проанализировать при прямом переборе вершин в многограннике допустимых решений? 

a₁=0, a₂=100, b₁=50, b₂=50

Ответ:

(1) 1 вариант

(2) 3 варианта

(3) 2 варианта

Номер 2

В пунктах А₁ и А₂ производится продукт в объемах а₁ и а₂ единиц. В пунктах В₁ и В₂ этот продукт потребляется в объемах b₁ и b₂. 

Из каждого пункта производства возможна транспортировка в любой пункт потребления. Транспортные издержки по перевозке из пункта A_iв пункт B_j равны c_ij. 
Необходимо решить транспортную задачу, т.е. найти такой план перевозок, при котором запросы всех потребителей полностью удовлетворены, весь продукт из пунктов производства вывезен, и суммарные транспортные издержки минимальны.
Формальная постановка задачи: Z = c₁₁ x₁₁ + c₁₂ x₁₂ + c₂₁ x₂₁ + c₂₂ x₂₂→ min  

при ограничениях 
x₁₁+x₁₂=a₁
x₂₁+x₂₂=a₂
x₁₁+x₂₁=b₁
x₁₂+x₂₂=b₂
при условии неотрицательности решения, x_ij≥ 0, и баланса: a₁+a₂=b₁+b₂. Введем сквозную нумерацию переменных и исключим из рассмотрения последнее условие (устраним линейную зависимость уравнений на основе баланса). Система уравнений всех граней (действительных и возможных) многогранника допустимых решений имеет вид:y₁ +y₂ =a₁
y₃+y₄ =a₂
y₁ +y₃ =b₁
y₁ =0
y₂ =0
y₃ =0
y₄ =0

Сколько вариантов решения систем линейных уравнений следует проанализировать при прямом переборе вершин в многограннике допустимых решений? 

a₁=012, a₂=0, b₁=70, b₂=50

Ответ:

(1) 3 варианта

(2) 1 вариант

(3) 2 варианта

Номер 3

В пунктах А₁ и А₂ производится продукт в объемах а₁ и а₂ единиц. В пунктах В₁ и В₂ этот продукт потребляется в объемах b₁ и b₂. 
Из каждого пункта производства возможна транспортировка в любой пункт потребления. Транспортные издержки по перевозке из пункта A_iв пункт B_j равны c_ij. 
Необходимо решить транспортную задачу, т.е. найти такой план перевозок, при котором запросы всех потребителей полностью удовлетворены, весь продукт из пунктов производства вывезен, и суммарные транспортные издержки минимальны.
Формальная постановка задачи: 
Z = c₁₁ x₁₁ + c₁₂ x₁₂ + c₂₁ x₂₁ + c₂₂ x₂₂→ min  при ограничениях 
x₁₁+x₁₂=a₁
x₂₁+x₂₂=a₂
x₁₁+x₂₁=b₁
x₁₂+x₂₂=b₂
при условии неотрицательности решения, x_ij≥ 0, и баланса: a₁+a₂=b₁+b₂. 

Введем сквозную нумерацию переменных и исключим из рассмотрения последнее условие (устраним линейную зависимость уравнений на основе баланса). Система уравнений всех граней (действительных и возможных) многогранника допустимых решений имеет вид:
y₁ +y₂ =a₁
y₃+y₄ =a₂
y₁ +y₃ =b₁
y₁ =0
y₂ =0
y₃ =0
y₄ =0

Сколько вариантов решения систем линейных уравнений следует проанализировать при прямом переборе вершин в многограннике допустимых решений? 
a₁=60, a₂=40, b₁=50, b₂=50

Ответ:

(1) 4 варианта

(2) 6 вариантов

(3) 10 вариантов

Упражнение 5:

Номер 1

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

Ответ:

(1) максимальная пропускная способность сети равна 6

(2) максимальная пропускная способность сети равна 8

(3) максимальная пропускная способность сети равна 12

Номер 2

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

Ответ:

(1) максимальная пропускная способность сети равна 9

(2) максимальная пропускная способность сети равна 10

(3) максимальная пропускная способность сети равна 11

Номер 3

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

Ответ:

(1) максимальная пропускная способность сети равна 11

(2) максимальная пропускная способность сети равна 12

(3) максимальная пропускная способность сети равна 13

Упражнение 6:

Номер 1

Исследуйте идеи, лежащие в основе решения транспортных и сетевых задач. Пусть в транспортной задаче без ограничения пропускной способности коммуникаций mxn – общее число переменных. Сколько возможных вариантов необходимо проанализировать методом прямого перебора?

Ответ:

(1)

(2)

(3)

Номер 2

Исследуйте идеи, лежащие в основе решения транспортных и сетевых задач. Какую стратегию ускоренного параллельного поиска решения транспортной задачи без ограничения пропускной способности коммуникаций целесообразно реализовать в ВС SPMD-архитектуры или в локальной вычислительной сети?

Ответ:

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

(2) монопрограмма по номеру процессора (РС) выбирает очередное ребро, исходящее из первоначально найденной вершины многогранника допустимых решений. Вдоль него ищется смежная вершина с меньшим значением целевой функции. Если на нескольких процессорах поиск закончился успешно, выбирается вершина с минимальным значением целевой функции. Все процессоры приступают к анализу ребер, исходящих из новой вершины. Так – до исчерпания поиска вершин с меньшим значением целевой функции

(3) монопрограмма выбирает очередное ребро, исходящее из первоначально найденной вершины многогранника допустимых решений. Вдоль него ищется смежная вершина с меньшим значением целевой функции. Процессор (РС) с минимальным номером, нашедший такую вершину, вынуждает все процессоры приступить к анализу ребер, исходящих из новой вершины. Так – до исчерпания поиска вершин с меньшим значением целевой функции

Номер 3

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

Ответ:

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

(2) необходимо строить и параллельно обрабатывать два многогранника допустимых решений: для ограничений переменных снизу и сверху

(3) количество испытываемых вариантов поиска решения увеличивается вдвое

Номер 4

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

Ответ:

(1) производится параллельный анализ полных множеств взаимно независимых каналов, образующих сеть

(2) производится параллельный анализ всех возможных множеств взаимно независимых каналов

(3) производится параллельная обработка строк матрицы следования, описывающей сеть

(4) в соответствии с SPMD-технологией, каждый процессор (РС) в соответствии со своим номером выбирает строку матрицы следования и метит еепосле обработки. Затем он выбирает первую из неотмеченных строк и т.д.

y₁	+y₂		=a₁
		y₃+y₄	=a₂
y₁		+y₃	=b₁
y₁			=0
	y₂		=0
		y₃	=0
		y₄	=0

Параллельное программирование - тест 5