Метод наискорейшего подъёма.

Модификацией метода градиентного подъёма является метод наискорейшего подъёма. В этом методе после вычисления градиента в точке движутся в направлении градиента, пока целевая функция продолжает возрастать до точки . В точке процедура повторяется.

 

 

 

 

 

 

 

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

Рассмотрим простейшие задачи линейного программирования. В этом случае целевая функция и условия ограничения – линейны. Линейные ограничения на проектные параметры образуют в пространстве проектных параметров многогранник. Оптимальным решением будет соответствовать одна из вершин этого многогранника. Могут быть случаи, когда оптимальному решению соответствуют все точки на ребре или на целой грани многоугольника

 

 

 

 

 

 

Типичными задачами линейного программирования являются транспортная задача и задача об использовании ресурсов.

Тема №10

 

Задания для самостоятельной проработки.

Транспортная задача.

Автобаза обслуживает три магазина, доставляя в них товары из двух торговых баз. Известно, что ежедневно вывозится с первой базы 12т. товара, а со второй базы 15т. При этом в магазины ежедневно завозится в первый – 8т., во второй 9т., в третий 10т. Стоимость перевозки одной тонны определяется таблицей.

База	Магазин
	0, 80	1, 1	0, 90
	1, 00	0, 70	1, 20

 

Требуется спланировать перевозки так, чтобы их стоимость была минимальной.

Введём переменные величины, соответствующие количеству товара доставляемого в первый, второй и третий магазины соответственно; - количество товара поставляемого со второй базы. Стоимость перевозок запишем в виде:

- это и есть целевая функция.

- проектные параметры. На проектные параметры накладываются ограничения. Во-первых, это ограничение равенства, оно следует из условия задачи и описывает количество товаров, которые вывозят с баз и доставляют в магазины.

 

 

К данной системе необходимо добавить систему неравенств

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

А целевая функция принимает вид . Теперь условия неравенства принимают вид.

Система этих неравенств определяет область допустимых значений переменных - область . запишем систему неравенств в виде

 

 

 

Теперь мы должны найти в этой области точки, обеспечивающие минимум целевой функции. Возьмём и - это точки, которые являются узлами области .

Минимальное значение целевой функции достигается в вершине области допустимых значений .

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

Задача о ресурсах.

В распоряжении бригады имеются следующие ресурсы: 300 кг металла, 100 м² стекла, 160 чел.-ч. (человеко-часов) рабо­чего времени. Бригаде поручено изготовлять два наименования изделий: А и Б. Цена одного изделия А 1 тыс. р., для его изготовления необходимо 4 кг металла, 2 м² стекла и 2 чел.-ч. рабочего времени. Цена одного изделия Б 1.2 тыс. р., для его изготовления необходимо 5 кг металла, 1 м² стекла и 3 чел.-ч. рабочего времени. Требуется так спланировать объем выпуска продукции, чтобы ее стоимость была максимальной.

Сначала сформулируем задачу математически. Обозначим через количество изделий А и Б, которое необходимо запланировать (т. е. это искомые величины). Имеющиеся ресурсы сырья и рабочего времени зададим в виде ограничений-неравенств:

Полная стоимость запланированной к производству продукции выражается формулой

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

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

При этом очевидно, что , , . Заметим, что вве­дение дополнительных неизвестных не повлияло на вид целевой функции, которая зависит только от параметров .Фактически будут указывать остатки ресурсов, не использованные в производ­стве.

Выразим через свободные переменные . Получим

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

Этому решению соответствует нулевое значение целевой функции

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

Таким образом, полагая = 50, х₂ = 0, получаем новое решение

Значение целевой функции при этом будет равно

Новое решение лучше, поскольку значение целевой функции уменьшилось по сравнению с предыдущим.

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

Получим

 

 

 

 

Выражение для целевой функций запишем через свободные парамет­ры. Получим

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

Быстрее всех нулевого значения достигнет переменная при х₂ = 30. Дальнейшее увеличение х₂ поэтому невозможно. Следо­вательно, получаем новое опорное решение, соответствующее значени­ям х₂ = 30, = 0 и тогда

При этом значение целевой функции равно

Покажем, что полученное решение является оптимальным. Для про­ведения следующего шага ненулевые переменные , , , нужно принять в качестве базисных, а нулевые переменные х₄, х₅ — в качестве свободных переменных. В этом случае целевую функцию можно записать в виде

 

Поскольку коэффициенты при , положительные, то при уве­личении этих параметров целевая функция возрастает. Следовательно, =71 является оптимальным.

