![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|
![]() |
![]() |
||||||
![]() |
Eng | Rus | Ukr | ![]() |
![]() |
||||
![]() |
|||||||
![]() |
![]() |
||||||
![]() |
![]() |
![]() |
|||||
![]() |
Исследование операций
|
19.09.2004
|
![]() |
![]() |
|||
6.10. ПОЛИНОМИАЛЬНЫЙ АЛГОРИТМ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯРассмотрим новый алгоритм ЛП, предложенный Н. Кармаркаром в 1984 г. Он имеет полиномиальную сложность. Этот алгоритм в идейном плане близок к алгоритму эллипсоидов и применяется к задачам ЛП, приведенным к некоторой специальной форме. Постановка задачиРассмотрим задачу ЛП над рациональными числами, которая приведена к такой канонической форме: минимизировать при ограничениях
где Пусть Тогда рассмотренная проблема будет иметь вид: минимизировать при ограничениях Оптимизация на сфереЕсли заменим ограничение Сечением сферы и афинного пространства является сфера меньшего размера внутри этого афинного пространства. Откуда задача становится следующей: минимизировать при ограничениях где с' - получена ортогональным проектированием с на Границы целевой функцииПусть
Последнее неравенство следует из линейности
или Таким образом, перейдя из точки Как видим, скорость сходимости этого метода зависит от Проективные преобразованияРассмотрим проективные преобразования пространства
где Нас интересуют проективные преобразования гиперплоскости Эти преобразования описываются следующим образом: где Эти преобразования задаются выражением
Сравнив (6.11.10) с (6.11.9), увидим, что соответствующая матрица
Преобразование
Обратное преобразование задается следующим образом:
Каждая грань симплекса, задаваемая Образ точки Пусть превращается в систему или Будем обозначать афинное подпространство
Очевидно Сечением сферы и афинного подпространства является сфера меньшего размера в том же самом подпространстве, и она имеет тот же самый радиус, если центр исходной сферы лежит в афинном подпространстве. Отсюда мы получим выражение
которое доказывает, что размерность пространства Инвариантные потенциальные функцииАлгоритм генерирует последовательность точек Тем не менее здесь мы сталкиваемся со следующим явлением. Множество линейных функций не инвариантно относительно проективного преобразования, тем не менее отношение линейных функций преобразовывается в отношение линейных функций. С каждой линейной ц.ф.
где Эта функция имеет следующие свойства: любого произвольного уменьшения в значении
оптимизации Описание базового алгоритмаЧтобы сосредоточиться на главных идеях, сделаем некоторые упрощающие допущения. В разделе 3 мы их снимем и покажем, как привести общую задачу линейного программирования (ЗЛП) к канонической форме. Итак, пусть задача ЛП задана в канонической форме (6.10.1)-(6.10.4). Сделаем следующие допущения:
Результаты работы алгоритма следующие: либо существует Алгоритм задает последовательность точек Ш.0. Задать Ш.1. Вычислить следующую точку последовательности: Ш.2. Проверить допустимость. Ш.3. Проверить оптимальность: если условие (признак) оптимальности не выполняется, то перейти к первому шагу. Дадим теперь подробное описание алгоритма. Первый шаг. Он имеет вид П 1. Проектирующее преобразование симплекса П 2. Приближенная оптимизация преобразованной целевой функции на вписанной сфере для нахождения П 3. Применение обратного преобразования Опишем подробно основные процедуры. П 1. Проектирующее преобразование Пусть
где Зададим матрицу Приближенная оптимизация на сфере (алгоритм А). Свяжем ц.ф.
Пусть
где Пусть П 2. Оптимизация насфере Пусть Ограничим афинное пространство Заменим минимизацию потенциальной функции Спроектировать вектор
Нормализовать Сделать шаг длиной
где Применив к
Использовать Второй шаг. Проверка допустимости. Ждем улучшения на величину на каждом шаге. Значение параметра Третий шаг. Проверка оптимальности. Эта проверка делается периодически. Она включает переход из текущей внутренней точки в крайнюю точку без увеличения значения ц.ф. и проверки этой крайней точки на оптимальность. Эта проверка делается только тогда, когда пройдет заданное время с момента последней проверки. Теоретическое обоснавание алгоритмаПриведем несколько теорем, которые дают теоретическое обоснование полиномиального алгоритма Кармаркара. Сначала докажем существование точки, обеспечивающей постоянное уменьшение потенциальной функции. Это утверждается в следующей теореме. Теорема 6.7. Существует точка Далее докажем, что минимизацию Теорема 6.8. Пусть Теорема 6.9. Точка Завершают теоретическое обоснование алгоритма следующие теоремы о сходимости метода. Теорема 6.10. За
Теорема 6.11. При использовании алгоритма выполняется одно из двух условий:
где минимальное значение ц.ф. строго положительно. Докажем эти теоремы. Доказательство теоремы 6.7. Пусть
Следовательно, Пусть
Откуда
Далее используем следующее неравенство. Если
где
Выбрав Доказательство теоремы 6.8. Сначала рассмотрим несколько вспомогательных лемм. Лемма 6.5. Если Доказательство этой леммы основано на простых результатах математического анализа. Лемма 6.6. Пусть
Доказательство. Из того, что В соответствии с леммой 6.5. Доказательство. Из того, что Согласно лемме 6.5.
Здесь И подставив (6.10.28) в (6.10.27), получим окончательно
Теперь докажем теорему 6.8. Обозначим Справедлива следующая цепочка равенств
Согласно теореме 6.7
Для Согласно лемме 6.6 Поскольку Согласно (6.10.30) - (6.10.32)
Положим
Тогда
Заметим, что:
если Доказательство теоремы 6.9. Согласно теореме 6.7. Доказательство теоремы 6.10. Для любого
Однако
Приведение общей задачи ЛП к каноническому видуРассмотрим задачу ЛП в стандартной форме: минимизировать при ограничениях
Покажем, как эту задачу можно привести к требуемому каноническому виду (6.10.1)-(6.10.2). Этот переход основывается на теории двойственности. Первый шаг. Рассмотрим двойственную задачу к (6.10.38)-(6.10.40): максимизировать при ограничениях
Объединим прямую и двойственную задачи в одну:
Согласно теории двойственности эта комбинированная задача допустима тогда и только тогда, когда исходная задача (6.10.38) имеет окончательное решение. Второй шаг. Введем свободные переменные
Третий шаг. Введем искусственную (фиктивную) переменную минимизировать при ограничениях
Заметим, что Для удобства дальнейшего описания сделаем замену обозначений и запишем задачу на третьем шаге в виде минимизировать при ограничениях
где Четвертый шаг. Выполним проективное преобразование положительного ортанта в симплекс. Рассмотрим преобразование
Пусть Преобразование отображает оно однозначное, а обратное к нему задается следующим образом:
образом точки пусть
Итак, определили столбцы матрицы Тогда Пусть поскольку мы заинтересованы в получении значения ц.ф., равном 0, определим
Подставив сюда
получим
Определим Тогда из минимизировать при ограничениях
Центром симплекса является допустимая начальная точка. Таким образом, исходная задача (6.10.38)-(6.10.40) приведена к канонической форме. Применение базового алгоритма А к этой задаче либо даст решение Вычислительная сложность алгоритмаЗначение ц.ф. уменьшается с постоянным коэффициентом для всех
где
Ясно, что величина Два любых различных значения ц.ф. на вершинах На каждом шаге необходимо решать линейную систему уравнений, которая требует Для каждой арифметической операции нужна точность Множитель вида Заключительный анализ и выводыМетод Кармаркара и алгоритмы, которые базируются на нем, могут оказаться полезными при разработке алгоритмов со свойствами глобальной сходимости. Этот метод можно рассматривать как метод наискорейшего спуска в некотором специальном метрическом пространстве на симплексе. Глобальные свойства полученных результатов стали возможными благодаря тому, что произвольную строго внутреннюю точку можно отобразить в любую другую внутреннюю точку с помощью преобразования, которое сохраняет афинность пространства и его метрику. Эту метрику легко обобщить на произвольные выпуклые множества с 'хорошими' границами, а также на сечение этих множеств. Эта метрика эффективно преобразует допустимую область так, что границы области будут находиться на бесконечном расстоянии от внутренних точек. Более того, это преобразование не зависит от вида ц.ф., которая оптимизируется. Поскольку представление исходных переменных в задаче ЛП требует в наихудшем случае Функционирование алгоритма на практикеКаждый шаг алгоритма требует оптимизации линейной функции на эллипсоиде или, что эквивалентно, решения системы линейных уравнений типа Разработанный метод базируется на последовательных модификациях ранга 1. Для него доказано, что верхняя граница необходимого числа операций на один шаг составляет На практике встречаются разреженные матрицы. Поэтому можно сконструировать более эффективные методы для решения рассмотренной выше проблемы. Еще одна особенность алгоритма, которая может привести к сокращению вычислений, следует из того, что не обязательно нужно искать строго оптимальное решение. Полезно различать два вида приближенных решений. Пусть Будем отличать сильное приближение (или приближение в пространстве решений) от слабого приближения (или приближение в пространстве целевых функций). Сильное приближение требует, чтобы решение Для предложенного метода вполне достаточно слабого приближения, а его легче достичь численными методами. Число шагов зависит от Вычислительная стойкость и погрешности округленияВ предложенном алгоритме погрешности округления не накапливаются. Наоборот, этот алгоритм самокорригируется в том понимании, что погрешность округления, полученная на первом шаге, компенсируется на следующих шагах. Если допущена погрешность в 1% в вычислении вектора |
![]() |
||||||
![]() |
|||||||
Copyright © 2002-2004 | ![]() |
||||||
![]() |
![]() |