Вычислительная схема метода потенциалов

⇐ ПредыдущаяСтр 7 из 7

Шаг 1. Строим опорный план (методом северо-западного угла) с

n+m-1 базисными клетками.

Шаг 2. Определяем платежи

для всех базисных клеток. Один из платежей (например a1 ) полагаем равньм нулю.

Шаг 3. Считаем

для всех свободных клеток. Если

для всех клеток, то план оптимален. Вычисляем значение целевой функции L на этом плане и исследования прекращаем.

Шаг 4. Если есть свободная клетка, для которой

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

Шаг 5. Возвращаемся к шагу 2 для пересчета платежей нового опорного плана.

Пример

Решить методом потенциалов транспортную задачу

Опорный план этой задачи найден методом северо-западного угла.

Приписываем к таблице добавочную строку для платежей

и добавляем столбец для платежей

Псевдостоимости записываем в левом углу клетки, а стоимости - в правом углу.

Из условий

в базисных клетках получаем систему уравнений

Полагая, находим последовательно платежи

и псевдостоимости для свободных клеток. Получаем таблицу

Стоимость перевозок по плану этой таблицы

Так как клетка (1, 3) имеет отрицательную цену

то план не является оптимальным. Строим для клетки (1, 3) цикл. Цена

цикла

ɣ ₁₃=2-12=-10

По циклу переносим 20 единиц груза (больше нельзя, чтобы перевозки в клетке (1, 2) не стали отрицательными).При этом стоимость плана уменьшается на

Для нового плана вычисляем новые значения платежей и псевдостоимостей:

Стоимость перевозок по плану этой таблицы

Полученная таблица имеет клетку (2, 1 ) с отрицательной ценой

По циклу этой клетки переносим 10 единиц груза,

при этом стоимость плана уменьшается на

единиц, и получаем новый опорный план с новой системой платежей и псевдостоимостей:

Стоимость перевозок по плану этой таблицы

Так как в последней таблице все псевдостоимости не превосходят

соответствующих стоимостей, то полученный опорный план

является оптимальным. Стоимость перевозок при этом

Игровой подход в решении прикладных задач

Урок 1.

Тема урока: «Предмет теория игр».

Цель урока: Дать понятие теории игр и изучить методы решения задач.

Оборудование: доска, компьютер, электронный учебник.

Задачи урока: научить различать типы моделей, разрабатывать по этапам модель.

План урока:

1. Организационный момент.

2. Мотивация изучения нового материала.

3. Изучение нового материала.

4. Подведение итогов урока.

Продолжительность урока: 40 минут.

Тип урока: урок изучения нового материала.

Ход урока:

I. Организационный момент.

Приветствие, проверка присутствующих. Объяснение хода урока.

II. Мотивация изучения нового материала

С этого урока мы начинаем знакомство с решения задач линейного программирования.

Сначала речь пойдет о предмете «Теория игр».

III. Изучение нового материала

Сегодня мы познакомимся с предметом «Теория игр».

Теорией игр называется математическая теория конфликтных ситуаций.

Игра это упрощенная модель конфликтной ситуации.

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

В парной игре называют А и В. В правилах игры перечисляют все возможные ситуации и все возможные варианты действий игроков. Объем информации каждой из сторон о поведении другой и каждая игра явно или косвенно должна быть оценена некоторым числом. Это число называется выигрышем или проигрышем. Кодом теории матричных игр называется выбор одного из предложенных противниками игры действий.

Стратегия – план, по которому совершается выбор в любой возможной ситуации и при любой возможной фактической информации.

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

Парной игрой с нулевой суммой называется игра, в которой выигрыш одного игрока равен проигрышу другого игрока.

А теперь мы рассмотрим пример решения задачи, используя матрицу игры.

Пусть игрок А выбирает одну из своих стратегий А₁, А₂, …А_m, игрок В выбирает B₁, B₂, …, B_n. Причем выбор осуществляется при полном незнании выбора другого игрока. Парная игра состоит из двух ходов:

1) выбор игроком А своих стратегий;

2) выбор игроком В своих стратегий.

Пусть - выигрыш игрока А (проигрыш игрока В) при условии, что игрок А выбирает стратегию А_i, а игрок B – B_j. Элементы располагают в виде таблицы:

B_j A_i	B₁	B₂	…	B_n
A₁	a₁₁	a₁₂	…	a_1n
A₂	a₂₁	a₂₂	…	a_2n
…	…	…	…
A_m	a_m1	a_m2	…	a_mn

Эта таблица называется платежной матрицей игры.

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

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

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

Таким образом, для любой конечной матричной игры чистая нижняя цена игры не превосходит чистой верхней цены. Если чистая нижняя цена игры совпадает с чистой верхней ценой, т.е. , то матричная игра имеет седловую точку в чистых стратегиях. Пусть i₀ и j₀ – номера чистых стратегий игроков А и В, при которых достигается это равенство. Тогда пара чистых стратегий (А_i₀, B_j₀) называется седловой точкой матричной игры. Элемент a_i₀_j₀ платежной матрицы называется седловым элементом матричной игры, называется чистой ценой игры, (А_i₀, B_j₀, ) называют решением игры.

Если игра имеет седловую точку, то седловой элемент a_i₀_j₀ является наименьшим для строки с номером i₀ и наибольшим для столбца с номером j₀. Поэтому .

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

IV. Подведение итогов урока

Подведение итога урока.

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

V. Домашнее задание

Знать, что такое Теория игр.

Урок 2.

Тема: Матричные игры и их аналитическое решение.

Цель урока: Познакомить с методами решения матричной игры.

Задачи:

1. Рассказать о матричных играх и их решении.

2. Закрепить материал.

3. Дать домашнее задание.

Продолжительность урока: 40 минут.

Тип урока: урок изучения нового материала.

Этапы урока:

1. Организационный момент.

2. Изучение нового материала.

3. Подведение итогов урока.

4. Домашнее задание.

Ход урока.

Этап 2. Изучение нового материала.

Кроме игр с Седловой точкой имеются игры без таких точек. При многократном проведении игры игрокам выгодно менять свои стратегии. Предположим, что в ходе игры игрок А применяет свои чистые стратегии А₁, А₂, …, А_m соответственно с вероятностями . Так как А₁, А₂, …, А_m образуют полное пространство событий, то . Игрок В применяет свои чистые стратегии В₁, В₂, …, В_n в соответствии с вероятностями , то .

Упорядоченное множество называют смешанной стратегией игрока А.

Упорядоченное множество называют смешанной стратегией игрока В.

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

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

Имеет место следующая основная теорема теории игр.

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

- верхняя цена игры

- нижняя цена игры

Смешанные стратегии называются оптимальным, если имеет место следующее равенство: , где - цена игры и .

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

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

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

Дублирующими называются стратегии, которым соответствуют одни и те же элементы игровой матрицы, т.е. если матрица игры содержит одинаковые столбцы или строки.

Если все элементы i-той строки меньше соответствующих элементов k-той строки, то стратегия А_i игрока А соответствующая этой строке будет доминирующей. В этом случае i-тую строку в матрице можно убрать. Если все элементы j-того столбца будут больше соответствующих элементов r-того столбца, то стратегия В_j игрока В будет доминирующей и в этом случае j-тый столбец матрицы можно отбросить. Наиболее простой игрой является матрица 2х2, когда оба игрока имеют по две чистых стратегии. Пусть игра без седловой точки, матрица игры имеет вид: , требуется найти оптимальную смешанную стратегию игрока А.

Она отличается тем свойством, что, каковы бы ни были действия противника (если только он не выходит за пределы своих «полезных» стратегий), выигрыш будет равен цене игры . В игре 2х2 обе стратегии противника являются «полезными», - иначе игра имела бы решение в области чистых стратегий (седловую точку). Стратегия игрока В также смешанная, поэтому если игрок А применяет свою оптимальную стратегию, то игрок В может придерживаться любой из своих чистых стратегии В₁, В₂, не изменяя среднего выигрыша . Отсюда имеем два уравнения:

из которых, принимая во внимание, что , получим: , .

Цену игры найдем, подставляя в любое из уравнений системы. .

Если цена игры известна, то для определения оптимальной стратегии противника, игрока В достаточно одного из уравнений системы: . Откуда, учитывая, что , имеем: , .

А теперь попробуем решить некоторые примеры по использованию

матричной игры:

Найти решение игры, если сторона А располагает пятью стратегиями А1, А2, А3, А4 и А5, сторона В – двумя В1 и В2. Матрица игры имеет вид:

В А	В1	В2
А1
А2
А3
А4
А5

Решение. Платежную матрицу игры можно записать в виде:

Проверим, имеет игра решение в чистых стратегиях или нет. Для этого найдем максимин m и минимакс M.

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

Матрица игры имеет размерность , можно найти решение графически. Возьмем на оси абсцисс участок длиной 1. Левый конец будет изображать стратегию В1 игрока В, а правый – стратегию В2. Через точки В1 и В2 проведем перпендикуляры и на них будем откладывать выигрыши при использовании игроком В своих чистых стратегий. На левом перпендикуляре будем откладывать выигрыш при стратегии В1, а на правом выигрыш при использовании стратегии В2. Проводим отрезки, соединяющие точки на левом и правом перпендикулярах, соответствующие стратегиям игрока А.

Выделим верхнюю границу выигрыша для игрока А. Это будет ломаная А1КА4. Отрезок KN определяет цену игры , а отрезки B1N и B2N определяют смешанные стратегии игрока В.

