Задачи оптимального управления

Задачи оптимального управления

1. Понятие об управлении

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

2. Оптимизация процессов управления

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

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

Оптимизация системы – процесс поиска наилучшего варианта её структуры и численного значения её параметров.

3. Оптимизация систем классическими математическими методами

а) Функция одной переменной

Пример 1. Исследовать на экстремум функцию

тогда: , т.е. , .

Т.к. , то при  функция достигает максимума,

Т.к. , то при  функция достигает минимума.

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

Если число  четное:

• при условии  функция имеет минимум в точке ;
• при условии , функция имеет максимум в точке .

Если число  нечетное – экстремума не существует, а точка  является седловой точкой.

б) Функция  переменных

,

где X – это вектор с координатами .

Градиент функции

.

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

Необходимое условие экстремума функции в точке :

или

 при .

Достаточное условие экстремума:

• для минимума функции – положительно определенная матрица ;
• для максимума функции – отрицательно определенная матрица .

Пример 2.

Исследовать на экстремум функцию

Необходимое условие существования экстремума

выполняется при , , .

Достаточное условие существования экстремума

.

Т.к. матрица  положительно определена, все её собственные значения положительны, значит в точке с координатами (2, 4, 6) функция  достигает минимума. Решить уравнение вида  не всегда просто. Поэтому разработаны итерационные методы оптимизации: «золотого сечения», «чисел Фибоначчи» для формул одного градиента и др. для функций нескольких переменных. Можно считать общеизвестным, что проблема оптимизации – одна из центральных в науке и технике.

Методы оптимального планирования составляют сущность математического программирования.

4. Математическое программирование

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

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

Основы линейного программирования.

Здесь слово «программирование» понимается как планирование. Основные идеи линейного программирования возникли во время второй мировой войны в связи с поиском оптимальных стратегий при ведении военных операций. С тех пор они нашли широкое применение в промышленности, торговле и государственных масштабах. Этими методами решить многие (хотя не все) задачи, связанные с эффективным использованием ограниченных ресурсов.

Пример 3.

Фирма производит две модели А и В сборных книжных полок. Их производство ограничено наличием сырья и временем машинной обработки. Для каждого изделия модели А требуется 3 м3 досок, а для изделия модели В – 4м3. Фирма может получить от своих поставщиков до 1700м2 досок в неделю. Для любой модели А требуется 12 минут машинного времени, а для изделия В – 30 минут. В неделю можно использовать 160 часов машинного времени. Сколько изделий каждой модели следует выпускать в неделю, чтобы получить максимальную прибыль, если изделие модели А приносит 2 доллара прибыли, а любое изделие модели В – 4 доллара прибыли?

Чтобы сформулировать эту задачу математически, обозначим  – количество выпущенных за неделю полок модели а,  – модели В.

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

                                                                                (1)

Функцию, которую надо оптимизировать называют целевой функцией.

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

 и .

И никаким подбором  и нельзя обратить эти производные в нуль. Чтобы увеличить, надо увеличить  и . Но  и  нельзя бесконечно увеличивать. Эти значения ограничены лимитами на сырьё и машинное время. Поскольку  и  выражают еженедельный объём выпускаемых изделий, то они не могут быть отрицательны, то есть

                                                                                (2)

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

Для досок:

.

;                                                        (3)

Для машинного времени:

.

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

.

Стандартная и основная задачи линейного программирования

Определение 1.

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

.                                                                                (7)

при условиях:

;                                                                        (8)

;                                                                (9)

,

,                                                                        (10)

где  - заданные постоянные величины и .

Определение 2.

Функция (7) называется целевой функцией (или линейной формой) задачи (7-10), а условия (8-10) ограничениями этой задачи.

Определение 3.

Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении такого малого или минимального значения функции (7) при выполнении условий (8) и (9), где  и .

Определение 4.

Основной (или канонической) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции(7) при выполнении условий (9) и (10), где  и .

Определение 5.

Вектор , удовлетворяющий ограничениям задачи (8-10) называется допустимым решением (или опорным планом)

Определение 6.

План , при котором целевая функция задачи (7) принимает своё максимальное (минимальное) значение, называется оптимальным.

Значение целевой функции (7) при плане  будем обозначать . Следовательно,  - оптимальный план, если для любого  выполняется неравенство  или неравенство .

Определение 7.

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

Определение 8.

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

Таким образом, сформулируем задачу. Дана линейная функция

                                                        (11)

и система ограничений вида:

,                                                        (12)

, ,                                                                        (13)

где ,  и  - заданные постоянные величины. Найти такие неотрицательные значения , которые удовлетворяют системе ограничений (12) и доставляют линейной функции (11) максимальное значение.

Векторная система записи:

Максимизировать линейную функцию вида

при ограничениях

, ,                                                (14)

где:

