1. Метод ветвей и границ, его основные этапы

• Основная задача ветвится на несколько подзадач

• Редукция – сведение задачи к более простой, исключение целочисленного ограничения

• Определение оценок путём вычисления целевой функции

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

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

2. Венгерский метод

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

Среди оставшихся не вычеркнутых ненулевых элементов редуцированной матрицы выбирается наименьший элемент. Он вычитается из всех элементов матрицы и прибавляется ко всем ранее вычеркнутым элементам строк и столбцов. На пересечении вычёркивающих линий это число суммируется дважды. В результате получается новая редуцированная матрица, в которой появляется как минимум 1 дополнительный нулевой элемент.

Суть венгерского метода:

Если из элементов исходной матрицы затрат С вычитать некоторые константы строк и столбцов, то полученные новые элементы преобразованной матрицы не приводят и к изменению оптимального плана.

3. Суть метода идеальной точки

4. Объясните смысл переменной xmj в транспортной модели, если m поставщик - фиктивный

5. Где используется метод сетевого планирования и управления и как мат аппарат используется в этом методе

Основное назначение сетевых методов – управление длительными, многоэтапными научными, конструкторскими, производственными и др. проектами, такими как строительство зданий, разработка нового изделия и т.д.

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

Мат.методы. вариант 112  1.Решить методом Лагранжа

2. Критерий группировки целевой функции (многокрит.Задачи)

Пусть x⁰ – некоторый допустимый план

Вектор значений критериев

ЛПР не удовлетворён планом x⁰

Разделим все критерии на три группы G₁ G₂ G₃

1. f_j(x) G₁, если его значение может быть уменьшено, по сравнению с

2. f_j(x) G₂, если его значение желательно увеличить по сравнению с

3. f_j(x) G₃, если его значение не хотелось бы уменьшать по сравнению со значение м достигнутым в точке x⁰

S – некоторая переменная величина

l_j –порог уменьшения целевой функции из интервала

3. Метод Лэнд и Дойг

4.Нарисовать граф с петлями и циклами. Как рассчитать длительность работы для сетевой задачи

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

5. Зачем должны быть 0 в общем положении

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

Если нули находятся в общем положении – можно приступать к построению оптимального плана. Это следует из того, что если минимальное число горизонтальных и вертикальных линий, необходимых для того, чтобы вычеркнуть нулевые элементы редуцированной матрицы равно числу строк и столбцов, то существует назначение нулевой стоимости(затрат), т.е. минимальное значение целевой функции. 6. Зачем вводят фиктивные перевозки

1. Чем отличается процесс решения многокритериальной задачи ЛП от обычной задачи ЛП

2. Напишите математическую модель задач ЛП, которые решаются на фиксированном уровне дерева вариантов в методе неявного перебора вариантов целочисленного программирования.

При С₁₃>6

4. Понятие игры с природой. Каким образом она задаётся?

Процесс принятия решений в условиях неопределённостей и риска представляет собой игру с природой.

5. Определение графа. Способы его представления. При решении каких экономических задач применяется теория графов?

В теории множеств графом считается любое отображение множества в себя.

Каждому элементу X_i из множества X (X_i X) поставим в соответствие ноль, один или несколько элементов из Х, тогда мы построим некоторый граф.

Запишем через Г закон, представляющий данное соответствие, запишем граф в виде

G ={x, Г}

Строительство объектов, разработка нового изделия и т.п.

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

Игра с нулевой суммой – игра, в которой каждый игрок выигрывает за счёт других игроков.

Простейшим примером антагонистической игры является игра «Орлянка». Первый игрок прячет монету орлом или решкой вверх, а второй пытается угадать, как она спрятана. Если он не угадывает — он платит первому одну денежную единицу, если угадывает — первый платит ему одну денежную единицу.

X \ Y	Орел	Решка
Орел	-1, 1	1, -1
Решка	1, -1	-1, 1

В данной игре каждый участник имеет две стратегии: «орел» и «решка». Множество ситуаций в игре состоит из четырех элементов. В строках таблицы указаны стратегии первого игрока х, в столбцах — стратегии второго игрока y. Для каждой из ситуаций указаны выигрыши первого и второго игроков.

В аналитическом виде функция выигрыша первого игрока имеет следующую форму:

где x ∈ X и y ∈ Y — стратегии первого и второго игроков, соответственно.

Так как выигрыш первого игрока равен проигрышу второго, то F₂(x,y) = − F₁(x,y).

13