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

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

(Отметьте один правильный вариант ответа.)

Варианты ответа

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

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

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

Похожие вопросы

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

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

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

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

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

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

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

Обсудите метод нахождения опорного плана решения задачи линейного программирования. Какое основное предположение лежит в основе метода?

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