Формула приращений целевой функции
Предмет курса. Основные понятия. Общая схема решения задач. Производственная задача.
Функция 
, заданная на множестве 
- целевая функция, задача оптимизации в общей форме имеет вид: 
.
План 
называется оптимальным, если выполняется условие:
, где 
- оптимальный план, число 
– оптимальное значение целевой функции.
Предмет курса: изучение и разработка методов и алгоритмов разнообразных экстремальных задач.
При несуществовании у задачи оптимального плана под решением может пониматься нахождение числа (экстремального значения целевой функции) 
, и минимизирующей (максимизирующей) последовательности планов в 
, обладающей свойством 
. Если у задачи существует оптимальный план, то минимизирующая последовательность сходится к значениям 
и 
.
План 
называется 
- оптимальным, если для некоторого положительного 
(обычно малого) выполняется неравенство: 
План 
называется локально-оптимальным, если существует 
, что выполняется неравенство: 
,где 
- это 
-окрестность плана в 
, 
, то есть план 
наилучший по крайней мере в своей окрестности радиуса 
.
Общая схема. Пусть существует некоторый объект поведения, который необходимо оптимизировать.
Этапы достижения цели исследования следующие:
1. Изучение и описательная постановка.
Он включает:
а) изучение структуры объекта, его составных частей;
б) установление связей и закономерностей его функционирования;
в) выяснение смысла качества, улучшение поведения объекта ;
г) сбор числовых данных, описывающих состояние связи и закономерности, качество поведения объекта;
2. Математическая формализация задачи.
Оно включает:
а) введение неизвестных управляемых параметров для изменения поведения объекта - 
, которые однозначно описывают состояние объекта, и изменяя который можно добиваться целей;
б) запись в виде математических соотношений основных связей и закономерности. Обычно они имеют вид неравенств и равенств, связывающих переменные 
, 
и используют собранную в 1. информацию. Система этих соотношений и определяет (задаёт) множество;
в) запись целевой функции и операции оптимизации.
В результате второго этапа мы получаем задачу оптимизации (1).
3. Исследование задачи и построение метода.
Оно включает:
а) выяснение, к какому типу задач оптимизации относится наша, имеет ли разработанная теория и методы решения;
б) если теория разработана и имеются методы, то изучаем теории и выбор наиболее подходящего метода;
в) если теории и методов (подходящих) нет, то исследование задачи (дополнительное) и на этой основе разработка методов.
4. Численное решение.
Оно включает:
а) составление на основе метода алгоритма;
б) написание и отладка по алгоритму программы на ЭВМ;
в) получение оптимального плана и оптимального значения целевой функции.
5. Анализ решения и уточнение модели и процесса оптимизации, (сравниваем полученное решение с реальным поведением объекта; если есть возможность, то проводим эксперименты; если 
удовлетворяет, то процесс оптимизации заканчивается, если нет, то уточняем этот процесс на этапах 1-4. при оптимизации возможны ошибки сбора информации, моделирования, исследования, вычисления).
Графический метод.
Метод применим к задачам линейного программирования с двумя переменными:
(1)
(2)
Алгоритм:
1. В декартовой системе координат на плоскости строим множество 
планов задачи, как пересечение 
-полуплоскостей, задаваемых линейными ограничениями системы (2).
При этом возможен один из случаев:
а) 
– пустое множество;
б) 
– выпуклый многоугольник;
в) – выпуклая неограниченная многоугольная область.
Если а), то задача не имеет решения; б) или в) – переходим к пункту 2.
2. По целевой функции 
строим вектор 
(градиент целевой функции), через начало координат проводим прямую 
(линию нулевого уровня целевой функции): 
.
3. При решении задачи максимизации (минимизации) прямую 
перемещаем параллельно в направлении вектора 
(вектора - 
) в наиболее отдалённую точку А (точку В) множества плана 
. Координаты точки А (точки В) и составляют оптимальный план задачи максимизации (минимизации) функции 
на множестве 
.
Если множество – ограничено, то задача всегда имеет решение. Если же – неограниченная многоугольная область, то задача может не иметь решения в случае, когда не существует наиболее удалённой точки, то есть целевая функция неограниченно возрастает (убывает) на .
Если задача имеет оптимальный план, то он достигается либо в одной из вершин границы множества , либо на одной из её сторон (альтернативный оптимум).
Каноническая задача. Базисный план. Формула приращений
Метод разработан для канонической задачи линейного программирования
(1)
Её особенность: целевая функция максимизируется; все основные ограничения имеют вид равенств; на все переменные наложены прямые ограничения неотрицательности.
Введём обозначения:
индексное множество номеров переменных.
индексное множество номеров основных ограничений.
ый столбец матрицы А.
Определение. Пусть дан некоторый план 
. Его будем называть базисным планом, если компоненты можно разбить на две группы: базисные 
или 
и небазисные 
и выполняются два условия:
а) небазисные компоненты плана нулевые 
;
б) базисным компонентам соответствуют линейно-независимые столбцы матрицы А, то есть 
.
Построим матрицу 
. Согласно определению, она не вырождена 
. Эта матрица называется базисной, а матрица 
называется небазисной.
Определение.Базисный план 
называться невырожденным, если все базисные компоненты положительны 
.
Формула приращений целевой функции
Будем рассматривать задачу вида:
(1)
Предположим, что известен базисный план 
, характеризующийся индексным множеством 
. Рассмотрим произвольный другой план 
и подсчитаем, как изменится целевая функция при переходе 
.
Обозначим через 
– вектор приращения базисного плана, тогда по базисному множеству введем разбиение:
поскольку 
– планы задачи (1), то выполняется соотношения:
Вычитая основные ограничения, получим: 
или 
.
Таким образом,
(2)
Формула (2) выражает базисные компоненты вектора приращений через небазисные. И если вектор 
удовлетворяет (2), то вектор 
будет планом задачи тогда и только тогда, когда – будет план, причём 
. Для приращения целевой функции получим:
(3)
где 
вектор оценок, 
– вектор потенциалов.
(3) – искомая формула приращения целевой функции при переходе от базисного плана 
к произвольному плану 
. Её можно переписать
(3)
Критерий оптимальности.
Теорема 1.Условие 
(4) достаточно, а в случае невырожденности базисного плана и необходимо для его оптимальности.
Доказательство. Достаточность.Пусть выполняется условие (4). Так как 
, то из формулы приращения 
или 
, это означает, что – оптимальный план задачи.
Необходимость.Пусть известно, что – оптимальный базисный план, причем невырожденный для задачи (1), тогда
(5)
Предположим противное, что условие (4) не выполняется. Следовательно, существует
(6)
По базисному плану будем строить вектор 
, где вектор приращения 
выберем следующим образом.
Положим, что 
(7)
Выберем 
, чтобы выполнялось соотношение (2), то есть
(8)
Вектор в силу (2) при любом 
удовлетворяет основным ограничениям (1): 
. Очевидно, компоненты удовлетворяют прямым ограничениям задачи (1). Имеем
(9)
Поскольку выполняется условие (5), можно подобрать 
положительным, что будут выполняться прямые ограничения 
, тогда для найденного 
получаем, 
является планом задачи. Но подстановка его в (3) приводит к неравенству: 
. Следовательно, 
. Это противоречит оптимальности базисного плана , что и доказывает необходимость.
Ч.т.д.
Дата добавления: 2018-10-27; просмотров: 511; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!