13. Метод потенциалов
Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке совершает поворот на 90 , Знаком " + " отмечают те вершины, в которых перевозки увеличиваются, а знаком "- " - те вершины, в которых перевозки уменьшаются. Перемещение какого-то количества единиц груза по циклу означает увеличение перевозок на это количество единиц в положительных вершинах и уменьшение перевозок на это же количество единиц в отрицательных вершинах. При этом, если перевозки остаются неотрицательными, план остается допустимым. Стоимость плана при этом может меняться.
Ценой цикла называется увеличение стоимости перевозок при перемещении единицы груза по этому циклу. Очевидно, цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, при этом стоимости в положительных вершинах берутся со знаком " +", а стоимости в отрицательных вершинах берутся со знаком " - ".
Идея метода потенциалов состоит в следующем. Для любой свободной клетки транспортной таблицы всегда существует единственный цикл, положительная вершина которого лежит в этой свободной клетке, а все остальные - в базисных. Если цена такого цикла отрицательна, то план можно улучшить перемещением перевозок по данному циклу. Количество единиц груза, которое можно переместить, определяется минимальным значением перевозок, стоящих в отрицательных вершинах цикла (если переместить большее число единиц груза, возникнут отрицательные перевозки). Если циклов с отрицательной ценой нет, то это означает, что дальнейшее улучшение плана невозможно, т.е. оптимальный план найден.
Для нахождения циклов с отрицательной ценой вводится система
платежей
и определяются величины
называемые "псевдостоимостями" перевозок единицы груза из пункта i
в пункт j. При этом цена цикла пересчета для каждой свободной клетки
равна
если платежи
для всех базисных клеток (i, j)
9.9 Вычислительная схема метода потенциалов [1, 3]
Шаг 1. Строим опорный план (методом северо-западного угла) с
n+m-1 базисными клетками.
Шаг 2. Определяем платежи
для всех базисных клеток. Один из платежей (например a1 ) полагаем равньм нулю.
Шаг 3. Считаем псевдостоимости
для всех свободных клеток. Если
для всех клеток, то план оптимален. Вычисляем значение целевой функции L на этом плане и исследования прекращаем.
Шаг 4. Если есть свободная клетка, для которой
то улучшаем план, перебрасывая перевозки по циклу этой свободной клетки.
Шаг 5. Возвращаемся к шагу 2 для пересчета платежей нового опорного плана.
Пример
Решить методом потенциалов транспортную задачу
Опорный план этой задачи найден методом северо-западного угла.
Приписываем к таблице добавочную строку для платежей
и добавляем столбец для платежей
Псевдостоимости записываем в левом углу клетки, а стоимости - в правом углу.
Из условий
в базисных клетках получаем систему уравнений
Полагая 
,
находим последовательно платежи
и псевдостоимости для свободных клеток. Получаем таблицу
Стоимость перевозок по плану этой таблицы
Так как клетка (1,3) имеет отрицательную цену
то план не является оптимальным. Строим для клетки (1,3) цикл. Цена
цикла. 
По циклу переносим 20 единиц груза (больше нельзя, чтобы перевозки в клетке (1, 2) не стали отрицательными).При
этом стоимость плана уменьшается на
Для нового плана вычисляем новые значения платежей и псевдостоимостей:
Стоимость перевозок по плану этой таблицы
Полученная таблица имеет клетку (2,1 ) с отрицательной ценой
По циклу этой клетки переносим 10 единиц груза,
при этом стоимость плана уменьшается на
единиц, и получаем новый опорный план с новой системой платежей и псевдостоимостей:
Стоимость перевозок по плану этой таблицы
Так как в последней таблице все псевдостоимости не превосходят
соответствующих стоимостей, то полученный опорный план
является оптимальным. Стоимость перевозок при этом
14. ИГРА С “ПРИРОДОЙ” [game with nature] — игра, в которой имеется только один игрок, причем исход ее зависит не только от его решений, но и от состояния “природы”, т. е. не от сознательно противодействующего противника, но от объективной, невраждебной действительности. Платежная матрица в этом случае похожа на показанную в ст. “Матрица игры”, но здесь игрок X — это лицо, принимающее одно из m различных возможных решений, а игрок Y — “природа”, принимающая nвозможных состояний. При выборе решения игроком X могут использоваться различные критерии, напр.:
критерий Лапласа (“принцип недостаточного основания”), предполагающий, что все состояния одинаково вероятны, поэтому следует выбирать такую стратегию, которая максимизирует средний выигрыш по строке;
принцип максимакса, предполагающий, что Y — это доброжелательный партнер, поэтому следует выбирать строку с наибольшим из всех максимальных элементов по столбцам;
критерий максимаксного сожаления (риска), при котором любое решение сопоставляется с тем решением, которое было бы принято, если бы было известно состояние “природы”.
Критерий Сэвиджа — один из критериев принятия решений в условиях неопределённости. Условиями неопределённости считается ситуация, когда последствия принимаемых решений неизвестны, и можно лишь приблизительно их оценить. Для принятия решения используются различные критерии, задача которых — найти наилучшее решение максимизирующее возможную прибыль и минимизирующее возможный убыток.
Критерий заключается в следующем:
Строится матрица стратегий (платёжная матрица). Столбцы соответствуют возможным исходам. Строки соответствуют выбираемым стратегиям. В ячейки записывается ожидаемый результат при данном исходе и при данной выбранной стратегии.
Строится матрица сожаления (матрица рисков). В ячейках матрицы величина сожаления — разница между максимальным результатом при данном исходе (максимальном числе в данном столбце) и результатом при выбранной стратегии. Сожаление показывает величину, теряемую при принятии неверного решения.
Минимаксное решение соответствует стратегии, при которой максимальное сожаление минимально. Для этого для каждой стратегии (в каждой строке) ищут максимальную величину сожаления. И выбирают то решение (строку), максимальное сожаление которого минимально.
Критерий Вальда (максиминный критерий[1]) — один из критериев принятия решений в условиях неопределённости. Критерий крайнего пессимизма.
Коэффициент Гурвица, также Критерий Гурвича (англ. Hurwicz criterion) — в теории принятия решений один из критериев принятия решений в условиях неопределённости. Позволяет с помощью параметра λ руководствоваться промежуточным случаем между крайним оптимизмом и крайним пессимизмом. Впервые выдвинут американским экономистом русского происхождения Леонидом Гурвичем в 1950.
15. Тео́рия игр — математический метод изучения оптимальных стратегий в играх. Под игрой понимается процесс, в котором участвуют две и более сторон, ведущих борьбу за реализацию своих интересов. Каждая из сторон имеет свою цель и использует некоторую стратегию, которая может вести к выигрышу или проигрышу — в зависимости от поведения других игроков. Теория игр помогает выбрать лучшие стратегии с учётом представлений о других участниках, их ресурсах и их возможных поступках.[1]
Теория игр — это раздел прикладной математики, точнее — исследования операций. Чаще всего методы теории игр находят применение в экономике, чуть реже в другихобщественных науках — социологии, политологии, психологии, этике и других. Начиная с 1970-х годов её взяли на вооружение биологи для исследования поведения животных и теории эволюции. Очень важное значение она имеет для искусственного интеллекта и кибернетики, особенно с проявлением интереса к интеллектуальным агентам.