Ответы: Контрольные работы прошлых лет

// ======================================== ======================================== ======================================== ====================================

Контрольная работа 1

Может ли матрица размером 3х3 иметь 7 седловых точек?

Может ли матрица 4х4 иметь 11 седловых точек?

имеет ли функция ??? на единичном квадрате ??? седловую точку? Если да, то найти все седловые точки.

Найти решение в смешанных стратегиях в игре с платежной матрицей ???

Найти все оптимальные стратегии первого игрока в игре с платежной матрицей ???

Найти все ситуации равновесия в биматричной игре: ??? ???

// ======================================== ======================================== ======================================== ====================================

Контрольная работа 2 Билет 4

1. Дана сеть G с дугами (1, 2), (1, 3), (1,4), (1, 5), (2, 5), (2,6), (2, 8), (3, 2), (3, 6), (4, 3), (4, 6), (4, 7), (5, 8), (6, 8), (7, 8), пропускные способности которых равны соответственно 3, 3, 4, 3, 2, 2, 4, 2, 3, 3, 3, 3, 4, 4, 4.

А. Найти максимальный поток из узла 1 в узел 8 и его величину с помощью алгоритма Форда-Фалкерсона. В качестве начального взять нулевой поток. Для каждой итерации указать увеличивающий путь и величину увеличения потока.

B. Найти максимальный поток из узла 1 в узел 8 и его величину с помощью алгоритма Карзанова. В качестве начального взять нулевой поток. Для каждого этапа указать сеть G(f), слоистую сеть G*(f) и тупиковый поток в ней.

C. Построить минимальный разрез в сети G.

2. Дана сеть G с дугами (0, 1), (0,2), (1,2), (2, 1), (1, 3), (2, 3), (3, 0), параметры которых равны соответственно (1, 8, 1), (1, 8, 1), (2, 3, 1), (0, 3, 0), (1, 6, 2), (1,4, 1), (3, 5, 1) (дуга (i,j) имеет параметры Lij, Uij, cij, где Lij - нижняя граница потока по дуге, Uij - верхняя граница потока по дуге, с,, - стоимость единицы потока по дуге). С помощью алгоритма дефекта найти циркуляцию минимальной стоимости в сети G. В качестве начального взять нулевой поток. Для каждой итерации указать поток по каждой дуге, наличие или отсутствие ее дефекта, возможные изменения потока по ней, узловые числа. При изменении потоков указать соответствующий цикл и величину изменения потока, а при изменении узловых чисел привести соответствующие вычисления.

3. Даны вычислительная система, состоящая из двух идентичных процессоров, и четыре работы со следующими

характеристиками:

Работа I bi fi ti

1 0 5 4

2 1 6 4

3 0 8 2

4 0 8 6

(bi, fi, ti - соответственно начальный директивный срок, конечный директивный срок и длительность выполнения работы i). Определить, существует ли допустимое расписание с прерываниями и найти его, если оно существует. Издержками на прерывания и переключения пренебречь. Свести указанную задачу к задаче о максимальном потоке в сети. При нахождении максимального потока привести все вычисления.

// ======================================== ======================================== ======================================== ====================================

Контрольная работа 2 Билет 3

1. Дана сеть G с дугами (1, 2), (1, 3), (1,4), (2, 5), (2, 7), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (4, 7), (4, 8), (5, 8), (6, 8), (7, 6), (7, 8), пропускные способности которых равны соответственно 6, 6, 6, 3, 3, 3, 2, 3, 1, 3, 4, 6, 4, 6, 1, 4.

A. Найти максимальный поток из узла 1 в узел 8 и его величину с помощью алгоритма Форда-Фалкерсона. В качестве начального взять нулевой поток. Для каждой итерации указать увеличивающий путь и величину увеличения потока.

B. Найти максимальный поток из узла 1 в узел 8 и его величину с помощью алгоритма Карзанова. В качестве начального взять нулевой поток. Для каждого этапа указать сеть G(f), слоистую сеть G*(f) и тупиковый поток в ней.

C. Построить минимальный разрез в сети G.

2. Дана сеть G с дугами (0, 1), (0,2), (1,2), (2, 1), (1, 3), (2, 3), (3, 0), параметры которых равны соответственно (0, 5, 2), (2, 5, 2), (1, 1, 0), (1, 2, 0), (2, 6, 2), (3, 6, 1), (7, 9, 0) (дуга (i,j) имеет параметры Lij, Uij, cij, где Lij - нижняя граница потока по дуге, Uij - верхняя граница потока по дуге, с,, - стоимость единицы потока по дуге). С помощью алгоритма дефекта найти циркуляцию минимальной стоимости в сети G. В качестве начального взять нулевой поток. Для каждой итерации указать поток по каждой дуге, наличие или отсутствие ее дефекта, возможные изменения потока по ней, узловые числа. При изменении потоков указать соответствующий цикл и величину изменения потока, а при изменении узловых чисел привести соответствующие вычисления.

Даны вычислительная система, состоящая из двух идентичных процессоров, и четыре работы со следующими

характеристиками:

Работа I bi fi ti

1 1 6 3

