Задачи для самостоятельного решения

1. На двух складах А и В находится по 90 т горючего. Перевозка одной тонны горючего со склада А в пункты 1, 2, 3 соответственно стоит 1, 3 и 5 ден. ед., а перевозка одной тонны со склада В в те же пункты — соответственно 2,5 и 4 ден. ед. В каждый пункт надо доставить по одинаковому количеству тонн горючего. Составить такой план перевозки горючего, при котором транспортные расходы будут наименьшими.

2. В резерве трех железнодорожных станций А, В и С находятся соответственно 60, 80 и 100 вагонов. Составить оптимальный план перегона этих вагонов к четырем пунктам погрузки хлеба, если к пункту № 1необходимо 40 вагонов, № 2 ― 60 вагонов, № 3 ― 80 вагонов и № 4—60 вагонов. Стоимости перегонов одного вагона со станции А в указанные пункты соответственно равны I, 2, 3, 4 ден. ед., со станции В — 4, 3,2,0 ден. ед. и со станции С — 0, 2, 2, 1 ден. ед.

3. Завод имеет три цеха А, В, С и четыре склада № 1, 2, 3, 4, Цех А производит 30 тыс, шт. изделий, цех В 40 тыс. шт., цех С—20 тыс. шт. Пропускная способность складов за то же время характеризуется следующими показателями: склад № 1—20 тыс, шт., склад № 2—30 тыс. шт., склад № 3 — 30 тыс. шт., склад № 4 —10 тыс. шт. Стоимости перевозки 1 тыс, шт изделий из цеха А в склады № 1, 2, 3, 4 соответственно равны 2, 3, 2, 4 ден. ед.; из цеха В — 3, 2, 5, 1 ден. ед., а из цеха С — 4, 3, 2, б ден. ед. Составить такой план перевозки изделий, при котором расходы на перевозку 90 тыс. шт. изделий были бы наименьшими.

4. На трех складах А, В, С находится сортовое зерно соответственно 10, 15, 25 т, которое надо доставить в четыре пункта: пункту № 1—5 т, № 2—10 т, № 3—20 т и № 4 — 15 т. Стоимости доставки одной тонны со склада А в указанные пункты соответственно равны 8, 3, 5, 2 ден ед.; со склада В — 4,1,6, 7 ден. ед. и со склада С — 1, 9, 4, 3 ден. ед. Составитьоптимальный план перевозки зерна в четыре пункта, минимизирующий стоимость перевозок.

5. Груз, находящийся в пунктах А ₁: А ₆, соответственно в количестве а ₁: а ₆,требуется перевести в пункты В ₁: В ₆ соответственно в количестве b ₁: b ₆. Известны тарифы с_ij ―стоимость перевозки единицы груза из пункта А _i в пункт В _j.

bj ai

Спланировать перевозки так, чтобы общая стоимость перевозок была наименьшей.

Ответы: 1. F _min=510 ден.ед.; х ₁₁=30, х ₁₂=60, х ₂₁=30, х ₂₃=60.

2. F _min=280 ден.ед. Оптимальный план: х ₁₂= х ₂₄= х ₃₃=60, х ₂₃=20, х ₃₁=40.

3. F _min=395 ден.ед. Оптимальный план: х ₁₁=25, х ₁₃= х ₃₂=20, х ₁₂= х ₂₁=5, х ₂₃=35;

4. F _min=140 ден.ед. Оптимальный план: х ₁₄= х ₂₂=10, х ₂₃= х ₃₁= х ₃₄=5, х ₃₃=15.

5. F _min=148 ден.ед. Оптимальный план: Х ^*= .

ГЛАВА II. ТЕОРИЯ ИГР

Математические модели конфликтных ситуаций

 

