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

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

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

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

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

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

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

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

Z = c11 x11 + c12 x12 + c21 x21 + c22 x22→​ min 

при ограничениях

x11+x12=a1x21+x22=a2x11+x21=b1x12+x22=b2

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

y1	+y2		=a1
		y3+y4	=a2
y1		+y3	=b1
y1			=0
	y2		=0
		y3	=0
		y4	=0

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

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

Z = c11 x11 + c12 x12 + c21 x21 + c22 x22→​ min 

при ограничениях

x11+x12=a1x21+x22=a2x11+x21=b1x12+x22=b2

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

y1	+y2		=a1
		y3+y4	=a2
y1		+y3	=b1
y1			=0
	y2		=0
		y3	=0
		y4	=0

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

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

Z = c11 x11 + c12 x12 + c21 x21 + c22 x22→​ min 

при ограничениях

x11+x12=a1x21+x22=a2x11+x21=b1x12+x22=b2

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

y1	+y2		=a1
		y3+y4	=a2
y1		+y3	=b1
y1			=0
	y2		=0
		y3	=0
		y4	=0

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

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