Для студентов МГУ им. Ломоносова 11 семестрa по предмету Теория игр и исследование операций Контрольные работы прошлых летКонтрольные работы прошлых лет 2020-08-25 СтудИзба

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

Описание

Описание файла отсутствует

Список файлов в архиве

2006 Контрольные работы 1_ 2_ 3

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

Контрольная работа 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. В качестве начального взять нулевой поток. Для каждой итерации указать поток по каждой дуге, наличие или отсутствие ее дефекта, возможные изменения потока по ней, узловые числа. При изменении потоков указать соответствующий цикл и величину изменения потока, а при изменении узловых чисел привести соответствующие вычисления.

2013 esyr Разбор контрольной работы

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

Комментарии

Сопутствующие материалы
Дата публикации 25 августа 2020 в 17:20
Рейтинг -
0
0
0
0
0
Автор Koala (- из 5)
Цена Бесплатно
Скачивания 0
Просмотры 18
Размер 23,3 Mb
Безопасность Файл был вручную проверен администрацией в том числе и на вирусы
Поделитесь ссылкой:
Свежие статьи
Популярно сейчас