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

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

Номер 1

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

Ответ:

(1) все ограничения и условия записываются в виде линейных уравнений действительных и потенциальных граней многогранника допустимых решений. Из полученной системы процессоры формируют очередные комбинации по n (размерность пространства) уравнений и решают образовавшуюся систему. Если решение существует и удовлетворяет всем ограничениям и условиям, то для найденной вершины находится значение целевой функции. Фиксируется вершина с максимальным значением этой функции

(2) все ограничения записываются в виде линейных уравнений граней многогранника допустимых решений. Из полученной системы процессоры формируют очередные комбинации по п (размерность пространства) уравнений и решают образовавшуюся систему. Если решение существует и удовлетворяет всем ограничениям и условиям, то для найденной вершины находится значение целевой функции. Фиксируется вершина с максимальным значением этой функции

(3) все ограничения и условия записываются в виде линейных уравнений потенциальных граней многогранника допустимых решений. Из полученной системы процессоры формируют очередные комбинации по п (размерность пространства) уравнений и решают образовавшуюся систему. Если решение существует и удовлетворяет всем ограничениям и условиям, то для найденной вершины находится значение целевой функции. Фиксируется вершина с максимальным значением этой функции

Номер 2

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

Ответ:

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

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

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

Номер 3

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

Ответ:

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

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

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

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

Номер 2

В "плоской" задаче линейного программирования многогранник допустимых решений имеет вид, представленный на рисунке. Его ребра обусловлены ограничениями и условиями. Ограничения, при замене указанных в них неравенств на равенство, порождают границы q, обозначающие уравнения прямой. Показана прямая - возможный график целевой функции при заданном или испытываемом еезначении. Параллельное перемещение графика целевой функции в сторону еевозрастания показано стрелкой. Найдите графически решение задачи линейного программирования

Ответ:

(1) решение (максимум значения целевой функции) достигается в точке С

(2) решение - в точке А

(3) решение достигается на всем отрезке [C, D]

Номер 4

В "плоской" задаче линейного программирования многогранник допустимых решений имеет вид, представленный на рисунке. Его ребра обусловлены ограничениями и условиями. Ограничения, при замене указанных в них неравенств на равенство, порождают границы q, обозначающие уравнения прямой. Показана прямая - возможный график целевой функции при заданном или испытываемом еезначении. Параллельное перемещение графика целевой функции в сторону еевозрастания показано стрелкой. Найдите графически решение задачи линейного программирования

Ответ:

(1) решение достигается в точке D

(2) решение достигается на отрезке [A, B]

(3) решение достигается в точке С

Номер 3

В "плоской" задаче линейного программирования многогранник допустимых решений имеет вид, представленный на рисунке. Его ребра обусловлены ограничениями и условиями. Ограничения, при замене указанных в них неравенств на равенство, порождают границы q, обозначающие уравнения прямой. Показана прямая - возможный график целевой функции при заданном или испытываемом еезначении. Параллельное перемещение графика целевой функции в сторону еевозрастания показано стрелкой. Найдите графически решение задачи линейного программирования

Ответ:

(1) решение достигается в точке А

(2) решение достигается в точке Е

(3) решение достигается на отрезке [A, E]

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

Номер 1

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

Ответ:

(1) 15 систем, решение определяется системой files

(2) 10 систем, решение определяется системой files

(3) 5 систем, решение определяется системой files

Номер 2

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

Ответ:

(1) 10 систем, решение определяется системой files

(2) 5 систем, решение определяется системой files

(3) 10 систем, решение определяется системой files

Номер 3

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

Ответ:

(1) 15 систем, решение определяется системой files

(2) 10 систем, решение определяется системой files

(3) 5 систем, решение определяется системой files

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

Номер 1

Решение задачи линейного программирования найдено в точке А(7,5, 7,5). С помощью параллельного переноса целевой функции Z = ax + by вглубь многогранника допустимых решений "захватите" точку с целыми координатами (решите задачу целочисленного линейного программирования), в которой значение целевой функции максимально. а = 5, b = 4 (см. Вариант 1 на рисунке ниже)

Ответ:

(1) x=7, y=7

(2) x=2, y=8

(3) x=8, y=6

Номер 2

Решение задачи линейного программирования найдено в точке А(7,5, 7,5). С помощью параллельного переноса целевой функции Z = ax + by вглубь многогранника допустимых решений "захватите" точку с целыми координатами (решите задачу целочисленного линейного программирования), в которой значение целевой функции максимально. а = 9, b = 2 (см. Вариант 2 на рисунке ниже)

Ответ:

(1) x=7, y=7

(2) x=8, y=5

(3) x=8, y=4

Номер 3

Решение задачи линейного программирования найдено в точке А(7,5, 7,5). С помощью параллельного переноса целевой функции Z = ax + by вглубь многогранника допустимых решений "захватите" точку с целыми координатами (решите задачу целочисленного линейного программирования), в которой значение целевой функции максимально. а = 1, b = 2 (см. Вариант 3 на рисунке ниже)

Ответ:

(1) x=7, y=7

(2) x=8, y=7

(3) x=7, y=8

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