9. Метод потенциалов.

Метод потенциалов позволяет, исходя из некоторого опорного плана, построить за конечное число итераций решение Т-задачи.

Общая схема метода такова. В данном начальном опорном плане перевозок каждому пункту ставят в соответствие некоторое число, называемое его предварительным потенциалом. Предварительные потенциалы выбирают так, чтобы их разность для любой пары пунктов A_i i B_j, связанных основной коммуникацией, была равна c_ij. Если окажется, что разность предварительных потенциалов для всех других коммуникаций не превосходит c_ij, то данный план перевозок – оптимальное решение задачи. В противном случае указывают способ улучшения текущего плана Т-задачи.

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

На предварительном этапе строят начальный опорный план и составляют матрицу С1.

Предварительный этап. С помощью известного метода (например северо-западного угла или минимального элемента) определяют начальный опорный план Х₀ и вычисляют предварительные потенциалы .

Первый этап. Вычисляют матрицу С_k+1. Преобразвание матрицы С_k в матрицу С_k+1 состоит в следующем. Выбирают наибольший по модулю отрицательный элемент С_k

 Пусть это элемент . Тогда вычеркивают (или выделяют) строку, в которой он содержится. Просматривают эту строку и отыскивают множество существенных его элементов.Х_k -существенными элементами называют те элементы =0, которые отвечают базисным элементам планаХ_k т.е. для которых . Вычеркивают столбцы, которые содержат эти элементы. Далее просматривают вычеркнутые столбцы и ищут в них новые существенные элементы, которые лежат в строках отличных от уже вычеркнутых ранее. Если такие элементы имеются, то вычеркивают строки, в которых они содержатся. Процесс выделения продолжают до тех пор,  пока очередное множество новых существенных элементов не окажется пустым. Поскольку каждые строка и столбец не могут быть выделены дважды, то весь процесс заканчивается не более чем заl =m+ n – 1 шагов. Далее строят матрицу С_k+1. Для этого величину прибавляют ко всем элементам выделенных строк и вычитают из элементов всех выделенных столбцов матрицыС_k. При этом все существенные элементы матрицы С_k остаются равными нулю, а кроме того, в нуль превращается и элемент .

Если все элементы матрицы С_k+1 окажутся неотрицательными, то X_k – оптимальный план, и на этом процесс заканчивается. В противном случае переходят ко второму этапу.

Второй этап. Цель этого этапа – построить более экономичный план Х_k+1. Выбирают наибольший по модулю отрицательный элемент матрицы С_k+1.

10. Пример игры с двумя пальцами.

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