Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Динамическое программирование. Распределение капитальных вложений




Динамическое программирование - это вычислительный метод для решения задач управления определённой структуры. Данная задача с n переменными представляется как много шаговый процесс принятия решений. На каждом шаге определяется экстремум функции только от одной переменной.

Рассмотрим нелинейную задачу распределения ресурсов между предприятиями отрасли. Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через fj(xj) прирост мощности или прибыли на j-том предприятии, если оно получит xj рублей капвложений. Требуется найти такое распределение (х1, х2,..., хn) капвложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли

Z=f1(x1)+f2(x2)+...+fn(xn)

при ограничении по общей сумме капвложений х1 + х2 +...+хn = b, причём будем считать, что все переменные xj принимают только целые значения xj =1,2,...

Функции fj(xj) мы считаем заданными, заметив, что их определение -довольно трудоёмкая экономическая задача.

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

Введём параметр состояния и определим функцию состояния. За параметр состояния x примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния Fk(x) определим как максимальную прибыль на первых k предприятиях, если они вместе получат x рублей. Параметр x может меняться от 0 до b. Если из x рублей k-ое предприятие получит Хк рублей, то каково бы ни было это значение, остальные x-Хк рублей естественно распределить между предприятиями от 10-го до (к-1)-го предприятия, чтобы была получен максимальная прибыль Fk-1(x-xk). Тогда прибыль k предприятий будет равна fk(xk) + Fk-1(x-xk). Надо выбрать такое значение xk между 0 и x, чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению:

Fk(x) = max {fk(xk) + Fk-1(x-xk)}

0 £ X £ x

для k=2,3,....,n.Если же k=1,то

F1(x)=f1(x).

В нашем случае производственное объединение состоит из 4-х предприятий (k=4).Общая сумма капвложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей.

Значения функций fj(xj) приведены в таблице 1.

Таблица 1

xj                
f1(xj)                
f2(xj)                
f3(xj)                
f4(xj)                

Прежде всего заполняем таблице2. Значения f2(x2) складываем со значениями F1(x-x2)=f1(x-x2) и на каждой побочной диагонали находим наибольшее число, которое помечаем звёздочкой. Продолжая процесс табулируем функции F3(x), x3(x) и т.д. В таблице 6 заполняем только одну диагональ для значения x=700.

Таблица 2

x-х2                
X2 F(x-x2) f2(x2)                
      15*            
    15* 30* 41* 52* 61*     ---
          61* 70* 77* --- ---
              --- --- ---
            --- --- --- ---
          --- --- --- --- ---
        --- --- --- --- --- ---
      --- --- --- --- --- --- ---

Таблица 3

x                
F2(x)                
x2(x)                
x2(x)                

Таблица 4

x-х3                
Х3 F(x-x3) f2(x3)                
      15* 30*          
                  ---
    30* 45* 60* 71* 82* 91* --- ---
              --- --- ---
            --- --- --- ---
          --- --- --- --- ---
        --- --- --- --- --- ---
      --- --- --- --- --- --- ---

Таблица 5

x                
F3(x)                
X3(x)                
X3(x)                

 


Таблица 5

x-х4                
Х4 F(x-x4) f2(x4)                
                   
                  ---
                --- ---
              --- --- ---
            --- --- --- ---
          --- --- --- --- ---
        --- --- --- --- --- ---
      --- --- --- --- --- --- ---

Zmax = 107 тыс. руб.,

причем четвертому предприятию должно быть выделено

х4* = х4(700) = 200 тыс. руб.

На долю остальных трех предприятий остается 500 тыс. руб. Из Таблицы 5 видно, что третьему предприятию должно быть выделено

х3* = х3(700 - х4*) = х3(500) = 200 тыс. руб.

Продолжая обратный процесс, находим

х2* = х2(700 - х4* - х3*) = х2(300) = 100 тыс. руб.

На долю первого предприятия останется

х1* = 700 - х4* - х3* - х2* = 200 тыс. руб.

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

х1* = 200; Zmax = 107
х2* = 100;
х3* = 200;
х4* = 200

Этот план обеспечивает производственному объединению наибольший возможный прирост прибыли 107 тыс. руб.

В качестве проверки правильности решения задачи можно использовать равенство

f1(x1*) + f2(x2*) + f3(x3*) + f4(x4*) = Zmax

f1(200) + f2(100) + f3(200) + f4(200) = 26 + 15 + 30 + 36 = 107 = Zmax

Следовательно, полученные решения верны.


Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...