•  - вектор с координатами ;
•  - вектор с координатами ;
•  - скалярное произведение векторов  и .

Векторы

,                ,                 … ,        ,                 

состоят из постоянных коэффициентов при неизвестных и свободных членов.

Матричная форма записи

Минимизировать линейную функцию

при ограничениях

, ,

где

•  - матрица строка;
•  - матрица системы, имеющая размерность ;
•  - матрица столбец;
•  - матрица столбец.

Пример 4.

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

                                                                (1)

при ограничениях

,                                                        (2)

, .                                                                        (3)

Решение:

Каноническая форма задачи характеризуется следующими тремя признаками:

1. Однородная система ограничений в виде системы уравнений;
2. Однородные условия неотрицательности распространяются на все переменные, участвующие в задаче;
3. Максимизация линейной функции.

В этой задаче нарушены все три признака.

Первый шаг:

Преобразуем систему ограничений (2). Это преобразование выполняется путем введения неотрицательных «балансовых» переменных ,  и  в левые части неравенств со знаками «плюс» или «минус» в зависимости от знака неравенства. В результате (2) и (3) запишутся в следующем виде:

,                                                        (2/)

, ,, , .                                                (3/)

Второй шаг:

Преобразуем неохваченные на первом шаге переменные х и х, которые назовём «произвольными». Можно воспользоваться двумя приёмами.

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

Второй прием более сложный. На начальном этапе, он упрощает дальнейшие расчеты, так как связан с уменьшением как числа переменных, так и числа уравнений. Сущность его заключается в следующем. Найдем из каких-либо двух уравнений системы (2) «произвольные» переменные х3 и х4, выразив их через остальные переменные, а потом исключим с помощью найденных выражений эти переменные из остальных уравнений системы и из данной линейной функции (1). Практически это можно сделать с помощью таблиц Гаусса (таблица 1), если в них соответственно выбрать в качестве разрешающих столбцы при переменных х3 и х4.

Таблица 1

Кроме коэффициентов и свободных членов всех пяти уравнений (2), в таблицу внесена еще строка, соответствующая линейной функции (1), рассматриваемой как шестое уравнение z + 2х+х+ 3х- 2х= 0. Таким образом можно одновременно вести исключение х3 и х4  из уравнений системы и из линейной функции Z. После второй операции получили два уравнения (четвертое и первое), разрешенные относительно произвольных переменных х3 и х4:

,                                                        (4)

а остальные выражения и функция Z не зависят от этих переменных:

,                                                        ()

.                                                                ()

Все переменные, входящие в выражения () и (), подчинены условиям неотрицательности

.                                                        ()

Третий шаг:

Переход к задаче максимизации линейной функции осуществляется путем введения новой функции Z, из равенства

.                                                        ()

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

Пример 4.

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

при ограничениях

,

Решение:

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

,

разрешенное относительно базисной переменной z. Выполняя преобразования метода последовательных исключений, не следует выбирать в качестве разрешающей строку, соответствующую последнему уравнению. Таким образом, оно будет оставаться разрешенным относительно базисной переменной z (таблица 2).

Таблица 2

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

.

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

при ограничениях

,

,

или

,

.

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

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

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

Графический метод решения задачи линейного программирования

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

Найти минимальное значение функции:

                                                                        (1)

при

                                                                (2)

                                                                                (3)

Допустим, что система (2) при условии (3) совместна и ее многогранник решений ограничен. Построим его и график линейной функции при z=0. Тогда поставленной задаче линейного программирования можно дать следующую интерпретацию. Найти точку многогранника решений, в которой прямая  - опорная и функция z при этом достигает минимума.

Значения  возрастают в направлении нормали к прямой =, поэтому прямую z=0 передвигаем параллельно сомой себе в направлении . Из рисунка 1 следует, что прямая дважды становится опорной к многоугольнику решений (A и С), причем минимальное значение принимает в точке А.

Рис. 1

Координаты точки А находим решая систему уравнений прямых АВ и AE. Если многоугольник решений представляет собой неограниченную область, то возможны случаи:

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

Второй случай. Прямая, передвигаясь все же становится опорной для многоугольника решений (рисунок 2).

Рисунок 2а

Рисунок 2б

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

Рисунок 2в

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

Задача использования сырья

Для изготовления двух видов продукции  используют три вида сырья:Все данные приведены в таблице 1.

Таблица 1

Обозначим:  количество единиц продукции ,  количество единиц продукции . Тогда получим систему ограничений:

.

Знак «» показывает, что количество сырья, затрачиваемое на изготовление продукции не должно превышать запасы.

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

Логическая цель задачи – получение максимальной прибыли. Реализация  единиц продукции вида  дает 50 рублей прибыли и  единицу продукции  дает 40 рублей прибыли, суммарная прибыль составляет z=50+40 рублей.

