Навигация
МЕТОДЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
13525
знаков
4
таблицы
0
изображений
2 МЕТОДЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
Методы динамического программирования применяются при решении оптимизационных задач, в которых целевая функция или ограничения, или же первое и второе одновременно характеризуются нелинейными зависимостями. Признаками нелинейности является, в частности, наличие переменных, у которых показатель степени отличается от единицы, а также наличие переменной в показателе степени, под корнем, под знаком логарифма.
Примеры нелинейных зависимостей достаточно обширны. Например, экономическая эффективность производства возрастает или убывает непропорционально изменению масштабов производства; величина затрат на производство партии деталей возрастает в связи с увеличением размеров партии, но не пропорционально им. И в том, и в другом случае мы, по существу, сталкиваемся с проблемой переменных и условно-постоянных издержек.
Известно, что себестоимость с увеличением объема выпускаемой продукции понижается, но при нарушении ритмичности производства она может и возрастать, (за счет оплаты сверхурочных работ в конце отчетного периода). Здесь затраты представляются, как и в вышеприведенной ситуации, нелинейной функцией от объема производства.
Нелинейной связью характеризуются величины износа производственного оборудования в зависимости от времени его работы, удельный расход бензина (на 1 км пути) — от скорости движения автотранспорта и многие другие хозяйственные ситуации.
Использование в экономическом анализе метода динамического программирования покажем на простейшем примере.
Имеется некое транспортное средство грузоподъемностью W. Требуется заполнить его грузом, состоящим из предметов W различных типов, таким образом, чтобы стоимость всего груза оказалась максимальной.
Для этого введем соответствующие обозначения:
Рi—вес одного предмета i-го типа; Vi — стоимость одного предмета i-го типа; xi —число предметов i-го типа, загружаемых на имеющееся транспортное средство.
Необходимо подобрать груз максимальной ценности с учетом грузоподъемности транспортного средства W.
Математически формализовать данную экстремальную задачу можно следующим образом:
при ограничениях:
Решение задачи разбивается на п этапов, на каждом из которых определяется максимальная стоимость груза, состоящего из предметов 1-го типа (первый этап), 1-го и 2-го типов (второй этап) и т. д. Для этого воспользуемся рекуррентным соотношением (критерием оптимальности Беллмана):
— максимальная ст-ть груза, состоящего из предметов N-го типов;
—стоимость взятых предметов N-гo типа;
—максимальная стоимость груза, состоящего из предметов (N— 1) типа с общим весом не более
—наибольшее целое число, не превосходящее
.
Будем считать, f0(W) = 0 для любого W. Последовательно найдя значение функций f1,(W), f2(W),..., fn(W), можно получить полное решение сформулированной задачи.
Пусть:
Р1, = 4; Р2 = 3; Р3 = 2; Р4 = 1 (единиц груза); V1, = 28; V2 = 20; V3 = 13; V4 = 6 (денежных единиц); грузоподъемность транспортного средства W = 10 (единиц груза).
Найдем последовательно значения функций b1(W): f1(W), f2(W), f2(W), f3(W), при различных значениях W(0< W<10).
Таким образом, максимальная стоимость груза f4(10) равна 69 денежным единицам, при этом предметы 4-го типа загружать не следует, так как f4(10) = 69 достигается при х4= О (табл. 6.7).
Таблица 6.7
| W | 0—3 | 4—7 | 8—10 |
| f1(W) | 0 | 28 | 56 |
| х1 | 0 | 1 | 2 |
Таблица 6.8
| W | 0—2 | 3 | 4—5 | 6 | 7 | 8 | 9 | 10 |
| f2(W) | 0 | 20 | 28 | 40 | 48 | 56 | 60 | 68 |
| х2 | 0 | 1 | 0 | 2 | 1 | 0 | 3 | 2 |
Таблица 6.9
| W | 0—1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| f3(W) | 13 | 20 | 28 | 33 | 41 | 48 | 56 | 61 | 69 | |
| x3 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | J |
Таблица 6.10
| W | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| f4(W) | 0 | 6 | 13 | 20 | 28 | 34 | 41 | 48 | 56 | 62 | 69 |
| Х4 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
Предметы остальных типов распределяются следующим образом:
х3 = 1, так как f3(10) = 69 достигается при х3 = 1 (табл. 6.9), следовательно, вес этого предмета равен 2 единицам груза, поэтому остальные предметы можно загрузить лишь в пределах веса, равного 8(10 2) единицам груза;
f2(8) = 56 достигается при x= 0 (табл. 7.8), следовательно, предметы 2-го типа брать не следует.
И наконец, f1(8)= 56 достигается при x1 = 2 (табл. 6.7), следовательно, предметов 1-го типа следует взять два.
В итоге наилучший вариант нагрузки транспортного средства достигается при значениях х1 =2; х2 = 0; х3 = 1; х4 = 0 (берутся два предмета 1-го тина и один предмет 3-го типа).
Похожие работы
... переход к показателю реализованной продукции. В стоимостном выражении дается оценка валовой товарной продукции сельскохозяйственных предприятий, что необходимо и для подсчета совокупного общественного продукта. Совокупность информации, используемой в оценочной деятельности, должна отвечать многим требованиям, например: достаточности, достоверности, объективности, точности, комплексности и т. д. ...
... (соединение отдельных элементов в общий показатель). Таким образом, финансовый анализ играет огромную роль в аудиторской деятельности, способен оказать существенное влияние на дальнейшее развитие экономического субъекта его место в рыночной экономике. Качественный финансовый анализ - основа всего процесса аудиторской проверки, поэтому ему уделяется самое пристальное внимание как аудиторской ...
... в самостоятельную отрасль экономических знаний, он используется в экономической теории, народно-хозяйственном прогнозировании и статистике. Экономический анализ деятельности организаций обособился и занимает самостоятельное место в системе экономических наук и учебных дисциплин. Главное его обеспечение составляют системный бухгалтерский учет и бухгалтерская (финансовая) отчетность. Несмотря на ...
... к проблеме теоретической идентификации /А.И. Соловьев // Полис. - 2002. - № 3. - С.5-18 18. Тимофеева Л.Н. Политическая коммуникативистика: проблемы становления // Полис. - 2009. - №5. - С.41 - 54. 19. Федотова Л.Н. Социология массовой коммуникации: Учебник для вузов, СПб: Питер, 2004. - 400 с. 20. Шарков Ф.И. Истоки и парадигмы исследований социальной коммуникации / Ф.И. Шарков ...
0 комментариев