Файл: Чесноков, Н. И. Оптимизация решений при разработке урановых месторождений.pdf

но появится опасность пропустить в промежутке между двумя соседними точками искомый оптимум. Чрезмер­ ное уменьшение а может привести к неоправданно боль­ шому числу приближений (шагов). Кроме того, направ­ ление градиента не всегда совпадает с линией, соеди­ няющей начальную точку с точкой оптимума, в связи с чем могут иметь место отклонения от этой линии и обус­ ловленное этим замедление скорости сходимости. В на­ стоящее время существуют методы выбора оптимальных коэффициентов [55] и расчета поправок к градиенту с использованием вторых частных производных для сни­ жения отклонения от линии, соединяющей начальную и оптимальную точки.

Приведем пример использования градиентного мето­ да для решения нелинейной задачи. Для простоты и сравнения рассмотрим нелинейную задачу предыдуще­ го раздела и решим ее с использованием градиентного метода.

В данном примере следует найти maxZ = 2xi—х^+ + х2 при условии 2хі + а'2^4, 2хі+ 3x2^6.

Определим частную производную целевой функции

где у = (хі, хг) — обозначение точек; (2—2хь 1 )— коор­ динаты точек градиента, представленные в виде векто­ ра-строки (это и есть вектор частных производных).

Примем за исходную (начальную) точку начало ко­ ординат, т. е. г/0= (0, 0). Вычислим для этой точки гра­ диент, т. е. подставим значения у0 в выражение (3.79), тогда

Следующая точка в соответствии с (3.78) будет иметь координаты yi^yo + aiZ'(уо): подставив значения, по­ лучим

181

максимально допустимое значение а = 0,857. Зная допу­ стимое значение а, можно определить максимально воз­ можное. Для этого в целевую функцию подставляем значение у\ из уравнения (3.81):

Z = 2-2х — (2а)2 -|- а, дифференцируем ее и приравниваем нулю:

можное значение а меньше допустимого, и мы не дохо­

т. е. отличается от градиента Z'(y0), а это значит, что и двигаться дальше мы должны в сторону нового гра­ диента:

Откуда «9= 0,8125, что означает 0 ^ а 2^0,8125.

Второе ограничение дает ос2<0,8125, что легко про­ верить. Подставляя в целевую функцию значение у2 из уравнения (3.85), дифференцируя и приравнивая ее нулю, получаем максимально возможное а2:

Z = 2 (1,25 — 0,5'Ло) — (1,25 — 0,5х,)2 4- 0,625 + „,

Z' = — 1 + 1,25 — 0,25аа + 1 = 0 ,

а2 = 5.

Итак, мы можем принять а2 = 0,8125. Тогда, подставляя

значения у\, а2, Z'(уі) в (3.85), получим координаты третьей точки, приближающей нас к максимуму:

или

№ = (0,844; 1,44).

182

В точке у2 градиент Z' (у2) [см. уравнение (3.79)] тогда

будет иметь следующее значение:

Z'(y,) = (2 — 2-0,844; 1,00) = (0,312; 1). (3.87)

Четвертая точка в соответствии с (3.79) должна иметь координаты

Уз — (0,844; 1,44)+ (-0,0022).(0,312; 1,0),

или

у3 = (0,844; 1,438).

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

Сравните: У2 —(0,844; 1,44) и і/3= (0,844; 1,438). Про­

верим еще раз полученные данные с точки зрения вы­ полнения граничных условий: 2а'і+ х2< 4,2-0,844 +

+ 1,438 = 3,126<4, 2х\ + Зх2< 6,2 • 0,844 + 3-1,438 = 6,00.

Проверка показала, что точка максимума находится на граничной липни 2л'і+ З х 2 = 6.

Вычислим теперь значение целевой функции в най­ денной точке: ma.\Z = 2 - 0,844—0,8442+ 1,438 = 2,426. Ра­ нее для этой же задачи было получено х'і = 0,75, я?=1,5,

ZMUKC= 2,4374.

Сравнение результатов расчета двумя разными ме­ тодами показывает, что разница между ними составляет менее 0,5% и не может играть существенной роли при оценке точности того или другого приближенного мето­ да. Конечно, можно было бы продолжить расчеты на­ шего примера с помощью градиентного метода и даль­ ше, но, как только что было указано, к существенному повышению точности определения оптимума это все равно не привело бы.

183

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

4. Д И Н А М И Ч Е С К О Е П Р О ГР А М М И РО В А Н И Е

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

Таким образом, динамическое программирование мо­ жет быть применено как самостоятельный метод про­ граммирования и как один из эффективных вычисли­ тельных методов [13, 26, 35, 38].

Основы метода динамического программирования были разработаны Веллманом [13, 55], который и дал ему название.

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

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

Прежде чем перейти к рассмотрению сущности ди­ намического программирования, следует отметить, что

184

при решении задач оптимизации, в которых в качестве одной из переменных является время, кроме динамиче­ ского программирования, применяются дифференциаль­ ное и вариационное исчисления. При этом дифферен­ циальное и вариационное исчисления применяются при условии непрерывности переменных и функций. В дан­ ной работе решение задач с непрерывным временем не приводится, так как это потребовало бы изложения од­ ного из крупных разделов высшей математики — вариа­ ционного исчисления. Кроме того, учитывая стохастиче­ ский характер изменения состояния горнорудного про­ изводства, в особенности на урановых рудниках, наибо­ лее надежным периодом времени для принятия опти­ мального решения может быть 1 месяц, 1 квартал или даже 1 год [24, 26, 35]. Поэтому для условий горноруд­ ного производства с успехом может быть принято ди­ скретное изменение времени при решении задач дина­ мического программирования.

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

Будем решать эту задачу методом математической ин­ дукции. Предположим, что известію значение хп, мак­ симизирующее Z, и соответствующее ему значение fn(x-n). Тогда можно переписать уравнение (3.89) в сле­ дующем виде:

уже выбрано, граничные условия должны быть записа­ ны в следующем виде:

185