Правило Блэнда
Правило Блэнда (известное также как алгоритм Блэнда или антицикличное правило Блэнда) — это алгоритмическое уточнение симплекс-метода для линейной оптимизации.
С правилом Блэнда алгоритм симплекс-метода решает допустимые задачи линейной оптимизации без зацикливания[1][2][3]. Существуют примеры вырожденных задач оптимизации, на которых оригинальный симплекс-метод переходит в бесконечный цикл. Такое зацикливание предотвращает правило Блэнда выбора столбца при вводе в базис.
Правило Блэнда разработал Роберт Г. Блэнд, ныне профессор в области исследования операций в Корнеллском университете, когда он был научным сотрудником центра исследования операций и эконометрики в Бельгии[1].
Алгоритм
правитьПравило Блэнда используется во время итерации симплекс-метода для определения, какой столбец вводится в базис (т.е. вводимая переменная) и какая строка (выводимая переменная) выводится из базиса. Если принять, что задача заключается в минимизации целевой функции, алгоритм можно описать в общих чертах следующим образом:
- Выбираем небазисный столбец с наименьшим индексом (т.е. самый левый) с отрицательной невязкой цены.
- Среди всех строк выбираем ту, для которой достигается минимум отношения (преобразованной) правой части и коэффициента вводимого столбца в таблице при условии, что этот коэффициент больше нуля. Если такой минимум достигается на нескольких строках, выбираем строку, соответствующую столбцу (переменной) с наименьшим индексом.
Расширение для ориентированных матроидов
правитьВ среде ориентированных матроидов правило Блэнда на некоторых примерах зацикливается. Класс ориентированных матроидов, на которых правило Блэнда не зацикливается, Джек Эдмондс назвал "ориентированными матроидами Блэнда". Другое правило выбора, перекрёстный алгоритм[англ.], избегает зацикливания для всех задач линейного программирования на ориентированных матроидах[4].
Примечания
править- ↑ 1 2 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. — .
- 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.
На эту статью не ссылаются другие статьи Википедии. |
Для улучшения этой статьи желательно:
|