Лекция: Принцип Беллмана для оптимальных путей.

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

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

Рис. 52.1

В задаче имеется ограничение — двигаться по изображенным на схеме маршрутам можно только слева на право, т.е. попав, например, в пункт 7, мы имеем право переместиться только в пункт 10 и не можем возвратиться обратно в 5-й или 6-й. Эта особенность транспортной сети дает право отнести каждый из десяти пунктов к одному из поясов. Будем считать, что пункт принадлежит k-му поясу, если из него попасть в конечный пункт ровно за k шагов, т.е. с заездом ровно в (k — 1)-й промежуточный пункт. Таким образом, пункты 7, 8и 9принадлежат к первому поясу, 5 и 6 — ко второму, 2, 3 и 4 — к третьему и 1 — к четвертому. Тогда на k-м шаге будем находить оптимальные маршруты перевозки груза из пунктов k-го пояса до конечного пункта. Оптимизацию будем производить с конца процесса, и потому, дойдя до k-го шага, неизвестно, в каком из пунктов k-го пояса окажется груз, перевозимый из первого пункта.

Введем обозначения:

k — номер шага (k = 1, 2,3,4);

i — пункт, из которого осуществляются перевозки (i = 1,2,..., 9);

j — пункт, в который доставляется груз (j = 2,3,.., 10);

Сi,j — стоимость перевозки груза из пунктаi в пунктj.

Fk (i) — минимальные затраты на перевозку груза на k-м шаге решения задачи из пункта i до конечного пункта.

Очевидно, что минимум затрат на перевозку груза из пунктов k-го пояса до пункта 10 будет зависеть от того, в каком пункте этого пояса мы оказались. Номерi пункта, принадлежащего k-му поясу, будет являться переменной состояния системы на k-м шаге. Поскольку оптимизация осуществляется с конца процесса, то, находясь в некотором пункте i k-го пояса, принимается решение о перемещении груза в один из пунктов (k– 1)-го пояса, а направление дальнейшего движения известно из предыдущих шагов. Номерj пункта (k — 1)-го пояса будет переменной управления на k-м шаге.

Для первого шага управления (k — 1) функция Беллмана представляет собой минимальные затраты на перевозку груза из пунктов 1-го пояса в конечный пункт, т.е. F1(i) = Сi,10. Для последующих шагов затраты складываются из двух слагаемых — стоимости перевозки груза Сi,j из пункта i k-го пояса в пунктj (k — 1)-го пояса и минимально возможных затрат на перевозку из пункта j до конечного пункта, т.е. — Fk — 1(i). Таким образом, функциональное уравнение Беллмана будет иметь вид

(52.1)

Минимум затрат достигается на некотором значении j*, которое является оптимальным направлением движения из пункта i в конечный пункт. На четвертом шаге попадаем на4-й пояс и состояние системы становится определеннымi=1. Функция F4(1) представляет собой минимально возможные затраты по перемещению груза из 1-го пункта в 10-й. Оптимальный маршрут определяется в результате анализа всех шагов в обратном порядке, а выбор некоторого управления j на k-м шаге приводит к тому, что состояние системы на (k — 1)-м шаге становится определенным.

Пример: решим сформулированную выше задачу, исходные данные которой приведены на рисунке.

I этап. Условная оптимизация.

1-й шаг. k = 1 .

На первом шаге в пункт 10 груз может быть доставлен из пунктов 7,8 или 9.

Таблица 52.1

2-й шаг. k = 2 .

Функциональное уравнение на втором шаге принимает вид:

Все возможные перемещения груза на втором шаге и результаты расчета приведены в следующей таблице 33.2:

Таблица 52.2

3-й шаг. k = 3.

Таблица 52.3

4-й шаг. k = 4.

Таблица 52.4

II этап.Безусловная оптимизация.

Рис. 52.2

На этапе условной оптимизации получено, что минимальные затраты на перевозку груза из пункта 1 в пункт 10 составляют F4(1) = 20. Данный результат достигается при движении груза из 1-го пункта в 3-й. По данным табл. 52.3, из пункта 3 необходимо двигаться в пункт 6, затем — в пункт 7 (см. табл. 52.2) и из него — в конечный пункт (см. табл. 52.1). Таким образом, оптимальный маршрут доставки груза: 1 => 3 => 6 => 7 => 10. На рисунке он показан жирными стрелками.

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

