Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Математический аппарат динамического программирования, основанный на методологии пошаговой оптимизации, может быть использован при нахождении кратчайших расстояний, например, на географической карте, представленной в виде сети. Решение задачи по определению кратчайших расстояний между пунктами отправления и пунктами получения продукции по существующей транспортной сети является исходным этапом при решении таких экономических задач, как оптимальное прикрепление потребителей за поставщиками, повышение производительности транспорта за счет сокращения непроизводительного пробега и др.
Пусть транспортная сеть состоит из 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 до конечного пункта, т.е. - F k - 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
тыс. усл. ед. | тыс. усл. ед. | тыс. усл.ед. | тыс. усл.ед. |
1,5 | 1,7 | ||
2,1 | 2,4 | ||
2,5 | 2,3 | 2,7 | |
3,5 | 3,2 | ||
3,6 | 3,5 |
Для . (53.7)
Для простоты в задаче сделано предположение, что вкладываются только тысячи условных единиц.
Проведем условную оптимизацию.
По ее результатам заполняется таблица 53.2.
Таблица 53.2
S | k=3 | k=2 | k=1 | |||
1,7 | ||||||
2,4 | 3,7 | |||||
2,7 | 4,4 | |||||
3,2 | 4,7 | |||||
3,5 | 1/4 | 5,2 | 6,4 |
В первой колонке таблицы записываются возможные состояния системы 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
1,7 | 1,7 | |||
, следовательно , .
2) S=2
Таблица 53.4
2,4 | 2,4 | |||
1,7 | 3,7 | |||
2,1 | 2,1 |
, следовательно ;
3) S=3
Таблица 53.5
2,7 | 2,7 | |||
2,4 | 4,4 | |||
2,1 | 1,7 | 3,8 | ||
2,3 | 2,3 |
, следовательно ;
4) S=4
Таблица 53.6
3,2 | 3,2 | |||
2,7 | 4,7 | |||
2,1 | 2,4 | 4,5 | ||
2,3 | 1,7 | |||
3,5 | 3,5 |
, следовательно ; .
5) S=5
Таблица 53.7
3,5 | 3,5 | |||
3,2 | 5,2 | |||
2,1 | 2,7 | 4,8 | ||
2,3 | 2,4 | 4,7 | ||
3,5 | 1,7 | 5,2 | ||
Для S =5 возможны два условных варианта управления: и .
· Условная оптимизация для i =1.
Перед первым шагом состояние системы известно.
S = D =5 тыс. у.е., и условную оптимизацию следует проводить только для этого значения S =5
Таблица 53.8
5,2 | 5,2 | |||
1,5 | 4,7 | 6,2 | ||
4,4 | 6,4 | |||
2,5 | 3,7 | 6,2 | ||
3,6 | 3,6 |
, следовательно, , .
Оптимальная прибыль, приносимая тремя предприятиями при инвестировании в них 5000 у.е., равна 6,4 тыс. у.е.
.
Проведем безусловную оптимизацию.
Ее результаты отмечены в таблице 34.2.
Для i =1 ; .
Для i =2 по формуле (34.3) .
; .
Для i =3 .
; .
.
Следует пронимать, что полученное решение есть лишь некоторое приближение к оптимальному решению. Его можно улучшить, т.е. приблизить к оптимальному, взяв более мелкий шаг оптимизации, например, вкладывать в предприятия средства, кратные 500 у.е.
Дата публикования: 2015-01-26; Прочитано: 700 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!