пользователей: 21265
предметов: 10469
вопросов: 178036
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

I семестр:
» Физика
» ИСО

задачи линейного программирования. Табличный симплекс-метод (симплекс-алгоритм). Модель игры с нулевой суммой.

 

 

 

ВОПРОС 1.


В наиболее общей форме математическая постановка задачи линейного программирования (ЛП) имеет вид 

или в матричной форме

где х = (х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 -1 = 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.


Теорема Куна-Таккреа:

 


хиты: 602
рейтинг:0
Точные науки
математика
исследование операций
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь