Б В Г Д З И К Л М Н О П Р С Т Х Ц Ч Э
Игра называется бесконечной, если у каждого игрока имеется бесконечное число стратегий.
Вершины, прилегающие к одному и тому же ребру, называются смежными.
Вырожденный опорный план - опорный план, число ненулевых компонент которого меньше числа ограничений.
Геометрическое программирование. Под задачами геометрического программирования понимают задачи наиболее плотного расположения некоторых объектов в заданной двумерной или трехмерной области. Такие задачи встречаются в задачах раскроя материала для производства каких-то изделий и т.п. Это - еще недостаточно разработанная область математического программирования и имеющиеся здесь алгоритмы в основном ориентированы на сокращение перебора вариантов с поиском локальных минимумов.
Геометрическое решение игры - нахождение решения игры посредством представления данных задачи в виде геометрических фигур на координатной плоскости.
Граф это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек.
Дерево это связный граф без циклов.
Динамическое программирование. Для отыскания оптимального решения планируемая операция разбивается на ряд шагов (этапов) и планирование осуществляется последовательно от этапа к этапу. Однако выбор метода решения на каждом этапе производится с учетом интересов операции в целом.
Задачами теории массового обслуживания является анализ и исследование явлений, возникающих в системах обслуживания. Одна из основных задач теории заключается в определении таких характеристик системы, которые обеспечивают заданное качество функционирования, например, минимум времени ожидания, минимум средней длины очереди.
Игра - математическая модель конфликтной ситуации, стороны, участвующие в конфликте, называются игроками, а исход конфликта - выигрышем.
Канонической форма задачи ЛП является задачей на максимум (минимум) некоторой линейной функции F, ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х1, х2 , ..., хn являются неотрицательными.
Компьютерная модель — это модель, реализованная средствами программной среды.
Игра называется конечной, если у каждого игрока имеется конечное число стратегий.
Граф без цикла называется лесом.
Линейное программирование состоит в нахождении экстремального значения линейной функции многих переменных при наличии линейных ограничений, связывающих эти переменные.
Вершины степени 1 в дереве называются листьями.
Личный ход — это сознательный выбор игроком одного из возможных действий.
Максиминная стратегия - стратегия игрока, при которой он стремится сделать минимальный выигрыш максимальным, т. е. получить наилучшую выгоду в наихудших условиях.
Математическая модель любой задачи линейного программирования включает в себя:
Математические моделирование – наука, занимающаяся разработкой и практическим применением методов наиболее оптимального управления организационными системами.
Матричные игры - это игры, математические модели которых можно представить в виде матриц.
Модель – материальный или мысленно представляемый объект, который в процессе исследования замещает объект-оригинал так, что его непосредственное изучение дает новые знания об объекте-оригинале.
Моделировaние – это изучение объектa путем построения и исследования его модели, осуществляемое с определенной целью и состоит в зaмене экспериментa с оригинaлом экспериментом нa модели.
Метод аппроксимации Фогеля - один из группы методов определения первоначального опорного плана транспортной задачи. Данный метод состоит в следующем:
Метод двойного предпочтения - один из группы методов определения первоначального опорного плана транспортной задачи.
Метод минимальной стоимости - один из группы методов определения первоначального опорного плана транспортной задачи. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai , или bj.
Метод потенциалов - один из методов проверки опорного плана транспортной задачи на оптимальность.
Метод северо-западного угла - один из группы методов определения первоначального опорного плана транспортной задачи.
Минимаксная стратегия - стратегия игрока, при которой он стремится сделать максимальный проигрыш минимальным.
Игра называется множественной, если число игроков больше двух.
Нелинейное программирование. Целевая функция и ограничения могут быть нелинейными функциями.
Игра с нулевой суммой (антагонистическая), если выигрыш одного из игроков равен проигрышу другого.
Оптимальный план ЗЛП - решение задачи линейного программирования, т. е. такой план, который входит в допустимую область и доставляет экстремум целевой функции.
Остовной подграф - это граф, множество вершин которого совпадает с множеством вершин самого графа.
Открытая ТЗ - если общее количество груза в пунктах отправления и общая потребность в пунктах назначения не совпадают (
)
Игра называется парной, если в ней участвуют два игрока.
Подграф графа - это граф, являющийся подмоделью исходного графа, т. е. подграф содержит некоторые вершины исходного графа и некоторые ребра (только те, оба конца которых входят в подграф).
Полным называется граф, в котором каждые две вершины смежные.
Платежная матрица игры - матрица размерности m на n, i = 1, ..., n, j = 1, ..., m, (i,j)-ый элемент которой значение выигрыша (пригрыша) игроков в случае i-го хода первого игрока и j-го хода второго игрока.
Предмет теории игр принятие решений в условиях неопределенности, в условиях столкновения, конфликтных ситуациях, когда принимающий решение субъект (игрок), располагает информацией лишь о множестве возможных ситуаций, в одной из которых он в действительности находится, о множестве решений, которые он может принять, и о количественной мере того выигрыша, который он мог бы получить, выбрав в данной ситуации данную стратегию.
Принцип оптимальности динамического программирования - каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая выигрыш на данном шаге. Простая цепь - маршрут, в котором все вершины попарно различны.
Простой граф - это граф без кратных ребер и петель.
Простой цикл - цикл, в котором все вершины, кроме первой и последней, попарно различны.
Пустым называется граф без ребер.
Путь в ориентированном графе это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Решение – всякий определенный набор зависящих параметров.
Граф называется связным, если любая пара его вершин связана.
Симплекс метод - алгоритм последовательного улучшения плана, позволяющий осуществлять переход от одного допустимого базисного решения к другому таким образом, что значение целевой функции непрерывно возрастают и за конечное число шагов находится оптимальное решение.
Седловой точкой действительной функции f (x,y), определённой для всех x € A, y € B, называется точка (x0 , y0 ), где x € A, y € B, если выполнены следующие условия:
x € A, f (x , y0x,y0) f (x0 , y0), x € В, f (x0 , y0) f (x0 , y). Случайный ход — это случайно выбранное действие игроком.
Стандартная форма задачи линейного программирования является задачей на максимум (минимум) линейной целевой функции. Система ограничений ее состоит из одних линейных неравенств типа «≤» или «≥». Все переменные задачи неотрицательны.
Стационарная точка - точка X* , в которой все частные производные функции Z = f (Х) равны 0.
Степень вершины - это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер.
Стохастическое линейное программирование. Бывает много практических ситуаций, когда коэффициенты ci целевой функции, коэффициенты aij в матрице коэффициентов, коэффициенты ограничений bi - являются случайными величинами. В этом случае сама целевая функция становится случайной величиной, и ограничения типа неравенств могут выполняться лишь с некоторой вероятностью. Приходится менять постановку самих задач с учётом этих эффектов и разрабатывать совершенно новые методы их решения. Соответствующий раздел получил название стохастического программирования.
Стратегией игрока называется совокупность правил, определяющих выбор его действия при каждом личном ходе в зависимости от сложившейся ситуации.
Теорема об активных стратегиях. Если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий.
Теория графов. С помощью теории графов решаются многие сетевые задачи, связанные с минимальным протяжением сети, построение кольцевого маршрута и т.д.
Теория игр пытается математически объяснить явления возникающие в конфликтных ситуациях, в условиях столкновения сторон. Такие ситуации изучаются психологией, политологией, социологией, экономикой.
Транспортная задача - в общем виде состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления A1, A2 , ..., Am в n пунктов назначения B1, B2 , ..., Bn .
Ход игрока - выбор и осуществление одного из предусмотренных правилами действий.
Целевая функция - функция в математическом программировании, для которой требуется найти экстремум.
Цена игры - величина выигрыша игрока.
Выигрыш, соответствующий оптимальному решению, называется ценой игры v.
Цепь маршрут, в котором все ребра попарно различны.
Цикл замкнутый маршрут, являющийся цепью.
Циклом называют замкнутую ломаную линию, все вершины которой лежат в занятых ячейках, кроме одной, расположенной в свободной клетке, подлежащей заполнению, а звенья параллельны строкам и столбцам, причем в каждой строке (столбце) лежит не более 2-х вершин.
Чистые стратегии - возможные ходы в распоряжении игроков.
Элементы решения – параметры, совокупность которых образует решение
