Математические методы экономических исследований

Итак, этапы решения задачи методом Франка-Вулфа заключаются в следующем:

1. Определяют одно из допустимых решений.

2. Находят градиент функции f в точке допустимого решения.

3. Строят функцию F и находят ее максимальное значение при условиях исходной задачи.

4. Определяют шаг вычислений.

5. По формуле X(k+1) = X(k) + lk(Z(k) - X(k)) находят следующее допустимое решение.

Проверяют необходимость перехода к следующему допустимому решению. В случае необходимости переходят к этапу 2, если такой необходимости нет, то приемлемое решение найдено.

Метод штрафных функций

Пусть имеем вогнутую функцию f(x1, x2, ., xn). Необходимо найти максимум этой функции при условиях: gi(x1, x2, ., xn) £ bi, (i = 1, 2, .,m), xj ³ 0, где gi - выпуклые функции.

Строится функция: F (x1, x2, ., xn) = f (x1, x2, ., xn)+H (x1, x2, ., xn), где функция H(x1, x2, ., xn) определяется системой ограничений и называется штрафной функцией. Она может быть построена многими способами. Чаще всего эта функция строится в виде:

, где

ai ‑ весовые коэффициенты,

qi = bi - gi .

Используя H, последовательно переходят от одной точки к другой до тех пор, пока получится приемлемое решение. При этом координаты последующей точки находят по формуле:

(Б.3)

Из (Б.3) следует, что если предыдущая точка находится в области допустимых решений, то второе слагаемое в квадратных скобках равно 0, и переход к последующей точке определяется только градиентом целевой функции. Если же предыдущая точка не принадлежит области допустимых решений, то за счет указанного слагаемого на последующих итерациях достигается возвращение в область допустимых решений. При этом, чем меньше  i, тем быстрее находится приемлемое решение, но точность определения решения снижается. Поэтому в начале  i берут малым, постепенно увеличивая.

Итак, процесс решения включает этапы:

1. Определяют исходное допустимое решение.

2. Выбирают шаг вычислений.

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

4. По (Б.3) определяют координаты точки - возможное новое решение.

5. Проверяют, удовлетворяют ли координаты найденной точки системе ограничений задачи. Если не удовлетворяют, то переходят к следующему этапу. Если координаты найденной точки определяют допустимое решение задачи, то исследуют необходимость перехода к последующему решению. Если такой переход необходим, то переходят к пункту 2, иначе решение найдено.

6. Устанавливаются значения весовых коэффициентов и переходят к этапу 4.

 Скачать реферат