Правило Бланда
В математической оптимизации правило Бланда (также известное как алгоритм Бланда , правило антизацикливания Бланда или правило поворота Бланда ) представляет собой алгоритмическое усовершенствование симплексного метода линейной оптимизации .
С помощью правила Бланда симплексный алгоритм решает возможные задачи линейной оптимизации без циклического выполнения. [ 1 ] [ 2 ] [ 3 ]
Исходный симплексный алгоритм начинается с произвольного базового допустимого решения , а затем меняет базис, чтобы уменьшить цель минимизации и найти оптимальное решение. Обычно цель действительно уменьшается на каждом шаге, и, таким образом, после ограниченного числа шагов находится оптимальное решение. Однако существуют примеры вырожденных линейных программ, в которых исходный симплексный алгоритм работает вечно. Он застревает на базовом допустимом решении (угле допустимого многогранника) и циклически меняет основания, не уменьшая цель минимизации.
Таких циклов позволяет избежать правило Блэнда для выбора столбца для входа и столбца для выхода из базиса.
Правило Бланда было разработано Робертом Г. Бландом , ныне почетным профессором исследования операций в Корнелльском университете , когда он был научным сотрудником в Центре исследования операций и эконометрики в Бельгии. [ 1 ]
Алгоритм
[ редактировать ]Во время итерации симплексного метода используется правило Бланда, чтобы решить, какой столбец (известный как входная переменная ), а затем строку (известную как выходная переменная ) в таблице следует поворачивать. Предполагая, что задача состоит в минимизации целевой функции, алгоритм в общих чертах определяется следующим образом:
- Выберите небазовый столбец с наименьшим номером (т. е. самый левый) с отрицательной (приведенной) стоимостью.
- Теперь среди строк выберите строку с наименьшим соотношением между (преобразованной) правой частью и коэффициентом в сводной таблице, где коэффициент больше нуля. Если минимальное соотношение является общим для нескольких строк, выберите строку с базовым столбцом (переменной) с наименьшим номером.
Формально можно доказать, что с помощью правила выбора Бланда симплексный алгоритм никогда не повторяется, поэтому он гарантированно завершится за ограниченное время.
Хотя правило поворота Бланда теоретически важно, с практической точки зрения оно весьма неэффективно, и для его сходимости требуется много времени. На практике используются другие правила разворота, и зацикливания почти никогда не происходит. [ 4 ] : 72–76
Расширения ориентированных матроидов
[ редактировать ]В абстрактной ситуации ориентированных матроидов правило Блэнда повторяется на некоторых примерах. Ограниченный класс ориентированных матроидов, для которых правило Бланда позволяет избежать циклического движения, был назван Джеком Эдмондсом «ориентированными матроидами Бланда» . Другое правило поворота, алгоритм крест-накрест , позволяет избежать циклов во всех линейных программах с ориентированным матроидом. [ 5 ]
Примечания
[ редактировать ]- ^ Перейти обратно: а б Блэнд (1977) .
- ^ Христос Х. Пападимитриу, Кеннет Стейглиц (29 января 1998 г.). Комбинаторная оптимизация: алгоритмы и сложность . Дуврские публикации. стр. 53–55 . ISBN 9780486402581 .
- ^ Университет Брауна - факультет компьютерных наук (18 октября 2007 г.). «Заметки о симплексном алгоритме» (PDF) . Проверено 17 декабря 2007 г.
- ^ Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования . Берлин: Шпрингер. ISBN 3-540-30697-8 . : 44–48
- ^ Фукуда, Комей ; Терлаки, Тамаш (1997). Томас М. Либлинг; Доминик де Верра (ред.). «Перекрестные методы: свежий взгляд на алгоритмы поворота» (PDF) . Математическое программирование, серия Б. 79 (1–3). Амстердам: Издательство Северной Голландии: 369–395. дои : 10.1007/BF02614325 . МР 1464775 . S2CID 2794181 .
Дальнейшее чтение
[ редактировать ]- Бланд, Роберт Г. (май 1977 г.). «Новые конечные правила поворота для симплексного метода». Математика исследования операций . 2 (2): 103–107. дои : 10.1287/moor.2.2.103 . JSTOR 3689647 . МР 0459599 .
- Джордж Б. Данциг и Мукунд Н. Тапа. 2003. Линейное программирование 2: теория и расширения . Спрингер-Верлаг.
- Катта Г. Мурти, Линейное программирование , Wiley, 1983.
- Эвар Д. Неринг и Альберт В. Такер , 1993, Линейные программы и связанные с ними проблемы , Academic Press.
- М. Падберг, Линейная оптимизация и расширения , второе издание, Springer-Verlag, 1999.
- Христос Х. Пападимитриу и Кеннет Стейглиц, Комбинаторная оптимизация: алгоритмы и сложность , Исправленное переиздание с новым предисловием, Дувр. (Информатика)
- Александр Шрийвер , Теория линейного и целочисленного программирования . Джон Уайли и сыновья, 1998 г. ISBN 0-471-98232-6 (математический)
- Майкл Дж. Тодд (февраль 2002 г.). «Многогранность линейного программирования». Математическое программирование . 91 (3): 417–436. дои : 10.1007/s101070100261 . S2CID 6464735 . (Приглашенный опрос с Международного симпозиума по математическому программированию.)