Решение задачи распределения ресурсов методом динамического программирования

I.Условия оптимизации
Планирование начинаем с последнего третьего этапа

II. Безусловная оптимизация
Выясним, каким должно быть оптимальное управление процессом выделения средств между первым и вторым предприятиями для получения максимального дохода в количестве 4950 ден. ед.
1-й год. Так как x₁ = a₁ и , y₁ = 0, то все средства в количестве 900 ден. ед. отдаются первому предприятию.
2-й год. Выделяются средства a₂ = 0,3x₁ + 0,2a₁ = 0,5 a₁ =450 ед., x₂ = a₂ , y₂ = 0.
Все они передаются первому предприятию.
3-й год. Выделяются средства a₃ = 0,3x₂ + 0,2a₂ = 0,5 a₂ = 225 ед., x₃ = 0, y₃ = a₃ . Все они передаются второму предприятию.
Результаты решения представим в виде таблицы.

Пример №2 . Оптимальное поэтапное распределение средств между предприятиями в течении планового периода.
Руководство фирмы, имеющей договор о сотрудничестве с тремя малыми предприятия, на плановый годовой период выделила для них оборотные средства в объеме 100000 у.е. Для каждого предприятия известны функции поквартального дохода и поквартального остатка оборотных средств в зависимости от выделенной на квартал суммы x. В начале квартала средства распределяются полностью между тремя предприятиями (из этих вложенных средств и вычисляется доход), а по окончанию квартала остатки средств аккамулируются у руководства фирмы и снова распределяются полностью между предприятиями.
Составить план поквартального распределения средств на год (4 квартала), позволяющего достичь максимальный общий доход за год.
f₁(x)=1,2x, f₂(x)=1.5x, f₃(x)=2x; g₁(x)=0.7x, g₂(x)=0.6x, g₃(x)=0.1x

Задача распределения средств на два года

Найти оптимальный способ распределения средств S₀ = 100 тыс.руб между двумя предприятиями на два года, если вложенные средства в первое предприятие дают доход f₁(x) = 0.9x и возвращаются в размере j₁(x) = 0.5x. Аналогично, для второго предприятия f₂(x) = 0.8x и j₂(x) = 0.7x.

Отсюда можно сделать вывод о том, что х₁=0, х₂=70, максимальная прибыль за два года составит 143 ден. ед.

Источник

Глава 7. Динамическое программирование §1. Примеры задач динамического программирования

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

Динамическое программирование — это математический метод оптимизации многошаговых процессов, разработанный в начале 50-х годов американским ученым Р. Беллманом. Его использование позволяет свести решение сложной задачи к последовательному решению серии более простых «подзадач». Название метода связано с тем, что первоначально с его помощью проводилась оптимизация динамических систем, т.е. систем, изменяющихся во времени. Однако затем он стал применяться и для решения задач, в которых временной фактор отсутствует, в частности для задач целочисленного программирования.

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

Пример 1.1. Планируется производственная деятельность фирмы на период времени в n лет. Для ее развития выделены капиталовложения в объеме K, которые нужно распределить по годам планового периода. Известно, что годовой доход фирмы зависит от объема средств, вложенных в начале года. Нужно определить, сколько капиталовложений следует выделить фирме в начале каждого года, чтобы общий доход за n лет был максимальным.

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

Управление u_k на k-м шаге (k = ) этого процесса — величина капиталовложений, полученных фирмой в начале k-го года. Управление u в целом представляет собой совокупность всех пошаговых управлений:

Обозначим x_k — величину средств, доступных для выделения фирме после k-го года (остаток капиталовложений). Переменная x_k характеризует состояние управляемого процесса после k-го шага. Ясно, что

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

Управление u = (u₁, u₂,…, u_n), для которого эти условия выполнены, будем называть допустимым.

Обозначим f_k(u_k) — доход, который получит фирма в k-м году, если ей выделить в начале этого года средства в объеме u_k. Функция f_k характеризует эффективность управления на k-м шаге.

Общая эффективность управления u оценивается при помощи показателя Z — суммарного дохода фирмы за весь плановый период. Этот показатель равен сумме пошаговых показателей эффективностей (годовых доходов):

Таким образом, задача состоит в выборе таких допустимых управлений , т.е. распределения капиталовложений, при котором функция Z достигнет максимума.

