7.2.1.2 Венгерский метод

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

Алгоритм венгерского метода состоит из подготовительного этапа и из конечного числа итераций. На подготовительном этапе строится матрица X₀ (x_ij[0])_m,n, элементы которой неотрицательны и удовлетворяют неравенствам:

, i 1, …, m; (7.30)

, j 1, …, m. (7.31)

Если эти условия являются равенствами, то матрица Х_o - решение транспортной задачи. Если среди условий имеются неравенства, то осуществляется переход к первой итерации. На k-й итерации строится матрица Х_k (x_ij[0])_m,n. Близость этой матрицы к решению задачи характеризует число _k — суммарная невязка матрицы Х_k:

. (7.32)

В результате первой итерации строится матрица Х_l, состоящая из неотрицательных элементов. При этом _l ₀. Если _l 0, то Х_l - оптимальное решение задачи. Если _l 0, то переходят к следующей итерации. Они проводятся до тех пор, пока _k при некотором k не станет равным нулю. Соответствующая матрица Х_k является решением транспортной задачи.

Венгерский метод наиболее эффективен при решении транспортных задач с целочисленными объемами производства и потребления. В этом случае число итераций не превышает величины ₀/2 (₀ ‑ суммарная невязка подготовительного этапа).

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

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

Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Общая схема отдельной итерации такова. По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам А_i соответствуют числа u_i, пунктам B_j ‑ числа v_j. Они выбираются таким образом, чтобы их разность на k-й итерации была равна С_ij - стоимости перевозки единицы продукции между пунктами А_i и В_j:

v_j[k] – u_i[k] C_ij, i 1, ..., m; j 1, …, п. (7.33)

Если разность предварительных потенциалов для каждой пары пунктов А_i, В_j не превосходит С_ij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.

7.3 Прямые методы условной оптимизации

7.3.1 Основные определения

Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции f(x)n-мерного векторного аргументах (в дальнейшем без ограничения общности будут рассматриваться задачи поиска минимального значения функции):

f(x)min (7.34)

при ограничениях:

g_i(x) 0, i 1, ..., k;

h_j(x) 0, j 1, .., m; (7.35)

a x b.

Здесь x, a, b— векторы-столбцы:

, , (7.36)

Оптимизируемую функцию f(x)называютцелевой функцией.Каждая точкаxвn-мерном пространстве переменныхx₁, ...,х,в которой выполняются ограничения задачи, называетсядопустимой точкой задачи.Множество всех допустимых точек называетсядопустимой областью G .Будем считать, что это множество не пусто.Решением задачисчитается допустимая точках*, в которой целевая функцияf(х)достигает своего минимального значения. Векторх*называютоптимальным.Если целевая функцияf(x)и ограничения задачи представляют собой линейные функции независимых переменныхх₁, ..., х_n, то соответствующая задача являетсязадачей линейного программировании,в противном случае -задачей нелинейного программирования.В дальнейшем будем полагать, что функцииf(x), g(x), i 1, ..., k , h_j(x), j 1, …, m, -непрерывные и дифференцируемые.

В общем случае численные методы решения задач нелинейного программирования можно разделить на прямые и непрямые. Прямые методыоперируют непосредственно с исходными задачами оптимизации и генерируют последовательности точек {x[k]}, таких, чтоf(х[k+1]) f(x[k]).В силу этого такие методы часто называютметодами спуска.Математически переход на некоторомk-м шаге(k. 0, 1, 2, ...) от точких[k] к точкеx[k+1] можно записать в следующем виде:

x[k+l] x[k] + a_kp[k], (7.37)

где р[k] —вектор, определяющий направление спуска;а_k —длина шага вдоль данного направления. При этом в одних алгоритмах прямых методов точких[k] выбираются так, чтобы для них выполнялись все ограничения задачи, в других эти ограничения могут нарушаться на некоторых или всех итерациях. Таким образом, в прямых методах при выборе направления спуска ограничения, определяющие допустимую областьG,учитываются в явном виде.

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

Рассмотрим некоторые алгоритмы прямых методов.