Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

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

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

z = CX → min AX ≤ B при X ≥ 0; (1.12)

и

z = RY → max при ATY ≥ C, Y ≥ 0. (1.13)

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

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

- неравенства AX ≤ B и ATY ≥ 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. Здесь каждая строка-ограничение прямой задачи может быть задана как совокупность двух строк

ai1x1 + ... + ainxn ≥ bi

или

ai1x1 + ... + ainxn ≤ bi
ai1x1 + ... + ainxn ≥ bi

или

-ai1x1 - ... - ainxn ≤ - bi

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

a111 - a112 + a213 - a214 +....+am12m-1 - am12m ≤ c1
..... ...... ..... .....
a1n1 - a1n2 + a2n3 - a2n4 +....+amn2m-1 - amn2m ≤ cn (1.14)
1,...,ȳ2m ≥ 0

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

z = CX → min при AХ = B, Х ≥ 0, и
z̄ = BY → →max при ATY ≤ CΟ

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

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"