Формула приращений целевой функции

Предмет курса. Основные понятия. Общая схема решения задач. Производственная задача.

Функция , заданная на множестве - целевая функция, задача оптимизации в общей форме имеет вид: .

План  называется оптимальным, если выполняется условие:

, где - оптимальный план, число  – оптимальное значение целевой функции.

Предмет курса: изучение и разработка методов и алгоритмов разнообразных экстремальных задач.

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

 План  называется - оптимальным, если для некоторого положительного  (обычно малого) выполняется неравенство:

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

Общая схема. Пусть существует некоторый объект поведения, который необходимо оптимизировать.

Этапы достижения цели исследования следующие:

1. Изучение и описательная постановка.

Он включает:

 а) изучение структуры объекта, его составных частей;

 б) установление связей и закономерностей его функционирования;

 в) выяснение смысла качества, улучшение поведения объекта ;

 г) сбор числовых данных, описывающих состояние связи и закономерности, качество поведения объекта;

2. Математическая формализация задачи.

 Оно включает:

а) введение неизвестных управляемых параметров для изменения поведения объекта - , которые однозначно описывают состояние объекта, и изменяя который можно добиваться целей;

б) запись в виде математических соотношений основных связей и закономерности. Обычно они имеют вид неравенств и равенств, связывающих переменные ,  и используют собранную в 1. информацию. Система этих соотношений и определяет (задаёт) множество;

 в) запись целевой функции и операции оптимизации.

В результате второго этапа мы получаем задачу оптимизации (1).

3. Исследование задачи и построение метода.

Оно включает:

а) выяснение, к какому типу задач оптимизации относится наша, имеет ли разработанная теория и методы решения;

б) если теория разработана и имеются методы, то изучаем теории и выбор наиболее подходящего метода;

в) если теории и методов (подходящих) нет, то исследование задачи (дополнительное) и на этой основе разработка методов.

4. Численное решение.

Оно включает:

а) составление на основе метода алгоритма;

б) написание и отладка по алгоритму программы на ЭВМ;

в) получение оптимального плана и оптимального значения целевой функции.

5. Анализ решения и уточнение модели и процесса оптимизации, (сравниваем полученное решение с реальным поведением объекта; если есть возможность, то проводим эксперименты; если  удовлетворяет, то процесс оптимизации заканчивается, если нет, то уточняем этот процесс на этапах 1-4. при оптимизации возможны ошибки сбора информации, моделирования, исследования, вычисления).

 

Графический метод.

Метод применим к задачам линейного программирования с двумя переменными:

                                                                (1)

                                                                                        (2)

Алгоритм:

1. В декартовой системе координат на плоскости строим множество  планов задачи, как пересечение -полуплоскостей, задаваемых линейными ограничениями системы (2).

 При этом возможен один из случаев:

а) – пустое множество;

б) – выпуклый многоугольник;

в) – выпуклая неограниченная многоугольная область.

Если а), то задача не имеет решения; б) или в) – переходим к пункту 2.

2. По целевой функции  строим вектор (градиент целевой функции), через начало координат проводим прямую  (линию нулевого уровня целевой функции): .

3. При решении задачи максимизации (минимизации) прямую  перемещаем параллельно в направлении вектора  (вектора - ) в наиболее отдалённую точку А (точку В) множества плана . Координаты точки А (точки В) и составляют оптимальный план задачи максимизации (минимизации) функции на множестве .

Если множество – ограничено, то задача всегда имеет решение. Если же – неограниченная многоугольная область, то задача может не иметь решения в случае, когда не существует наиболее удалённой точки, то есть целевая функция неограниченно возрастает (убывает) на .

Если задача имеет оптимальный план, то он достигается либо в одной из вершин границы множества , либо на одной из её сторон (альтернативный оптимум).

 

3. Каноническая задача. Базисный план. Формула приращений

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

                             (1)

    Её особенность: целевая функция максимизируется; все основные ограничения имеют вид равенств; на все переменные наложены прямые ограничения неотрицательности.

    Введём обозначения:

индексное множество номеров переменных.

индексное множество номеров основных ограничений.

ый столбец матрицы А.

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

а) небазисные компоненты плана нулевые ;

б) базисным компонентам соответствуют линейно-независимые столбцы матрицы А, то есть .

Построим матрицу . Согласно определению, она не вырождена . Эта матрица называется базисной, а матрица   называется небазисной.

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

Критерий оптимальности.

Теорема 1. Условие   (4)  достаточно, а в случае невырожденности базисного плана и необходимо для его оптимальности.

Доказательство. Достаточность. Пусть выполняется условие (4). Так как , то из формулы приращения  или , это означает, что  – оптимальный план задачи.

Необходимость. Пусть известно, что  – оптимальный базисный план, причем невырожденный для задачи (1), тогда

                                                                                                            (5)

