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

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

Номер 1

Запишите параметрическое уравнение выпуклого многогранника допустимых решений задачи нелинейного программирования с помощью координат всех его вершин. A(40, 10, 12), B(0, 20, 10), C(20, 0, 16), D(50, 16, 0)

Ответ:

(1) x=40k₁+20k₃+50k₄ y=10k₁+20k₂+16k₄ z=12k₁+10k₂+16k₃ 0≤k₁,k₂,k₃,k₄≤1

(2) x=40k₁+20k₃+50k₄ y=10k₁+20k₂+16k₄ z=12k₁+10k₂+16k₃ 0≤k₁,k₂,k₃,k₄≤1, k₁+k₂+k₃+k₄=1

(3) x=40k₁+20k₃+50k₄ y=10k₁+20k₂+16k₄ z=12k₁+10k₂+16k₃ k₁+k₂+k₃+k₄=1

Номер 2

Запишите параметрическое уравнение выпуклого многогранника допустимых решений задачи нелинейного программирования с помощью координат всех его вершин. A(0, 12, 20), B(0, 20, 10), C(12, 16, 3), D(20, 0, 10)

Ответ:

(1) x=12k₃+20k₄ y=12k₁+20k₂+16k₃ z=20k₁+10k₂+3k₃+10k₄ 0≤k₁,k₂,k₃,k₄≤1, k₁+k₂+k₃+k₄=1

(2) x=12k₃+20k₄ y=12k₁+20k₂+16k₃ z=20k₁+10k₂+3k₃+10k₄ 0≤k₁,k₂,k₃,k₄≤1,

(3) x=12k₃+20k₄ y=12k₁+20k₂+16k₃ z=20k₁+10k₂+3k₃+10k₄ k₁+k₂+k₃+k₄=1

Номер 3

Запишите параметрическое уравнение выпуклого многогранника допустимых решений задачи нелинейного программирования с помощью координат всех его вершин. A(5, 12, 8), B(0, 16, 12), C(20, 16, 7), D(0, 4, 18)

Ответ:

(1) x=5k₁+20k₃ y=12k₁+16k₂+16k₃+4k₄ z=8k₁+12k₂+16k₃+18k₄ 0≤k₁,k₂,k₃,k₄≤1, k₁+k₂+k₃+k₄=1

(2) x=5k₁+20k₃ y=12k₁+16k₂+16k₃+4k₄ z=8k₁+12k₂+16k₃+18k₄ 0≤k₁,k₂,k₃,k₄≤1,

(3) x=5k₁+20k₃ y=12k₁+16k₂+16k₃+4k₄ z=8k₁+12k₂+16k₃+18k₄ k₁+k₂+k₃+k₄=1

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

Номер 1

Даны линейные уравнения прямых - граней выпуклого многогранника R допустимых решений, на котором алгоритмически определена некоторая функция f(x, y). Составьте план расчета таблицы значений этой функции методом сеток. Сетку с шагом h формируйте с помощью параметрического описания R
 
     -x+2y-10=0
      x+y-8=0

Ответ:

(1) вершины многогранника R допустимых решений:О(0, 0),A(0,5),B(2,5),C(7,0). Описание R

`x=0k₁+0k₂+2k₃+7k₄`				`0≤k₁,k₂, k₃, k₄≤1`
`y=0k₁+5k₂+6k₃+0k₄`				`k₁+ k₂= k₃+ k₄=1`

Перебор точек R

Точки	`k₁`	`k₂`	`k₃`	`k₄`
0	0	0	0	1
1	`h`	0	0	`1-h`
2	`h`	`h`	0	`1-2h`
3	`h`	`h`	`h`	`1-3h`
4	`2h`	`h`	`h`	`1-4h`
и т.д.

(2) вершины многогранника R допустимых решений:О(0, 0), A(0, 5), B(2, 5), C(7, 0) Описание R:

`x=0k₁+0k₂+2k₃+7k₄`				`0≤k₁,k₂,k₃,k₄≤1`
`y=0k₁+5k₂+6k₃+0k₄`

Перебор точек R

Точки	`k₁`	`k₂`	`k₃`	`k₄`
0	0	0	0	0
1	`h`	0	0	0
2	`2h`	0	0	0
..........
`N`	`Nh`	0	0	0
`N=1`	0	`h`	0	0
и т.д.

(3) вершины многогранника R допустимых решений:О(0, 0), A(0, 5), B(2, 5), C(7, 0) Описание R:

`x=0k₁+0k₂+2k₃+7k₄`				`0≤k₁,k₂,k₃,k₄≤1`
`x=0k₁+5k₂+6k₃+0k₄`				`k₁+k₂+k₃+k₄=1`

Перебор точек R

Точки	`k₁`	`k₂`	`k₃`	`k₄`
0	0	0	0	1
1	`h`	0	0	`1-h`
2	`2h`	0	0	`1-2h`
..........
`N`	`Nh`	0	0	`1-Nh`
`N+1`	0	`h`	0	`1-h`
и т.д.

Номер 2

Даны линейные уравнения прямых - граней выпуклого многогранника R допустимых решений, на котором алгоритмически определена некоторая функция f(x, y). Составьте план расчета таблицы значений этой функции методом сеток. Сетку с шагом h формируйте с помощью параметрического описания R
     -x+3y-14=0
      x=y-6=0

Ответ:

(1) вершины многогранника R допустимых решений: О(0, 0), A(0, 6), B(1, 5), C(6, 0) Описание R

`x=0k₁+0k₂+1k₃+6k₄`				`0≤k₁,k₂,k₃,k₄≤1`
`y = 0k₁+6k₂+5k₃+0k₄`				`k₁+k₂+k₃+k₄=1`