Активными стратегиями игрока А являются стратегии А1 и А4, тогда .

Тогда игра сводится к игре с матрицей .

Уравнения, из которых определяются и следующие:

Отсюда: ; ; .

Уравнения, из которых определяются и следующие:

Отсюда: ; ;

Задача решена.

Смешанная стратегия игрока А: . Смешанная стратегия игрока В: . Цена игры .

Этап 3. Подведение итогов урока.

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

Этап 4. Домашнее задание.

Решить задачу: Найти решение игры, если сторона А располагает двумя стратегиями А1 и А2, сторона В – пятью В1, В2, В3, В4, В5. Матрица игры имеет вид:

Урок 3.

Тема: Графический метод решения задач.

Цель: Научить решать задачи графическим методом.

Задачи:

1. Дать представление о графическом методе.

2. Закрепить материал.

3. Задать домашнее задание.

Продолжительность урока: 40 минут.

Оборудование: доска, компьютер, компьютерная презентация.

Этапы урока:

1. Организационный момент.

2. Изучение материала.

3. Подведение итогов урока.

4. Домашнее задание.

Ход урока.

Этап 1. Организационный момент.

Сегодня мы рассмотрим графический метод решения задач на примере.

Начинается показ слайда 1.

Этап 2. Изучение материала.

Рассмотрим графический метод решения задач на примере:

Возьмем участок оси абсцисс длиной 1, изображенного на слайде 2. Левый конец участка (точка с абсциссой х=0) будет изображать стратегию А₁; правый конец участка (х=1) — стратегию А₂. Проведем через точки А₁ и А₂ два перпендикуляра к оси абсцисс: ось I—I и ось II—II. На оси I—I будем откладывать выигрыши при стратегии А₁, на оси II—II —выигрыши при стратегии А₂.

Рассмотрим стратегию противника В₁, она дает две точки на осях I—I и II—II с ординатами соответственно а₁₁ и а₂₁. Проведем через эти точки прямую В₁В₁. Очевидно, если мы при стратегии противника B₁ будем применять смешанную стратегию, то наш средний выигрыш, равный в этом случае , изобразится точкой М на прямой В₁В₁; абсцисса этой точки равна р₂. Прямую В₁В₁, изображающую выигрыш при стратегии B₁ будем условно называть «стратегией B₁».

Очевидно, точно таким же способом может быть построена и стратегия В₂, изображенного на слайде 3.

Нам нужно найти оптимальную стратегию игрока А, т. е. такую, для которой минимальный выигрыш (при любом поведении В) обращался бы в максимум. Для этого построим нижнюю границу выигрыша при стратегиях B₁ B₂, т. е. ломаную B₁NB₂, отмеченную на слайде 3 жирной линией. Эта нижняя граница будет выражать минимальный выигрыш игрока А при любых его смешанных стратегиях; точка N, в которой этот минимальный выигрыш достигает максимума, и определяет решение и цену игры. Нетрудно убедиться, что ордината точки N есть цена игры v, а ее абсцисса равна р₂ — частоте применения стратегии А₂ в оптимальной смешанной стратегии игрока А.

В нашем случае решение игры определялось точкой пересечения стратегий. Однако это не всегда будет так; на слайде 4 показан случай, когда, несмотря на наличие пересечения стратегий, решение дает для обоих игроков чистые стратегии (А₂ и В₂), а цена игры v = a₂₂ В данном случае матрица имеет седловую точку, и стратегия А₁ является заведомо невыгодной, т. к. при любой чистой стратегии- противника она дает меньший выигрыш, чем А₂.

В случае, когда заведомо невыгодная стратегия имеется у противника, геометрическая интерпретация имеет вид, представленный на слайде 5.

В данном случае нижняя граница выигрыша совпадает со стратегией В₁; стратегия В₂ для противника является заведомо невыгодной. Геометрическая интерпретация дает возможность представить наглядно также нижнюю и верхнюю цены игры (слайд 6).

Мы убедились, что любая игра 2x2 может быть решена элементарными приемами. Совершенно аналогично может быть решена любая игра 2хn, где у нас имеются всего две стратегии, а у противника — произвольное число.

