Правило Блэнда
Правило Блэнда (известное также как алгоритм Блэнда или антицикличное правило Блэнда) — это алгоритмическое уточнение симплекс-метода для линейной оптимизации.
С правилом Блэнда алгоритм симплекс-метода решает допустимые задачи линейной оптимизации без зацикливания[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.
 | На эту статью не ссылаются другие статьи Википедии. |
| Для улучшения этой статьи желательно:
|