Математика (3 сем-р) (стр. 4 )

Если все неотрицательны, значит, опорный план оптимален, и решение закончено.

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

3. Пересчёт по циклу.

Для избранной свободной клетки строится цикл пересчёта.

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

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

В последнем случае место пересечения двух линий цикла не входит в сам цикл, поскольку в вершинах цикла, которые, собственно, только и входят в цикл, совершается поворот на 90 0.

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

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

Поставка , перредаваемая по циклу, определяется как минимум среди поставок в клетках со знаком «-»: .

Найденная поставка передвигается по циклу. В клетках со знаком «+» она увеличивается на единиц, а в клетках с «-» - уменьшается на . Клетка, в которой поставка стала равна нулю считается свободной. Поскольку в цикле чётное число вершин, то в пределах цикла общий объём перевозок не изменится, что не приведет к нарушению баланса между запасами и заявками.

Получаем новое базисное распределение.

4. Переходим к п.2.

Пример 1 решить методом потенциалов.

Особые случаи:

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

2. Если при переводе поставки по циклу, поставка обращается в нуль сразу в нескольких заполненных клетках, то свободной из них следует считать только одну (любую), остальные клетки будут заполнены нулевой поставкой.

Пример 2 решить методом потенциалов.

В.4. Другие типы транспортных задач

4.1. Открытые модели ТЗ ()

1. У поставщиков имеются избыточные запасы товара, т. е. .

Экономико-математическая модель такой ТЗ также является ЗЛП:

(8)

Обратите внимание, что вместо уравнений (1) в модели (8) появились неравенства, означающие, что не все товары будут вывезены с баз.

Введение дополнительных (балансовых) переменных в эти неравенства для получения канонического вида модели эквивалентно введению (n+1)-го (фиктивного) потребителя, т. е. дополнительного столбца в таблице поставок.

Спрос фиктивного потребителя равен:, а тарифы соответствуют затратам на хранение неотправленного груза. Если же информация об этих издержках отсутствует, то тарифы клеток дополнительного столбца принимаются равными одному и тому же числу, например, нулю, т. е. . Таким образом, получаем закрытую модель ТЗ. Эта задача решается обычными методами, рассмотренными выше. При этом в некоторых клетках дополнительного столбца после оптимального решения остаются ненулевые значения перевозок (фиктивные значения); значит, с соответствующих баз не вывезены остатки товаров.

2. Открытая модель ТЗ с дефицитом ресурсов, т. е. (спрос превышает предложение).

ЭММ имеет вид: (9)

Обратите внимание на то, что вместо системы уравнений (2) записана система неравенств. Вводим «фиктивного» поставщика (т. е. дополнительную строку) с номером (m+1) и запасом груза в нем, равным: . Тарифы определяются издержками из-за недогрузки мощностей потребителей. Если же информация о них отсутствует, то . Перевозки в этих клетках являются балансовыми переменными. В результате получаем закрытую модель ТЗ и решаем её обычными методами. При этом в оптимальном решении некоторые из дополнительных клеток обязательно будут заполнены ненулевыми значениями перевозок. Смысл этих значений - недополученный груз соответствующими заказчиками.

Пример 3. Найти оптимальное распределение поставок для следующей ТЗ:

Поставщики	Запасы	Потребители, спрос
B1	B2	B3	B4
45	35	55	65
А1	40	4	1	2	5
А2	60	3	2	3	7
А3	90	4	4	5	2

4.2. Транспортная задача по критерию времени

В некоторых транспортных задачах вместо тарифов задают величины tij – время доставки товара от i-го поставщика к j-му потребителю (например, при перевозках скоропортящихся грузов). Требуется найти план перевозок, при котором будет затрачено минимальное время. Эта задача не является ЗЛП, поскольку целевая функция не линейна относительно переменных xij. Рассмотрим метод решения этой задачи, который называется «методом запрещенных клеток».

Алгоритм решения (для закрытой модели ТЗ) содержит следующие этапы:

1)  Находим опорное решение, например, методом северо-западного угла.