Пусть мы располагаем двумя стратегиями: A₁ A₂, а противник — n стратегиями: B₁, B₂,..., В_n. Матрица ||a_ij|| задана; она состоит из двух строк и n столбцов. Аналогично случаю двух стратегий дадим задаче геометрическую интерпретацию; n стратегий противника изобразятся n прямыми (слайд 7). Строим нижнюю границу выигрыша (ломаную B₁MNB₂ и находим на ней точку N с максимальной ординатой. Эта точка дает решение игры; ордината точки N равна цене игры v, а абсцисса равна частоте р₂ стратегии А₂.

В данном случае оптимальная стратегия противника получается применением смеси двух «полезных» стратегий: В₂ и B₄, пересекающихся в точке N. Стратегия В₃ является заведомо невыгодной, а стратегия В₁—невыгодной при оптимальной стратегии игрока А. Если А будет придерживаться своей оптимальной стратегии, то выигрыш не изменится, какой бы из своих «полезных» стратегий ни пользовался В, однако, он изменится, если В перейдет к стратегиям В₁ или В₃.

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

В частности, из этого следует, что у игры 2 x m всегда имеется решение, в котором с той и другой стороны участвует не более двух, «полезных» стратегий.

Пользуясь геометрической интерпретацией, можно дать простой способ решения любой игры 2 x m. Непосредственно но чертежу находим пару «полезных» стратегий противника B_j и В_k, пересекающиеся в точке N (если в точке N пересекается более двух стратегий, берем любые две из них). Мы знаем, что если игрок А придерживается своей оптимальной стратегии, то выигрыш не зависит от того, в какой пропорции применяет В свои «полезные» стратегии, следовательно, Из этих уравнений и условия , находим р₁, р₂ и цену игры v.

Зная цену игры, можно сразу определить оптимальную стратегию игрока В. Для этого решается, например, уравнение: , где .

В случае, когда мы располагаем m стратегиями, а противник — всего двумя, очевидно, задача решается совершенно аналогичным способом; достаточно заметить, что, изменяя знак выигрыша на обратный, можно превратить игрока А из «выигрывающего» в «проигрывающего». Можно решить игру и без перемены знака выигрыша; тогда задача решается непосредственно для В, но строится не нижняя, а верхняя граница выигрыша (слайд 8). На границе ищется точка N с минимальной ординатой, которая и есть цена игры v.

Этап 3. Подведение итогов урока.

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

а) б)

Этап 4. Домашнее задание.

Прочитать конспект.

Решить задания: а) б)

Слайд шоу к уроку:

слайд 1 слайд 2

слайд 3 слайд 4

слайд 5 слайд 6

слайд 7 слайд 8

Урок 4.

Тема: Сведение задач к линейному программированию.

Цель: Научить решению задач линейного программирования симплекс-методом.

Задачи:

1. Дать представление о симплекс-методе.

2. Научить сводить задачи к симплекс-методу.

3. Закрепить материал.

4. Задать домашнее задание.

Продолжительность урока: 40 минут.

Этапы урока:

1. Организационный момент.

2. Изучение материала.

3. Подведение итогов урока.

4. Домашнее задание.

Ход урока.

Этап 2. Изучение материала.

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

Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с n неотрицательными переменными: (X1, ..., Xn), где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (X1, ..., Xm), которые должны иметь неотрицательные значения, когда остальные (n-m) свободные переменные равны 0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1:

X₀ + A_{0, m+1}*X_m+1 +... + A_{0, n}*X_n = A_{0, 0} X₁ + A_{1, m+1}*X_m+1 +... + A_{1, n}*X_n = A_{1, 0} .................. X_i + A_{i, m+1}*X_m+1 +... + A_{i, n}*X_n = A_{i, 0} .................. X_m + A_{m, m+1}*X_m+1 +... + A_{m, n}*X_n = A_{m, 0}

Данная формальная модель задачи линейного программирования обычно задается в форме так называемой симплекс-таблицы, удобной для выполнения операций симплекс-метода:

Симплекс-таблица

		X₁	X₂	...	X_m	X_m+1	...	X_n
X₀	A_{0, 0}			...		A_{0, m+1}	...	A_{0, n}
X₁	A_{1, 0}			...		A_{1, m+1}	...	A_{1, n}
X₂	A_{2, 0}			...		A_{2, m+1}	...	A_{2, n}
...	...	...	...	...	...	...	...	...
X_m	A_{m, 0}			...		A_{m, m+1}	...	A_{m, n}

Верхняя строка симплекс-таблицы представляет целевую функцию задачи. Каждая строка симплекс-таблицы, кроме первой, соответствует определенному ограничению-равенству задачи. Свободные члены ограничений составляют крайний левый столбец таблицы. Слева от таблицы записаны текущие базисные переменные (X1, ..., Xm). Сверху от таблицы приведен набор всех переменных задачи, где Xm+1, ..., Xn - свободные переменные задачи.

Преобразования таблицы надо производить до тех пор, пока не будет получена симплекс-таблица, которая одновременно является прямо и двойственно допустимой.

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

Этап 3. Подведение итогов урока.

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

2) за компьютером на MS Excel

Решить симплекс-методом задачу ЛП, начав с указанного опорного плана и взяв в качестве базисных переменных .

№	a	b	c	№	a	b	c
			-1

			-1




					-2		-1




			-1

Этап 4. Домашнее задание.

Прочитать конспект.

Решить пример симплекс-методом:

⇐ Предыдущая 1 2 3 4 5 67