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

У нас уже 21989 рефератов, курсовых и дипломных работ

Сделать закладку на сайт

Заказать диплом, курсовую, диссертацию

Быстрый переход к готовым работам

Мнение посетителей:

Книга жалоб
и предложений

Название	Методы решения задач линейной оптимизации Большой размерности

Количество страниц	91

ВУЗ	МГИУ

Год сдачи	2010

Бесплатно Скачать	23545.doc

Содержание	Содержание ОГЛАВЛЕНИЕ ВВЕДЕНИЕ 7 1. МЕТОД РЕШЕНИЯ ПРЯМОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С БОЛЬШИМ ЧИСЛОМ НЕОТРИЦАТЕЛЬНЫХ ПЕРЕМЕННЫХ 13 1.1. Нахождение проекции точки на множество решений прямой задачи линейного программирования ... 13 1.2. Итерационный метод нахождения решений прямой и двойственной задач (метод ПД)... 23 1.3. Конечная сходимость итерационного метода ... 26 1.4. Обобщенный метод Ньютона... 28 1.5. Нахождение проекции точки на множество решений систем линейных уравнений ... 29 2. МЕТОД РЕШЕНИЯ ДВОЙСТВЕННОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С БОЛЬШИМ ЧИСЛОМ ПЕРЕМЕННЫХ 31 2.1. Нахождение проекции точки на множество решений двойственной задачи линейного программирования... 31 2.2. Итерационный метод нахождения решений двойственной и прямой задач (метод ДП) ... 38 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ 40 3.1. Генераторы тестовых задач... 40 3.2. Программная реализация метода ПД в системе MATLAB... 44 3.3. Результаты численных экспериментов с программой EGM1... 46 3.4. Программная реализация метода ДП в системе MATLAB... 62 3.5. Результаты численных экспериментов с программой EGM2... 63 3.6. Результаты численных экспериментов с помощью программ нахождения нормальных решений линейных систем 69 ВЫВОДЫ 74 ПРИЛОЖЕНИЕ 75 ЦИТИРОВАННАЯ ЛИТЕРАТУРА 91 Список обозначений Rn - множество п-мерных вещественных векторов Я? - множество п-мерных вещественных векторов, все компоненты которых неотрицательные 0 - пустое множество 0п - п-мерный нулевой вектор ап - п-мерный вектор, все компоненты которого равны скаляру а А — матрица т X п АТ - матрица, транспонированная к матрице А Ь - вектор т х 1 с - вектор п х 1 х € X - х принадлежит множеству X х - вектор прямых переменных п X 1 X - допустимое множество прямой задачи ЛП X* - множество решений прямой задачи х* - решение прямой задачи ?* - проекция произвольной точка х G Rn на множество решений X* ж* - проекция начала координата на множество решений X, т.е. нормальное решение прямой задачи ЛП (решение с наименьшей евклидовой нормой) и - вектор двойственных переменных т х 1 U - допустимое множество двойственной задачи ЛП Vi, - множество решений двойственной задачи и - решение двойственной задачи й* - проекция произвольной точка й Е Rm на множество решений U* й* - проекция начала координата на множество решений 17, т.е. нормальное решение двойственной задачи ЛП / - оптимальное значение целевой функции задачи ЛП v - неотрицательный вектор дополнительных переменных (v = c-ATu> 0). xTv - скалярное произведение векторов х и v /?, а - вспомогательные параметры е - параметр регуляризации D(z) - диагональная матрица, у которой г—й диагональный элемент есть г—я компонента вектора z -D" - диагональная матрица в обобщенную матрицу Гессе а+ - вектор а, у которого все отрицательные компоненты заменены на нули \|\|а\|\| - евклидова норма вектора а \|\|а\|\|оо ~~ чебышевская норма вектора а ЛП - линейное программирование Р - прямая задача ЛП D - двойственная задача ЛП ПД - метод нахождения решений прямой и двойственной задач ДП - метод нахождения решений двойственной и прямой задач Список программ, составленных для системы MATLAB Code 1 - Генератор тестовых задач линейного программирования . . 41 Code 2 - Генератор тестовых задач линейного программирования с целочисленными элементами...42 Code 3 - Генератор линейных систем уравнений с неотрицательными переменными...43 Code 4 - Генератор линейных систем уравнений...44 Code 5 - Программа EGM1 для решение задач ЛП...45 Code б - Программа EGM2 для решения задач ЛП...62 Code 7 - Программа SS1 для решения линейных систем...70 Code 8 - Программа SS2 для решения линейных систем с неотрицательными переменными...71 ВВЕДЕНИЕ Теории и методам решения задач линейного программирования (ЛП) и систем линейных неравенств посвящено огромное количество исследований. Укажем лишь несколько опубликованных на русском языке мо-нографий [2], [4], [5], [13], [18] - [22], [26], [29], [30], [33], [36], [42], [43]. Огромный интерес к задачам ЛП определяется прежде всего их экономической содержательностью, многочисленными практическими приложениями и применением в качестве вспомогательных процедур во многих численных методах нелинейной оптимизации. Несмотря на продолжающееся повышение производительности вычислительной техники, всегда актуальным остается возможность решения задач линейного программирования очень большой размерности. Первоначально исследования в области численных методов ЛП концентрировались в основном на симплекс-методе. Далее разрабатывались разнообразные итерационные методы, а после опубликования статей [24], [14], [15], [16], [52] внимание многих исследователей переключилось на методы внутренних точек. При этом возникли новые формулировки задач ЛП и появились новые формы задания необходимых и достаточных условий оптимальности (см. например, [60], [17], [49]). Укажем на специальный выпуск журнала Optimization Methods & Software [61], целиком посвященный методу внутренней точки, а также обзор [50]. В работах советских математиков в 70-х годах активно разрабатывался подход к задачам ЛП, основанный на использовании метода внешних штрафных функций (квадратичная функция штрафа). Хорошо известны работы в этом направлении, которые проводились А.С. Антипиным, Ф.П. Васильевым, Е.Г. Голыптейном, И.И. Ереминым, Б.Т. Поляком, Б.С. Разумихиным, Н.В. Третьяковым и другими исследователями из МГУ, ИПУ, ЦЭМИ, ИММ УрО РАН, ВЦ РАН [3], [13], [51], [32]-[35], [42], [44]. Примерно в это же время в США близкие исследования проводились О.Мангасарьяном и его сотрудниками. В их работах [53]-[55] основное внимание уделялось нахождению нормальных решений в задачах ЛП, т.е. решений, обладающих минимальной евклидовой нормой. Широкое распространение этот подход в то время не получил. Только в последнее время появились свидетельства о его перспективности с вычислительной точки зрения [57], [58]. Связано это с использованием быстро сходящегося обобщенного метода Ньютона для минимизации выпуклой кусочно квадратичной непрерывно дифференцируемой штрафной функции. У нее не существует матрица Гессе. Однако для такой штрафной функции можно построить обобщенный метод Ньютона, введя обобщенную матрицу Гессе. В работах [57], [58], [51] доказана конечная глобальная сходимость обобщенного метода Ньютона для минимизации выпуклой кусочно квадратичной функции. Минимизация этой штрафной функции, примененной к двойственной задаче ЛП, дает возможность получить точное нормальное (с минимальной евклидовой нормой) решение прямой задачи, начиная с некоторого конечного значения коэффициента штрафа. Заметим, что, как правило, большие задачи ЛП имеют не единственное решение. Указанные методы представляют ценность тем, что дают различные решения в случае неединственности. Так, симплекс-метод дает решение, которое принадлежит вершине многогранного множества. Методы внутренней точки сходятся к решению, в котором выполнено условие строгой дополняющей нежесткости. Метод квадратичной штрафной функции, будучи примененным к двойственной задаче, дает возможность получить нормальное решение прямой задачи при конечном значении коэффициента штрафа. Весьма актуальным является обобщение метода квадратичной штрафной функции для получения проекции произвольной точки на множество решений прямой или двойственной задач Л П. Задача нахождения проекции заданной точки на множество решений часто может иметь важный содержательный смысл для приложений. Так, пусть известен некоторый оптимальный план, который из-за изменившихся условий уже не только не оптимальный, но может даже оказаться и недопустимым. Желательно найти такой новый оптимальный план, который был бы ближайшим к первоначальному плану. Работа посвящена созданию методов нахождения проекции заданной точки на множество решений задачи ЛП с большим числом переменных, программной реализации, проведению вычислительных экспериментов (в том числе и на практической задаче). В главе 1 предлагается метод решения прямой задачи ЛП с большим числом (до нескольких десятков миллионов) неотрицательных переменных и средним числом ограничений-равенств (несколько тысяч). В §1.1 рассматривается задача нахождения проекции заданной точки на множество решений прямой задачи. Вместо обычно применяемой кусочно квадратичной штрафной функции предлагается использовать вспомогательную функцию, сходную с модифицированной функцией Лагранжа (см., например [31], [1]), зависящую от некоторого параметра /3. Этот подход характеризуется следующим: начиная с некоторого фиксированного значения параметра /3* после однократной безусловной максимизации вспомогательной функции при всех (3 > (3* по простой формуле вычисляется точная проекция заданной точки на множество решений прямой задачи ЛП (теорема 1.1). В этой теореме при определенных предположе-нях получена формула для порогового значения /3. Эта величина может быть отрицательна. В этом случае расстояние от заданной проектируемой точки до множества решений прямой задачи совпадает с расстоянием от этой точки до допустимого множества прямой задачи. Показана связь предложенной вспомогательной функции с методами регуляризации и квадратичным штрафом, примененным к двойственной задаче. Подставляя найденную проекцию во вспомогательную функцию и, максимизируя ее, находим некоторое точное решение двойственной задачи ЛП (теорема 1.2). В §1.2 приводится итерационный метод нахождения решений прямой и двойственной задач Л П. Этот метод является прямым-двойственным методом (ПД-метод). В процессе итераций метод дает допустимые прямые точки и недопустимые двойственные. Формально в нем не требуется знания порогового значения параметра /?+. Но, если выбранное значение (3 меньше порогового значения, то метод решает задачу ЛП более, чем за две итерации. Метод за конечное число шагов находит некоторое решение прямой задачи, но не проекцию начальной точки на множество решений прямой задачи. При некоторых дополнительных предположениях доказана сходимость метода и в §1.3. Доказана конечная сходимость. В §1.4 приводятся сведения об обобщенном методе Ньютона ([57], [58], [51]), который рекомендуется применять для безусловной максимизации вспомогательной функции, если прямая задача ЛП имеет среднее число ограничений (до 4 тыс.). Обобщенный метод Ньютона для данной задачи глобально сходится за конечное число шагов. В §1.5 предложенный метод переносится на задачу нахождения проекции заданной точки на множество решений систем линейных уравнений с неотрицательными переменными. Во второй главе рассматривается аналогичный подход для решения двойственных задач ЛП с большим числом переменных (до нескольких десятков миллионов) и средним числом ограничений-неравенств (до 4 тыс.). Здесь модифицированная функция Лагранжа зависит от параметра а. В §2.1 приводится оценка для порогового значения параметра а, начиная с которого, в результате однократной максимизации вспомогательной функции на положительном ортанте, находится точная проекция заданной точки на множество решений двойственной задачи. В §2.2 приводится итерационный метод решения двойственной и прямой задач (метод ДП). В процессе итераций получаются допустимые двойственные точки и недопустимые прямые. Как и в первой главе, этот метод может быть использован со значением параметра а, меньшим, чем пороговое значение. Однако расчеты при этом не дают проекцию начальной точки на множество решений двойственной задачи. В этом методе максимизация производится на положительном ортанте. Для снятия ограничений на знак переменных применялась квадратичная штрафная функция. Это позволило здесь так же применить обобщенный метод Ньютона. Глава 3 посвящена программной реализации и вычислительным экспериментам. В §3.1 приведено описание генераторов задач линейного программирования Code I, Code 2 и генератора систем линейных уравнений с неотрицательными переменными Code 3. Для систем, генерируемых случайным образом, известны нормальные решения. Приводятся программы генераторов задач, написанных для системы MATLAB. В §3.2 содержится описание программы EGM1 - итерационного метода ПД из первой главы, реализованного в системе MATLAB. В §3.3 в таблицах 3.1-3.8 даны результаты численных экспериментов с программой EGM1. Расчеты проведены, в основном, на компьютере PENTIUM-IV с 1Гб оперативной памяти со случайно сгенерированными задачами ЛП и показали высокую эффективность метода при решении задач с большим числом неотрицательных переменных (решались задачи до 50 миллионов переменных) и средним числом ограничений-равенств (до 4 тысяч). Время решения таких задач составляло от нескольких десятков секунд до нескольких часов. Такие впечатляющие результаты объясняются тем, что основная вычислительная трудность предлагаемого метода приходилась на решение вспомогательных задач безусловной максимизации. Их размерность определялась количеством ограничений типа равенств, число которых существенно меньше, чем число переменных в исходной задаче ЛП и поэтому они сравнительно просто решались обобщенным методом Ньютона. Приведено сравнение программы EGM1 с некоторыми известными зарубежными исследовательскими и коммерческими пакетами. Результаты свидетельствуют о конкурентноспособности программы EGM1 на небольших задачах, сгенерированных программой Code 2 и явном преимуществе программы EGM1 в случае задач большой размерности, которые не удалось решить другими пакетами. В §3.4 и §3.5 приведена программа EGM2, реализующая итерационный метод ДП, и даны результаты численных экспериментов со случайным образом сгенерированными задачами ЛП. В §3.6 представлены результаты численных экспериментов с программами нахождения нормального решения систем линейных уравнений с неотрицательными переменными. Сопоставлялись результаты работы метода из §1.5 и метода, основанного на теоремах об альтернативах [7]-[9]. На рисунках 3.1 - 3.6 даны зависимости времени счета, числа итераций и количества шагов, суммарной невязки от параметра /3, полученные по программе EGM1. На рисунках 3.7 - 3.9 приведены аналогичные графики для метода ДП, полученные по программе EGM2. В приложении дано описание практической задачи определения оптимального состава машинно-тракторного парка и результаты счета с помощью программы EGM1. ГЛАВА 1. МЕТОД РЕШЕНИЯ ПРЯМОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С БОЛЬШИМ ЧИСЛОМ НЕОТРИЦАТЕЛЬНЫХ ПЕРЕМЕННЫХ 1.1. Нахождение проекции точки на множество решений прямой задачи линейного программирования Для решения прямой и двойственной задач линейного программирования (ЛП) предлагается использовать новую вспомогательную функцию, близкую к модифицированной функции Лагранжа, и применить обобщенный метод Ньютона для безусловной максимизации этой функции. Предлагаемый подход применим для решения задач ЛП с большим числом (несколько десятков миллионов) неотрицательных переменных и средним числом (несколько тысяч) ограничений типа равенств. Результаты тестовых расчетов на компьютере P-IV показали, что задачи указанных размерностей решаются за время от нескольких десятков секунд до нескольких часов. Пусть задана прямая задача ЛП в стандартной форме /* = min стх} X = {х в Rn : Ах = Ь, х > 0n}. (P) Двойственная к ней имеет вид /, = max bTu, U = {ueRm : Ати < с}. (D) Здесь А ? Rmxn, с G Rn и Ь G Rm заданы, х - вектор прямых переменных, an- двойственных, через 0$ обозначен г-мерный нулевой вектор. Предположим, что множество решений X* прямой задачи (Р) непусто, следовательно, множество решений U* двойственной задачи (D) также непусто. Необходимые и достаточные условия оптимальности (условия Куна-Таккера) для задач (Р) и (D) запишем в виде Ах* — b = Qm, ж* > 0n, xjv* = 0, (1.1) v* = с-Атщ >0п. (1.2) Здесь в ограничения двойственной задачи (D) введен неотрицательный вектор дополнительных переменных v = с — Ати > 0п. Пусть задан произвольный вектор х € Rn. Рассмотрим задачу нахождения проекции х* этой точки х на множество решений X* прямой задачи (Р) -\\х-х\\2 = min -Ь-ж\|\|2, (1.3) 2" " х<=х. 2" " к J X = {x€Rn : Ax = Ъ, стх = /», х > 0п}. Здесь и всюду ниже, если не оговорено иное, используется евклидова норма векторов. Введем функцию Лагранжа для задачи (1.3) где р € i?m и /3 6 i?1 есть множители Лагранжа, а ? будем считать фиксированным вектором параметров. Двойственная к (1.3) задача имеет вид max max min L(x,p,6,x). (1.4) p<=r™, р&в> xgri v ' v ' Запишем условия Куна-Таккера для задачи (1.3) х-х- Атр + /3с> On, D(x)(x-x-ATp + l3c) = 0„, ж > 0„, (1.5) Ах = 6, стх = Д, (1.6) где через -D(z) обозначена диагональная матрица, у которой г-й диагональный элемент есть г-я компонента вектора z. Легко проверить, что формулы (1.5) эквивалентны выражению x = (x + ATp-j3c)+1 (1.7) где а+ обозначает вектор а, у которого все отрицательные компоненты заменены на нули. Формула (1.7) дает решение внутренней задачи минимизации в задаче (1.4). Подставляя (1.7) в функцию Лагранжа L(x,p,(3,x), получаем двойственную функцию L(p, /?, х) = Ътр - i\|\|{х + Лтр - /Зс)+\|\|2 -15U + ipll2- Функция L(p,/3} х) вогнута, кусочно квадратична и непрерывно дифференцируема по своим переменным р и /3. Двойственная задача (1.4) сводится к решению внешней задачи максимизации max max Ь(р,в,х). (1-8) PeRm /зея1 v J Решив задачу (1.8), найдем оптимальные р и /3. После их подстановки в (1.7) получаем проекцию ?, т.е. решение задачи (1.3). Необходимые и достаточные условия оптимальности для задачи (1.8) имеют вид 3,x) = Ь - А(х + Атр - /Зс)+ = Ъ - Ах = 0т, , Р, ) = сТ(х + Атр - рс)+ - /• = стх - /* = О, где х определен формулой (1.7). Эти условия выполнены тогда и только тогда, когда х G X* и х = х. К сожалению, задача безусловной оптимизации (1.8) содержит неизвестную априори величину /+ - оптимальное значение целевой функции задачи ЛП. Однако задачу (1.8) можно упростить, избавившись от этого недостатка. Для этого вместо (1.8) предлагается решать следующую упрощенную задачу безусловной максимизации h = max S(p,P,x), (1.9) peRm где вектор х и скаляр (3 фиксированы, а функция S(p, /3, х) определена следующим образом Sfa№) =ЬТР-Ых + ATp-Pc)+f. (1.10) Без потери общности предположим, что первые I компонент вектора ? строго больше нуля. В соответствии с этим предположением представим векторы ?, х и с, а также матрицу А в виде х1 = [&1Т,х?], хт = [xlT,xdT], cT = [ciT,cdT], A = [A,\ А], (1.11) где х{ > О/, xi = Od, d = п — I. В этих обозначениях необходимые и достаточные условия оптимальности (1.5), (1.6) для задачи (1.3) можно переписать в развернутом виде х{ =xl + Ajp - /Зс1 > 0/, (1.12) xf = Od, xd + Ajp - j3cd < 0d, (1.13) Aix\ = 6, c1 x\ = /. В (1.12) линейная система уравнений относительно неизвестных р совместна, поэтому, если предположить, что матрица А\ имеет полный ранг m и I > т, то единственное решение р этой системы дается формулой р = (AAjy'Mxi -xl + (Зс1). (1.14) Подставляя эту формулу в (1.13), получаем неравенство q < pz, (1.15) где введены обозначения q = xd + Aj(AiAj)~1Ai(x[ — х1) и z = cd — Если р определено согласно (1.14) и (3 удовлетворяет неравенству (1.15), то пара [р, /3] является решением двойственной задачи (1.8). Найдем минимальное значение /3, при котором выполнено неравенство (1.15). В соответствие с разбиением (1.11) оптимальный вектор дополнительных переменных г> из условий Куна-Таккера (1.1), (1.2) для задач (Р) и (D) представим в виде t>7 = [v[ ,vd ]. Тогда, согласно условию дополняющей нежесткости xjv* = 0, х* > 0n, v+ > 0n, выражение (1.2) запишется в виде v[ = с1 - Aju* = Of, (1.16) v* = cd- Aju* > 0* (1.17) Из (1.16) получаем it* = {AiA[)~lAid. Подставляя это выражение в (1.17), получаем vd = z > 0^. Определим следующее индексное множество: а = {1 + 1<г<п : (vd)1 > 0}. Если а = 0, то (1.15) выполнено при любом р. Определим 4 если 0 • (1Л8) 7> —со, если а = 0, где 7 - произвольное число. Тогда неравенство (1.15) имеет место при любом /3 > /?* и можно решать упрощенную задачу безусловной максимизации (1.9). Ее решение одновременно дает решение двойственной задачи (1.8). Далее, используя формулу (1.7), получаем проекцию ?. Итак, справедлива следующая Теорема 1.1. Пусть множество решений X задачи (Р) непусто, ранг матрицы А[, соответствующий ненулевым компонентам вектора ж; равен т. Тогда при любом /3 > /3 проекция точки х на множество решений X* прямой задачи (Р) определяется по формуле х* = (х + АТр{(3)-/Зс)+, (1.19) где р(/3) - решение задачи безусловной максимизации (1.9). Эта теорема позволяет заменить задачу (1.8), содержащую априори неизвестное число /, на задачу (1.9), в которой вместо этого числа фигурирует полуинтервал [/?, +оо), что существенно проще с вычислительной точки зрения. Теорема обобщает результаты, полученные в [6] и посвященные нахождению нормального решения прямой задачи ЛП (проекции нуля на множество решений задачи (Р)). Очевидно, что значение Д», найденное из формулы (1.18), может быть отрицательным. Соответствующий пример нахождения проекции начала координат приведен в Формально задача безусловной максимизации (1.9) не имеет функции Лагранжа и, следовательно, соответствующая двойственная задача не может быть построена. Но можно ввести в задачу (1.9) дополнительные переменные и с их помощью сконструировать искусственные ограничения, т.е. получить эквивалентную задачу нелинейного программирования, для которой уже можно построить двойственную задачу. Такое построение двойственной задачи не является общепринятым, оно основано на двухшаговом представлении задачи (1.9) (см., например [23],[8]).

Список литературы

Цена, в рублях: (при оплате в другой валюте, пересчет по курсу центрального банка на день оплаты)	1425

Скачать бесплатно	23545.doc

Найти готовую работу

ЗАКАЗАТЬ

Обратная связь:

Связаться

Вход для партнеров

Регистрация

Восстановить доступ

Материал для курсовых и дипломных работ

03.11.24 Лексикографический анализ единиц поля

03.11.24 Из истории слова гость и его производных

03.11.24 Семантическое поле гость в русском языке

Архив материала для курсовых и дипломных работ

Ссылки:

Счетчики:

© 2006-2024. Все права защищены.
Выполнение уникальных качественных работ - от эссе и реферата до диссертации. Заказ готовых, сдававшихся ранее работ.