Правило Блэндса - Википедия - Blands rule

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

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

Исходный симплекс-алгоритм начинается с произвольного базовое возможное решение, а затем меняет основу, чтобы увеличить цель максимизации и найти оптимальное решение. Обычно цель действительно увеличивается на каждом шаге, и, таким образом, после ограниченного количества шагов находится оптимальное решение. Однако есть примеры вырожденных линейных программ, в которых исходный симплексный алгоритм повторяется бесконечно. Он застревает в базовое возможное решение (угол допустимого многогранника) и циклически меняет основания без увеличения цели максимизации.

Таких циклов избегает правило Бланда о выборе столбца для входа в основу.

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

Алгоритм

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

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

Можно формально доказать, что с помощью правила выбора Блэнда симплекс-алгоритм никогда не зацикливается, поэтому его завершение гарантировано за ограниченное время.

Хотя правило поворота Блэнда теоретически важно, с практической точки зрения оно довольно неэффективно и требует много времени, чтобы сойтись. На практике используются другие правила разворота, и зацикливания почти не бывает.[4]:72–76

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

В абстрактной обстановке ориентированные матроиды Правила Блэнда повторяются на некоторых примерах. Ограниченный класс ориентированных матроидов, на которых правило Блэнда избегает цикличности, был назван "Блэндориентированными матроидами". Джек Эдмондс. Еще одно поворотное правило: перекрестный алгоритм, избегает циклов на всех ориентированных матроидных линейных программах.[5]

Примечания

  1. ^ а б Блэнд (1977).
  2. ^ Христос Х. Пападимитриу, Кеннет Стейглиц (1998-01-29). Комбинаторная оптимизация: алгоритмы и сложность. Dover Publications. стр.53 –55.
  3. ^ Брауновский университет - Департамент компьютерных наук (2007-10-18). «Замечания по симплексному алгоритму» (PDF). Получено 2007-12-17.
  4. ^ Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования. Берлин: Springer. ISBN  3-540-30697-8.:44–48
  5. ^ Фукуда, Комей; Терлаки, Тамаш (1997). Томас М. Либлинг; Доминик де Верра (ред.). «Перекрестные методы: свежий взгляд на алгоритмы разворота» (PDF). Математическое программирование, серия B. Амстердам: North-Holland Publishing Co. 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.CS1 maint: ref = harv (связь)
  • Джордж Б. Данциг и Мукунд Н. Тапа. 2003 г. Линейное программирование 2: теория и расширения. Springer-Verlag.
  • Каттта Дж. Мурти, Линейное программирование, Wiley, 1983.
  • Эвар Д. Неринг и Альберт В. Такер, 1993, Линейные программы и связанные с ними задачи, Academic Press.
  • М. Падберг, Линейная оптимизация и расширения, Второе издание, Springer-Verlag, 1999.
  • Христос Х. Пападимитриу и Кеннет Стейглиц, Комбинаторная оптимизация: алгоритмы и сложность, Исправленное переиздание с новым предисловием, Dover. (Информатика)
  • Александр Шрайвер, Теория линейного и целочисленного программирования. Джон Вили и сыновья, 1998 г., ISBN  0-471-98232-6 (математический)
  • Майкл Дж. Тодд (февраль 2002 г.). «Многогранность линейного программирования». Математическое программирование. 91 (3): 417–436. Дои:10.1007 / с101070100261. S2CID  6464735. (Приглашенный опрос с Международного симпозиума по математическому программированию.)