2 1 5 3

3 0 6 3

4 0 4 3

(bi, fi, ti - соответственно начальный директивный срок, конечный директивный срок и длительность выполнения работы i). Определить, существует ли допустимое расписание с прерываниями и найти его, если оно существует. Издержками на прерывания и переключения пренебречь. Свести указанную задачу к задаче о максимальном потоке в сети. При нахождении максимального потока привести все вычисления.

// ======================================== ======================================== ======================================== ====================================

Контрольная работа 2 Билет 2

1. Дана сеть G с дугами (1, 2), (I, 3), (1,4), (2, 3), (2, 5), (2,6), (2, 8), (3, 6), (3, 7), (4, 6), (4, 7), (5, 8), (6, 5), (6, 8), (7, 8), пропускные способности которых равны соответственно 3, 4, 5, 1,3, 1, 2, 2, 3, 4, 2, 5, 2, 4, 2.

A. Найти максимальный поток из узла 1 в узел 8 и его величину с помощью алгоритма Форда-Фалкерсона. В качестве начального взять нулевой поток. Для каждой итерации указать увеличивающий путь и величину увеличения потока.

B. Найти максимальный поток из узла 1 в узел 8 и его величину с помощью алгоритма Карзанова. В качестве начального взять нулевой поток. Для каждого этапа указать сеть G(f), слоистую сеть G*(f) и тупиковый поток в ней.

C. Построить минимальный разрез в сети G.

2. Дана сеть G с дугами (0, 1), (0,2), (1,2), (2, 1), (1, 3), (2, 3), (3, 0), параметры которых равны соответственно (0, 6, 1), (0, 8, 2), (1, 3, 1), (1, 3, 1), (2, 6, 3), (2, 5, 4), (4, 5, 1) (дуга (i,j) имеет параметры Lij, Uij, cij, где Lij - нижняя граница потока по дуге, Uij - верхняя граница потока по дуге, с,, - стоимость единицы потока по дуге). С помощью алгоритма дефекта найти циркуляцию минимальной стоимости в сети G. В качестве начального взять нулевой поток. Для каждой итерации указать поток по каждой дуге, наличие или отсутствие ее дефекта, возможные изменения потока по ней, узловые числа. При изменении потоков указать соответствующий цикл и величину изменения потока, а при изменении узловых чисел привести соответствующие вычисления.

3. Даны вычислительная система, состоящая из двух идентичных процессоров, и четыре работы со следующими

характеристиками:

Работа I bi fi ti

1 0 1 5

2 1 4 2

3 0 7 5

4 2 5 2

(bi, fi, ti - соответственно начальный директивный срок, конечный директивный срок и длительность выполнения работы i). Определить, существует ли допустимое расписание с прерываниями и найти его, если оно существует. Издержками на прерывания и переключения пренебречь. Свести указанную задачу к задаче о максимальном потоке в сети. При нахождении максимального потока привести все вычисления.

// ======================================== ======================================== ======================================== ====================================

Контрольная работа 2 Билет 1

1. Дана сеть G с дугами (1, 2), (1, 3), (1,4), (2, 3), (2, 5), (2,6), (3, 5), (3, 6), (3, 7), (4, 3), (4, 5), (4, 7), (5, 8), (6, 8), (7, 8), пропускные способности которых равны соответственно 2, 4, 6, 1, 1, 1, 2, 2, 2, 1, 3, 3, 5, 3, 4.

A. Найти максимальный поток из узла 1 в узел 8 и его величину с помощью алгоритма Форда-Фалкерсона. В качестве начального взять нулевой поток. Для каждой итерации указать увеличивающий путь и величину увеличения потока.

B. Найти максимальный поток из узла 1 в узел 8 и его величину с помощью алгоритма Карзанова. В качестве начального взять нулевой поток. Для каждого этапа указать сеть G(f), слоистую сеть G*(f) и тупиковый поток в ней.

C. Построить минимальный разрез в сети G.

2. Дана сеть G с дугами (0, 1), (0,2), (1,2), (2, 1), (1, 3), (2, 3), (3, 0), параметры которых равны соответственно (2, 4, 2), (2, 4, 5), (0, 1, 1), (0, 1, 1), (3, 4, 3), (1, 2, 6), (3, 4, 0) (дуга (i,j) имеет параметры Lij, Uij, cij, где Lij - нижняя граница потока по дуге, Uij - верхняя граница потока по дуге, с,, - стоимость единицы потока по дуге). С помощью алгоритма дефекта найти циркуляцию минимальной стоимости в сети G. В качестве начального взять нулевой поток. Для каждой итерации указать поток по каждой дуге, наличие или отсутствие ее дефекта, возможные изменения потока по ней, узловые числа. При изменении потоков указать соответствующий цикл и величину изменения потока, а при изменении узловых чисел привести соответствующие вычисления.

http://esyr.org/wiki/%D0%A2%D0%B8%D0%B3% D1%80%D1%8B%2C_%D0%BA%D0%BE%D0%BD%D1%82% D1%80%D0%BE%D0%BB%D1%8C%D0%BD%D0%B0%D1%8 F_1