ВОПРОС 1.
В наиболее общей форме математическая постановка задачи линейного программирования (ЛП) имеет вид
.JPG)
или в матричной форме
где х = (х1, …, хп)Т – вектор переменных задачи, f(x) целевая функция, D – множество допустимых решений. Целью задачи является нахождение такого вектора х* из D, который либо максимизирует, либо минимизирует целевую функцию, т. е
.
Графическая иллюстрация.
Для графического решения задачи необходимо:
- построить область допустимых решений D;
- построить линии уровня целевой функции f(x) = cTx = f0;, которые будут перпендикулярны вектору с;
- выбрать линию с максимальным уровнем: она пересекает множество D либо в одной вершине, либо в двух вершинах. В первом случае имеем одно оптимальное решение, а во втором случае – бесчисленное множество оптимальных решений.
На рис.1.1 изображены : а) выпуклое (ограниченное по расстоянию) множество допустимых решений D, б) линии уровня целевой функции f(x), перпендикулярные вектору с = (5, 4)Т. Линия максимального уровня проходит через вершину х* с координатами х1* = 3, х2* = 1.5, являющейся оптимальным решением задачи. Максимальное значение целевой функции в этой точке равно f* = f(x*) = 21000. Таким образом, искомое решение есть х* = (x1*, x2*)T = (3, 1.5)T, f* = f(x*) = 21000.
Очевидно, что найденные оптимальные значения х* и f* зависят от параметров задачи сj, j = 1, …, n, bi, i = 1, …, m, aij, i = 1, …, m, j = 1, …, n, другими словами, х* = х*(с, b, А), f* = f*(с, b, А). Поэтому, перед тем, как рекомендовать найденное решение к внедрению, необходимо провести его анализ чувствительности, т. е. решить вопрос о том, как влияют параметры задачи на оптимальное решение.
1.5. Табличный симплекс-метод (симплекс-алгоритм)
Cимплекс - метод основан на итеративном процессе перебора (или преобразования) вершин области допустимых решений и проверки в этих вершинах условия оптимальности. Вершины, как отмечалось выше, генерируются с помощью базисов. Табличный вариант алгоритма весьма удобен для машинного счета, так как связан с преобразованием таблиц – массивов данных, которые содержат сведения о текущем базисе, базисном решении, правиле остановки и, наконец, об оптимальном решении. В процессе преобразования таблиц, которое представляет собой реализацию процедуры полного исключения Гаусса, формируется также информация о двойственных переменных решаемой задачи.
Пусть задача представлена в канонической форме
где с и х – векторы размерности (п х1), т. е. с принадлежит Еп, х принадлежит Еп, А – матрица размерности (mхп), b – (пх1) – вектор.
Допустим, что матрица А допускает представление в виде А = [B, N], где B – (mхm) – матрица полного ранга. Для простоты предположим, что B - единичная матрица, т.е. B = I. Это может иметь место, например, если ограничения исходной задачи имеют вид Ax ≤ b. В случае неотрицательного вектора b, т. е. b ≥ 0, это предположение помогает найти первое базисное решение в виде
xB = B -1b = I -1b = b ≥ 0. (5.2)
Тогда первая вершина будет равна
х1 = (0Тп - m, bТ)Т, (5.3)
где через 0п–m обозначен нулевой вектор с п–m координатами. Для построения исходной таблицы обозначим через IB и IN, множества индексов векторов из B и N соответственно и вычислим так называемые симплекс -разности для векторов, принадлежащих N по формуле
Предварительный этап. Представить задачу в канонической форме.
Шаг 2. Нахождение базисного решения.
Шаг 3.Вычисление симплекс - разностей и построение правила остановки.
Шаг 4.Построение и преобразование исходной таблицы Т0.
Шаг 5. Проверка правила остановки
Шаг 6. Выбор направляющего столбца и направляющей строки.
Шаг 7. Симплексные преобразования таблицы.
ВОПРОС 2.
Модель игры с нулевой суммой.
Антагонистическая игра (игра с нулевой суммой, англ. zero-sum) — термин теории игр. Антагонистической игрой называется некооперативная игра, в которой участвуют два игрока, выигрыши которых противоположны.
Формально антагонистическая игра может быть представлена тройкой , где X и Y — множества стратегий первого и второго игроков, соответственно; F — функция выигрыша первого игрока, ставящая в соответствие каждой паре стратегий (ситуации) (x,y),
действительное число, соответствующее полезности первого игрока при реализации данной ситуации. Так как интересы игроков противоположны, функция F одновременно представляет и проигрыш второго игрока.
Исторически антагонистические игры являются первым классом математических моделей теории игр, при помощи которых описывались азартные игры. Считается, что благодаря этому предмету исследования теория игр и получила свое название. В настоящее время антагонистические игры рассматриваются как часть более широкого класса некооперативных игр.
Простейшим примером антагонистической игры является игра «Орлянка». Первый игрок прячет монету орлом или решкой вверх, а второй пытается угадать, как она спрятана. Если он не угадывает — он платит первому одну денежную единицу, если угадывает — первый платит ему одну денежную единицу.
В данной игре каждый участник имеет две стратегии: «орел» и «решка». Множество ситуаций в игре состоит из четырех элементов. В строках таблицы указаны стратегии первого игрока х, в столбцах — стратегии второго игрока y. Для каждой из ситуаций указаны выигрыши первого и второго игроков.
В аналитическом виде функция выигрыша первого игрока имеет следующую форму:
где x ∈ X и y ∈ Y — стратегии первого и второго игроков, соответственно.
Так как выигрыш первого игрока равен проигрышу второго, то
Игры с нулевой суммой — особая разновидность игр с постоянной суммой, то есть таких, где игроки не могут увеличить или уменьшить имеющиеся ресурсы, или фонд игры. В этом случае сумма всех выигрышей равна сумме всех проигрышей при любом ходе. Посмотрите направо — числа означают платежи игрокам — и их сумма в каждой клетке равна нулю. Примерами таких игр может служить покер, где один выигрывает все ставки других; реверси, где захватываются фишки противника; либо банальное воровство.
Многие изучаемые математиками игры, в том числе уже упоминавшаяся «Дилемма заключённого», иного рода: в играх с ненулевой суммой выигрыш какого-то игрока не обязательно означает проигрыш другого, и наоборот. Исход такой игры может быть меньше или больше нуля. Такие игры могут быть преобразованы к нулевой сумме — это делается введением фиктивного игрока, который «присваивает себе» излишек или восполняет недостаток средств.
Ещё игрой с отличной от нуля суммой является торговля, где каждый участник извлекает выгоду.
ВОПРОС 3.
Теорема Куна-Таккреа:
.JPG)
