Математическое программирование
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
>
2) Прямой ход: от известного начального состояния к последнему из полученного множества условно-оптимальных управлений составляется искомое оптимальное управление для всего процесса в целом.
Оптимальную стратегию управления можно получить, если сначала найти оптимальную стратегию управления на n-м шаге, затем на двух последних шагах, затем на трех последних шагах и т.д., вплоть до первого шага.
Чтобы можно было использовать принцип оптимальности практически, необходимо записать его математически. Обозначим через z1(xn-1), z2(xn-2),…, zn(x0) условно-оптимальные значения приращений целевой функции на последнем шаге, двух последних,…, на всей последовательности шагов, соответственно.
Тогда для последнего шага:
z1(xn-1) = (min) {Fn(xn-1, un)},
где un - множество допустимых (возможных) управлений на n-ом шаге, xn-1 - возможные состояния системы перед n-ым шагом.
Для двух последних шагов:
z2(xn-2) = (min) {Fn-1(xn-2, un-1) + z1(xn-1)}.
Для k последних шагов:
zk(xn-k) = (min) {Fn-k+1(xn-k, un-k+1) + zk-1(xn-k+1)}.
Для всех n шагов:
zn(x0) = (min) {F1(x0, u1) + zn-1(x1)}.
Полученные рекуррентные соотношения называют функциональными уравнениями Беллмана.
При этом согласно определению zn(x0) = F*.
3. Задача оптимального распределения ресурсов
а) Постановка задачи.
Задачи на оптимальное распределение ресурса, который можно использовать различным образом, возникают при разработке оперативных и перспективных планов особенно часто. К ним относятся задачи о распределении средств на приобретение оборудования, закупку сырья и найм специалистов; задачи о распределении товара по торговым предприятиям и складам; задачи по определению последовательности пропорций между продукцией с/х производства, предназначенной для реализации и воспроизводства и т.д.
Рассмотрим задачу оптимального распределения заданного объема капиталовложений в несколько предприятий.
Пусть на реконструкцию и модернизацию 4-х своих филиалов фирма имеет возможность выделить 200 млн. руб. Ожидаемый прирост прибыли зависит как от финансируемого филиала, так и от объема этого финансирования. Однако, прирост прибыли в отдельно взятом филиале не зависит от вложенных средств в другие филиалы, а общая прибыль фирмы равна сумме всех приростов по филиалам. Следует определить оптимальное распределение капиталовложений между филиалами, максимизирующее общий прирост прибыли фирмы.
В данном случае речь идет об однократном распределении средств, и поэтому задача сама по себе не является динамической. Однако, ее можно наиболее просто решить как многошаговую, если объекты капиталовложений (филиалы) включать в рассмотрение последовательно, т.е. на каждом шаге к рассмотренным добавлять следующий.
При таком подходе можно использовать функциональные уравнения Беллмана. Для их решения в табулированном виде общий объем капиталовложений разбивается на N интервалов с шагом (для нашей задачи положим N = 4, тогда = 200/4=50 млн. руб.). Т.е. значения функций, входящих в уравнения Беллмана, будут определяться только в точках, кратных (в нашем примере в точках 0, 50, 100, 150, 200).
Пусть ожидаемый прирост прибыли филиалов при соответствующих капиталовложениях задан таблицей.
Кап. ВложенияПрирост прибыли по филиалам12345025303628100607064561501009095110200140122130142
С =200 - общий объем распределяемых средств;
х - объем средств, выделяемых филиалам (на каждом шаге), 0? х ?C.
Fi(xi) - ожидаемый прирост i-той фирмы при выделении ей хi средств. Тогда целевая функция
F = F1(x1) + F2(x2) + F3(x3) + F4(x4) > max
при ограничении x1 + x2 + x3 + x4 = C, xi ? 0, i = .
б) Схема решения.
1. Введем последовательность функций:
z1(x) - max прибыль фирмы, если x средств выделить одному 1-му филиалу;
z2(x) - max прибыль фирмы, если x средств распределить между 1-м и 2-м филиалами;
z3(x) - max прибыль фирмы, если х средств распределить между 3-м и двумя первыми филиалами;
z4(x) - max прибыль фирмы, при распределении x средств между всеми 4-мя филиалами.
Очевидно, что z4(C) = max F = F*, a zi(0) = 0.
. Обратный ход.
Рассмотрим финансирование только 1-го филиала, тогда по определению
z1(x) = F1(x). (1)
Пусть теперь средства в объеме x распределяются между 1-м и 2-м филиалами: 2-му в объеме x2, тогда х - х2 = х1 выделяется 1-му. Общая прибыль двух филиалов
z2(x) = (F2(x2) + z1(x - x2)). (2)
Теперь включим в рассмотрение дополнительно 3-й филиал: из общей суммы х выделим 3-му филиалу х3, тогда остальная часть х - х3 оптимальным образом распределяется между двумя первыми
z3(x) = (F3(x3) + z2(x - x3)). (3)
Наконец, по аналогии находим
z4(x) = (F4(x4) + z3(x - x4)). (4)
. Прямой ход.
Функциональные уравнения Беллмана (1) - (4) позволяют рассчитать значения zi и Fi для всех возможных х. Среди них находим z4(C) = F* и оптимальное x4* такое, что
F4(x4*) = F4*, после чего результаты вычислений просматриваются в обратном порядке. Зная x4*, находим С-х4* - объем финансирования остальных трех филиалов, а следовательно, и F3* и х3*, и т.д. до нахождения х1* и F1* = F1(x1*).
в) Расчет.
….
4. Задача о замене
а) Постановка задачи.
Оборудование со временем изнашивается и стареет морально, падает его производительность, растут издержки на ремонт. Поэтому на каком-то этапе его эксплуатация становится менее выгодной, чем замена на новое. Возникает задача определения оптимальной стратегии замены оборудования в рассматр