Теория оптимального управления. 2
Содержание
1. Теоретическая часть 2
Общие принципы теории оптимального управления 2
Возможность применения линейного программирования в теории оптимального управления 4
Симплекс-метод линейного программирования 8
Описание графического метода линейного программирования 12
2. Расчетная часть 16
Список используемой литературы 22
Теоретическая часть
Общие принципы теории оптимального управления
Оптимальное управление —
это задача проектирования системы,
обеспечивающей для заданного объекта
управления или процесса закон управления
или управляющую
Для решения задачи оптимального управления строится математическая модель управляемого объекта или процесса, описывающая его поведение с течением времени под влиянием управляющих воздействий и собственного текущего состояния. Математическая модель для задачи оптимального управления включает в себя: формулировку цели управления, выраженную через критерий качества управления; определение дифференциальных или разностных уравнений, описывающих возможные способы движения объекта управления; определение ограничений на используемые ресурсы в виде уравнений или неравенств.
Если управляемый объект или процесс является детерминированным, то для его описания используются дифференциальные уравнения. Наиболее часто используются обыкновенные дифференциальные уравнения вида. В более сложных математических моделях (для систем с распределёнными параметрами) для описания объекта используются дифференциальные уравнения в частных производных. Если управляемый объект является стохастическим, то для его описания используются стохастические дифференциальные уравнения.
Реальное поведение объекта
или системы всегда отличается от
программного вследствие неточности в
начальных условиях, неполной информации
о внешних возмущениях, действующих
на объект, неточности реализации программного
управления и т.д. Поэтому для
минимизации отклонения поведения
объекта от оптимального обычно используется
система автоматического
Иногда в исходных данных и знаниях об управляемом объекте при постановке задачи оптимального управления содержится неопределённая или нечёткая информация, которая не может быть обработана традиционными количественными методами. В таких случаях можно использовать алгоритмы оптимального управления на основе математической теории нечётких множеств (Нечёткое управление). Используемые понятия и знания преобразуются в нечёткую форму, определяются нечёткие правила вывода принимаемых решений, затем производится обратное преобразование нечётких принятых решений в физические управляющие переменные.
Сформулируем задачу оптимального управления:
- Уравнения состояния: (1).
- Граничные условия , (2).
- Минимизируемый функционал:
.
здесь — вектор состояния — управление, — начальный и конечный моменты времени.
Задача оптимального управления заключается в нахождении функций состояния и управления для времени , которые минимизируют функционал.
Возможность применения линейного программирования в теории оптимального управления
В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решений
Линейное программирование
представляет собой наиболее часто
используемый метод оптимизации. К
числу задач линейного
- рационального использования сырья и материалов; задачи оптимального раскроя;
- оптимизации производственной программы предприятий;
- оптимального размещения и концентрации производства;
- составления оптимального плана перевозок, работы транспорта;
- управления производственными запасами;
- и многие другие, принадлежащие сфере оптимального планирования.
Для большого количества практически интересных задач целевая функция выражается линейно - через характеристики плана, причем допустимые значения параметров подчинены линейным равенствам или неравенствам. Нахождение при данных условиях абсолютного экстремума целевой функции носит название линейного программирования
Прямая задача линейного программирования является математической формулировкой проблемы составления такого плана использования различных способов производства, который позволяет получить максимальное количество однородного продукта при имеющихся в наличии ресурсах
Линейное программирование
- это наука о методах
Целевая функция задачи линейного
программирования достигает своего
экстремума (минимума или максимума)
в вершине допустимой области. Если
целевая функция достигает
Доказательство. Обозначим
вершины выпуклого
Тогда её можно представить как выпуклую комбинацию вершин
Поскольку - линейный функционал, то
Обозначим через m минимум из всех значений , и пусть он достигается в вершине , т.е.
Но тогда, так как ,
то
С другой стороны, по определению оптимального плана, должно быть . Сравнивая, получим, что , то есть существует такая вершина , где целевая функция достигает того же минимального значения.
Для доказательства второй части теоремы допустим, что принимает свое минимальное значение на нескольких вершинах сразу, например, на . Тогда Если - выпуклая комбинация этих вершин
то принадлежит допустимой области и
,
что и доказывает теорему.
Эта теорема имеет важнейшее значение, так как она указывает путь решения задачи линейного программирования. Совсем не надо перебирать все точки допустимой области. Достаточно перебрать вершины допустимой области, а ведь их - конечное число. Кроме того, как это окажется далее, не нужно перебирать все вершины, можно этот перебор существенно сократить. Только вот как узнать, имеем ли мы дело с вершиной или нет?
Все дальнейшее изложение
будет вестись для задач
Примеры моделей, приводящих
к задачам линейного
Линейное программирование является одной из основных частей того раздела современной математики, который получил название математического программирования. В общей постановке задачи этого раздела выглядят следующим образом.
Имеются какие-то переменные и функция этих переменных , которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции при условии, что переменные x принадлежат некоторой области G:
В зависимости от вида функции и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Подробнее об этом будет сказано в заключении.
Линейное программирование характеризуется тем, что
а) функция является линейной функцией переменных ;
б) область G определяется системой линейных равенств или неравенств
Симплекс-метод линейного программирования
Симплекс метод - является универсальным методам, которым можно решить любую задачу линейного программирования.
Сформулировать алгоритм симплекс-метода для решения задач линейного программирования, заданных в канонической форме. Обычно он реализуется в виде симплекс-таблицы.
В первом столбце этой таблицы
располагаются обозначения
Второй столбец - коэффициенты целевой функции, соответствующие векторам, входящим в базис.
Третий столбец - компоненты опорного плана. В дополнительной строке в этом столбце пишется величина . Её легко вычислить перемножая числа из второго столбца и третьего столбца и складывая их.
Далее идут столбцы, соответствующие всем векторам , и в этих столбцах записываются координаты этих векторов в рассматриваемом базисе. Заметим, что для векторов, входящих в базис, эти координаты имеют вид (0,0,.,0,1,0,., 0), где единица стоит в той строке, где находится сам этот базисный вектор. В дополнительной строке сверху обычно выписывают коэффициенты , соответствующие этим векторам. В дополнительной строке снизу пишутся величины , вычисляемые по формулам:
.
Заметим, что для векторов, входящих в базис, эти разности всегда равны нулю.
Далее идут следующие этапы,
связанные с преобразованием
этой таблицы. При ручном счете каждый
раз эту таблицу лучше
Этап 1
Просматривается дополнительная строка снизу, где записаны разности.
Если все эти разности , то план является оптимальным
Этап 2
Если есть столбцы, где , то выбирается столбец с максимальным значением этой разности. Индекс j определит вектор, вводимый в базис.
Пусть , то есть в базис надо вводить вектор . Назовем столбец, соответствующий этому вектору, направляющим столбцом. В дальнейшем мы будем направляющий столбец помечать символом .
Этап 3
Просматривается столбец, соответствующий этому вектору. Если все , то значения целевой функции не ограничены снизу. Если есть , то находятся
где просматриваются лишь те дроби , для которых
Пусть этот минимум достигается для вектора . Тогда именно вектор подлежит выводу из базиса. Строка, соответствующая этому вектору, называется направляющей строкой. В дальнейшем в примерах мы будем помечать ее символом .
Этап 4
После того, как определены
направляющие столбец и строка, начинает
заполняться новая симплекс-
Обычно заполнение этой новой таблицы начинается именно с направляющей строки. В качестве компоненты опорного плана туда пишется величина , то есть
.
Остальные элементы этой строки заполняются величинами
.
Обратите внимание на особую роль элемента , стоящего на пересечении направляющей строки и направляющего столбца. Именно на него делятся все бывшие элементы направляющей строки. На месте бывшего элемента автоматически появляется единица.
Написанные выше формулы
для пересчета элементов
.
Этап 5
Далее начинается пересчет всех остальных строк таблицы, включая и дополнительную нижнюю строку по формулам: для компонент плана
;
для координат разложения по базису
;
для дополнительной строки
.
Обратите внимание на то, что все эти формулы по сути дела строятся по одному правилу
.
Это правило применимо и к компонентам плана, и к величинам , и к разностям . Его даже можно использовать для пересчета элементов самого направляющего столбца, хотя проще заполнить его нулями, оставив 1 на месте бывшего элемента .
Далее итерации продолжаются.
Описание графического метода линейного программирования
Графический метод довольно
прост и нагляден для решения
задач линейного
Каждое из неравенств задачи линейного программирования определяет на координатной плоскости некоторую полуплоскость, а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи ОДР является пустым множеством.
Все вышесказанное относится и к случаю, когда система ограничений включает равенства, поскольку любое равенство
можно представить в виде системы двух неравенств
ЦФ при фиксированном значении определяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.
Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси (начальная ордината), а угловой коэффициент прямой останется постоянным (см.рис.2.1). Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.
Вектор с координатами из коэффициентов ЦФ при и перпендикулярен к каждой из линий уровня. Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора .
Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки . Оптимальной считается точка, через которую проходит линия уровня , соответствующая наибольшему (наименьшему) значению функции . Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.
При поиске оптимального решения
задач линейного
Рисунок 1 - Геометрическая интерпретация ограничений и ЦФ задачи.
- В ограничениях задачи заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.
- Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задач. Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства.
Если неравенство истинное,
то надо заштриховать полуплоскость, содержащую данную точку;
иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.
Поскольку и должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси и правее оси , т.е. в I-м квадранте.
Ограничения-равенства
- Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений.
- Если ОДР – не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L – произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.
- Построить вектор , который начинается в точке (0;0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны.
- При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ – против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).
- Определить координаты точки max (min) ЦФ и вычислить значение ЦФ . Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .
2. Расчетная часть
А. Графически и аналитически решить задачу максимизации целевой функции Z согласно варианту. Исходные данные приведены в таблице.
Z=1,5х1+12х2
х1 ≥ 0, х2 ≥ 0
х1+8х2 ≤ 56
3х1+х2 ≤ 18,5
Б. Выполнить первый пункт задания, используя приложение MS Excel. По полученным результатам сделать выводы.
Вычислительные возможности Microsoft Excel позволяют создавать любые документы, содержащие текстовые и числовые данные, рисунки, диаграммы.
При запуске программы Microsoft Excel появляется рабочая книга. Книга в Microsoft Excel представляет собой файл, используемый для обработки и хранения данных. Каждая книга может состоять из нескольких листов, поэтому в одном файле можно поместить разнообразные сведения и установить между ними необходимые связи.
В Microsoft Excel существует понятие текущей ячейки.
Текущая ячейка — это ячейка, которая в данный момент способна воспринимать ввод с клавиатуры. Текущая ячейка отображается двумя способами:
• в самой таблице она подсвечена жирной линией, которая называется табличным курсором;
• номер ячейки отображается в строке формул, которая расположена над панелью, содержащей названия столбцов.
Взаимодействие пользователя с программой Microsoft Excel происходит с помощью следующих компонентов:
• меню приложений;
• панели инструментов;
• стоки формул;
• строки состояния.
Строка формул — строка над рабочей областью, разбита на три части. Первая часть содержит адрес текущей ячейки. При вводе данных в текущую ячейку эти данные автоматически отображаются в третьей части стоки формул. В средней части находятся кнопки, появляющиеся при вводе и редактировании данных. + Строка состояния — область в нижней части окна, отображающая сведения о выбранной команде или выполняемой операции.
Типы данных, используемые в Microsoft Excel.
В Microsoft Excel поддерживается три типа данных:
• текстовые данные;
• числовые константы;
• формулы.
Текст — любая последовательность, состоящая из цифр, пробелов и нецифровых символов. Введенный текст выравнивается в ячейке по левому краю.
Формулы представляют собой последовательность значений, ссылок на ячейки, имен, функций или операторов и вычисляют новое значение на основе существующих. Формула всегда начинается со знака равенства (=).
Построение и оформление диаграмм.
Конструктор диаграмм является одним из наиболее мощных средств в программе Excel. Построение диаграммы с его помощью выполняется за несколько шагов. Конструктору указывается исходная область таблицы, тип диаграммы, Используемые надписи и цвета. На основной панели имеется пиктограмма для вызова конструктора диаграмм. Прежде чем строить диаграмму, необходимо закончить все работы в таблице, включая ее форматирование. Если вносятся изменения в ту часть таблицы, по которой строилась диаграмма, то программа Excel автоматически модифицирует диаграмму.
Поиск решения. Процедура поиска решения позволяет найти оптимальное значение формулы содержащейся в ячейке, которая называется целевой. Эта процедура работает с группой ячеек, прямо или косвенно связанных с формулой в целевой ячейке. Чтобы получить по формуле, содержащейся в целевой ячейке, заданный результат, процедура изменяет значения во влияющих ячейках. Чтобы сузить множество значений, используемых в модели, применяются ограничения. Эти ограничения могут ссылаться на другие влияющие ячейки. Пункт поиск решения находится в меню сервис.
Решение задачи максимизации целевой функции
1. Графический способ.
х1 =3,8 х2 =6,5
2.Аналитический способ.
Решаем данную систему уравнений
1· x1 + 8 ·x2 = 56
3· x1 + 1 · x2 = 18,5
В первом уравнении выразим x через y:
1· x1=56-8· x2
X1=(56-8· x2)/1
Подставим полученное выражение во второе уравнение
3 ·(56-8· x2)/1 + 1 · x2 = 18,5
(3·56/1) - (3·8· x2/1) +1· x2 = 18,5
(1 - 3·8/1)· x2= 18,5 - (3·56/1)
x2=(18,5 - (3·56/1))/(1 - 3·8/1)
x2=(18,5 - (168))/(1 - 3·8/1)
x2=(18,5 - 168)/(1 - 24)
x2=(-150)/(-23)=6.
Подставим полученное значение x2 в любое уравнение системы и найдем x1
Например, y подставляем в первое уравнение системы
1·x1 + 8·6.5217391304348 =56
1·x1 =56 - 8·6.5217391304348
X1 =(56 - 8·6.5217391304348)/1
X1 =(56 - 8·6.5217391304348)/1
X1 =(3.8260869565217)/1
X1 =3.8260869565217
Значение x1 =3.8260869565217
Значение x2 =6.5217391304348
Z=1,5х1+12х2=5,74+78,24=84
Решение в пакете Excel.
1. Ввод данных.
Введем начальные коэффициенты, равнные 0 и фрмулы. Для наглядности отобразим лист в режиме формул.
Со вкладки «Данные» выбираем инструмент «Поиск решения».
Указываем целевую ячейку, вводим ограничения согласно условия задачи. Нажимаем «Выполнить».
В результате получили решение.
Решение, полученное в пакете MS Excel примерно одинаково с графическим и аналитическим решением. Следовательно, решение выполнено верно.
Список используемой литературы
Самойленко В. И., Пузырев В. А., Грубрин И. В. «Техническая кибернетика», учеб. пособие, М., изд-во МАИ, 1994, 280 с. ил.
Коршунов Ю. М. «Математические основы кибернетики», учеб. пособие для вузов, 2-е изд., перераб. и доп., М., «Энергия», 1980, 424 с., ил.
А.Г. Александров, Оптимальные и адаптивные системы, М., Вышая школа, 1989, 263 с.
Э. М. Галеев, В. М. Тихомиров «Оптимизация: теория, примеры, задачи», М., «Эдиториал УРСС», 2000, 320 с.
«Численные методы в теории оптимальных систем», Моисеев Н. Н., «Наука», 1971, 424 стр.
Кулич И.Л. Математическое программирование в примерах и задачах. /И.Л. Акулич. - Минск: Высшая школа, 2004 год.
Гельман В.Я. Решение математических задач средствами Excel: Практикум. / В.Я. Гельман. - СПб.: Питер, 2003. - 237 с.
Карасев А.Н., Кремер Н.Ш., Савельева Т. Н “Математические методы в экономике”, М. 2000
Кузнецов, А.Г., Новикова, Г.И., Холод И.И. Высшая математика. Математическое программирование./А.Г. Кузнецов, Г.И. Новикова, И.И. Холод. - Минск: Высшая школа, 2001 год
Павлова Т.Н., Ракова О.А. Решение задач линейного программирования средствами EXCEL. Учебное пособие. Димитровград, 2002 г.
