Правило Блэнда

Правило Блэнда (известное также как алгоритм Блэнда или антицикличное правило Блэнда) — это алгоритмическое уточнение симплекс-метода для линейной оптимизации.

С правилом Блэнда алгоритм симплекс-метода решает допустимые задачи линейной оптимизации без зацикливания^[1]^[2]^[3]. Существуют примеры вырожденных задач оптимизации, на которых оригинальный симплекс-метод переходит в бесконечный цикл. Такое зацикливание предотвращает правило Блэнда выбора столбца при вводе в базис.

Правило Блэнда разработал Роберт Г. Блэнд, ныне профессор в области исследования операций в Корнеллском университете, когда он был научным сотрудником центра исследования операций и эконометрики в Бельгии^[1].

АлгоритмПравить

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

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

Расширение для ориентированных матроидовПравить

В среде ориентированных матроидов правило Блэнда на некоторых примерах зацикливается. Класс ориентированных матроидов, на которых правило Блэнда не зацикливается, Джек Эдмондс назвал "ориентированными матроидами Блэнда". Другое правило выбора, перекрёстный алгоритм^[en], избегает зацикливания для всех задач линейного программирования на ориентированных матроидах^[4].

ПримечанияПравить

↑ ¹ ² Bland, 1977.
↑ Papadimitriou, Steiglitz, 1998, с. 53–55.
↑ Brown University, 2007.
↑ Fukuda, Terlaky, 1997, с. 369–395.

ЛитератураПравить

Christos H. Papadimitriou, Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. — Dover Publications, 1998.
Brown University - Department of Computer Science. Notes on the Simplex Algorithm. — 2007. — Октябрь.
Komei Fukuda, Tamás Terlaky. Criss-cross methods: A fresh view on pivot algorithms // Mathematical Programming: Series B / Thomas M. Liebling, Dominique de Werra. — Amsterdam: North-Holland Publishing Co., 1997. — Т. 79, № 1–3. — С. 369–395. — doi:10.1007/BF02614325.

Литература для дальнейшего чтенияПравить

Robert G. Bland. New finite pivoting rules for the simplex method // Mathematics of Operations Research. — 1977. — Май (т. 2, вып. 2). — С. 103–107. — doi:10.1287/moor.2.2.103. — JSTOR 3689647.
George B. Dantzig, Mukund N. Thapa. Linear Programming 2: Theory and Extensions. — Springer-Verlag, 2003.
Kattta G. Murty. Linear Programming. — Wiley, 1983.
Evar D. Nering, Albert W. Tucker. Linear Programs and Related Problems. — Academic Press, 1993.
M. Padberg. Linear Optimization and Extensions. — Second Edition. — Springer-Verlag, 1999.
Christos H. Papadimitriou, Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. — Corrected republication with a new preface. — Dover. (computer science).
Alexander Schrijver. Theory of Linear and Integer Programming. — John Wiley & sons, 1998. — ISBN 0-471-98232-6.
Michael J. Todd. The many facets of linear programming // Mathematical Programming. — 2002. — Февраль (т. 91, вып. 3). — С. 417–436. — doi:10.1007/s101070100261.

[_1338d5b856f134fc-1] ¹ ² Bland, 1977.

[_8f7779f2ca8d1174-2] Papadimitriou, Steiglitz, 1998, с. 53–55.

[_1fac519baf8b23b0-3] Brown University, 2007.

[_9bac2c88853617c7-4] Fukuda, Terlaky, 1997, с. 369–395.

[1]

[2]

[3]

[4]