Условиями не оговорена неделимость продукции, поэтому  и (план выпуска продукции) могут быть и дробными числами.

Решение:

Построим многоугольник решений. Для этого на координатной плоскости X1OX2 изобразим граничные прямые.

,

=0; =0.

Взяв какую-нибудь точку, например, начало координат, установим, какую полуплоскость определяет неравенство. Многоугольником решений данной задачи является ограниченный пятиугольник ОАВСD (рисунок 3).

Рисунок 3

Для построения прямой 50+40=0 строим радиус вектор =(50;40)=10(5;4) и через точку О проводим прямую, перпендикулярную ему. Построенную прямую z=0 перемещаем параллельно самой себе в направлении вектора . Из рисунка видно, что опорной по отношению к многоугольнику решений эта прямая становится в точке С где функция z принимает максимальное значение. Точка С лежит на пересечении прямых   и . Для определения ее координат решим систему уравнений:

.

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

Таким образом, для того чтобы получать максимальную прибыль в размере 260,3 руб, необходимо запланировать производство 3,9 ед. продукции  и 1,7 ед. продукции .

Задача о рационе

При откорме любое животное должно получать не менее 9 единиц питательного вещества , не менее 8 единиц вещества  и не менее 12 единиц вещества  Для составления рациона используют два вида корма. Содержание количества единиц питательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведены в таблице 2.

Таблица 2

Необходимо составить дневной рацион нужной питательности, причем затраты на него должны быть минимальными.

Обозначим через  и соответственно количество килограммов корма 1 и 2 в дневном рационе. Тогда получаем систему ограничений вида

.

Если корм 1 в рационе не используется, то =0, в противном случае >0. Аналогично и . Таким образом, .

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

Z=.

Решение:

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

.

В результате получаем неограниченную многоугольную область с угловыми точками А,В,С и D (рисунок 4).

Рисунок 4

Построим вектор  и прямую . Перемещаем прямую z в параллельно самой себе в направлении вектора . Из рисунка видно, что она впервые коснется многоугольника решений и станет опорной по отношению к нему в угловой точке В. Если прямую перемещать далее в направлении , то значения линейной функции на многоугольнике решений возрастут. Это значит, что в точке В линейная функция принимает минимальное значение. Точка В лежит на пересечении прямых  и ; для определения ее координат решаем систему уравнений вида

.

Решением системы уравнений являются числа , . Тогда

Для того, чтобы обеспечить минимум затрат (26 рублей в день), необходимо дневной рацион I составить из расчёта 2 кг корма, а дневной рацион II – из расчёта 3 кг корма.

Если задача задана не в стандартной форме, надо предварительно привести ее к этой форме.

Пример. Решить задачу линейного программирования графически заданную в канонической форме:

при ограничениях:

,

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

.

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

Рисунок 5

Оптимальное решение совпадает с точкой , лежащей на пересечении прямых  и .

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

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

,

Получаем решения  и .

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

Выпуклые множества.

На плоскости многоугольник называют выпуклым, если он целиком лежит по одну сторону от прямых, на которых лежат его стороны. Например на рисунке а) выпуклый многоугольник, а на б) не является выпуклым.

В первом случае любые две точки M и N можно соединить отрезком, и этот отрезок целиком целиком лежит внутри многоугольника, а во втором случае нет.

Определение. Множество точек называется выпуклым, если оно вместе с любыми двумя точками содержит весь отрезок , соединяющий точки.

Примеры выпуклых множеств: круг , сектор, отрезок, многоугольная область, куб, пирамида, многогранная область, прямая, полуплоскость, полупрямая и т.д.

Пересечение (общая часть) любого числа выпуклых множеств есть выпуклое множество.

Точка множества называется внутренней, если в некоторой ее окрестности содержатся точки только данного множества.

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

К граничным точкам относятся угловые точки.

Точка множества называется угловой (или крайней), если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.

Множество называется замкнутым, если оно включает все свои граничные точки.

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

Выпуклое замкнутое множество точек пространства (плоскости), имеющее конечное число угловых точек, называется выпуклым многогранником (многоугольником), если оно ограничено, и выпуклой многогранной (многоугольной) областью, если оно неограниченно.

Таким образом, рассматривая выпуклые множества на плоскости, имеем аналогичное соответствие =(х1;х2) и в пространстве =(х1;х2;х3).

Эти понятия можно обобщить в случае n-мерного пространства =(х1;х2;…;хn).

Точка  называется выпуклой линией кривой линией кривой точек ,,…,

Т.1 Выпуклый и n-мерный многогранник является выпуклым своих угловых точек

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

Треугольник- тремя

Тетраэдр- четырьмя

Множество решений систем неравенств.

Теорема 2. Множество решений совместной системы т линейного неравенства с n переменными

Является выпуклым многоугольником или выпуклой многоугольной областью.

Пример. Построить множество решений системы

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