Решение систем уравнений методом прогонки примеры

Метод прогонки

Пример №1 . Решить задачу методом динамического программирования в прямом и обратном времени для целевой функции, заданной таблично.
F(x₁,x₂,x₃) = f₁(x₁) + f₂(x₂) + f₃(x₃) → max
x₁ + 2x₂ + 2x₃ ≤ 5

Решение.
I этап. Условная оптимизация. f₁(L) = max(f₁); 0 ≤ x₁ ≤ 5; x₁ = 0,1,2,3,4,5.
f₁(0) = max[6] = 6
f₁(1) = max[6, 7] = 7
f₁(2) = max[6, 7, 11] = 11
f₁(3) = max[6, 7, 11, 12] = 12
f₁(4) = max[6, 7, 11, 12, 15] = 15
f₁(5) = max[6, 7, 11, 12, 15, 16] = 16
Таблица 1 – Расчет значения функции f₁(L)

f₂(L) = max[f₂ + f₁(L — 2x₂)]; 0 ≤ x₂ ≤ 5; x₂ = 0,1,2,3,4,5.
f₂(0) = max[9+6] = 15
f₂(1) = max[9+7] = 16
f₂(2) = max[9+11, 11+6] = 20
f₂(3) = max[9+12, 11+7] = 21
f₂(4) = max[9+15, 11+11, 13+6] = 24
f₂(5) = max[9+16, 11+12, 13+7] = 25
Таблица 2 – Расчет значения функции f₂(L)

f₃(L) = max[f₃ + f₂(L — 2x₃)]; 0 ≤ x₃ ≤ 5; x₃ = 0,1,2,3,4,5.
f₃(0) = max[8+15] = 23
f₃(1) = max[8+16] = 24
f₃(2) = max[8+20, 12+15] = 28
f₃(3) = max[8+21, 12+16] = 29
f₃(4) = max[8+24, 12+20, 14+15] = 32
f₃(5) = max[8+25, 12+21, 14+16] = 33
Таблица 3 – Расчет значения функции f₃(L)

II этап. Безусловная оптимизация.
Таким образом, максимум f₃(5) = 33
При этом x₃ = 0, так как f₃(5) = 33 достигается при х₃=0 (см. таблицу 3).
Остальные x распределяются следующим образом:
L = 5 — 2 * 0 = 5
f₂(5) = 25 достигается при х₂ = 0 (см. таблицу 2).
L = 5 — 2 * 0 = 5
f₁(5) = 16 достигается при х₁ = 5 (см. таблицу 1).
L = 5 — 1 * 5 = 0
В итоге наилучший вариант достигается при значениях: x₁ = 5, x₂ = 0, x₃ = 0

Пример №2 . Рассмотрим задачу об оптимальном размещении капитала K = nh в m различных независимых фондах (банки, организации, фирма и т.д.), для которых известна ожидаемая прибыль f_i при капиталовложениях x_i = ih, i = 1..n. Здесь n – количество дискретных приращений h (дискрет), на которые разбит капитал К.
Пусть такие данные имеются по четырем (m=4) фондам для h = 1 млн. руб., n = 6

Решение.
I этап. Условная оптимизация.
1-й шаг: k = 4.
Предположим, что все средства в количестве x₄ = 6 отданы 4-у предприятию. В этом случае максимальный доход, как это видно из таблицы 1*, составит 0.56, следовательно:
F₄(c₄) = g₄(x₄)
Таблица 1.

Таблица 1*.

2-й шаг: k = 3.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F₃(c₃) = max [ g₃(x₃) + F₄(c_{3 — x3})]
Таблица 2.

Заполняем таблицу 2*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x₂.
Таблица 2*.

3-й шаг: k = 2.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F₂(c₂) = max [ g₂(x₂) + F₃(c_{2 — x2})]
Таблица 3.

Заполняем таблицу 3*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x₃.
Таблица 3*.

4-й шаг: k = 1.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F₁(c₁) = max [ g₁(x₁) + F₂(c_{1 — x1})]
Таблица 4.

Заполняем таблицу 4*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x₄.
Таблица 4*.

II этап. Безусловная оптимизация.
1-й шаг: k = 1.
По данным таблицы 4* максимальный доход при распределении 6 между предприятиями составляет c₁ = 6, F₁(6) = 1.26. При этом 1-му предприятию нужно выделить x₁ = 3.
2-й шаг: k = 2.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c₂ = c₁ — x₁ = 6 — 3 = 3.
По данным таблицы 3* максимальный доход при распределении 3 между предприятиями составляет c₂ = 3, F₂(3) = 0.61. При этом 2-му предприятию нужно выделить x₂ = 2.
3-й шаг: k = 3.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c₃ = c₂ — x₂ = 3 — 2 = 1.
По данным таблицы 2* максимальный доход при распределении 1 между предприятиями составляет c₃ = 1, F₃(1) = 0.2. При этом 3-му предприятию нужно выделить x₃ = 0.
4-й шаг: k = 4.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c₄ = c₃ — x₃ = 1 — 0 = 1.
По данным таблицы 1* максимальный доход при распределении 1 между предприятиями составляет c₄ = 1, F₄(1) = 0.20. При этом 4-му предприятию нужно выделить x₄ = 1.
Таким образом, оптимальный план инвестирования предприятия: x₁ = 3, x₂ = 2, x₃ = 0, x₄ = 1, который обеспечит максимальный доход, равный: F(6) = g₁(3) + g₂(2) + g₃(0) + g₄(1) = 0.65 + 0.41 + 0 + 0.20 = 1.26.

Пример №3 . Распределите c=200 млн ден. ед. инвестиций между четырьмя министерствами республики ( n=4 ) на реконструкцию и модернизацию производственных мощностей таким образом, чтобы суммарный прирост производства продукции всех министерств f4(с) был максимальным. Прирост выпуска продукции в каждом из министерств gi(x) в зависимости от объема выделенных средств x (0 c=200 млн ден. ед. между первыми тремя министерствами, максимизирующее их суммарный прирост производства продукции f3(с).
Примечание. Основная задача решается с помощью процедуры прямой прогонки. Ответ на подзадачу можно получить из таблицы n-1 исходного решения.

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

Метод прогонки (алгоритм Томаса) используют для решения СЛУ типа Ax=F, где A — трёхдиагональная матрица. Это вариант метода последовательного исключения неизвестных.

Система уравнений Ax=F равноценна соотношению:

Метод прогонки базируется на предположении, что неизвестные, которые необходимо найти, связаны соотношением:

Выразим x_i-1 и x_i через x_i+1, подставим в уравнение, используя это соотношение, (1):

где F_i — правая часть i-го уравнения.

Это соотношение выполняется не завися от решения, если потребовать:

,

,

Получаем из 1-го уравнения:

.

После того, как нашли прогоночные коэффициенты α и β, используем уравнение (2) и получим решение системы. Причем,

.

Еще одним вариантом объяснения смысла метода прогонки является такой вариант: преобразуем уравнение (1) к равнозначному ему уравнению:

c надиагональной (наддиагональной) матрицей:

Рассчеты проводим в 2 этапа. На 1-ом этапе вычисляем компоненты матрицы C′_i и вектора F′, начиная с i=2 до i=n:

На 2-ом этапе, для i=n,n−1,…,1 вычисляем решение:

Для применимости формул метода прогонки достаточно свойства строгого диагонального преобладания у матрицы A.

Метод прогонки

Метод прогонки является модификацией метода Гаусса для частного случая разреженных систем – системы уравнений с трехдиагоналъной матрицей. Такие системы получаются при моделировании некоторых инженерных задач, а также при численном решении краевых задач для дифференциальных уравнений.

Запишем систему уравнений в виде

(2.13)

На главной диагонали матрицы этой системы стоят элементы b1, b2, …, bn,над ней – элементы с1, с2. , сn-1 под ней – элементы а2, а3. , ап (при этом обычно все коэффициенты bi не равны нулю). Остальные элементы матрицы равны нулю.

Метод прогонки состоит из двух этапов – прямой прогонки (аналога прямого хода метода Гаусса) и обратной прогонки (аналога обратного хода метода Гаусса). Прямая прогонка состоит в вычислении прогоночных коэффициентов Ai,Bi,с помощью которых каждое неизвестное xi выражается через zi+1:

(2.14)

Из первого уравнения системы (2.13) найдем

С другой стороны, по формуле (2.14) Приравнивая коэффициенты в обоих выражениях для х1, получаем

(2.15)

Подставим во второе уравнение системы (2.13) вместо х1его выражение через х2по формуле (2.14):

Выразим отсюда х2 через х3:

Аналогично вычисляют прогоночные коэффициенты для любого номера i:

(2.16)

Обратная прогонка состоит в последовательном вычислении неизвестных xi. Сначала нужно найти хп. Для этого воспользуемся выражением (2.14) при i = п –1 и последним уравнением системы (2.13). Запишем их:

Отсюда, исключая хn-1, находим

Далее, используя формулы (2.14) и вычисленные ранее по формулам (2.15), (2.16) прогоночные коэффициенты, последовательно вычисляем все неизвестные хn—1, xn-2. ,х1. Алгоритм решения системы линейных уравнений вида (2.13) методом прогонки приведен на рис. 2.4.

Рис. 2.4. Алгоритм метода прогонки

При анализе алгоритма метода прогонки надо учитывать возможность деления на нуль в формулах (2.15), (2.16). Можно показать, что при выполнении условия преобладания диагональных элементов, т.е. если , причем хотя бы для одного значения iимеет место строгое неравенство, деления на нуль не возникает, и система (2.13) имеет единственное решение.

Приведенное условие преобладания диагональных элементов обеспечивает также устойчивость метода прогонки относительно погрешностей округлений. Последнее обстоятельство позволяет использовать метод прогонки для решения больших систем уравнений. Заметим, что данное условие устойчивости прогонки является достаточным, но не необходимым. В ряде случаев для хорошо обусловленных систем вида (2.13) метод прогонки оказывается устойчивым даже при нарушении условия преобладания диагональных элементов.