12. Геометрическая интерпретация линейных оптимизационных задач.

Сущ-т 2 вида геометрических представлений оптимизационных задач

1. в пространстве решений

2. в пространстве условий

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

Представление в пространстве решений большого числа измерений

Рассмотрим n-мерное Евклидово пространство, те множество точек, каждая из которых задается n-координатами. Каждое уравнение ограничений соответствует гиперплоскости, которая делит n-мерное пространство на 2 полупространства. Переход в ограничениях от неравенства к равенству указывает направление, точки какого из полупространств является допустимыми.

Пересечение m-полуплоскостей соответствует полному набору ограничений, определяющих множество допустимых решений. В том случае, если это множество является замкнутым, то оно является выпуклым и полиэдральным. Целевая функция также представлена в виде гиперплоскости и если значение целевой функции для оптимального решения является конечным, то оно обязательно задается экстремальной точкой полиэдра системы ограничений. Если N>=2 экстремальных точек является оптимальными, то оптимальными также будут являться. Все точки, лежащие на ребрах и гранях, соединяющих эти точки.

13. Вырожденность и зацикливание

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

Метод 1. Пусть вектор Pj соответствует j-му столбцу матрицы (A,I). Введем бесконечно малое число >0, с помощью его определяем величину b_. Из теории СМ следует, что если b представляет собой вектор правой части ограничений, а В – текущий базис, то все базисные переменные можно представить через . Из этого выражения видно, что выбирая величину  достаточно малой и формируя базис, можно однозначно модифицировать переменную, подлежащую исключению.

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

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

Переменные с явным ограничением

Для многих практических задач ограничения имеют вид:

0<=l_j<x_j<=u_j<=∞(infinity), где l, u – константы, x – переменные.

Если эти ограничения учитывать в явном виде, то размерность задачи (особенно число ограничений) резко увеличится. Поэтому стараются данные ограничениия учитывать косвенным образом, чтобы в явном виде исп-ть лишь основные ограничения вида Ax=b/

Нижний предел 0<=l_j<x_j может контролироваться с помощью использования следующей подстановки x_j=l_j+x’_j (x’_j>=0), то верхним пределом огр-я будет x’_j<=u_j - l_j

При ограничении сверху вида x_j<=u_j< нельзя использовать x_j=u_j - x’_j, тк при этом не гарантируется допустимое решение переменной x_j, чаще всего это ограничение учитывают в неявном виде.

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

При использовании ограничений, принятых в СМ, ограничения сверху для рассмотренной ситуации будут отражены следующим образом : предположим, что Pj – вводимый вектор, который соответсвует условию оптимальности, а(X_B)i – текущее значение базисной переменной, тогда определяем 1 и 2. =min[1, 2, Uj]

Если =1, то x базисное становится не базисным при нулевом значении, а xj вводится в базис.

=2, то x ,удаляется из базиса при достижении верхнего предела, а xj входит в базис.

Для повышения эф-ти вычисления, все небазисные переменные приводятся к нулевой величине путем преобразованием условий задачи к новому виду с помощью подстановки xk=Uk- x’_k (0<= x’_k<=xk) для всех xk, являющимися небазисными и значения которых соответствует верхнему пределу.