Решение задач и выполнение научно-исследовательских разработок: Отправьте запрос сейчас: irina@bodrenko.org    
математика, IT, информатика, программирование, статистика, биостатистика, экономика, психология
Решение задач: по математике, IT, экономике, психологии




 Динамическое программирование , Нефть и газ , Методы SEO оптимизации SEO оптимизация Компьютерные науки Математика и информатика Векторный и тензорный анализ Теория игр Аналитическая геометрия и линейная алгебра Дифференциальная геометрия и топология Дополнительные главы дифференциальной геометрии Bodrenko.com Bodrenko.org © 2008-2012 Bodrenko.org: Irina I. Bodrenko. All rights reserved.
© 2008-2012 Bodrenko.org: Ирина Ивановна Бодренко. Все права защищены

Bodrenko.org

Bodrenko.com
Bodrenko.org

Учебные дисциплины на сайте Bodrenko.org
Портабельные Windows-приложения на сайте Bodrenko.com
Методы SEO оптимизации - SEO оптимизация - "Геометрические методы математической физики" Компьютерные науки Математика и информатика Векторный и тензорный анализ Теория игр Аналитическая геометрия и линейная алгебра Римановы многообразия Элементы вариационного исчисления Дифференциальная геометрия и топология "Геометрия подмногообразий" Дополнительные главы дифференциальной геометрии "Дифференциальные уравнения на многообразиях" "Дифференциальная геометрия и топология кривых" Bodrenko.com Bodrenko.org


ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ РЕСУРСАМИ, МАКСИМИЗИРУЮЩЕЕ ЦЕЛЕВУЮ ФУНКЦИЮ ПРИБЫЛИ
2.1. Динамическое программирование
Реально функционирующая большая экономическая система требует еженедельного принятия микроэкономических решений. Взятое по отдельности каждое такое решение малосущественно, но их совокупность может оказать большое влияние на прибыль.
В динамическом программировании для управляемых процессов среди всевозможных управлений ищется то, которое доставляет экстремальное (наименьшее или наибольшее) значение целевой функции --- некоторой числовой характеристике процесса. Процесс принятия решения разбивается на этапы (шаги). Такие операции называются многошаговыми. Таким образом, в названии "динамическое программирование" под программированием понимают принятие решений, планирование, а слово динамическое указывает на существенную роль времени и порядка выполнения операций в рассматриваемых процессах и методах. Проиллюстрируем основную идею. Пусть процесс управления S некоторой системой состоит из m шагов. На i-м шаге управление X_i переводит систему S из состояния s_i-1, достигнутого в результате (i-1)-го шага, в новое состояние s_i. Этот процесс перехода осуществляет заданная функция s_i = f_i(s_i-1,X_i), и новое состояние определяется значениями s_i-1,X_i). Таким образом, управления X_1, ..., X_m переводят систему из начального состояния s_0 в конечное --- s_m. Пусть X(X_1, ..., X_m) --- управление, переводящее систему S из состояния s_0 в состояние s_m. Показатель эффективности рассматриваемой управляемой операции --- целевая функция Z = F(s_0, X). Выделим особенности модели динамического программирования: --- задача оптимизации интерпретируется как m-шаговый процесс управления; --- целевая функция равна сумме целевых функций каждого шага; --- выбор управления на k-м шаге зависит только от состояния системы к этому шагу и не влияет на предшествующие шаги (нет обратной связи); --- состояние s_k после k-го шага управления зависит только от предшествующего состояния s_k-1 и управления X_k (отсутствие последействия); --- на каждом шаге управление X_k зависит от конечного числа управляющих переменных, а состояние s_k --- от конечного числа параметров. Вычислительная схема в задачах динамического программирования основана на принципе оптимальности Беллмана и использует рекуррентные соотношения. Принцип оптимальности впервые был сформулирован Р.Беллманом в 1953 году: каково бы ни было состояние s системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило бы к оптимальному "выигрышу" на всех оставшихся шагах, включая данный.

2.2. Задача об оптимальном вложении денежных средств
в нефтепереработку

Нефтяная компания планирует эксплуатацию четырех нефтеперерабатывающих заводов на очередной год. Начальные средства составляют s_0 = 5 у.е._1. В зависимости от наличия на НПЗ условий для деструктивных углубляющих технологий, приносящих максимальную прибыль, облагораживающих технологических процессов и прочих углубляющих процессов, а также облагораживающих технологических процессов и т.д., k-й НПЗ (k=1,2,3,4) приносит в конце года прибыль f_k(x) при вложении в него x у.е._1 денежных средств. Пусть максимальная прибыль, при неограниченном увеличении вложений денежных средств в любой из НПЗ не превышает 4 у.е._ 2. Заметим, что условные единицы вложений и прибылей в задаче различны, например, вложения можно измерять в рублях, а прибыли в долларах, а также в любых других валютах и пропорциях.

