1.5. Двойственность в линейном программировании. Проблема зацикливания

Рассмотрим следующие две задачи с ограничениями- неравенствами:

и

Нетрудно видеть, что они имеют ряд особенностей:

- матрица коэффициентов в условиях (1.13) является транспортированной матрицей A системы (1.12),

- неравенства AX ≤ B и A^TY ≥ C имеют противоположные знаки;

- при переходе от (1.12) к (1.13) меняются роли R и C

- смысл экстремума z противоположен смыслу экстремума z̄.

Задачи, обладающие перечисленными свойствами, называются взаимно двойственными. Их изучение оправдано тем, что в практике различных исследований иногда легче решать двойственную задачу, чем прямую. Допустимость перехода от прямой задачи к двойственной (и наоборот) утверждается теоремой двойственности, приводимой здесь без доказательства: если существуют решения систем (1.12), (1.13), то среди чих есть и оптимальные, причем такие, что min z = max z̄.

Удобство формального перехода от (1.12) к (1.13) сохраняется лишь тогда, когда задачи даны в нестандартной форме, поэтому важно рассмотреть и случай стандартных условий AХ =B, X ≥ 0. Здесь каждая строка-ограничение прямой задачи может быть задана как совокупность двух строк

или

или

после чего двойственные условия принимают вид

Количество переменных ȳ в (1.14) возросло до 2m, и этот нежелательный эффект компенсируется несложными преобразованиями системы (1.14), где каждая разность (ȳ₁ - ȳ₂),..., (ȳ_2m-1 - ȳ_m) рассматривается как новая переменная у с соответствующим индексом, не имеющая ограничения на знак. Таким образом, возникает новый вариант записи условий двойственных задач:

Одним из основных недостатков симплекс-метода является так называемое зацикливание, возникающее в тех случаях, когда на очередном шаге поиска X^*, z^* приходится иметь дело с вырожденным базисным решением. Подобная ситуация характеризуется невозможностью перехода к новому допустимому базисному решению; она начинает повторяться с определенной частотой (зависящей от числа нулевых базисных переменных), и такое повторение может продолжаться довольно долго. В принципе зацикливание преодолимо (оно встречается сравнительно редко); в качестве практических рекомендаций здесь называют обычно отказ от ввода в базис той x_р, для которой c̄_p = s = _m+1≤j≤nmin{c̄_j < 0} (сМ. § 1.4); случайный выбор новой крайней точки множества U (с целью продолжить процесс поиска экстремума в облегченных условиях), использование конкретных особенностей исследуемой задачи для предсказания структуры оптимальных решений и т. д.