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

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

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

ЦФ  при фиксированном значении определяет на плоскости прямую линию . Изменяя значения 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. По полученным результатам сделать  выводы.

 

 

 

 

Список используемой литературы

 

Самойленко В. И., Пузырев  В. А., Грубрин И. В. «Техническая кибернетика», учеб. пособие, М., изд-во МАИ, 1994, 280 с. ил.

Коршунов Ю. М. «Математические  основы кибернетики», учеб. пособие  для вузов, 2-е изд., перераб. и доп., М., «Энергия», 1980, 424 с., ил.

А.Г. Александров, Оптимальные  и адаптивные системы, М., Вышая школа, 1989, 263 с.

Э. М. Галеев, В. М. Тихомиров  «Оптимизация: теория, примеры, задачи», М., «Эдиториал УРСС», 2000, 320 с.

«Численные методы в теории оптимальных систем», Моисеев Н. Н., «Наука», 1971, 424 стр.

Кулич И.Л. Математическое программирование в примерах и задачах. /И.Л. Акулич. - Минск: Высшая школа, 2004 год.

Гельман В.Я. Решение математических задач  средствами Excel: Практикум.  / В.Я. Гельман. - СПб.: Питер, 2003. - 237 с.

Карасев А.Н., Кремер Н.Ш., Савельева Т. Н “Математические  методы в экономике”, М. 2000

Кузнецов, А.Г., Новикова, Г.И., Холод И.И. Высшая математика. Математическое программирование./А.Г. Кузнецов, Г.И. Новикова, И.И. Холод. - Минск: Высшая школа, 2001 год

Павлова Т.Н., Ракова О.А. Решение задач линейного  программирования средствами EXCEL. Учебное пособие. Димитровград, 2002 г.