Пример расчета 1 у.е._ 2

По данным таблицы 1 [1, c. 99] в 2003 году объем нефтепереработки в России составил 190 млн. т. а прибыль предприятий от нефтепереработки составила 21 млрд. руб. Значит, в среднем прибыль от переработки 1 т. сырой нефти в среднем приближенно равна 21*10^3/190 = 110,52631 руб. за 1 т. По данным [2, c. 19] в России 25 НПЗ мощностью 257,8 млн. т. в год. Предприятия нефтеперерабатывающей отрасли в 2003 году были загружены на 69,2%. Значит, на всех российских НПЗ в 2003 году было переработано 257,8 * 0,692 = 178,3976 млн. т. Таким образом, в среднем на 1 НПЗ было за год переработано 178,3976/25 = 7135904 т. Следовательно, прибыль 1 НПЗ за год в среднем равна 7135904 * 110,52631 = 788705137,63424 руб. т.е. порядка 800 млн. руб. (при загрузке мощностей на 69,2%.)

Исходя из этих данных, условно можно считать, что 1 у.е._ 2 имеет в задаче порядок 1 млрд. руб.

Предположим, что функции прибылей подчинены закону Госсена об убывающей полезности и имеют вид: f(x) = a_0 + (a_0 a_1)/( x - a_1). (2.1) Коэффициенты в уравнении (2.1) подчинены неравенствам: a_0 >0, a_1<0. В соответствии с данными, приведенными в таблице 4 [2, с. 21], предположим, что --- первый НПЗ функционирует по первому варианту и при вложении в него 9,14 у.е._ 1 коэффициент загрузки НПЗ составляет 91,4% к мощности, и следовательно, при вложении в него 9,14 у.е._ 1 первый НПЗ дает прибыли 1,75 у.е._ 2 --- второй НПЗ функционирует по второму варианту и при вложении в него 9,42 у.е._ 1 коэффициент загрузки НПЗ составляет 94,2% к мощности, и следовательно, при вложении в него 9,42 у.е._ 1 он дает прибыли 2,4 у.е._2; --- третий и четвертый НПЗ функционируют по третьему варианту, но при этом, на третьем НПЗ при вложении в него 9,87 у.е._ 1 коэффициент загрузки НПЗ составляет 98,7% к мощности, и следовательно, при вложении в него 9,87 у.е._ 1 он дает прибыли 3,53 у.е._ 2, на четвертом НПЗ при вложении в него 10 у.е._ 1 коэффициент загрузки НПЗ составляет 100% к мощности, и следовательно, при вложении в него 10 у.е._ 1 он дает прибыли 3,9 у.е._2 в конце года. Найдем вид функций f_k(x) исходя из данных условий. Учитывая, что a_0 = 4 у.е._ 2, находим: f_1(9,14) = 4 + (4 a_1)/( 9,14 - a_1) = 1,75; f_2(9,42) = 4 + (4 a_1)/( 9,42 - a_1) = 2,4; f_3(9,87) = 4 + (4 a_1)/( 9,87 - a_1) = 3,53; f_4(10) = 4 + (4 a_1)( 10 - a_1) = 3,9. Выражая коэффициент a_1, найдем функции f_k(x), k=1,2,3,4: f_1(x) = 4 - 47/(x+11,75), f_2(x) = 4 - 25,12/(x+6,28), f_3(x) = 4 - 5,24/(x+1,31), f_4(x) = 4 - 1,04/(x+0,26). Далее, составим для функций f_k(x) таблицу значений:

Таблица 1

x f_1(x) f_2(x) f_3(x) f_4(x)
1 0,31 0,55 1,73 3,17
2 0,58 0,97 2,42 3,54
3 0,81 1,29 2,78 3,68
4 1,02 1,56 3,01 3,76
5 1,19 1,77 3,17 3,80