В этом примере многошаговый характер процесса управления, по сути, был задан его условиями, согласно которым средства выделяются в начале каждого года. Однако иногда, чтобы использовать метод динамического программирования, «многошаговость» управления приходится вводить искусственно.

Пример 1.2. Имеется груз, состоящий из неделимых предметов n видов, который нужно погрузить на баржу грузоподъемностью Р. Известны стоимость c_k и вес p_k каждого предмета k-го вида (k = ). Нужно определить, сколько предметов каждого вида следует погрузить на баржу, чтобы суммарная стоимость груза была максимальной, а его общий вес не превышал грузоподъемности баржи.

Обозначим u_k — количество предметов k-го вида, загружаемых на баржу. Тогда математическая модель этой задачи выглядит так:

u_k — целые числа для всех k = .

Это задача линейного целочисленного программирования, но для нахождения ее оптимального решения можно использовать динамическое программирование. Для этого процесс загрузки следует представить в виде многошагового управляемого процесса, состоящего из n шагов, причем на каждом шаге баржа загружается предметами одного вида.

Будем считать, что на первом шаге баржа загружается предметами первого вида, на втором шаге — второго вида и т.д. Управление u_k на k-м шаге (k = ) — это количество предметов k-го вида, загружаемых на баржу. Параметры состояния x_k на k-м шаге — это количество груза, которое еще можно погрузить на баржу после того как на нее погрузили предметы первых k видов. Ясно, что

Так как на каждом шаге должны выполняться неравенства x_k ≥ 0, то управления на каждом шаге должны удовлетворять неравенствам:

Управление u = (u₁, u₂,…, u_n), для которого эти условия выполнены, назовем допустимым.

Эффективность управления на k-м шаге определяется стоимостью всех предметов, загруженных на этом шаге, т.е. она равна c_ku_k. Эффективность всего процесса управления Z равна сумме эффективностей всех шагов, т.е. суммарной стоимостью загруженных предметов:

Оптимальное управление доставляет максимальное значение этой функции на множестве всех допустимых управлений.

Пример 1.3. Решается задача оптимального распределения дефицитного ресурса (сырье, оборудование, инвестиции) между n объектами, причем общий объем ресурса равен S. Для каждого объекта считается известной зависимость между размером ресурса и величиной прибыли, полученной в результате выделения ресурса данному объекту. Эта зависимость, вообще говоря, имеет нелинейный характер. Нужно найти распределение ресурса, дающее максимальную общую прибыль.

Обозначим f_k(u_k) (k = ) — величину прибыли, получаемую от k—го объекта при выделении ему ресурса в объеме u_k. единиц. Математическая модель этой задачи имеет следующий вид:

Z = f₁(u₁) + … + f_n(u_n) → max,

Это задача нелинейного программирования. Если все функции f_k вогнутые, то она является задачей выпуклого программирования, и ее оптимальное решение можно найти при помощи какого-либо метода решения задач этого класса, например, при помощи метода множителей Лагранжа. Если же хотя бы одна из функций прибыли не является вогнутой, то использование методов нелинейного программирования может не привести к нужному результату, так как в этом случае найденный локальный максимум может не быть глобальным (см. п.6 §2 главы 5).

В такой ситуации для нахождения оптимального решения целесообразно использовать аппарат динамического программирования. Для этого нужно, представить распределение ресурса как многошаговый процесс, состоящий из n шагов, причем на каждом шаге ресурс выделяется одному из объектов. Будем считать, что на первом шаге ресурс выделяется первому объекту, на втором шаге — второму и т.д.

Управление u_k на k-м шаге (k = ) — это количество ресурса, выделяемого k-му объекту, а параметры состояния x_k — это остатки ресурса после его выделения первым k объектам, задаваемые формулами:

Управление u_k на каждом шаге должно удовлетворять условию:

Управление u = (u₁, u₂,…, u_n), для которого эти условия выполнены, будем называть допустимым.

Эффективность управления u_k на k-м шаге определяется величиной прибыли, получаемой от k—го объекта, т.е. она равна f_k(u_k). Эффективность всего процесса управления Z равна сумме эффективностей всех шагов:

Оптимальное управление доставляет максимальное значение этой функции на множестве всех допустимых управлений.

Источник