Простейшие задачи оптимального управления

3.4. Простейшие задачи оптимального управления 3.4.1. Задача распределения ресурсов во времени. Оптимальное регулирование запасов Планируется производство однородного продукта для удовлетворения потребностей, меняющихся во времени. Весь планируемый период разбит на n периодов. Потребности на продукт в i-м периоде составляют 𝑏𝑖 единиц. Известны также затраты на выпуск дополнительной единицы продукта a рублей и на хранение той же единицы продукции c рублей. Составить оптимальный график производства по периодам с минимальными суммарными затратами. Обозначим через 𝑥𝑖 ≥ 0 выпуск продукции за -й период, а через 𝑢𝑖 запасы, которые образуются в конце 𝑖-го периода за счет превышения накопленного выпуска продукции над накопленным расходом продукции, начиная с первого периода до данного. Пусть к началу планируемого периода выпуск продукции составляет 𝑥0 единиц. Средний размер запасов, хранящихся в течении 𝑖-го периода составит (𝑢𝑖−1 + 𝑢𝑖 ) ∙ 1 . Расходы на хранение за весь планируемый период составят 𝑧хр = 𝑐 ∙ 0,5 ∑𝑛𝑖=1(𝑢𝑖−1 + 𝑢𝑖 ). 2 Введем две новые неотрицательные переменные 𝑦𝑖 и 𝑧𝑖 из соотношений 𝑥𝑖 − 𝑥𝑖−1 = 𝑦𝑖 − 𝑧𝑖 , (𝑖 = ̅̅̅̅̅ 2, 𝑛 ). При этом в оптимальном графике производства yi можно трактовать как величину, на которую произошло расширение производства в -м периоде, а 𝑧𝑖 соответственно как свертывание производства в 𝑖-м периоде. Суммарные дополнительные затраты на расширение производства 𝑧расш = 𝑎 ∑𝑛𝑖=2 𝑦𝑖 . Модель задачи линейного программирования: 𝑛 𝑛 𝑧 = 𝑐 ∙ 0,5 ∑(𝑢𝑖−1 + 𝑢𝑖 ) + 𝑎 ∑ 𝑦𝑖 → min 𝑖=1 𝑖=2 𝑦𝑖 ≥ 0 (𝑖 = ̅̅̅̅̅ 1, 𝑛 ) 𝑥𝑖 − 𝑥𝑖−1 = 𝑦𝑖 − 𝑧𝑖 (𝑖 = ̅̅̅̅̅ 2, 𝑛) 𝑖 𝑖=1 (3.2) (3.3) 𝑖 𝑢𝑖 = 𝑢0 + ∑ 𝑥𝑖 − ∑ 𝑏𝑖 { (3.1) (𝑖 = ̅̅̅̅̅ 1, 𝑛 ) (3.4) 𝑖=1 𝑧𝑖 ≥ 0 (𝑖 = ̅̅̅̅̅ 1, 𝑛) 𝑢𝑖 ≥ 0 (𝑖 = ̅̅̅̅̅ 1, 𝑛 ) Модель можно упростить, исключив из нее переменные 𝑥𝑖 , для этого вычтем из уравнения (3.4) аналогичное уравнение для периода (i-1): 𝑢𝑖 − 𝑢𝑖−1 = (𝑢0 + ∑𝑖𝑖=1 𝑥𝑖 − 𝑖−1 ∑𝑖𝑖=1 𝑏𝑖 ) − (𝑢0 + ∑𝑖−1 𝑖=1 𝑥𝑖 − ∑𝑖=1 𝑏𝑖 ) = 𝑥𝑖 − 𝑏𝑖 , 𝑢𝑖−1 − 𝑢𝑖−2 = 𝑥𝑖−1 − 𝑏𝑖−1 . Откуда почленным вычитанием из предыдущего равенства получаем: 𝑢𝑖 − 2𝑢𝑖−1 + 𝑢𝑖−2 = 𝑥𝑖 − 𝑥𝑖−1 − 𝑏𝑖 + 𝑏𝑖−1 => 𝑥𝑖 − 𝑥𝑖−1 = 𝑢𝑖 − 2𝑢𝑖−1 + 𝑢𝑖−2 + 𝑏𝑖 − 𝑏𝑖−1. Подставляя это выражение в левую часть равенства (3.3), получаем: 𝑢𝑖 − 2𝑢𝑖−1 + 𝑢𝑖−2 + 𝑏𝑖 − 𝑏𝑖−1 = 𝑦𝑖 − 𝑧𝑖 (𝑖 = ̅̅̅̅̅ 2, 𝑛 ) (3.3′) Дальнейшее решение задачи, описанное выражениями (3.1), (3.2) и (3.3') ведется как обычно. Пример 1. Планируется поквартальный выпуск продукции для удовлетворения переменного спроса потребителей 𝑏1 = 50, 𝑏2 = 30, 𝑏3 = 40, 𝑏4 = 20. Составить оптимальный график работы предприятия, если затраты на дополнительный выпуск одной единицы продукции составляет 30 рублей, а затраты на ее хранение в течение периода 3 рубля. Начальный запас продукции на складе 5 единиц. 4 𝑛 𝑧 = 1,5 ∑(𝑢𝑖−1 + 𝑢𝑖 ) + 30 ∑ 𝑦𝑖 → min 𝑖=1 𝑖=2 ̅̅̅̅) 𝑦𝑖 ≥ 0 (𝑖 = 1,4 𝑢2 − 2𝑢1 + 𝑢0 + 𝑏2 − 𝑏1 = 𝑦2 − 𝑧2 𝑢3 − 2𝑢2 + 𝑢1 + 𝑏3 − 𝑏2 = 𝑦3 − 𝑧3 𝑢4 − 2𝑢3 + 𝑢2 + 𝑏4 − 𝑏3 = 𝑦4 − 𝑧4 ̅̅̅̅) 𝑧𝑖 ≥ 0 (𝑖 = 1,4 ̅̅̅̅) { 𝑢𝑖 ≥ 0 (𝑖 = 1,4 ̅̅̅̅) 𝑦𝑖 ≥ 0 (𝑖 = 1,4 𝑢2 − 2𝑢1 + 5 + 30 − 50 = 𝑦2 − 𝑧2 𝑢3 − 2𝑢2 + 𝑢1 + 40 − 30 = 𝑦3 − 𝑧3 𝑢4 − 2𝑢3 + 𝑢2 + 20 − 40 = 𝑦4 − 𝑧4 ̅̅̅̅) 𝑧𝑖 ≥ 0 (𝑖 = 1,4 ̅̅̅̅) { 𝑢𝑖 ≥ 0 (𝑖 = 1,4 После простейших преобразований: 𝑧 = 1,5(5 + 2𝑢1 + 2𝑢2 + 2𝑢3 + 𝑢4 ) + 30(𝑦2 + 𝑦3 + 𝑦4 ) → min ̅̅̅̅) 𝑦𝑖 ≥ 0 (𝑖 = 1,4 𝑢2 − 2𝑢1 − 15 = 𝑦2 − 𝑧2 𝑢3 − 2𝑢2 + 𝑢1 + 10 = 𝑦3 − 𝑧3 𝑢4 − 2𝑢3 + 𝑢2 − 20 = 𝑦4 − 𝑧4 ̅̅̅̅) 𝑧𝑖 ≥ 0 (𝑖 = 1,4 ̅̅̅̅) { 𝑢𝑖 ≥ 0 (𝑖 = 1,4 Решим задачу в Microsoft excel, используя пакет «Поиск решений»: при 𝑧𝑚𝑖𝑛 = 22,5 𝑢(0; 5; 0; 0) 𝑦(0; 0; 0) 𝑧(10; 0; 15) Перейдем к x используя (3.4) уравнение 𝑛 𝑛 𝑢𝑖 = 𝑢0 + ∑ 𝑥𝑖 − ∑ 𝑏𝑖 𝑖=1 (𝑖 = ̅̅̅̅̅ 1, 𝑛 ) 𝑖=1 𝑢1 = 𝑢0 + 𝑥1 − 𝑏1 ; 𝑢2 = 𝑢0 + 𝑥1 + 𝑥2 − 𝑏1 − 𝑏2 ; { 𝑢3 = 𝑢0 + 𝑥1 + 𝑥2 + 𝑥3 − 𝑏1 − 𝑏2 − 𝑏3 ; 𝑢4 = 𝑢0 + 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 − 𝑏1 − 𝑏2 − 𝑏3 − 𝑏4 . 0 = 5 + 𝑥1 − 50; 5 = 5 + 𝑥1 + 𝑥2 − 80; { 0 = 5 + 𝑥1 + 𝑥2 + 𝑥3 − 120; 0 = 5 + 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 − 140. 𝑥1 = 45; 𝑥1 + 𝑥2 = 80; { 𝑥1 + 𝑥2 + 𝑥3 = 115; 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 = 135. 𝑥1 = 45; 𝑥 = 35; { 2 𝑥3 = 35; 𝑥4 = 20. 3.4.2. Задача распределения ресурсов. Динамическая транспортная задача Пусть имеется m складов с номерами 𝑖 = ̅̅̅̅̅̅ 1, 𝑚 предназначенных для хранения ̅̅̅̅̅ однородного продукта. В дискретные моменты времени 𝑡 (𝑡 = 1, 𝑇 ), происходит его распределение между потребителями с номерами 𝑗 = ̅̅̅̅̅ 1, 𝑛. Пополнение запаса пункта хранения происходит в 𝑡 момент времени и определяется величинами 𝑎𝑖𝑡 (𝑖 = ̅̅̅̅̅̅ 1, 𝑚), а 𝑡 ̅̅̅̅̅ потребности клиентов составляют 𝑏𝑗 (𝑗 = 1, 𝑛). Обозначим через 𝑐𝑖𝑗𝑡 затраты на доставку одной единицы продукта с i-го склада jму клиенту в момент времени 𝑡. Так же предполагается, что продукт, поступивший на склад в момент времени 𝑡 может быть использован начиная со следующего момента времени 𝑡 + 1. 𝑡 𝑇 Требуется найти такой план распределения ресурсов {𝑥𝑖𝑗 } , который 𝑚×𝑛 минимизирует суммарные расходы на доставку потребителям продукции со складов, в течение полного периода функционирования системы 𝑇, где 𝑡 𝑥𝑖𝑗 – количество продукта, поставляемое с -го склада 𝑗-му потребителю в t момент времени; 𝑧𝑖𝑡 – общее количество продукта на -ом складе в момент времени 𝑡. 𝑡 𝑇 Задача состоит в нахождении таких совокупностей переменных {𝑥𝑖𝑗 } и {𝑧𝑖𝑡 }𝑇𝑚 , 𝑚×𝑛 которые обращают в минимум функционал 𝑚 𝑛 𝑇−1 𝑡 𝐹(𝑥̅ ) = ∑ ∑ ∑ 𝑐𝑖𝑗𝑡 𝑥𝑖𝑗 → min (3.5) 𝑖=1 𝑗=1 𝑡=0 При условиях: 𝑛 𝑡 𝑧𝑖𝑡+1 = 𝑧𝑖𝑡 − ∑ 𝑥𝑖𝐽 + 𝑎𝑖𝑡 (3.6) 𝑗=1 𝑚 𝑡 ∑ 𝑥𝑖𝐽 = 𝑏𝑗𝑡 (3.7) 𝑖=1 𝑧𝑖𝑡 ≥ 0 𝑡 𝑥𝑖𝑗 ≥0 (3.8) { 𝑖 = ̅̅̅̅̅̅ 1, 𝑚, 𝑗 = ̅̅̅̅̅ 1, 𝑛, 𝑡 = ̅̅̅̅̅̅̅̅̅̅ 0, 𝑇 − 1 Объемы начальных запасов должны быть заданы 𝑧𝑖0 = 𝑧̂𝑖 – оценка начального состояния. Составленная задача (3.5) – (3.8) – это динамическая транспортная задача линейного программирования, где 𝑡 𝑥𝑖𝑗 – параметры управления системой; 𝑡 𝑧𝑖 – параметры состояния системы в каждый момент времени 𝑡. Ограничение на 𝑧𝑖𝑡 ≥ 0 (3) означает, что в любой момент времени с любого склада не может быть вывезен объем продукта превышающий его фактическое количество. Ограничение (3.6) – это фазовое ограничение, оно задает правило изменения объема продукта на складе при переходе от одного периода к другому. Так же можно сказать, что оно задает изменение параметров состояния системы для двух смежных периодов 𝑡 и (𝑡 + 1). 3.4.3. Простейшая динамическая модель макроэкономики Представим экономику некоторого региона, как совокупность n отраслей с номерами 𝑗 = ̅̅̅̅̅ 1, 𝑛. Валовой продукт которых, в денежном выражении на некоторый момент времени t, может быть представлен в виде вектора 𝑧̅𝑡 = (𝑧1𝑡 , 𝑧2𝑡 , … , 𝑧𝑛𝑡 ), где 𝑡 = ̅̅̅̅̅ 1, 𝑇 . 𝑡 𝑡 Обозначим матрицу прямых производственных затрат, как 𝐴𝑡 = {𝑎𝑖𝑗 }, где 𝑎𝑖𝑗 в момент времени t, отражают затраты продукции i-ой отрасли (в денежном выражении), идущие на изготовление единицы продукции j-ой отрасли в t-ый момент времени. 𝑡 𝑇 Если 𝑥 𝑡 = {𝑥𝑖𝑗 } – матрица, задающая удельные нормы продукции i-ой отрасли, 𝑚×𝑛 идущие на расширение производства в j-ой отрасли, а 𝑦̅𝑡 = (𝑦1𝑡 , 𝑦2𝑡 , … , 𝑦𝑛𝑡 ) – это вектор объемов продукции отраслей, идущей на потребление, тогда условие расширенного производства выглядит так: 𝑧 𝑡+1 = 𝐴𝑡+1 ∙ 𝑧 𝑡+1 + 𝑥 𝑡+1 (𝑧 𝑡+1 − 𝑧 𝑡 ) + 𝑦 𝑡+1 𝑡 = ̅̅̅̅̅̅̅̅̅̅ 0, 𝑇 − 1, 𝑧𝑗𝑡 ≥ 0, 𝑗 = ̅̅̅̅̅ 1, 𝑛 , 𝑧 0 = 𝑧̂ (3.9) (3.10) Исходный запас продукции отраслей должен быть задан. В этой модели параметрами состояния модели являются 𝑧̅𝑡 , а параметрами управления системой являются 𝑥 𝑡 . На базе этой модели можно поставить различные задачи, например, задачу оптимального вывода экономики на момент времени T к некоторому заданному состоянию 𝑧 ∗. Тогда данная задача сводится к нахождению последовательности управляющих 𝑡 𝑇 параметров {𝑥𝑖𝑗 } , и удовлетворяющих условиям (3.9) и (3.10) с целевой функцией 𝑚×𝑛 |𝑧 𝑡 − 𝑧 ∗ | → min (3.11) – это простейшая модель для макроэкономики.