Таким образом, ответ на поставленную задачу об использовании ре­сурсов следующий: для получения максимальной суммарной стоимости продукции при заданных ресурсах необходимо запланировать изготовле­ние изделий А в количестве 35 штук и изделий Б в количестве 30 штук. Суммарная стоимость продукции равна 71 тыс. р. При этом все ресурсы стекла и рабочего времени будут использованы, а металла останется 10 кг.

 

Волновое уравнение.

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

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

Рассмотрим одномерное волновое уравнение, которое можно записать в виде

 

Для поперечных колебаний струны искомая функция U(x, t) описывает положение струны в момент t. В этом случае , где Т — натя­жение струны, — ее линейная плотность. Уравнение записано для случая свободных колебаний. Сопротивление среды колебательному процессу не учитывается.

 

 

Решим задачу Коши для этого уравнения. Вот условия задачи:

 

Эти условия описывают начальную форму струны и скорость ее точек.

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

 

 

 

 

Для решения такой задачи используем явную трехслойную схему типа крест. Заменим в начальном уравнении вторые производные искомой функции U по t и х их конечно-разностными соотношениями с помощью значений сеточной функции в узлах сетки

Отсюда можно найти явное выражение для значения сеточной функции на (j + 1)-м слое:

Здесь, как обычно в трехслойных схемах, для определения неизвестных значений на (j + 1)-м слое нужно знать решения на j-м и (j — 1)-м слоях. Поэтому начать счет можно лишь для второ­го слоя, а решения на нулевом и первом слоях должны быть известны. Они находятся с помощью начальных условий. На нулевом слое имеем

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

Из этого соотношения можно найти значения сеточной функции на пер­вом временном слое:

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

Так как,

то:

Теперь разностная схема обладает погрешностью аппрок­симации порядка .

Рассмотренная разностная схема решения задачи условно устойчива. Необхо­димое и достаточное условие устой­чивости имеет вид

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

Уравнение Лапласа.

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

При F(x, у, z) = 0, уравнение Пуассона называют уравнением Лапла­са.Для простоты будем рассматривать двумерное уравнение Лапласа

Решение этого уравнения будем искать для некоторой ограниченной об­ласти G изменения независимых переменных х, у. Границей области G является замкнутая линия L. Для полной формулировки краевой задачи кроме уравнения Лапласа нужно задать граничное условие на границе L.Примем его в виде

 

 

Задача, состоящая в решении уравнения Лапласа (или Пуассона) при заданных значениях искомой функции на границе расчетной области, называется задачей Дирихле.

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

Поскольку решение U(x, y) уравнения Лапласа не зависит от времени, то можно в это уравнение добавить равный нулю (при точном решении) член . Тогда уравнение примет вид

Это — известное нам уравнение теплопроводности, для которого мы уже строили разностные схемы. Остается только задать на­чальное условие. Его можно принять практически в произвольном виде, согласованном с граничными условиями. Положим

Граничное условие при этом остается стационарным, т. е. не зави­сящим от времени.

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

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

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

Другой способ решения задачи Дирихле состоит в построении разностной схемы путем аппроксимации уравнения Лапласа. Вве­дем в прямоугольной области G сетку с по­мощью координатных прямых х = const и у = const. Примем, для простоты значения шагов по переменным, х и у равными h (пред­полагается, что стороны области G соизме­римы). Значения функции U в узлах заменим значениями сеточной функции Тогда, аппроксимируя в урав­нении Лапласа вторые производные с помощью отношений конечных раз­ностей, получим разностное уравнение.

С помощью данного уравнения можно записать систему линейных алгебраических уравнений относительно значений сеточной функции в узлах в виде

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

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

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

Такой способ можно использовать и для решения уравнения Лапласа. Пусть требуется решить для него задачу Дирихле в прямоугольнике ABCD. Разо­бьем прямоугольник на полосы с помощью прямых, параллельных оси х. Для определенности проведем три отрезка , которые разделят прямоугольник на четыре полосы постоянной ширины h. Решение U задачи Дирихле приближенно заменим набором функций , каждая из которых определена на отрезке U и зависит только от одной переменной х, т. е. = для =1, 2, 3. На отрезках значения заданы граничными условиями.

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

Таким образом, решение задачи Дирихле сводятся к ре­шению краевой задачи для системы обыкновенных дифференциальных уравнений относительно значений искомой функции вдоль пря­мых . В этом состоит метод прямых. Граничные условия при х=а, х = b можно получить из уравнений

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

 

 

⇐ Предыдущая123456789

Поделиться: