Метод минимального элемента:

Выбираем клетку, которая находится на «северо-западе», т.е. крайняя верхняя левая клетка (обозначим ее исходными символами i и j)

Начинаем считать.

Если , то ставим в клетку значение . При этом все остальные клетки строчки i будут заполнены прочерками.

Если , то ставим в клетку значение , а все клетки столбца j заполняем прочерками.

Если , то ставим в клетку значение, равное обоим числам, а во всех столбцах и строчках ставим прочерки.

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

Метод минимального элемента:

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

14. Метод потенциала, цикл.

Метод потенциала заключается в следующем:

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

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

Значение называется «псевдостоимостью» перевозки груза из пункта поставщика i в пункт потребителя j.

Оптимальным будет являться план, при котором потребитель и поставщик не будут переплачивать сверх объективной стоимости «перевозчику».

Цикл – последовательный набор клеток, в котором любые 2 клетки находятся в одной строке или столбце таблицы. И никакие 3 соседние клетки не находятся в одной строке или столбце. Первая и последняя клетка цикла должна быть из одной строки или столбца.

15. Конфликты интересов. Матричные игры с нулевой суммой.

«Нулевая сумма» - понятие, означающее, что выигрыш одного игрока в одной игре будет равен проигрышу другого игрока. Ярким примером такой игры будет «Орлянка». Ее суть состоит в том, что при выпадении одной стороны монеты выигрывает один игрок и наоборот. Если выигрывает первый, второй проигрывает ровно ту сумму, которую первый выиграл. Такая игра еще называется антагонистической.

– объекты матричной игры с нулевой суммой, где

и - множество стратегий первого и второго игрока

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

16. Смешанные стратегии, чистые стратегии.

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

Чистая стратегия являет собой полную определенность, как будет действовать игрок.

Смешанная стратегия – это набор вероятностей, с которой игрок будет выбирать одну из чистых стратегий.

Смешанная стратегия первого игрока – вектор вероятности выбора стратегии p=( )

Смешанная стратегия второго игрока q=( )

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

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

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

17. Оптимальное решение игры в смешанных стратегиях. Оптимальное решение игры в чистых стратегиях. Седловая точка.

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

V = H( ) – цена игры, если

H( ) ≤ v = H( ) ≤ H( )

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

Седловая точка матрица – это элемент, который минимален в своей строке и максимален в своем столбце.

18. Верхняя цена игры, нижняя цена игры.

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

Нижняя цена игры равняется максимальному значению из возможных минимальных значений строк. , где - минимальное значение в строке, i – количество строк.

В случае, когда верхняя цена равна нижней ( ) – матричная игра решается в чистых стратегиях.

В противном случае ( ) – в смешанных стратегиях.

19. Основная теорема матричных игр.

Теорема фон Неймана. Каждая игра имеет хотя бы одно оптимальное решение в смешанных стратегиях.

Любая матричная игра разрешима в смешанных стратегиях, при этом:

Maxmin H (p,q)=	min	Max H (p,q)=v
p	q	p

( ) - оптимальное решение,

где - смешанная максиминная стратегия.

min H ( ,q)=	max	min H (p,q)
q	p	q

Где - смешанная минимаксная стратегия

max H (p, )=	min	max H (p,q)
p	q	p

20. Кооперативная игра, коалиции и дележи, С-ядро, цена Шепли.

Кооперативные игры получаются в тех случаях, когда, в игре n игроков разрешается образовывать определённые коалиции.

Игра называется кооперативной, или коалиционной, если игроки могут объединяться в группы, беря на себя некоторые обязательства перед другими игроками и координируя свои действия.

Кооперативной игрой в форме характеристической форме называется пара G = (N,V) где N={1,2,...,n} – конечное множество, называемое множеством игроков.

V – функция ставящая в соответствие каждому непустому подмножеству множества N вещественное число,

V: , V-характеристическая функция.

Непустое подмножество S множества N называется коалицией.

Максимальной или главной коалицией называется коалиция состоящая из всех игроков.

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

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

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

и для любой коалиции выполнено:

где u – характеристическая функция.

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