2)  Находим время, затрачиваемое на этот план: , т. е. самое продолжительное время перевозок в занятых клетках.

3)  Пытаемся улучшить решение, для чего:

a)  Вычеркиваем свободные клетки, в которых время перевозки не меньше, чем Т1 (эти клетки нет смысла занимать)

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

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

Пример 4. Решить ТЗ по критерию времени (рассмотрим таблицу с планом перевозок по методу С-З угла).

bj ai	50	60	30	80
70	4 50 -	2 20 +	1 -	6 -
90	1 - +	3 40 -	3 30	2 20
60	3 -	6 -	4 -	3 60

Отметим запрещенные клетки. Целевая функция имеет значение T1=max(4;2;3;3;2;3)=4=t11. Расставим разгрузочную цепь и знаки – плюсы и минусы – в вершинах. Перебрасываемая величина D=min(50;40)=40 (минимум берем по перевозкам в отрицательных вершинах). Значение этой величины вычитаем из отрицательных вершин и прибавляем к положительным вершинам цепи, получаем новый опорный план:

bj ai	50	60	30	80
70	4 10 -	2 60	1 - +	6 -
90	1 40 +	3 -	3 30 -	2 20
60	3 -	6 -	4 -	3 60

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

bj ai	50	60	30	80
70	4 -	2 60	1 10	6 -
90	1 50	3 -	3 20	2 20
60	3 -	6 -	4 -	3 60

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

Тема 5. Теория игр

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

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

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

(В экономике конфликтные ситуации: взаимоотношения между поставщиком и потребителем, банком и клиентом и т. д.)

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

Игроки – стороны, участвующие в конфликте. Выигрыш – исход конфликта.

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

Правила – система условий, определяющая: варианты действий игроков; объём информации каждого игрока о поведении партнёра; выигрыш, к которому приводит каждая совокупность действий.

Обычно выигрыш или проигрыш в игре может быть задан количественно (например, выигрыш «1», проигрыш «-1», ничья – «0»).

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

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

Стратегия – это последовательность всех ходов до окончания игры. Термин партия связан с частичной возможной реализацией правил.

Классификация игр:

-  По количеству игроков игры бывают парные (n=2) и множественные (n>2).

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

-  Игры бывают с нулевой суммой, если одни выигрывают за счет других.

-  Парные игры с нулевой суммой называются антагонистическими.

-  Конечные антагонистические игры называются матричными.

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

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

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

В. 2. Матричные игры. Нижняя и верхняя цена игры

Пусть игрок А имеет m возможных стратегий (A1, A2,…,Am), а другой игрок В – n возможных стратегий (B1,B2,…,Bn). Т. е. игра имеет размерность . В результате выбора игроками каждой пары стратегий (Ai, Bj) однозначно определяется исход игры, т. е. выигрыш игрока А (или проигрыш игрока В).

Матрица , элементами которой являются выигрыши игрока А, соответствующие стратегиям (Ai, Bj), называется платёжной матрицей (матрицей игры):

или

При этом значение выигрыша может быть меньше нуля.

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

Пример 1. Игра «прятки»: Игрок А может спрятаться в одном из двух убежищ. Игрок В ищет А и, если находит, то получает от А 1 у. е. Если В не находит А, то В платит А 1 у. е. Составить платёжную матрицу игры.

Решение. У игрока А 2 стратегии: А1 – спрятаться в 1-ом убежище, А2 – спрятаться во 2-ом.

У В тоже 2 стратегии: В1 – искать в 1-ом убежище, В2 – искать во 2-ом. Т. е. игра имеет размерность 22. Если А спрячется в 1-ом убежище и В будет искать его в 1-м (т. е. (A1, B1)), то игрок А заплатит игроку В 1 у. е. (). Т. о. платёжная матрица игры имеет вид:

.

Рассмотрим игру с платёжной матрицей.

Определим наилучшую стратегию игрока А.

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

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

Соответствующие стратегии первого игрока называются максиминными, а второго – минимаксными.

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