В приложениях теории оптимизации рассматриваются задачи, когда выбор решения осуществляется одной стороной (максимизация прибыли производителя, модели потребительского выбора и пр.). В реальности имеется столкновение интересов нескольких сторон, каждая из которых желает оптимизировать свою деятельность на рынке. Классическими примерами такой ситуации являются: продавец — покупатель; несколько производителей на рынке, воздействующих на цену товара (олигополия); объединения или коалиции, участвующие в столкновении разных интересов. Много подобных примеров встречается в биологии, социологии, психологии, в военном деле, в различных играх и т. д.

Математическая теория игр ведет свое начало от анализа обычных игр — салонных, карточных, спортивных. Впервые теория игр была систематически изложена Дж. фон Нейманом и О. Моргенштерном в 1944 г. Их книга содержала в основном экономические примеры, так как экономическую ситуацию относительно легко описать в численной форме. Уже во время второй мировой войны теория игр была применена в военном деле для исследования стратегических решений. Во второй половине XX в. главное внимание в теории игр стало уделяться экономическим приложениям.

Предмет теории игр. Основные понятия

При решении практических задач (в области экономики, военного дела и т.д.) приходится анализировать ситуации, где имеется столкновение двух (или более) сторон, преследующих противоположные цели и интересы, причём результат каждого мероприятия одной из сторон зависит от того, какой образ действий выберет соперник. Такие ситуации мы будем называть «конфликтной ситуацией».

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

Необходимость анализировать подобные ситуации вызвала к жизни специальный математический аппарат. Теория игр представляет собой математическую теорию конфликтных ситуаций. Цель теории - выработка рекомендаций по рациональному образу действий участников (игроков) в ходе конфликтной ситуации.

Каждая непосредственно взятая из практики конфликтная ситуация очень сложна, и анализ её затруднён наличием многочисленных факторов.

Чтобы сделать возможным математический анализ ситуации, необходимо отвлечься от второстепенных, приходящих факторов и построить упрощённую, формализованную модель ситуации. Такую модель мы будем называть «игрой».

От реальной конфликтной ситуации игра отличается тем, что ведётся по вполне определённым правилам. В игре сталкиваются интересы двух или более противников; в первом случае игра называется «парной», во втором - «множественная». Наибольшее практическое значение имеют парные игры; будем рассматривать парную игру, в которой участвуют два игрока А и В с противоположными интересами.

Под «игрой» будем понимать мероприятие, состоящее из ряда действий сторон А и В. Чтобы игра могла быть подвергнута математическому анализу, должны быть сформулированы правила игры.

Под "правилами игры" разумеется система условий, регламентирующая возможные варианты действий обеих сторон, объём информации каждой стороны о поведении другой, последовательность чередования «ходов» (отдельных решений, принятых в процессе игры), а также результат или исход игры, к которому приводит данная совокупность ходов. Этот результат не всегда имеет количественное выражение, но можно установить шкалу измерения, выразить его определённым числом.

Например, в шахматной игре выигрышу можно условно приписать значение "+1", проигрышу "-1", ничьей "0".

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

В игре с нулевой суммой интересы игроков прямо противоположны.

Развитие игры во времени мы будем представлять состоящим из ряда последовательных этапов или "ходов".

Определение 2. Ходом в теории игр называется выбор одного из предусмотренных правилами игры вариантов.

Ходы делятся на личные и случайные.

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

Определение 4. Случайным ходом называется выбор одного из ряда возможностей, осуществляемых не решением игрока, а каким-либо механизмом случайного выбора. Например, бросание монеты.

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

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

Большинство игр принадлежат к играм смешанного типа, то есть содержат как случайные ходы, а также и личные ходы.

Игры классифицируются не только по характеру ходов (личные, случайные), но и по характеру, и по объему информации, доступной каждому игроку относительно действий другого. Особый класс игр составляют так называемые «игры с полной информацией». Игрой с полной информацией называется игра, в которой каждый игрок при каждом личном ходе знает результаты всех предыдущих ходов как личных, так и случайных. Например, шахматы, шашки.

Большинство игр, имеющих практическое значение, не принадлежат к классу игр с полной информацией, так как неизвестность по поводу действий соперника обычно является существенным элементом конфликтной ситуации. Одним из основных понятий теории игр является понятие «стратегии».

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

