2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Линейное программирование и матричные игры
Сообщение21.11.2006, 12:06 
Здравствуйте!
У меня не получается такая задача.
Есть игра
$$\begin{pmatrix}
0&A&-e\\
-A'&0&e\\
e'&-e'&0\\
\end{pmatrix}$$
Вопрос: как она соотносится с задачей линейного программирования
\max \lbrace\lambda\mid A'x-\lambda e\ge0,e'x=1,x\ge0\rbrace?
Думала, думала, но не понимаю, чего от меня хотят получить в качестве решения. Я считаю, что если мы найдем оптимальное решение данной задачи линейного программирования, то это даст нам оптимальную стратегию игрока, который играет по строкам, если матрица игры - матрица A, так?
А что можно сказать об исходной матрице? Ведь вопрос о ней.
Если применять задачу ЛП к исходной матрице, то по виду матрицы оптимальное значение \lambda должно получиться нулевым. А что можно сказать об оптимальной стратегии игрока, который играет по строкам, в этом случае? В общем, надо ответить на вопрос, как соотносится с приведенной задачей ЛП именно заданная матрица.

 
 
 
 Re: Линейное программирование и матричные игры
Сообщение21.11.2006, 16:33 
marine писал(а):
если мы найдем оптимальное решение данной задачи линейного программирования, то это даст нам оптимальную стратегию игрока, который играет по строкам, если матрица игры - матрица A, так?

Нет, матрица А - это подматрица матрицы игры.
Вам нужно доказать, что для игры такого специального вида можно значительно понизить размерность решаемой задачи ЛП.

 
 
 
 
Сообщение21.11.2006, 17:48 
То есть вы хотите сказать, что данная задача линейного программирования эквивалентна задаче ЛП max \lbrace \lambda \mid B'x-\lambda e\ge 0, e'x=1, x \ge0 \rbrace, где B - заданная матрица специального вида? Я имею в виду, что решения будут совпадать?

 
 
 
 
Сообщение21.11.2006, 20:11 
marine писал(а):
То есть вы хотите сказать, что данная задача линейного программирования эквивалентна задаче ЛП max \lbrace \lambda \mid B'x-\lambda e\ge 0, e'x=1, x \ge0 \rbrace, где B - заданная матрица специального вида? Я имею в виду, что решения будут совпадать?

Что значит "данная задача линейного программирования"? У Вас есть задача теории игр. Задачи ТИ обычно решают сведением к задаче ЛП. Если нет доминирующих стратегий, то размер матрицы ЛП такой же, как и у матрицы ТИ. В Вашем частном случае, когда матрица игры имеет специальную структуру, можно ожидать, что решение игры можно получить из решения задачи ЛП с матрицей значительно меньшего размера.
Помните, Вы писали: "Вопрос: как она соотносится с задачей линейного программирования..."? Ответы могут быть:
1) Решение исходной задачи ТИ легко найти из решения задачи ЛП ... (И указать, как именно!)
2) Решение исходной задачи ТИ не имеет отношения к решению задачи ЛП ...
3) Решение исходной задачи ТИ легко найти из решения задачи ЛП ... при следующих доп. условиях: ....
4) ... и т.д.

 
 
 
 
Сообщение21.11.2006, 21:55 
Уважаемый Юрий!
Я все понимаю, что вы написали. К сожалению теорию игр, как отдельный курс, не изучала, прочитала только соответствующую главу учебника по линейному программированию. Этого, со слов преподавателя, должно хватить. Но я не могу понять, как действовать. Пробовала решать данную задачу с помощью мат.пакета для разных матриц. Как получаемые ответы могут быть связаны, не представляю. Например, матрица А имеет размер 2х3, тогда исходная - 6х6. Стратегия игрока - это уже не двухразмерный вектор, а шестиразмерный. Я в начале думала, что может остальные 4 значения будут просто нулевыми, но это так, интуитивно. Практика показала, что мое предположение не верно. Если вы можете подсказать идею, была бы очень благодарна.

 
 
 
 
Сообщение22.11.2006, 01:44 
Вот Ваш вопрос: Вы не понимаете
Цитата:
чего от меня хотят получить в качестве решения. Я считаю, что если мы найдем оптимальное решение данной задачи линейного программирования, то это даст нам оптимальную стратегию игрока, который играет по строкам, если матрица игры - матрица , так?
Вам нужно именно доказать, то, что Вы считаете. Не пробовать разные матрицы, а доказать теорему. Формулировка теоремы - в Вашем первом посте.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group