Перебор точек R

Точки	`k₁`	`k₂`	`k₃`	`k₄`
0	0	0	0	1
1	`h`	0	0	`1-h`
2	`2h`	0	0	`1-2h`
..........
`N`	`Nh`	0	0	`1-Nh`
`N+1`	0	`h`	0	`1-h`
и т.д.

(2) вершины многогранника R допустимых решений:О(0, 0), A(0, 6), B(1, 5), C(6, 0) Описание R

`x=0k₁+0k₂+1k₃+6k₄`				`0≤k₁,k₂,k₃,k₄≤1`
`y = 0k₁+ 6k₂+ 5k₃+0k₄`

Перебор точек R

Точки	`k₁`	`k₂`	`k₃`	`k₄`
0	0	0	0	0
1	`h`	0	0	0
2	`2h`	0	0	0
..........
`N`	`Nh`	0	0	0
`N+1`	0	`h`	0	0
и т.д.

(3) вершины многогранника R допустимых решений:О(0, 0), A(0, 6), B(1, 5), C(6, 0) Описание R

`x=1k₃+6k₄`				`0≤k₂,k₃,k₄≤1`
`y=6k₂+5k₃+0k₄`	`k₂+k₃+k₄=1`

Перебор точек R

Точки	`k₂`	`k₃`	`k₄`
0	0	0	1
1	`h`	0	`1-h`
2	`2h`	0	`1-2h`
..........
`N`	`Nh`	0	`1-Nh`
`N+1`	0	`h`	`1-h`
и т.д.

Номер 3

Даны линейные уравнения прямых - граней выпуклого многогранника R допустимых решений, на котором алгоритмически определена некоторая функция f(x, y). Составьте план расчета таблицы значений этой функции методом сеток. Сетку с шагом h формируйте с помощью параметрического описания R
        -x+3y-14=0
         x=y-6=0

Ответ:

(1) вершины многогранника R допустимых решений: A(0, 1), B(0, 10), C(10, 0), D(1, 0) Описание R

`x=0k₁+0k₂+10k₃+1k₄`				`0≤k₁,k₂,k₃,k₄≤1`
`y=1k₁+10k₂+0k₃+0k₄`				`k₁+k₂+k₃+k₄=1`

Перебор точек R

Точки	`k₁`	`k₂`	`k₃`	`k₄`
0	0	0	0	1
1	`h`	0	0	`1-h`
2	`2h`	0	0	`1-2h`
..........
`N`	`Nh`	0	0	`1-Nh`
`N+1`	0	`h`	0	`1-h`
и т.д.

(2) вершины многогранника R допустимых решений: A(0, 1), B(0, 10), C(10, 0), D(1, 0) Описание R

`x=0k₁+0k₂+10k₃+1k₄`				`0≤k₁,k₂,k₃,k₄≤1`
`y=1k₁+10k₂+0k₃+0k₄`

Перебор точек R

Точки	`k₁`	`k₂`	`k₃`	`k₄`
0	0	0	0	1
1	`h`	0	0	`1-h`
2	`h`	`h`	0	`1-2h`
3	`h`	`h`	`h`	`1-3h`
`4`	`2h`	`h`	`h`	`1-4h`
и т.д.

(3) вершины многогранника R допустимых решений: A(0, 1), B(0, 10), C(10, 0), D(1, 0) Описание R

`x=10k₃+1k₄`				`0≤k₁,k₂,k₃,k₄≤1`
`y=1k₁+10k₂`				`k₁+ k₂+ k₃+ k₄=1`

Перебор точек R

Точки	`k₁`	`k₂`	`k₃`	`k₄`
0	0	0	0	1
1	`h`	0	0	0
2	`2h`	0	0	0
..........
`N`	`Nh`	0	0	0
`N+1`	0	`h`	0	0
и т.д.

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

Номер 1

Опишите прямоугольник сетки, включающий данную фигуру

Ответ:

(1) 1≤x≤11 1≤y≤7

(2) 1≤x≤11 1≤y≤11

(3) 1≤x≤7 1≤y≤11

Номер 2

Опишите прямоугольник сетки, включающий данную фигуру

Ответ:

(1) 2≤x≤11 2≤y≤9

(2) 2≤x≤10 2≤y≤8

(3) 2≤x≤11 2≤y≤8,5

Номер 3

Опишите прямоугольник сетки, включающий данную фигуру

Ответ:

(1) 1≤x≤9 1≤y≤8

(2) 1,5≤x≤9 1,3≤y≤7,6

(3) 1,2≤x≤9 1,4≤y≤7,5

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

Номер 1

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

Ответ:

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

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

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

Номер 2

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

Ответ:

(1) в n-мерном пространстве (n>3) не определено понятие угла, а косинус, определяемый с помощью скалярного произведения, не является монотонно возрастающей функцией меры

(2) в n-мерном пространстве (n>3) не видны углы, а косинус, определяемый на абстрактном уровне с помощью скалярного произведения, ни на каком интервале изменения не может является функцией меры

(3) в n-мерном пространстве (n>3) не определено понятие угла, а косинус, определяемый с помощью скалярного произведения нормалей к действительным граням многогранника допустимых решений, не является монотонно возрастающей функцией меры

Номер 3

Обсудите метод нахождения опорного плана решения задачи линейного программирования. При каких предположениях решается проблема нахождения хотя бы одной вершины многогранника допустимых решений с помощью косинусов «углов» между нормалями к граням, образующим эту вершину?

Ответ:

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

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

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

Номер 4

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

Ответ:

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

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

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

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