Понятие стратегии объясним подробнее. Обычное решение (выбор) при каждом личном ходе принимается игроком в ходе самой игры в зависимости от сложившейся конкретной ситуации. Однако теоретически дело не изменится, если мы представим себе, что все эти решения принимаются игроком заранее. Для этого игрок должен был бы заблаговременно составить перечень всех возможных в ходе игры ситуаций и предусмотреть своё решение для каждой из них. В принципе это возможно для любой игры (если не практически). Если такая система решений будет принята, это будет означать, что игрок выбрал определённую стратегию. Игрок, выбравший стратегию, может теперь не участвовать в игре лично, а заменить своё участие списком правил, алгоритмом, который за него может применять какое-либо незаинтересованное лицо (судья). Стратегия может быть также задана машине-автомату в виде определённой программы. Именно так в настоящее время играют в шахматы электронные счётные машины. Чтобы понятие "стратегии" имело смысл, необходимо наличие в игре личных ходов; в играх, которые состоят только из одних случайных ходов, стратегии отсутствуют.

В зависимости от числа возможных стратегий игры делятся на "конечные" и "бесконечные".

Определение 6. Конечной называется игра, в которой у каждого игрока только конечное число стратегий.

Конечная игра, в которой игрок А имеет " т " стратегий, а игрок В - " п " стратегий, называется игрой m x n.

Рассмотрим игру m x n двух игроков А и В. Будем обозначать наши стратегии А₁, А₂,..., А _т стратегии противника В₁, В₂,..., В _п.

Пусть каждая сторона выбрала определённую стратегию; для игрока А это будет A _i, для игрока В это В _j.

Если игра состоит только из личных ходов, то выбор стратегии А _i, В _j, однозначно определяет исход игры - наш выигрыш. Обозначим его a_{i j}.

Если игра содержит, кроме личных, случайные ходы, то выигрыш при паре стратегий А _i, В _j есть случайная величина, зависящая от исходов всех случайных ходов. В этом случае оценкой ожидаемого выигрыша является его среднее значение (математическое ожидание).

Пусть нам известны все значения выигрыша a_{i j} при каждой паре стратегий. Значение a_{i j} можно записать в виде прямоугольной таблицы (матрицы), строки которой соответствуют нашим стратегиям (А _i), а столбцы - стратегиями противника (B _j). Такая таблица называется платёжной матрицей или просто матрицей игры (таблица 11).

Таблица 11 - Матрица игры m x n.

 

В А	В1	В2	…	Вn
А1	а 11	а 12		a 1 n
А2	а 21	а 22		а 2 п
…	…	…	…	…
А m	am 1	ат 2	…	атп

 

Сокращённо будем обозначать матрицу игры ║ a_ij ║. Если игра записана в таком виде, то говорят, что она приведена к нормальному виду.

Целью теории игр является выработка рекомендаций для разумного поведения игроков в конфликтных ситуациях, то есть определение «оптимальной стратегии» каждого из них.

Определение 7. Оптимальной стратегией игрока в теории игр называется такая стратегия, которая при многократном повторении игры обеспечивает данному игроку максимальный выигрыш (или, что то же, минимально возможный средний проигрыш).

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

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

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

Стратегия, являющаяся оптимальной по одному критерию, может быть не оптимальной по другим критериям.

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

Нижняя и верхняя цена игры. Принцип "минимакса"

Рассмотрим игру m x n с матрицей, представленной в таблице 11.

Будем обозначать буквой i номер стратегии игрока А; j - номер стратегии игрока В. Поставим задачу определить оптимальную стратегию. Проанализируем последовательно каждую из стратегий игрока А, начиная с А₁.

Выбирая стратегию А _i игрок А должен рассчитывать на то, что игрок В (противник) ответит на нее той же из стратегий B _j, для которой выигрыш игрока А - a_{i j} в i строке и обозначим его α _i:

