Теория оптимального управления

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

можно представить в виде системы двух неравенств

ЦФ  при фиксированном значении определяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.

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

Вектор  с координатами из коэффициентов ЦФ при и перпендикулярен к каждой из линий уровня. Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора .

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

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

Рисунок 1 - Геометрическая интерпретация ограничений и ЦФ задачи.

1. В ограничениях задачи заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.
2. Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задач. Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства.

Если  неравенство истинное,

то    надо заштриховать полуплоскость, содержащую данную точку;

иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

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

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

3. Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений.
4. Если ОДР – не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня    (где L – произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.
5. Построить вектор , который начинается в точке (0;0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны.
6. При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ – против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).
7. Определить координаты точки 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.5217391304348

Подставим полученное значение 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 г.