Лекция: Проблема двойственности в линейном программировании.

Вопросы на ГЭК 2012

1. Нелинейные САР. Понятия: «пространство состояний», «фазовая траектория», «фазовый портрет».

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

Дифференциальное уравнение 3-го порядка (мы взяли 3-ий порядок для возможности геометрической иллюстрации процессов, в общем же случае речь может идти о «n»-м порядке) замкнутой САР, представленное в форме Коши, имеет вид

при

Здесь — отклонения переменных системы от их установившихся значений; — любые функции (в том числе нелинейные) от этих переменных.

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

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

Выше говорилось, что уравнения нелинейной системы (1) составлены в отклонениях от установившегося состояния, которое характеризуется. Следовательно, изображением установившегося состояния системы является начало координат. Отсюда вытекает, если использовать определение устойчивости по Ляпунову, что если фазовые траектории с течением времени стягиваются к некоторой малой окрестности вокруг начала координат, то система устойчива. Если же фазовые траектории приходят строго в начало координат, то имеет место асимптотическая устойчивость. И, наконец, если при фазовые траектории неограниченно удаляются от начала координат, то САР неустойчива.

Проблема двойственности в линейном программировании.

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

1. Пусть ограничения исходной задачи имеют вид(1):

На множестве решений этой системы требуется максимизиро­вать функцию

Двойственной для этой задачи будет задача с ограничениями

И минимизируемой целевой функцией

Сравним обе задачи, нетрудно заметить, что:

1. Матрица из коэффициентов при переменных в исходной задаче

И аналогичная матрица в двойственной задаче

получаются друг из друга простой заменой строк столбцами с сохранением их порядка. Такая операция получила название транспонирование.

2. В исходной задаче n переменных и m ограничений» в двой­ственной—m переменных и n ограничений.

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

4. В систему ограничений исходной задачи входят неравен­ства типа, причем в задаче требуется максимизировать целе­вую функцию F. В систему ограничений двойственной задачи входят неравенства типа, причем в двойственной задаче требуется минимизировать целевую функцию.

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

Следующая таблица значительно облегчает процесс составле­ния математической модели двойственной задачи.

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

Чтобы получить, например, первое ограничение двойственной задачи, надо найти сумму произведений чисел, стоящих в столбце под х1 на соответствующие переменные первого столбца: а11у1+а21у2+…+аm1ym. Считаем, что эта сумма не меньше с1: а11у1+а21у2+…=аm1ym с1.

Аналогично составляются и остальные ограничения для двой­ственной задачи. При этом устанавливается такое соответствие:

1)переменной х1 исходной задачи соответствует первое ограничение двойственной задачи, переменной х2 — второе ограничение двойственной задачи и т. д., переменной хn -последнее ограничение двойственной задачи и наоборот;

2)переменной у1. двойственной задачи соответствует первое ограничение исходной задачи и т. д., переменной уm двойственной задачи соответствует последнее ограничение исходной задачи.

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

Если система ограничений исходной задачи на максимум, кроме неравенств типа, содержит неравенства типа, то перед построением двойственной задачи левые и правые части неравенств типа необходимо умножить на -1. А в задаче на минимум неравенства типа умножаем на -1. Если в исходной задаче имеются ограничения, заданные равенствами то каждое из них заменяется двумя ограничениями-неравенст­вами, а затем в зависимости от типа задач поступают, как было сказано выше Например, пусть в систему ограничении исход­ной задачи на максимум входит уравнение: 2х1+3х2+5х3-= 12.

Легко видеть, что

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