ПРАКТИЧЕСКОЕ ЗАНЯТИЕ. РЕШЕНИЕ ЗАДАЧ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
Оптимизация решения о капиталовложениях в несколько объектов единовременно
Допустим, имеется возможность вложения средств С в группу из n предприятий на реконструкцию и модернизацию оборудования. Известен возможный прирост продукции на каждом предприятии в зависимости от выделенных ему средств ri(x); . Необходимо таким образом распределить инвестиции С между предприятиями, чтобы общий прирост выпуска продукции на всех n предприятиях в сумме был максимальным. Составим основное функциональное уравнение. Обозначим через f1 – максимально возможный прирост выпуска продукции на одном предприятии при различных значениях вкладываемых средств х. Каждому значению х отвечает определённый результат r1(x): где yn-1 – допустимая сумма средств, которая может быть вложена в одно предприятие – это допустимое состояние процесса на начало первого шага вычислений. На следующем шаге - оптимальный эффект от вложения средств в два предприятия получаем максимизируя объём прироста продукции на втором предприятии r2(x) плюс оптимальный результат, полученный на предыдущем шаге: где yn-2 – средства, вкладываемые в два предприятия; х – средства, выделяемые второму предприятию; (yn-2 – x) – средства, вкладываемые в первое предприятие. В общем случае функциональное уравнение задачи, позволяющее максимизировать эффект, получаемый на i-м шаге, плюс оптимальное решение, полученное на предыдущем шаге, имеет вид: Задача. Составить оптимальный план распределения капиталовложений между четырьмя предприятиями (проектами) в размере С = 100 млн. ден. ед.
На первом этапе решения задачи динамического программирования, рассмотрим программу вложения средств в предприятие по шагам. На первом шаге максимизируем отдачу f1(C) от вложения средств x1 в одно (первое) предприятие: Отдача от средств, вкладываемых в 1-ое предприятие
На втором шаге максимизируем отдачу f2(C) от вложения средств в два предприятия, из которых x2 вкладывается во второе предприятие, с учётом результата, полученного на предыдущем шаге: Отдача от средств, вкладываемых во 2-ое предприятие и их остатков, вкладываемых в 1-ое предприятие
На третьем шаге максимизируем отдачу f3(C) от вложения средств в три предприятия, из которых x3 вкладывается в третье предприятие, с учётом результата, полученного на предыдущем шаге: Отдача от средств, вкладываемых в 3-е предприятие и их остатков, вкладываемых в 1-ое и 2-ое предприятия
На четвёртом шаге максимизируем отдачу f4(C) от вложения средств в четыре предприятия, из которых x4 вкладывается в четвёртое предприятие, с учётом результата, полученного на предыдущем шаге: Отдача от средств, вкладываемых в 4-ое предприятие и их остатков, вкладываемых в 1-ое, 2-ое и 3-е предприятия
На втором этапе решения задачи динамического программирования, проанализируем таблицы в обратном порядке. Максимальный прирост отдачи от вложения средств в размере 100 млн. ден. ед. на четырёх предприятиях составит 91 млн. ден. ед. (табл. 5). При этом в 4-ое предприятие следует вложить х4 = 40 млн. ден. ед. Остаток средств 100 – 40 = 60 млн. ден. ед. вкладывают в развитие 1-го, 2-го и 3-го предприятий. Из табл. 4 видно, что из этой суммы в 3-е предприятие следует вложить х3 = 40 млн. ден. ед. Остаток средств - 60 – 40 = 20 млн. ден. ед. вкладывают в развитие 1-го и 2-го предприятий. Из табл. 3 видно, что из этой суммы во 2-е предприятие следует вложить всю оставшуюся сумму х2 = 20 млн. ден. ед. Вложение средств в 1-ое предприятие нерентабельно. f = 91, x1 = 0, x2 = 20, x3 = 40, x4 = 40. Решение задач динамического программирования Оптимизация решения о капиталовложениях в течение нескольких временных периодов
Задача 1. Допустим, имеется возможность финансирования двух проектов в объеме 100 ден. ед. (Z1=100 ден. ед). Если в 1-й проект вложить Х ден.ед., то доход от этого проекта будет определяться функцией f(X)=4X. Если во 2-й проект вложить Y ден.ед., то доход от этого проекта будет определяться функцией g(Y)=3Y. Уменьшение остатка средств после вложения в 1-й и 2-й проекты происходит в соответствии с законами: φ(X)=0,2Х (для первого проекта) и Ψ(Y)=0,6Y (для второго проекта). Нужно распределить данные средства в течение 3 лет таким образом, чтобы общий доход за 3 года был максимальным. Решение. Решаем задачу с конца. 1 шаг. Планируем распределение средств на 3-й год. Предположим, что общий остаток средств после второго года – к началу 3-го года равна Z3. Распределим их между проектами. Если в 1-й проект вложить Х3 ден. ед., тогда во 2-й проект останется вложить Y3=Z3 – X3. Тогда доход за 3-й год от 1-го проекта составит f(X3)=4·X3, а от 2-го проекта g(Y3)=3(Z3 – X3).
Тогда суммарный доход за 3-й год составит F3=4 X3 +3Z3 – 3X3 = X3 +3Z3 Необходимо найти максимум этой функции дохода при условии, что 0≤X3≤Z3. Уравнение F3= X3 +3Z3 линейно относительно X3. Значит, максимальное значение лежит на границах интервала. Максимум достигается в точке X3 = Z3, т.е. для максимизации дохода необходимо в 3-м (последнем) году направить все оставшиеся средства на 1-й проект. мах. доход F3*=4 Z3 2 шаг. Начало 2-го года планирования к началу 2-го года функционирования системы в нашем распоряжении средства в количестве Z2. (Остаток после 1-го года). Если в 1-й проект вложить Х2 ден. ед., тогда во 2-й проект останется вложить Y2=Z2 – X2.
Тогда суммарный доход за 2 последние года составит F2,3=4 X2 +3Z2 – 3X2 + 4Z3, но Z3 – это остаток средств после 2-го года, который можно выразить через φ(X2)=0,2Х2 и Ψ(Y2)=0,6 Y2 Z3 = 0,2X2 + 0,6Y2 = 0,2 X2 + 0,6 (Z2 – X2) = 0,6 Z2 - 0,4 X2 F2,3=4 X2 +3Z2 – 3X2 + 4 (0,6 Z2 - 0,4 X2) = 5,4 Z2 - 0,6 X2 Найти максимум этой функции дохода при условии, что 0≤X2≤Z2. Значит, в начале 2-го года все средства надо вложить в 1 проект, в результате максимальный доход F2,3*= 5,4 Z2
3 шаг. Начало 1-го года. К началу 1-го года в нашем распоряжении средства в количестве Z1. 1-й проект получает Х1 ден. ед., 2-й - Y1=Z1 – X1.
Cуммарный доход за 3 года составит F1,2,3=4 X1 +3(Z1 – X1) + 5,4Z2, но Z2 – это остаток средств после 1-го года Z2 = 0,2X1 + 0,6Y1 = 0,2 X1 + 0,6 (Z1 – X1) = 0,6 Z1 - 0,4 X1 F1,2,3= X1 +3Z1 + 5,4 (0,6 Z1 - 0,4 X1) = 6,24 Z1 - 1,16 X1 Найти максимум этой функции дохода при условии, что 0≤X1≤Z1. Все средства вкладываем во 2 проект, в результате максимальный доход F1,2,3*= 6,24 Z1 = 6,24 * 100 = 624 ден. ед. Оптимальное управление состоит в том, что в первые два года все средства нужно вложить во 2-й проект и только в 3-м году все средства нужно отдать 1-му проекту. Тогда доход будет максимальным.
2 этап.
Задачи об использовании и замене оборудования Общая постановка Для осуществления своей деятельности предприятия время от времени должно производить замену своего оборудования. При замене оборудования учитывается: 1) производительность используемого оборудования; 2) затраты на ремонт и содержание оборудования; 3) стоимость приобретенного и заменяемого оборудования. Предположим, что к началу планируемого периода на предприятии установлено новое оборудование, позволяющее за каждый τ-й год выпустить готовой продукции на сумму R(τ) рублей, а ежегодные затраты, связанные с ремонтом и содержанием оборудования равны Z(τ) рублей. В τ-й год оборудование может быть продано за S(τ) рублей, а новое куплено за С рублей. С учетом всех этих факторов найти план замены оборудования, обеспечивающий максимальную прибыль за N лет.
3адача. На предприятии установлено новое оборудование. Зависимость производительности его от времени использования, а также зависимость затрат на содержание и ремонт при различном времени использования приведены в табл. 1. Таблица 1
Зная затраты, связанные с приобретением и установкой нового оборудования (идентичного старому оборудованию), которые составляют 40 тыс.р. и то, что заменяемое оборудование списывается, составить такой план замены оборудования в течении 5 лет, при котором общая прибыль (полезный эффект) за весь период была бы максимальной
Решение Обозначим через u1 – решение сохранить (оставить) старое оборудование, а через u2 – решение о замене оборудования. 1-й этап. Начинаем от начала 5-го года. Для того, чтобы найти условно-оптимальное управление составим уравнение Беллмана. Мы предполагаем, что к концу k-го года (k=1..5) может применяться одно из 2 решений: либо сохранить, либо заменить оборудование. Исходя из этого прибыль предприятия за k-й год можем записать следующим образом: где τ(k) – возраст оборудования к началу k-го года, u(k) – управление, реализуемое к началу k-го года, С – стоимость нового оборудования. Уравнение Беллмана выглядит следующим образом: (12) это прибыль за k лет. Используя уравнение (1) начнем с определения условно-оптимального управления для последнего 5-го года. Для этого находим множество допустимых состояний оборудования к началу данного года. Т.к. к началу первого года пятилетки имеется новое оборудование, а это означает что τ(1) =0, то возраст оборудования к началу 5-го года может быть 1,2,3,4 года. Поэтому допустимые состояния на данный период таковы: к началу 5 года: τ1(5) =1; τ2(5) =2; τ3(5) =3; τ4(5) =4. Для каждого из этих состояний найдем условно-оптимальное управление, и соответствующие значения прибыли (полезного эффекта) F5(τ(5)). Используя уравнение (12) и соотношение F6(τ(6))=0, получим следующее значение прибыли: (13) Подставляя в (13) все значения τ(5) и учитывая данные табл. 1, получим: , т.к. max достигается при управлении u1. . Запишем данные в табл. 2. Таблица 2
Подходим к началу 4-го года τ1(4) =1; τ2(4) =2; τ3(4) =3. Подставляя в (13) все значения τ(5) и учитывая данные табл. 1, получим: Таблица 3
Подходим к началу 3-го года τ1(3) =1; τ2(3) =2. Таблица 4
Подходим к началу 2-го года τ1(2) =1. Таблица 5
Согласно условию к началу 1-го года состояние оборудования τ(1) =0, поэтому проблемы выбора нет и оборудование сохраняют. F1(τ(1))=80-20-40+155=175 - условно-оптимальное решение. Это максимальная прибыль соответствует оптимальному плану замены оборудования, которая получается на основе данных всех таблиц и в результате реализации 2-го этапа. 1-й год – решение единственное – оборудование сохранить. К началу 2-го оборудованию будет 1 год. Тогда в соответствии с данными табл. 5 оптимальным решением 2-го года будет решение тоже сохранить оборудование. Реализация такого решения приводит к тому, что возраст оборудования к началу 3-го года будет 2 года. Тогда в 3-м году оптимальное решение поменять оборудование (табл. 4). После замены оборудования его возраст к началу 4-го года равен 1 году. Из табл. 3 видно, что оборудование менять не следует. Поэтому к началу 5 года возраст оборудования будет 2 года и менять его не надо (табл. 2). Таким образом, оптимальный план замены оборудования: 1 год –сохранять, 2- сохранять, 3 – заменить, 4 – сохранять, 5 – сохранять.
Популярное: Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (1096)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |