27.Линейное программирование. Решение задачи методом потенциалов.

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

Алгоритм

Метод потенциалов является модификацией симплекс-метода, в котором базисная матрица B[M, N_B] представлена в виде дерева.Двойственные переменные симплекс-метода для транспортной задачи называются потенциалами.

Потенциалы P[M] вычисляются по формуле C[N_B]=B[M, N_B]P[M], что эквивалентно P[M]= C[N_B]B^-1[N_B,M]

Для дуги потенциалы дуг связаны формулой P[i]+C[n]=P[j].

Таким образом, потенциал потребителя равна потенциалу производителя + стоимость перевозки. С экономической точки зрения это можно трактовать как стоимость продукта в точке потребления.

Проверка оптимальности плана P[i]+C[n]>=P[j] легко трактуется с экономической точки зрения — если стоимость продукта в точке потребления больше стоимости в точке производства + цена перевоза, по этой дуге следует везти. Величина P[j]-P[i]-C[n] называется невязкой дуги.

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

Остается только пересчитать потенциалы — добавить (или вычесть — зависит от направления дуги) ко всем вершинам «повисшей ветки» величину невязки P[j]- P[i]-C[n]

Процесс завершается, когда условие оптимальности P[i]+C[n]>=P[j] выполняется для всех дуг.

28. Решение интегрального уравнения методом замены ядра уравнения на вырожденное.

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

(1

Аппроксимация ядра вырожденным

Некоторые сведения об уравнениях с вырожденным ядром. Ядро уравненияK(x,s) называют вырожденным, если оно представимо в виде

(9)

Функции_i (i = 1,…, n) можно, очевидно, считать линейно независимыми. Аналогичное можно сказать о функциях _i (i = 1,…, n).

Когда в интегральном уравнении (5) ядро K(x,s)имеет форму (9), то его решение, если оно существует, представимо в следующем виде:

(10)

где коэффициенты A_i есть некоторые неизвестные постоянные

Для нахождения этих коэффициентов может быть просто построена линейная система уравнений. Введем следующие обозначения:

Подставим в уравнение (5)вместоу представление (10):

Ввиду линейной независимости функций _i(x) коэффициенты при них в левой и правой частях равенства должны быть одинаковыми и после сравнения их мы получим систему уравнений для A_i:

. (11)

Построение решения у(x) приводит в случае вырожденного ядра K(x,s) к вычислению величинf_i, _ij и к решению линейной системы (11).

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