Предположим противное, что условие (4) не выполняется. Следовательно, существует

                                                      (6)

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

Положим, что                                 (7)

Выберем , чтобы выполнялось соотношение (2), то есть

                                                                          (8)

Вектор  в силу (2) при любом  удовлетворяет основным ограничениям (1): . Очевидно, компоненты  удовлетворяют  прямым ограничениям задачи (1). Имеем

                              

                                                                                              (9)      

Поскольку выполняется условие (5), можно подобрать  положительным, что будут выполняться прямые ограничения , тогда для найденного  получаем,  является планом задачи. Но подстановка его в (3) приводит к неравенству: . Следовательно, . Это противоречит оптимальности базисного плана , что и доказывает необходимость.

                                                                                                           Ч.т.д.

 

Двухфазный симплекс-метод.

 

Предмет курса. Основные понятия. Общая схема решения задач. Производственная задача.

Функция , заданная на множестве - целевая функция, задача оптимизации в общей форме имеет вид: .

План  называется оптимальным, если выполняется условие:

, где - оптимальный план, число  – оптимальное значение целевой функции.

Предмет курса: изучение и разработка методов и алгоритмов разнообразных экстремальных задач.

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

 План  называется - оптимальным, если для некоторого положительного  (обычно малого) выполняется неравенство:

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

Общая схема. Пусть существует некоторый объект поведения, который необходимо оптимизировать.

Этапы достижения цели исследования следующие:

1. Изучение и описательная постановка.

Он включает:

 а) изучение структуры объекта, его составных частей;

 б) установление связей и закономерностей его функционирования;

 в) выяснение смысла качества, улучшение поведения объекта ;

 г) сбор числовых данных, описывающих состояние связи и закономерности, качество поведения объекта;

2. Математическая формализация задачи.

 Оно включает:

а) введение неизвестных управляемых параметров для изменения поведения объекта - , которые однозначно описывают состояние объекта, и изменяя который можно добиваться целей;

б) запись в виде математических соотношений основных связей и закономерности. Обычно они имеют вид неравенств и равенств, связывающих переменные ,  и используют собранную в 1. информацию. Система этих соотношений и определяет (задаёт) множество;

 в) запись целевой функции и операции оптимизации.

В результате второго этапа мы получаем задачу оптимизации (1).

3. Исследование задачи и построение метода.

Оно включает:

а) выяснение, к какому типу задач оптимизации относится наша, имеет ли разработанная теория и методы решения;

б) если теория разработана и имеются методы, то изучаем теории и выбор наиболее подходящего метода;

в) если теории и методов (подходящих) нет, то исследование задачи (дополнительное) и на этой основе разработка методов.

4. Численное решение.

Оно включает:

а) составление на основе метода алгоритма;

б) написание и отладка по алгоритму программы на ЭВМ;

в) получение оптимального плана и оптимального значения целевой функции.

5. Анализ решения и уточнение модели и процесса оптимизации, (сравниваем полученное решение с реальным поведением объекта; если есть возможность, то проводим эксперименты; если  удовлетворяет, то процесс оптимизации заканчивается, если нет, то уточняем этот процесс на этапах 1-4. при оптимизации возможны ошибки сбора информации, моделирования, исследования, вычисления).

 

Графический метод.

Метод применим к задачам линейного программирования с двумя переменными:

                                                                (1)

                                                                                        (2)

Алгоритм:

1. В декартовой системе координат на плоскости строим множество  планов задачи, как пересечение -полуплоскостей, задаваемых линейными ограничениями системы (2).

 При этом возможен один из случаев:

а) – пустое множество;

б) – выпуклый многоугольник;

в) – выпуклая неограниченная многоугольная область.

Если а), то задача не имеет решения; б) или в) – переходим к пункту 2.

2. По целевой функции  строим вектор (градиент целевой функции), через начало координат проводим прямую  (линию нулевого уровня целевой функции): .

3. При решении задачи максимизации (минимизации) прямую  перемещаем параллельно в направлении вектора  (вектора - ) в наиболее отдалённую точку А (точку В) множества плана . Координаты точки А (точки В) и составляют оптимальный план задачи максимизации (минимизации) функции на множестве .

Если множество – ограничено, то задача всегда имеет решение. Если же – неограниченная многоугольная область, то задача может не иметь решения в случае, когда не существует наиболее удалённой точки, то есть целевая функция неограниченно возрастает (убывает) на .

Если задача имеет оптимальный план, то он достигается либо в одной из вершин границы множества , либо на одной из её сторон (альтернативный оптимум).

 

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) приводит к неравенству: . Следовательно, . Это противоречит оптимальности базисного плана , что и доказывает необходимость.

                                                                                                           Ч.т.д.

 

12Следующая ⇒

Поделиться: