Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 10
Текст из файла (страница 10)
2.3. Симплекс-алгоритм. Если мы забудем пока о проблеме вырождениости, то каждое замещение дает 0«)0, и мы получаем симплекс-алгоритм — конечный алгоритм для задачи ЛП: если некоторое сг(0, произвести операцию замещения столбцом 1; если с!)О для всех 1, то получено оптимальное бдр. Мы никогда не вернемся к ранее рассмотренному бдр, поскольку стоимость монотонно убывает. Так как имеется лишь г.б. Выбор выгодного столбца конечное число бдр, алгоритм должен закончить работу за конечное число шагов. Отложим вопрос о вырожденности до следующего параграфа, завершив этот параграф неформальной программой (рис.
2,3) и примером симплекс-алгоритма. Пример 2,6. Рассмотрим задачу ЛП с ограничениями из 3 2.5 и функцией стоимости г=х,+х,+х„+х,+х,. Таблица для исходной задачи имеет вид х! хг хэ хл Х5 Для того чтобы начать алгоритм, нужно некоторое бдр и, кроме того, нужно сделать нулевыми компоненты сь соответствующие базисным столбцам. Из 3 2.5 мы знаем, что столбцы 3, 4 и 5 дают бдр, Вычитая строку ! из строк 2 и 3 и вычитая затем полученные строки 1, 2 и 3 из строки О, получаем Б,г, ° -г =- Эта таблица представляет бдр, соответствующее переменным, укаэанным слева, со стоимостью г=б. В столбцах 1 и 2 строки 0 имеем соответственно с,= — 3 и с,= — 3.
Поэтому выгодно ввести в базис столбец 1 или 2. Выбрав столбец 2, находим 6,=! /2 для 1=1, после чего производим операцию замещения относительно элемента х„=2, обведенного кружком. Получающаяся таблица имеет вид х! Х2 х3 хл хо н она дает оптимальное решение со стоимостью г=9/2, ! ] Гл. 2. Симплекс-алгоршпм 54 Выбор ведущего элемента и алгоритм Бяэнда, устраняющий эацинпивание В описанном выше симплекс-алгоритме имеется некоторая неопределенность: мы не сказали, как решить, какой именно столбец 1 (из тех столбцов, которые удовлетворяют условию сз — г,(0) ввести в базис, и мы также не сказали, как быть в том случае, если при вычислении 0„, которое определяет строку 1 и переменную хв,п, выводимую из базиса, минимум достигается более чем при одном значении й Обратимся вначале к вопросу о выборе столбца.
К сожалению, здесь нет хорошей теоретической базы и приходится полагаться на эмпирические наблюдения. Старейший и наиболее широко используемый критерий состоит просто в выборе наиболее отрицательного сг(0. Как установлено выше, при возрастании на единицу переменной кь вводимой в базис, стоимость изменяется на с„поэтому сг можно рассматривать как производную стоимости по расстоянию в пространстве внебазиснык переменных. Тогда выбор наиболее отрицательного сг является разновидностью метода наискорейшего спуска, называемого в этом случае методом внебазисного градиента [Кф.
Однако отсюда вовсе не следует, что действительное уменьшение стоимости О„с; будет максимально возможным, поскольку мы не знаем О,, пока не вычислим отношений для выбора строки, Отсюда вытекает другой подход: выбра1ь столбец, который дает наи. большее уменьшение стоимости. Этот метод, называемый методом наибольшего приращения, требует дополнительных вычислений для каждой операции замещения, но дает возможность достигнуть оптимальности с использованием меньшего числа замещений, чем метод виебазисиого градиента. Увеличение внебазисной переменной кг на единицу изменяет весь вектор х на +1, й=1, х = — хгу, й= В(Г), 1=1, ..., т, 0 в противном случае.
Следовательно, можно вычислить производную стоимости по расстоянию в пространстве всек переменных с)!гл 1+ ~~';,хо. Подход к выбору столбца, соответствующий этой производной, называется методом градиента по всем переменным. Куи и Куанд1КО! сообщают о результатах обширных вычислительных экспериментов с этими и другими методами, Результаты для задач с числом строк до 25 указывают, что метод градиента по всем переменным приводит к оптимальному решению, используя 2.7.
Видар ведущего ох«мента и алгоритм Бтнда ьв меньше замещений, чем методы внебазисного градиента и наибольшего приращения, и является более быстрым. Голдфарб и Рейд [ОЙ1 описали быстрый способ вычисления производной по всем переменным и сообщают о хороших результатах при применении метода градиента по всем переменным. Однако читатель должен относиться к этим результатам с некоторой осторожностью.
Во-первых, времена вычисления, о которых сообщают Кун и Куанд, указывают на ускорение в лучшем случае вдвое, а такое ускорение времени ра. боты часто может быть Результатом изменений в деталях программирования. Во-вторых, случайный класс задач ЛП, использованный в качестве тестов, может не отражать чьих-либо «типичных» задач ЛП. Наконец, важным преимуществом метода внебазисного градиента является простота, и он остается наиболее популярным методом, реально используемым в программировании.
Обратимся теперь к разрешению неопределенностей в процедуре выбора строки. Возможность вырожденности представляет здесь определенную опасность: если в качестве ведущего элемента в симплекс-алгоритме выбран элемент хи(0 и компонента хм из бдр равна О, го 0,=0 и приращение стоимости 0,(с; — г,) =О. То есть стоимость г не убывает, даже если мы выбираем столбец 1, такой, что сг — гг(0. Возможно, далее, что, проделав последовательность таких замещений, мы вернемся в исходную точку. Это означает, что алгоритм будет неограниченхо выполнять один и тот же цикл (в предположении, что выбор столбца и строки делается детерминирован- но), а такая ситуация была бы очень нежелательной. Это явление называется зацикливанием, Пример 2.7 1Ве11.
Рассиотрим таблицу х~ х» х» хл хз хе х« Будем, начиная с данного бдр, проводить операции замещения, используя следующие правила разрешения неопределенностей. (а) Для введения в базисвсегда выбирать внебазисную переменную с наиболее отрицателыым ср (б) При появлении неоднозначности в выборе переменной, выводимой из базиса, всегда вы1ирать базисную переменную с наименьшим индексом.
В результа1е получим следующую последовательность таблиц (ведущие элеуенты обведены кружком). 2.7, Выбор ввдуи!вгв ввемента и алгоритм Бленда 57 После шести операций замещения мы вернулись к исходному бдр. При всех промежуточных замещениях новые базисные переменные вводились на нулевом уровне и стоимость не изменялась, Мы будем говорить, чтосимплекс-алгоритм (с этим специальным правилом замещения) зацикливается. ! ! Стоящую в данный момент перед нами проблему можно рассматривать как проблему такого разрешения неопределенностей в симплекс-алгоритме, которое устраняло бы зацикливание.
Иногда сообщается, что зацикливание вообще не возникает в практике, даже несмотря на то что можно построить искуственные примеры. Одна' ко это противоречит одному недавнему сообщению [КЯ. Кроме того, формулировки некоторых комбинаторных задач в виде задач ЛП сильно вырожденны, и не совсем ясно, можно ли положиться на счастливую случайность избежать зацикливания, не говоря уже об эстетических аспектах. Простейший путь избежать зацикливания — разрешать неопределенности случайным образом. Тогда с вероятностью ! мы выйдем из любого цикла. Однако это усложняет программирование проверки отношения и не является настолько же интеллектуально удовлетворительным, как детерминированное правило, гарантирующее конечность симплекс-алгоритма. Поэтому похоже, что такой подход не популярен.
В одном стандартном подходе к устранению зацикливания допускается произвольный выбор столбца, и неопределенности при вычислении йв разрешаются таким образом, чтобы нулевая строка лексикографически возрастала, обеспечивая, таким образом, тот факт, что никакой базис никогда не повторяется. Этот метод обладает тем преимуществом, что допускает произвольное правило выбора столбца. Мы отложим описание этого метода до гл. !4, Ниже будет описан относительно недавний замечательный по своей простоте алгоритм Блэнда !В!1, устраняющий зацикливание.
Нам потребуется Лемма 2.3. Пусть с' — строка относительных стоимостей в любой таблице Х, с единичным базисом, не обязательносоответствуювцим допустимому решению ('т. е. некоторые х„в нулевом столбце могут быть отрицательными). Пусть у — любое решение системы ограничений Ау=Ь, не обязательно соответствующее допусти. мому решению !'т, е. некоторые у! могут быть отрицательными). Пусть ! — стоимость, соответствующая Х;, и д — стоимость, соответствуюсцая у. Тогда с'у=у — !. Доказательство.
Непосредственными вычислениями получаем с'у= !с' — г') у=с'у — г'у=у — свВ 'Ау=у — с„'В 'Ь=д — Г, посколькУ В гй — нУлевой столбец таблицы Хм [ ! Гл. г. Симплекс-алгоритм Теорема 2.9 (алгоритм Блэнда, устраняющий зацикливание (В1!). Пусть столбец для введения в базис в симплекс-алгоритме выбирается по правилу 1 гп(п(1': с — гг <О) (выбрать прибыльный столбец с наименьшим номером), а сапрока выбирается по правилу В(1) =ппп (В(1): х; > О и — "("аа для хы хаг каждого й, такого, что хаг > О) 1в случае неопределенности для вывода из базиса выбрать столбец с наименьшим номером).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