. (11)

Под знаком (минимум по j) обозначено минимальное из значений данного параметра при всех возможных j. Выпишем α _i рядом с матрицей справа в виде добавочного столбца.

Таблица 12 - Измененная таблица 11 с добавочным столбцом.

 

В А	В1	В2	….	В п	α i
А1	а 11	а 12	….	а 1 п	α1
А2	а 12	а 22	….	а2п	α 2
….	….	….	….	….	….
А т	а т 2	ат 2	….	атп	α т
β j	β1	β2	…	β п

 

Выбирая какую-либо стратегию A _i надо рассчитывать на то, что в итоге разумных действий игрока В, игрок А не выиграет больше, чем α _i. Останавливаемся на той стратегии А _i; для которой число α _i является максимальным. Обозначим это число через α:

. (12)

Определение 8. Величина α называется нижней ценой игры; иначе - максимальным выигрышем или просто максимином.

Число α лежит в определённой строчке матрицы; та стратегия игрока А, которая соответствует этой строчке, называется максиминной стратегией.

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

Аналогичные рассуждения можно провести за игрока В. Так как он заинтересован в том, что обратить выигрыш игрока А в минимум, он должен просмотреть каждую свою стратегию, с точки зрения максимального выигрыша при этой стратегии. Поэтому внизу матрицы выпишем максимальные значения α _ij по каждому столбцу:

(13)

и найдем минимальное значение из β _j:

. (14)

Величина β называется «верхней ценой игры» иначе «минимаксом». Соответствующая минимаксному выигрышу стратегия конкурента называется его «минимаксной стратегией».

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

Принцип осторожности, диктующий игрокам выбор соответствующих стратегий (максиминной и минимаксной), в теории игр и её приложениях часто называют «принципом минимакса».

Наиболее осторожные максиминную и минимаксную стратегии игроков иногда обозначают общим термином «минимальные стратегии».

Пример 19. В нашем распоряжении имеется три вида вооружения: А_1, А₂, А₃; у противника три вида танков: В₁, В₂, В₃. Наша задача - поразить танк; задача противника - сохранить его не поражённым. При применении вооружения A₁ танки В₁, В₂, В₃ поражаются соответственно с вероятностями 0,9; 0,4 и 0,2; при вооружении А₂ - с вероятностями 0,3; 0,6 и 0,8; при вооружении А₃ - с вероятностями 0,5; 0,7 и 0,2. Требуется сформулировать ситуацию в терминах теории игр и составить матрицу игры. Определить нижнюю и верхнюю цену игры и минимаксные стратегии.

Решение. Ситуация может рассматриваться как игра 3x3 с двумя личными и одним случайным ходами. Наш личный ход - выбор типа вооружения; личный ход противника - выбор танка для участия в бою. Случайный ход - применение вооружения; этот ход может закончиться поражением или не поражением танка.

Наш выигрыш равен единице, если танк поражён, и равен нулю в противном случае. Нашими стратегиями являются три вида вооружения; стратегиями противника - три вида танков. Среднее значение выигрыша при каждой заданной паре стратегий есть не что иное, как вероятность поражения данного танка данным вооружением. Тогда матрица игры выглядит следующим образом.

Нижняя цена игры α= 0,3; верхняя цена игры β= 0,7. Наша наиболее осторожная игра (максиминная) стратегия есть А₂, мы гарантируем, что будем поражать танк в среднем не менее чем в 0,3 всех случаев.

Таблица 13 - Игра с нижней и верхней границами.

 

В А	В1	В2	В п	α i
А1	0,9	0,4	0,2	0,2
А2	0,3	0,6	0,8	0,3
А т	0,5	0,7	0,2	0,2
β j	0,9	0,7	0,8

 

Наиболее осторожной стратегией (минимаксной) противника является В₂, применяя этот танк, противник может быть уверен, что он будет поражаться не более чем в 0,7 всех случаев.

