8.2. ВЫПУКЛЫЙ СИМПЛЕКСНЫЙ МЕТОД

Метод линейной аппроксимации для решения подзадачи ЛП использует линейный симплексный метод. Выпуклый симплексный метод стремится действовать по

структуре линейного симплексного метода. Действительно, встречая любой линейный участок целевой функции,

- он ведет себя точно так же, как линейный симплексный метод. Метод первоначально был разработан для задач минимизации выпуклой функции при линейных ограничениях в виде неравенств. Учитывая его связь с линейным симплексным методом, его назвали выпуклым симплексным методом. Для обеспечения соответствия с остальными частями книги здесь выпуклый симплексный метод описан для задачи (8.1) с функцией общего вида имеющей непрерывные частные производные

Сущность выпуклого симплексного метода. Выпуклый симплексный метод будет обоснован неформальным рассмотрением. После этого эвристического объяснения представим точную математическую формулировку метода. Мы будем следовать линейному симплексному методу для задачи (8.1) до тех пор, пока это можно, и модифицировать его только в связи с требованием нелинейности целевой функции. Здесь приписывание нижнего индекса к вектору обозначает компоненту вектора, например представляет собой компоненту вектора

Без ограничения общности предполагается, что, как этого требует стандартная процедура фазы все строки матрицы А линейно независимы и процедура фазы 1 дает исходное допустимое базисное решение симплексную таблицу и соответствующую правую часть , такую, что

Выпуклый симплексный метод вырабатывает последовательность таблиц, каждая из которых получается из предыдущей стандартным методом направляющего элемента. Можно предположить, что каждая таблица Т представляет собой матрицу размером Пусть номер столбца, связанного с базисным переменным, тогда столбец целиком состоит из нулей

за исключением позиции, где стоит единица. Так как базисное решение, то

где базисное переменное, а - множество первых положительных целых чисел. Все небазисные переменные в векторе равны нулю.

В линейном симплексном методе далее вычислили бы вектор оценок, соответствующий таблице и либо выяснилась бы оптимальность либо увеличили бы некоторое небазисное переменное. При нелинейной целевой функции вектор оценок может быть вычислен с помощью соответственно определяемого градиента функции Для данной таблицы Т положим

Тогда оценками вектора х для данной таблицы Т будут

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

Пусть для таблицы вычислен вектор оценок . В линейном симплексном методе мы определили бы значение

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

Если для всех то могло бы быть увеличено бесконечно, что означает неограниченность целевой функции. В противном случае увеличивается до

тех пор, пока некоторое базисное переменное, скажем не превратится в нуль. Тогда таблица преобразуется по направляющему элементу Заметим, что компоненты х, которые входят в новый базис, это компоненты с наибольшими значениями. Таким образом, наибольших компонент х входят в базис.

При нелинейной целевой функции, если увеличение и соответствующее изменение только базисных переменных, первоначально вызывая увеличение может при слишком большом увеличении привести к уменьшению Выпуклый симплексный метод увеличивает либо до тех пор, пока дальнейшее возрастание не увеличивает либо до превращения некоторого базисного переменного в нуль. Значение х, при котором первым наступает одно из этих двух событий, представляет собой точку

Точная процедура заключается в следующем. Либо для некоторого либо нет. Если существует

для которого то увеличение может свести некоторое базисное переменное к нулю. Пусть представляет собой значение х, которое достигается при возрастании до тех пор, пока некоторое базисное переменное становится нулем. Значение при этом получается из формулы

С другой стороны, нет оказаться, что

Тогда можно увеличивать бесконечно, не перемещая к нулю ни одно из базисных переменных (геометрически точка опишет луч, исходящий из точки . В этом случае пусть — произвольная точка на этом луче. Определим точку на этом луче, которая максимизирует

для очень большого значения а.

После того как вычислена, в качестве таблицы выбирается любая таблица, где наибольших по величине компонент х образуют базис.

Итерация 1 завершена, и мы переходим к итерации 2. Следует обратить внимание на то, что, если одно из переменных старого базиса не превратилось в нуль, то точка соответствующая таблице может иметь положительное небазисное переменное. Итак, некоторое небазисное переменное, скажем может быть положительным. Для общности предположим, что это так. Опять вычислим вектор оценок

Если положительное небазисное переменное имеет отрицательную оценку, то, уменьшая это переменное и меняя соответственно только базисные переменные, можно увеличить Аналогично, если какое-либо небазисное переменное имеет положительную оценку, то его возрастание будет увеличивать Пусть

Если то — подходящий кандидат для увеличения. Если то должно быть положительным и — подходящий кандидат для уменьшения.

Правило для выбора или будет изложено далее. Если то следует увеличивать до тех пор, пока либо перестанет возрастать, либо некоторое базисное переменное станет нулем. Если то следует уменьшать до тех пор, пока либо перестанет возрастать, либо само превратится в нуль, либо, наконец, одно из базисных переменных обратится в нуль. Обозначим соответствующее значение переменного х через Далее процедура продолжается аналогично итерации 2.

Теперь дадим точную формулировку выпуклого симплексного метода.

Алгоритмическая процедура. В нижеприведенной процедуре любая связь может быть произвольно разорвана.

Исходный шаг. Процедурой фазы 1 линейного симплексного метода получаем допустимое базисное решение с соответствующей таблицей Переходим к шагу 1 итерации со значением

Итерация Дана допустимая точка и таблица

Шаг 1. Вычисляется вектор оценок. Пусть

Если то конец. В противном случае происходит переход к шагу 2.

Шаг 2. Определяется небазисное переменное для изменения. Если то увеличивается при соответствующем изменении только базисных переменных; если то уменьшается при соответствующем изменении только базисных переменных.

Шаг 3. Вычисляется Здесь следует рассмотреть три случая.

Случай а. должно быть увеличено, и для некоторого

Соответствующее возрастание превратит некоторое базисное переменное в нуль. Пусть — значение х, которое при этом достигается. В явной форме

где — множество индексов небазисных переменных за исключением , а

Определяем

где

Случай б. должно быть увеличено, для всех . В этом случае может возрастать бесконечно, не приближая при этом к нулю ни одно из базисных

переменных. Определяется как в (8.19), за исключением того, что принимается Определяется такое, что

где при очень большом значении а и

Случай в. должно быть уменьшено. Определяем с помощью (8.19), за исключением того, что определяется следующим образом:

где

и

Если то полагаем Здесь значение х, соответствующее точке, в которой при уменьшении либо некоторое базисное переменное становится нулем, либо само превращается в нуль (в зависимости от того, что происходит раньше). Далее вычисляется с помощью (8.21).

Шаг 4. Вычислив определяем таблицу как показано в следующем пункте, и заменив на осуществляем переход к итерации.

Выбор таблицы. В любом из перечисленных случаев таблица определяется по точке следующим образом. Осуществляется упорядочение компонент по величине Определяем наибольших по величине. Пусть — любая такая таблица, что эти компонент входят в базис для этой таблицы. Таким образом, переменные являются базисными и соответствующие им столбцы таблицы представляют собой единичные векторы. Случайно, из-за линейной зависимости, может оказаться невозможным включить наибольших компонент в базис. В таком случае базис определяется из наибольших компонент или, если необходимо, то из Величины компонент в базисе должны быть как можно

болышими. Короче, в базис нужно включать наибольшее количество наибольших по величине компонент

Как пример правила для выбора таблицы предположим, сначала ограничения имеют следующий вид:

Если то образуют базис. Соответствующая таблица имеет вид

где Если было бы , то мы могли бы выбрать с таблицей

В этом случае и также могли бы быть выбращл в качестве базисных.

Следует обратить внимание на то, что правая часть не имеет значения.

Вырождение. Очевидно, что в случае, если — линейная функция, выпуклый симплексный метод превращается в линейный симплексный метод. При этом известно, что если базисное переменное превращается в нуль, то линейный симплексный метод может не сходиться. Для того чтобы избежать этого вырождения и возможного нарушения сходимости, разработаны специальные процедуры. Однако на практике нет особой необходимости в применении этих процедур. Поэтому, чтобы упростить изложение, мы просто принимаем следующее предположение невырожденности, которое аналогично соответствующему предположению для линейного симплексного метода.

Предположение невырожденности. Базисные переменные всегда положительны. Принятие этого предположения невырожденности весьма целесообразно, так как при этом наибольших компонент могут быть приняты за базисные.

Доказательство сходимости. Теперь можно доказать сходимость метода в предположениях невырожденности и непрерывной дифференцируемости . Воспользуемся теоремой сходимости А.

Как обычно, мы предполагаем, что все входят в компактное множество так что условие 1 удовлетворяется.

Пусть определим

Точка х будет называться подходящей, если х удовлетворяет условиям Куна — Таккера для задачи (8.1). Следующая лемма поможет нам при доказательстве. В лемме квадратные скобки с нижним индексом означают компоненты, например

Лемма 8.1. Рассмотрим задачу (8.1) с непрерывно дифференцируемой целевой функцией Пусть — некоторая симплексная таблица линейного программирования с соответствующей правой частью так что в том и только в том случае, если х — допустимая точка. Предположим также, что х — допустимая точка, а

— соответствующий ей вектор оценок. Пусть

Тогда, если то подходящая точка.

Доказательство. Так как то х удовлетворяет соотношениям

Кроме того, так как — соответствующая то существует неособенная базисная обратная матрица порядка такая, что

где А — исходная матрица ограничений.

Если положить

то (8.23) принимает вид

Но из (8.26) видно, что х удовлетворяет условиям Куна—Таккера для задачи (8.1). Лемма доказана.

Условие 2. Если то алгоритм завершает свою работу и согласно лемме 8.1 х является подходящим, что подтверждает выполнение условия 2б теоремы сходимости А.

Чтобы установить выполнение условия 2а, допустим, что должно быть увеличено. Пусть имеет место случай Положим, где определяется по (8.19). Обратите внимание на то, что 0, так как благодаря предположению невырожденности

Таким образом,

Используя определение получим

Так как из (8.27) и по предположению, то

Но из (8.21) максимизирует в направлении Значит,

Аналогичное доказательство остается в силе и для остальных случаев и, следовательно, условие 2а выполняется.

Условие 3. Следует проверить выполнение условия 3.

Анализ алгоритма обнаруживает, что мы можем разбить алгоритмическое отображение А на четыре

компоненты, Здесь по данному х дает тот же х и таблицу Т

Отображение по дает один из случаев (а),(б) или (в), индекс небазисного переменного подлежащего изменению и те же

Далее определяет направление

Следует обратить внимание на то, что таблица уже больше не требуется.

Наконец, — это обычное отображение и оно определяет последующую точку, но в этой процедуре зависит не только от х и но и от того, какой случай имеет место. Случай определяет интервал потому что в случаях (а) и а в случае .

где — точка, следующая за х.

Замкнутость композиции. Нам следует доказать, что все эти отображения замкнуты. Тогда замкнутость А будет следовать из следствия 4.2.1 потому, что все отображения отображают из компактных множеств в компактные множества. Мы предположили, что все х входят в компактное множество X. Имеется только конечное количество таблиц, так что все таблицы также входят в компактное множество. Следовательно, так как отображение дает точки , значит, оно переводит из компактного множества в компактное множество.

Для индексы конечно, принадлежат к компактному множеству, так как их имеется только конечное число, аналогично случаи (а),(б),(в) также входят в компактное множество. Рассмотрение показывает, что оно тоже входит в компактное множество, так как направление и все у их входят в компактное множество. Аналогично также отображает из компактного множества в компактное множество. Таким образом, как только будет доказана замкнутость всех составляющих А, само А также будет замкнутым.

Напомним, что при доказательстве замкнутости можно предположить, что х не является допустимой точкой и что все связи могут быть произвольно разорваны.

Замкнутость Пусть

Необходимо доказать, что или, эквивалентно, что в точке может быть составлена таблица

Вследствие того, что существует конечное число таблиц, должны существовать таблица такие, что для

В точке таблица Т также будет таблицей с наибольшим числом наибольших по величине компонент в базисе. Это следует из того, что для если входит в базис, соответствующий таблице не входит, то

Переходя к пределу, получаем Таким образом, в точке опять может быть в базисе. Следовательно, в точке в качестве таблицы может быть выбрано Т. Напомним, что связи могут быть разорваны произвольно. Поэтому, если то замкнуто.

Замкнутость Пусть

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

Мы должны установить, что могут быть получены из с таблицей реализуется случай и можно изменять компоненту

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

качестве упражнения. Наконец, какая-то таблица Т также реализуется бесконечное число раз.

Таким образом, для некоторого

Описывая случаи (в) в явной фирме для имеем

Ни вследствие непрерывности чекгор также не прерывен, и перейдя к пределу в (8.31), получаем

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

Замкнутость Для так же, как было при доказательстве замкнутости можно предположить

Замкнутость будет установлена доказательством того, что можно выработать направление по данной точке таблице и компоненте подлежащей уменьшению.

В случае (в) или или Поэтому существует" такое, что реализуется один из этих двух случаев. Предположим, что (Для

случая аргументация аналогичная.) Тогда согласно выбору

Благодаря тому, что в базисе содержится лишь конечное число переменных, существует такое, что для на данном скажем достигается максимум. Значит, для

Взяв предел в (8.34), получим следующее выражение:

Но из (8.19) для получаем

где

Итак, по построению

Учитывая выражения (8.35) и (8.36) и то, что реализуется случай видим, что в точке в качестве направления может быть выбрано Следовательно, замкнуто.

Наконец, на основе леммы 5.1 отображение замкнуто для всех трех случаев.

Резюмируя, видим, что все составляющие отображения А замкнуты. Выполнение условия 3 доказано, и выпуклый симплексный метод сходится.

Пример.

Рассмотрим задачу

Следует обратить внимание на то, что вместо максимизаций требуется минимизация. После введения дополнительных переменных ограничения принимают вид

Допустим, что уже сделано несколько итераций и получено . Для простоты знаки транспонирования будут ощущены, и соответствующая ей таблица имеют вид

Здесь

Шаг 1.

Так как наша задача заключается в минимизации, мы меняем местами операции при вычислении

Шаг 2. Поэтому уменьшаем Имеет место случай (в).

Шаг 3. Случай (в)

так что

(см. скан)