Решение задачи линейного программирования

Для решения задач с ограничениями в виде неравенств используется вычислительный аппарат линейного программирования. При решении задач оптимального управления появляются задачи линейного программирования, требующие использования нестандартных, специализированных методов решения.

Задачи линейного программирования, возникающие при решении задач оптимального управления методом последовательной линеаризации, являются конечно-разностными аппроксимациями континуальных задач вида: найти функцию из условий

,

, ,

.

Задача линейного программирования появляется как характерная промежуточная задача в алгоритмах поиска минимума после проведения конечномерной аппроксимации. Она формулируется следующим образом: найти числа из условий

, (1.26)

, (1.27)

.

Здесь , , , - заданные числа.

Разработано большое количество алгоритмов точного решения задачи (1.26) - (1.27), которые объединяются общим термином симплекс-метод. Как прямые, так и двойственные варианты симплекс-метода позволяют решать задачи линейного программирования с ограничениями типа неравенств.

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

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

После проведения конечномерной аппроксимации путем введения на отрезке времени сетки с большим числом интервалов (например, в рассматриваемых в монографии задачах N=50 - 100 и более) при наличии в условиях задачи многочисленных ограничений (в рассматриваемых задачах =1 - 10) приходится иметь дело с задачей вида (1.26) - (1.27), решение которой симплекс-методом весьма затруднительно. Кроме того, полученную промежуточную задачу линейного программирования нет необходимости решать точно, достаточно получить приближенное решение итерационным методом, задав приемлемую точность решения.

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

.

Требуется найти точку с наименьшим и ее прообраз в , где - вектор, орт -мерного пространства, соответствующий оси .

Алгоритм приближенного решения задачи линейного программирования по основной идее близок к двойственному варианту симплекс-метода. Ведущим подходом является эквивалентность сформулированной задачи задаче на минимакс: найти

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

Итерационный метод дает приближенное решение в том смысле, что вместо соотношения

получается

,

где - малый параметр. Кроме того, величина не будет точным минимумом, поэтому для нее требуется выполнение оценки

,

где - заданное число. Число и параметр определяют требуемую точность решения.

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

Однако, это приводит к тому, что за заранее определенное количество итераций приближенного метода решения задачи (1.26) - (1.27) может не выполниться условие для оценки , в связи с чем снижается точность решения задачи линейного программирования. Как следствие этого уменьшается эффективность алгоритма формирования командного управления в целом.

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

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

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

Использование метода штрафных функций.Рассмотрим метод штрафных функций, сводящийся в используемых обозначениях к минимизации по квадратичной формы следующего вида:

.

Метод штрафных функций обеспечивает решение задачи условной минимизации как последовательности решений задач безусловной минимизации.

Алгоритм решения задачи линейного программирования (1.26) - (1.27) на основе метода штрафных функций сводится к выполнению следующих операций.

1. Осуществляется нормировка задачи.

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

2. Задается начальное приближение вариаций управления - компоненты вектора : .

3. Задаются целые числа - пределы изменения значений штрафного коэффициента и счетчика в методе условного градиента .

4. Задаются значения точности , с которыми должны выполняться -е ограничения.

5. Для всех значений выполняется цикл действий, соответствующий -кратному выполнению пунктов 6 - 12.

6. Вычисляются невязки:

.

7. Определяется функция:

, если ,

, если .

8. Вычисляется и запоминается значение обобщенной функции:

.

9. Вычисляются компоненты градиента обобщенной функции:

.

10. Определяется вспомогательное приближение:

при ,

при ,

при .

11. Находится параметр , определяющий длину шага изменения вариации управления из условия:

.

Минимизация обобщенной функции осуществляется методом золотого сечения.

12. Определяется новое приближение градиентного спуска:

, .

13. Среди чисел выбирается наименьшее. Соответствующие ему значения принимаются за решение задачи линейного программирования (1.26) - (1.27).

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

Практическое занятие № 2

РЕШЕНИЕ ЗАДАЧ С ПОМОЩЬЮ