Инвестор выделяет средства в размере D условных единиц, которые должны быть распределены между n-предприятиями. Каждое k-тое предприятие при инвестировании в него средств x приносит прибыль Wk (S, xk) условных единиц, k=1...n. Нужно выбрать оптимальное распределение инвестиций между предприятиями, обеспечивающее максимальную прибыль.

Выигрышем F в данной задаче является прибыль, приносимая n-предприятиями.

Построение математической модели:

1. Определение числа шагов. Число шагов n равно числу предприятий, в которые осуществляется инвестирование.

2. Определение состояний системы. Состояние системы на каждом шаге характеризуется количеством средств Sk, имеющихся в наличии перед данным шагом, .

3. Выбор шаговых управлений. Управление на k-м шаге является количество средств, инвестируемых вk-тое предприятие.

4. Функция выигрыша на k-м шаге:

(53.1)

это прибыль, которую приносит k-тое предприятие при инвестировании в него средств .

, (53.2)

следовательно, данная задача может быть решена методом динамического программирования.

5. Определение функции перехода в новое состояние.

. (53.3)

Таким образом, если на k-м шаге система находилась в состоянии, а выбрано управление, то на (k+1)-м шаге система будет находиться в состоянии. Другими словами, если в наличии имеются средства в размере у.е., и в k-тое предприятие инвестируется у.е., то для дальнейшего инвестирования остается ( ) у.е.

6. Составление функционального уравнения для k=n:

, (53.4)

. (53.5)

На последнем шаге, т.е. перед инвестированием средств в последнее предприятие, условное оптимальное управление соответствует количеству средств, имеющихся в наличии; т.е. сколько средств осталось, столько и надо вложить в последнее предприятие. Условный оптимальный выигрыш равен доходу, приносимому последним предприятием.

7. Составление основного функционального уравнения.

Подставив в формулу (53.2) выражения (53.1) и (53.3), получим следующее функциональное уравнение:

(53.6)

Поясним данное уравнение. Пусть перед k-м шагом у инвестора остались средства в размере у.е. Тогда у.е. он может вложить в k-тое предприятие, при этом оно принесет доход, а оставшиеся ( ) у.е.—в остальные предприятия с k+1-го до n-го. Условный оптимальный выигрыш от такого вложения. Оптимальным будет то условное управление, при котором сумма и максимальна.

Пример:D=5000, n=3. Значения, заданы в таблице 34.1.

Таблица 53.1

Для . (53.7)

Для простоты в задаче сделано предположение, что вкладываются только тысячи условных единиц.

Проведем условную оптимизацию.

По ее результатам заполняется таблица 53.2.

Таблица 53.2

В первой колонке таблицы записываются возможные состояния системы S=1..5, в верхней строке — номера шагов i=1..3. На каждом шаге определяются условные оптимальные управления и уcловные оптимальные выигрыши .

· Проведение условной оптимизации для последнего шага i=3. Функциональное уравнение на последнем шаге имеет вид:

, (53.8)

поэтому два столбца таблицы 33.2, соответствующие i=3, заполняются автоматически по таблице 33.1 исходных данных.

· Условная оптимизация для i=2. Функциональное уравнение

. (53.9)

Для проведения условной оптимизации заполним ряд вспомогательных таблиц (таблицы 34.3—34.8), соответствующих различным значениям S, т.е. различным исходам окончания предыдущего шага.

1) S=1

Таблица 53.3

, следовательно, .

2) S=2

Таблица 53.4

, следовательно;

3) S=3

Таблица 53.5

, следовательно;

4) S=4

Таблица 53.6

, следовательно; .

5) S=5

Таблица 53.7

Для S=5 возможны два условных варианта управления: и .

· Условная оптимизация для i=1.

Перед первым шагом состояние системы известно.

S=D=5 тыс. у.е., и условную оптимизацию следует проводить только для этого значения S=5

Таблица 53.8

, следовательно,, .

Оптимальная прибыль, приносимая тремя предприятиями при инвестировании в них 5000 у.е., равна 6,4 тыс. у.е.

.

Проведем безусловную оптимизацию.

Ее результаты отмечены в таблице 34.2.

Для i=1; .

Для i=2 по формуле (34.3) .

; .

Дляi=3 .

; .

.

Следует пронимать, что полученное решение есть лишь некоторое приближение к оптимальному решению. Его можно улучшить, т.е. приблизить к оптимальному, взяв более мелкий шаг оптимизации, например, вкладывать в предприятия средства, кратные 500 у.е.