Обозначим через x_k количество средств, выделенных k-му НПЗ. Суммарная прибыль равна Z =um_k=1^4 f_k(x_k). (2.2) Переменные x удовлетворяют ограничениям um_k=1^4 x_k = 5, x_k >= 0, k=1,2,3,4. (2.3) Требуется найти переменные x_1, x_2. x_3, x_4, удовлетворяющие системе ограничений (2.3) и обращающие в максимум функцию (2.2). Схема решения задачи методом динамического программирования имеет следующий вид: процесс решения распределения средств s_0 = 5 у.е._1 можно рассматривать как 4-шаговый, номер шага совпадает с номером НПЗ, выбор переменных x_1, x_2, x_3, x_4 --- управление соответственно на I, II ,III , IV шагах, s --- конечное состояние процесса распределения равно нулю. Уравнения состояний в данной задаче имеют вид s_k = s_k-1 - x_k, k=1,2,3,4, где s_k --- параметр состояния --- количество средств, оставшихся после k-го шага, т.е. средства, которые остается распределить между оставшимися (4-k) НПЗ. Введем в рассмотрение функцию Z_k(s_k-1 --- условную оптимальную прибыль, полученную от k-го, ..., до 4-го НПЗ включительно, при условии, что между ними средства s_k-1 распределены оптимально. Допустимые управления на k-м шаге удовлетворяют условию: 0<= x_k <= s_k-1 (либо k-му НПЗ ничего не выделяем, т.е. s_k = 0, либо не больше того, что имеем к k-му шагу, т.е. x_k<= s_k-1.

Решение задачи оформим с помощью таблицы 2.

Шаг IV. Из таблицы 1 видно, что для f_4(x) прибыли монотонно возрастают, поэтому все средства, оставшиеся к 4-му шагу, следует вложить в 4-й НПЗ. При этом, для возможных значений s_3= 0, 1,..., 5 получим Z*_4(s_3) = f_4(s_3) и x*_4(s_3) = s_3.

Шаг III. Делаем все предположения относительно остатка средств s_2 к 3-му шагу (т.е. после выбора x_1 и x_2). s_2 может принимать значения 0, 1,2,3,4,5 (например s_2=0, если все средства отданы 1-му и 2-му НПЗ, а s_2=5, если 1-й и 2-й НПЗ ничего не получили). Искомая оптимизация дана в таблице 2 при k=3.

Шаг II. Условная оптимизация проведена в таблице 2 при k=2.

Шаг I. Условная оптимизация проведена в таблице 2 при k=1 для s_0=5.

Таблица 2

s_k-1 x_k s_k k=3 k=3 k=3 k=2 k=2 k=2 k=1k=1k=1
f_3(x_3)+ Z*_4(s_3) Z*_3(s_2) x*_3(s_2) f_2(x_2)+ Z*_3(s_2) Z*_2(s_1) x*_2(s_1) f_1(x_1)+ Z*_2(s_1) Z*_1(s_0) x*_1(s_9)
1 2 3 4 5 6 7 8 9 10 11 12
0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 3,17 3,17 0 3,17
1 1 0 1,73 3,72 3,72 1 0,31
2 0 2 3,54 4,90 4,90 4,90 4,90 0
2 1 1 4,90 4,90 1 3,72 4,03
2 2 0 2,42 0,97 0,58
3 0 3 3,68 5,59 5,59 0 5,59 5,59 0
3 1 2 5,27 5,45 5,21
3 2 1 5,59 5,59 2 4,14 4,30
3 3 0 2,78 1,29 0,81
4 0 4 3,76 5,96 6,14 6,14 0
4 1 3 5,41 6,14 6,14 1 5,90
4 2 2 5,96 5,96 2 5,87 5,48
4 3 1 5,95 4,46 4,53
4 4 0 3,01 1,56 1,02
5 0 5 3,80 6,32 6,56 6,56 0
5 1 4 5,49 6,51 6,45
5 2 3 6,10 6,56 6,56 2 6,17
5 3 2 6,32 6,32 3 6,19 5,71
5 4 1 6,18 4,73 4,74
5 5 0 3,17 1,77 1,19

Выводы. Максимум суммарной прибыли равен 6,56 у.е._ 2 при условии, что первый НПЗ ничего не получит, второму НПЗ будет выделено 2 у.е._ 2, третьему НПЗ --- 2 у.е._ 2, четвертому НПЗ --- 1 у.е._ 2. Таким образом, максимальную прибыль мы получим, вложив все средства в НПЗ, работающие по 2-му и 3-му вариантам.

Литература


1. Нефть России// 2004, N 7.
2. Нефть России// 2004, N 8.
3. Беллман Р. Динамическое программирование, пер. с англ., М. 1960.
4. Хедли Дж., Уайтин Т. Анализ систем управления запасами, пер. с англ., М., 1969.
5. Математическая энциклопедия, т.2. М., 1979.