Файл: Шепелев, И. Г. Математические методы планирования и управления в строительстве конспект лекций.pdf

целевой функции и ограничений (5.2.1), (5.2.2); 2) степень ди­ намичности модели; 3) непрерывность функций; 4) степень не­ определенности функций.

Приведем краткую характеристику методов программирова­ ния, внесенных в схему (рис. 9).

По виду математических выражений различают линейное и нелинейное программирование. Если оптимизируемая функция и ограничения линейны, т. е. все переменные выражены в первой степени, то задачи относятся к классу задач линейного про­ граммирования, если же в модели все математические выраже­ ния, или хотя бы одно из них, нелинейны, т. е. переменные участ­ вуют в степени, отличной от первой, или в выражении есть про-

Рис. 9. Схема классификации методов оптимального програм­ мирования

3 И. Шепелев

изведения переменных, то такие задачи относятся к классу за­ дач нелинейного программирования.

По степени динамичности модели методы подразделяются на статические и динамические. Если задача поставлена в стати­ ке, т. е. рассматривается какой-то один период времени, или задача решается в один этап, то такие задачи относятся к клас­ су статических задач и, наоборот, если поставлена задача на­ хождения оптимума не только в зависимости от изменения пере­ менных, но и в зависимости от изменения времени, или в ходе решения задача разделяется на несколько этапов, решаемых последовательно, то такие задачи относятся к классу динамиче­ ских задач.

Если целевая функция непрерывна, а на переменные не на­ ложено ограничение целочисленности, то такие задачи относятся к классу задач непрерывного программирования, если наблю­ даются разрывы целевой функции, или на переменные нало­ жено ограничение целочисленности, то такие задачи относятся к классу задач дискретного программирования.

Если целевая функция и ограничения заданы детерминиро­ ванными математическими выражениями, то такие задачи отно­ сятся к классу задач детерминированных. Если целевая функ­ ция, или хотя бы одно ограничение, заданы случайными функция-

fми, законами распределения вероятностей или вероятностями, то такие задачи относятся к классу задач стохастического программирования.

Особый класс задач представляют задачи эвристического программирования. Эвристическое программирование — это на­ хождение оптимального решения с включением элементов эв­ ристики. Эвристика — наука, изучающая закономерности твор­ ческого мышления и занимающаяся разработкой методов, ана­ логичных методам творческого мышления человека.

Задачи и методы линейного программирования в строитель­ стве достаточно полно отражены в работах [4, 6 , 11] и здесь не рассматриваются. Эвристические методы в настоящее время на­ ходятся в стадии разработки и поэтому включать их в курс лекций нет необходимости. В дальнейшем будут рассмотрены

методы динамического, стохастического и дискретного про­ граммирования.

§ 5.4. Динамическое программирование

Динамическое программирование — это метод, позволяющий найти экстремум общего критерия многошагового процесса, при этом на каждом этапе оптимизируется только один шаг;

66

решения, принимаемые на последующих шагах, не оказывают влияния на предыдущие решения. В экономике существует не­ сколько типов задач, которые по постановке или методам реше­ ния относятся к задачам динамического программирования:

1. Задачи оптимального перспективного планирования во времени. Эти задачи нашли широкое применение в СССР, и ре­ шаются двумя методами: а) путем решения изолированных ста­ тических задач для каждого из взаимосвязанных периодов с увязкой и необходимой корректировкой полученных планов, при этом, как правило, задачи решаются методом линейного про­ граммирования; б) решение одной динамической задачи оп­ тимального программирования, с применением многошаговой процедуры принятия решений.

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

2. Задачи многошагового нахождения оптимума при разме­ щении призводства в статическом периоде. Например, для про­ изводства однородного продукта необходимо построить несколько предприятий. Известны размеры каждого из предприятий, необ­ ходимые в каждом случае капиталовложения и возможная при­ быль. Необходимо определить оптимальное, в смысле макси­ мальной прибыли, количество предприятий и их мощности для получения необходимого количества продукта. Задача относит­ ся к динамическому программированию, так как решается ме­ тодами многошаговой оптимизации. При этом нахождение мак­ симума функции многих переменных заменяется многократным нахождением максимума одного переменного.

3. Задачи оптимального быстродействия. Допустим, что известна некоторая оптимальная структура производства с кри­ терием эффективности Ui. В настоящее время существует неоп­

В основу метода динамического программирования зало­ жен известный принцип, сформулированный Ричардом Белманом [1, 3, 5]. Смысл этого принципа заключается в том, что оптимальное управление обладает таким свойством, что каково бы ни было начальное состояние и начальное управление, по­ следующее управление должно быть оптимальным к состоянию, получающемуся в результате действия начального управления. Короче говоря, если в данный момент времени не выбирается оптимальное управление, то впоследствии ошибку исправить невозможно. При решении задач динамического программиро­ вания используют определенный набор стандартных понятий и обозначений: фазовые переменные (переменные, которые ха­ рактеризуют объект управления и могут быть подвержены управляющему воздействию. Обозначают их через Pi; qi — управ­ ления, это те возможные стратегии, которые переводят началь­ ное состояние Pi_i в состояние'Pi. Задача решается многократ­ но до приведения системы в конечное состояние Рп, т. е. отыски­ вается максимум

где F (Р2) — максимум функции (5.4.1).

Соотношения (5.4.1—5.4.2) называются рекуррентными со­

К? — капиталовложения по каждому предприятию в зависимо­

. <38

данном продукте за счет строительства одного предприятия, ес­

После этого рассматривают возможность удовлетворения по­ требности в данном продукте за счет строительства двух пред­ приятий и определяют шах функции F2 = шах [Иг (х2)

+ U] (Х\)~\ при ограничениях:

х, -{- х-~> А

одним переменным, вместо решения одной задачи с п-перемен- ными.

Рассмотрим пример применения метода динамического про­ граммирования в данной постановке.

Т1еобходимо оптимально распределить капиталовложения в строительство новых предприятий в угольных бассейнах, кото­ рые условно назовем: первый, второй, третий и четвертый. Об­ щий объем капитальных вложений А равен 10 млн. руб. Допу­ скается, что угольная промышленность находится на таком уровне, когда объем добычи не является критерием оптималь­ ности. В качестве критерия принимается чистая прибыль, яв­ ляющаяся функцией капиталовложений. Чистая прибыль от ре­ ализации угля с учетом его качества, горных условий и затрат на транспортировку в разных бассейнах различна.

Функции прибыли: fi (х) — по первому бассейну, f2 (х) — по

бассейнам представлена в табл. 13.

69