Замечание 1. В данном примере можно показать важное свойство минимаксных стратегий - их неустойчивость. Если мы применим свою наиболее осторожную (максиминную) стратегию В₂, то, придерживаясь этих стратегий, обе стороны будут иметь средний выигрыш 0,6, он будет уже больше нижней цены игры и меньше верхней цены игры: α=0,3<0,6<0,7=β.

Если предположим, что игрок В узнал, что игрок А применяет стратегию А₂, то он на неё может ответить стратегией B₁ и сведёт выигрыш А к 0,3; но, в свою очередь, на стратегию противника В₁, игрок А может ответить стратегией А₁ которая даёт выигрыш 0,9 и так далее.

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

Однако существуют некоторые игры, для которых минимаксные стратегии являются устойчивыми. Это те игры, для которых нижняя цена равна верхней: α=β.

Определение 9. Если нижняя цена игры равна верхней, то их общее значение называется чистой ценой игры (ценой игры) и обозначается буквой v.

Пример 20. Пусть дана игра 4x4 и задана её матрица. Произвести анализ игры.

Решение.

Нижняя цена игры α= 0,6; верхняя цена игры β= 0,6.

Таким образом, α=β= v = 0,6 - чистая цена.

Элемент 0,6, выделенный в платёжной матрице, является одновременно минимальным в своей строке и максимальным в своём столбце.

Таблица 14 - Игра 4x4 с нижней и верхней границами.

 

В А	В1	В2	В3	В4	α i
А1	0,4	0,5	0,9	0,3	0,3
А2	0,8	0,4	0,3	0,7	0,3
А3	0,7	0,6	0,8	0,9	0,6
А4	0,7	0,2	0,4	0,6	0,2
β j	0,8	0,6	0,8	0,9

 

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

Определение 10. Элемент матрицы игры, который является минимальным в строке и максимальным в столбце, называют седловой точкой матрицы, а про игру говорят, что она имеет седловую точку.

Седловой точке соответствует пара минимальных стратегий. Эти стратегии называются оптимальными, а их совокупность — решением игры.

Решение игры обладает следующим замечательным свойством: если один из игроков придерживается своей оптимальной стратегии, а другой игрок будет любым образом отклоняться от своей оптимальной стратегии, то для игрока, который допустит отклонение, это никогда не может оказаться выгодным.

Отклонение игрока В от своей оптимальной стратегии в лучшем случае может оставить выигрыш неизменным, а в худшем случае - увеличить его.

Если игрок В придерживается своей оптимальной стратегии, а игрок А отклоняется от своей стратегии, то это ни коем образом не может быть выгодным для игрока А.

В случае игры с седловой точкой минимальные стратегии обладают «устойчивостью»: если одна сторона придерживается своей минимальной стратегии, то для другой может быть только не выгодным отклоняться от своей. В том случае, если один игрок узнал, что противник избрал свою оптимальную стратегию, то другому нет необходимости изменить свою собственную стратегию, в противном случае он будет действовать против своих же интересов.

Значит, пара оптимальных стратегий в игре с седловой точкой является как бы «положением равновесия»: любое отклонение от оптимальной стратегии приводят отклоняющуюся сторону в игре к невыгодным последствиям, которые вынудят его вернуться в исходное положение.

Итак, для каждой игры с седловой точкой существует решение, которое определяет пару оптимальных стратегий обеих сторон, которые отличаются следующими свойствами:

1. Если обе стороны придерживаются своих оптимальных стратегий, то средний выигрыш равен чистой цене игры v, одновременно являющейся её нижней и верхней ценой.

2. Если одна из сторон придерживается своей оптимальной стратегии, а другая отклоняется от своей, то от этого отклоняющаяся сторона может только потерять и ни в коем случае не может увеличить свой выигрыш.

Теорема 13. Каждая игра с полной информацией имеет седловую точку, следовательно, имеет решение, то есть существует пара оптимальных стратегий той и другой стороны, дающая средний выигрыш, равный цене игры [1].

 

⇐ Предыдущая13141516171819202122Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: