Метод последовательной активации ограничений в линейном программировании | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/11

Метод последовательной активации ограничений в линейном программировании

Представлен алгоритм решения задачи линейного программирования посредством процедуры последовательной активации ограничений (включения в расчёт одного за другим) с удержанием состояния оптимальности на сгенерированной последовательности вложенных многогранников. Вследствие сжатия области допустимых решений при критерии оптимальности «шах» целевая функция на каждом шаге убывает (движение к максимуму сверху), в противоположность росту в других методах (снизу). Компьютерные эксперименты демонстрируют преимущества программной реализации этого алгоритма перед опцией симплекс-метода программы linprog библиотеки MATLAB в скорости и полноте выводимой информации.

Method for sequential activation of limitations in linear programming.pdf Введение Число существенно различных методов условной линейной оптимизации невелико. Еще в 1939 г. Л. В. Канторович сформулировал ряд задач линейного программирования и для их решения предложил метод разрешающих множителей [1]. В 1947 г. Дж. Данцигом был создан симплекс-метод, нашедший отражение в отечественной литературе в изложении автора в переводе [2]. Разработанные в то время методы последовательного улучшения плана, сокращения оценок и сокращения невязок классифицируются по типу решаемых ими задач - прямой, двойственной или сразу обеих [3]. В середине 1960-х годов И. И. Дикин в [4] предложил решение задачи линейного программирования методом внутренних точек. Поиск новых подходов к оптимизации дал эффектный, но вычислительно неэффективный метод эллипсоидов Л. Г. Хачияна [5], принципиально важным достоинством которого явилось выражение времени счёта полиномом от размерности задачи. Полиномиальность варианта метода внутренних точек Н. Кармаркара от 1984 г. в совокупности с его вычислительной эффективностью послужила причиной его патентования в США. Следствием изысканий в данном направлении было множество публикаций, в их числе [6-8]. Метод внутренних точек глубоко проработан и как эффективный оптимизатор задействован в ряде программных продуктов, в том числе в MATLAB. К недавним разработкам относятся метод оператора-проектора [9] и скелетный алгоритм [10]. Суть первого заключается в проектировании произвольной точки на гиперплоскости ограничений вплоть до попадания в область допустимых решений и удержании последующих перемещений в заданных границах согласно критерию оптимальности. Скелетный алгоритм не требует обращения матриц и подменяет исходную задачу рядом вспомогательных задач пониженной размерности. В процессе тестовых расчётов установлено быстрое продвижение к оптимуму в начале вычислительного процесса и его резкое замедление по мере приближения к цели. Метод внутренних точек является приближённым и находит решение со сколь угодно малой заданной погрешностью, но полиномиален; ни один из известных точных алгоритмов таким важным свойством не обладает, за некоторыми исключениями. Так, при условии неотрицательности всех параметров задачи и совместности системы ограничений метод экспоненциальной аппроксимации [11] обещает находить точный оптимум в задаче с n переменными и m ^ n равенствами всего за (n - m) шагов. Алгоритм выявляет и исключает переменные с гарантированно нулевыми оптимальными значениями, и решение исходной задачи завершается решением системы уравнений с квадратной матрицей m-го порядка. Перспективы ослабления жёстких требований этого метода к исходным данным не просматриваются. Перечисленные выше методы объединяют два общих свойства: - многогранник допустимых решений подразумевается существующим в своем целостном виде, т. е. предполагается одновременная действенность всех ограничений системы условий; - на каждом шаге поиск следующей точки производится с умыслом улучшения значения целевой функции в пределах области допустимых решений. Недавние публикации свидетельствуют, что, несмотря на снижение интереса к проблематике линейного программирования, поиск новых путей в этой сфере продолжается. В [12] автор завершил разработку точного алгоритма решения задачи линейного программирования с использованием параметризации лимитов системы условий, запрограммировал его на языке Fortran-4 и успешно апробировал на ЕС-ЭВМ. С учётом современных возможностей программных и аппаратных средств данный метод им основательно доработан и реализован средствами MATLAB. Далее изложена доказательная база этого по сути геометрического метода решения общей задачи линейного программирования, отличительная черта которого состоит в следующем. Многогранник допустимых решений не существует изначально, а формируется путём последовательного включения в расчёт (активации с помощью параметризации лимитов) ограничений с удержанием оптимальности целевой функции на генерируемой последовательности вложенных многогранников. Начальным является гиперпараллелограмм, задаваемый ограничениями на переменные с возможно неограниченными лимитами, на котором оптимум определяется элементарно. Затем в его систему условий добавляется первое нетривиальное ограничение, быстрым пересчётом находится оптимум на построенном многограннике (вложенном в предыдущий) и т. д. Активируя неравенства, алгоритм последовательно усекает образующиеся многогранники до окончательной конфигурации, постепенно сужая область допустимых решений, вычисляя и фиксируя на каждой итерации алгебраические и геометрические характеристики текущего оптимума для последующих применений. Метод оперирует с неравенствами и, исключая переменные через посредство равенств, понижает размерность задачи, но может работать напрямую и с равенствами, легко разбираясь с ситуациями вырожденности и маскировки равенств совокупностью неравенств. В результате сжатия области допустимых решений в задачах с критерием оптимальности «max» целевая функция на каждом шаге убывает или, по крайней мере, не возрастает (к максимуму сверху), в противоположность её традиционному увеличению в других методах (снизу). Геометрически происходит перемещение в оптимум вдоль некоторой ломаной прямой из тривиально определяемой точки, которая для многогранника допустимых решений может оказаться как граничной, так и внешней. В процессе активации ограничений выявляется несовместность системы условий с указанием виновных в этом ограничений, вычисляются координаты оптимальной вершины и смежных с ней в случае неединственности, а также определяются двойственные переменные как оценки чувствительности. Разработанный алгоритм реализован автором в виде программы mpao в среде MATLAB и апробирован на обширном экспериментальном материале. Показана простота процедуры ввода исходных данных и запуска программы. Установлено преимущество по быстродействию и широте выводимой информации программы mpao по сравнению с опцией симплекс-метода программы linprog библиотеки MATLAB на примерах задач с размерностями до 1000 х 1000. 1. Теоретическое обоснование алгоритма В евклидовом пространстве En решается задача линейного программирования в самой общей постановке с разделением ограничений на «многофакторные», содержащие несколько переменных, и «координатные» (однофакторные), устанавливающие диапазоны возможных изменений собственно переменных при допущении отрицательности и неограниченности всех фигурирующих здесь величин включая сами переменные: L(x) = cx ^ max, c, x E En, - to ^ b(i) ^ aix ^ b(i) ^ +to, ai=(a(1)... a(n)), i=1,..., m (многофакторные), (1) - to ^ d(j) ^ x(j) ^ d(j) ^ +to, j = 1,..., n (координатные). Здесь сам вектор нумеруется нижним индексом, а его координаты - верхним в скобках. Многофакторные и координатные ограничения, высекая в En многогранник допустимых решений (МДР) M, геометрически равнозначны. Первым отвечают гиперплоскости с задаваемой нормалями ai ориентацией в пространстве, а вторым - ортогональные осям координат. Равенства реализуются уравниванием значений нижней и верхней границ разрешённых изменений и в отдельную группу не выделяются. Равенствам отвечает размещение МДР в пересечении соответствующих гиперплоскостей, что открывает принципиальную возможность понижения размерности задачи за счёт фактического исключения (в отличие от симплекс-метода) части переменных. Это обстоятельство порождает две алгоритмические ветви. Следуя первой ветви, из равенства a(1)x(1) + ... + a(n)x(n) = b(i) выражается переменная с ненулевым коэффициентом; пусть это x(n) = а(1)x(1) + ... + a(n 1)ж(п-1) + a(n). При её исключении из остальных многофакторных ограничений и целевой функции координатное ограничение d(n) ^ x(n) ^ d(n) преобразуется в многофакторное неравенство в(п) ^ a(1)x(1) + ... + a(n 1)x(n-1) ^ в(п) с меньшим числом переменных. В итоге размерность пространства решений понижается, но только за счет переменных при сохранении количества многофакторных ограничений. Исключением равенств из системы условий заканчивается подготовительный шаг алгоритма. С этого момента МДР считается полноразмерным (dimM = n), т.е. задаётся только неравенствами. Особенности другой ветви алгоритма без исключения равенств из системы условий будут разъяснены позже. Совокупности неравенств в En отвечает выпуклый многогранник M. Её любая подсистема ранга n представляет собой неограниченный многогранник М(ж) D M с единственной вершиной в точке ж, являющейся решением соответствующей системы линейных равенств; пусть это ja^x = b(i) : i = 1,... ,n} .В параметрическом представлении M(x) = {ж = x + Е в?V(x), в? ^ 0, j = 1,... , n), (2) I j=1 J где Vj (x) - направляющие векторы рёбер Rj (x) = {x = X + tVj (x), t ^ 0} многогранника M, выходящих из вершины xx и образованных пересечением n - 1 гиперплоскоn стей GGi - ^ x : a^x - Тогда Rj (xx) = P| Gi и {xx} = Rj (xx) П Gj. Алгебраически i=1,i=j Rj (xx) = {x : aix = b(i), i = 1,... , n, i = j; ajx ^ b(j)}, где оно индексируется номером того единственного ограничения, которое в его образовании не участвует. Возьмём произвольную точку xj G Rj (xx) и построим вектор Vj (xx) = xj - xx, который, будучи направляющим вектором, удовлетворяет однородной системе ранга n - 1: |aiVj(xx) = aixj - aixx = b(i) - b(i) = 0, i = 1,..., j - 1, j + 1,..., n. Этот вектор ортогонален нормалям n- 1 гиперплоскостей и может быть найден с помощью алгоритма Грама - Шмидта, который линейно независимую совокупность векторов u1,..., un-1 G En рекуррентными соотношениями ортогонального проектирования u°=Mi, uk=uk-1- (uk-1ujk-1) uk-1, ui-1=ui-1/ || ui-1 ll, k < i < n (3) (k - «порядок» проекции) преобразует в ортонормированную систему {Ui-1, i = 1,... , n - 1 : Ui-1 uj-1 = }, - символ Кронекера. Очевидно, что при линейной независимости {uo, u1,... , un-1} решением системы {uiv = 0: i = 1,... , n - 1} будет вектор n- 1 ( ) v (u0,u1,... ,un-1) = -u0 + E (u0ui-1) ui-1, где векторы ui-1 вычислены проектором i=1 Грама - Шмидта (3). Легко проверяются такие свойства построенного вектора, как u0v < 0 и u^v = 0, i Е {1,... ,n - 1}. Поскольку вершина ж образована пересечением n гиперплоскостей, то, принимая поочередно в качестве u0 их нормали, можно найти все направляющие векторы. В такой схеме для каждого вектора строится своя матрица ортогонализации. Поэтому более эффективно работает приём с одноразовым обращением матрицы координат нормалей и принятием в качестве направляющих векторов её столбцов, взятых с обратным знаком. С ростом размерности задачи метод ортогона-лизации быстро уступает обращению матрицы, которое представляет собой механизм вычисления направляющих векторов, выходящих из вершины многогранника. Рассматриваемый метод опирается на общеизвестный факт достижения линейной функцией экстремума на выпуклом замкнутом многограннике по крайней мере в одной из его вершин. Метод реализует идею формирования из имеющихся ограничений начального многогранника M0, с гарантией содержащего оптимум задачи ж*, нахождения на нём оптимальной вершины ж* и построения последовательности оптимальных вершин ж* - ж* - ... - жт = ж* на промежуточных вложенных многогранниках M0 D M1 D ... D Mm = M. В этой цепочке текущий Mk получен усечением предыдущего Mfc_1 следующим k-м ограничением. В качестве M0 разумно принять ортогональный параллелепипед, образованный координатными ограничениями. В случае неопределённости какой-либо границы её значение сообразно конкретной ситуации полагается равным Если M = 0, то, безусловно, ж* Е M0. В силу структурной примитивности M0 максимум на нём линейной функции L достигается в вершине ж* = ^ж01) ,... , ж0п) ^, координаты которой (j)* ( d(j), если c(j) ^ 0, • определяются простым правилом: ж0 = < ^' ^ ' j = 1,... , n. I d ' , если c b), и незначимым в противном случае (аж ^ b). Значимость и незначимость гиперплоскости (равенства) G = {ж : аж = b} определяются через неравенство аж = b и равенство аж = b. В результате усечения M0 первым многофакторным двусторонним неравенством образуется многогранник M1 = M0 П P1 П P1, где P1, P1 -встречные полупространства с непустым пересечением: P1 = {ж : b(1) ^ а1 ж}, P1 = {ж : а1ж ^ b }. Поскольку M1 С M0, то maxL(#) ^ maxL(ж). Характер последующих действий определяется значимостью данного ограничения для ж0, т.е. расположением величины а1ж* относительно отрезка , b ]. Неравенство b(1) ^ а1ж0 ^ b означает, что ж0 Е M1, и потому максимум L на M1 достигается в той же самой вершине, т.е. ж* = ж*. Таким образом, данное ограничение для ж* незначимо и можно перейти к построению многогранника M2, усекая M1 следующим ограничением. В противном случае проверяется M1 = 0, вычисляется ж* и т.д. Рассмотрим k-й шаг алгоритма, к началу которого уже построен многогранник Mk_1 = M0 П P1 П P1 П ... П Pk-1 П Pk_1; пусть Mfc_1 = 0. Если ж^ Е Mfc, то _1 и текущий шаг на этом завершается. Остаётся разобраться с ситуацией (,) -(k) ж£_ 1 Е Mk. Здесь двустороннее неравенство b( ) ^ akж ^ b для вершины ж^ 1 может (k) _(k) быть не выполнено лишь с одной стороны и либо а^;ж^ 1 < b( ), либо akж^ 1 > b . Принципиального различия между типами этих двух неравенств нет, так как один сводится к другому умножением неравенства на -1. производятся основные рас- В случае значимости ограничения akxk_ 1 Ф b(k),b( ) чёты. Пусть для определённости Ф Pk, граница которого Gk = {ж : akж = b(k)}. Параметризуем статическое полупространство Pk = {ж : akж ^ b( ^, образовав динамическую структуру Pk(Л) = {ж : akж ^ Л}, Pk(b(k)) = Pk, Gk(Л) = {x : akж = Л}, Gk (b(k)) = Gk. -(k) Определение 2. Активацией значимого ограничения ak ж ^ b называется изменение параметра Л от до Ь ), в результате чего движение гиперплоскости (Gk(Л) влечёт трансформацию ж^ ^ xk. Активация ограничения - динамическая процедура его приведения в активное состояние в случае значимости. Под активностью ограничения P = {ж : ax ^ b} в точке ж традиционно понимается её принадлежность граничной гиперплоскости, т. е. ж Ф G = {ж : аж = b} или ax = b. Вычисление ж* составляет содержание «нулевого» шага алгоритма, на котором активированы только все координатные ограничения. Обозначим: {жж j : j = 1,...,r} - концевые точки рёбер R (xk_ 1) с направляющими векторами Vj (xk_ 1), являющиеся вершинами Mk-1, смежными с ж*_ 1; Pk(Л) = = {ж : ak ж ^ Л} - активируемое динамическое полупространство; Л* = ak xk_ 1; Л j = = akж,-; MMk(Л) = Mk-i П Pk(Л). _ Сигналом к активации многофакторного ограничения Pk является его значимость, и на k-м шаге этому отвечает решение задачи оптимизации L(xk(Л)) = max L(x), хемfc(A) ~ ~ -(k) ~ при том что Mk(Л) = Mk-1 ПP^k(Л), = Л ^ b . По построению Mk(Л) при всех Л из указанного диапазона относительно Mk-1 не расширяется и Mk (Л) С Mk-1, Mk (+^) = = Mk-1, Mk (b(k)) = Mk, ж*(b(k)) = жk. Полупространство Pk(Л) при Л ^ Л* = akxk-1 для xk_ 1 является незначимым. Его граница Gk (Л) при Л = Л* проходит через ж*_ 1, а при Л < Л* отвечает за трансформацию xk_ 1 ^ xk(Л). Теорема 1. Если akVj(xk-1) ^ 0 для всех j Ф {1,...,r}, то для всех Л < Л* система условий задачи (1) несовместна (M = 0). Доказательство. Для любого Л ^ Л* по построению Mk(Л) С Mk-1, и в соответствии с представлением (2) для любого P Ф Mk (Л) с учётом в ^ 0 для всех r j Ф {1,..., r} находим ak ж = ak xk-1 + ^ в ak Vj (xk-1) ^ ak x*-1 = Л*. Тогда ж ф Mk (Л) j=i при Л < Л*, т. е. Mk(Л) = 0, а вследствие M С Mk(Л) и M = 0. ■ Замечание 1. Здесь сформирован механизм выявления противоречивости системы условий задачи в процессе активации ограничений. Теорема 2. Пусть ж - вершина выпуклого многогранника M = 0 с направляющими векторами всех выходящих из неё рёбер vi(x),...,vr(ж). Максимум L = сж на M достигается в ж, если cvj (ж) ^ 0 для всех j; эта вершина единственна в случае cVj (ж) < 0 для всех j. Верно и обратное. Доказательство. Достаточность следует из (2). Из включения M С М(ж) поr лучаем, что сж = cxr + в cvj (ж) для всех ж Ф M. Учитывая существование хотя j=1 бы одного ek > 0 при ж = ж в случае cvk (ж) ^ 0, получаем сж ^ сжг, а при строгом неравенстве cvk (ж) < 0 таким же строгим будет неравенство сж < сжг. Необходимость докажем от противного. Пусть cX > cx для всех x Е M, но существует vk(X), для которого cvk(X) > 0. Так как x(t0) = X + t0vk(X) Е M при некотором малом t0 > 0, то cx(t0) = cX + t0cvk(X) > cX, что противоречит оптимальности X. Далее, предположив единственность оптимума и существование vk(X), для которого cvfc(X) = 0, получаем противоречие со сделанным предположением, поскольку cx(t0) = cX при x(t0) = X. ■ Замечание 2. Так фиксируется неединственность решения. Теорема 3. Если Mk = 0, то для любого Л Е (Л* - е, Л*}, где Л* = akxk-1, при достаточно малом е > 0 имеет место akXk(Л) = Л, чему геометрически соответствует Xk(Л) Е Gk(Л). Доказательство. Поскольку Xk(Л) Е Mk(Л), то akXk(Л) ^ Л. При допущении противного (Xk (Л) Е G k (Л)) это неравенство может быть только строгим (ak Xk (Л) < Л). Из Мд.(Л) С Mk-1 следует Xk (Л) Е Mk-1 и в силу выпуклости Mk-1 D [Xk ^),xk_ 1]. По условию Л < Л* и, следовательно, концевые точки отрезка Xk (Л) и xk_ 1 лежат строго по разные стороны гиперплоскости Gk(Л), а значит, существует xa Е (Xk(Л)^^), что xa Е G k (Л). В параметрическом представлении (Xk ^),xk_ 1) = (x(t) = Xk (Л) + t(xk_ 1 - - Xk (Л)) : t Е (0,1)}; тогда существует tA Е (0,1), при котором xA = x(tA) = Xk (Л) + -1-xk(Л)).Отсюда находим xk_ 1 = xk(Л)+to (xa-xk (Л)) to = 1/tA >1 Сделанное допущение Xk (Л) Е G k (Л) влечёт строгое неравенство cXk (Л) > cx для всех x Е G k (Л), в том числе cXk (Л) > cxA или c(xA - Xk (Л)) < 0. Посчитав cxk-1 = c(Xk (Л) + t0 (xA - - Xk (Л))) = cXk (Л) + t0c(xA - Xk (Л)) < cXk (Л), приходим к противоречию с оптимальностью xk_ 1 на Mk-1 э Xk (Л). ■ Замечание 3. Таким образом, если Mk = 0, то либо сохраняется оптимальность предыдущей вершины и xk = xk 1 , либо оптимальная вершина удовлетворяет активируемому ограничению как равенству с одной из его границ, что означает её принадлежность гиперплоскости Gk = {x : akx = b(k)} или Gk = {x : akx = Ь )}. Теорема 4. Если многогранник Mk = 0 и активируемое ограничение Pk = (x : -(k) г -(k) akx ^ b } значимо для xk-1, т. е. J = {j : akvj (xk-1) < 0} = 0 и akxk-1 > b , то в малой окрестности [/£(Л*) = (Л :0

Ключевые слова

линейное программирование, активация ограничения, MATLAB, компьютерный эксперимент, linear programming, activation of limitation, MATLAB, computer experiment

Авторы

ФИООрганизацияДополнительноE-mail
Колосов Вадим Сергеевичг. Москвакандидат технических наук, старший научный сотрудникvs.kolosov@yandex.ru
Всего: 1

Ссылки

Канторович Л. В. Математические методы в организации и планировании производства. Л.: Изв. Ленингр. гос. ун-та, 1939. 67с.
Данциг Дж. Линейное программирование, его применение и обобщения. М.: Прогресс, 1966. 600 с.
Юдин Д. Б., Гольштейн Е. Г. Линейное программирование: теория, методы и приложения. М.: Наука, 1969. 424 с.
Дикин И. И. Итеративное решение задач линейного и квадратичного программирования // Докл. АН СССР. 1967. Т. 174. С. 747-748.
Хачиян Л. Г. Полиномиальный алгоритм в линейном программировании // Докл. АН СССР. 1979. Т. 244. С. 1093-1096.
Зоркальцев В. И. Двойственные алгоритмы внутренних точек // Изв. вузов. Математика. 2011. №4. С. 33-53.
Зоркальцев В. И., Медвежонков Д. С. Численные эксперименты с вариантами алгоритмов внутренних точек на нелинейных задачах потокораспределения // Управление большими системами. Ин-т систем энергетики им. Л. А. Мелентьева СО РАН, 2013. Вып. 46. С.68-87.
Медвежонков Д. С. Экспериментальные исследования алгоритмов внутренних точек на нелинейных задачах потокораспределения // Вестник Бурятского гос. ун-та. 2013. №9. С. 12-16.
Вылегжанин О. Н., Шкатова Г. И. Решение задачи линейного программирования с использованием оператора-проектора // Изв. Томского политехн. ун-та. 2009. Т. 314. №5. С.37-40.
Бахшиян Б. Ц., Гориянов А. В. Скелетный алгоритм решения задачи линейного программирования и его применение для решения задач оценивания // Вестник МАИ. 2008. Т. 15. №2. С. 5-16.
Гордуновский В. М. Метод экспоненциальной аппроксимации для линейного программирования. М.: Эдитус, 2013. 32 с.
Колосов В. С. Конечный параметрический метод решения задачи линейного программирования // Науч. труды МЛТИ. 1978. Вып. 103. С. 197-198.
Колосов В. С. Роль двойственных оценок в параметрическом методе решения задачи линейного программирования // Науч. труды МЛТИ. 1986. Вып. 183. С. 51-54.
Карманов В. Г. Математическое программирование. М.: ФИЗМАТЛИТ, 2004. 264 с.
 Метод последовательной активации ограничений в линейном программировании | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/11

Метод последовательной активации ограничений в линейном программировании | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/11